Схема шифрования RSA: практика

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

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

• 1. Модуль т = pq должен быть целым числом, являющимся произведением двух простых чисел р, q и удовлетворяющим условию |_log₂mJ € {2¹⁰, 2¹¹, 2¹², …}. Столь большие размеры числа т делают затруднительным применение методов факторизации целых чисел общего вида, таких как метод квадратичного решета, см. главу 13.
• 2. Числа р, q не должны быть маленькими и удовлетворять неравенствам

Как правило, простые числа р, q выбирают величинами одного порядка с у/m. Подобное ограничение затрудняет применение методов разложения на множители, основанных на поиске маленьких простых делителей, например методов Брента или Ленстры^[1].

3. Должно выполняться неравенство.

Это условие не позволяет реализовывать методы факторизации, основанные на близости делителей числа гп, например метод Ферма, см. |2|.

Иногда накладывается еще более строгое условие, а именно величина р — q должна иметь большой простой делитель г, удовлетворяющий неравенству г > В.

А. Числа р± 1 и q± 1 должны иметь большие простые делители, то есть.

где pi р2, — простые числа, удовлетворяющие неравенствам.

Подобное ограничение делает невозможным применение методов разложения па множители частного вида, таких как методы Полларда и Вильямса, см. |2].

• 5. Величина w — НОД (р-1, <7 — 1) должна удовлетворять неравенству wB < фт. Подобное ограничение существенно снижает число эквивалентных ключей схемы RSA и делает невозможным определение величины р (т), см. раздел
• 10.1.1.8.
• 6. Величина | не должна быть близкой к отношению двух небольших целых чисел, то есть неравенство pr—q.s < фт не должно быть разрешимо ни для каких натуральных чисел г, s, удовлетворяющих неравенствам г < В, s < В. Данное ограничение делает невозможным факторизацию модуля схемы RSA методом Лемана, см. [2].
• 7. Как правило, открытый ключ е должен удовлетворять равенству 2^1С + 1 = 65 537. Модуль т схемы RSA должен удовлетворять условию

огс^_(т) е> В.

Подобное ограничение делает затруднительными атаки на основе итерационного дешифрования, см. раздел 10.1.1.6.

• 8. Величина НОД (р-1, е — 1) • НОД (д-1, е — 1) должна принимать наименьшее из возможных значений, равное 4, см. раздел 10.1.1.7.
• 9. Модуль схемы т не должен иметь вид т = а" ± с для значений с, удовлетворяющих неравенству 1 < с < В. Подобное ограничение делает затруднительным применение частных случаев метода решета числового поля для факторизации модуля т.

Перечисленные нами требования не являются стандартизированными, а вытекают из большого числа методов компрометации схемы RSA. Вместе с тем стандартизированные решения накладывают специальные требования на формирование целого числа s, получаемого из зашифровываемого сообщения. Приведем описание двух вариантов схемы шифрования RSA в том виде, в каком они изложены в действующем в настоящее время стандарте PKCS#1.

• [1] См. Lenstra H.W. Factoring integers with elliptic curves // Ann. Math. -Vol. 126. — 1987. — pp. 649−673.