Слабые моменты реализации RSA

Разделенный модуль: Поскольку арифметика остатков – дорогое удовольствие с точки зрения компьютера, весьма заманчиво разработать систему шифрования, в которой пользователи разделяют общий модуль N, но применяют различные открытые и закрытые экспоненты (E_i, d_i).

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

Предположим, что нападающим является один из законных клиентов криптосистемы, скажем пользователь номер 1. Он может найти значение секретной экспоненты пользователя 2 – d ₂. Сначала он вычисляет p и q по известному ему d ₁. Затем злоумышленник находит

j (N) = (p – 1)(q – 1) и, наконец, при помощи расширенного алгоритма Евклида раскрывает значение d ₂ по формуле

Предположим, что теперь атакующий не принадлежит к пользователям криптосистемы, использующей общий модуль. Допустим, происходит рассылка одинакового (допустим циркулярного) сообщения m двум клиентам криптосистемы, открытые ключи которых

(N, E ₁) и (N, E ₂).

Противник, нападающий извне, видит зашифрованные сообщения С ₁ и C ₂, где

Он может вычислить

и восстановить сообщение m по следующей схеме:

Пример. N = N ₁ = N ₂ = 18923, E ₁ = 11 и E ₂ = 5.

Предположим, что перехвачены шифртексты

C ₁ = 1514 и C ₂ = 8189,

соответствующие одному открытому тексту m. Тогда противник вычисляет T ₁ = 1 и T ₂ = 2, после чего раскрывает исходную информацию:

Вывод. При использовании общего модуля N любой законный пользователь системы может восстановить секретную экспоненту d другого пользователя, а внешний противник сможет читать циркулярные сообщения m.

Малые шифрующие экспоненты:

Иногда в криптосистемах RSA с целью экономии затрат на шифрование используются небольшие шифрующие экспоненты E. Это тоже создает дополнительные проблемы, связанные с криптостойкостью. Предположим, что есть три пользователя с различными модулями шифрования

N ₁, N ₂ и N ₃

и одинаковой шифрующей экспонентой E = 3. Пусть некто посылает им одно сообщение m, зашифрованное тремя разными открытыми ключами. Нападающий видит три криптограммы:

C ₁ = m ³ (mod N ₁),

C ₂ = m ³ (mod N ₂),

C ₃ = m ³ (mod N ₃)

и с помощью китайской теоремы об остатках находит решение системы

{ X = C_i (mod N_i)| i = 1, 2, 3}

в виде

X = m ³ (mod N ₁ N ₂ N ₃).

Но поскольку m ³ < N ₁ N ₂ N ₃, целые числа X и m ³ должны совпадать. Поэтому, вычисляя обычный кубический корень из X, нападающий раскрывает сообщение m.