Интернет магазин китайских планшетных компьютеров

Компьютеры - Криптоанализ RSA - Малые значения секретной экспоненты

Начальные данные: Чтобы увеличить скорость расшифрования было уменьшено число ненулевых битов двоичного представления секретной экспоненты .

Задача: вычислить секретную экспоненту .

В 1990 году Михаэль Винер показал, что в случае малого значения d возможен взлом системы RSA, а именно:

Теорема Винера:
  Пусть 
         n = pq, где 
         
  Тогда, если известно , где ,
  то существует эффективный способ вычислить d.

Защита: Таким образом если n имеет размер 1024 бита, необходимо чтобы d был не менее 256 бит длиной.

Малые значения открытой экспоненты

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

.

Атака Хастада

Начальные условия: Сторона отсылает зашифрованное сообщение пользователям . Каждый пользователь имеет свой открытый ключ , причём . Сторона зашифровывает сообщение, используя поочерёдно открытый ключ каждого пользователя, и отсылает его соответствующему адресату. Противник прослушивает канал передачи и собирает переданных шифротекстов.

Задача: противник хочет восстановить сообщение .

Положим , тогда противник может восстановить если .