Стандарт шифрования данных США

Для достижения потребного уровня криптостойкости реальные алгоритмы шифрования, применяемые в ИВС - общего пользования, включают многократно повторяемые шаги перестановки (транспозиции, запутывания), гаммирования и нелинейной подстановки. Классическим примером такого подхода является криптосистема DES (Data Encryption Standard), к рассмотрению которой мы переходим.

DES была разработана специалистами фирмы IBM no заказу Национального бюро стандартов США и принята в качестве федерального стандарта шифрования после освидетельствования ее Агенством национальной безопасности США в 1977 г. Несмотря на тщательное исследование и активную критику в течение всего периода ее существования и практического применения, криптосистема DES до настоящего времени считается нескомпроментированной и широко используется для реализации различных служб безопасности в ИВС общею пользования. Этому способствует доступность DES в виде аппаратных средств (так называемых плат криптографического закрытия), микропрограмм ЭВМ и элементов программного обеспечения, а также наличие разнообразных модификаций DES, ориентированных на использование в тех или иных службах безопасности. Стоимость шифровального устройства на основе DES составляет порядка 100-3000 долларов. О степени доверия к криптосистеме DES свидетельствует тот факт, что функционирующая в США система межбанковских клиринговых расчетов, обрабатывая в неделю более полумиллиона сообщений о переводах денежных средств порядка нескольких миллионов долларов каждый (при этом общая сумма переводов за неделю составляет 1,5 трлн. долларов), использует DES для защиты от несанкционированных изменений хранимых и передаваемых данных. Возможны четыре режима работы DES:

· ЕСВ (Electronic Code Book), или электронный кодоблокнот;

· СВС (Cipherblock Chaining), или сцепление блоков шифра;

· CFB (Cipher Feedback), или обратная связь по шифртексту;

· OFB (Output Feedback), или обратная связь по выходу.

Базовым является режим ЕСВ, для которого характерны разбиение открытого текста на 64-битовые блоки и их независимое шифрование при помощи одного и того же 64-битового ключа; блок шифртекста, как и соответствующий ему блок открытого текста, имеет длину 64 бита. Для шифрования используются 56 бит ключа из 64. Оставшиеся 8 бит необходимы для контроля. Обобщенная структурная схема алгоритма DES приведена на рис. 4.5. Результатом шифрования 64-битного блока открытого текста А при помощи ключа К является 64-битный шифртекст С, что принято обозначать, равенством: .

Алгоритм DES функционирует следующим образом. Вначале выполняется так называемая начальная перестановка IP входного блока А. Логика этой перестановки приведена в табл. 4.1, где обозначает номер позиции входного блока, а номер позиции, и которую поступает бит входного блока в результате перестановки.

После начальной перестановки выполняются 16 циклов шифрующих преобразований, подробно описываемых ниже, после чего следует завершающая обратная перестановка, логика которой представлена в табл.2, где обозначает номер позиции блока шифртекста, полученного в результате выполнения упомянутых 16 циклов, а - номер позиции, на которую поступает -й бит указанного блока в результате перестановки. Блок есть не что иное, как DES (А, К).

Перейдем к рассмотрению шифрующих преобразований, выполняемых внутри каждого ИЗ 16 циклов. Через и , . обозначаются, соответственно, левые и правые 32-битпые полублоки блока, являющегося входным для i-го цикла. При этом L, и R, определяются по следующим правилам: ; , где есть 32-6итовый полублок, а операция сложения по модулю 2 выполняется над битами, находящимися в идентичных позициях обоих операндов.

Рис. 4.1.Структурная схема алгоритма шифрования DES.

Логика вычисления значений представлена в виде структурной схемы, проведенной на рис 4.2. Вычисление начинается с так называемого расширения, преобразующего 32-битовой полублок в 48-битовый вектор в соответствии с таблицей 3, в которой j обозначает номер позиции в , a -номер позиции, в которую поступает j-й бит полублока . В случае, когда j-й бит "размножается" в две позиции, их номера указываются а соответствующей "клетке" через запятую.

