2.3.1.1. Метод возведения в степень

Известно несколько методов шифрования, разработанных на основе дис­кретного возведения в степень. Наиболее распространенным из них явля­ется метод дискретного возведения в степень в конечных полях. К ним от­носятся криптоалгоритмы Диффи-Хелмана (DH) и Месси-Омура. Задача дискретного возведения в степень в аддитивной абелевой группе положена в основу построения алгоритмов на алгеброических кривых.

Идея криптографии с открытым ключом тесно связана с идеей односто­ронних функций. По заданному аргументу х легко вычислить значение фун­кции f(x), тогда как определение х из f(x) трудновычислимо. Здесь «трудно-вычислимость» понимается в смысле теории сложности. Ситуация изобра­жена на рис. 5.27.

Мы говорим о f(x), как о функции. Определение х из f(x) трудновычис­лимо только для криптоаналитика. Законный получатель информации име­ет подходящую лазейку. Далее такие односторонние функции будем назы­вать криптографическими.

Упомянем по этому поводу, что ни одного примера криптографической односторонней функции не известно. Зато существует много криптографи­ческих функций f(x), таких, что:

• Легко вычислить f(x) из х

• Определение х из f(x), вероятно, будет трудновычислимым.

Рис. 5.27. Смысл теории сложности для односторонней функции

С точки зрения криптографии с открытым ключом вполне подходят функ­ции, удовлетворяющие этим двум требованиям. В типичных криптосисте­мах с открытым ключом только прямой криптоанализ основан на вычисле­нии х из ^х). Могут существовать и другие, более гениальные криптоаналитические методы, избегающие этого вычисления. Таким образом, криптоаналитик может достичь успеха даже в том случае, когда доказано, что нахождение х из f(x) трудно вычислимо.

Функция f(x) будет односторонней, если перевод х в f(x) легок, а об­ратный перевод из f(x) в х трудновычислим. Второе требование часто заменяется более слабым условием: обратный перевод, вероятно, будет трудновычислимым.

Можно выделить две основные группы методов криптографической за-

щиты информации с открытым ключом, использующих ту или иную одно­стороннюю функцию с «потайной лазейкой». В качестве такой функции может быть использовано модульное возведение в степень с фиксирован­ным показателем степени m и модулем п:

f(x)=x^mmodn ( )

Эффективный алгоритм для обратной операции — извлечения корня т-ой степени по модулю п для произвольных тип неизвестен. Это так называ­емая проблема дискретного логарифмирования для больших чисел. Один из методов использует эффективный алгоритм извлечения корня при извест­ном разложении числа п на простые множители. Это и позволяет отнести функцию вида f(x) к классу односторонних функций с «потайной лазейкой».