Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Нынешнее состояние наших знаний пока еще не позволяет нам доказать, что однонаправленные функции (обоих типов) вообще существуют, так как их существование разрешило бы знамени-?
тую (Р — Лг'Р)-проблему [186]. Более того, теория IVP-полноты не кажется вполне убедительной, чтобы обеспечить даже простую аргументацию существования таких функций [64, 169, 207]. И все же, несмотря ни на что, у нас в этом смысле имеются кандидаты среди функций, эффективно вычислять которые мы умеем, хотя при этом никаких эффективных алгоритмов вычисления обратных им (во всяком случае среди общедоступных!) до сих пор не известно.
44 Системы с открытым ключом
Глава 4
Первым простым примером кандидата на однонаправленную функцию является целочисленное умножение. В самом деле, известно, что перемножить два любых,-пусть и очень больших, числа относительно нетрудно, тогда как даже самый мощный из существующих сейчас компьютеров не в состоянии разложить на множители с помощью наилучшего имеющегося в его распоряжении алгоритма четырехсотзначное десятичное число, являющееся произведением двух примерно одинакового размера простых чисел. Конечно, необходимо понимать, что «не в состоянии» здесь означает «не в состоянии за приемлемое время (например, в течении человеческой жизни или за время, ограниченное возрастом вселенной)»1.
Другим очень важным примером кандидата на однонаправленную функцию является модульное возведение в степень, или модульное эхспоненцирование (с фиксированными основанием и модулем). Пусть п и а — целые числа, такие, что 1<а<п, и пусть также Z„ = {0,1,2,... , п—1}. Тогда модульным возведением в степень, или экспоненцированием (относительно основания а и модуля п), называется функция fa n: Zn —> Zn, определяемая как fa,n{jn) — am mod n, где г mod j — положительный остаток при делении i на j. Сразу не очевидно, что такую функцию можно вычислить эффективно, когда длина каждого из трех параметров а, п и т составляет несколько сотен знаков. То, что, возможно, это и в самом деле так, лучше всего продемонстрировать на примере:
Л25 ///я2 я
а = (((а - а) ) ) а ,
который показывает, что а25 можно вычислить с помощью всего лишь четырех возведений в квадрат и двух умножений. При вычислении ат mod п приведение по модулю п желательно делать после каждого возведения в квадрат и каждого умножения, чтобы избежать получения очень больших целых чисел. Если
1 Карл Померавц [290], как-бы подтверждая, что по-американски цремя — деньги, разработал проект специализированного компьютера, который при использовании самого эффективного алгоритма факторизации в принципе позволяет при все более увеличивающемся объеме оборудования разлагать на множители за заданное время числа любой длины, и оценил стоимость разработки такого компьютера в зависимости от размера этих чисел. Для факторизации четырехсотзначного десятичного числа в течение одного года она равна примерно 100 миллиардам миллиардов долларов!
Однонаправленные функции 45
экспонента т является числом длиной I битов то, для того чтобы вычислить ат mod п, приведенному ниже рекурсивному алгоритму потребуется выполнить от / до 21 модульных умножений (считая при этом умножением и возведение в квадрат):
function expmod(a, т, п) if т — 0 then return 1
if т четно then return (expmod (a, —, mod n
else return (a • expmod(a, m—1, n)) mod n
По аналогии с вещественным анализом задача вычисления функции, обратной модульному возведению в степень, известна как задана дискретного логарифмирования: даны целые числа а, п иг, требуется найти такое целое т (если конечно оно существует), что ат mod п = х. Например, 54 mod 21 = 16. Так что 4 — это дискретный логарифм 16 с основанием 5 по модулю 21. При желании можно проверить, например, что число 3 вообще не имеет логарифма с основанием 5 по модулю 21. В настоящее время вычисление больших модульных экспонент можно выполнить очень быстро даже на «персоналке», но, тем не менее, на сегодняшний день неизвестно ни одного алгоритма вычисления дискретных логарифмов больших чисел за приемлемое время даже на самых мощных, самых быстродействующих суперкомпьютерах. При этом, хотя мы и не можем доказать, что эффективных таких алгоритмов вообще не существует, имеются веские основания предполагать, что модульное возведение в степень (с фиксированными основанием и модулем) действительно является однонаправленной функцией.
Очевидно, что однонаправленные функции не могут непосредственно использоваться в качестве криптосистем (когда т шифруется как f(m)), поскольку тогда даже законный получатель не смог бы определить открытый текст! Позднее мы увидим, что несмотря на это они полезны для защиты паролей (см. § 5.3). Гораздо более употребимым в криптографии является понятие однонаправленной функции с потайным ходом (лазейкой). Функция f :X -+Y называется однонаправленной функцией с потайным ходом (или, что то же самое, с лазейкой), если, во-первых, не только сама /, нО и функция /-1, обратная ей, могут быть вычислены эффективно, а во-вторых, даже если такой эффек-
