Математические основы криптологии и криптографические методы и средс

В этом случае для модификации данных могут быть использо­ ваны пары взаимно обратных операций, такие как сложение и вычи­ тание в пределах разрядной сетки блоков или умножение и деление по модулю простого числа. Мы не будем подробно рассматривать необходимые свойства, которыми должны обладать операции этой пары. Мы просто отметим, что они должны быть подобны перечис­ ленным выше парам. Предположим, например, что используется па­ ра операций « i» и «^» - скажем, сложение и вычитание в пределах разрядной сетки чисел, определенные следующим образом:

H ± L (H+L) mod 2т и Н < Ь (,H-L) mod 2т

В этом случае процедуры модификации половин шифруемого блока и функция выработки инварианта могут быть следующими:

Н'=Н*Г, L’=£*Г, J(H,L)=H^L, Н'=Н*Г, L =Ь*Г, J(H,L)=H*L, Н'=Н*Г, Г =L±Г, J(H,L)=H*L, Н'=Н*Г, П=ЫТ, J(H,L)=H*L,

Иными словами, для каждой пары операций с указанными свой­ ствами возможны четыре варианта их использования для выполне­ ния шага шифрования. Общим в этих четырех вариантах является то, что они исчерпывают все случаи, в которых операция вычитания (или ее аналог из использованной пары операций) присутствуют в уравнениях преобразования нечетное число раз, а операция сложе­ ния (или ее аналог) - четное. Можно разделить модифицируемые части блока на «зоны» согласованным образом, так, что каждому вы­ деленному фрагменту в одной части будет взаимно однозначно соот­ ветствовать фрагмент такого же размера в другой части. В этом слу­ чае для каждой пары фрагментов можно использовать свою пару операций для модификации фрагментов и выработки инварианта:

H =(H\JT2,..,H K),

L= (L\,L2,...,LK),

Г= (Г1,Г2,..., Гк),

Рис. 30. Способ построе­ ния раунда шифрования в шифрующих сетях общего типа с использованием опе­ рации ИСКЛЮЧАЮЩЕГО

ИЛИ

