Криптографические способы защиты

Суть алгоритма (алгоритм разработан для блока данных длиной 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’=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 ЭВМ, находящихся в разных странах мира.

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

Криптографы постоянно  вели поиски более эффективных систем открытого шифрования, и в 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 одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В случае же системы, построенной с помощью алгоритма ЭльГамаля, угрозе раскрытия подвергнуты все абоненты криптографической сети. 

2.7 Сравнение основных  криптографических  методов

Метод шифрования с использованием датчика ПСЧ  наиболее часто используется в программной  реализации системы криптографической защиты данных. Это объясняется тем, что с одной стороны, он достаточно прост для программирования, а с другой стороны позволяет создавать алгоритмы с очень высокой криптостойкостью. Кроме того, эффективность данного метода шифрования достаточно высока. Системы основанные на методе шифрования с использованием датчика ПСЧ, позволяют зашифровать в секунду от нескольких десятков до сотен килобайт данных (здесь и в дальнейшем все характеристики приведены для персональных компьютеров).

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

Основным преимуществом метода DES является то, что он является стандартом. Как утверждает Национальное Бюро Стандартов США алгоритм обладает следующими свойствами;

1. высокий уровень  защиты данных против дешифрования  и возможной модификации данных;

2. простота в  понимании;

3. высокая степень  сложности, которая делает его  раскрытие дороже получаемой  при этом прибыли;

4. метод защиты  основывается на ключе и не  зависит ни от какой “секретности”  алгоритма;

5. Экономичен  в реализации и эффективен  в быстродействии.

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

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

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

Самым существенным недостатком DES специалисты признают размер ключа, который считается слишком малым. Стандарт в настоящем виде не является неуязвимым, хотя и

очень труден для  раскрытия (до сих пор не были зарегистрированы случаи дешифрования информации, зашифрованной  с использованием метода DES). Для  дешифрования информации методом подбора ключей достаточно выполнить 2⁵⁶ операций расшифрования (т.е. всего около 7? 10¹⁶ операций). Хотя в настоящее время нет аппаратуры, которая могла бы выполнить в обозримый период времени подобные вычисления, никто не гарантирует, что она не появится в будущем. Некоторые специалисты предлагают простую модификацию для устранения этого недостатка: исходный текст Р зашифровывается сначала по ключу К1, затем по ключу К2 и, наконец, по ключу К3. В результате время, требующееся для дешифрования, возрастает до 2¹⁶⁸ операций (приблизительно, до 10³⁴ операций).

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

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

Алгоритм криптографического преобразования, являющийся отечественным  стандартом и определяемый ГОСТ 28147-89, свободен от недостатков стандарта DES и в то же время обладает всеми  его преимуществами. Кроме того, в стандарт уже заложен метод, с помощью которого можно зафиксировать необнаруженную случайную или умышленную модификацию зашифрованной информации.

Однако у алгоритма  есть очень существенный недостаток, который заключается в том, что  его программная реализация очень  сложна и практически лишена всякого смысла из-за крайне низкого быстродействия. По оценкам авторов, за одну секунду на персональном компьютере может быть обработано всего лишь несколько десятков (максимально сотен) байт данных, а подобная производительность вряд ли удовлетворит кого-либо из пользователей. Хотя сейчас уже разработаны аппаратные средства, реализующие данный алгоритм криптографического преобразования данных, которые демонстрируют приемлемую производительность (около 70 Кб/с для IBM PC AT с тактовой частотой 12 Мгц), все же складывается впечатление, что разработчики алгоритма совершенно не заботились об эффективности его программной реализации и о стоимости шифрования данных.