2.5.1 Стандарт DES
Одним из наиболее распространенных криптографических стандартов на шифрование данных, применяемых в США, является DES (Data Encryption Standard). Первоначально метод, лежащий в основе данного стандарта, был разработан фирмой IBM для своих целей. Он был проверен Агентством Национальной Безопасности (АНБ) США, которое не обнаружило в нем статистических или математических изъянов. Это означало, что дешифрование данных, защищенных с помощью DES, не могло быть выполнено статистическими (например, с помощью частотного словаря) или математическими (“прокручиванием” в обратном направлении) методами.
После этого метод фирмы IBM был принят в качестве федерального стандарта. Стандарт DES используется федеральными департаментами и агентствами, для защиты всех достаточно важных данных в компьютерах (исключая некоторые данные, методы защиты которых определяются специальными актами). Его применяют многие негосударственные институты, в том числе большинство банков и служб обращения денег. Оговоренный в стандарте алгоритм криптографической защиты данных опубликован для того, чтобы большинство пользователей могли использовать проверенный и апробированный алгоритм с хорошей криптостойкостью. С одной стороны, публикация алгоритма нежелательна, поскольку может привести к попыткам дешифрования закрытой информации. Но, с другой стороны, это не столь существенно (если стандарт сильный) по сравнению со слабыми методами защиты данных, используемыми государственными институтами. Иначе говоря, потери от публикации алгоритма криптографической защиты намного меньше, чем потеря от применения методов с низкой криптостойкостью. Разумеется, стандартный алгоритм шифрования данных должен обладать такими характеристиками, чтобы его опубликование не сказалось на криптостойкости.
Суть алгоритма (алгоритм разработан для блока данных длиной 64 бит) заключается в преобразовании, которое состоит из серии перестановок (правая половина блока становится левой половиной “следующего” блока), операций запутывания (из правой половины блока длиной 32 бит формируется код длиной 48 бит, а каждый бит ключа размножается и превращается в подключ длиной 48 бит) и логических операций (с помощью функций ИСКЛЮЧАЮЩЕЕ ИЛИ производится обработка кода длиной 48 бит и подключа такой же длины, затем из получившегося сегмента длиной 48 бит выбираются 32 бит и, наконец, с помощью функции ИСКЛЮЧАЮЩЕЕ ИЛИ производится совместная обработка отобранных на втором этапе 32 бит и левой половины блока длиной 32 бит). Этот процесс перестановок в половине блока, повторных операций запутывания и многократных логических операций выполняется 16 раз, так как ключ состоит из 16 бит, каждый из которых генерирует 16 подключей (за счет выполнения операций запутывания).
Недостатки метода в малой длине блока и ключа, что недостаточно для таких задач, как национальная безопасность. Свое развитие DES получил в ГОСТ 281478-89 (отечественный стандарт на шифрование данных), который увеличил длину ключа до 256 бит и допустил произвольные перестановки.
2.6 Шифры с открытым ключом
Наиболее перспективными системами криптографической защиты данных являются системы с открытым ключом. В таких системах для зашифрования данных используется один ключ, а для расшифрования другой. Первый ключ не является секретным и может быть опубликован для использования всеми пользователями системы, которые зашифровывают данные. Расшифрование данных с помощью известного ключа невозможно. Для расшифрования данных получатель зашифрованной информации использует второй ключ, который является секретным. Разумеется, ключ расшифрования не может быть определен из ключа зашифрования. Системы с открытым ключом применяются, главным образом, в системах передачи данных по линиям связи большой протяженности.
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’=SD MOD N.
5. Получатель сообщения расшифровывает его, возводя в степень Е по модулю N, так как
S=S’E MOD N=SDE MOD N.
Где под простым числом понимается такое число, которое делится только на 1 и на само себя. Взаимно простые числа - числа, которые не имеют ни одного общего делителя кроме 1.
Результат операции i mod j - остаток от целочисленного деления i на j.
Таким образом, открытым ключом служит пара чисел N и D, а секретным ключом число Е. Смысл этой системы шифрования становится понятным, если упомянуть про малую теорему Ферма, которая утверждает, что при простом числе Р и любом целом числе К, которое меньше Р, справедливо тождество
KP-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’=SD MOD N=165016813 MOD 47053=3071
Получатель расшифровывает ее с помощью секретного ключа:
S=S’E MOD N=307119837 MOD 47053=1650
Криптостойкость системы RSA основана на том, что М не может быть просто вычислена без знания простых сомножителей P и Q , а нахождение этих сомножителей из N считалась трудно разрешимой задачей. Однако недавние работы по разложению больших чисел на сомножители показали, что для этого могут быть использованы разные и даже самые неожиданные средства. Сначала авторы RSA предлагали выбрать простые числа P и Q случайно, по 50 десятичных знаков каждое. Считалось, что такие большие числа очень трудно разложить на простые сомножители при криптоанализе. Райвест полагал, что разложение на простые множители такого числа (около 130 десятичных цифр) потребует более 40 квадриллионов лет машинного времени. Но математики Ленстра из фирмы Bellcore и манасси из фирмы DEC разложили число из 155 десятичных цифр на простые сомножители всего за 6 недель, соединив для этого 1000 ЭВМ, находящихся в разных странах мира.
2.6.2 Шифр ЭльГамаля
Криптографы постоянно вели поиски более эффективных систем открытого шифрования, и в 1985 году ЭльГамаль предложил следующую схему на основе возведения в степень по модулю большого простого числа. Для этого задается большое простое число Р. Сообщения представляются целыми числами S из интервала (1, Р). Оригинальный протокол передачи сообщения выглядит в варианте Шамира, одного из авторов RSA, так:
1. Отправитель А и получатель В знают лишь Р. А генерирует случайное число Х из интервала (1, Р) и В тоже генерирует случайное число Y из того же интервала.
2. А шифрует сообщение S1=SX MOD P и посылает В.
3. В шифрует его своим ключом S2=S1Y MOD P и посылает S2 к А.
4. А “снимает” свой ключ S3=S2-X MOD P и возвращает S3 к В.
5. Получатель В расшифровывает сообщение:
S=S3-Y MOD P.
В системе ЭльГамаля большая степень защиты, чем у алгоритма RSA достигается с тем же по размеру N, что позволяет почти на порядок увеличить скорость шифрования и расшифрования. Криптостойкость системы ЭльГамаля основана на том, что можно легко вычислить степень целого числа, то есть произвести умножение его самого на себя любое число раз так же, как и при операциях с обычными числами. Однако трудно найти показатель степени, в которую нужно возвести заданное число, чтобы получить другое тоже заданное. В общем случае эта задача дискретного логарифмирования кажется более трудной, чем разложение больших чисел на простые сомножители, на основании чего можно предполагать, что сложности вскрытия систем RSA и ЭльГамаля будут сходными. С точки зрения практической реализации, как программным, так и аппаратным способом ощутимой разницы между этими двумя стандартами нет. Однако в криптостойкости они заметно различаются. Если рассматривать задачу разложения произвольного целого числа длиной в 512 бит на простые сомножители и задачу логарифмирования целых чисел по 512 бит, вторая задача, по оценкам математиков, несравненно сложнее первой. Однако есть еще одна особенность. Если в системе, построенной с помощью алгоритма RSA, криптоаналитику удалось разложить открытый ключ N одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В случае же системы, построенной с помощью алгоритма ЭльГамаля, угрозе раскрытия подвергнуты все абоненты криптографической сети.