Глава 4

Системы с открытым ключом

§ 1. Однонаправленные функции

Два понятия - однонаправленной функции и однонаправленной функции с «потайным ходом», или «лазейкой» - являются центральными для всей криптографии с открытым ключом. Рассмотрим произвольные множества X и У, а также некоторую функцию f:X-Y. Обозначим через f[X] область значений /. Функция / называется однонаправленной, если ее значение f{x) может быть легко вычислено для каждого аргумента х Е X, тогда как почти для всех у G f{X] нахождение такого х £ X, что f{x) = у, является трудновычислимым. Однонаправленные функции не следует путать с функциями, которые являются математически необратимыми из-за того, что они не взаимнооднозначны или не «на» (то есть из-за того, что либо существует несколько различных значений х, таких что f{x) = у, либо же их нет вовсе).

Нынешнее состояние наших знаний пока еще не позволяет нам доказать, что однонаправленные функции (обоих типов) вообще существуют, так как их существование разрешило бы знамени-

тую {Т = ЛГР)-проблему [186]. Более того, теория JVP-полноты не кажется вполне убедительной, чтобы обеспечить даже простую аргументацию существования таких функций [64, 169, 207]. И все же, несмотря ни на что, у нас в этом смысле имеются кандидаты среди функций, эффективно вычислять которые мы умеем, хотя при этом никаких эффективных алгоритмов вычисления обратных им (во всяком случае среди общедоступных!) до сих пор не известно.

* Карл Померавц [290], как-бы подтверждая, что по-амернкааскж время - деньги, разработал проект специализированного компьютера, который при использовании самого эффективного алгоритма факторизгщии в принципе позволяет 1фи все более увеличивающемся объеме оборудования разлагать на множители за заданное время числа любой длины, и оценил стоимость разработки такого компьютера в зависимости от размера этих чисел. Ддя факторизации четырехсотзначного десятичного числа в течение одного года она равна примерно 100 миллиардам миллиардов долларов!

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

Другим очень вгьжным примером кандидата на однонаправленную функцию является модульное возведение в степень, или модульное экспоненцирование (с фиксированными основанием и модулем). Пусть п и а - целые числа, такие, что 1<а<п, и пусть также Z„ = {Q, 1,2,... , п-1}. Тогда модульным возведением в степень, или экспоненцированием (относительно основания а и модуля п), называется функция /а,пп -Z„, определяемая как fa,n{fn) = о"* mod п, где i mod j - положительный остаток при делении j на j. Сразу не очевидно, что такую функцию можно вычислить эффективно, когда длина каждого из трех параметров а, пят составляет несколько сотен знаков. То, что, возможно, это и в самом деле так, лучше всего продемонстрировать на примере:

« = (((a.a)W.«,

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

S 1 Одионадравлснные функщжм 45

экспонента т является числом длиной / битов то, для того чтобы вычислить а"* mod п, приведенному<ниже рекурсивному алгоритму потребуется выполнить от / до 2/ модульных умножений (считая при этом }гмножением и возведение в квадрат):

function expmod(a, т, п) if m = О then return 1

if m четно then return expmoda,,nj mod n else return (a expmod{a, m-1, n)) mod n

По аналогии с вещественным анализом задача вычисления функции, обратной модульному возведению в степень, известна как задача дискретного логарифмирования: даны целые числа а, п та. X, требуется найти такое целое т (если конечно оно существует), что а"* mod п = х. Например, 5 mod 21 = 16. Тале что 4 - это дискретный логарифм 16 с основанием 5 по модулю 21. При желании можно проверить, например, что число 3 вообще не имеет логарифма с основанием 5 по модулю 21. В настоящее время вычисление больших модульных экспонент можно выполнить очень быстро даже на «персоналке», но, тем не менее, на сегодняшний день неизвестно ни одного алгоритма вычисления дискретных логарифмов больших чисел за приемлемое время даже на самых мощных, самьгх быстродействующих суперкомпьютерах. При этом, хотя мы и не можем доказать, что эффективных таких алгоритмов вообще не существует, имеются веские основания предполагать, что модульное возведение в степень (с фиксированными основанием и модулем) действительно является однонаправленной функцией.

Очевидно, что однонапргшленные функции не могут непосредственно использоваться в качестве криптосистем (когда т шифруется как /(т) ), поскольку тогда даже законный получатель не смог бы определить открытый текст! Позднее мы увидим, что несмотря на это они полезны для занщты паролей (см. § 5.3). Гораздо более употребимым в криптографии является понятие однонаправленной функции с потайным ходом (лазейкой). Функция /: X -> У называется однонаправленной функцией с потайным ходом (или, что то же самое, с лазейкой), если, во-нёрвых, не только сама /, но и функция обратная ей, могут быть вычислены эффективно, а во-вторых, даже если такой эффек-