Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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

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

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

(N, E 1) и (N, E 2).

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

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

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

Пример. N = N 1 = N 2 = 18923, E 1 = 11 и E 2 = 5.

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

C 1 = 1514 и C 2 = 8189,

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

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

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

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

N 1, N 2 и N 3

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

C 1 = m 3 (mod N 1),

C 2 = m 3 (mod N 2),

C 3 = m 3 (mod N 3)

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

{ X = Ci (mod Ni)| i = 1, 2, 3}

в виде

X = m 3 (mod N 1 N 2 N 3).

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





Дата публикования: 2014-11-02; Прочитано: 412 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...