id: Гость   вход   регистрация
текущее время 13:23 28/03/2024
Владелец: unknown (создано 08/02/2013 12:08), редакция от 10/02/2013 19:47 (автор: unknown) Печать
Категории: криптография, алгоритмы, шифрование с открытым ключом, распределение ключей
https://www.pgpru.com/Новости/2013/ВыполнениеПротоколаДиффи-ХеллманаВоВложенныхАлгебраическихСтруктурах
создать
просмотр
редакции
ссылки

08.02 // Выполнение протокола Диффи-Хеллмана во вложенных алгебраических структурах


Протокол Диффи-Хеллмана является истоком криптографии с открытым ключом и до сих пор применяется достаточно широко. Исходный простейший его вариант использует в качестве основы мультипликативную группу целых чисел Z*p по модулю простого числа p. Также есть открытый элемент g Z*p, который является примитивным корнем по модулю p.


Сам классический протокол выглядит так:


  1. Алиса выбирает целое число a, вычисляет A = ga mod p и публикует A.
  2. Боб выбирает целое число b, вычисляет B = gb mod p и публикует B.
  3. Алиса вычисляет KA = Ba mod p.
  4. Боб вычисляет KB = Ab mod p.

В итоге у Алисы и Боба получается совместно выведенный ключ K = KA = KB = gba mod p = gab mod p.


Безопасность протокола зависит от правильного выбора параметров, в т.ч. g. Для взлома протокола пассивный атакующий (Ева) должна вычислить gab на основании знания g и перехваченных параметров обмена ga и gb, что, как общепринято считать, сводится к труднорешаемой задаче поиска дискретного логарифма: нахождения a из g и ga. Однако, строгого доказательства эквивалентности решения проблемы Диффи-Хеллмана к поиску дискретных логарифмов до настоящего времени не существует. Также как и не существует строгого доказательства отсутствия простых методов решения таких задач.


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


Попытки оптимизации DH-протокола путём переноса его в различные алгебраические структуры применялись неоднократно. При этом признанно успешным оказалось лишь выполнение DH в группах точек эллиптических кривых.


Очередное оригинальное исследование по нестандартному выполнению DH-протокола представили Delaram KahrobaeI, Charalambos Koupparis и Vladimir Shpilrain (CUNY Graduate Center and City Tech, The City College of New York, City University of New York).


Они использовали алгебраические группы над кольцами, получая т.н. групповое кольцо, над котором впоследствии развернули матрицы. Полученная вложенная структура вида Mk (Zn [Sm ]) обладает очевидным интересным свойством: при небольших размерах составляющих элементов m, n, k, размер самой структуры получается достаточно большим. Что с одной стороны позволяет эффективно проводить вычисления, сохраняя небольшой размер ключа, а сдругой стороны обеспечить безопасность за счёт большой величины составного алгебраического объекта.


Так, один из вариантов протокола выглядит следующим образом:


  1. Алиса выбирает открытую матрицу MMk (Zn [Sm ]) и большое положительное число a, вычисляет Ma и публикует M, Ma.
  2. Боб выбирает другое большое положительное число b и публикует Mb.
  3. Обе стороны вычисляют совместный ключ K = (Ma) b = (Mb) a

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


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


Источник: ArXiV.org: Cryptography and Security, Group Theory.
См. также: Асимметричные алгоритмы на основе тропической алгебры.


 
Много комментариев (18) [показать комментарии/форму]
Общая оценка документа [показать форму]
средний балл: +3респондентов: 2