Некоммутативная криптография

Некоммутативная криптография является областью криптологии , где криптографические примитивы , методы и системы основаны на алгебраических структуры , как полугруппы , группы и кольца , которые некоммутативные . Одним из первых применений некоммутативной алгебраической структуры для криптографических целей было использование групп кос для разработки криптографических протоколов. Позже несколько других некоммутативных структур, таких как группы Томпсона , полициклические группы , группы Григорчука и матричные группыбыли определены как потенциальные кандидаты для криптографических приложений. В отличие от некоммутативной криптографии, широко используемые в настоящее время криптосистемы с открытым ключом, такие как криптосистема RSA , обмен ключами Диффи – Хеллмана и криптография на основе эллиптических кривых , основаны на теории чисел и, следовательно, зависят от коммутативных алгебраических структур.

Некоммутативные криптографические протоколы были разработаны для решения различных криптографических проблем, таких как обмен ключами , шифрование- дешифрование и аутентификация . Эти протоколы очень похожи на соответствующие протоколы в коммутативном случае.

Некоторые некоммутативные криптографические протоколы [ править ]

В этих протоколах было бы предположить , что G является неабелева группой. Если w и a являются элементами G, запись w ^a будет указывать на элемент a ⁻¹ wa .

Протоколы обмена ключами [ править ]

Протокол, принадлежащий Ко, Ли и др. [ редактировать ]

Следующий протокол, разработанный Ко, Ли и др., Устанавливает общий секретный ключ K для Алисы и Боба .

1. Публикуется элемент w группы G.
2. Две подгруппы А и В из G , такие , что абы = Ьы для всех а в A и B в B опубликованы.
3. Алиса выбирает элемент a из A и отправляет w ^a Бобу. Алиса держит в секрете.
4. Боб выбирает элемент b из B и отправляет w ^b Алисе. Боб держит b в секрете.
5. Алиса вычисляет K = ( w ^b ) ^a = w ^ba .
6. Боб вычисляет K ' = ( w ^a ) ^b = w ^ab .
7. Поскольку ab = ba , K = K ' . Алиса и Боб делят общий секретный ключ K .

Протокол Аншель-Аншель-Гольдфельд [ править ]

Этот протокол обмена ключами с использованием неабелевых группы G . Это важно, потому что не требует двух коммутирующих подгрупп A и B группы G, как в случае протокола Ко, Ли и др.

1. Элементы a ₁ , a ₂ ,. . . , а _к , б ₁ , б ₂ ,. . . , b _m из G выбраны и опубликованы.
2. Алиса выбирает частную й в G как слова в виде ₁ , ₂ ,. . . , a _k ; то есть x = x ( a ₁ , a ₂ , ..., a _k ).
3. Алиса посылает б ₁ ^х , б ₂ ^х ,. . . , b _m ^x Бобу.
4. Боб выбирает частное y в G как слово в b ₁ , b ₂ ,. . . , б _м ; то есть y = y ( b ₁ , b ₂ , ..., b _m ).
5. Боб посылает на ₁ ^у , а ₂ ^у ,. . . , _К ^у Алисе.
6. Алиса и Боб используют общий секретный ключ K = x ⁻¹ y ⁻¹ xy .
7. Алиса вычисляет x ( a ₁ ^y , a ₂ ^y , ..., a _k ^y ) = y ⁻¹ xy . Предварительно умножив его с й ^-1 , Алиса получает K .
8. Боб вычисляет y ( b ₁ ^x , b ₂ ^x , ..., b _m ^x ) = x ⁻¹ yx . Предварительно умножив его у ^-1 , а затем принимать обратное, Боб получает K .

Протокол обмена ключами Stickel [ править ]

В первоначальной формулировке этого протокола использовалась группа обратимых матриц над конечным полем .

1. Пусть G - открытая неабелева конечная группа .
2. Пусть a , b - открытые элементы группы G такие, что ab ≠ ba . Пусть порядки a и b равны N и M соответственно.
3. Алиса выбирает два случайных числа n < N и m < M и отправляет Бобу u = a ^m b ⁿ .
4. Боб выбирает два случайных числа r < N и s < M и отправляет v = a ^r b ^s Алисе.
5. Общий ключ, которым пользуются Алиса и Боб, - это K = a ^{m + r} b ^{n + s} .
6. Алиса вычисляет ключ по формуле K = a ^m vb ⁿ .
7. Боб вычисляет ключ по K = a ^r ub ^s .

Протоколы для шифрования и дешифрования [ править ]

Этот протокол описывает, как зашифровать секретное сообщение, а затем расшифровать его с помощью некоммутативной группы. Пусть Алиса хочет отправить секретное сообщение m Бобу.

1. Пусть G - некоммутативная группа. Пусть и B публичные подгруппы G такие , что абы = Ьо для всех а в А и Ь в В .
2. Выбирается и публикуется элемент x из G.
3. Боб выбирает секретный ключ b из A и публикует z = x ^{b в} качестве своего открытого ключа.
4. Алиса выбирает случайное r из B и вычисляет t = z ^r .
5. Зашифрованное сообщение является С = ( х ^г , Н ( т ) м ), где Н некоторая хэш - функция и обозначает XOR операцию. Алиса отправляет C Бобу.${\displaystyle \oplus }$ ${\displaystyle \oplus }$
6. Чтобы расшифровать C , Боб восстанавливает t следующим образом: ( x ^r ) ^b = x ^rb = x ^br = ( x ^b ) ^r = z ^r = t . Обычное текстовое сообщение, отправленное Алисой, имеет вид P = ( H ( t ) m ) H ( t ) = m .${\displaystyle \oplus }$ ${\displaystyle \oplus }$

