id: Гость   вход   регистрация
текущее время 06:58 19/03/2024
Владелец: unknown (создано 15/01/2013 16:52), редакция от 21/01/2013 11:35 (автор: unknown) Печать
Категории: криптография, алгоритмы, шифрование с открытым ключом, распределение ключей, протоколы
http://www.pgpru.com/Новости/2013/АсимметричныеКриптоалгоритмыНаОсновеТропическойАлгебры
создать
просмотр
редакции
ссылки

15.01 // Асимметричные криптоалгоритмы на основе тропической алгебры


Те, кому часто приходиться оперировать в своих выводах и расчётах со степенями больших величин, зачастую не задумываясь применяют правило xaxb = xa+b. При этом связь между умножением величин и сложением степеней выглядит вполне естественной. Реже приходиться задумываться о закономерностях сложения вида (xa + xb).


Рассмотрим такие операции на основе полиномов. Пусть f(x) = x + 2, а g(x) = 3x2 + x.


Пусть наибольшая степень полинома является степенью (degree) собственно самого полинома, а наименьшая степень — его порядком (order).


Тогда:


  1. degree (f) = 1
  2. degree (g) = 2
  3. order (f) = 0
  4. order (g) = 1

После перемножения полиномов мы получим:


f(x)g(x) = (x + 2)(3x2 + x) = 3x3 + x2 + 6x2 + 2x = 3x3 + 7x2 + 2x


Тогда:


  1. degree (f ∙ g) = 3
  2. order (f ∙ g) = 1

Проделаем такую же операцию со сложением полиномов:


f(x) + g(x) = x + 2 + 3x2 + x = 3x2 + 2x + 2


Тогда:


  1. degree (f + g) = 2
  2. order (f + g) = 0

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


По некоторым соображениям, больший интерес представляет нахождение минимума двух операторов.
Теперь можно ввести две абстрактные операции:


xy = min { x, y }
xy = x + y


Нахождение такого же минимума как в классической алгебре, называется тропическим сложением в тропической алгебре. Сложение в классической алгебре соответствует тропическому умножению в тропической алгебре.


Иногда в качестве обозначений используют обычные знаки + и ∙. Тогда вполне правомерны, например, такие выражения как 3 + 2 = 2 или 2 ∙ 1 = 3.


Несмотря на тривиальные основы, переход к изучению тропической алгебры произошёл лишь в 70-е — 90-е годы XX-века.


Также, как и в наиболее традиционной алгебре, тропические операции коммутативны:


ab = ba


ab = ba


ассоциативны:


(ab) ⊕ c = a ⊕ (bc)
(ab) ⊗ c = a ⊗ (bc)


и дистрибутивны:


a ⊗ (bc) = (ab) ⊕ (ac)


Таблица соотношений операций между традиционной и тропической алгеброй выглядит так:


традиционнаятропическая
min {a,b} ab
a + b ab
ab a 0 b
ab ab = ba
a / b b√a
max {a, b} a v b

Следует отметить, что операция нахождения минимума ⊕ — необратима.


Осталось определить в алгебре понятие нейтральных и обратных элементов:


a ⊕ ∞ = a — бесконечность является нейтральным элементом для сложения.
При этом aa = a;


a ⊗ 0 = a — ноль является нейтральным элементом для умножения.
При этом a ⊗ ∞ = ∞.


a ⊗ -a = 0, откуда a-1 = 1/a = -a, обратным элементом является противоположное по знаку число.
Поскольку нейтральным элементом для операции ⊕ является ∞, то нахождение обратного элемента b, такого, что ab = ∞ не имеет смысла. Можно рассматривать два случая: a ⊕ 0 = 0 при a ≥ 0; и a ⊕ 0 = a при a < 0.


Для наглядности также можно составить таблицы сложения и умножения в тропической алгебре:


1234567
1 1111111
2 1222222
3 1233333
4 1234444
5 1234555
6 1234566
7 1234567

1234567
1 2345678
2 3456789
3 45678910
4 567891011
5 6789101112
6 78910111213
7 891011121314

В тропической алгебре в явном виде отсутствует вычитание (например 13 – 4), поскольку не существует реального числа, удовлетворяющего решению уравнения 4 ⊕ x = 13, однако может быть определено тропическое деление за исключением отсутствия аксиомы обратного элемента по сложению. Это определяет тропическую алгебраическую систему как полукольцо.


На первый взгляд, эта всего лишь одна из множества экзотических алгебр, которая смотрится достаточно примитивно, но на самом деле это не так. Изучены тропические полиномы, векторы, матрицы, топологические объекты. В конце двадцатого века был распознан большой потенциал в описании решения систем уравнений, римановых поверхностей (и даже таких экзотических объектов как "амёбы с тентаклями") и других областей топологии, задач из теории графов. Тропическая алгебра находит применение в анализе сетей, физике, социологии и др.


