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

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

C = M2 mod n

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

m1 = C(+1)4 mod p

m2 = (p - C(+1)4) mod ,p

m3 = C(q+1)4 mod q

m4 = (q - C(q+1)4) mod q

Затем выбирается целые числа a = q(q-1 mod и b = ,p(p-1 mod q). Четырьмя возможными решениями являются:

M1 = (am1 + bm3) mod n M2 = (am1 + bm4) mod n M3 = (am2 + bm3) mod n M4 = (am2 + bm4) mod n

Один из четырех результатов, M1, M2, M3 и M4, равно M. Если сообщение написано по английски, выбрать правильное Mi нетрудно. С другой стороны, если сообщение является потоком случайных битов (скажем, для генерации ключей или цифровой подписи), способа определить, какое Mi - правильное, нет. Одним из способов решить эту проблему служит добавление к сообщению перед шифрованием известного заголовка .

Williams

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

p = 3 mod 8

q = 7 mod 8

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

k = 1/2 (1/4 (p - 1) (q - 1) + 1)

Для шифрования сообщения M вычисляется c1, такое что J(M,N) =(-1) c1 . Затем вычисляется M = (Sc1 *M) mod N. Как и в схеме Рабина, C = M2 mod N. И c2 = M mod 2. Окончательным шифротекстом сообщения является тройка:

(C, cl, c2)

Для дешифрирования C, получатель вычисляет M" с помощью Ck M" (mod N)

Правильный знак M" определяет c2. Наконец M= (Sc1 * (-1) c1 *M) mod N

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

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

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

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

[866, 889]. 19.6 ElGamal

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

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

y = gx mod p

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

Подписи ElGamal

Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно простое с p-1. Затем вычисляется

a = gk mod p

и с помощью расширенного алгоритма Эвклида находится b в следующем уравнении: M = (xa + kb) mod (p - 1)

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

yaab mod p = gM mod p

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

14-й.

Табл. 19-5.

Подписи ElGamal

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

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

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

y=gx mod ,p

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

Подпись:

k выбирается случайным образом, взаимно простое с p-1

a (подпись) =gk mod p

b (подпись), такое что M = (xa + kb) mod (p - 1)

Проверка:

Подпись считается правильной, если yaab mod p = gM mod p

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

y = gx mod p = 28 mod 11 = 3

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

a = gk mod p = 29 mod 11 = 6

и с помощью расширенного алгоритма Эвклида находим b: M = (xa + kb) mod (p - 1) 5 = (8*6 + 9*b) mod 10

Решение: b = 3, а подпись представляет собой пару: a = 6 и b = 3. Для проверки подписи убедимся, что yaab mod p = gM mod p 3663 mod 11 = 25 mod 11

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

Шифрование ElGamal

Модификация EIGamal позволяет шифровать сообщения. Для шифрования сообщения M сначала выбирается случайное число k, взаимно простое с p - 1. Затем вычисляются

a = gk mod p

b = yk M mod p

Пара (a,b) является шифротекстом. Обратите внимание, что шифротекст в два раза длиннее открытого те к-ста. Для дешифрирования (a,b) вычисляется

M = b/a* mod p

Так как a* = gkx (mod и b/a* = yk M/a* = gxk M/ gkx = M (mod то все работает (см. 13-й). По сути это то же самое, что и обмен ключами Диффи-Хеллмана (см. раздел 22.1) за исключением того, что y - это часть ключа, а при шифровании сообщение умножается на yk.

Табл. 19-6. Шифрование ElGamal

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

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

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

y=gx mod ,p

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

Шифрование:

k выбирается случайным образом, взаимно простое с p-1

a (шифротекст) =gk mod p

b (шифротекст)= yk M mod p

Дешифрирование: M (открытый текст) = b/a* mod p

Скорость

Некоторые примеры скорости работы программных реализаций EIGamal приведены в 12-й [918].

Табл. 19-7.