где для	всех к - 1 , 2	К	справедливо	\Нк\= \Lk\ = |	Г*| = |/*| = г*.
В этом	случае модификация		фрагментов	и выработка	инварианта
осуществляется по следующим формулам:

Н'к = Н кк г к,

L'k - Lkk Гь

J'k = H kk L*.

где к и к - пара взаимно обратных операций над блоками размера zk бит. Понятно, что в рамках применения указанных двух операций к фрагментам данных независимо от других фрагментов может быть использована любая из четырех возможных вышеприведенных схем. При этом, однако, указанное деление на фрагменты не должно затра­ гивать выработки модифицирующего значения (Г) из инварианта (J) с использованием раундового ключевого элемента. Характер зависи­ мости второго от первого должен в полной мере соответствовать принципам перемешивания и рассеивания - все биты Г должны за­ висеть от всех битов /, и характер этой зависимости должен быть как можно более сложным и запутанным.

Как всегда, особый случай возникает при использовании опера­ ции побитового ИСКЛЮЧАЮЩЕГО ИЛИ, так как она является об­ ратной самой себе. В этом случае вместо четырех возможных вари­ антов комбинирования использования мы получаем всего один:

f f = H е г , L' = L ФГ, J(L,H) = Н® L.

Именно такой инвариант использует­ ся в известном шифре IDEA. Раунд шифра стандартной архитектуры при использова­ нии для получения инварианта операции побитового ИСКЛЮЧАЮЩЕГО ИЛИ вы­ глядит так, как показано ниже на рис. 30.

Очевидно, что смежные раунды шиф­ ра должны использовать различные инва­ рианты или должны быть отделены друг

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

Другими словами, инварианты смежных раундов в общей шиф­ рующей сети должны как можно меньше походить друг на друга. Если между ними значение частей блока модифицируется с исполь­ зованием ключевых элементов, операция, используемая для этого, должна как можно сильнее отличаться от операции комбинирования данных с модифицирующим блоком в раунде. Даже для различных операций одной и той же аддитивной группы отличий может ока­ заться недостаточно для получения нужной стойкости. Хорошим вы­ ходом в такой ситуации является использование операций иного ти­ па, например мультипликативных. Именно такой подход реализован в уже упоминавшемся выше шифре IDEA. Понятно, что использова­ ние операции умножения может сильно снизить эффективность реа­ лизации алгоритма, особенно на относительно несложных микро­ процессорах, микроконтроллерах и однокристальных ЭВМ. Вот по­ чему данный тип шифров является скорее экзотикой, чем распро­ страненным явлением, имеется всего один широко известный и ис­ пользуемый представитель этого класса шифров - IDEA. В качестве альтернативы использованию мультипликативных операций для межраундовых модификаций шифруемого блока можно предложить

комбинирование с ключевым элементом с помощью более простой операции аддитивной группы с последующим выполнением подста­

новок.

Шифр рассмотренной архитектуры имеет структуру, изображенную на рис. 31. На этом рассмотрение данной темы закон­ чим, в заключение подведем итог:

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

2. В качестве «строительных элемен­ тов» шифров используются битовые пере­ становки, замены (подстановки) в битовых

группах, арифметические и логические опе­

1

Fn-1 К >-л-1 рации. При этом наибольшее перемешива­

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

Jличаются друг от друга.

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

t r

Рис. 31. Обобщен­ ная шифрующая сеть с использова­ нием операции по­ битового ИСКЛЮ­ ЧАЮЩЕГОИЛИ для выработки инварианта и модификации блока на раунде

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

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

5.Наиболее простой и популярный способ создать инвариантоставлять часть шифруемого блока неизменной. В этом случае для

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

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

7.Для использования на раундах шифрования обычно требуется больше ключевой информации, чем содержится в ключе шифрования. Для выработки нужного объема ключевой информации для после­ дующего ее применения в раундах используют различные схемы, от самых простых - повторного использования одних и тех же фраг­ ментов ключа, как в ГОСТе, до наиболее сложных - выработки клю­ чевых элементов с использованием тех же самых шифрующих пре­ образований, что используются при шифровании, как в шифре BLOWF1SH.

1.5.4. Вопросы и задачи для самоконтроля

1.Что понимается под простым шифрующим преобразованием?

2.Назовите группы простых шифров.

3.Рационально ли при каскадировании комбинировать две опе­ рации, принадлежащие одной группе?

4.Перечислите обратимые процедуры зашифровывания.

5.Приведите схему шифрующего преобразования с линейной структурой.

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

7.Приведите схемы стандартного шифрующего преобразования (прямого и обратного).

8.Определите инвариант стандартного шифрующего преобразо­

вания.

9.Опишите способ построения раунда шифрования в шифрую­ щих сетях общего типа.

2. КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ И СРЕДСТВА ОБЕСПЕЧЕНИЯ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ________________

2.1.СИНТЕЗ И АНАЛИЗ КРИПТОГРАФИЧЕСКИХ АЛГОРИТМОВ

2.1.1.Криптоанализ

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

Видов криптоанализа множество, вот некоторые из них: Частотный анализ - определение ключа шифрования через

частоту появления символов в шифруемом тексте.

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

Линейный криптоанализ - поиск ключа шифрования по из­ вестному куску открытого текста и соответствующего ему шифро­ ванного.

Статистический криптоанализ - основан на применении со­ временных статистических методов.

XSL-атака (алгебраическая атака) — это атака на криптогра­ фический шифр, основанная на алгебраических свойствах шифра. Она предполагает решение особой системы уравнений.

Осуществляя атаку, криптоаналитик может ставить целью ре­ шение следующих задач:

♦Получение открытого текста из шифрованного.

♦Вычисление ключа шифрования.

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

Атаки на алгоритмы шифрования принято классифицировать в зависимости от того набора информации, который имеет злоумыш­ ленник перед осуществлением своей атаки. Прежде всего, крипто­ аналитические атаки можно разделить на две категории:

Категория L Криптоаналитик имеет только возможность пас­ сивного прослушивания некоего канала, по которому пересылаются шифрованные данные (рис. 32). В результате у злоумышленника есть лишь набор шифртекстов, шифрованных на определенном ключе. Такая атака называется атакой с известным шифртекстом. Она наи­ более сложна, но данный вариант атаки наиболее распространен, по­ скольку он является самым «жизненным» - в подавляющем боль­ шинстве реальных случаев криптоаналитик не имеет возможности

получить больше данных.
□	Зашифрованные данные		□ J
	\	О Й
Перехват и анализ и		|*|

1Ы

Рис. 32. Пассивный перехват шифрованных данных

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

ническим окружением, а также тактическими условиями осуществ­ ления атаки) действия для получения требуемой ему информации, например «прогонять» через шифратор какие-либо открытые тексты для получения соответствующих им шифртекстов (рис. 33).

Шифратор

Команды на шифрование требуемых данных /

и результаты их выполнения ^

Анализ исходных и полученных данных

Рис. 33. Активное воздействие на шифратор

В зависимости от данных, которые криптоаналитик может «до­ быть» у шифратора, существуют следующие виды атак:

Атака со знанием лишь шифрованного текста (<ciphertext - only attack): это ситуация, когда атакующий не знает ничего о содержании сообщения, и ему приходится работать лишь с самим шифрованным текстом. На практике часто можно сделать правдоподобные предполо­ жения о структуре текста, поскольку многие сообщения имеют стан­ дартные заголовки. Даже обычные письма и документы начинаются с легко предсказуемой информации. Также часто можно предположить, что некоторый блок информации содержит заданное слово.

Атака со знанием содержимого шифровки {known - plaintext attack): атакующий знает или может угадать содержимое всего или части шифрованного текста. Задача заключается в дешифровке ос­ тального сообщения. Это можно сделать либо путем вычисления ключа шифровки, либо минуя это.

Атака с заданным текстом {chosen - plaintext attack): ата­ кующий имеет возможность получить шифрованный документ для любого нужного ему текста, но не знает ключа. Задачей является на­

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

Атака с подставкой {Man —in —the - middle attack): атака на­ правлена на обмен шифрованными сообщениями и, в особенности, на протокол обмена ключами. Идея заключается в том, что, когда две стороны обмениваются ключами для секретной коммуникации (на­ пример, используя шифр Диффи - Хеллмана, Diffie - Heilman), про­ тивник внедряется между ними на линии обмена сообщениями. Да­ лее противник выдает каждой стороне свои ключи. В результате ка­ ждая из сторон будет иметь разные ключи, каждый из которых из­ вестен противнику. Теперь противник будет дешифровать каждое сообщение своим ключом и затем шифровать его с помощью другого ключа перед отправкой адресату. Стороны будут иметь иллюзию секретной переписки, в то время как на самом деле противник читает все сообщения. Одним из способов предотвратить такой тип атак за­ ключается в том, что стороны при обмене ключами вычисляют крип­ тографическую хэш-функцию значения протокола обмена (или по меньшей мере значения ключей), подписывают ее алгоритмом циф­ ровой подписи и посылают подпись другой стороне. Получатель проверит подпись и то, что значение хэш-функции совпадает с вы­ численным значением. Такой метод используется, в частности, в системе Фотурис (Photuris).

Атака с помощью таймера {timing attack): этот новый тип атак основан на последовательном измерении времени, затрачиваемого на выполнение операции возведения в степень по модулю целого числа. Ей подвержены, по крайней мере, следующие шифры: RSA, Дйффи - Хеллмана и метод эллиптических кривых.

Имеется множество других криптографических атак и крипто­ аналитических подходов.

Рассмотрим задачи из сферы криптографии, связанные с защи­ той данных, передаваемых по открытым каналам связи в наиболее полной постановке. В системе имеются две легальные стороны -