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

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

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

Пусть т - открытый текст сообщения. Два ключа шифрования - е_г и е₂. Общий модуль - п. Шифротекстами сообщения являются:

Cj = m"¹ mod и

с₂ = т¹ mod и

Криптоаналитик знает п, е_и е₂, с_г и с₂. Вот как он узнает т.

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

ге_г + se₂ = 1

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

(dY * c₂^s = m mod n

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

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