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

Развитие криптографии в XX веке было стремительным, но неравномерным. Анализ истории ее развития как специфической области человеческой деятельности выделяет три основных периода.

1. Начальный, имевший дело лишь с ручными шифрами, начавшийся в седой древности, закончился лишь в конце тридцатых годов XX века. Криптография за это время прошла длинный путь от магического искусства древних жрецов до будничной прикладной профессии чиновников секретных ведомств.

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

3. Началом третьего периода развития криптологии обычно считают 1976 год, когда американские математики Диффи и Хеллман предложили принципиально новый вид организации засекреченной связи без предварительного снабжения абонентов секретными ключами, так называемое шифрование с открытым ключом. В результате стали появляться криптографические системы, основанные на подходе, сформулированном еще в сороковых годах Шенноном. Он предложил строить шифр таким способом, чтобы его раскрытие было эквивалентно решению математической задачи, требующей выполнения объемов вычислений, превосходящих возможности современных ЭВМ. Новый период развития криптографии характеризуется появлением полностью автоматизированных систем шифрованной связи, в которых каждый пользователь имеет свой индивидуальный пароль для подтверждения подлинности, хранит его, к примеру на магнитной карте, и предъявляет при входе в систему, а весь остальной процесс проведения секретной связи происходит автоматически.

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

При шифровании с открытым ключом для шифрования и расшифровывания используются разные ключи, и знание одного из них не дает практической возможности определить второй. Поэтому ключ для шифрования может быть сделан общедоступным без потери стойкости шифра, если ключ для расшифровывания сохраняется в секрете, например, генерируется и хранится только получателем информации. Несмотря на подозрительность (кому верят криптоаналитики?) и консерватизм (лучшее – для криптографов – враг хорошего!) новые идеи стали быстро реализовываться на практике. Шифруют и сейчас традиционными методами, но рассылка ключей и цифровая подпись стали выполняться уже по-новому. Сейчас два метода шифрования с открытым ключом получили признание и закреплены в стандартах. Национальный институт стандартов и технологий США NIST (бывший ANSI) принял стандарт MD 20899, основанный на алгоритме ЭльГамаля, а на основе алгоритма RSA приняты стандарты ISO/IEC/DIS 9594-8 международной организацией по стандартизации и Х.509 международным комитетом по связи.

Криптографические системы с открытым ключом используют так называемые необратимые или однонаправленные (односторонние) функции. Понятия однонаправленной функции и однонаправленной функции с “потайным ходом” являются центральными понятиями всей криптографии с открытым ключом.

Рассмотрим два произвольных множества X и Y . Функция f: X ® Y называется однонаправленной, если f(x) может быть легко вычислена для каждого xÎX, тогда как почти для всех yÎY вычисление такого xÎX, что f(x) = y (при условии, что хотя бы один такой x существует), является сложным. Это понятие не нужно путать с функциями, которые являются математически необратимыми из-за того, что они не взаимнооднозначны (т. е. из-за того, что существует несколько различных x, таких что f(x) = y, или их нет вовсе). Наше нынешнее состояние знаний не позволяет нам доказать, что однонаправленные функции вообще существуют. Однако, несмотря ни на что, у нас имеются кандидаты в этом смысле среди функций, как эффективно вычислить которые мы знаем, тогда как никаких эффективных алгоритмов их обращения (во всяком случае среди общедоступных) неизвестно.

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

Конечно, необходимо понимать, что “не в состоянии” означает не в состоянии за приемлемое время (такое, как время человеческой жизни или возраст вселенной).

Другим важным примером кандидата на однонаправленную функцию является модульное возведение в степень или модульное экспонирование (с фиксированными основанием и модулем). Пусть n и a – целые числа, такие что 1 < a < n. Тогда модульное возведение в степень (относительно основания a и модуля n это функция, определяемая как f(x) = a^x mod n, где i mod j обозначает положительный остаток при делении i на j. Сразу не очевидно, что такую функцию можно вычислить эффективно, когда длина каждого из трех параметров a, n и x составляет несколько сотен знаков. То, что это возможно мы увидим несколько позже.

Обратная операция известна как задача дискретного логарифмирования: даны целые числа a, n и y, требуется найти такое целое x (если оно существует), что a^x mod n = y. Например, 5⁴ mod 21 = 16. Следовательно, 4 это дискретный логарифм 16 с основанием 5 по модулю 21 (если y = a^x, то x = log_a y). При желании можно проверить, что, например, число 3 вообще не имеет логарифма с основанием 5 по модулю 21. Несмотря на то, что вычисление больших модульных экспонент может быть осуществлено эффективно, в настоящее время неизвестно ни одного алгоритма для вычисления дискретных логарифмов больших чисел за приемлемое время даже на самых быстродействующих компьютерах, т.е. функция дискретного возведения в степень является однонаправленной. Однако строгого доказательства этого факта для данной функции (равно как и для других) пока что не найдено. При этом, хотя мы и не можем доказать, что таких алгоритмов вообще не существует, имеется предположение, что модульное возведение в степень (с фиксированным основанием и модулем) действительно является однонаправленной функцией.

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

Более употребимым в криптографии является понятие однонаправленной функции с потайным ходом. Такими названы односторонние функции f_z с параметром z, обладающие свойством: при данном z можно найти алгоритмы E_z и D_z, позволяющие легко вычислить соответственно f_z(x) для всех x из области определения, и для всех y из области значений; однако практически для всех z и практически для всех y из области значений f_z нахождение вычислительно неосуществимо даже при известном E_z.

Вообще же все предлагаемые сегодня криптосистемы с открытым ключом опираются на один из следующих типов необратимых преобразований:

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

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

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