Современная прикладная криптография (стр. 14 )

В качестве возможной односторонней функции Гилл Дж. [Gill] предложил показательную функцию f(x) = modn, где а (основание) принадлежит интервалу (l, n-1), а умножение ведется по модулю числа n. Значение modn вычисляется достаточно эффективно, даже при больших числах х из (l. n) за операций, с помощью схемы Горнера "слева-направо" или "справа-налево").

Если двоичное разложение числа х имеет вид, то

(вариант "слева-направо")/(вариант "справа-налево")

Операция, обратная к этой операции, известна как операция вычисления дискретного логарифма: по данным а и у найти такое целое т. что modn = у. До настоящего времени не найдено достаточно эффективных алгоритмов решения этой задачи. Более подробно об этом сказано в [32,34,35].

С помощью показательной функции Диффи и Хеллман разработали так называемую схему открытого распределения ключей [4]. В этой же работе Диффи и Хеллман предложили для построения однонаправленных функций использовать классические криптосистемы с одним ключом, стойкие к методам вскрытия по известному открытому и шифрованному текстам (known plaintext attack). Если зафиксировать какой-нибудь открытый текст и рассмотреть отображение пространства ключей в пространство шифртекстов, определяемое в виде f(x) = = с, то нахождение по f(x) эквивалентно задаче нахождения ключа по известному открытому и соответствующему шифрованному текстам.

Для шифрования информации однонаправленная функция не применима, так как никто, даже законный адресат, не сможет расшифровать шифртекст C = f(M), полученный с ее помощью. В [85] найдено хорошее сравнение преобразования однонаправленоой функции с разбиением тарелки: восстановить рисунок по мелким кусочкам разбитой тарелки достаточно трудная задача. Однако именно эти свойства однонаправленных функций, как уже было сказано, нашли применение в парольной аутентификации пользователей ЭВМ.

Понятие однонаправленной функции оказалось также связанным с понятием широко используемых в криптографии генераторов псевдослучайных последовательностей [21], а также с понятием так называемой функции хэширования информации [164]. Кроме того, это понятие послужило толчком к определению однонаправленной функции с секретом (trap-door one-way function)

2.3 Открытое распределение ключей. Схема Диффи-Хеллмана

Одной из проблем криптографии, решенной в работе Диффи и Хеллмана [4], стала проблема распределения (рассылки) ключей для секретной связи. Использование криптосистем с секретным ключом предполагает заблаговременные до сеансов связи договоренности между абонентами о сеансовых секретных ключах или их предварительную пересылку по защищенному каналу связи. Разработанные в [4] принципы так называемого открытого распределения ключей (ОРК) и открытого шифрования (ОШ) и явились "новыми направлениями в криптографии", давшими начало криптографии с открытым ключом. Несмотря на то, что идеи ОРК и ОШ были сформулированы одновременно, удалось сразу предложить конкретную реализацию только для схемы ОРК, на основе показательной односторонней функции. Эта схема получила название экспоненциального ключевого обмена Диффи - Хеллмана.

Рассмотрим схему в ее оригинальном изложении. В протоколе обмена секретными ключами предполагается, что все пользователи знают некоторое большое простое число р и примитивный элемент (1<<p) конечного поля GF(р) (то есть элемент, степени которого аt дают все ненулевые элементы поля {l,2,...,p-1}). Такие элементы всегда существуют, их число равно , где - функция Эйлера [66]. Для выработки общей секретной информации k пользователи A и B должны сделать следующее.

1. Пользователи а и в независимо выбирают случайные числа и из интервала {l,...,p-1}, называемые секретными ключами пользователей.

2. Вычисляют с использованием известных р и величины

и ,

которые являются открытыми ключами пользователей.

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

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

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

Безопасность (секретность) изложенной схемы зависит от (не превышает) сложности вычисления дискретных логарифмов в мультипликативной группе конечного поля GF(p). Пока не найдено удовлетворительных быстрых алгоритмов нахождения К из ,, без вычисления из , и из ,.

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

-мультипликативная группа конечного поля: GF(p)*, р - простое число > 2 ;

-мультипликативная группа конечного поля характеристики 2: GF;

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

Некоторые последние результаты по проблеме дискретного логарифмирования

Общие методы для произвольной группы:

Метод Шенкса (Daniel Shanks) или ”baby steps, giant steps”.

Pollard ro-method.(рандомизированный алгоритм)

- метод Полларда.

Аддитивная группа кольца вычетов целых чисел (Z, +) по модулю m.

Найти x из a х=b (mod m). Очень просто решается.

Мультипликативная группа целых чисел по модулю простого числа p.

Метод Шенкса (baby steps, giant steps)).

Pollard ro-method.(рандомизированный алгоритм).

Сложность методов решения DLP – О(), где q наибольший простой делитель числа

(p-1), хотя метод Полларда почти не использует память.

1993. Van Oorschot – Wiener предложили способ распараллеливания метода Полларда на t процессоров. Это дало сложность в t раз меньшую.

Обычно число q выбирают сравнимым с числом p, например берут p=2q+1.

Использование дополнительных свойств группы.

Методы исчисления индексов (Index calculus methods)

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

Субэкспоненциальная сложность. L[1/2, c], где с – некоторая константа с > 0.

Метод линейного решета (Lenear sieve method) и Gaussian integer method достигли с=1.

L[t, c] = exp((с+0(1))((lnp)(lnlnp))