11.6 Дискретные логарифмы в конечном поле

В качестве другой однонаправленной функции в криптографии часто используется возведение в степень по модулю. Легко вычислить:

ax mod n

Задачей, обратной возведению в степень по модулю, является поиск дискретного логарифма. А это уже н е-легкая задача:

Найти x, для которого ax = b (mod n).

Например:

Если 3x = 15 mod 17, то x = 6

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

3x =7 (mod 13)

Еще сложнее решать эту задачу для 1024-битовых чисел.

Вычисление дискретных логарифмов в конечной группе

Криптографы интересуются дискретными логарифмами следующих трех групп:

- Мультипликативная группа полей простых чисел: GF(

- Мультипликативная группа конечных полей степеней 2: GF(2n)

- Группы эллиптической кривой над конечными полями F: EC(F)

Безопасность многих алгоритмов с открытыми ключами основана на задаче поиска дискретных логарифмов, поэтому эта задача была глубоко изучена. Хороший подробный обзор этой проблемы и ее наилучшие решения на соответствующий момент времени можно найти в [1189, 1039]. Лучшей современной статьей на эту тему является [934].

Если p является простым числом и используется в качестве модуля, то сложность поиска дискретных лог а-рифмов в GF(p) по существу соответствует разложению на множители числа n того же размера, где n - это произведение двух простых чисел приблизительно равной длины [1378,934]. То есть:

e (1+O (1))(ln( n )).12(ln((ln(n)))12

Решето числового поля быстрее, оценка его эвристического времени выполнения:

e(1.923+O (1))(ln( n))13(ln((ln(n )))23

Стивен Полиг (Stephen Pohlig) и Мартин Хеллман нашли способ быстрого вычисления дискретных лог а-рифмов в GF() при условии, что p - 1 раскладывается на малые простые множители [1253]. По этой причине в криптографии используются только такие поля, для которых p - 1 обладает хотя бы одним большим простым множителем. Другой алгоритм [14] вычисляет дискретных логарифм со скоростью, сравнимой с разложением на множители, он был расширен на поля вида GF( pn) [716]. Этот алгоритм был подвергнут критике в [727] по ряду теоретических моментов. В других статьях [1588] можно увидеть, насколько на самом деле трудна пр о-блема в целом.

Вычисление дискретных логарифмов тесно связано с разложением на множители. Если вы можете решить проблему дискретного логарифма, то вы можете и разложить на множители. (Истинность обратного никогда не была доказана.) В настоящее время существует три метода вычисления дискретных логарифмов в поле простого числа [370, 934, 648]: линейное решето, схема целых чисел Гаусса и решето числового поля.

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

В мире расширенных полей исследователями не игнорируются и GF(2 n). Алгоритм был предложен в [727]. Алгоритм Копперсмита (Coppersmith) позволяет за приемлемое время находить дискретные логарифмы в таких полях как GF(2127) и делает принципиально возможным их поиск в полях порядка GF(2 400) [368]. В его основе лежит [180]. У этого алгоритма очень велика стадия предварительных вычислений, но во всем остальном он хорош и эффективен. Реализация менее эффективной версии этого же алгоритма после семи часов предвар и-тельных вычислений тратила на нахождение каждого дискретного логарифма в поле GF(2 127) лишь несколько

секунд [1130, 180]. (Это конкретное поле, когда-то использовавшееся в некоторых криптосистемах [142, 1631, 1632], не является безопасным.) 0бзор некоторых из этих результатов можно найти в [1189, 1039].

Позднее были выполнены предварительные вычисления для полей GF(2 227), GF(2313) и GF(2401), удалось значительно продвинуться и для поля GF(2 503). Эти вычисления проводились на nCube-2, массивном параллельном компьютере с 1024 процессорами [649, 650]. Вычисление дискретных логарифмов в поле GF(2 593) все еще находится за пределами возможного.

Как и для нахождения дискретных логарифмов в поле простого числа, для вычисления дискретных лог а-рифмов в полиномиальном поле также требуется один раз выполнить предварительные вычисления. Тахер Эль-Джамаль (Taher EIGamal) [520] приводит алгоритм вычисления дискретных логарифмов в поле GF( /72).

Глава 12 Стандарт шифрования данных DES (Data Encryption Standard)

12.1 Введение

Стандарт шифрования данных DES (Data Encryption Standard), который ANSI называет Алгоритмом ши ф-рования данных DEA (Data Encryption Algorithm), а ISO - DEA-1, за 20 лет стал мировым стандартом. Хотя на нем и появился налет старости, он весьма прилично выдержал годы криптоанализа и все еще остается безопа с-ным по отношению ко всем врагам, кроме, возможно, самых могущественных.

Разработка стандарта

В начале 70-х годов невоенные криптографические исследования были крайне редки. В этой области почти не публиковалось исследовательских работ. Большинство людей знали, что для своих коммуникаций военные используют специальную аппаратуру кодирования, но мало кто разбирался в криптографии как в науке. Заме т-ными знаниями обладало Агентство национальной безопасности (National Security Agency, NSA), но оно даже не признавало публично своего собственного существования.

Покупатели не знали, что они покупают. Многие небольшие компании изготавливали и продавали крипт о-графическое оборудование, преимущественно заокеанским правительствам. Все это оборудование отличалось друг от друга и не могло взаимодействовать. Никто не знал, действительно ли какое-либо из этих устройств безопасно, не существовало независимой организации, которая засвидетельствовала бы безопасность. Как гов о-рилось в одном из правительственных докладов [441]:

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

В 1972 году Национальное бюро стандартов (National Bureau of Standards, NBS), теперь называющееся Н а-циональным институтом стандартов и техники (National Institute of Standards and Technology, NIST), выступило инициатором программы защиты линий связи и компьютерных данных. Одной из целей этой программы была разработка единого, стандартного криптографического алгоритма. Этот алгоритм мог бы быть проверен и се р-тифицирован, а использующие его различные криптографические устройства могли бы взаимодействовать. Он мог бы, к тому же, быть относительно недорогим и легко доступным.

15 мая 1973 года в Federal Register NBS опубликовало требования к криптографическому алгоритму, который мог бы быть принят в качестве стандарта. Было пр иведено несколько критериев оценки проекта:

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

- Алгоритм должен быть полностью определен и легко понятен.

- Безопасность алгоритма должна основываться на ключе и не должна зависеть от сохранения в тайне с а-мого алгоритма.

- Алгоритм должен быть доступен всем пользователям.

- Алгоритм должен позволять адаптацию к различным применениям.

- Алгоритм должен позволять экономичную реализацию в виде электронных приборов.

- Алгоритм должен быть эффективным в использовании.

- Алгоритм должен предоставлять возможности проверки.

- Алгоритм должен быть разрешен для экспорта.

Реакция общественности показала, что к криптографическому стандарту существует заметный интерес, но опыт в этой области чрезвычайно мал. Ни одно из предложений не удовлетворяло предъявленным требованиям.

27 августа 1972 года в Federal Register NBS опубликовало повторное предложение. Наконец, у Бюро появи л-ся подходящий кандидат: алгоритм под именем Люцифер, в основе которого лежала разработка компании IBM, выполненная в начале 70-х (см. раздел 13.1). В IBM существовала целая команда криптографов, работавшая в Кингстоне (Kingston) и Йорктаун Хайтс (Yorktown Heights), в которую входили Рой Адлер (Roy Adler), Дон Копперсмит (Don Coppersmith), Хорст Фейстель (Horst Feistel), Эдна Кроссман (Edna Crossman), Алан Конхейм (Alan Konheim), Карл Майер (Carl Meyer), Билл Ноц (Bill Notz), Линн Смит (Lynn Smith), Уолт Тачмен (Walt Tuchman) и Брайант Такерман (Bryant Tuckerman).

Несмотря на определенную сложность алгоритм был прямолинеен. Он использовал только простые логич е-