Полученные 48 бит гаммируются с 48-битиаым вектором К, логика формирования которого рассматривается ниже. Результат гаммироваяия разбивается на восемь 6-битовых лекторов, поступающих на входы так называемых S-блоков .

Каждый S-блок выдает 4-битовый вектор, причем взаимосвязь между входными и выходными данными определяется содержимым приводимых ниже таблиц (табл.4 и табл.5.) и правилами их использования, существо которых состоит в следующем. Пусть, - 6-битовый вектор, поступающий на вход некоторого S-блока . Образуем два десятичных числа k и I, двоичная запись первого из которых есть а второго - . (Например, применительно к вектору 000110, , ), Тогда результатом работы S-блока , соответствующим входу , является 4-битовая двоичная запись десятичного числа, стоящего в j-й матрице на пересечении k-й строки и I-го столбца. (Например, при поступлении упомчнуташ вектора 000110 на вход S-блока результатом будет 14 = 1110; результатом работы S-блока при том же входном векторе будет ). Восемь 4-битовых векторов, поступающих с выходов S-блоков, образуют 32-битовый полублок, который подвергается перестановке, определяемой табличей Р, в которой по аналогии с ранее приведенными таблицами, P(i) есть номер позиции, к которую попадает i-й бит входного полублока.

Рассмотрим логику формирования ключей , , используемых для гамыироваяия в ходе выполнения соответствующих циклов шифрования. Исходный 64-битовыЙ ключ разбивается на восемь 8-битовых блоков. Восьмой бит каждого блока служит для контроля четности, который позволяет выявлять ошибки типа искажения нечетного числа битов (подобные ошибки могут возникнуть при хранении или непосредственно в процессе формирования ключей). При этом значение указанного восьмого бита представляет собой результат сложения по модулю 2 предшествующих сем к битов. Контрольные питы в процессе формирования ключей не используются.

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

Обобщенная структурная схема алгоритма формирования ключей приведена на рис.4.6

Рис. 4.2.Структурная схема алгоритма вычислений значений f(R_{i-1}, K_i).

	2,48			5,7	6,8			11,13	12,14				18,20			23,25

	24,26			29,31	30,32			35,37	36,38				42,44			1,47

После выполнения перестановки-выбора полученный 56-битовый вектор разбивается на два 28-битных вектора и .

Далее в каждом из 16 циклов над 28-битными векторами , и , полученными на предыдущем цикле, выполняется операция циклического сдвига на позиций влево (значения приведены в табл. 4.7).

Рис. 4.3. Структурная схема алгоритма формирования ключей в процессе функционирования DES.

Полученные в результате выполнения укачанной операции 28-битовые вектора и в укачанном порядке объединяются в 56-битовый вектор. Последний подвергается перестановке-выбору РС-2, в результате которой его j-й бит поступает в РС-2( j )-ю позицию формируемого 48-битового вектора, который и есть ключ . Логика перестановки-выбора РС-2 определяется табл. 4.8.

Таковы основные особенное алгоритма шифрования DES. Следует отметить, что криптостойкость DES определяется, главным образом, нелинейностью S-блоков. Однако логика, в соответствии с которой разработаны S-блоки, авторами DES не раскрыта и до сих пор неизвестна пользователям. В то же время исследование статистических свойств указанных блоков показывает, что они не являются полностью случайными. В связи с этим, среди специалистов распространена точка зрения о возможности существования "лазеек", разрушающих DES. Другим объектом критики является относительно малая длина ключа (56 бит), которая, в принципе, делает реальной так называемую "силовую атаку" на DES путем организации полного перебора всего пространства ключей. Гем не менее, вычислительных ресурсов современных ЭВМ. в том числе структур с высокой степенью параллельности (систолических массивов, конвейеров, транспьютеров и т.п.). для реализации подобной атаки пока недостаточно.

