Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 26.07.2004, 10:03   #1
Moderator
 
acid's Avatar
 
Join Date: 09 2001
Location: South Korea, Gumi
Posts: 7,699
Downloads: 102
Uploads: 34
Blog Entries: 16
Reputation: 561 | 6
Default Алгоритм шифрования данных с открытым ключом RSA

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/ Данные, приведенные выше, не должны быть использованы в незаконных целях!
Reply With Quote
Old 27.07.2004, 23:06   #2
VIP Роджер
 
darrel's Avatar
 
Join Date: 08 2002
Location: Yereven
Age: 51
Posts: 4,462
Downloads: 0
Uploads: 0
Reputation: 10 | 4
Default

Quote:
Originally Posted by acid
Криптостойкость алгоритма RSA основывается на предположении, что исключительно трудно определить секретный ключь по известному, поскольку для этого необходимо решить задачу о существовании делителей целого числа.
А разве не может быть дырки в самой программе? Т.е. не в самом алгоритме, а в его реализации?
Reply With Quote
Old 27.07.2004, 23:15   #3
Moderator
 
acid's Avatar
 
Join Date: 09 2001
Location: South Korea, Gumi
Posts: 7,699
Downloads: 102
Uploads: 34
Blog Entries: 16
Reputation: 561 | 6
Default

Думаю у этого алгоритма, как есть у многих алгоритмов кодирования/декодирования будут тестовые векторы. Таким образом можно проверить конкретную реализацию на ошибки/дыры.
Reply With Quote
Old 28.07.2004, 07:12   #4
спасибо, коллега
 
tig's Avatar
 
Join Date: 03 2003
Location: yerevan, am
Age: 38
Posts: 2,090
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

тест-векторы, конечно, есть, но они ни от чего не защищают и не гарантируют. увы.
Reply With Quote
Old 28.07.2004, 08:05   #5
панаехавший
 
Obelix's Avatar
 
Join Date: 06 2003
Location: форпост
Age: 30
Posts: 4,007
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally Posted by darrel
А разве не может быть дырки в самой программе? Т.е. не в самом алгоритме, а в его реализации?
Конечно может. Но в основном в таких программах дырки редко появляются, т.е. в самой реализации шифровального механизма дырки вряд ли появятся, но вот если все это будет как-то связано с сетью, то уже возможно многое.

>acid
Но ведь этот алгоритм довольно старый, если я конечно не ошибаюсь. И уже довольно широко используется. Думаю он уже протестирован достаточно.
Reply With Quote
Old 28.07.2004, 08:09   #6
спасибо, коллега
 
tig's Avatar
 
Join Date: 03 2003
Location: yerevan, am
Age: 38
Posts: 2,090
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

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

кстати, еще один тяжелейший вопрос - надежное распространение открытых ключей.
Reply With Quote
Old 28.07.2004, 11:37   #7
VIP Роджер
 
darrel's Avatar
 
Join Date: 08 2002
Location: Yereven
Age: 51
Posts: 4,462
Downloads: 0
Uploads: 0
Reputation: 10 | 4
Default

Quote:
Originally Posted by tig
кстати, еще один тяжелейший вопрос - надежное распространение открытых ключей.
а в чем тут, собтвенно, пороблема?
Reply With Quote
Old 28.07.2004, 11:59   #8
спасибо, коллега
 
tig's Avatar
 
Join Date: 03 2003
Location: yerevan, am
Age: 38
Posts: 2,090
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

цель защиты информации - защита данных, защита целостности данных и верификация сторон. последняя задача как раз одна из самых нетривиальных. насколько я знаю, каких-либо окончательных решений для нее не предложено.
смотри - если 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).
Reply With Quote
Old 28.07.2004, 13:15   #9
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

sxema otkrytogo rasprostraneniya klyuchey Diffie-Helman -a.
eto i est' standart.
Reply With Quote
Old 28.07.2004, 13:17   #10
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

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.
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/
Reply With Quote
Old 28.07.2004, 13:25   #11
спасибо, коллега
 
tig's Avatar
 
Join Date: 03 2003
Location: yerevan, am
Age: 38
Posts: 2,090
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Diffie-Hellman никак проблему аутентификации не решает. а номер стандарта назвать сможешь ?
ага, сертификат - одно из решений проблемы. единственный минус - в большом дереве его найти практически не возможно.
Reply With Quote
Old 28.07.2004, 13:30   #12
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

Diffie-Helman [email protected] upomyanut mnoyu ne v svyazi s autentifikaciey, ne tak li?

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

lol
Reply With Quote
Old 28.07.2004, 13:34   #13
спасибо, коллега
 
tig's Avatar
 
Join Date: 03 2003
Location: yerevan, am
Age: 38
Posts: 2,090
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Greka, а к чему тогда ?
а все-таки, его стандартизировали ? мне важно - не могу же дезинформировать студентов.
Reply With Quote
Old 28.07.2004, 14:00   #14
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

Quote:
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.
...

"
Reply With Quote
Old 28.07.2004, 14:02   #15
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

P.S. bylo by interesno (ochen' ) uznat' sxemu obmena otkrytymi klyuchami, ne yavlyayusheysya proizvodnoy (t.e. chastnym sluchaem) ot [email protected] Diffie-Helman -a.
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 13:58.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.