Исследование алгоритмов криптозащиты

Алгоритм DES (Data Encryption Standard)

Алгоритм DES представляет собой блочный шифр, предназначенный для шифрования данных 64-битовыми блоками. На вход алгоритма поступает 64-битовый блок открытого текста, на выход выдается 64-битовый блок шифртекста. Длина ключа равна 56 бит. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для контроля по четности и игнорируется. Биты четности - наименьшие значащие биты в байтах ключа). Ключ, которым может служить любое 56-битовое число, можно изменить в любой момент времени. Секретность всецело определяется ключом. Ряд чисел полагаются слабыми ключами, но их можно легко избежать. На простейшем уровне алгоритм представляет комбинацию двух основных методов шифрования: рассеивания и перемешивания. Раундом DES является применение к тексту единичной комбинации этих методов (подстановка, а за ней - перестановка), зависящей от ключа. DES включает 16 раундов, одна и та же комбинация методов применяется к открытому тексту 16 раз. В алгоритме используется только стандартная арифметика и логические операции над 64-битовыми числами, поэтому он без труда реализовывался в аппаратуре второй половины семидесятых годов. Изобилие повторений в алгоритме делает его идеальным для реализации специализированными микросхемами. Первоначальные программные реализации были довольно медленны, но современные программы намного лучше.

DES оперирует 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 раундов одинаковых действий, называемых функцией f, в которых данные объединяются с ключом. После шестнадцатого раунда правая и левая половины объединяются, и алгоритм завершается заключительной перестановкой (обратной к первоначальной).

Рис. 1. Алгоритм DES

На каждом раунде (см. рис. 2) биты ключа сдвигаются, а затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов путем пере­становки с расширением, складывается операцией XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставля­ется снова. Эти четыре операции и выполняются функцией f. Затем результат исполнения функции f складывается с левой половиной с помощью еще одной операции XOR. В итоге этих действий появляется новая правая половина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 раундов алгоритма DES.

Рис. 2. Один раунд DES

Если обозначить B_i результат i-ой итерации, L_i и R_i – левую и правую половины, B_i, К_i – 48-битовый ключ для раунда i, a f - функцию, выполняющую все подстановки, перестановки и операции XOR с ключом, то раунд можно представить так:

Начальная перестановка выполняется над входным блоком еще до раунда 1 и задается фиксированной таблицей перестановки.

Таблица 1. Начальная перестановка DES

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

Первоначально 64-битовый ключ DES сокращается до 56-битового ключа отбрасы­ванием каждого восьмого бита. Эти биты используются только для контроля четности, позволяя проверять отсутствие в ключе ошибок. После извлечения 56-битового ключа, для каждого из 16 раундов DES генерируется новый 48-битовый подключ. Эти подключи K_i определяются следующим образом: 56-битовый ключ делится на две 28-битовые половины, каждая из которых сдвигаются на 1 или 2 бита в зависимости от номера раунда.

Алгоритм Generalized DES

Обобщенный алгоритм DES (Generalized DES - GDES) спроектирован для ускорения исполнения DES и повышения устойчивости алгоритма. Общий размер блока увеличился, а объем вычислений остался неизменным.

На рис. 3 показана блочная схема алгоритма GDES. Алгоритм GDES работает с блоками открытого текста переменной длины. Блоки шифрования делятся на q 32-битовых подблоков, точное число которых зависит от полного размера блока (который, по идее, может меняться, но фиксирован для конкретной реализации). В общем случае q равно размеру блока, деленному на 32.

Функция f рассчитывается один раз для каждого раунда для крайнего правого блока. Результат с помощью операции XOR объединяется со всеми остальными частями, которые затем циклически смещаются направо. Алгоритм GDES использует переменное число раундов n. В последний раунд внесено незначительное изменение, с тем, чтобы процессы зашифрования и расшифрования отличались только порядком применения подключей (точно так же, как в DES). При q = 2 и n = 16, описанный алгоритм превращается в DES.

Рис. 3. Блочная схема алгоритма GDES

Однако дифференциальный криптоанализ вскрывает GDES с q = 8 и n = 16 с помощью всего 6 подобранных открытых текстов. При использовании независимых подключей требуются 16 подобранных открытых текстов. Поэтому, несмотря на повышение скорости, проявилось катастрофическое снижение стойкости алгоритма.

Алгоритм NewDES

