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

[acid]

Copyright (c) Roman Lonely

Алгоритм шифрования данных с открытым ключом является наиболее переспективным в настоящий момент (RSA - Rivest, Shamir and Aldeman - его изобретатели).

Понятия:

Простое число - делится только на 1 и на само себя;

Взаимно простым- не имеют ни одного общего делителя, кроме 1;

Результат операции i mod j - остаток от целочисленного деления i на j.

Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый и секретные ключи выполнив следующие шаги:

1) Выберем два очень больших простых числа p and q.

2) Определим n, как результат умножения p on q (n= p*q).

3) Выберем большое случайное число, которое назовем d. Это число должно быть взаимно простым с результатом умножения (p-1)*(q-1).

4) Определим такое число е, для которого является истинным следующее соотношение (e*d) mod ((p-1)*(q-1))=1.

5) Hазовем открытым ключем числа e и n, а секретным ключом - чмсла d и n.

=================================

Теперь, чтобы зашифровать данные по известному ключу {e,n}, необходимо сделать следующее:

- разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0,1,2..., n-1( т.е. только до n-1).

- зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле C(i)=(M(I)^e)mod n.

Чтобы расшифровать эти данные, используя секретный ключ {d,n}, необходимо выполнить следующие вычисления: M(i) = (C(i)^d) mod n. В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

==========================

Hу, чтобы более наглядно представить алгоритм RSA, приведу следующий пример:

Зашифруем и расшифруем сообщение "САВ" по алгоритму RSA. Для простоты буду использовать маленькие числа(на практике - нужно брать намного большие).

1) Выберем p=3 and q=11.

2)Определим n= 3*11=33.

3) Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).

4) Выберем число е по следующей формуле: (e*3) mod 20=1. Значит е будет равно, например, 7: (e=7).

5) Представим шифруемое сообщение как последовательность чисел в диапозоне от 0 до 32 (незабывайте, что кончается на n-1). Буква А =1, В=2, С=3.

Теперь зашифруем сообщение, используя открытый ключ {7,33}

C1 = (3^7) mod 33 = 2187 mod 33 = 9;

C2 = (1^7) mod 33 = 1 mod 33 = 1;

C3 = (2^7) mod 33 = 128 mod 33 = 29;

Теперь расшифруем эти данные, используя закрытый ключ {3,33}.

M1=(9^3) mod 33 =729 mod 33 = 3(С);

M2=(1^3) mod 33 =1 mod 33 = 1(А);

M3=(29^3) mod 33 = 24389 mod 33 = 2(В);

Все, данные расшифрованы.

================================

Криптостойкость алгоритма RSA основывается на предположении, что исключительно трудно определить секретный ключь по известному, поскольку для этого необходимо решить задачу о существовании делителей целого числа. Данная задача является NP-полной, и, как следствие этого факта, не допускает cейчас эффективного (полиноминального) решения. Более того, сам вопрос существования эффективных алгоритмов решения NP-полных задач является до настоящего времени открытым. Если Вы используете числа, состоящие из 200 цифр(такие и надо использовать при шифровании данных), для несанкционированной расшифровки придется генерировать огромное число операций (около 10^23).


P.S/ Данные, приведенные выше, не должны быть использованы в незаконных целях!

[darrel]

Originally Posted by acid

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

А разве не может быть дырки в самой программе? Т.е. не в самом алгоритме, а в его реализации?

[acid]

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

[tig]

тест-векторы, конечно, есть, но они ни от чего не защищают и не гарантируют. увы.

[Obelix]

Originally Posted by darrel

А разве не может быть дырки в самой программе? Т.е. не в самом алгоритме, а в его реализации?

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

>acid
Но ведь этот алгоритм довольно старый, если я конечно не ошибаюсь. И уже довольно широко используется. Думаю он уже протестирован достаточно.

[tig]

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

кстати, еще один тяжелейший вопрос - надежное распространение открытых ключей.

[darrel]

Originally Posted by tig

кстати, еще один тяжелейший вопрос - надежное распространение открытых ключей.

а в чем тут, собтвенно, пороблема?

[tig]

цель защиты информации - защита данных, защита целостности данных и верификация сторон. последняя задача как раз одна из самых нетривиальных. насколько я знаю, каких-либо окончательных решений для нее не предложено.
смотри - если A посылает спаслание B, совершенно естественно они должны иметь открытые ключи друг друга (назовем их Pk(A) и Pk(B)). встает вопрос - как надежно и достоверно передать ключ A на сторону B и наоборот (Pk(A)=>B и Pk(B)=>A). просто послать по сети нельзя - если между ними есть какой-нибудь активный негодяй T, то он может подменить ключи: если A<=>T<=>B, то Pk(A)=>T, Pk(T)=>B и Pk(B)=>T, Pk(T)=>A. после этого и A и B уверены, что у них есть соответствующие ключи, однако контент уже скомпроментирован. физически передавать ключи (как делаеться во многих банковских системах), конечно, надежно, но не всегда приемлемо. есть много разнообразных изворотов, частично решающих проблему. например, введение сертификатов, участие третьего лица, которому доверяют и A и B, и которое отвечает за распространение и верификацию ключей; но там тоже проблем очень много.

кстати, в современных сетевых протоколах исключительно ассиметричная криптография в виду некоторой медлительности и ресурсоемкости используеться редко. чаще ее используют с целью аутентификации сторон и договора о симметричном сессионном ключе (например, в протоколе SSL).

[greka]

sxema otkrytogo rasprostraneniya klyuchey Diffie-Helman -a.
eto i est' standart.

[greka]

a garantom vernosti otkryutogo klyucha yavlyaetsa kakaya-nit' trusted organizaciya, tipa VerySign.

t.e. garantiruyut (t.e. mojesh' proverit', sprosiv u nix, vot chto eto oznachaet), chto ty poluchayesh' istinyy otkrytyy klyuch.

klyuchi (otkrytye) nikogda ne berutsa "na veru" - proveryaetsa eshe i ix istochnik - cherez digital signature, kotoryy podmenit' nevozmojno bez togo, chtob podmena ne byla obnarujena.

[tig]

Diffie-Hellman никак проблему аутентификации не решает. а номер стандарта назвать сможешь ?
ага, сертификат - одно из решений проблемы. единственный минус - в большом дереве его найти практически не возможно.

[greka]

Diffie-Helman b@l upomyanut mnoyu ne v svyazi s autentifikaciey, ne tak li?

"ага, сертификат - одно из решений проблемы. единственный минус - в большом дереве его найти практически не возможно."

lol

[tig]

Greka, а к чему тогда ?
а все-таки, его стандартизировали ? мне важно - не могу же дезинформировать студентов.

[greka]

Originally Posted by tig

Diffie-Hellman никак проблему аутентификации не решает. а номер стандарта назвать сможешь ?
...

RFC 2409 - The Internet Key Exchange (IKE)

Skazat', chto Diffie-Helman -ovskiy method kak-to standartizirovan - neverno, eto lish' princip.
Nikto ved' ne licenziroval dvoichnoe slojenie, ne tak li ?

A vot ispol'zovanie etogo principa uje i est' tot samyy 2409.

I'l give an intro shortcut from the specified RFC:
"1. Abstract

[MSST98] (ISAKMP) provides a framework for authentication and key
exchange but does not define them. ISAKMP is designed to be key
exchange independant; that is, it is designed to support many
different key exchanges.
...
"

[greka]

P.S. bylo by interesno (ochen' ) uznat' sxemu obmena otkrytymi klyuchami, ne yavlyayusheysya proizvodnoy (t.e. chastnym sluchaem) ot sxem@ Diffie-Helman -a.