Некоммутативная криптография (Uytkbbrmgmnfugx tjnhmkijgsnx)
Некоммутативная криптография — область криптологии, в которой шифровальные примитивы, методы и системы основаны на некоммутативных алгебраических структурах.
В основе некоммутативной криптографии лежат операции над некоммутативной группой 𝐺 из (𝐺, ∗), состоящей из групп, полугрупп или колец, в которой существуют хотя бы два элемента группы 𝑎 и 𝑏 из 𝐺 для которых верно неравенство 𝑎∗𝑏 ≠ 𝑏∗𝑎[1]. Использующие данную структуру протоколы были развиты для решения различных проблем шифрования.Примером могут послужить задачи аутентификации, шифрования-дешифрования и установления сеанса обмена ключами[1].
Актуальность
[править | править код]Одним из самых ранних применений некоммутативной алгебраической структуры в шифровальных целях было использованием группы кос, с последующим развитием шифровального протокола. Позже несколько других некоммутативных структур таких как группы Томпсона, полициклические группы, группы Григорчука и матричные группы были идентифицированы как потенциальные кандидаты для применения в шифровании. В отличие от некоммутативной криптографии, в настоящее время широко используемый криптосистемы с открытым ключом такие как RSA, протокол Диффи — Хеллмана и эллиптическая криптография основаны на теории чисел и следовательно зависят от коммутативных алгебраических структур[1]. Однако, применение квантового компьютера в криптографии, которое может произойти в ближайшем будущем, существенно ускорит решение задач факторизации и дискретного логарифмирования в циклической группе(данные задачи будут решатся за полиномиальное время)[2]. Последнее означает, что все наиболее широко применяемые криптосистемы станут небезопасны, поскольку их стойкость основана на сверхполиномиальной сложности указанных двух задач при их решении на имеющихся в настоящее время компьютерах.В этом случае, безопасность может быть достигнута путем построения криптосистем в основе которых лежит некоммутативная группа.
Базовая группа
[править | править код]Некоммутативная группа, которая используется в основе шифровального протокола, называют базовой группой этого протокола. Только группы, имеющие определенные свойства, могут использоваться в качестве базовых групп для внедрения в некоммутативные шифровальные системы.Пусть G является группой, предложенной в качестве базовой для построения некоммутативной криптосистемы. Ниже представлен список свойств, которым должен удовлетворять G.
- Группа G должна быть хорошо известна. Другими словами, проблема поиска сопряженности для нее либо давно и безуспешно изучалась, либо может быть сведена к другой хорошо известной задаче.
- Задача равенства слов[англ.] в группе G должна иметь быстрое решение детерминированным алгоритмом. Должна существовать эффективно вычисляемая «нормальная форма» для элементов из G.
- G должна быть группой сверхполиномиального роста, то есть количество элементов длины n в G растет быстрее, чем любой полином от n.(Защищает от простого перебора)
- Возврат элементов x и y от произведения xy в G должен быть невозможен.
Примеры базовых групп
[править | править код]Группа кос
[править | править код]Пусть n- положительное целое число. Группа кос Bn можно задать (n − 1) образующими и соотношениями[3]:
В частности, любой элемент B4 можно записать как композицию следующих трёх элементов (и обратных к ним):
![]() |
![]() | ![]() |
Группа Томпсона
[править | править код]Группа Томпсона является бесконечной группой F, имеющей следующее бесконечное представление[4]:
Группа Григорчука
[править | править код]Пусть T обозначает бесконечное корневое двоичное дерево. Множество V вершин - это множество всех конечных двоичных последовательностей. Пусть A(T) обозначает множество всех автоморфизмов T. (Автоморфизм T переставляет вершины, сохраняя связность.) Группа Григорчука Γ - подгруппа A(T), порождаемая автоморфизмами a, b, c, d, определяющимися следующим образом:
Группа Артина
[править | править код]Группа Артина A(Γ) - это группа со следующим представлением[5]:
где
Для , обозначает знакопеременное произведение и длинной , начиная с . Например,
и
Если , тогда (по соглашению) нет никакого отношения между и .
Матричные группы
[править | править код]Пусть 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) m), где H это некоторая хеш-функция и обозначает операцию XOR. Алиса отправляет C Бобу.
- Чтобы расшифровать C, Боб восстанавливает t через: (xr)b = xrb = xbr = (xb)r = zr = t. Текстовое сообщение отправленное Алисой вычисляется как P = ( H(t) m ) 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 2 3 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". arXiv:1103.4093.
{{cite arXiv}}
: Явное указание et al. в:|last1=
(справка) - Alexei G. Myasnikov; Vladimir Shpilrain; Alexander Ushakov. Non-commutative Cryptography and Complexity of Group-theoretic Problems (англ.). — American Mathematical Society, 2011. — ISBN 9780821853603.