63 Стандарт rsa. Алгоритм работы стандарта rsa.

RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом.

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

Криптографические системы с открытым ключом используют так называемые однонаправленные функции, которые обладают следующим свойством:

• Если   известно, то   вычислить относительно просто

• Если известно  , то для   нет простого пути вычисления

Под однонаправленностью понимается не теоретическая однонаправленость, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.

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

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и секретным ключом (англ. secret key). Каждый ключ — это часть информации. В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и секретный ключ самостоятельно. Секретный ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и секретный ключи каждого участника обмена сообщениями образуют «согласованную пару» в том смысле, что они являются взаимно обратными

Алгоритм создания открытого и секретного ключей

RSA-ключи генерируются следующим образом:^[4]

1. Выбираются два случайных простых числа p и q заданного размера (например, 1024 бита каждое).

2. Вычисляется их произведение n = pq, которое называется модулем.

3. Вычисляется значение функции Эйлера от числа n:

4. Выбирается целое число e ( ), взаимно простое со значением функции  . Обычно в качестве e берут простые числа, содержащие небольшое количество единичных битов в двоичной записи, например, простые числа Ферма 17, 257, или 65537.

   • Число e называется открытой экспонентой (англ. public exponent)

   • Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в e.

   • Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA.^[5]

5. Вычисляется число d, мультипликативно обратное к числу e по модулю  , то есть число, удовлетворяющее условию:

 или:  , где k — некоторое целое число.

• Число d называется секретной экспонентой.

• Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.

Пара P = (e,n) публикуется в качестве открытого ключа RSA (англ. RSA public key).