Основы несимметричного шифрования. Пример

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

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

Существуют два класса криптосистем - симметричные и асимметричные. В сим­метричных схемах шифрования (классическая криптография) секретный ключ зашифровки совпадает с секретным ключом расшифровки. В асимметричных схе­мах шифрования (криптография с открытым ключом) открытый ключ зашиф­ровки не совпадает с секретным ключом расшифровки.

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

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

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

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

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

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

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

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

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

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

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

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

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

6) Для шифрования сообщения необходимо вычислить C= X^e по модулю n.

7) Для дешифрирования вычисляется x=с^d по модулю n.

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

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

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