A version of the Diffie - Hellman protocol based on using additional hidden factors.pdf В серии работ [1-4] В. А. Романьков предложил использовать скрытые множители из подгрупп мультипликативных групп соответствующих колец вычетов и конечных полей, чтобы придать системе шифрования RSA и ряду других криптографических схем свойства семантической секретности. В данной работе представлен аналог классического протокола Диффи - Хеллмана, основанного на трудности вычисления дискретного логарифма в мультипликативной группе конечного поля, также использующий скрытые множители из подгрупп этого поля. Пусть G = f* - мультипликативная группа конечного поля fq, q = p* (p - простое число), g - порождающий элемент этой группы. Целое x, 0 ^ x ^ q - 2, удовлетворяющее уравнению вида gx = f, где f - произвольный элемент группы G, называется дискретным логарифмом элемента f по основанию g. Задача нахождения logg (f) по порождающему элементу g и произвольному f известна как проблема дискретного логарифма. Она считается вычислительно трудной, значит, функция $(x) = gx может рассматриваться как односторонняя. Задача вычисления дискретного логарифма составляет основу целого ряда алгоритмов криптографии, в частности, на её сложности основывается криптографическая стойкость классического протокола Диффи - Хеллмана [5 - 7]. Версия протокола Диффи - Хеллмана Протокол Диффи - Хеллмана строится на мультипликативной группе конечного поля. В предлагаемой версии этого протокола в качестве основы берётся мультипликативная группа f* простого конечного поля fp характеристики p, которая выбирается корреспондентами Алисой и Бобом на основе некоторых других данных (см. подробности далее). Алгоритмы построения больших простых чисел, в данном случае числа p, хорошо известны и эффективны [5, 6]. Итак, двум корреспондентам Алисе и Бобу необходимо выбрать секретным образом достаточно большое случайное число (секретный ключ), с помощью которого будет производиться дальнейшее шифрование, или для каких-то других целей. Считается, что переписка по поводу выбора этого числа происходит по открытому каналу связи. Установка. Сначала Алиса выбирает секретное простое число r, а Боб - секретное простое число s. Затем Алиса случайным образом выбирает число x и передаёт Бобу произведение r1 = rx. Боб выбирает случайным образом число y и передаёт Алисе произведение s1 = sy. После этого они открытым образом договариваются о выборе простого числа p, такого, что p = 1 + 2r1s1z. Далее Алиса и Боб используют группу G = f* для реализации алгоритма. Они договариваются о выборе элемента g группы G достаточно большого порядка | g| . Как и в классическом случае, в качестве g можно выбрать порождающий элемент. Данные p и g являются открытыми. Выбор циклических подгрупп. Алиса выбирает циклическую подгруппу F группы G порядка r. Для этого она находит порождающий элемент этой подгруппы f Е f*, |f | = r, который существует, так как r|(p - 1) по построению p. Для нахождения этого элемента она случайным образом выбирает последовательно элементы f, i = 1, 2,... , каждый раз вычисляя степень f/, где t = 2xs1 z = (p - 1)/r, до тех пор, пока не получит неравенство f = 1. Тогда она полагает f = f*. Ясно, что fr = fp-1 = 1. Так как r - простое число, то |f | = r. В группе fP в точности t элементов являются корнями из 1 степени t. Вероятность выбора такого элемента при случайном равномерном распределении равна t/(p - 1) = 1/r. Следовательно, вероятность неудачи при выборе в m последовательных испытаниях равна (1/r)m. При достаточно большом r и сравнительно небольшом значении m (20-30) вероятностью неудачи можно пренебречь. После того как f найден, Алиса передаёт его Бобу. Аналогично Боб выбирает циклическую подгруппу H группы G порядка s и отправляет её порождающий элемент h Алисе. Далее Алиса выбирает случайным образом натуральное число a и элемент z G H (случайную степень элемента h), вычисляет u = zgar и передаёт результат Бобу. Тем временем Боб аналогичным образом выбирает натуральное число b и элемент y G F (случайную степень элемента f) и сообщает по сети элемент v = ygbs Алисе. Формирование секретного ключа. Алиса, зная a, v и r, вычисляет vra = = yragbsra = gabrs, так как yr = 1 (mod n). Боб, зная b, u и s, вычисляет usb = zsbgarsb = = gabrs. Таким образом, корреспонденты Алиса и Боб сформировали секретное число gabrs. Криптографическая стойкость. Криптографическая стойкость данного протокола основывается на трудной разрешимости двух проблем - дискретного логарифма и определения порядка элемента мультипликативной группы конечно поля. Известна разрешимость второй задачи за полиномиальное время при знании разложения порядка мультипликативной группы поля на примарные множители [5]. Тогда можно со сравнимой трудоёмкостью находить дискретные логарифмы, например алгоритмом Полига - Сильвера - Хеллмана. Такого разложения потенциальный взломщик не имеет. Более того, указанный алгоритм допускает практическое применение далеко не всегда. При наличии больших простых делителей в разложении необходимая база данных становится очень большой, что существенно замедляет работу алгоритма [5, 6]. Замечание 1. В предложенной версии числа r и s простые. Это условие можно исключить. Подгруппы F и H можно выбирать не обязательно циклическими. Можно, например, выбрать F = gp(fi,...,fk), где наименьшее общее кратное порядков элементов fi равно r. Точно так же можно выбирать H, где аналогичное наименьшее общее кратное равно s.

Скачать электронную версию публикации