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

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

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

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

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

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

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

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

элемент w из G. Опубликован
две подгруппы A и B группы G такие, что ab = ba для всех a в A и b в B. Опубликованы
Алиса выбирает элемент a из A и отправляет w ^а Бобу. Алиса сохраняет приватность .
Боб выбирает элемент b из B и отправляет w ^б к Алисе. Боб держит b в тайне.
Алиса вычисляет K = ( w ^б) ^а = v ^нет.
Боб вычисляет K' = ( w ^а) ^б= v ^аб.
Поскольку ab = ba , K = K' . имеют общий секретный ключ K. Алиса и Боб

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

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

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

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

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

Пусть G — публичная неабелева конечная группа .
Пусть a , b — общедоступные элементы G такие, что ab ≠ ba . Пусть порядки a и b равны N и M соответственно.
Алиса выбирает два случайных числа n < N и m < M и отправляет u = a ^мб ^н Бобу.
Боб выбирает два случайных числа r < N и s < M и отправляет v = a ^рб ^с к Алисе.
Общий ключ, используемый Алисой и Бобом, равен K = a. ^{м + р}б ^{п + с}.
Алиса вычисляет ключ по K = a ^мВ.Б. ^н.
Боб вычисляет ключ по K = a ^руб ^с.

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

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

Пусть G — некоммутативная группа. Пусть A и B — открытые подгруппы группы такие , что ab = ba для всех a в A и b в B. G
Элемент x из G выбирается и публикуется.
Боб выбирает секретный ключ b из A и публикует z = x. ^б в качестве его открытого ключа.
Алиса выбирает случайный r из B и вычисляет t = z ^р.
Зашифрованное сообщение имеет вид C = ( x ^р, Ч ( т ) $\oplus$ m ), где H — некоторая хеш-функция и $\oplus$ обозначает операцию XOR . Алиса отправляет C Бобу.
Чтобы расшифровать C , Боб восстанавливает t следующим образом: ( x ^р) ^б = х ^РБ = х ^бр = ( х ^б) ^р = г ^р = т . Простое текстовое сообщение, отправленное Алисой, имеет вид P = ( H ( t ) $\oplus$ м ) $\oplus$ ЧАС ( т ) знак равно м .

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

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

Пусть G — некоммутативная группа, и пусть A и B — подгруппы G такие, что ab = ba для всех a в A и b в B .
Элемент w из G выбирается и публикуется.
Алиса выбирает частный s из A и публикует пару ( w , t ), где t = w ^с.
Боб выбирает r из B и отправляет вызов w ' = w ^р к Алисе.
Алиса отправляет ответ w ' ' = ( w ') ^с Бобу.
Боб проверяет, w ' ' = t ^р. Если это правда, то личность Алисы установлена.

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

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

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

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

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

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

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

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

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

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

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, имеющая следующее бесконечное представление:

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

$a(b_{1},b_{2},\ldots ,b_{n})=(1-b_{1},b_{2},\ldots ,b_{n})$
$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}}$
$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}}$
$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 (Γ) — это группа следующего представления:

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

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

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

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

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

^[1]

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

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

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

^ Хабиб, М.; Каробаи, Д.; Куппарис, К.; Шпильрайн, В. (2013). «Обмен открытыми ключами с использованием полупрямого продукта (полу)групп». Прикладная криптография и сетевая безопасность. АЦНС 2013 . Конспекты лекций по информатике. Том. 7954. Спрингер. стр. 475–486. arXiv : 1304.6572 . CiteSeerX 10.1.1.769.1289 . дои : 10.1007/978-3-642-38980-1_30 . ISBN 978-3-642-38980-1 .

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

Myasnikov, Alexei; Shpilrain, Vladimir; Ushakov, Alexander (2008). Group-based Cryptography . Birkhäuser Verlag. ISBN 9783764388270 .
Цао, Чжэньфу (2012). Новые направления современной криптографии . ЦРК Пресс. ISBN 978-1-4665-0140-9 .
Бенджамин Файн; и др. (2011). «Аспекты криптографии на основе неабелевых групп: обзор и открытые проблемы». arXiv : 1103.4093 [ cs.CR ].
Мясников Алексей Георгиевич; Шпильрайн Владимир; Ушаков, Александр (2011). Некоммутативная криптография и сложность теоретико-групповых задач . Американское математическое общество. ISBN 9780821853603 .

[1] Хабиб, М.; Каробаи, Д.; Куппарис, К.; Шпильрайн, В. (2013). «Обмен открытыми ключами с использованием полупрямого продукта (полу)групп». Прикладная криптография и сетевая безопасность. АЦНС 2013 . Конспекты лекций по информатике. Том. 7954. Спрингер. стр. 475–486. arXiv : 1304.6572 . CiteSeerX 10.1.1.769.1289 . дои : 10.1007/978-3-642-38980-1_30 . ISBN 978-3-642-38980-1 .

[1]