Патенты. Алгоритм Pohlig-Hellman запатентован в США [722] и в Канаде

Алгоритм 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-й.

Табл. 19-5. Подписи EIGamal

Открытый ключ:

р простое число (может быть общим для группы пользователей)

g <p (может быть общим для группы пользователей)

у =g^x mod p

Закрытый ключ:
х <р

Подпись:
к выбирается случайным образом, взаимно простое с р- 1

а (подпись) =/ mod/;

Ъ (подпись), такое что М= (ха + kb) mod (p - 1)

Проверка: Подпись считается правильной, если у^аа^ъ mod/; = g^M mod p

Например, выберем/; = 11 и g = 2, а закрытый ключ х = 8. Вычислим

у = g^x mod/; = 2⁸ mod 11 = 3

Открытым ключом являются j = 3, g = 2H/>=ll. Чтобы подписать М = 5, сначала выберем случайное число к=9. Убеждаемся, что gcd(9, 10)= 1. Вычисляем

a = /mod/; = 2⁹ modll= 6

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

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

5 = (8*6 + 9*ft) modl0

Решение: Ъ = 3, а подпись представляет собой пару: а = 6 и й = 3.

Для проверки подписи убедимся, что

j/Vmod/^mod/;

3⁶6³ modll= 2⁵ modll

Вариант EIGamal, используемый для подписей, описан в [1377]. Томас Бет (Thomas Beth) изобрел вариант схемы EIGamal, подходящий для доказательства идентичности [146]. Существуют варианты для проверки под­линности пароля [312] и для обмена ключами [773]. И еще тысячи и тысячи других (см. раздел 20.4).