Программные Speedups

Шифрование RSA выполняется намного быстрей, если вы правильно выберете значение e. Тремя наиболее частыми вариантами являются 3, 17 и 65537 (2¹⁶ + 1). (Двоичное представление 65537 содержит только две единицы, поэтому для возведения в степень нужно выполнить только 17 умножений.) X.509 советует 65537 [304], PEM рекомендует 3 [76], а PKCS #l (см. раздел 24.14) - 3 или 65537 [1345]. Не существует никаких проблем безопасности, связанных с использованием в качестве e любого из этих трех значений (при условии, что вы дополняете сообщения случайными числами - см. раздел ниже), даже если одно и то же значение e используется целой группой пользователей.

Операции с закрытым ключом можно ускорить при помощи китайской теоремы от остатках, если вы сохранили значения pи q, а также дополнительные значения: dmod (p - 1), dmod (q - 1) и q^-1mod p[1283, 1276]. Эти дополнительные числа можно легко вычислить по закрытому и открытому ключам.

Безопасность RSA

Безопасность RSA полностью зависит от проблемы разложения на множители больших чисел. Технически, это утверждение о безопасности лживо. Предполагается, что безопасность RSA зависит от проблемы разложения на множители больших чисел. Никогда не было доказано математически, что нужно разложить n на множители, чтобы восстановить mпо c и e. Понятно, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Я не слишком волнуюсь об этом.

Также можно вскрыть RSA, угадав значение (p-1)(q-1). Это вскрытие не проще разложения n на множители [1616].

Для сверхскептиков: доказано, что некоторые варианты RSA также сложны, как и разложение на множители (см. раздел 19.5). Загляните также в [361, где показано, что раскрытие даже нескольких битов информации по зашифрованному RSA шифротексту не легче, чем дешифрирование всего сообщения.

Самым очевидным средством вскрытия является разложение nна множители. Любой противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ дешифрирования d, противник должен разложить n на множители. Современное состояние технологии разложения на множители рассматривалось в разделе 11.4. В настоящее время передним краем этой технологии является число, содержащее 129 десятичных цифр. Значит, nдолжно быть больше этого значения. Рекомендации по выбору длины открытого ключа приведены в разделе 7.2.

Êîíå÷íî, криптоаналитик может перебирать все возможные d, пока он не подберет правильное значение. Но такое вскрытие грубой силой даже менее эффективно, чем попытка разложить nна множители.

Время от времени появляются заявления о том, что найден простой способ вскрытия RSA, но пока ни одно из подобных заявлений не подтвердилось. Íàïðèìåð, в 1993 году в черновике статьи Вильяма Пейна (William Payne) был предложен метод, основанный на малой теореме Ферма [1234]. К сожалению, этот метод оказался медленнее разложения на множители

Существует еще один повод для беспокойства. Большинство общепринятых алгоритмов вычисления простых чисел pи qвероятностны, что произойдет, если p или qокажется составным? Ну, во первых, можно свести вероятность такого события до нужного минимума. И даже если это произойдет, скорее всего такое событие будет сразу же обнаружено - шифрование и дешифрирование не будут работать. Существует ряд чисел, называемых числами Кармайкла (Carmichael), которые не могут обнаружить определенные вероятностные алгоритмы поиска простых чисел. Они небезопасны, но чрезвычайно редки [746]. Честно говоря, меня бы это не обеспокоило.