Алгоритм RSA

Протокол генерации ключей алгоритма Диффи-Хеллмана

Абоненты А и В:

1. знают числа A и P, которые являются открытыми константами протокола и известны всем участникам Р – простое число и А является примитивным корнем Р;

2. генерируют независимо друг от друга случайные числа – закрытые ключи: Ka, Kb, удовлетворяющих условию: 1 < K < P;

3. вычисляют значения Y_A = A ^Ka mоd(P) и Y_B = A ^Kb mоd(P) и обмениваются ими по открытому каналу связи;

4. вычисляют общий секретный ключ K, которым шифруют сообщения по симметричному алгоритму.

абонент А:

K = (Y_B)^Ка mod (Р) = (A^Кb mod (Р))^Ка mod (Р) = (A^Кb)^Ка mod (Р)

абонент В:

K = (Y_А)^Кb mod (Р) = (A^Ка mod (Р))^Кb mod (Р) = (A^Ка)^Кb mod (Р)

Таким образом, две стороны обменялись секретным ключом. Так как значения К_а и К_b являются секретными, противник может получить только следующие значения: Р, A, Y_А и Y_В. Для вычисления ключа атакующий должен взломать дискретный логарифм, т.е. вычислить К_а и К_b, что является вычислительно трудной задачей.

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

Следует заметить, что данный алгоритм уязвим для атак типа "man-in-the-middle". Если противник может осуществить активную атаку, т.е. имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников Y_i и Y_j, создать свою пару открытого и закрытого ключа (К_н, Y_н) и послать каждому из участников свой открытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником. Если нет контроля целостности, то участники не смогут обнаружить подобную подмену.

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

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest), Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. С тех пор алгоритм Rivest-Shamir-Adleman (RSA) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом. Криптостойкость алгоритма основана на использовании того факта, что задача факторизации является трудной, т.е. легко перемножить два числа, в то время как не существует полиномиального алгоритма нахождения простых сомножителей большого числа.

Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные являются целыми между 0 и n -1 для некоторого n.

Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа. Для алгоритма RSA этап создания ключей состоит из следующих операций:

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

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

3. Выбирается произвольное число e (e < n), такое, что

НОД(e,(p-1)(q-1))=1,

то есть e должно быть взаимно простым с числом (p-1)(q-1).

4. Методом Евклида решается в целых числах уравнение

e*d+(p-1)(q-1)*y=1.

Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.

5. Два числа { e,n } – являются открытым ключом KU.

6. Число d хранится в секрете – это и есть закрытый ключ – KR = {d,n}, который позволит расшифровать сообщения, зашифрованные с помощью пары чисел (e,n).

Как же производится собственно шифрование с помощью этих чисел:

1. Отправитель разбивает свое сообщение на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

2. Подобный блок может быть интерпретирован как число из диапазона (0; 2^k-1). Для каждого такого числа m_i вычисляется выражение c_i=(m_i)^e mod n. Блоки c_i и есть зашифрованное сообщение.

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

(x^(p-1)(q-1))mod n = 1.

Для дешифрования RSA-сообщений используется эта формула. Возведем обе ее части в степень (-y):

(x^{(-y) (p-1) (q-1)}) mod n = 1^(-y) = 1.

Теперь умножим обе ее части на x:

(x^{(-y) (p-1) (q-1) +1})mod n = 1*x = x (1)

А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в выражении (1) мы можем заменить показатель степени на число (e*d). Получаем (x^e*d)mod n = x. То есть для того чтобы прочесть сообщение c_i=(m_i)^emod n достаточно возвести его в степень d по модулю m:

(c_i)^dmod n = (m_i)^e*dmod n = m_i.

Алгоритм RSA основан на использовании односторонней функции с лазейкой. Зная публично известные n и e, мы можем найти С = M^e (mod n) по заданному M, но не наоборот (если злоумышленник перехватит C, то восстановить M вычислительно трудная задача). При этом, если мы знаем как n раскладывается на множители, то выполнить обратную операцию легко, вычислив d. Разложение числа n на множители и есть та самая лазейка. Наличие лазейки позволяет применять RSA как для шифрования, так и в схеме цифровой подписи.

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