сразу же обнаружено - шифрование и дешифрирование не будут работать . Существует ряд чисел, называемых числами Кармайкла (Carmichael), которые не могут обнаружить определенные вероятностные алгоритмы пои ска простых чисел. Они небезопасны, но чрезвычайно редки [746]. Честно говоря, меня бы это не обеспокоило.

Вскрытие с выбранным шифротекстом против RSA

Некоторые вскрытия работают против реализаций RSA. Они вскрывают не сам базовый алгоритм, а надстроенный над ним протокол. Важно понимать, что само по себе использование RSA не обеспечивает безопасности. Дело в реализации.

Сценарий 1: Еве, подслушавшей линии связи Алисы, удалось перехватить сообщение с, шифрованное с помощью RSA открытым ключом Алисы. Ева хочет прочитать сообщение. На языке математики, ей нужно от, для которого

Для раскрытия от она сначала выбирает первое случайное число r, меньшее n. Она достает открытый ключ Алисы e. Затем она вычисляет

x = re mod n

у = xc mod n

t = r-1 mod n

Если x = re mod n, то r = xd mod n.

Теперь просит Алису подписать y ее закрытым ключом, таким образом расшифровав у. (Алиса должна подписать сообщение, а не его хэш сумму.) Не забывайте, Алиса никогда раньше не видела у. Алиса посылает Еве

u = yd mod n

Теперь Ева вычисляет

tu mod n = r-1 yd mod = r-1 xdcd mod n = cd mod n = т И Ева получает т.

Сценарий 2: Трент - это компьютер-нотариус. Если Алиса хочет заверить документ, она посылает его Тренту. Трент подписывает его цифровой подписью RSA и отправляет обратно. (Однонаправленные хэш-функции не используются, Трент шифрует все сообщение своим закрытым ключом .)

Мэллори хочет, чтобы Трент подписал такое сообщение, которое в обычном случае он он никогда не подп и-шет. Может быть это фальшивая временная метка, может быть автором этого сообщения является другое лицо . Какой бы ни была причина, Трент никогда не подпишет это сообщение, если у него будет возможность выбора . Назовем это сообщение от.

Сначала Мэллори выбирает произвольное значение x и вычисляет у = xe mod n. e он может получить без труда - это открытый ключ Трента, который должен быть опубликован, чтобы можно было проверять подписи Трента. Теперь Мэллори вычисляет от = уот mod n и посылает от Тренту на подпись. Трент возвращает md mod n. Now Мэллори вычисляет (md mod n)x-1 mod n, которое равно nd mod n и является подписью m.

На самом деле Мэллори может использовать множество способов решить подобную задачу [423, 458, 486]. Слабым местом, которое используют такие вскрытия, является сохранение мультипликативной структуры входа при возведении в степень. То есть:

(xm)d mod n = x dmd mod n

Сценарий 3: Ева хочет, чтобы Алиса подписала от3. Она создает два сообщения, ml и от2, такие что т3 = т1 т2 (mod n)

Если Ева сможет заставить Алису подписать ml и от2, она может вычислить подпись для от3: m3d = (mld mod n) (m2d mod n)

Мораль: Никогда не пользуйтесь алгоритмом RSA для подписи случайных документов, подсунутых вам п о-сторонними. Всегда сначала воспользуйтесь однонаправленной хэш-фунцией . Формат блоков ISO 9796 предотвращает это вскрытие.

Вскрытие общего модуля RSA

При реализации RSA можно попробовать раздать всем пользователям одинаковый модуль n, но каждому свои значения показателей степени e и d. К сожалению, это не работает. Наиболее очевидная проблема в том,

что если одно и то же сообщение когда-нибудь шифровалось разными показателями степени (с одним и тем же модулем), и эти два показателя - взаимно простые числа (как обычно и бывает), то открытый текст может быть раскрыт, даже не зная ни одного ключа д ешифрирования [1457].

Пусть m - открытый текст сообщения. Два ключа шифрования - e1 и e2. Общий модуль - n. Шифротекстами сообщения являются:

c1 = me1 mod n c2 = me2 mod n

Криптоаналитик знает n, e1, e2, c1 и c2. Вот как он узнает m.

Так как e1 и e2 - взаимно простые числа, то с помощью расширенного алгоритма Эвклида r и s, для которых

re1 + se2 = 1

Считая r отрицательным (или r, или s должно быть отрицательным, пусть отрицательным будет r), то снова можно воспользоваться расширенным алгоритмом для вычисления c1-1. Затем

(c1-1)-r * c2s = m mod n

Существует два других, более тонких вскрытия систем такого типа . Одно использует вероятностный метод для разложения n на множители. Другой - детерминированный алгоритм вычисления какого-нибудь секретного ключа без разложения модуля на множители . Оба вскрытия подробно описаны в [449].

Мораль: Не делайте n общим для группы пользователей .

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

Шифрование и проверка подписи RSA выполняется быстрее, если для e используется небольшое значение, но это также может быть небезопасным [704]. Если e(e + 1)/2 линейно зависящих сообщений с различными открытыми ключами шифруются одним и тем же значением e, существует способ вскрыть такую систему. Если сообщений не так много, или если сообщения не связаны, то проблем нет. Если сообщения одинаковы, то достаточно e сообщений. Проще всего дополнять сообщения независимыми случайными числами .

Это также гарантирует, что me mod n ф me. Так делается в большинстве практических реализаций RSA, например, в PEM и PGP (см. разделы 24.10 и 24.12).

Мораль: Дополняйте сообщения перед шифрованием случайными значениями, убедитесь, что размер m примерно равен n.

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

Другим вскрытием, предложенным Майкл Винер (Michael Wiener), раскрывает d, где d не превышает четверти размера n, а e меньше n [1596]. При случайном выборе e и d это встречается редко, и никогда не произойдет, если значение e мало.

Мораль: Выбирайте большое значение d. Полученные уроки

Джудит Мур (Judith Moore) на основании перечисленных вскрытий приводит следующие ограничения RSA [1114, 1115]:

-Знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику разложить модуль на множители .

-Знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику вычислить другие пары показателей, не раскладывая модуль на множители.

-В протоколах сетей связи, применяющих RSA, не должен использоваться общий модуль. (Это является быть очевидным следствием предыдущих двух пунктов .)

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

-Показатель дешифрирования должен быть большим .

Не забывайте, недостаточно использовать безопасный криптографический алгоритм, должны быть безопа с-ными вся криптосистема и криптографический протокол . Слабое место любого из трех этих компонентов сдел а-ет небезопасной всю систему.

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

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

Алиса хочет послать сообщение Бобу. Сначала она шифрует его открытым ключом Боба, а затем подписывает своим закрытым ключом . Ее зашифрованное и подписанное сообщение выглядит так :

me" mod nB )dA mod nA

Вот как Боб может доказать, что Алиса послала ему т, а не т. Так как Бобу известно разложение на множители nB (это его собственный модуль), он может вычислить дискретные логарифмы по основанию nB. Следовательно, ему нужно только найти x, для которого

mx = m mod nB

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

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

Стандарты

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 года.

19.4 Pohlig-Hellman

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

C = P mod n

P = Cd mod n

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

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

e = logC mod n

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

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

19.5 Rabin

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