Протоколы для аутентификации [ править ]

Пусть Боб хочет проверить, действительно ли отправителем сообщения является Алиса.

1. Пусть G быть некоммутативное группа и и B подгруппы группы G такие , что AB = Ьа для всех а в A и B в B .
2. Выбирается и публикуется элемент w из G.
3. Алиса выбирает частный s из A и публикует пару ( w , t ), где t = w ^s .
4. Боб выбирает r из B и отправляет Алисе запрос w '= w ^r .
5. Алиса отправляет Бобу ответ w '' = ( w ') ^s .
6. Боб проверяет, является ли w '' = t ^r . Если это правда, то личность Алисы установлена.

Основа безопасности протоколов [ править ]

Основой безопасности и надежности различных протоколов, представленных выше, является сложность следующих двух проблем:

• Проблема решения сопряженности (также называемая проблемой сопряженности ): для двух элементов u и v в группе G определите, существует ли в G элемент x такой, что v = u ^x , то есть такой, что v = x ⁻¹ ux .
• Задача поиска сопряженности : для заданных двух элементов u и v в группе G найти такой элемент x в G , что v = u ^x , то есть такой, что v = x ⁻¹ ux .

Если не известен алгоритм решения задачи поиска сопряженности, то функцию x → u ^x можно рассматривать как одностороннюю .

Группы платформ [ править ]

Некоммутативная группа, которая используется в конкретном криптографическом протоколе, называется группой платформ этого протокола. Только группы, обладающие определенными свойствами, могут использоваться в качестве групп платформы для реализации некоммутативных криптографических протоколов. Пусть G - группа, предлагаемая в качестве платформенной группы для некоторой некоммутативной криптографической системы. Ниже приведен список свойств , ожидаемых от G .

1. Группа G должна быть хорошо известна и изучена.
2. Проблема слов в G должна иметь быстрое решение с помощью детерминированного алгоритма. Для элементов группы G должна существовать эффективно вычислимая «нормальная форма» .
3. Восстановить множители x и y из произведения xy в G должно быть невозможно .
4. Число элементов длины n в G должно расти быстрее, чем любой многочлен от n . (Здесь «длина n » - это длина слова, представляющего элемент группы.)

Примеры групп платформ [ править ]

Группы кос [ править ]

Пусть n - натуральное число. Группа кос B _n - это группа, порожденная элементами x ₁ , x ₂ ,. . . , x _{n -1,} имеющий следующее представление:

${\displaystyle B_{n}=\left\langle x_{1},x_{2},\ldots ,x_{n-1}{\big |}x_{i}x_{j}=x_{j}x_{i}{\text{ if }}|i-j|>1{\text{ and }}x_{i}x_{j}x_{i}=x_{j}x_{i}x_{j}{\text{ if }}|i-j|=1\right\rangle }$

Группа Томпсона [ править ]

Группа Томпсона - это бесконечная группа F, имеющая следующее бесконечное представление:

${\displaystyle F=\left\langle x_{0},x_{1},x_{2},\ldots {\big |}x_{k}^{-1}x_{n}x_{k}=x_{n+1}{\text{ for }}k<n\right\rangle }$

Группа Григорчука [ править ]

Пусть T обозначает бесконечное корневое двоичное дерево . Множество V вершин - это множество всех конечных двоичных последовательностей. Пусть ( T ) обозначим множество всех автоморфизмов Т . (Автоморфизм T переставляет вершины, сохраняя связность.) Группа Григорчука Γ - это подгруппа в A ( T ), порожденная автоморфизмами a , b , c , d, определенными следующим образом:

• ${\displaystyle a(b_{1},b_{2},\ldots ,b_{n})=(1-b_{1},b_{2},\ldots ,b_{n})}$
• ${\displaystyle b(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},c(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}}$
• ${\displaystyle c(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},d(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}}$
• ${\displaystyle d(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},b(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}}$

Группа Артина [ править ]

Группа Артина A (Γ) - это группа со следующим представлением:

${\displaystyle A(\Gamma )=\left\langle a_{1},a_{2},\ldots ,a_{n}|\mu _{ij}=\mu _{ji}{\text{ for }}1\leq i<j\leq n\right\rangle }$

где ( факторы) и .${\displaystyle \mu _{ij}=a_{i}a_{j}a_{i}\ldots }$${\displaystyle m_{ij}}$${\displaystyle m_{ij}=m_{ji}}$

Группы матриц [ править ]

Пусть F - конечное поле. Группы матриц над F использовались в качестве платформенных групп некоторых некоммутативных криптографических протоколов.

Полупрямые продукты [ править ]

^[1]

См. Также [ править ]

• Групповая криптография

Дальнейшее чтение [ править ]

1. Алексей Мясников; Владимир Шпильрайн; Александр Ушаков (2008). Групповая криптография . Берлин: Birkhäuser Verlag.
2. Чжэньфу Цао (2012). Новые направления современной криптографии . Бока-Ратон: CRC Press, Taylor & Francis Group. ISBN 978-1-4665-0140-9.
3. Бенджамин Файн; и другие. (2011). «Аспекты криптографии на основе неабелевых групп: обзор и открытые проблемы». arXiv : 1103.4093 [ cs.CR ].
4. Алексей Г. Мясников; Владимир Шпильрайн; Александр Ушаков (2011). Некоммутативная криптография и сложность теоретико-групповых задач . Американское математическое общество. ISBN 9780821853603.

Ссылки [ править ]