Несимметричные алгоритмы шифрования

В середине 70-х двое ученых — Винфилд Диффи и Мартин Хеллман — описали принципы шифрования с открытыми ключами.

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

В модели криптосхемы с открытым ключом также три участника: отправитель, получатель, злоумышленник (рис. 11.3).

Задача отправителя заключается в том, чтобы по открытому каналу связи передать некоторое сообщение в защищенном виде. Получатель генерирует на своей стороне два ключа: открытый Е и закры­тый D. Закрытый ключ D (часто называемый также личным ключом) абонент должен сохранять в защищенном месте, а открытый ключ Е он может передать всем, с кем он хочет поддерживать защищенные отношения. Открытый ключ ис­пользуется для шифрования текста, но расшифровать текст можно только с по­мощью закрытого ключа. Поэтому открытый ключ передается отправителю в незащищенном виде. Отправитель, используя открытый ключ получателя, шиф­рует сообщение X и передает его получателю. Получатель расшифровывает со­общение своим закрытым ключом D.

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

Пусть абонент 1 (рис. 11.4, а) решает вести секретную переписку со своими со­трудниками на малоизвестном языке, например санскрите. Для этого он обзаво­дится санскритско-русским словарем, а всем своим абонентам посылает русско-санскритские словари. Каждый из них, пользуясь словарем, пишет сообщения на санскрите и посылает их абоненту 1, который переводит их на русский язык, пользуясь доступным только ему санскритско-русским словарем. Очевидно, что здесь роль открытого ключа Е играет русско-санскритский словарь, а роль за­крытого ключа Р — санскритско-русский словарь. Могут ли абоненты 2, 3 и 4 прочитать чужие сообщения S₂, S₃, S₄,.которые посылает каждый из них абонен­ту 1? Вообще-то нет, так как, для этого им нужен санскритско-русский словарь, обладателем которого является только абонент 1. Но теоретическая возможность этого имеется, так как затратив массу времени, можно прямым перебором со­ставить санскритско-русский словарь по русско-санскритскому словарю. Такая процедура, требующая больших временных затрат, является отдаленной анало­гией восстановления закрытого ключа по открытому.

На рис. 11.4, б показана другая схема использования открытого и закрытого клю­чей, целью которой является подтверждение авторства (аутентификация или электронная подпись) посылаемого сообщения. В этом случае поток сообщений имеет обратное направление — от абонента 1, обладателя закрытого ключа D, к его корреспондентам, обладателям открытого ключа Е. Если абонент 1 хочет аутентифицировать себя (поставить электронную подпись), то он шифрует извест­ный текст своим закрытым ключом D и передает шифровку своим корреспон­дентам. Если им удается расшифровать текст открытым ключом абонента 1, то это доказывает, что текст был зашифрован его же закрытым ключом, а значит, именно он является автором этого сообщения. Заметим, что в этом случае сооб­щения S₂, S₃, S₄, адресованные разным абонентам, не являются секретными, так как все они — обладатели одного и того же открытого ключа, с помощью которо­го они могут расшифровывать все сообщения, поступающие от абонента 1.

Если же нужна взаимная аутентификация и двунаправленный секретный обмен сообщениями, то каждая из общающихся сторон генерирует собственную пару ключей^! посылает открытый ключ своему корреспонденту.

Для того чтобы в сети все п абонентов имели возможность не только принимать зашифрованные сообщения, но и сами посылать таковые, каждый абонент дол­жен обладать своей собственной парой ключей Е и D. Всего в сети будет 2n клю­чей: n открытых ключей для шифрования и n секретных ключей для дешифри­рования. Таким образом решается проблема масштабируемости — квадратичная зависимость количества ключей от числа абонентов в симметричных алгоритмах заменяется линейной зависимостью в несимметричных алгоритмах. Исчезает и задача секретной доставки ключа. Злоумышленнику нет смысла стремиться за­владеть открытым ключом, поскольку это не дает возможности расшифровывать текст или вычислить закрытый ключ.

Хотя информация об открытом ключе не является секретной, ее нужно защи­щать от подлогов, чтобы злоумышленник под именем легального пользователя не навязал свой открытый ключ, после чего с помощью своего закрытого ключа он может расшифровывать все сообщения, посылаемые легальному пользователю и отправлять свои сообщения от его имени. Проще всего было бы распро­странять списки, связывающие имена пользователей с их открытыми ключами широковещательно, путем публикаций в средствах массовой информации (бюл­летени, специализированные журналы и т. п.). Однако при таком подходе мы снова, как и в случае с паролями, сталкиваемся с плохой масштабируемостью. Решением этой проблемы является технология цифровых сертификатов.

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

В настоящее время одним из наиболее популярных криптоалгоритмов с откры­тым ключом является криптоалгоритм RSA.

Криптоалгоритм RSA

В 1978 году трое ученых (Ривест, Шамир и Адлеман) разработали систему шиф­рования с открытыми ключами RSA (Rivest, Shamir, Adleman), полностью отве­чающую всем принципам Диффи-Хеллмана. Этот метод состоит в следующем:

1. Случайно выбираются два очень больших простых числа р и q.

2. Вычисляются два произведения n=pxq и nv=(p-l)x(q-l).

3. Выбирается случайное целое число Е, не имеющее общих сомножителей с т.

4. Находится D, такое, что DE-1 по модулю т.

5. Исходный текст, X, разбивается на блоки таким образом, чтобы 0<Х<п.

6. Для шифрования сообщения необходимо вычислить С=Х^Е по модулю п.

7. Для дешифрирования вычисляется X=C^D no модулю п.

Таким образом, чтобы зашифровать сообщение, необходимо знать пару чисел (Е, п), а чтобы Дешифрировать — пару чисел (D, п). Первая пара — это открытый ключ, а вторая — закрытый.

Зная открытый ключ (Е, п), можно вычислить значение закрытого ключа D. Не­обходимым промежуточным действием в этом преобразовании является нахож­дение чисел р и q, для чего нужно разложить на простые множители очень боль­шое число п, а на это требуется очень много времени. Именно с огромной вычислительной сложностью разложения большого числа на простые множите­ли связана высокая криптостойкость алгоритма RSA. В некоторых публикациях приводятся следующие оценки: для того чтобы найти разложение 200-значно-го числа, понадобится 4 миллиарда лет работы компьютера с быстродействием миллион операций в секунду. Однако следует учесть, что в настоящее время ак­тивно ведутся работы по совершенствованию методов разложения больших чи­сел, поэтому в алгоритме RSA стараются применять числа длиной более 200 де­сятичных разрядов.

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

В табл. 11.1 приведены некоторые сравнительные характеристики классического криптоалгоритма DES и криптоалгоритма RSA.