Современная прикладная криптография (стр. 16 )

Дано: G = (g) – циклическая группа порядка p с генератором g, в которой DLP трудно решаема. Это открытая информация.

Сторона А: выбирает секретный ключ а из {1,…,p} и вычисляет открытый ключ g*g*…*g=Y(a раз), передает Y стороне B по открытому каналу с аутентификацией.

Сторона B: выбирает секретный ключ b из {1,…,p} и вычисляет открытый ключ g*g*…*g=Y_B (b раз), передает Y стороне A по открытому каналу с аутентификацией.

Сторона А: вычисляет К= Y*…* Y (a раз) = g*…*g(ab раз)

Сторона B: вычисляет К= Y*…* Y (b раз) = g*…*g(ba раз)

Вычислительная задача Диффи-Хеллмана (The computational DH problem - CDH)

Дано: G = (g), g, g, g.

Найти: g.

Задача принятия решения Диффи-Хеллмана (The decisional HH problem – DDH)

Дано: G = (g), g, g, g, g.

Найти: g^ab = g^c или не равно.

(The Gap DH problem)

Дано: G = (g), g, g, g, и оракул, который корректно решает задачу принятия решений Диффи-Хеллмана.

Найти: g.

Очевидно, что если задача DDH является трудно решаемой в группе (g), то тогда трудно решаемы задачи CDH и DLP.

Сильная задача Диффи-Хеллмана и ее варианты(SDH - strong Diffie-Hellman problem)

t-слабая задача Диффи-Хеллмана(t-weak Diffie-Hellman(t-wDH) problem

Дано: G = (g), g, g) для i = 1,2,…,t.

Найти: g.

(задача была сформулирована Mitsunari-Sakai-Kasahara в 2002 году)

t-сильная задача Диффи-Хеллмана(t-weak Diffie-Hellman(t-wDH) problem

Дано: G = (g), g, g) для i = 1,2,…,t.

Найти: g

(задача является ослабленной версией t-wDH задачи. Она была введена Boneh и Boyen (eurocrypt 2004) для построения схем коротких подписей)

Задача SDH обощается на так называемые билинейные группы.

The `-Bilinear Diffie-Hellman Inversion (`-BDHI) Problem.

E-1 -06

Security Analysis of the Strong Diffie-Hellman Problem

(Анализ безопасности сильной задачи Диффи-Хеллмана)

Jung Hee Cheon

В работе показано, что если g – элемент простого порядка p в абелевой группе и а из Z, то если известны элементы g, g, и g для некоторого положительного делителя d числа (p - 1), то секрет а можно найти за

O(log p·(+)) групповых операций, используя память объема O(max{,}). Если g (i = 0, 1, 2, . . . , d) известны для положительного делителя d числа (p + 1), то секрет а может быть найден за O(log p·(+d)) групповых операций, используя память объема O(max{, }). Это означает, что SDH задача имеет вычислительную сложность в O() меньшую, чем DLP для таких простых чисел.

Далее автор применяет предложенный алгоритм к криптосхемам, основанным на DLP в абелевых группах простого порядка. Это понижает сложность нахождения ключа с О() до О() для подписи вслепую Болдыревой и схемы шифрования Эль Гамаля, когда (p-1) (соответственно (p+1)) имеет делитель d (соответственно d) .

2.4. Односторонняя функция с секретом

и Хеллман развили понятие однонаправленной (односторонней) функции, позволившее приспособить его для целей шифрования и давшее начало всей новой области криптографии - криптографии с открытым ключом [4].

Однонаправленной (односторонней) функцией с секретом (или с лазейкой, с потайной дверью - a trapdoor one-way function) называется зависящая от параметра k функция , такая, что при известном параметре k известны полиномиальные алгоритмы и , позволяющие легко вычислять соответственно значение для всех х из области определения и прообраз для всех у из области значений, однако, почти для всех k и почти для всех y из области значений функции , нахождение вычислительно неосуществимо без знания k (не существует полиномиального алгоритма), даже при известном алгоритме .

Один из первых предложенных примеров таких функций основан на степенной функции f(x) = mod n, вычисление которой при известных m и n производится одним из методов быстрого экспоненцирования не более чем за ^3 операций умножения. Преобразование, обратное к преобразованию возведения в степень mod n называется вычислением корня m-й степени по модулю n. В настоящее время эффективный алгоритм вычисления такого x, что mod n = у при известных числах m, n и у требует знания разложения числа n по степеням простых чисел. Таким образом, эта информация может служить как секретный параметр k.

Именно эта односторонняя функция с секретом используется в криптосистеме с открытым ключом RSA [9]. Другие широко известные примеры односторонних функций с секретом легли в основу криптосистемы на основе задачи о рюкзаке (knapsack function) [24], и криптосистемы Мак Элайса [57], и другие. Выбор систем и функций для изучения должен определяться их распространенностью применения и объемом необходимого для их объяснения нового материала.

2.5. Открытое шифрование, криптосистема с открытым ключом

На основе введенного понятия односторонней функции с секретом Диффи и Хеллман предложили новый принцип так называемого открытого шифрования, который вместе с открытым распределением ключей составил новое направление в криптографии, когда для организации секретной связи не требуется снабжения абонентов секретной информацией(ключами).

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