Шифры с открытым ключом

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

2.6.1 Шифр Райвеста - Шамира - Алдемана

Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году так называемая система RSA. Ее название происходит от первых букв фамилий авторов Rivest, Shamir и Aldeman, которые придумали ее во время совместных исследований в массачусетском технологическом институте в 1977 году. Она основана на трудности разложения очень больших целых чисел на простые сомножители. Международная сеть электронного перечисления платежей SWIFT уже требует от банковских учреждений, пользующихся ее услугами, применения именно этой криптографической системы. Алгоритм ее работает так :

1. Отправитель выбирает два очень больших простых числа P и Q и вычисляет два произведения N=PQ и

M=(P-1)(Q-1).

2. Затем он выбирает случайное целое число D, взаимно простое с М, и вычисляет Е, удовлетворяющее условию

DE=1 MOD M.

3. После этого он публикует D и N как свой открытый ключ шифрования, сохраняя Е как закрытый ключ.

4. Если S - сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале (1,N), то оно превращается в шифровку возведением в степень D по модулю N и отправляется получателю

S’=S^D MOD N.

5. Получатель сообщения расшифровывает его, возводя в степень Е по модулю N, так как

S=S’^E MOD N=S^DE MOD N.

Где под простым числом понимается такое число, которое делится только на 1 и на само себя. Взаимно простые числа - числа, которые не имеют ни одного общего делителя кроме 1.

Результат операции i mod j - остаток от целочисленного деления i на j.

Таким образом, открытым ключом служит пара чисел N и D, а секретным ключом число Е. Смысл этой системы шифрования становится понятным, если упомянуть про малую теорему Ферма, которая утверждает, что при простом числе Р и любом целом числе К, которое меньше Р, справедливо тождество

K^P-1=1 MOD P.

Эта теорема позволяет определять, является ли какое-либо число простым или же составным.

Например выберем (для простоты малые) простые числа Р=211 и Q=223. В этом случае N=47053 и М=46620. Выберем открытый ключ шифрования D=16813 и вычислим секретный ключ расшифрования Е=19837. Теперь, взяв за сообщение название метода RSA, переведем его в число. Для этого будем считать букву R равной 18, S равной 19, А раной 1 по порядковому номеру их положения в английском алфавите. На представление каждой буквы отведем по 5 бит числа, представляющего открытый текст. В этом случае слову RSA соответствует следующее число:

S=((1*32)+19)*32+18=1650

С помощью открытого ключа получаем шифровку:

S’=S^D MOD N=1650¹⁶⁸¹³ MOD 47053=3071

Получатель расшифровывает ее с помощью секретного ключа:

S=S’^E MOD N=3071¹⁹⁸³⁷ MOD 47053=1650

Криптостойкость системы RSA основана на том, что М не может быть просто вычислена без знания простых сомножителей P и Q , а нахождение этих сомножителей из N считалась трудно разрешимой задачей. Однако недавние работы по разложению больших чисел на сомножители показали, что для этого могут быть использованы разные и даже самые неожиданные средства. Сначала авторы RSA предлагали выбрать простые числа P и Q случайно, по 50 десятичных знаков каждое. Считалось, что такие большие числа очень трудно разложить на простые сомножители при криптоанализе. Райвест полагал, что разложение на простые множители такого числа (около 130 десятичных цифр) потребует более 40 квадриллионов лет машинного времени. Но математики Ленстра из фирмы Bellcore и манасси из фирмы DEC разложили число из 155 десятичных цифр на простые сомножители всего за 6 недель, соединив для этого 1000 ЭВМ, находящихся в разных странах мира.

Шифр ЭльГамаля

Криптографы постоянно вели поиски более эффективных систем открытого шифрования, и в 1985 году ЭльГамаль предложил следующую схему на основе возведения в степень по модулю большого простого числа. Для этого задается большое простое число Р. Сообщения представляются целыми числами S из интервала (1, Р). Оригинальный протокол передачи сообщения выглядит в варианте Шамира, одного из авторов RSA, так:

1. Отправитель А и получатель В знают лишь Р. А генерирует случайное число Х из интервала (1, Р) и В тоже генерирует случайное число Y из того же интервала.

2. А шифрует сообщение S₁=S^X MOD P и посылает В.

3. В шифрует его своим ключом S₂=S₁^Y MOD P и посылает S₂ к А.

4. А “снимает” свой ключ S₃=S₂^-X MOD P и возвращает S₃ к В.

5. Получатель В расшифровывает сообщение:

S=S₃^-Y MOD P.

В системе ЭльГамаля большая степень защиты, чем у алгоритма RSA достигается с тем же по размеру N, что позволяет почти на порядок увеличить скорость шифрования и расшифрования. Криптостойкость системы ЭльГамаля основана на том, что можно легко вычислить степень целого числа, то есть произвести умножение его самого на себя любое число раз так же, как и при операциях с обычными числами. Однако трудно найти показатель степени, в которую нужно возвести заданное число, чтобы получить другое тоже заданное. В общем случае эта задача дискретного логарифмирования кажется более трудной, чем разложение больших чисел на простые сомножители, на основании чего можно предполагать, что сложности вскрытия систем RSA и ЭльГамаля будут сходными. С точки зрения практической реализации, как программным, так и аппаратным способом ощутимой разницы между этими двумя стандартами нет. Однако в криптостойкости они заметно различаются. Если рассматривать задачу разложения произвольного целого числа длиной в 512 бит на простые сомножители и задачу логарифмирования целых чисел по 512 бит, вторая задача, по оценкам математиков, несравненно сложнее первой. Однако есть еще одна особенность. Если в системе, построенной с помощью алгоритма RSA, криптоаналитику удалось разложить открытый ключ N одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В случае же системы, построенной с помощью алгоритма ЭльГамаля, угрозе раскрытия подвергнуты все абоненты криптографической сети.