Алгоритм RSA

Фирма RSA Data Security образована в США в 1982 г. тремя математиками-выпускниками Массачусетского технологического института Rivest-Shamir-Adleman. RSA опубликован в 1978. Был частной собственностью, срок действия патента закончился в 2000г.

Алгоритм RSA (по первым буквам фамилий его создателей Rivest-Shamir-Adleman) основан на свойствах простых чисел (причем очень больших) и китайской теореме об остатках – CRT Chinese Remainder Theorem – в своей базовой форме впервые была доказана китайским математиком Сунь Цзе, жившем в первом веке до н.э.

Простыми называются такие числа, которые не имеют делителей, кроме самих себя и единицы. А взаимно простыми называются числа, не имеющие общих делителей, кроме 1.

Пусть p и q – простые числа, для каждого целого числа X можно вычислить пару (x mod p, x mod q). CRT утверждает, что можно выполнить и обратную операцию: зная пару (x mod p, x mod q), восстановить исходное значение Х.

Для начала выберем два очень больших простых числа p и q, длина каждого из которых составляет порядка 1000 бит и более (большие исходные числа нужны для построения больших криптостойких ключей. Например, Unix-программа ssh-keygen по умолчанию генерирует ключи длиной 1024 бита).

Определим параметр n как результат перемножения p и q, которые должны быть примерно одного размера.

= (p -1)*(q -1) - функция Эйлера

Выберем большое случайное число и назовем его e < , причем оно должно быть взаимно простым с .

Отыщем такое число d < , для которого верно соотношение

(e*d) mod = 1

Открытым ключом является пара чисел e и n, а закрытым — d и n.

При шифровании исходный текст рассматривается как числовой ряд, и над каждым его числом мы совершаем операцию

C = (Oi^e) mod n.

В результате получается последовательность C(i), которая и составит криптотекст. Декодирование информации происходит по формуле

Oi = (Ci^d) mod n.

Как видите, расшифровка предполагает знание секретного ключа.

Система относится к блочным экспоненциальным системам, так как каждый блок О_i открытого текста рассматривается как целое число в интервале (0,..., n-1) и преобразуется в блок С_i открытым преобразованием

Без знания простых сомножителей p и q значение ключей е и d определить очень трудно. Поэтому если делать открытыми числа e и n, а число d держать в секрете, то нахождение О из С сводится к трудной задаче извлечения корня степени е из числа С по модулю n. Это и означает, что алгоритм RSA может быть использован для построения криптосистемы с открытым ключом, т.е. системы открытого шифрования, когда преобразование шифрования открыто, а преобразование дешифрования держится в секрете. Стойкость алгоритма RSA можно оценить сверху сложностью разложения целого числа n на простые сомножители p и q. Это весьма трудная задача. (Единственная возможность вычислить d – это попытаться разложить n на простые множители p, q) При достаточно большом значении n не существует известного на сегодня алгоритма, который мог бы определить закрытый ключ за приемлемое время. Вот почему разложение на простые множители играет такую важную роль в криптографии. Так как в силу открытости любой злоумышленник имеет доступ к преобразованию шифрования E_(e,n), то он может всегда выбрать любой открытый текст и получить соответствующий ему шифротекст. Поэтому криптосистемы с открытым ключом должны быть устойчивы к методам криптоанализа по паре открытый/закрытый текст.

Рассмотрим конкретный пример: Выбрать два простых числа: р = 7, q = 17.
Вычислить n = p·q = 7 · 17 = 119.
Вычислить (n) = (p - 1)·(q - 1) = 96.
Выбрать е так, чтобы е было взаимнопростым с (n) = 96 и меньше, чем (n): е = 5.
Определить d так, чтобы d·e ≡ 1 mod 96 и d < 96.
d = 77, так как 77 · 5 = 385 = 4 · 96 + 1.
Результирующие ключи открытый Kp = { 5, 119 } и закрытый KS = { 77, 119 }.
Например, требуется зашифровать сообщение O = 19.
19⁵ (mod 119) = 66; С = 66.
Для дешифрования вычисляется 66⁷⁷ (mod 119) = 19.

Для определения того, является ли число простым применяют различные алгоритмы: решето Эратосфена, цикличный перебор всех целых чисел, или метод основанный на малой теореме Ферма – при простом числе P и любом целом числе K < P справедливо следующее тождество à K^P-1 mod P = 1

Для полноты изложения отметим, что для алгоритма RSA существует малая вероятность того, что шифровка числа O возведем в степень е по модулю n может не изменить открытый текст O. Это следует из теоретического факта, что для каждого значения е существует, по крайней мере, 9 таких значений O, что

Например, для n = p · q = 47·59=2773 это числа

O = 0,1,2773,2537,2303,235,2538,471,236.

Э лектронная Ц ифровая П одпись – ЭЦП. Служит для:

1) удостоверения подлинности документа

2) удостоверения подлинности автора

3) запрета отказа от авторства подписанного документа

4) защищает от изменения документа.

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

отправитель шифрует подпись открытым ключом получателя + делает хэш-отпечаток подписи и посылает все это вместе с криптограммой документа получателю. Получатель принимает сообщение и дешифрует подпись своим секрктным ключом, затем выполняет вычисление h-кода подписи. Если присланный и полученный хэши совпали, то документ получен от истинного лица

ХЭШ

Перевод сообщения O в число H(O) (схема Горнера):

H(O)=

где X – основание системы

Возьмем в качестве подписи название алгоритма, т.е. RSA. Чтобы перевести RSA в число будем считать букву R = 18, S = 19, A = 1 по порядковому номеру в латинском алфавите. Пусть X=32 Тогда слову RSA будет соответствовать число

Kp = { 5, 119 } и закрытый KS = { 77, 119 }

Дата добавления: 2015-07-24