Атака на основе общего RSA-модуля

При реализации RSA можно попробовать раздать всем абонентам криптосети одинаковый модуль n, но каждому — свои значения показателей степени e и d. При этом наиболее очевидная проблема заключается в том, что если одно и то же сообщение когда-нибудь шифровалось разными показателями степени (при фиксированном модуле) и эти два показателя — взаимно-простые числа (как обычно и бывает), то открытый текст может быть раскрыт даже при неизвестных ключах дешифрования. Пусть заданы: m — открытый текст, e1 и e2 — два ключа шифрования, n — общий модуль. Шифротекстами сообщения являются:

c1 = me1 mod n,.

c2 = me2 mod n,.

Криптоаналитик знает n, e1, e2, c1 и c2. Так как e1 и e2 — взаимно-простые числа, то, воспользовавшись расширенным алгоритмом Евклида, можно найти такие числа r и s, что.

re1 + se2 = 1.

Полагая r отрицательным (или r, или s должно быть отрицательным), можно снова воспользоваться расширенным алгоритмом Евклида для вычисления c1−1. Тогда.

(c1−1)-rc2s = m mod n.

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