Мы до сих пор не останавливались на алгоритме дешифрования двоичных блоков, зашифрованных при помощи DES. Этот алгоритм, обозначаемый через DES"1, достаточно, очевиден: достаточно "прогнать" DES с тем же ключом в обратном направлении. При этом: , .

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

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

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

Для нейтрализации этих недостатков разработан специальный режим использования DES, называемый СВС (Cipherbiock Chaining, или сцепление блоков шифра). Обобщенная структурная схема функционирования DES в режиме СВС приведена на рис. 4.7.

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

Далее для любого логика шифрования определяется соотношением: , а логика дешифрования - соотношением , или, что то же самое .

Рис. 4.4. Структурная схема функционирования DES в режиме СВС.

Рис. 4.5. Структурная схема функционирования DES в режиме CFB.

Рис. 4.6. Структурная схема функционирования DES в режиме OFB.

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

Наряду с режимами ЕСВ и СВС, алгоритм DES используется еще в двух режимах с так называемой обратной связью. Обобщенная структурная схема использования алгоритма DES в режиме обратной связи по шифртексту (CFB) с k-битовыми блоками приведена на рис. 4.8; а в режиме обратной связи по выходу (OFB) с k-битовыми блоками - на рис. 4.9.

В отличие от режимов ЕСВ и СВС. оперирующих 64-битовыми блоками, режимы CFB и OFB оперируют k-битовыми блоками . Это, в частности, позволяет шифровать текстовые данные посимвольно (для кода EBCDIC достаточно положить , а для кода ASCII - ).

Шифрование в режиме CFB происходит следующим образом. Вначале па вход поступает случайным образом сгенерировапный 64-битовый вектор который шифруется алгоритмом DES с некоторым стандартным ключом . Левые бит результата шифрования гаммируются с левыми битами открытого текста и полученный таким образом k-битовый шифртекст поступает на дальнейшую обработку (передачу по каналу связи, хранение и т.п.). Существенно, что k-битовый вектор, гаммируемый с битами открытого текста, загружается в правых битов входного блока посредством сдвига его содержимого па позиций влево, после чего описанные операции повторяются применительно к следующим битам открытого текста и т. д. Обратим внимание на то, что упомянутый сдвиг содержимого входного блока не является циклическим, в связи с чем левые битов этого содержимого на каждом шаге как бы "выталкиваются" за пределы блока.

Процесс дешифрования в режиме СFВ аналогичен описанному и поэтому очевиден из правой половины рис.4.8.

Режим OFB отличается от режима CFB тем. что k-битовый вектор обратной связи поступает в правых битов входного блока не после гаммирования, а до него. Иными слонами, указанный вектор еще не является блоком шифртекста и, таким образом, не зависит от открытого текста. При этом DES как бы "зацикливается" сам на себя, генерируя k-битовые ключи для гаммирования с соответствующими блоками открытого текста. Это обстоятельство, как считается, снижает крипто стойкость OFB в сравнении с CFB.

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

Теоретически максимальный период повторения для DES-генератора, равный 264, применительно к доступным в настоящее время вычислительным ресурсам, по-видимому, достаточен, чтобы обеспечить приемлемую криптостойкость. Однако реальный период повторения подобных генераторов, как правило, существенно меньше максимального (в частности, по некоторым оценкам, этот период для DES находится в районе ).

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

Существенным достоинством OFB является отсутствие явления размножения искажений, имевших место при передаче шифртекста, в процессе дешифрования последнего. В то же время искажение одного бита k-битового блока шифртекста, полученного в режиме СFВ, будет влиять на k-битовые блоки открытого текста до тех пор, пока искаженный бит не будет вытолкнут за пределы входного 64-битового блока в результате последовательности сдвигов его содержимого, выполняемых в процессе дешифрования. Интересным свойством СFВ является то, что он отображает любое множество k-битовых блоков само на себя: результатом шифрования любого блока из этого множества является блок из этого же множества. Это свойство особенно важно для реализации байт-ориентированных протоколов типа канального протокола BSC, в которых допускаются только такие восьмибитовые комбинации, которые соответствуют символам кода ASCII (с контрольным битом).