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

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

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

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

В этих протоколах предполагается, что грамм это неабелев группа. Если ш и а являются элементами грамм обозначение ш^а укажет элемент а⁻¹ва.

Протоколы обмена ключами

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

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

1. Элемент ш из грамм опубликовано.
2. Два подгруппы А и B из грамм такой, что ab = ба для всех а в А и б в B опубликованы.
3. Алиса выбирает элемент а из А и отправляет ш^а Бобу. Алиса держит а частный.
4. Боб выбирает элемент б из B и отправляет ш^б Алисе. Боб держит б частный.
5. Алиса вычисляет K = (ш^б)^а = ш^ба.
6. Боб вычисляет K ' = (ш^а)^б=ш^ab.
7. С ab = ба, K = K '. Алиса и Боб имеют общий секретный ключ K.

Протокол Аншель-Аншель-Гольдфельд

Основная статья: Обмен ключами Аншель-Аншель-Гольдфельд

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

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

Протокол обмена ключами Stickel

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

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

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

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

1. Позволять грамм некоммутативная группа. Позволять А и B быть публичными подгруппами грамм такой, что ab = ба для всех а в А и б в B.
2. Элемент Икс из грамм выбрано и опубликовано.
3. Боб выбирает секретный ключ б из А и издает z = Икс^б как его открытый ключ.
4. Алиса выбирает случайный р из B и вычисляет т = z^р.
5. Зашифрованное сообщение C = (Икс^р, ЧАС(т) ${\displaystyle \oplus }$ м), куда ЧАС есть некоторые хеш-функция и ${\displaystyle \oplus }$ обозначает XOR операция. Алиса отправляет C Бобу.
6. Расшифровать C, Боб выздоравливает т следующее: (Икс^р)^б = Икс^rb = Икс^br = (Икс^б)^р = z^р = т. Текстовое сообщение, отправленное Алисой, выглядит так: п = ( ЧАС(т) ${\displaystyle \oplus }$ м ) ${\displaystyle \oplus }$ ЧАС(т) = м.

Протоколы для аутентификации

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

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

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

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

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

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

Группы платформ

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

1. Группа грамм должны быть хорошо известны и хорошо изучены.
2. В проблема со словом в грамм должно иметь быстрое решение по детерминированному алгоритму. Должна существовать эффективно вычислимая "нормальная форма" для элементов грамм.
3. Восстановить факторы должно быть невозможно. Икс и у из продукта ху в грамм.
4. Количество элементов длины п в грамм должен расти быстрее, чем любой многочлен от п. (Здесь "длина п"- длина слова, представляющего элемент группы.)

Примеры групп платформ

Группы кос

Основная статья: Группа кос

Позволять п быть положительным целым числом. Группа кос B_п группа, порожденная Икс₁, Икс₂, . . . , Икс_п-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 }$

Группа Григорчука

Основная статья: Группа Григорчука

Позволять Т обозначают бесконечное укорененный двоичное дерево. Набор V вершин - это множество всех конечных двоичных последовательностей. Позволять А(Т) обозначают множество всех автоморфизмов Т. (Автоморфизм Т переставляет вершины, сохраняя связность.) Группа Григорчука Γ является подгруппой А(Т), порожденные автоморфизмами а, б, 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}}}$

Группа Артин

Основная статья: Группа Артин

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

${\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.

Рекомендации

1. M. Habeeb, D. Kahrobaei, C. Koupparis, V. Shpilrain, Обмен открытым ключом с использованием полупрямого произведения (полу) групп, в: ACNS 2013, Lecture Notes Comp. Sc. 7954 (2013), 475-486.