Алгоритм NewDES («новый DES») спроектирован в 1985 году Робертом Скоттом как возможная замена DES. Этот алгоритм - не модификация DES, как может показаться из названия. Он оперирует 64-битовыми блоками текста, но использует 120-битовый ключ. NewDES проще DES, в нем нет начальной и заключи­тельной перестановок. Все операции выполняются над целыми байтами. Блок открытого текста разделяется на восемь 1-байтовых подблоков: В0, В1.., В6, B7. Затем подблоки проходят через 17 раундов. Каждый раунд состоит из восьми этапов. На каждом этапе один из подблоков подвергается операции XOR с частью ключа (за одним исключением), заменяется другим байтом с помощью функции f, подвергается операции XOR с другим подблоком, который и заменяется результатом. 120-битовый ключ делится на 15 подблоков ключа. К0, К1,..., К13, К14. Алгоритм шифрования NewDES показан на рис. 4.

Рис. 4. Схема NewDES

Уже после седьмого раунда каждый бит блока открытого текста влияет на каждый бит шифртекста. Но в целом NewDES гораздо слабее DES.

Алогритм RSA

Алгоритм RSA предполагает, что посланное закодированное сообщение может быть прочитано адресатом и только им. В этом алгоритме используется два ключа открытый и секретный. Данный алгоритм привлекателен также в случае, когда большое число субъектов (N) должно общаться по схеме все-со-всеми. В случае симметричной схемы шифрования каждый из субъектов каким-то образом должен доставить свои ключи всем остальным участникам обмена, при этом суммарное число используемых ключей будет достаточно велико при большом значении N. Применение асимметричного алгоритма требует лишь рассылки открытых ключей всеми участниками, суммарное число ключей равно N.

Сообщение представляется в виде числа M. Шифрование осуществляется с помощью общедоступной функции f(M), и только адресату известно, как выполнить операцию f^-1. Адресат выбирает два больших простых (prime) числа p и q, которые делает секретными. Он объявляет n=pq и число d, c (d,p-1)=(d,q-1)=1 (один из возможных способов выполнить это условие, выбрать d больше чем p/2 и q/2). Шифрование производится по формуле:

f(M) º M^d mod n,

где M и f(M) оба £ n-1,как было показано, может быть вычислено за разумное время, даже если M, d и n содержит весьма большое число знаков. Адресат вычисляет M на основе M^d, используя свое знание p и q. Если
dc º_(p-1)1, то (M^d)^eº _p1.

Исходный текст M получается адресатом из зашифрованного F(M) путем преобразования: M = (F(M))^e (mod pq). Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа.

Аналогично (M^d)^e º _qM, если dc º _(q-1)1. e удовлетворяет этим двум условиям, если cd º _{(p-1) (q-1)}1.Теорема 1 гласит, что мы можем позволить e=x, когда x является решением уравнения dx + (p-1)(q-1)y = 1.

Так как (M^d)^eделимо на p и q, оно делимо и на pq, следовательно, мы можем определить M, зная M^d, вычислив его значение в степени e и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, было нельзя вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором ~10⁵⁰ комбинаций. Данная проблема изучается уже около 100 лет. RSA-алгоритм запатентован (20 сентября 1983, действует до 2000 года).

Теоретически можно предположить, что возможно выполнение операции f^-1, не вычисляя p и q. Но в любом случае задача эта не проста и разработчики считают ее трудно факторизуемой.

Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M, и мы хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно адо знать все возможные значения M_i.

Проясним использование алгоритма RSA на конкретном примере. Выбираем два простые числа p=7; q=17 (на практике эти числа во много раз длиннее). В этом случае n = p*q будет равно 119. Теперь необходимо выбрать e, выбираем e=5. Следующий шаг связан с формированием числа d так, чтобы d*e=1 mod [(p-1)(q-1)]. d=77 (использован расширенный алгоритм Эвклида). d екретный ключ, а e и n характеризуют открытый ключ. Пусть текст, который нам нужно зашифровать представляется M=19. С = M^emod n. Получаем зашифрованный текст C=66. Этот екстожет быть послан соответствующему адресату. Получатель дешифрует полученное сообщение, используя М= C^dmod n и C=66. В результате получатся M=19.

На практике общедоступные ключи могут помещаться в специальную базу данных. При необходимости послать партнеру зашифрованное сообщение можно сделать сначала запрос его открытого ключа. Получив его, можно запустить программу шифрации, а результат ее работы послать адресату. На использовании общедоступных ключей базируется и так называемая электронная подпись, которая позволяет однозначно идентифицировать отправителя. Сходные средства могут применяться для предотвращения внесения каких-либо корректив в сообщение на пути от отправителя к получателю. Быстродействующие аппаратные 512-битовые модули могут обеспечить скорость шифрования на уровне 64 кбит в сек. Готовятся ИС, способные выполнять такие операции со скоростью 1 Мбайт/сек. Разумный выбор параметра e позволяет заметно ускорить реализацию алгоритма.

Исследование алгоритмов криптозащиты

Мы поможем в написании ваших работ!