Некоммутативная криптография
Некоммутативная криптография — область криптологии, в которой шифровальные примитивы, методы и системы основаны на некоммутативных алгебраических структурах.
В основе некоммутативной криптографии лежат операции над некоммутативной группой 𝐺 из (𝐺, ∗), состоящей из групп, полугрупп или колец, в которой существуют хотя бы два элемента группы 𝑎 и 𝑏 из 𝐺 для которых верно неравенство 𝑎∗𝑏 ≠ 𝑏∗𝑎[1]. Использующие данную структуру протоколы были развиты для решения различных проблем шифрования.Примером могут послужить задачи аутентификации, шифрования-дешифрования и установления сеанса обмена ключами[1].
Актуальность
Одним из самых ранних применений некоммутативной алгебраической структуры в шифровальных целях было использованием группы кос, с последующим развитием шифровального протокола. Позже несколько других некоммутативных структур таких как группы Томпсона, полициклические группы, группы Григорчука и матричные группы были идентифицированы как потенциальные кандидаты для применения в шифровании. В отличие от некоммутативной криптографии, в настоящее время широко используемый криптосистемы с открытым ключом такие как RSA, протокол Диффи — Хеллмана и эллиптическая криптография основаны на теории чисел и следовательно зависят от коммутативных алгебраических структур[1]. Однако, применение квантового компьютера в криптографии, которое может произойти в ближайшем будущем, существенно ускорит решение задач факторизации и дискретного логарифмирования в циклической группе(данные задачи будут решатся за полиномиальное время)[2]. Последнее означает, что все наиболее широко применяемые криптосистемы станут небезопасны, поскольку их стойкость основана на сверхполиномиальной сложности указанных двух задач при их решении на имеющихся в настоящее время компьютерах.В этом случае, безопасность может быть достигнута путем построения криптосистем в основе которых лежит некоммутативная группа.
Базовая группа
Некоммутативная группа, которая используется в основе шифровального протокола, называют базовой группой этого протокола. Только группы, имеющие определенные свойства, могут использоваться в качестве базовых групп для внедрения в некоммутативные шифровальные системы.Пусть G является группой, предложенной в качестве базовой для построения некоммутативной криптосистемы. Ниже представлен список свойств, которым должен удовлетворять G.
- Группа G должна быть хорошо известна. Другими словами, проблема поиска сопряженности для нее либо давно и безуспешно изучалась, либо может быть сведена к другой хорошо известной задаче.
- Задача равенства слов[англ.] в группе G должна иметь быстрое решение детерминированным алгоритмом. Должна существовать эффективно вычисляемая «нормальная форма» для элементов из G.
- G должна быть группой сверхполиномиального роста, то есть количество элементов длины n в G растет быстрее, чем любой полином от n.(Защищает от простого перебора)
- Возврат элементов x и y от произведения xy в G должен быть невозможен.
Примеры базовых групп
Группа кос
Пусть n- положительное целое число. Группа кос Bn можно задать (n − 1) образующими и [math]\displaystyle{ \tfrac{n\cdot(n-1)}{2} }[/math] соотношениями[3]:
- [math]\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\le i\le n-2\ \text{и}\ \sigma_i \sigma_j=\sigma_j \sigma_i \ \text{for}\ |i-j|\ge 2\rangle : }[/math]
В частности, любой элемент B4 можно записать как композицию следующих трёх элементов (и обратных к ним):
Группа Томпсона
Группа Томпсона является бесконечной группой F, имеющей следующее бесконечное представление[4]:
- [math]\displaystyle{ F = \left\langle x_0, x_1, x_2, \ldots \big| x_k^{-1}x_nx_k=x_{n+1} \text{ for } k\lt n \right\rangle }[/math]
Группа Григорчука
Пусть T обозначает бесконечное корневое двоичное дерево. Множество V вершин - это множество всех конечных двоичных последовательностей. Пусть A(T) обозначает множество всех автоморфизмов T. (Автоморфизм T переставляет вершины, сохраняя связность.) Группа Григорчука Γ - подгруппа A(T), порождаемая автоморфизмами a, b, c, d, определяющимися следующим образом:
- [math]\displaystyle{ a(b_1,b_2,\ldots, b_n) = (1-b_1,b_2,\ldots, b_n) }[/math]
- [math]\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} }[/math]
- [math]\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} }[/math]
- [math]\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} }[/math]
Группа Артина
Группа Артина A(Γ) - это группа со следующим представлением[5]:
- [math]\displaystyle{ \begin{align} \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{align} }[/math]
где
- [math]\displaystyle{ m_{i,j} = m_{j,i} \in \{2,3,\ldots, \infty\}. }[/math]
Для [math]\displaystyle{ m \lt \infty }[/math], [math]\displaystyle{ \langle x_i, x_j \rangle^m }[/math] обозначает знакопеременное произведение [math]\displaystyle{ x_i }[/math] и [math]\displaystyle{ x_j }[/math] длинной [math]\displaystyle{ m }[/math], начиная с [math]\displaystyle{ x_i }[/math]. Например,
- [math]\displaystyle{ \langle x_i, x_j \rangle^3 = x_ix_jx_i }[/math]
и
- [math]\displaystyle{ \langle x_i, x_j \rangle^4 = x_ix_jx_ix_j. }[/math]
Если [math]\displaystyle{ m=\infty }[/math], тогда (по соглашению) нет никакого отношения между [math]\displaystyle{ x_i }[/math] и [math]\displaystyle{ x_j }[/math].
Матричные группы
Пусть F-конечное поле. Группы матриц над F были использованы в качестве базовых групп некоторых некоммутативных криптографических протоколов.
Некоторые некоммутативные криптографические протоколы
В этих протоколах предполагается, что G-неабелева группа. Если w и a являются элементами группы G, то запись wa будет обозначать элемент a−1wa.
Протоколы для обмена ключами
Протокол Ko, Lee, и др.
Следующий протокол похож на протокол Диффи-Хеллмана. Он устанавливает общий секретный ключ K для Алисы и Боба.
- Элемент w из G известен всем.
- Две подгруппы A и B из G такие, что ab = ba для всех a из A и b из B публикуются.
- Алиса выбирает элементa из A и передает wa Бобу. Алиса держит a в секрете.
- Боб выбирает элемент b из B и передает wb Алисе. Боб держит b в секрете.
- Алиса вычисляет K = (wb)a = wba.
- Боб вычисляет K' = (wa)b=wab.
- Когда ab = ba и K = K',тогда Алиса и Боб делятся общим секретным ключом K.
Протокол Аншель-Аншеля-Гольдфельда
Это протокол обмена ключами с использованием неабелевой группы G. Это важно, поскольку он не требует двух коммутирующих подгрупп A и B группы G, как в случае предыдущего протокола.
- Элементы a1, a2, . . . , ak, b1, b2, . . . , bm из G выбраны и опубликованы.
- Алиса выбирает секретный x из G как слово[англ.] состоящие из a1, a2, . . . , ak; следовательноx = x( a1, a2, . . . , ak ).
- Алиса отправляет b1x, b2x, . . . , bmx Бобу.
- Боб выбирает секретный y из G как слово состоящие из b1, b2, . . . , bm; следовательно y = y ( b1, b2, . . . , bm ).
- Боб отправляет a1y, a2y, . . . , aky Алисе.
- Алиса и Боб делятся общим секретным ключом K = x−1y−1xy.
- Алиса вычисляет x ( a1y, a2y, . . . , aky ) = y−1 xy. Умножив его на x−1, Алиса получает K.
- Боб вычисляет y ( b1x, b2x, . . . , bmx) = x−1yx. Умножив его на y−1 и взяв обратный элемент, Боб получает K.
Протокол обмена ключами Стикеля
В первоначальной формулировке этого протокола использовалась группа обратимых матриц над конечным полем.
- Пусть G - известная неабелева конечная группа.
- Пустьa, b- известная пара элементов изG такая что: ab ≠ ba. Пусть порядок a и b соответствуетN и M.
- Алиса выбирает два случайных числа n < N и m < M и посылает u = ambn Бобу.
- Боб принимает два случайных числа r < N и s < M и отправляет v = arbs Алисе.
- Общим для Алисы и Боба ключом будет K = am + rbn + s.
- Алиса вычисляет ключ по формуле:K = amvbn.
- Боб вычисляет ключ по формуле:K = arubs.
Протоколы шифрования и дешифрования
Этот протокол описывает, как зашифровать секретное сообщение, а затем расшифровать его с помощью некоммутативной группы. Пусть Алиса хочет отправить Бобу секретное сообщение m.
- Пусть G - некоммутативная группа. Также, пусть A и B будут публичными подгруппами из G для которых верно: ab = ba для всех a из A и b из B.
- Элемент x из G выбран и опубликован.
- Боб выбирает секретный ключ b из A и публикует z = xb как свой открытый ключ.
- Алиса выбирает случайный r из B и вычисляет t = zr.
- Зашифрованным сообщение является C = (xr, H(t) [math]\displaystyle{ \oplus }[/math] m), где H это некоторая хеш-функция и [math]\displaystyle{ \oplus }[/math] обозначает операцию XOR. Алиса отправляет C Бобу.
- Чтобы расшифровать C, Боб восстанавливает t через: (xr)b = xrb = xbr = (xb)r = zr = t. Текстовое сообщение отправленное Алисой вычисляется как P = ( H(t) [math]\displaystyle{ \oplus }[/math] m ) [math]\displaystyle{ \oplus }[/math] H(t) = m.
Протоколы аутентификации
Боб хочет проверить, действительно ли отправителем сообщения является Алиса.
- Пусть G - некоммутативная группа. Также, пусть A и B будут подгруппами из G для которых верно: ab = ba для всех a из A и b из B.
- Элементw из G выбран и опубликован.
- Алиса выбирает секретный s из A и публикует пару ( w, t ) где t = w s.
- Боб выбирает r из B и посылает сообщение w ' = wr Алисе.
- Алиса отправляет ответw ' ' = (w ')s Бобу.
- Боб проверяет равенство w ' ' = tr. Если равенство выполняется, то личность Алисы подтверждается.
Основы безопасности протоколов
Основой безопасности и прочности различных протоколов, представленных выше, является сложность решения следующих двух проблем:
- Проблема существования сопряженности[англ.] : даны два элемента u и v из группы G. Определить, существует ли элемент x из G такой что v = ux, то есть такой, что v = x−1 ux.
- Проблема поиска сопряженности: даны два элемента u и v из группы G. Найти элемент x из G такой, что v = ux, то есть такой, что v = x−1 ux
Если алгоритм решения задачи поиска сопряженности неизвестен, то функцию x → ux можно рассматривать как одностороннюю функцию.
Примечания
- ↑ 1,0 1,1 1,2 Kumar, Saini. Novel Noncommutative Cryptography Scheme Using Extra Special Group (англ.). — 2017. — January. — P. 1—3. Архивировано 26 декабря 2018 года.
- ↑ Д.Н.Молдовян. Примитивы криптосистем с открытым ключом: конечные некоммутативные группы четырехмерных векторов (рус.). — 2010. Архивировано 26 марта 2020 года.
- ↑ David Garber. BRAID GROUP CRYPTOGRAPHY PRELIMINARY DRAFT (англ.). — 2007. — December. Архивировано 26 декабря 2018 года.
- ↑ Vladimir Shpilrain,Alexander Ushakov. Thompson’s Group and Public Key Cryptography (англ.). — 2007. — December. Архивировано 9 апреля 2019 года.
- ↑ K.I.Appel, P.E.Schupp. Artin groups and infinite Coxeter groups (англ.). — 1983. — June. Архивировано 26 декабря 2018 года.
Литература
- Alexei G. Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Non-commutative Cryptography and Complexity of Group-theoretic Problems. — ISBN 9780821853603.
- Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography.
- Benjamin Fine, et. al. Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems.
Ссылки
- Alexei Myasnikov; Vladimir Shpilrain; Alexander Ushakov. Group-based Cryptography (неопр.). — Berlin: Birkhäuser Verlag[англ.], 2008.
- Zhenfu Cao. New Directions of Modern Cryptography (неопр.). — Boca Raton: CRC Press, Taylor & Francis Group, 2012. — ISBN 978-1-4665-0140-9.
- Benjamin Fine, et. al., Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems, arΧiv:1103.4093.
- Alexei G. Myasnikov; Vladimir Shpilrain; Alexander Ushakov. Non-commutative Cryptography and Complexity of Group-theoretic Problems (англ.). — American Mathematical Society, 2011. — ISBN 9780821853603.