RSA

Определение:

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

Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи.

Реализация

Алгоритм RSA включает в себя четыре этапа: генерация ключей, передача ключей, шифрование и расшифрование.

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

Определение:

Односторонняя функция (англ. one-way function) — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции.

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

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

Определение:

Возведение в степень по модулю (англ. modular exponentiation) — это вычисление остатка от деления натурального числа [math]b[/math] (основание), возведенного в степень [math]n[/math] (показатель степени), на натуральное число [math]m[/math] (модуль). Обозначается: [math]c\equiv b^{n} \pmod m[/math]

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и закрытым ключом (англ. private key). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными. То есть для любых допустимых пар открытого и закрытого ключей [math](p,s)[/math] существуют соответствующие функции шифрования [math]E_p(x)[/math] и расшифрования [math]D_s(x)[/math] такие, что для любого сообщения [math]m \in M[/math], где [math]M[/math] — множество допустимых сообщений, [math]m=D_s(E_p(m))=E_p(D_s(m)).[/math]

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

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

1. Выбираются два различных случайных простых числа [math]p[/math] и [math]q[/math] заданного размера (например, [math]1024[/math] бита каждое).
2. Вычисляется их произведение [math]n=p\cdot q[/math], которое называется модулем.
3. Вычисляется значение функции Эйлера от числа [math]n[/math]:

   [math]\varphi(n) = (p-1)\cdot (q-1).[/math]

4. Выбирается целое число [math]e[/math] ([math]1 \lt e \lt \varphi(n)[/math]), взаимно простое со значением функции [math]\varphi(n)[/math]. Обычно в качестве [math]e[/math] берут простые числа, содержащие небольшое количество единичных бит в двоичной записи.
   • Число [math]e[/math] называется открытой экспонентой (англ. public exponent)
   • Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в [math]e[/math].
   • Слишком малые значения [math]e[/math], например 3, потенциально могут ослабить безопасность схемы RSA.
5. Вычисляется число [math]d[/math], мультипликативно обратное к числу [math]e[/math] по модулю [math]\varphi(n)[/math], то есть число, удовлетворяющее сравнению:

   [math]d\cdot e \equiv 1 \pmod{\varphi(n)}.[/math]

   • Число [math]d[/math] называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
6. Пара [math]\left\{ e, n \right\}[/math] публикуется в качестве открытого ключа RSA (англ. RSA public key).
7. Пара [math]\left\{ d, n \right\}[/math] играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

Определение:

Случайное простое число (англ. random prime numbers) — в криптографии, простое число, содержащее в двоичной записи заданное количество битов [math]k[/math]

Передача ключей

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

Шифрование

Предположим, Боб хочет послать Алисе сообщение [math]m[/math]. Сообщениями являются целые числа в интервале от [math]0[/math] до [math]n - 1[/math], то есть [math]m \in \mathbb{Z}_{n}[/math]. Алгоритм:

• Взять открытый ключ [math](e,n)[/math] Алисы
• Взять открытый текст [math]m[/math]
• Зашифровать сообщение с использованием открытого ключа Алисы:

  [math]c = E(m) = m^e \mod n [/math]

Расшифрование

Алгоритм:

• Принять зашифрованное сообщение [math]c[/math]
• Взять свой закрытый ключ [math](d,n)[/math]
• Применить закрытый ключ для расшифрования сообщения:

  [math]m = D(c) = c^d \mod n [/math]