Глава 13

Криптографические системы на основе дискретного

логарифмирования

Литература

1. Н. Коблиц, Курс теории чисел и криптографии, Москва, ТВП, 2001 г., 154 с.

2. В.Н. Крупский, Введение в сложность вычислений, М.: Факториал Пресс, 2006 г., 128 с.

3. Введение в криптографию / под общей ред. В.В. Ященко, -СПб, Питер, 2001 г., 288 с.

13.1. Дискретный логарифм

В поле вещественных чисел возведение в степень (нахождение bx с заданной точностью) не намного проще обратной

операции (нахождения logb x с заданной точностью).

Рассмотрим теперь конечную группу, например (Z/nZ)∗ или Fq (с умножением в качестве групповой операции).

Метод повторного возведения в квадрат позволяет вычислить b при больших x сравнительно быстро (за полиноми-

альное по log x время).

Определение. Пусть G – конечная группа, b – элемент группы G и y – элемент группы G, являющийся степенью b.

Любое целое число x, для которого bx = y, называется дискретным логарифмом y по основанию b.

13.2. Система Диффи-Хеллмана обмена ключами

Так как криптосистемы с открытым ключом значительно медленнее классических криптосистем (по крайней мере,

при нынешнем состоянии науки и техники), то разумнее использовать их в качестве дополнения к классическим

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

криптосистемы можно очень эффективно реализовать с помощью системы с открытым ключом.

Предположение Диффи-Хеллмана. Сложность вычисления gab по ga и gb чрезвычайно велика.

Предположение Диффи-Хеллмана априори не слабее предположения о чрезвычайной сложности дискретного ло-

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

ложение Диффи-Хеллмана было бы неверным.

13.3. Согласование случайного элемента из группы

Пусть значение q общеизвестно, т.е. все знают, из какого конечного поля выбирается ключ. Пусть, далее, g –

некоторый фиксированный элемент Fq , который также не является секретным. В идеале, g должен быть порождающим

элементом группы Fq .

Если же мы хотим, чтобы случайный элемент мог принимать любые значения из Fq , то g должен быть порожда-

ющим элементом.

Пусть есть два пользователя, Аида и Бернардо. Аида выбирает случайное число a между 1 и q − 1, которое она

держит в секрете, и вычисляет ga ∈ Fq , которое объявляет открыто. Бернардо делает то же самое: он случайно

выбирает b и объявляет gb. В качестве секретного ключа используется gab. Оба пользователя могут вычислить этот

ключ.

13.4. Криптосистема Мэсси-Омуры

Предположим, что все согласились использовать конечное поле Fq ; оно зафиксировано и общеизвестно. Каждый

пользователь системы втайне выбирает такое случайное целое e между 0 и q − 1, что НОД(e, q − 1) = 1, и с помощью

алгоритма Евклида вычисляет обратное к нему число d ≡ e−1 (mod q − 1), т.е. de ≡ 1 (mod q − 1).

Алиса (пользователь A) намерена передать сообщение P Бобу, она сначала посылает ему элемент P eA . Это послание

для Боба бессодержательно, так как он не знает dA (или eA, что то же самое) и не может восстановить P . Не пытаясь

понять смысл сообщения, Боб возводит его в свою степень eB и отсылает P eAeB обратно Алисе. Третий шаг состоит

в том, что Алиса несколько распутывает сообщение, возводя его в степень dA; так как P dAeA = P , то, по сути дела,

она отсылает Бобу P eB , который теперь может прочитать сообщение, возведя его в степень dB .

∗

x

∗

∗

13.5. Криптосистема Эль-Гамаля

13.5. Криптосистема Эль-Гамаля

Сначала зафиксируем очень большое конечно поле Fq и элемент g ∈ Fq (желательно, хотя и не обязательно, чтобы

он был порождающим). Предположим, что используются элементы открытого текста с численными эквивалентами

P в Fq . Каждый пользователь A выбирает случайно целое число a = aA, скажем, из диапазона 0 < a < q − 1. Это

секретный ключ дешифрования. Открытым ключом шифрования является элемент ga ∈ Fq .

Чтобы передать сообщение P пользователю A, мы выбираем случайно целое число k и посылаем A следующую

пару элементов из Fq :

(gk , P gak ).

Заметим, что вычислить gak можно, не зная a, просто возведя ga в степень k. Теперь A, зная a, может по этой

паре раскрыть P , возведя первый элемент gk в степень a-ю степень и разделив на результат второй элемент (или, что

эквивалентно, возведя gk в степень q − 1 − a и умножив на второй элемент).

13.6. Цифровая подпись на основе Эль-Гамаля

1. выбирается простое число q приблизительно в 160 бит (для этого используется генератор случайных чисел и

тест на простоту)

2. выбирается другое простое число p, сравнимое с 1 по модулю q размером приблизительно в 512 бит

3. выбирается порождающий элемент g единственной циклической подгруппы в Fp порядка q (т.е. вычисляется

(p−1)/q

g ≡ g0

(mod p) для случайного целого g0; если g = 1, то он и будет порождающим элементом)

4. выбирается секретный ключ как случайное целое число x из диапазона 0 < x < q. В качестве открытого ключа

берётся y = gx (mod p).

13.7. Вычисление и проверка подписи

Пусть Алиса хочет подписать сообщение. Сначала она применяет к своему открытому тексту хеш-функцию и

получает целое число h из диапазона 0 < h < q. Затем она выбирает случайное целое k из того же диапазона и

вычисляет gk (mod p). Пусть r – наименьший неотрицательный вычет по модулю q последнего выражения (значит, gk

сначала вычисляется по модулю p, а результат приводится по меньшему простому модулю q). Наконец, Алиса находит

такое целое s, что sk ≡ h + xr (mod q). Пара (r, s) вычетов по модулю q является её подписью.

Чтобы проверить подпись, получатель Боб вычисляет u1 ≡ s−1h (mod q) и u2 ≡ s−1r (mod q). Потом он вычисляет

g y (mod p). Если результат сравним с r по модулю q, то подпись считается подлинной. (Заметим, что gu1 yu2 ≡

−1

gs (h+xr) ≡ gk (mod p).)

51

∗

∗

u1 u2