Криптосистемы с открытым ключом — RSA

В качестве второго примера криптографического алгоритма рассмотрим широко используемую систему с открытым ключом — RSA, названную в честь ее изобретателей — Ривеста (Rivest), Шамира (Shamir) и Альдемана (Aldeman). Защита RSA вытекает из того факта, что в настоящее время не существует эффективного метода нахождения простых множителей больших чисел. Можно показать, что любое целое число можно записать в виде произведения простых чисел. Так, например, 2100 может быть записано как:

2100 = 2 × 2 × 3 × 5 × 5 × 7.

Таким образом, 2, 3, 5 и 7 являются простыми множителями числа 2100. В RSA открытый и закрытый ключи создаются из очень больших простых чисел (содержащих сотни десятичных цифр). Взлом RSA эквивалентен обнаружению этих чисел. В настоящее время подобная задача неразрешима, несмотря на то, что математики работают над ней уже несколько столетий.

Создание открытых и закрытых ключей происходит в четыре этапа.

1. Выбираются два больших простых числа, р и q.

2. Вычисляется их произведение n = p×q и z = (p – 1)×(q – 1).

3. Выбирается число d, взаимно простое с z.

4. Вычисляется число е, такое, что e×d = 1 mod z.

Одно из чисел, например d, может впоследствии использоваться для расшифровки, а е — для шифрования. Только одно из этих двух чисел будет открытым, какое именно — зависит от используемого алгоритма.

Рассмотрим вариант, когда Алиса хочет, чтобы сообщение, которое она посылает Бобу, было конфиденциально. Другими словами, она хочет быть уверена в том, что никто кроме Боба не сможет перехватить и прочитать ее сообщение. RSA рассматривает любое сообщение т как строку битов. Каждое сообщение сначала разбивается на блоки фиксированной длины, и каждый очередной блок m_i представляется в виде числа в двоичном виде, лежащего в интервале 0 ≤ m_i < п.

Для шифрования сообщения т отправитель вычисляет для каждого блока m_i значение c_i = m^e_i(mod п), которое и отправляется получателю. Расшифровка на стороне получателя производится путем вычисления m_i = c^d_i(mod п). Отметим, что для шифрования необходимы e и n, в товремя как для расшифровки — d и n.

Сравним RSA с симметричными криптосистемами, такими как DES. Для RSA характерен недостаток — сложность вычислений, которая приводит к тому, что расшифровка сообщений, зашифрованных по алгоритму RSA, занимает в 100–1000 раз больше времени, чем расшифровка сообщений, зашифрованных по алгоритму DES. Точный показатель зависит от реализации. В результате многие криптографические системы используют RSA только для безопасного обмена общими секретными ключами, избегая применять этот способ для шифрования «обычных» данных.

Дата добавления: 2014-01-13