Патенты

Алгоритм Pohlig-Hellman запатентован в США [722] и в Канаде. РКР получила лицензию вместе с другими патентами в области криптографии с открытыми ключами (см. раздел 25.5).

19.5 Rabin

Безопасность схемы Рабина (Rabin) [1283, 1601] опирается на сложность поиска квадратных корней по мо­дулю составного числа. Эта проблема аналогична разложению на множители . Вот одна из реализаций этой схе­мы.

Сначала выбираются два простых числа р и q, конгруэнтных 3 mod 4. Эти простые числа являются закры­тым ключом, а их произведение п =pq - открытым ключом.

Для шифрования сообщения М (М должно быть меньше и), просто вычисляется

С = М² mod n

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

т^&^тойр

т₂ = (р-&⁺^)то&р

m₃ = C*^+1)/4 mod<7

m₄ = (<7- C*^+1)/4) mod<7

Затем выбирается целые числа а = q{q^l mod/;) и Ъ = р(р^л mod q). Четырьмя возможными решениями явля-ются:

Mi = (атг + bm₃) mod и

М₂ = (атпг + 6от₄) mod и

М_ъ = (д/я₂ + йот₃) mod и

М₄ = (д/я₂ + Ъпи) mod и

Один из четырех результатов, М_ь М₂, М₃ и М₄, равно М. Если сообщение написано по английски, выбрать правильное М, нетрудно. С другой стороны, если сообщение является потоком случайных битов (скажем, для генерации ключей или цифровой подписи), способа определить, какое М, - правильное, нет. Одним из способов решить эту проблему служит добавление к сообщению перед шифрованием известного заголовка .

Williams

Хью Вильяме (Hugh Williams) переопределил схему Рабина, чтобы устранить эти недостатки [1601]. В его схеме/; и q выбираются так, чтобы

р = 3 mod 8

q = 7 mod 8

и

N = pq

Кроме того, используется небольшое целое число, S, для которого J(S,N) = -1. (J - это символ Якоби - см. раздел 11.3). NhS опубликовываются. Секретным ключом является к, для которого

к = 1/2 (1/4 (р- ) (q - 1) + 1)

Для шифрования сообщения М вычисляется с_ь такое что J(M,N) =(-l)^Cl • Затем вычисляется М' — (S^c' *M) mod N. Как и в схеме Рабина, С = М'² mod N. И с₂ = М' mod 2. Окончательным шифротекстом сообщения явля­ется тройка:

(С, с_и с₂)

Для дешифрирования С, получатель вычисляет М" с помощью

С^к=±М" (mod ЛО

Правильный знак М" определяет с₂. Наконец

M= (S^C' *(-iy*M") mod N

Впоследствии Вильяме улучшил эту схему в [1603, 1604, 1605]. Вместо возведения в квадрат открытого тек­ста сообщения, возведите его в третью степени. Большие простые числа должны быть конгруэнтны 1 по модулю 3, иначе открытый и закрытый ключи окажутся одинаковыми . Даже лучше, существует только одна уникальная расшифровка каждого шифрования.

Преимущество схем Рабина и Вильямса перед RSA в том, что доказано, что они также безопасны, как и раз­ложение на множители. Однако перед вскрытием с выбранным шифротекстом они совершенно беззащитны . Если вы собираетесь использовать эти схемы для случаев, когда взломщик может выполнить такое вскрытие (например, алгоритм цифровой подписи, когда взломщик может выбирать подписываемые сообщения ), не за-

бывайте использовать перед подписанием однонаправленную хэш-функцию . Рабин предложил другой способ защититься от такого вскрытия: к каждому сообщению перед хэшированием и подписанием добавляется уни­кальная случайная строка. К несчастью, после добавления однонаправленной хэш-функцией тот факт, что си с-тема столь же безопасна, как и разложение на множители, больше не является доказанным [628]. Хотя с прак­тической точки зрения добавление хэширования не может ослабить систему.

Другими вариантами схемы Рабина являются [972, 909, 696, 697, 1439, 989]. Двумерный вариант описан в [866, 889].

19.6 EIGamal

Схему EIGamal [518,519] можно использовать как для цифровых подписей, так и для шифрования, его без о-пасность основана на трудности вычисления дискретных логарифмов в конечном поле .

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

y = g^x mo&p

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

Подписи EIGamal

Чтобы подписать сообщение М, сначала выбирается случайное число к, взаимно простое ср-. Затем вычис­ляется

a = g^k mo&p

и с помощью расширенного алгоритма Эвклида находится Ъ в следующем уравнении:

М= (xa + kb) mod (p - 1)

Подписью является пара чисел: а и Ъ. Случайное значение к должно храниться в секрете. Для проверки под­писи нужно убедиться, что

y^aa»mod p = g^M mod p

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