id: Гость   вход   регистрация
текущее время 15:56 28/03/2024
Владелец: unknown (создано 15/01/2013 16:52), редакция от 21/01/2013 11:35 (автор: unknown) Печать
Категории: криптография, алгоритмы, шифрование с открытым ключом, распределение ключей, протоколы
https://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


 
— Гость (17/01/2013 02:58)   <#>
В тропической алгебре в явном виде отсутствует вычитание (например 13 – 4), поскольку не существует реального числа, удовлетворяющего решению уравнения 4 ⊕ x = 13, однако может быть определено тропическое деление за исключением отсутствия аксиомы обратного элемента по сложению. Это определяет тропическую алгебраическую систему как полукольцо.

А такое хорошее начало было... Я думал, поле будет. Или все возможные поля уже известны и описаны (с тоностью до изоморфизма)?
— unknown (17/01/2013 10:20)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Есть не вполне полноценные малоизвестные квазиполя, неополя и прочие экзотические объекты и ещё более экзотические криптосистемы на их основе.

А зачем именно поле? Чем примитивнее объект, тем с одной стороны меньше возможностей для построений на его основе чего-либо, а с другой стороны, тем меньше лишних операций, которые могут быть использованы для атак. Для обмена ключами и асимметричного шифрования достаточно и группы или даже её более примитивного аналога (квазигруппы, полугруппы). И если нет способа перенести операции из группы в поле (как в ECC), то стойкость повышается, при прочих равных.
— Гость (18/01/2013 01:04)   <#>

Ну, я не знал, что
если нет способа перенести операции из группы в поле (как в ECC), то стойкость повышается, при прочих равных.
Если из общих соображений, то поле даёт универсальность и "полноту" по операциям, анализ хорошо строится поверх таких структур, а если структура совсем примитивна, то там даже топологии может не быть.
— Гость (18/01/2013 01:24)   <#>
“There is no deeper meaning in the adjective ‘tropical’. It simply stands for the French view of Brazil.” ©
А вообще, https://en.wikipedia.org/wiki/Max-plus_algebra. :)
— unknown (18/01/2013 09:49, исправлен 18/01/2013 13:06)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

По максимуму вместо минимума — это как-бы зеркальный вариант с минус-бесконечностью.


Интереснее другое. Почему-то во всех публикациях встречается только полукольцо на бесконечности. А если взять конечный объект и вместо бесконечности использовать максимальный элемент множества? А все операции проводить по его модулю. Возможно, тогда удасться непротиворечиво ввести обратные операции и построить хотя-бы урезанный аналог конечного поля.


Если пофантазировать, что это было бы так, то возможны интересные перспективы и в симметричных криптоалгоритмах, и в симметричном криптоанализе. А вдруг как обычные полиномы AES, SHA-3, GOST-Стрибог легко разрешаются в тропическом представлении? А власти скрывают!


P.S.: По этой теореме может выйти полуполе. Впрочем, почти поле или квазиполе на тропических полукольцах, вероятно, тоже возможны.

— Гость (19/01/2013 00:45)   <#>
А если взять конечный объект и вместо бесконечности использовать максимальный элемент множества?
Даже не знаю. Бесконечность обычно определяется, как формальный элемент, больший чем все элементы множества. В случае классического анализа бесконечность множеству не принадлежит, но в конечном множестве максимум ему как раз принадлжежит, т.е. как минимум для одного элемента множества так определённая бесконечность будет не больше его, а равна ему. Возможно, это всё проблемой не является. Я не математик, чтоб судить.
— Блондинка (20/01/2013 19:30)   <#>
Вообще-то наименьшая степень f(x) равна 0. И тогда order(fg)=order(f)+order(g).
Более того, если f(x)=x, то fg=3x^3+x^2, order(fg)=2, и вывод о том, что порядок произведения равен минимуму снова неверен.
Собственно, дальше можно не читать, ибо предпосылки неверны.
— unknown (20/01/2013 20:59)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Спасибо за очевидное замечание.


Скорее всего, получится наоборот. Вводная часть по тропической алгебре была скомпилирована из разных источников, разобраться в которых у меня не хватило элементарной компетентности. Она не вся взята из самой работы и как раз этот кусок к работе не относится. Придёться выкинуть его из новости, если не найду первоисточник и причину ошибки и возможность её исправления.
— Блондинка (20/01/2013 22:43)   <#>


Вообще, по приведённому выше определению тропической алгебры, умножение там всегда коммутативно. А значит такой тропической алгебры R (в которой мы нашли бы два неккомутирующих элемента) не существует.

Или в данном случае ⊗ – это что-то другое? Может, это обычное умножение матриц (которое действительно некоммутативно)? Или фраза "как и в наиболее традиционной алгебре, тропические операции коммутативны" тоже относится к вводной части и действительности не соответствует? Но тогда – что же такое на самом деле тропическая алгебра?
— Гость (20/01/2013 23:33)   <#>
[офтоп]Да тропическая алгебра – это уже вчерашний день. Сейчас лучшие умы человечества анализируют субтропическую и экваториальную!!11[/офтоп]
— unknown (20/01/2013 23:35)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
То, что мне удалось поместить в новость — это только основы работы с числами в ТА, самое простое и наглядное. Про тропические полиномы, матрицы и более сложные объекты пришлось только упомянуть. Авторы действительно используют и полиномы и матрицы и разбирают примеры работы с ними в ТА. Но разместить это на движке сайта, который не поддерживает LaTeX-форматирования как-то малореально, да и перегружать новость чем-то, кроме отсылок к общим идеям, не хотелось. По этой же причине в новости приведён только протокол совместной генерации ключа, а протокол асимметричного шифрования здесь не разобран вовсе.

Главное, что если кого-то заинтересует идея, он сможет посмотреть подробности в первоисточниках.
— Блондинка (21/01/2013 02:30)   <#>
Судя по всему, матричные операции и операции с полиномами – они ровно по тем же формулам, что и в обычной алгебре, только классические сложения/умножения заменены на соотв. тропические. Просто желательно такие вещи указывать, чтоб не возникало сомнений и разночтений. Учитывая специфичность описываемой алгебры, это не очевидно.
А в остальном – спасибо за статью, даёт пищу для размышлений!
— unknown (21/01/2013 10:22, исправлен 21/01/2013 10:43)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Поправил с вашей помощью опечатки в новости и разобрал ваш пример:


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


degree (f) = 1
degree (g) = 2
order (f) = 1
order (g) = 1


f(x) ∙ g(x) = 3x3 + x2


degree (fg) = 3
order (fg) = 2


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


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


Вроде теперь понятно, где сложение, а где минимум и максимум?

— Гость (25/01/2013 16:14, исправлен 25/01/2013 16:28)   <#>

Тропическая алгебра

Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3