Отметим, что в определении шифра расшифрования не содержится требований инъективности функции f по переменной k Kp.

Алгебраической обобщенной моделью шифра назовем тройку ( Аш,Ар, f ).

К положительным свойствам этой модели относится возможность моделирования шифров как с симметричным, так и с асимметричным ключом.

При этом учитываются следующие соображения:

ключ kш Кш несекретен, а ключ kр=f (kш) Kp является секретным;

определение значения k связано с решением сложных проблем;

синтез пар ключей (kш , kр) проводится достаточно просто.

Заметим, что здесь проявляется возможность классификации шифров по параметру сложности вычисления значения f (kш) ключа расшифрования, что определяет основной параметр криптографической стойкости шифров с ассиметричным ключом.

Односторонние функции

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

Определение. Функция f: Х У называется односторонней (oneway function), если существует эффективный алгоритм для вычисления f(x) x, но не существует эффективного алгоритма для вычисления хотя бы одного элемента прообраза f -1(у).

Никто не знает, существуют ли вообще односторонние функции. Основным критерием отнесения функции f к классу односторонних или необратимых является отсутствие эффективных с вычислительной точки зрения алгоритмов обратного преобразования Y X. В криптографии под необpатимостью понимается не теоретическая необратимость функции, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства за заданный интервал времени. Таким образом, проблемы построения односторонних функций связаны с теоретико-вероятностной сложностью алгоритмов и алгоритмическими вопросами теории чисел.

Множество классов необратимых функций и порождает все разнообразие систем с открытым ключом. Большинство предлагаемых сегодня криптосистем с открытым ключом опираются на один из следующих типов необратимых преобразований:

338

1.Разложение больших целых чисел на простые множители.

2.Вычисление логарифма в конечном поле.

3.Вычисление корней алгебраических уравнений.

Факторизация

В качестве первого примера однонаправленной функции рассмотрим целочисленное умножение. Прямая задача — вычисление произведения двух очень больших целых чисел р и q, т.е. нахождение значения n=p·q, является относительно несложной задачей.

Обратная задача, называемая задачей факторизации, - разложение на множители большого целого числа, т.е. нахождение делителей p и q большого целого числа

n = p·q,

является практически неразрешимой задачей при достаточно больших значениях n. По современным оценкам теории чисел при целом n 2664 и p q для разложения числа n потребуется около 1023 операций, т.е. задача практически неразрешима на современных ЭВМ.

Если простые сомножители имеют специальный вид, известны более эффективные алгоритмы факторизации. Речь идет о сомножителях р, таких, у которых величины р-1 или р+1 являются «гладкими», т. е. имеют только малые простые делители.

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

Дискретный логарифм

Другой пример однонаправленной функции — это модульная экспонента с фиксированными основанием и модулем. Пусть а и n - целые числа, такие, что 1 a n. Тогда модульная экспонента с основанием a по модулю n представляет собой функцию

y = ax mod n,

где х – целое число. Естественно записать х = loga (у).

Задачу обращения этой функции в множестве целых чисел называют задачей нахождения дискретного логарифма.

Определение. Число х называют дискретным логарифмом числа y по основанию a и модулю n, если для всех а Zn найдется такое целое y, что

y = ax mod n.

339