Современные информационные технологии/Информационная безопасность

Иваница А.В.

Национальный горный университет, Украина

Алгоритм шифрования с открытым ключом RSA

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

Алгоритм RSA состоит из следующих пунктов:

1. Выбрать простые числа p и q

2. Вычислить n = p * q

3. Вычислить m = (p - 1) * (q - 1)

4. Выбрать число d взаимно простое с m

5. Выбрать число e так, чтобы e * d = 1 (mod m)

Числа e и d являются ключами. Шифруемые данные необходимо разбить на блоки - числа от 0 до n - 1. Шифрование и дешифровка данных производятся следующим образом:

· Шифрование: b = a^e (mod n)

· Дешифрование: a = b^d (mod n)

Следует также отметить, что ключи e и d равноправны, т.е. сообщение можно шифровать как ключом e, так и ключом d, при этом расшифровка должна быть произведена с помощью другого ключа.

В первом пункте алгоритма RSA сказано, что необходимо выбрать два простых числа p и q. Простой способ - деление предполагаемого простого числа на все числа меньшие его не работоспособен уже с 32-битными числами (требуется очень много времени на выполнение).

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

Нахождение взаимно простых чисел

На шаге 4 алгоритма RSA необходимо найти число d взаимно простое с m, т.е. не имеющее общих делителей с ним, кроме единицы. Число d должно быть меньше m, т.о. разрядность числа d равна сумме бит в числах p и q. Для нахождения взаимно простых чисел используется алгоритм Евклида, который находит наибольший общий делитель двух чисел. Если найденный делитель больше единицы, то необходимо выбрать другое число d и повторить проверку.

Решение уравнения a * x + b * y = 1

В 5-м пункте алгоритма RSA предполагается нахождение такого числа e, чтобы e * d = 1 (mod m). Для этого нужно использовать модифицированный алгоритм Евклида, который работает только если числа d и m взаимно просты. Вычисление числа e сводится к решению уравнения m * x + d * e = 1 в натуральных числах. Число x не существенно.

Большие числа и работа с ними

На данный момент времени рекомендуется в качестве чисел e и d брать числа, длиной не менее 768 бит. Ключ в 1024 бит является достаточно надежным для обычных целей шифрования. Для повышенной безопасности рекомендуется брать ключи размером 2048 бит. Т.о. числа p и q должны иметь разрядность вдвое ниже чисел e, d, m и n (p и q рекомендуется брать примерно одного порядка, но не слишком близко друг к другу).

Алгоритм быстрого возведения в степень

В алгоритме RSA очень много возведений в степень по модулю натурального числа. Конечно же, не нужно производить триллиарды умножений, а затем брать остаток от деления числа из миллиардов цифр. Остаток от деления берется после каждого умножения. Таким образом, при перемножении двух чисел, состоящих из k бит потребуется 2 * k-битное число, которое затем делится на модуль и получается остаток, опять же состоящий из k бит (если модульное число состоит из k бит).

Сложность этого алгоритма может быть оценена как O(ln m), где m - модуль, по которому производится умножение. Запись O(ln m) означает, что для реализации алгоритма потребуется порядка ln m операций. Например, если число имеет разрядность 1024 бит (при этом длина m не менее 1024 бит), то умножение по модулю необходимо будет провести порядка ln m = ln 2¹⁰²⁴ = 710 раз, что относительно немного.

Алгоритм вычисления a^d (mod m):

1. Число d представить в двоичной системе счисления: d = d₀ * 2^r + ... + d_{r - 1} * 2 + d_r, где d_i - цифры в двоичном представлении, равные 0 или 1, d₀ = 1

2. Положить a₀ = a, затем для i = 1, ... , r вычислить a_i = (a_{i - 1}) ² * a^d_i (mod m)

3. a_r есть искомое число a^d (mod m)

Литература:

1. С. Бернет, С. Пэйн. Криптография. Официальное руководство RSA Security - "  Бином-Пресс ", 2009. -384 с.:ил.

2. С. Коутинхо. Введение в теорию чисел. Алгоритм RSA – " Постмаркет ", 2007 -328с.:ил.

3. Б. А. Фороузан. Криптография и безопасность сетей – "Бином. Лаборатория знаний", 2010 -784с.:ил.