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

редактировать

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

Некоммутативные криптографические протоколы были разработаны для решения различных криптографических проблем, таких как обмен ключами, шифрование -шифрование и аутентификация. Эти протоколы очень похожи на соответствующие протоколы в коммутативном случае.

Содержание

1 Некоторые некоммутативные криптографические протоколы
- 1.1 Протоколы для обмена ключами
  - 1.1.1 Протокол, разработанный Ко, Ли и др.
  - 1.1.2 Протокол Аншеля-Аншеля-Голдфельда
  - 1.1.3 Протокол обмена ключами Stickel
- 1.2 Протоколы для шифрования и дешифрования
- 1.3 Протоколы для аутентификации
2 Основы безопасности протоколов
3 Группы платформ
4 Примеры групп платформ
- 4.1 Группы кос
- 4.2 Группа Томпсона
- 4.3 Группа Григорчука
- 4.4 Группа Артина
- 4.5 Матричные группы
- 4.6 Полупрямые продукты
5 См. Также
6 Дополнительная литература
7 Ссылки

Некоторые некоммутативные криптографические протоколы

В этих протоколах предполагается, что G является неабелевой группой. Если w и a являются элементами G, запись w будет указывать на элемент awa.

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

Протокол, разработанный Ко, Ли и др.

Следующий протокол, разработанный Ко, Ли и др., Устанавливает общий секретный ключ K для Алисы и Боба.

публикуется элемент w из G.
Две подгруппы A и B группы G, такие что ab = ba для всех a в A и b в B.
Алиса выбирает элемент a из A и отправляет w Бобу. Алиса сохраняет частное.
Боб выбирает элемент b из B и отправляет w Алисе. Боб сохраняет b закрытым.
Алиса вычисляет K = (w) = w.
Боб вычисляет K '= (w) = w.
Поскольку ab = ba, K = К '. Алиса и Боб используют общий секретный ключ K.

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

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

Элементы a 1, a 2,..., a k, b 1, b 2,..., b m из G выбираются и публикуются.
Алиса выбирает частный x в G как слово в 1, a 2,..., a k ; то есть x = x (a 1, a 2,..., a k).
Алиса отправляет b 1, b 2,..., B m Бобу.
Боб выбирает частное y в G как слово в b 1, b 2,..., b m ; то есть y = y (b 1, b 2,..., b m).
Боб отправляет Алисе 1, 2,..., k.
Алиса и Боб совместно используют общий секретный ключ K = xyxy.
Алиса вычисляет x (a 1, a 2,..., a k) = y xy. Умножив его на x, Алиса получит K.
Боб вычисляет y (b 1, b 2,..., b m) = xyx. Предварительно умножив его на y, а затем взяв обратное, Боб получает K.

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

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

Пусть G - публичная неабелева конечная группа.
. Пусть a, b - публичные элементы G такие, что ab Let ba. Пусть порядки a и b равны N и M соответственно
Алиса выбирает два случайных числа n < N and m < M and sends u = ab to Bob.
Боб выбирает два случайных числа r < N and s < M and sends v = ab to Alice.
Общий ключ, используемый Алисой и Бобом, равен K = ab.
Алиса вычисляет ключ K = avb.
Боб вычисляет ключ K = aub.

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

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

Пусть G некоммутативная группа. Пусть A и B - общедоступные подгруппы группы G такие, что ab = ba для всех a в A и b в B.
Выбирается и публикуется элемент x из G.
Боб выбирает секрет ключ b из A и публикует z = x как свой открытый ключ.
Алиса выбирает случайное r из B и вычисляет t = z.
Зашифрованное сообщение C = (x, H ( t) $⊕ {\ displaystyle \ oplus}$ $\ oplus$ m), где H - некоторая хеш-функция и $⊕ {\ displaystyle \ oplus}$ $\ oplus$ обозначает операцию XOR. Алиса отправляет C Бобу.
Чтобы расшифровать C, Боб восстанавливает t следующим образом: (x) = x = x = (x) = z = t. Алиса отправляет простое текстовое сообщение P = (H (t) $⊕ {\ displaystyle \ oplus}$ $\ oplus$ m) $⊕ {\ displaystyle \ oplus}$ $\ oplus$ H (t) = m.

Протоколы для аутентификации

Пусть Боб хочет проверить, действительно ли отправителем сообщения является Алиса.

