Алгоритм шифрования данных с открытым ключом 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/ Данные, приведенные выше, не должны быть использованы в незаконных целях!

[greka]

Originally Posted by tig

greco El, а ты пробовал PKCS-ы реализовывать ? веселейшее занятие

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


как ты думаешь, почему PKI заглох ?

Что означает "PKI заглох", сорри?
Я не в курсе этой темы.

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

------------------------------------------------------
Погоди, организация в цепочки - это лишь переподписывание. Сложность организации ни при чем.
Алиса передала Бобу tulik, и подписала его своей подписью. Боб знает, что tulik - от Алисы, а не от.. Гугушика.
Далее, если Боб захочет передать tulik своему другу Jeremiah, он должен уверить друга, что tulik - от него, того самого Боба, с которым пили пиво. Т.е. - переподписать своим ключем.

Если Jeremiah не значет, кто такой Боб, он откажется открывать tulik, т.к. Талмуд запрещает открывать анонимные посылки.

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

И еще вопрос, вернее, два:
-зачем организации "создавать сотни CA"? Одного CA, роль которого будет нести ОТК организации, недостаточно?
-разве есть система доверия сертификатов, отличная от линейной?

[tig]

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

это понятно, если Алиса, Боб и кто-там-еще имеют сертификаты от одного CA. а представь, если CA разные ? например, у Алисы с Бобом - VeriSign и а у кого-там-еще - CA. как тогда верифицировать ? а если второй CA - какой-то из CA, расположенных ниже root CA-a или "братский" CA (сорри, лень в документацию лезть за точным названием) ?
-зачем организации "создавать сотни CA"? Одного CA, роль которого будет нести ОТК организации, недостаточно?
представь компанию типа Microsoft с отделениями в разных частях мира и разными отделами с разными правами доступа... не думаю, что там только один CA стоит.
отличные от линейной системы протоколами подразумеваються, точнее не ограничиваються. но я никогда таких не видел.

[darrel]

Originally Posted by greco El

2 darrel: сертификат - понятие не законодательное, в даннмо случае, сколько техническое.

Сертификат да, его использование нет. Вы фактически обсуждаете схему "trusted цertificates", которая использовалась на заре внедрения ЭЦП. Для того чтобы не возникало сомнение в том можно доверять тому или иному сесртификату используются аккредитованные сертификационные центры. Не нужно проверять цепочку, поскольку если используется сертификат аккредитованного центра, то последный гарантирует его подлинность.

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

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

Нередко проверяют на достоверность лишь последний сертификат.
Но злоумышленнику не составит труда купить за 20$ сертификат у VeriSign-а, и перерподписать все что ему нужно, а сверху заляпать еще каким-то трастед-сертификатом.

А получатель, что не догадается запросить сертификат с сервера VerySign, да? Тем более, что многие средства сами сверяют, автоматом.

[tig]

Originally Posted by darrel

А получатель, что не догадается запросить сертификат с сервера VerySign, да? Тем более, что многие средства сами сверяют, автоматом.

darrel, представь ситуацию: сервер A выдал сертификаты серверам Б и В. они, в свою очередь, выдали клинтам К(Б) и К(В). теперь если клиенты хотять верифицировать сертификаты друг друга а так же удостовериться, что у них есть общий root, к кому им обращаться ? а если серверов в дереве не 3, а больше ? или если деревья независимые, но "дружные" (то есть один из серверов в левом дереве знает сервер в правом и наоборот) ? тут и возникают проблемы по-этому технологии сверения публичных сертификатов не так сильно развиты.
кстати, VeriSign-то тоже не один такой шустрый. их как минимум 4

[darrel]

Originally Posted by tig

darrel, представь ситуацию: сервер A выдал сертификаты серверам Б и В. они, в свою очередь, выдали клинтам К(Б) и К(В). теперь если клиенты хотять верифицировать сертификаты друг друга а так же удостовериться, что у них есть общий root, к кому им обращаться ?

У PGP, например 2 или 3 сервера. Программа автоматически ищет на кажном из них. Причем, насколько я помню можно регистрировать свой сертификат или на обоих или на осдном сервере. Один у них, кажись в Европе, второй в США. Естественно, что если человек живет в Европе, то логичнее искать на европейском сервере, просто потому, что европеец следую обывательской логике зарегистрирует на европейском.

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

Ну, я думаю, что 2, 3 и даже 4 сервера не проблема, хотя минуту ил две (при нашей долбанной связи) отнимает. Мне кажется как раз развиты технологии сверения публичных сертификатов, а trusted certificates и trusted notaries уходят в прошлое.