View Full Version : Алгоритм шифрования данных с открытым ключом 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/ Данные, приведенные выше, не должны быть использованы в незаконных целях!
darrel
Jul 27, 2004, 22:06
Криптостойкость алгоритма RSA основывается на предположении, что исключительно трудно определить секретный ключь по известному, поскольку для этого необходимо решить задачу о существовании делителей целого числа.
А разве не может быть дырки в самой программе? Т.е. не в самом алгоритме, а в его реализации?
Думаю у этого алгоритма, как есть у многих алгоритмов кодирования/декодирования будут тестовые векторы. Таким образом можно проверить конкретную реализацию на ошибки/дыры.
тест-векторы, конечно, есть, но они ни от чего не защищают и не гарантируют. увы.
Obelix
Jul 28, 2004, 07:05
А разве не может быть дырки в самой программе? Т.е. не в самом алгоритме, а в его реализации?
Конечно может. Но в основном в таких программах дырки редко появляются, т.е. в самой реализации шифровального механизма дырки вряд ли появятся, но вот если все это будет как-то связано с сетью, то уже возможно многое.
>acid
Но ведь этот алгоритм довольно старый, если я конечно не ошибаюсь. И уже довольно широко используется. Думаю он уже протестирован достаточно.
алгоритм-то хороший, только уже недостаточный. нет, пока брют-форс атаки не проходят, но этот страшный день не за горами. плюс вся эта истерия про квантовые компьютеры...
а атак на реализацию - зашибись. ломают как только не лень :)
кстати, еще один тяжелейший вопрос - надежное распространение открытых ключей.
darrel
Jul 28, 2004, 10:37
кстати, еще один тяжелейший вопрос - надежное распространение открытых ключей.
а в чем тут, собтвенно, пороблема?
цель защиты информации - защита данных, защита целостности данных и верификация сторон. последняя задача как раз одна из самых нетривиальных. насколько я знаю, каких-либо окончательных решений для нее не предложено.
смотри - если 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).
sxema otkrytogo rasprostraneniya klyuchey Diffie-Helman -a.
eto i est' standart.
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.
Diffie-Hellman никак проблему аутентификации не решает. а номер стандарта назвать сможешь ? :)
ага, сертификат - одно из решений проблемы. единственный минус - в большом дереве его найти практически не возможно.
Diffie-Helman b@l upomyanut mnoyu ne v svyazi s autentifikaciey, ne tak li?
"ага, сертификат - одно из решений проблемы. единственный минус - в большом дереве его найти практически не возможно."
lol
Greka, а к чему тогда ? :)
а все-таки, его стандартизировали ? мне важно - не могу же дезинформировать студентов.
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.
...
"
P.S. bylo by interesno (ochen' ;)) uznat' sxemu obmena otkrytymi klyuchami, ne yavlyayusheysya proizvodnoy (t.e. chastnym sluchaem) ot sxem@ Diffie-Helman -a.
Or Diffie-Hellman is not a part of the IPSec standard from now on :-?
:))
3-y PKCS kak-raz otnositsa k protokolu soglasovaniya klyuchey po D-H.
Chto skajesh' naschet nego?
а что про PKCS говорить ? они - неизбежное зло :)
я и не спорю, большинство современных протоколов опираеться на Диффи-Хэллмана. просто думал если есть какой-то соответствующий стандарт, то легче отсылать студентов к нему, чем заставлять читать тяжелые книжки :)
а так, например, есть еще протоколы Needham-Schroeder, Beller-Yacobi и т.д. :)
>acid
Но ведь этот алгоритм довольно старый, если я конечно не ошибаюсь. И уже довольно широко используется. Думаю он уже протестирован достаточно.
Алгоритм протестирован, но надо ведь еще и конкретные реализации алгоритма протестировать? :)
darrel
Jul 28, 2004, 15:40
просто думал если есть какой-то соответствующий стандарт, то легче отсылать студентов к нему, чем заставлять читать тяжелые книжки :)
А как может быть схема (в принципе тот же алгоритм) стандартом? Я так понял, что greco имел в виду то, что это общепринятая и единственная схема, а не стандарт в юридическом смысле. На сегодняшний день стандартов на алгоритмы, как яя понимаю, быть не может, поскольку они не патентируются и не сертифицируются, ни у нас, ни в Европе.
А чего тут тяжелого, даже я со своим гуманитарным образованием и то понял ... с третьего раза :rolleyes: Хочешь перешлю популярный материал про ЭЦП, как раз для ленивых студентов, чтобы не мучились бедняги :D ... правда он величиной в 1МБ ... с картинками :D
тяжелая - например, алгоритмизация поиска интересующего сертификата :) да и стандартов на сертификат не один.
лучше бедненьких тяжелыми книжками попотчую, есть у меня пара таких по полторы тысячи страниц. да стандартиками интересными на закуску... правда, пока ни одного не было, чтобы больше 10 страниц прочел :)
darrel
Jul 28, 2004, 17:31
тяжелая - например, алгоритмизация поиска интересующего сертификата :) да и стандартов на сертификат не один.
Нет, видимо мое гуманитарное образование не дает мне возможности понять что такое стандарт сертификата? В России вообще серификат только на бумажке выдают, какой там может быть стандарт? Я в первый раз слышу, что на сертификаты стандартизируются. Максимум, что можно стандартизировать, так это *сертификационные услуги*, да и то только в Европе и США, поскольку понятия sertification of services (SoS) очень новое и не везде оно еще принято. Правда в Армении я часто слышу словосочетание "сертификация сетей", но люди, которые его используют выдают желаемое за действительное.
Нет, конечно сертификаты разные бывают, но стандартов на них, насколько я знаю нет и не предвидется. Вообще в Европе существует понятие аккредитации сертификационных центров, т.е. проверка на соответствие требованиям закона об эл. подписи. Процедура аккредитации включает и проверку средст ЭЦП на соответствие требованиям того же закона. Стандартов, насколько я знаю, нет.
Другое дело Россия - страна непуганных идиотов. В РФ ввели стандарт ЭЦП, но это полнейший маразм, поскольку это означает, что все прочие алгоритмы создания ЭЦП незаконны. Но в РФ этот стандарт был принят, насколько я знаю, под давлением ФАПСИ и РусКрипто с единственной целью монополизации рынка. Причем одним из требований стандарта, если я не ошибаюсь, является длина ключей - 56МБ, не меньше (есть кое-какая логика), не больше (полный маразм, видимо по заявкам сотрудников ГБ, они, видимо, больше взломать не могут, мощностей не хватает, а РусКрипто, видимо, больше и не делает, а поскольку все зарубежные аналоги как минимум 128, значит они нестандартные).
Если интересно постну требования директивы ЕС об аккредитации сертиф. центров и средст ЭЦП.
я имел в виду сертификат - цифровое хранилище открытого (в некоторых случаях - закрытого) ключа и некоторой дополнительной информации о пользователе, подписанное со стороны третьего доверенного лица. тогда A вместо ключа пересылает B сертификат, из которого можно вытащить и ключ и много другой полезной информации. B же, в свою очередь, может проверить цифровую подпись доверенного лица, чтобы удостовериться, что ключи не подменили по дороге, опросить доверенное лицо на наличие такого сертификата и проверить не скомпроментирован ли он (утерян, истек срок действия, скомпроментированы ключи). это конечно все в иделе. реально же найти всю цепочку сертифицирования - задача ой ой ой. уже который год предлагаються расширения на разные сетевые протоколы с целью облегчения подобного поиска.
естественно, чтобы различные программы могли взаимодействовать друг с другом, такие сертификаты надо было стандартизировать. то есть стандартизировать их представление в памяти компьютера.
ты можешь посмотреть свои сертификаты, если откроешь IE/Tools/Internet Options/Content/Certificates/
если не ошибаюсь, в ЮЭс подобные сертификаты выдаються соответствующими организациями при наличии пасспорта.
56МБ - это мегабайты ? тогда они максималисты по полной :)
а на счет дыр в системах в угоду органов - это предмет постоянных споров. но дыры есть. во многих странах - законодательно подтвержденные.
кстати, я так и не разобрался, у нас закон о ЭЦП приняли ? и если да, то с какого он в силе ?
darrel
Jul 28, 2004, 21:00
естественно, чтобы различные программы могли взаимодействовать друг с другом, такие сертификаты надо было стандартизировать. то есть стандартизировать их представление в памяти компьютера.
Теперь понятно о чем идет речь. Систиматизировать сертификаты должен соответствующий гос орган, который ведет регистр сертификационных центров. Задача не очень простая даже на национальном уровне, но вполне выполнимая. Что же касается стандартизации сертификатов, то как мне кажется это из области далекого будущего. Сколько лет понадобилось для совместимости некоторых приложений Видовоза и МакОса? Каждый производитель будет промотировать свою технологию и пользователи будут вынуждены выбирать ту или иную ЭЦП. В иделе будут иметь 2, 3 а может и больше средст ЭЦП. Я лично в одно время так и делал, пользовался PGP и VerySign одновременно, взависимости от того кому писал и кто писал мне.
56МБ - это мегабайты ? тогда они максималисты по полной :)
сорри, конечно же это биты ... это я автоматически написал МБ
кстати сертификация в РФ предполагает предоставление кода программы и самого алгоритма ... :D
а на счет дыр в системах в угоду органов - это предмет постоянных споров. но дыры есть. во многих странах - законодательно подтвержденные.
Правда? Не слышал про "законодательно подтвержденные". Наверное юридически, т.е. судебные дела были?
У нас закона нет, есть законопроект. Скорее всего, примут до конца года.
Ну, например, Needham-Schroeder - это Diffie-Helman с участием третьей (trusted) стороны.
Было бы интересно послушать, почему PKCS - зло?
2 darrel: сертификат - понятие не законодательное, в даннмо случае, сколько техническое. ;)
by tig: "...алгоритмизация поиска интересующего сертификата да и стандартов на сертификат не один..."
Постольку поскольку если сертификатов несколько, то они могут образовать лишь цепь - т.е. нет ответвлений и пр.
Это означает, что "поиск сертификата" есть просто просмотр линейного списка сертификатов.
В одной из последних (если не ошибаюсь) реализаций OpenSSL была обнаружена ошибка касательно именно цепи сертификатов - там можно было выдать подпись злоумышленника за подпись trusted стороны.
Предполагаю, что была неверно реализована именно проверка цепи.
Нередко проверяют на достоверность лишь последний сертификат.
Но злоумышленнику не составит труда купить за 20$ сертификат у VeriSign-а, и перерподписать все что ему нужно, а сверху заляпать еще каким-то трастед-сертификатом.
Agregat
Jul 29, 2004, 09:53
A vse ravno, iirc, v Armenii ego ispol'zovat' nel'zya, tak chto vse eto erunda! :)
greco El, а ты пробовал PKCS-ы реализовывать ? веселейшее занятие :)
цепи сертификатов - идеальный случай. а что скажешь об организации с парой сотен CA, которым совсем не обязательно наследоваться друг от друга, уж тем более организовываться в цепочки ?
как ты думаешь, почему PKI заглох ?
Правда? Не слышал про "законодательно подтвержденные". Наверное юридически, т.е. судебные дела были?в US есть рекомендации организации, носящей гордое название NSA, ограничивающие, например, максимальную защиту для продуктов, производящихся не для внутреннего пользования. там еще много интересных ограничений было. потом их вроде отменили. после 11 сентября некоторые опять вспомнились.
greco El, а ты пробовал PKCS-ы реализовывать ? веселейшее занятие :)
цепи сертификатов - идеальный случай. а что скажешь об организации с парой сотен CA, которым совсем не обязательно наследоваться друг от друга, уж тем более организовываться в цепочки ?
как ты думаешь, почему PKI заглох ?
Что означает "PKI заглох", сорри?
Я не в курсе этой темы.
"...цепи сертификатов - идеальный случай. а что скажешь об организации с парой сотен CA, которым совсем не обязательно наследоваться друг от друга, уж тем более организовываться в цепочки ?"
------------------------------------------------------
Погоди, организация в цепочки - это лишь переподписывание. Сложность организации ни при чем.
Алиса передала Бобу tulik, и подписала его своей подписью. Боб знает, что tulik - от Алисы, а не от.. Гугушика.
Далее, если Боб захочет передать tulik своему другу Jeremiah, он должен уверить друга, что tulik - от него, того самого Боба, с которым пили пиво. Т.е. - переподписать своим ключем.
Если Jeremiah не значет, кто такой Боб, он откажется открывать tulik, т.к. Талмуд запрещает открывать анонимные посылки.
Как я уже говорил выше, вместо задачи:
просмотреть всю цепь; если хоть один нежелательный (вендор из черного списка, напр.), запретить подписанный продукт, обычно проверяют последнюю подпись, считая, что цепочка валидна, и, наверное, это правильно.
И еще вопрос, вернее, два:
-зачем организации "создавать сотни CA"? Одного CA, роль которого будет нести ОТК организации, недостаточно?
-разве есть система доверия сертификатов, отличная от линейной?
одно время компании, разрабатывающие PKI росли как на грибах. тогда же создавались разнообразные протоколы для ввдения инфраструктуры PKI в жизнь. а потом все как-то само собой исчезло. сейчас PKI занимаеться всего пара коммерческих компаний. остальные же предпочитают использовать сертификаты, не сильно расширяя их возможности.
это понятно, если Алиса, Боб и кто-там-еще имеют сертификаты от одного CA. а представь, если CA разные ? например, у Алисы с Бобом - VeriSign и а у кого-там-еще - CA. как тогда верифицировать ? а если второй CA - какой-то из CA, расположенных ниже root CA-a или "братский" CA (сорри, лень в документацию лезть за точным названием) ?
-зачем организации "создавать сотни CA"? Одного CA, роль которого будет нести ОТК организации, недостаточно?
представь компанию типа Microsoft с отделениями в разных частях мира и разными отделами с разными правами доступа... не думаю, что там только один CA стоит.
отличные от линейной системы протоколами подразумеваються, точнее не ограничиваються. но я никогда таких не видел.
darrel
Jul 29, 2004, 13:14
2 darrel: сертификат - понятие не законодательное, в даннмо случае, сколько техническое. ;)
Сертификат да, его использование нет. Вы фактически обсуждаете схему "trusted цertificates", которая использовалась на заре внедрения ЭЦП. Для того чтобы не возникало сомнение в том можно доверять тому или иному сесртификату используются аккредитованные сертификационные центры. Не нужно проверять цепочку, поскольку если используется сертификат аккредитованного центра, то последный гарантирует его подлинность.
Кстати схема, которую вы обсуждаете А получил от Б подпись с сертификатом С возникла на на заре и не в разгар информационных технологий, а гораздо раньше, в древнеримском праве. Называется это институт гарантов. Я хочу дать в долг А и спрашиваю у С можно ли ему доверять. А хочет взять у меня в долг, но должен мне оставить залог и он спрашивает у того же С, которому тоже доверяет, можно ли мне доверить залог. может быть та же цепочка, поскольку я могу доверять С, а А может доверять Д, который доверяет С ... и т.е. Так оно и было, пока не появились банки, ломбарды и нотариусы. Как только появилисть институты гарантирующие исполнение обязательств все эти цепочки стали ненужнымы.
Тоже самое и с сертификатами, если есть организация, которая прошла аккредитацию и получила "знак качества", то всего-то надо сверить полученный сертификат (ну и открытый ключ, разумеется) с том, что хранится в этой самой организации. Лично у меня на это уходят секунды. И зачем надо использовать различные сертификаты, если можно пользоваться одной, двумя или максимум тремя технологиями? Тем более, что стоимость таких средст - копейки.
Нередко проверяют на достоверность лишь последний сертификат.
Но злоумышленнику не составит труда купить за 20$ сертификат у VeriSign-а, и перерподписать все что ему нужно, а сверху заляпать еще каким-то трастед-сертификатом.
А получатель, что не догадается запросить сертификат с сервера VerySign, да? Тем более, что многие средства сами сверяют, автоматом.
А получатель, что не догадается запросить сертификат с сервера VerySign, да? Тем более, что многие средства сами сверяют, автоматом.
darrel, представь ситуацию: сервер A выдал сертификаты серверам Б и В. они, в свою очередь, выдали клинтам К(Б) и К(В). теперь если клиенты хотять верифицировать сертификаты друг друга а так же удостовериться, что у них есть общий root, к кому им обращаться ? а если серверов в дереве не 3, а больше ? или если деревья независимые, но "дружные" (то есть один из серверов в левом дереве знает сервер в правом и наоборот) ? тут и возникают проблемы :) по-этому технологии сверения публичных сертификатов не так сильно развиты.
кстати, VeriSign-то тоже не один такой шустрый. их как минимум 4 :)
darrel
Jul 29, 2004, 19:19
darrel, представь ситуацию: сервер A выдал сертификаты серверам Б и В. они, в свою очередь, выдали клинтам К(Б) и К(В). теперь если клиенты хотять верифицировать сертификаты друг друга а так же удостовериться, что у них есть общий root, к кому им обращаться ?
У PGP, например 2 или 3 сервера. Программа автоматически ищет на кажном из них. Причем, насколько я помню можно регистрировать свой сертификат или на обоих или на осдном сервере. Один у них, кажись в Европе, второй в США. Естественно, что если человек живет в Европе, то логичнее искать на европейском сервере, просто потому, что европеец следую обывательской логике зарегистрирует на европейском.
а если серверов в дереве не 3, а больше ? или если деревья независимые, но "дружные" (то есть один из серверов в левом дереве знает сервер в правом и наоборот) ? тут и возникают проблемы :) по-этому технологии сверения публичных сертификатов не так сильно развиты.
кстати, VeriSign-то тоже не один такой шустрый. их как минимум 4 :)
Ну, я думаю, что 2, 3 и даже 4 сервера не проблема, хотя минуту ил две (при нашей долбанной связи) отнимает. Мне кажется как раз развиты технологии сверения публичных сертификатов, а trusted certificates и trusted notaries уходят в прошлое.
vBulletin® v3.6.8, Copyright ©2000-2008, Jelsoft Enterprises Ltd.