§ 1. Алгоритм создания открытого и секретного ключей
RSA-ключи генерируются следующим образом:
Выбираются два случайных простых числа p и q заданного размера (например, 1024 бита каждое).
Вычисляется их произведение n=p·q, которое называется модулем.
Вычисляется значение функции Эйлера от числа n:
φ(n)=(p-1)·(q-1) .
Выбирается целое число e (1 < e < φ(n)), взаимно простое со значением функции φ(n). Обычно в качестве e берут простые числа, содержащие небольшое количество единичных битов в двоичной записи, например, простые числа Ферма 17, 257, или 65537.
Число e называется открытой экспонентой (англ. public exponent).
Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в e.
Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA.
Вычисляется число d, мультипликативно обратное к числу e по модулю φ(n), то есть число, удовлетворяющее условию:
d·e1(mod φ(n)) или: d·e=1+k ·φ(n)), где k – некоторое целое число.
Число d называется секретной экспонентой.
Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
Пара P=(e, n) публикуется в качестве открытого ключа RSA (англ. RSA public key).
Пара S=(d, n) играет роль секретного ключа RSA (англ. RSA private key) и держится в секрете.
Достарыңызбен бөлісу: |