Исследователи Дима (Дмитрий) Григорьев (Институт информационных и инженерных наук и технологий, Научно-технологический Университет Лилль, Франция, при содействии Российского Агентства по науке и инновациям) и Владимир Шпильрейн (Кафедра математики, Сити-колледж, Нью-Йорк США, при содействии Фонда национальных научных исследований США) решили изучить перспективы криптографических систем, выполненных на основе тропической алгебры.


Первоначально они рассмотрели два ранее известных протокола согласования ключей Штикеля, работающих в "обычной" алгебраической системе:


Первый протокол Штикеля использует публичную (открытую) некоммутативную полугруппу G и открытые элементы a, bG, такие, что abba:


  1. Алиса выбирает два случайных натуральных числа n, m и посылает u = anbm Бобу.
  2. Боб выбирает два случайных натуральных числа r, s и посылает v = arbs Алисе.
  3. Алиса вычисляет KA = anvbm = an+rbm+s.
  4. Боб вычисляет KB = arubs = an+rbm+s.

Как нетрудно заметить, совместно вычисленный общий ключ K = KA = KB.


Второй протокол Штикеля обобщает эту процедуру на любое кольцо, хотя может работать и с полукольцом. Пусть R — это открытое некоммутативное кольцо (или полукольцо) и открытые элементы a, bR, такие, что abba:


  1. Алиса выбирает два случайных полинома p1(x), p2(x) (с положительными целыми коэффициентами) и посылает p1(a) ∙ p2(b) Бобу
  2. Боб выбирает два случайных полинома q1(x), q2(x) и посылает q1(a) ∙ q2(b) Алисе.
  3. Алиса вычисляет KA = p1(a) ∙ (q1(a) ∙ q2(b)) ∙ p2(b)
  4. Боб вычисляет KB = q1(a) ∙ (p1(a) ∙ p2(b)) ∙ q2(b)

Поскольку p1(a) ∙ q1(a) = q1(a) ∙ p1(a) и p2(b) ∙ q2(b) = q2(b) ∙ p2(b), то Алиса и Боб получают совместно вычисленный общий ключ K = KA = KB.


Как видно из второго протокола, он имеет все необходимые предпосылки для переноса в систему тропической алгебры. Тогда тропический протокол будет выглядеть, по мнению авторов, так:


Пусть R — тропическая алгебра, заданная матрицами n x n над целыми числами и A, BR — открыто доступные (публичные) матрицы, такие, что A ⊗ B ≠ B ⊗ A.


  1. Алиса выбирает два случайных тропических полинома p1(x), p2(x) (с целыми коэффициентами) и посылает p1(A) ⊗ p2(B) Бобу.
  2. Боб выбирает два случайных тропических полинома q1(x), q2(x) (с целыми коэффициентами) и посылает q1(A) ⊗ q2(B) Алисе.
  3. Алиса вычисляет KA = p1(A) ⊗ (q1(A) ⊗ q2(B)) ⊗ p2(B).
  4. Боб вычисляет KB = q1(A) ⊗ (p1(A) ⊗ p2(B)) ⊗ q2(B).

Поскольку p1(A) ⊗ q1(A) = q1(A) ⊗ p1(A) и p2(B) ⊗ q2(B) = q2(B) ⊗ p2(B), то Алиса и Боб получают совместно вычисленный общий ключ K = KA = KB.


Авторы отмечают, что оригинальные протоколы Штикеля — нестойкие, т.к. могут быть уязвимы к линейно-алгебраическим атакам. В то время как тропический протокол основан на неинвертируемых матрицах, которые не могут быть сведены к системам линейных уравнений. Часть уравнений тропического протокола может быть сведена к особым формам линейных уравнений, решение которых, тем не менее, не относится к классу полиномиальных задач.


Также в своей работе авторы рассматривают систему шифрования на основе бирациональных автоморфизмов тропической полиномиальной алгебры.


Исследования по созданию криптографических алгоритмов и протоколов в экзотических алгебраических системах ведутся длительное время и в больших объёмах. Многие из них оказались нестойкими. Многие представляют лишь теоретический интерес из-за сложности доказательства стойкости или непрактичности реализации. Однако, существенным стимулом служит потенциальная возможность создания как более стойких (в некоторых случаях и квантовостойких), так и менее ресурсоёмких систем.


Единственным широко признанным результатом таких исследований стало создание алгоритмов, работающих в группах точек эллиптических кривых.


Использование рассмотренных в данной публикации алгоритмов и протоколов может быть перспективным из-за исходной простоты использованной алгебраической системы — тропической алгебры.


Источник: Cryptology ePrint Archive


 
Много комментариев (14) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3