Криптосистема шифрования данных RSA

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

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

Трудность факторизации больших чисел и трудность вычисления дискретных логарифмов определяют надежность алгоритма RSA. В данной криптосистеме открытый ключ Ко, секретный ключ Кс, сообщение М и криптограмма С принадлежат множеству целых чисел

 

 

где N – модуль, P и Q являются случайными большими взаимно простыми числами. Их выбирают равной длины и хранят в секрете для обеспечения максимальной безопасности.

Множество ZN с операциями сложения и умножения по модулю N образует арифметику по модулю N.

Открытый ключ Ко выбирают случайным образом так, чтобы выполнялись условия

 

 

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

Кроме того, открытый ключ Ко и функция Эйлера ϕ(N) также должны

быть взаимно простыми.

Затем, используя расширенный алгоритм Евклида, вычисляют секретный ключ Кс такой, что

 

 

Данное вычисление возможно, поскольку получатель знает пару простых чисел (P, Q) и может легко найти ϕ(N), при этом Кс и N должны быть взаимно простыми. Задачу зашифрования открытого текста М в криптограмму С можно решить, используя открытый ключ Ko, по следующей формуле:

 

 

Задачу расшифрования криптограммы С можно решить, используя секретный ключ Кс, по следующей формуле:

 

 

Процесс расшифрования можно записать так:

 

 

Подставляя значение в предыдущие 2 формулы, получаем:

 

 

Таким образом, получатель, который создает криптосистему, защищает два параметра: секретный ключ Кс и пару чисел P и Q, произведение которых даёт модуль N. Одновременно публикует значения модуля N и открытого ключа Ко, поэтому противнику известны только значения Ко и N. Если бы криптоаналитик смог разложить число N на множители P и Q, то он узнал бы тройку чисел (P,Q, Ko), значение функции Эйлера ϕ(N) = (P – 1) (Q – 1) и определил значение секретного ключа Kc.

Однако, как отмечалось выше, разложение большого числа N на множители вычислительно не осуществимо при длине выбранных P и Q не менее 100 десятичных знаков.