Некоммутативная криптография — область криптологии , в которой шифровальные примитивы , методы и системы основаны на некоммутативных алгебраических структурах.

В основе некоммутативной криптографии лежат операции над некоммутативной группой 𝐺 из (𝐺, ∗), состоящей из групп , полугрупп или колец , в которой существуют хотя бы два элемента группы 𝑎 и 𝑏 из 𝐺 для которых верно неравенство 𝑎∗𝑏 ≠ 𝑏∗𝑎 . Использующие данную структуру протоколы были развиты для решения различных проблем шифрования.Примером могут послужить задачи аутентификации , шифрования -дешифрования и установления сеанса обмена ключами .

Актуальность

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

Базовая группа

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

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

Примеры базовых групп

Группа кос

Пусть n - положительное целое число. Группа кос B _n можно задать ( n − 1) образующими и ${\displaystyle {\tfrac {n\cdot (n-1)}{2}}}$ соотношениями :

• ${\displaystyle B_{n}=\langle \sigma _{1},\ldots ,\sigma _{n-1}\ \mid \ \sigma _{i}\sigma _{i+1}\sigma _{i}=\sigma _{i+1}\sigma _{i}\sigma _{i+1}\ {\text{при}}\ 1\leq i\leq n-2\ {\text{и}}\ \sigma _{i}\sigma _{j}=\sigma _{j}\sigma _{i}\ {\text{for}}\ |i-j|\geq 2\rangle :}$

В частности, любой элемент B ₄ можно записать как композицию следующих трёх элементов (и обратных к ним):

σ 1	σ 2	σ 3

Группа Томпсона

Группа Томпсона является бесконечной группой 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 вершин - это множество всех конечных двоичных последовательностей. Пусть A(T) обозначает множество всех автоморфизмов 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},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 {\begin{aligned}{\Big \langle }x_{1},x_{2},\ldots ,x_{n}{\Big |}\langle x_{1},x_{2}\rangle ^{m_{1,2}}&=\langle x_{2},x_{1}\rangle ^{m_{2,1}},\ldots \\&\ldots ,\langle x_{n-1},x_{n}\rangle ^{m_{n-1,n}}=\langle x_{n},x_{n-1}\rangle ^{m_{n,n-1}}{\Big \rangle }\end{aligned}}}$

где

${\displaystyle m_{i,j}=m_{j,i}\in \{2,3,\ldots ,\infty \}.}$

Для ${\displaystyle m<\infty }$ , ${\displaystyle \langle x_{i},x_{j}\rangle ^{m}}$ обозначает знакопеременное произведение ${\displaystyle x_{i}}$ и ${\displaystyle x_{j}}$ длинной ${\displaystyle m}$ , начиная с ${\displaystyle x_{i}}$ . Например,

${\displaystyle \langle x_{i},x_{j}\rangle ^{3}=x_{i}x_{j}x_{i}}$

и

${\displaystyle \langle x_{i},x_{j}\rangle ^{4}=x_{i}x_{j}x_{i}x_{j}.}$

Если ${\displaystyle m=\infty }$ , тогда (по соглашению) нет никакого отношения между ${\displaystyle x_{i}}$ и ${\displaystyle x_{j}}$ .

Матричные группы

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

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

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

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

Протокол Ko, Lee, и др.

Следующий протокол похож на протокол Диффи-Хеллмана. Он устанавливает общий секретный ключ K для Алисы и Боба .

1. Элемент w из G известен всем.
2. Две подгруппы A и B из G такие, что ab = ba для всех a из A и b из B публикуются.
3. Алиса выбирает элемент a из A и передает w ^a Бобу. Алиса держит 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 ₂ , . . . , a _k , b ₁ , b ₂ , . . . , b _m из G выбраны и опубликованы.
2. Алиса выбирает секретный x из G как состоящие из a ₁ , a ₂ , . . . , a _k ; следовательно x = x ( a ₁ , a ₂ , . . . , a _k ).
3. Алиса отправляет b ₁ ^x , b ₂ ^x , . . . , b _m ^x Бобу.
4. Боб выбирает секретный y из G как слово состоящие из b ₁ , b ₂ , . . . , b _m ; следовательно y = y ( b ₁ , b ₂ , . . . , b _m ).
5. Боб отправляет a ₁ ^y , a ₂ ^y , . . . , a _k ^y Алисе.
6. Алиса и Боб делятся общим секретным ключом K = x ⁻¹ y ⁻¹ xy .
7. Алиса вычисляет x ( a ₁ ^y , a ₂ ^y , . . . , a _k ^y ) = y ⁻¹ xy . Умножив его на x ⁻¹ , Алиса получает K .
8. Боб вычисляет y ( b ₁ ^x , b ₂ ^x , . . . , b _m ^x ) = x ⁻¹ yx . Умножив его на y ⁻¹ и взяв обратный элемент, Боб получает K .

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

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

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 - некоммутативная группа. Также, пусть A и B будут публичными подгруппами из G для которых верно: ab = ba для всех a из A и b из B .
2. Элемент x из G выбран и опубликован.
3. Боб выбирает секретный ключ b из A и публикует z = x ^b как свой открытый ключ.
4. Алиса выбирает случайный r из B и вычисляет t = z ^r .
5. Зашифрованным сообщение является C = ( x ^r , H ( t ) ${\displaystyle \oplus }$ m ), где H это некоторая хеш-функция и ${\displaystyle \oplus }$ обозначает операцию XOR . Алиса отправляет C Бобу.
6. Чтобы расшифровать C , Боб восстанавливает t через: ( x ^r ) ^b = x ^rb = x ^br = ( x ^b ) ^r = z ^r = t . Текстовое сообщение отправленное Алисой вычисляется как P = ( H ( t ) ${\displaystyle \oplus }$ m ) ${\displaystyle \oplus }$ H ( t ) = m .

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

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

1. Пусть G - некоммутативная группа. Также, пусть A и B будут подгруппами из G для которых верно: ab = ba для всех a из 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 . Определить, существует ли элемент x из G такой что v = u ^x , то есть такой, что v = x ⁻¹ ux .
• Проблема поиска сопряженности : даны два элемента u и v из группы G . Найти элемент x из G такой, что v = u ^x , то есть такой, что v = x ⁻¹ ux

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

Примечания

Литература

1. Alexei G. Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Non-commutative Cryptography and Complexity of Group-theoretic Problems. — ISBN 9780821853603 .
2. Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography.
3. Benjamin Fine, et. al. .

Ссылки

1. Alexei Myasnikov; Vladimir Shpilrain; Alexander Ushakov. Group-based Cryptography (неопр.) . — Berlin: (англ.) ( , 2008.
2. Zhenfu Cao. New Directions of Modern Cryptography (неопр.) . — Boca Raton: CRC Press, Taylor & Francis Group, 2012. — ISBN 978-1-4665-0140-9 .
3. Benjamin Fine; et al. "Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems". arXiv : . {{ cite arXiv }} : Явное указание et al. в: |last1= ( справка )
4. Alexei G. Myasnikov; Vladimir Shpilrain; Alexander Ushakov. Non-commutative Cryptography and Complexity of Group-theoretic Problems (англ.) . — American Mathematical Society, 2011. — ISBN 9780821853603 .