Атака «шифрование коротких сообщений»

Известно, что криптосистема RSA обладает низкой криптостойкостью при зашифрованном на малом e коротком сообщении. Действительно, при c = me n трудоемкость такой атаки ниже трудоемкости исчерпывающего перебора для m. Однако меры противодействия также очевидны, — либо открытый ключ e должен быть достаточно большим, либо открытый текст не должен быть коротким. Выбор малого e обусловлен соображениями вычислительной эффективности шифрования и проверки подписи. Таким образом, разумный подход заключается в искусственном наращивании коротких открытых текстов («набивки»). При этом необходимо следить за тем, чтобы удлиненный открытый текст при числовом отображении не превращался в набор множителей некоторого известного числа P, например P = 2l, что происходит при дополнении открытого текста последовательностью нулей справа (со стороны младших разрядов).

Раскрытие малого показателя…

шифрования Хэстед (J. Hasted) продемонстрировал уязвимость RSA при условии, если криптоаналитик может получить множество шифротекстов фиксированного сообщения m, зашифрованного при помощи криптосистемы RSA с различными секретными параметрами p и q, но при использовании фиксированного открытого ключа e. При соблюдении сформулированных условий можно раскрыть сообщение m. Известен частный случай, когда при заданных l раз-личных результатах шифрования me mod n1,…, me mod nl можно раскрыть m при помощи Китайской теоремы об остатках. В общем случае, при заданных t результатах шифрования.

(a1m +b1)e mod n1,…,(atm + bt) e mod nt,.

где ai и bi, заданы и t > е (е+1)/2, можно раскрыть сообщение т, воспользовавшись известным математическим методом. Еще раз отметим, что данная атака возможна только при условии, что исходные сообщения получены известным криптоаналитику способом (фиксированное сообщение т является частным случаем) дешифрования.

Другая атака позволяет раскрывать d, когда d не превышает четверти размера n, а e < n. При случайном выборе e и d, это маловероятно и никогда не произойдет, если значение e мало. Значение d, должно быть большим.

Атака на протокол

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

(meB mod nB) dA mod nA.

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

m?x = m mod nB.

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