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

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

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

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

Некоммутативная группа, которая используется в основе шифровального протокола, называют базовой группой этого протокола. Только группы, имеющие определенные свойства, могут использоваться в качестве базовых групп для внедрения в некоммутативные шифровальные системы.Пусть 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}}}$ соотношениями^[3]:

• ${\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, имеющей следующее бесконечное представление^[4]:

${\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(Γ) - это группа со следующим представлением^[5]:

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

Следующий протокол похож на протокол Диффи-Хеллмана. Он устанавливает общий секретный ключ 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^mbⁿ Бобу.
4. Боб принимает два случайных числа r < N и s < M и отправляет v = a^rb^s Алисе.
5. Общим для Алисы и Боба ключом будет K = a^{m + r}b^{n + s}.
6. Алиса вычисляет ключ по формуле:K = a^mvbⁿ.
7. Боб вычисляет ключ по формуле:K = a^rub^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. Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems.

1. Alexei Myasnikov; Vladimir Shpilrain; Alexander Ushakov. Group-based Cryptography (неопр.). — Berlin: Birkhäuser Verlag^[англ.], 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:1103.4093. {{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.