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

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

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

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

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

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

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

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

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

Группа кос

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

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

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

$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},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(Γ) - это группа со следующим представлением:

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

где

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

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

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

и

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

Если $m=\infty$, тогда (по соглашению) нет никакого отношения между $x_{i}$ и $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^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) $\oplus$ m), где H это некоторая хеш-функция и $\oplus$ обозначает операцию XOR. Алиса отправляет C Бобу.
6. Чтобы расшифровать C, Боб восстанавливает t через: (x^r)^b = x^rb = x^br = (x^b)^r = z^r = t. Текстовое сообщение отправленное Алисой вычисляется как P = ( H(t) $\oplus$ m ) $\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, arΧiv:1103.4093. 
4. Alexei G. Myasnikov; Vladimir Shpilrain; Alexander Ushakov. Non-commutative Cryptography and Complexity of Group-theoretic Problems (англ.). — American Mathematical Society, 2011. — ISBN 9780821853603.