Алгоритм шифрования данных с открытым ключом 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]

Or Diffie-Hellman is not a part of the IPSec standard from now on :-?
)

[greka]

3-y PKCS kak-raz otnositsa k protokolu soglasovaniya klyuchey po D-H.

Chto skajesh' naschet nego?

[tig]

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

а так, например, есть еще протоколы Needham-Schroeder, Beller-Yacobi и т.д.

[acid]

Originally Posted by Obelix

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

Алгоритм протестирован, но надо ведь еще и конкретные реализации алгоритма протестировать?

[darrel]

Originally Posted by tig

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

А как может быть схема (в принципе тот же алгоритм) стандартом? Я так понял, что greco имел в виду то, что это общепринятая и единственная схема, а не стандарт в юридическом смысле. На сегодняшний день стандартов на алгоритмы, как яя понимаю, быть не может, поскольку они не патентируются и не сертифицируются, ни у нас, ни в Европе.

А чего тут тяжелого, даже я со своим гуманитарным образованием и то понял ... с третьего раза Хочешь перешлю популярный материал про ЭЦП, как раз для ленивых студентов, чтобы не мучились бедняги ... правда он величиной в 1МБ ... с картинками

[tig]

тяжелая - например, алгоритмизация поиска интересующего сертификата да и стандартов на сертификат не один.

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

[darrel]

Originally Posted by tig

тяжелая - например, алгоритмизация поиска интересующего сертификата да и стандартов на сертификат не один.

Нет, видимо мое гуманитарное образование не дает мне возможности понять что такое стандарт сертификата? В России вообще серификат только на бумажке выдают, какой там может быть стандарт? Я в первый раз слышу, что на сертификаты стандартизируются. Максимум, что можно стандартизировать, так это *сертификационные услуги*, да и то только в Европе и США, поскольку понятия sertification of services (SoS) очень новое и не везде оно еще принято. Правда в Армении я часто слышу словосочетание "сертификация сетей", но люди, которые его используют выдают желаемое за действительное.

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

Другое дело Россия - страна непуганных идиотов. В РФ ввели стандарт ЭЦП, но это полнейший маразм, поскольку это означает, что все прочие алгоритмы создания ЭЦП незаконны. Но в РФ этот стандарт был принят, насколько я знаю, под давлением ФАПСИ и РусКрипто с единственной целью монополизации рынка. Причем одним из требований стандарта, если я не ошибаюсь, является длина ключей - 56МБ, не меньше (есть кое-какая логика), не больше (полный маразм, видимо по заявкам сотрудников ГБ, они, видимо, больше взломать не могут, мощностей не хватает, а РусКрипто, видимо, больше и не делает, а поскольку все зарубежные аналоги как минимум 128, значит они нестандартные).

Если интересно постну требования директивы ЕС об аккредитации сертиф. центров и средст ЭЦП.

[tig]

я имел в виду сертификат - цифровое хранилище открытого (в некоторых случаях - закрытого) ключа и некоторой дополнительной информации о пользователе, подписанное со стороны третьего доверенного лица. тогда A вместо ключа пересылает B сертификат, из которого можно вытащить и ключ и много другой полезной информации. B же, в свою очередь, может проверить цифровую подпись доверенного лица, чтобы удостовериться, что ключи не подменили по дороге, опросить доверенное лицо на наличие такого сертификата и проверить не скомпроментирован ли он (утерян, истек срок действия, скомпроментированы ключи). это конечно все в иделе. реально же найти всю цепочку сертифицирования - задача ой ой ой. уже который год предлагаються расширения на разные сетевые протоколы с целью облегчения подобного поиска.
естественно, чтобы различные программы могли взаимодействовать друг с другом, такие сертификаты надо было стандартизировать. то есть стандартизировать их представление в памяти компьютера.
ты можешь посмотреть свои сертификаты, если откроешь IE/Tools/Internet Options/Content/Certificates/
если не ошибаюсь, в ЮЭс подобные сертификаты выдаються соответствующими организациями при наличии пасспорта.

56МБ - это мегабайты ? тогда они максималисты по полной

а на счет дыр в системах в угоду органов - это предмет постоянных споров. но дыры есть. во многих странах - законодательно подтвержденные.

[tig]

кстати, я так и не разобрался, у нас закон о ЭЦП приняли ? и если да, то с какого он в силе ?

[darrel]

Originally Posted by tig

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

Теперь понятно о чем идет речь. Систиматизировать сертификаты должен соответствующий гос орган, который ведет регистр сертификационных центров. Задача не очень простая даже на национальном уровне, но вполне выполнимая. Что же касается стандартизации сертификатов, то как мне кажется это из области далекого будущего. Сколько лет понадобилось для совместимости некоторых приложений Видовоза и МакОса? Каждый производитель будет промотировать свою технологию и пользователи будут вынуждены выбирать ту или иную ЭЦП. В иделе будут иметь 2, 3 а может и больше средст ЭЦП. Я лично в одно время так и делал, пользовался PGP и VerySign одновременно, взависимости от того кому писал и кто писал мне.

56МБ - это мегабайты ? тогда они максималисты по полной

сорри, конечно же это биты ... это я автоматически написал МБ
кстати сертификация в РФ предполагает предоставление кода программы и самого алгоритма ...

а на счет дыр в системах в угоду органов - это предмет постоянных споров. но дыры есть. во многих странах - законодательно подтвержденные.

Правда? Не слышал про "законодательно подтвержденные". Наверное юридически, т.е. судебные дела были?

У нас закона нет, есть законопроект. Скорее всего, примут до конца года.

[greka]

Ну, например, Needham-Schroeder - это Diffie-Helman с участием третьей (trusted) стороны.

Было бы интересно послушать, почему PKCS - зло?

[greka]

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

by tig: "...алгоритмизация поиска интересующего сертификата да и стандартов на сертификат не один..."

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

В одной из последних (если не ошибаюсь) реализаций OpenSSL была обнаружена ошибка касательно именно цепи сертификатов - там можно было выдать подпись злоумышленника за подпись trusted стороны.

Предполагаю, что была неверно реализована именно проверка цепи.

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

[Agregat]

A vse ravno, iirc, v Armenii ego ispol'zovat' nel'zya, tak chto vse eto erunda!

[tig]

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

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


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

[tig]

Originally Posted by darrel

Правда? Не слышал про "законодательно подтвержденные". Наверное юридически, т.е. судебные дела были?

в US есть рекомендации организации, носящей гордое название NSA, ограничивающие, например, максимальную защиту для продуктов, производящихся не для внутреннего пользования. там еще много интересных ограничений было. потом их вроде отменили. после 11 сентября некоторые опять вспомнились.