Разделенный модуль: Поскольку арифметика остатков – дорогое удовольствие с точки зрения компьютера, весьма заманчиво разработать систему шифрования, в которой пользователи разделяют общий модуль N, но применяют различные открытые и закрытые экспоненты (Ei, di).
Одна из причин, побуждающая это делать, - ускорить алгоритмы зашифрования и расшифрования в аппаратных средствах, специально настроенных на определенный модуль N. Однако это неудачная идея, поскольку пасует перед двумя типами нападающих: внутреннего, то есть законного пользователя системы, и внешнего.
Предположим, что нападающим является один из законных клиентов криптосистемы, скажем пользователь номер 1. Он может найти значение секретной экспоненты пользователя 2 – d2. Сначала он вычисляет p и q по известному ему d1. Затем злоумышленник находит
j(N) = (p – 1)(q – 1) и, наконец, при помощи расширенного алгоритма Евклида раскрывает значение d2 по формуле
Предположим, что теперь атакующий не принадлежит к пользователям криптосистемы, использующей общий модуль. Допустим, происходит рассылка одинакового (допустим циркулярного) сообщения m двум клиентам криптосистемы, открытые ключи которых
(N, E1) и (N, E2).
Противник, нападающий извне, видит зашифрованные сообщения С1 и C2, где
Он может вычислить
и восстановить сообщение m по следующей схеме:
Пример. N = N1 = N2 = 18923, E1 = 11 и E2 = 5.
Предположим, что перехвачены шифртексты
C1 = 1514 и C2 = 8189,
соответствующие одному открытому тексту m. Тогда противник вычисляет T1 = 1 и T2 = 2, после чего раскрывает исходную информацию:
Вывод. При использовании общего модуля N любой законный пользователь системы может восстановить секретную экспоненту d другого пользователя, а внешний противник сможет читать циркулярные сообщения m.
Малые шифрующие экспоненты:
Иногда в криптосистемах RSA с целью экономии затрат на шифрование используются небольшие шифрующие экспоненты E. Это тоже создает дополнительные проблемы, связанные с криптостойкостью. Предположим, что есть три пользователя с различными модулями шифрования
N1, N2 и N3
и одинаковой шифрующей экспонентой E = 3. Пусть некто посылает им одно сообщение m, зашифрованное тремя разными открытыми ключами. Нападающий видит три криптограммы:
C1 = m3 (mod N1),
C2 = m3 (mod N2),
C3 = m3 (mod N3)
и с помощью китайской теоремы об остатках находит решение системы
{X = Ci (mod Ni)| i = 1, 2, 3}
в виде
X = m3 (mod N1N2N3).
Но поскольку m3 < N1N2N3, целые числа X и m3 должны совпадать. Поэтому, вычисляя обычный кубический корень из X, нападающий раскрывает сообщение m.