Вскрытие шифрования и подписи с использованием RSA

Имеет смысл подписывать сообщение перед шифрованием (см. раздел 2.7), но на практике никто не выполняет этого. Для RSA можно вскрыть протоколы, шифрующие сообщение до его подписания [48].

Àëèñà хочет послать сообщение Áîáу. Сначала она шифрует его открытым ключом Áîáа, а затем подписывает своим закрытым ключом. Ее зашифрованное и подписанное сообщение выглядит так:

Вот как Áîá может доказать, что Àëèñà послала ему m', а не m. Так как Áîáу известно разложение на множители n_B(это его собственный модуль), он может вычислить дискретные логарифмы по основанию n_B. Следовательно, ему нужно только найти x, для которого

m'^x = m mod n_B

Тогда, если он может опубликовать xe_Bв качестве своего нового открытого показателя степени и сохранить свой прежний модуль n_B, он сможет утверждать, что Àëèñà послала ему сообщение m', зашифрованное этим новым показателем.

В некоторых случаях это особенно неприятное вскрытие. Заметим, что хэш-функции не решают проблему. Однако она решается при использовании для каждого пользователя фиксированного показателя шифрования.

Стандарты

RSA de factoявляется стандартом почти по всему миру. ISO почти, but not quite, created an RSA digital-signature standard; RSA служит информационным дополнением ISO 9796 [762.]. Французское банковское сообщество приняло RSA в качестве стандарта [525], так же поступили и австралийцы [1498]. В Соединенных Штатах из-за давления NSA и патентных вопросов в настоящее время нет стандарта для шифрования с открытым ключом. Многие американские компании используют PKCS (см. раздел 24.14), написанный RSA Data Security, Inc. RSA определен и в качестве чернового банковского стандарта ANSI [61].

Патенты

Алгоритм RSA запатентован в Соединенных Штатах [1330], но ни водной другой стране. PKP получила лицензию вместе с другими патентами в области криптографии с открытыми ключами (раздел 25.5). Срок действия патента США истекает 20 сентября 2000 года.

Pohlig-Hellman

Схема шифрования Pohlig-Hellman [1253] похожа на RSA. Это не симметричный алгоритм, так как для шифрования и дешифрирования используются различные ключи. Это не схема с открытым ключом, потому что ключи легко получаются один из другого, и ключ шифрования, и ключ дешифрирования должны храниться в секрете. Как и в RSA,

C= P^emod n

P= C^dmod n

где

ed º 1 (mod какое-нибудь составное число)

В отличие от RSA nне определяется с помощью двух простых чисел и остается частью закрытого ключа. Если у кого-нибудь есть eи n, он может вычислить d. Íå çíàÿ eили d, противник будет вынужден вычислить

e = log_pC mod n

Мы уже видели, что это является трудной проблемой.

Патенты

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

Rabin

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

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

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

C= M²mod n

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

m₁ = C^(p+1)/4 mod p

m₂= (p- C^(p+1)/4) mod p

m₃ = C^(q+1)/4 mod q

m₄= (q- C^(q+1)/4) mod q

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

M₁= (am ₁+ bm₃) mod n

M₂= (am ₁+ bm₄) mod n

M₃= (am ₂+ bm₃) mod n

M₄= (am ₂+ bm₄) mod n

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

Williams

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

pº 3 mod 8

q º 7 mod 8

и

N= pq

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

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

Для шифрования сообщения M вычисляется c₁, такое что J(M,N) = . Затем вычисляется M'= ( * M) mod N.Как и в схеме Рабина, C= M'²mod N. И c₂ = M'mod 2. Окончательным шифротекстом сообщения является тройка:

(C, c_l, c₂)

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

C^kº± M"(mod N)

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

M = ( * *M")mod N

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

Преимущество схем Рабина и Вильямса перед RSA в том, что доказано, что они также безопасны, как и разложение на множители. Однако перед вскрытием с выбранным шифротекстом они совершенно беззащитны. Если вы собираетесь использовать эти схемы для случаев, когда взломщик может выполнить такое вскрытие (íàïðèìåð, алгоритм цифровой подписи, когда взломщик может выбирать подписываемые сообщения), не забывайте использовать перед подписанием однонаправленную хэш-функцию. Рабин предложил другой способ защититься от такого вскрытия: к каждому сообщению перед хэшированием и подписанием добавляется уникальная случайная строка. К несчастью, после добавления однонаправленной хэш-функцией тот факт, что система столь же безопасна, как и разложение на множители, больше не является доказанным [628]. Хотя с практической точки зрения добавление хэширования не может ослабить систему.

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

ElGamal

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

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

y= g^xmod p

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

Подписи ElGamal

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

a= g^kmod p

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

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

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

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

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

Табл. 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)

Проверка:

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

Íàïðèìåð, выберем p= 11 и g= 2, а закрытый ключ x= 8. Вычислим

y= g^x mod p= 2⁸ mod 11 = 3

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

a= g^kmod p= 2⁹ mod 11 = 6

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

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

5 = (8*6 + 9*b) mod 10

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

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

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

3⁶6³ mod 11 = 2⁵mod 11

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