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

Прежде чем перейти к изложению основных идей криптографии с

открытым ключом, рассмотрим основные недостатки систем шифрования

с симметричным – секретным ключом. Самый очевидный из них – это

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

связан с тем, что защита от подделки сообщений с помощью

имитовставки, полученной на симметричном ключе, не обеспечивает

защиту информации от подделки одним из владельцев секретного

ключа. Это приводит к т ому, что недобросовестный участник

информационного обмена может сфабриковать якобы полученное

сообщение либо отказаться от сообщения, посланного им самим.

Все эти проблемы позволяет решить криптография с открытым

ключом.

А симмет р ичные(илис от к рытым к люч ом )

криптографические системы – криптосистемы, в которых для

шифрования и расшифрования используются разные ключи, связанные

между собой некоторой зависимостью. При этом данная зависимость

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

зрения очень трудно. Один из ключей (например, ключ шифрования)

может быть сделан общедоступным, и в этом случае проблема получения

общ его сек ретного ключа для связи отпадает . Если сделать

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

можно построить систему аутентификации передаваемых сообщений.

Поскольку в большинстве случаев один ключ из пары делается

общедоступным, такие системы и получили название криптосистем с

открытым ключом.

Предположим, что имеет ся п ара преобразований Е и D,

удовлетворяющих условиям:

• для любого сообщения хвыполняется равенство D(E(x)) =x;

• E и D легко вычисляются для любых исходных данных;

• преобразования Е и D сложно обратить, то есть, зная Е и значение

Е(х), трудно определитьх, а зная D их, трудно найтиутакое, что D(y) =x.

В данном случае преобразование Е обеспечивает шифрование

информации, а D – расшифрование. Для того чтобы обеспечить

секретную связь между абонентами А и В, нужно, чтобы каждый из них

создал свою пару преобразований (Е1, D1 и E2, D2) и передал своему

корреспонденту преобразование для шифрования (рис. 3).(44)

Заш ифрованное абонентом А сообщ ение Е 2( х) смож ет

расшифровать только владелец ключа расшифрования D2 – абонент В.

В свою очередь абонент В шифрует свои сообщения с помощью

открытого ключа E1, принадлежащего А.

Недостатком систем шифрования с открытым ключом является их

относительно низкая производительность. По этой причине такие

системы, как правило, используют совместно с обычными

симметричными системами шифрования для передачи секретного ключа.

В этом случае передача сообщения хот абонента А к абоненту В

производится следующим образом. Абонент А генерирует секретный

ключ К симметричного алгоритма шифрования F и шифрует на нем

сообщение х, а затем шифрует К на открытом ключе пользователя В. По

каналу связи зашифрованное сообщение Fk(x) передается вместе с

зашифрованным ключом Е2(К). Абонент В сначала расшифровывает

ключ симметричной системы шифрования K = D2(E2(K)), а затем

расшифровывает само сообщение x = FK

-1FK(х). Такая система обмена

сообщениями позволяет избежать необходимости передачи секретного

ключа по защищенному каналу связи и в то же время воспользоваться

быстродействием систем шифрования с симметричным ключом.

RSA-криптосистема с открытым ключом

В 1978 г. трое ученых (Ривест, Шамир и Адлеман) разработали

систему шифрования с открытыми ключами RSA (Rivest, Shamir, Adleman).

Этот метод состоит в следующем.

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

2. Вычисляются два произведения n = p ⋅q и m = (p – 1)⋅(q – 1).

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

сомножителей с m.

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

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

0 < Х < n.

6. Для шифрования сообщения необходимо вычислить C = XE по

модулю n.

7. Для дешифрирования вычисляется Х = СD по модулю n.

Таким образом, чтобы зашифровать сообщение, необходимо знать

пару чисел (Е, n), а чтобы дешифрировать – пару чисел (D, n). Первая

пара – это открытый ключ, а вторая – закрытый.

Зная открытый ключ (Е, n), можно вычислить значение закрытого

ключа D. Н еобходимым п ромежут очным действием в эт ом

преобразовании является нахождение чисел р и q, для чего нужно

разложить на простые множители очень большое число n, а на это

требуется очень много времени. Именно с огромной вычислительной

сложностью разложения большого числа на простые множители связана

высокая криптостойкость алгоритма RSA. В некоторых публикациях

приводятся следующие оценки: для того чтобы найти разложение

200-значного числа, понадобится 4 миллиарда лет работы компьютера

с быстродействием миллион операций в секунду. Однако следует учесть,

что в настоящее время активно ведутся работы по совершенствованию

методов разложения больших чисел, поэтому в алгоритме RSA стараются

применять числа длиной более 200 десятичных разрядов.

Программная реализация криптоалгоритмов типа RSA значительно

сложнее и менее производительна, чем реализация классических

криптоалгоритмов типа DES. Вследствие сложности реализации

операций модульной арифметики криптоалгоритм RSA часто используют

только для шифрования небольших объемов информации, например,

для рассылки секретных ключей или в алгоритмах цифровой подписи,

а основную часть пересылаемой информации шифруют с помощью

симметричных алгоритмов.

В таблице 5 приведены некоторые сравнительные характеристики

классического криптоалгоритма DES и криптоалгоритма RSA. (таблица)(45)