Пусть G - некоммутативная группа, а A и B - подгруппы в G такие, что ab = ba для всех a в A и b в B.
Элемент w из G выбирается и публикуется.
Алиса выбирает частный s из A и публикует пару (w, t), где t = w.
Боб выбирает r из B и отправляет вызов w '= w Алисе.
Алиса отправляет ответ w '' = (w ') Бобу.
Боб проверяет, w' '= t. Если это так, то личность Алисы установлена.

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

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

проблема решения о сопряженности (также называемая проблемой сопряженности): для двух элементов u и v в группе G определите, существует ли в G элемент x такой, что v = u, то есть такой, что v = x ux.
Проблема поиска сопряженности: для двух элементов u и v в группе G найти элемент x в G такой, что v = u, то есть такой, что v = x ux.

Если не известен алгоритм для решения проблемы поиска сопряженности, то функция x → u может рассматриваться как односторонняя функция.

Платформенные группы

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

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

Примеры групп платформ

Группы кос

Пусть n будет положительным целым числом. Группа кос B n является группой, сформированной x 1, x 2,..., x n-1 со следующим представлением:

B n = ⟨x 1, x 2,…, x n - 1 | x i x j = x j x i, если | i - j |>1 и x i x j x i = x j x i x j, если | i - j | Знак равно 1⟩ {\ displaystyle B_ {n} = \ left \ langle x_ {1}, x_ {2}, \ ldots, x_ {n-1} {\ big |} x_ {i} x_ {j} = x_ { j} x_ {i} {\ text {if}} | ij |>1 {\ text {and}} x_ {i} x_ {j} x_ {i} = x_ {j} x_ {i} x_ {j} {\ text {if}} | ij | = 1 \ right \ rangle}

B_{n}=\left\langle x_{1},x_{2},\ldots,x_{{n-1}}{\big |}x_{i}x_{j}=x_{j}x_{i}{\text{ if }}|i-j|>1 {\ text {and}} x_ {i} x_ {j} x_ {i} = x_ {j} x_ { i} x_ {j} {\ text {if}} | ij | = 1 \ right \ rangle

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

Группа Томпсона - это бесконечная группа F, имеющая следующее бесконечное представление:

F = ⟨x 0, x 1, x 2,… | xk - 1 xnxk = xn + 1 для k < n ⟩ {\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

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,…, bn) = (1 - b 1, b 2,…, bn) {\ displaystyle a (b_ {1}, b_ {2}, \ ldots, b_ {n }) = (1-b_ {1}, b_ {2}, \ ldots, b_ {n})}$ $a (b_ {1}, b_ {2}, \ ldots, b_ {n}) = (1-b_ { 1}, b_ {2}, \ ldots, b_ {n})$
$b (b 1, b 2,…, bn) = {(b 1, 1 - b 2,…, Bn), если b 1 = 0 (b 1, c (b 2,…, bn)), если b 1 = 1 {\ 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}}}$ $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, …, Bn) = {(b 1, 1 - b 2,…, bn), если b 1 = 0 (b 1, d (b 2,…, bn)), если b 1 = 1 {\ displaystyle c (b_ { 1}, b_ {2}, \ ldots, b_ {n}) = {\ begin {case} (b_ {1}, 1-b_ {2}, \ ldots, b_ {n}) и {\ text {если }} b_ {1} = 0 \\ (b_ {1}, d (b_ {2}, \ ldots, b_ {n})) {\ text {if}} b_ {1} = 1 \ end {случаях }}}$ $c (b_ {1}, b_ {2}, \ ldots, b_ {n}) = {\ begin {case} (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,…, bn) = {(b 1, b 2,…, bn), если b 1 = 0 (b 1, b (b 2,…, bn)) если b 1 = 1 {\ displaystyle d (b_ {1}, b_ {2}, \ ldots, b_ {n}) = {\ begin {cases} (b_ {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 {case}}}$ ${\ Displayst yle d (b_ {1}, b_ {2}, \ ldots, b_ {n}) = {\ begin {cases} (b_ {1}, b_ {2}, \ ldots, b_ {n}) {\ текст {if}} b_ {1} = 0 \\ (b_ {1}, b (b_ {2}, \ ldots, b_ {n})) {\ text {if}} b_ {1} = 1 \ конец {case}}}$

Группа Артина

Группа Артина A (Γ) - это группа со следующим представлением:

A (Γ) = ⟨a 1, a 2,…, a n | μ ij = μ ji для 1 ≤ i < j ≤ n ⟩ {\displaystyle A(\Gamma)=\left\langle a_{1},a_{2},\ldots,a_{n}|\mu _{ij}=\mu _{ji}{\text{ for }}1\leq i

A (\ Gamma) = \ left \ langle a_ {1}, a_ {2}, \ ldots, a_ {n} | \ mu _ {{ij}} = \ mu _ {{ji}} {\ text {for}} 1 \ leq i <j \ leq n \ right \ rangle

где $μ ij = aiajai… {\ displaystyle \ mu _ {ij} = a_ {i} a_ {j} a_ {i} \ ldots}$ $\ mu _ {{ij}} = a_ {i} a_ {j} a_ {i} \ ldots$ ( $mij {\ displaystyle m_ {ij}}$ $m_{ij}$ факторов) и $mij = mji {\ displaystyle m_ {ij} = m_ {ji}}$ $m _ {{ij}} = m _ {{ji}}$ .

Группы матриц

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

Полупрямые продукты

См. Также

Групповая криптография

Дополнительная литература

Алексей Мясников; Владимир Шпильрайн; Александр Ушаков (2008). Групповая криптография. Берлин: Birkhäuser Verlag.
Zhenfu Cao (2012). Новые направления современной криптографии. Бока-Ратон: CRC Press, Taylor Francis Group. ISBN 978-1-4665-0140-9.
Бенджамин Файн; и другие. «Аспекты криптографии на основе неабелевых групп: обзор и открытые проблемы». arXiv : 1103.4093.
Мясников Алексей Геннадьевич; Владимир Шпильрайн; Александр Ушаков (2011). Некоммутативная криптография и сложность теоретико-групповых задач. Американское математическое общество. ISBN 9780821853603.

Ссылки