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

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

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

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

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

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

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

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

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

Группа кос

Пусть n- положительное целое число. Группа кос Bn можно задать (n − 1) образующими и соотношениями[3]:

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

        
  σ1
  σ2
  σ3

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

Группа Томпсона является бесконечной группой 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 для Алисы и Боба.

  1. Элемент w из G известен всем.
  2. Две подгруппы A и B из G такие, что ab = ba для всех a из A и b из B публикуются.
  3. Алиса выбирает элементa из A и передает wa Бобу. Алиса держит a в секрете.
  4. Боб выбирает элемент b из B и передает wb Алисе. Боб держит b в секрете.
  5. Алиса вычисляет K = (wb)a = wba.
  6. Боб вычисляет K' = (wa)b=wab.
  7. Когда ab = ba и K = K',тогда Алиса и Боб делятся общим секретным ключом K.

Протокол Аншель-Аншеля-Гольдфельда

Это протокол обмена ключами с использованием неабелевой группы G. Это важно, поскольку он не требует двух коммутирующих подгрупп A и B группы G, как в случае предыдущего протокола.

  1. Элементы a1, a2, . . . , ak, b1, b2, . . . , bm из G выбраны и опубликованы.
  2. Алиса выбирает секретный x из G как слово[англ.] состоящие из a1, a2, . . . , ak; следовательноx = x( a1, a2, . . . , ak ).
  3. Алиса отправляет b1x, b2x, . . . , bmx Бобу.
  4. Боб выбирает секретный y из G как слово состоящие из b1, b2, . . . , bm; следовательно y = y ( b1, b2, . . . , bm ).
  5. Боб отправляет a1y, a2y, . . . , aky Алисе.
  6. Алиса и Боб делятся общим секретным ключом K = x−1y−1xy.
  7. Алиса вычисляет x ( a1y, a2y, . . . , aky ) = y−1 xy. Умножив его на x−1, Алиса получает K.
  8. Боб вычисляет y ( b1x, b2x, . . . , bmx) = x−1yx. Умножив его на y−1 и взяв обратный элемент, Боб получает K.

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

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

  1. Пусть G - известная неабелева конечная группа.
  2. Пустьa, b- известная пара элементов изG такая что: abba. Пусть порядок a и b соответствуетN и M.
  3. Алиса выбирает два случайных числа n < N и m < M и посылает u = ambn Бобу.
  4. Боб принимает два случайных числа r < N и s < M и отправляет v = arbs Алисе.
  5. Общим для Алисы и Боба ключом будет K = am + rbn + s.
  6. Алиса вычисляет ключ по формуле:K = amvbn.
  7. Боб вычисляет ключ по формуле:K = arubs.

Протоколы шифрования и дешифрования

Этот протокол описывает, как зашифровать секретное сообщение, а затем расшифровать его с помощью некоммутативной группы. Пусть Алиса хочет отправить Бобу секретное сообщение m.

  1. Пусть G - некоммутативная группа. Также, пусть A и B будут публичными подгруппами из G для которых верно: ab = ba для всех a из A и b из B.
  2. Элемент x из G выбран и опубликован.
  3. Боб выбирает секретный ключ b из A и публикует z = xb как свой открытый ключ.
  4. Алиса выбирает случайный r из B и вычисляет t = zr.
  5. Зашифрованным сообщение является C = (xr, H(t) m), где H это некоторая хеш-функция и обозначает операцию XOR. Алиса отправляет C Бобу.
  6. Чтобы расшифровать C, Боб восстанавливает t через: (xr)b = xrb = xbr = (xb)r = zr = t. Текстовое сообщение отправленное Алисой вычисляется как P = ( H(t) m ) 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 ' = wr Алисе.
  5. Алиса отправляет ответw ' ' = (w ')s Бобу.
  6. Боб проверяет равенство w ' ' = tr. Если равенство выполняется, то личность Алисы подтверждается.

Основы безопасности протоколов

Основой безопасности и прочности различных протоколов, представленных выше, является сложность решения следующих двух проблем:

  • Проблема существования сопряженности[англ.] : даны два элемента u и v из группы G. Определить, существует ли элемент x из G такой что v = ux, то есть такой, что v = x−1 ux.
  • Проблема поиска сопряженности: даны два элемента u и v из группы G. Найти элемент x из G такой, что v = ux, то есть такой, что v = x−1 ux

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

Примечания

  1. 1 2 3 Kumar, Saini. Novel Noncommutative Cryptography Scheme Using Extra Special Group (англ.). — 2017. — January. — P. 1—3. Архивировано 26 декабря 2018 года.
  2. Д.Н.Молдовян. Примитивы криптосистем с открытым ключом: конечные некоммутативные группы четырехмерных векторов (рус.). — 2010. Архивировано 26 марта 2020 года.
  3. David Garber. BRAID GROUP CRYPTOGRAPHY PRELIMINARY DRAFT (англ.). — 2007. — December. Архивировано 26 декабря 2018 года.
  4. Vladimir Shpilrain,Alexander Ushakov. Thompson’s Group and Public Key Cryptography (англ.). — 2007. — December. Архивировано 9 апреля 2019 года.
  5. K.I.Appel, P.E.Schupp. Artin groups and infinite Coxeter groups (англ.). — 1983. — June. Архивировано 26 декабря 2018 года.

Литература

  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.