Алгоритм шифрования RSA.

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

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

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом, так и закрытым ключом. В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, то есть:

• сообщения , где — множество допустимых сообщений;
• допустимых открытого и закрытого ключей и ;
• соответствующие функции шифрования и расшифрования , такие что

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

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

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

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

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

· Число называется открытой экспонентой;

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

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

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

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

6. Пара публикуется в качестве открытого ключа RSA.

7. Пара играет роль закрытого ключа RSA и держится в секрете.

Предположим, отправитель хочет послать получателю сообщение m.

Сообщениями являются целые числа в интервале от до , т.е .

Шифрование:

· Взять открытый ключ получателя;

· Взять открытый текст ;

· Зашифровать сообщение с использованием открытого ключа:

Дешифрование:

· Принять зашифрованное сообщение

· Взять свой закрытый ключ

· Применить закрытый ключ для расшифрования сообщения: