<<

стр. 2
(всего 2)

СОДЕРЖАНИЕ

системы отлична от линейной и содержит ветвления и циклы.

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

Прежде чем перейти непосредственно к рассмотрению предмета настоящего выпуска,
вернемся к теме выпуска предыдущего, и рассмотрим один вопрос, который остался в нем
без необходимого освещения. Вспомним, что ключевые данные могут комбинироваться с
шифруемыми данными в преобразованиях двух типов: заменах и функциональных
операциях. Оказывается, что второй способ использования ключевой информации
предпочтительнее. Вместо того, чтобы делить входы вектора замены между блоком
шифруемых данных и ключевым элементом, оказалось выгоднее скомбинировать данные с
ключом посредством подходящей бинарной операции, а затем подвергнуть результат замене.
Предположим, например, что мы преобразуем 32-битовый блок данных, используя 32-
битовый ключ и несколько узлов замены с 4-битовым входом. Если использовать для
комбинирования ключа и данных узлы замены, то нам необходимо будет использовать 16
узлов замены 4 бита на 2 бита, на вход каждого узла замены будут подаваться два бита
шифруемых данных и два бита ключа. При этом каждый выходной бит такого узла будет
зависеть ровно от двух битов данных и от двух битов ключа. Если же мы подвергнем
преобразованию замены побитовую сумму по модулю 2 ключа с данными, то нам
необходимо будет использовать 8 узлов замены 4 бита на 4 бита, и каждый выходной бит
узла замен будет зависеть уже от четырех битов ключа и от четырех битов данных. Тем
самым в этом преобразовании может быть достигнута большая степень перемешивания и
рассеивания.
В результате сказанного выше в практических шифрах для комбинирования шифруемых
данных и ключа почти повсеместно используются бинарные операции аддитивного и,
значительно реже, мультипликативного типа. Рассмотрим указанную процедуру,
соответствующий блок преобразования показан на рисунке 1:




Рис. 1. Комбинирование ключевого элемента с данными с
использованием бинарной операции "°"



В этом случае преобразование осуществляется по следующему уравнению:

Ti +1 = Ti  ° K .
i

Бинарная операция "°" , использованная для модификации шифруемого блока, должна
обладать свойством, необходимым для операции наложения гаммы, в частности, должна
существовать обратная ей операция "•", такая, что для любых блоков данных T и K
допустимого размера должно выполняться следующее условие:

(T ° K) • K = T.

Сложность преобразования существенно повысится, если комбинировать с данными не
непосредственно ключевой код, а код, выработанный из ключа и зависящий от данных, как
показано на рисунке 2:




Рис. 2. Шифрующее преобразование блока данных с использованием кода,
выработанного из ключевого элемента Ki и шифруемого блока Ti




В этом случае преобразование осуществляется по следующему уравнению:

Ti +1 = Ti  ° f(Ti ,K ).
i

На самом деле понятно, что с математической точки зрения данная запись мало отличается
от наиболее общей формы записи преобразования:

Ti +1 = F (Ti ,K ),          (*)
i
однако, в отличие от последней, она содержит некоторые указания на возможный способ
своей реализации. Ее важная особенность заключается в том, что от функции
преобразования f из первого уравнения уже не требуется обратимость, как от функции F из
уравнения (*), от нее требуется только как можно большая сложность плюс выполнение
некоторых дополнительных условий, которые в сильно упрощенном виде могут быть
сформулированы как отсутствие потерь информации при ее вычислении. Дело в том, что при
создании шифрующего преобразования общего вида бывает необходимо примирить два
противоречащих друг другу требования:

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

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

Обратимость изображенного на рисунке 2 преобразования означает, что должна
существовать эффективно вычислимая функция g(Ti+1,Ki), обладающая следующим
свойством:

f(Ti ,Ki ) = g(Ti +1,K ) = g(Ti  ° f(Ti ,K ),Ki )        (**)
i i

для любых допустимых блоков данных Ti и Ki. В этом случае обратное преобразование
будет иметь вид, изображенный на рисунке 3:




Рис. 3. Обращение шифрующего
преобразования.




Обратное преобразование выполняется в соответствии со следующим уравнением:

Ti  = Ti +1 • g(Ti +1,Ki ).

В общем случае сконструировать пару функций преобразования (f и g), удовлетворяющих
уравнению (**) и являющихся при этом сложными и нелинейными, достаточно трудно. Тем
не менее, это возможно, если "отделить" требование сложности функций f и g от требования
выполнения условия (**). Это легко можно сделать, если использовать операцию "°"
модификации шифруемого блока, которая оставляет неизменным значение некоторой
функции от преобразуемого блока данных:
Ii  = J (Ti ) = J (Ti  ° Гi ) = J (Ti +1)

для любых блоков данных T , Г подходящего размера. Понятно, что в этом случае и
i i
обратная ей операция "•" также обладает указанным свойством:

Ii  = J (Ti +1) = J (Ti +1 • Гi ) = J (Ti ).

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


Рис. 4. Стандартные
шифрующие
преобразования: прямое
(слева) и обратное (справа)




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

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

Функция, J(Ti ) используемая для выделения инвариантного относительно преобразования
блока данных как из самого преобразуемого блока, так и из результата его преобразования,
называется инвариантом стандартного шифрующего преобразования или инвариантом
стандартного шага шифрования , а функция f(Ii ,Ki ), предназначенная для выработки блока
данных, используемого для модификации шифруемого блока, из инварианта Ii и ключевого
элемента Ki , называется функцией шифрования шага преобразования . Сам шаг
шифрования в шифрах, построенных в соответствии с изложенными принципами,
называется раундом шифрования или просто раундом .

В рассматриваемом случае прямое и обратное шифрующие преобразования осуществляются
в соответствии со следующими уравнениями:

Ti +1 = Ti  ° f(J (Ti ),K ),
i

Ti  = Ti +1 • f(J (Ti +1),K ).
i

Прежде чем продолжить рассмотрение необходимых свойств стандартных шифрующих
преобразований, обсудим возможные соотношения между размерами блоков, участвующих в
них. Если между размерами преобразуемого блока (Ti ), модифицирующего значения (Гi ) и
инварианта (Ii ) выполняется следующее соотношение
| Ti  | = | Гi  | + | Ii  |,        (***)

то операция модификации данных (“°”) не должна терять информацию о своих аргументах, -
это, в частности, означает, что изменение любого из аргументов должно приводить к
изменению значения функции. Если равенство (***) не будет выполняться и его левая часть
будет больше правой части, то стойкость преобразования будет далеко от оптимума - ее
можно будет повысить, увеличив размер модификатора (Гi ), инварианта (Ii ), или их обоих.
Если же правая часть окажется больше левой части, то операция модификации обязательно
будет терять информацию о модифицирующем элементе - это означает, что будут
существовать различные элементы Г и Г', такие, что для некоторого блока данных T будет
выполняться следующее равенство:

T ° Г = T ° Г',

в чем также нет особого смысла. Таким образом, резонно выбирать размеры блоков,
участвующих в преобразовании, такими, чтобы выполнялось приведенное выше равенство
(***). Идем дальше, с точки зрения достижения необходимой стойкости и эффективности
шифрующего преобразования выгодно взять размеры модификатора (Г ) и инварианта (I )
i i
равными: | Г | = | I |. С учетом равенства (***) их размер будет равен половине размера
  i    i 
шифруемого блока:

| Г | = | I | = | T |/2.

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




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

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

блока данных, в котором инвариантом является

часть шифруемого блока.




В этом случае преобразование осуществляется по следующим уравнениям:

Hi +1 = Hi  ° f(Li ,Ki ),
Li +1 = Li ,

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




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

Hi +2 = Hi +1 = Hi  ° f(Li ,Ki ),
Li +2 = Li +1 ° g(Hi +1,K +1) = Li  ° g(Hi +1,K +1),
i i

Архитектура шифров, базирующаяся на описанном выше преобразовании, оставляющем
неизменной часть шифруемого блока, называется сетью Файстеля , точнее - обобщенной
сетью Файстеля . Разница между ними заключается в том, что в первой для модификации
данных используется операция побитового исключающего ИЛИ , а во втором - любая
подходящая бинарная операция. Данная архитектура шифров была предложена в 70-е годы
пионером в создании криптографических алгоритмов подобного типа доктором Хорстом
Файстелем, работавшим в то время в исследовательской лаборатории фирмы IBM и
создавший там криптосистему Люцифер , послужившую прототипом наиболее известного
шифра этого типа - американского стандарта шифрования, криптоалгоритма DES,
сохраняющего свой статус стандарта вплоть до настоящего времени, но, очевидно,
доживающего в этом качестве последние месяцы.




Рис. 7. Раунд шифрования в обобщенном
шифре Файстеля.




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

Если представлять преобразуемый блок данных как целое беззнаковое число, то уравнение
преобразования одного раунда будет следующим:

,

если же его интерпретировать как массив битов, то уравнение будет следующим:
,


 

где через Lo (X) и Hi (X) обозначен блок из n соответственно младших и старших битов
n n
блока X, через X || Y - конкатенация блоков X и Y, - их объединение в один блок данных
таким образом, что X является старшей частью объединенного блока, а Y - его младшей
частью, через [x] - целую часть действительного числа x, n и n - размер соответственно
H L
старшей (шифруемой) и младшей (шифрующей) частей преобразуемого блока.
Конечно, размер шифрующей и шифруемой части блока может изменяться от раунда к
раунду, однако особого смысла в этом нет и обычно эти величины постоянны для
конкретного криптоалгоритма. Если они равны друг другу, то такая схема называется
сбалансированной , а если нет - то несбалансированной сетью Файстеля .

http://www.enlight.ru/ib/tech/crypto/part6.htm
Цикл статей по криптографии. Выпуск 6

Архитектура блочных шифров. Окончание.
(Андрей Винокуров, 5/Мая/99)

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



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




По указанной причине на практике не так часто встречаются шифры Файстеля, в которых
шифрующая часть блока меньше шифруемой по размеру |Li | < |Hi |, особенно для размеров
блока, не превышающих 64 бита. С другой стороны, за один раунд шифруется |Hi | бит блока,
и если уменьшить эту величину, то при фиксированном количестве раундов каждый бит
блока будет шифроваться меньшее число раз, поэтому шифры Файстеля с размером
шифруемой части блока меньше шифрующей, тоже не получили значительного
распространения. Таким образом, остаются шифры, в которых размеры обеих частей блока
одинаковы: |Li | = |Hi |. Именно такие шифры, архитектура которых, как было отмечено выше,
называется сбалансированной сетью Файстеля, доминируют в современной практической
криптографии. Схематически их можно представить двояко, как показано на левой и правой
частях следующего ниже рисунка 1. Правая схема определяет в точности то же самое
преобразование, что и левая, и сделана в предположении, что число раундов (n) четно.
Рис. 1. Сбалансированная обобщенная сеть Файстеля.
В сбалансированной сети Файстеля преобразования выполняются по следующим

уравнениям:

X0 = HiT |/2(T), X1 = LoT |/2(T),
| |

Xi +1 = Xi -1 ° f(X ,Ki ) , для i = 1,2,...,n,
i

T' = Xn +1 || Xn ,

 




Рис. 2. Преобразования за- и расшифрования в сбалансированном шифре Файстеля.
это показано на следующем рисунке 2:


Если последовательность раундовых функций, использованных в шифре, палиндромиальна
(т.е. если



), и, в частности, если на всех раундах используется одна и та же функция шифрования, то
процедуры за- и расшифрования различаются только порядком использования раундовых
ключей - они взаимно обратны. В этом случае шифр обладает весьма полезным с точки
зрения удобства реализации свойством - процедуры за- и расшифрования могут быть
выполнены одним и тем же аппаратным или программным модулем. Использование
одинаковых или почти одинаковых функций шифрования позволит достигнуть другого
весьма желательного свойства шифра - итеративности. Это означает, что все итерации-
раунды может выполнять один и тот же модуль, в результате чего станет возможным
получить более компактные реализации шифров.
Следует отметить, что в цепочку преобразований блока в шифрах подобной структуры
иногда добавляют преобразования, рассмотренные в выпуске №4 - так называемые прямые
преобразования - перестановки, подстановки, функциональные операции непосредственно
над шифруемыми данными. Для того, чтобы алгоритмы за- и расшифрования были
структурно эквивалентны, необходимо, чтобы для каждого включенного в алгоритм прямого
преобразования, отстоящего от начала цепочки на несколько шагов, симметрично ему, то
есть точно на таком же расстоянии от конца преобразования находилось обратное
преобразование - в точности, как это было описано в выпуске №4. Обычно прямое
преобразование добавляют в начало алгоритма, это делают для того, чтобы "разбить"
типовые паттерны, встречающиеся в шифруемых данных. В соответствии с
вышеизложенным правилом в этом случае в конце цепочки используется обратное
преобразование. Например, перед первым раундом шифрования в алгоритме DES
выполняется битовая перестановка, а после последнего раунда - обратная ей битовая
перестановка. В более поздних шифрах для этой цели используется комбинирование с
ключевым элементом, выполняемое намного быстрее, нежели перестановка битов.
Следует отметить, что раундом шифрования обычно называют цикл преобразования с
использованием функции шифрования, нетривиальным образом зависящей от ключа раунда
и шифрующей части блока. Если преобразование проще, и в нем используется только
ключевой элемент или только шифрующая часть блока, такой шаг, хотя формально и мог бы
рассматриваться как раунд, таковым не считается. Например, шаги алгоритма, реализующие
изображенные на следующем ниже рисунке упрощенные преобразования, не считаются
раундами:




T' = P(T)
Рис. 3. Преобразования, используемые в шифрах наряду со стандартными шагами
(раундами) шифрования.
На этом мы с вами закончим рассмотрение сетей Файстеля и перейдем к рассмотрению

альтернативных решений в построении шифров. Оставлять часть преобразуемого блока
неизменной - наиболее простой и очевидный способ получить инвариант относительно
преобразования, но не единственный. Другой способ сделать это состоит в том, чтобы
разделить шифруемый блок на несколько частей и изменять их согласованным образом:

T = (T1,T2,...,TL ) ,

Ti ' = Ti   ™i   Г,

T' = (T 1',T2',...,TL ') ,

так, чтобы некоторая функция от преобразуемого блока не меняла своего значения:

J (T) = J (T') ,

или

J (T1,T2,...,TL ) = J (T 1',T2',...,TL ') ,

где J - функция выработки инварианта.

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

T = (H,L), |H| = |L| = | Г| = |T|/2 = N/2

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




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




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

H = (H 1,H 2,...,HK ) ,
L = (L1,L2,...,LK ) ,
Г = ( Г1,Г2,..., ГK ),
J  = (J 1,J 2,...,JK ) ,

где для всех k = 1, 2 ,..., K справедливо |H | = |L | = | Г | = |J | = z . В этом случае
k k k k k
модификация фрагментов и выработка инварианта осуществляется по следующим
формулам:




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



Именно такой инвариант используется в известном шифре IDEA. Раунд шифра стандартной
архитектуры при использовании для получения инварианта операции побитового
исключающего ИЛИ выглядит как показано ниже на рисунке 4:

Рис. 4. Способ построения раунда шифрования в шифрующих

сетях общего типа с использованием операции

исключающего ИЛИ.




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

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

Шифр рассмотренной архитектуры имеет структуру, изображенную на рисунке 5.




Рис. 5. Обобщенная шифрующая сеть с использованием

операции побитового исключающего ИЛИ для

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

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

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

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

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

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

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

http://www.enlight.ru/ib/tech/crypto/part7.htm
Цикл статей по криптографии. Выпуск 7

Режимы шифрования (начало)
(Андрей Винокуров)

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

Итак, предположим, что в нашем распоряжении имеется симметричный блочный шифр,
содержащий два зависящих от ключа K преобразования за- и расшифрования N-битовых
блоков, E и D соответственно. Простейший способ использовать эти преобразования -
K K
разбить шифруемый массив T на N-битовые блоки и шифровать их независимо друг от
друга:

T = (T1,T2,...,Tn ),
T'i  = EK (Ti ),
T' = (T' 1,T' 2,..., T'n ),
где |T'i | = |Ti | = N.

Этот режим шифрования , то есть способ использования криптографического
преобразования для шифрования данных, в отечественной литературе и части зарубежных
источников называется режимом простой замены , в другой части зарубежных источников,
тяготеющей к англосаксонской криптографической терминологии, он называется режимом
электронной кодовой книги (Electronic Code Book, сокращенно ECB). Использование данного
простейшего режима шифрования сопряжено с рядом трудностей. Первая, чисто техническая
трудность называется проблемой последнего блока и заключается в том, что размер
шифруемого текста может быть не кратен размеру блока используемого шифра. В этом
случае последний блок будет неполным (|Tn | < N), и его необходимо как-либо дополнить до
размера в N бит, так как криптографическому преобразованию может быть подвергнут
только блок полного размера. При этом все полученные биты блока шифротекста будут
значащими, их нельзя отбрасывать без потери информации, что приводит к увеличению
размера шифротекста по сравнению с открытым текстом, а это не во всех случаях
допустимо.

Вторая проблема связана со стойкостью шифра и заключается в том, что при использовании
блочного криптографического преобразования E для зашифрования данных из одинаковых
K
блоков открытого текста получаются одинаковые блоки шифротекста:

Ti  = Tj    EK (Ti ) = EK (Tj ).

Обратное также верно: если два блока шифротекста совпадают, то соответствующие им
блоки открытого текста идентичны:

EK (Ti ) = EK (Tj ) Ti  = Tj .

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

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

T'i  = F (T1,T2,...,Ti ,T' 1,T' 2,...,T'i –1,S).

Понятно, что при вычислении функции F должно использоваться криптографическое
преобразование E и приведенное выше соотношение должно быть разрешимо относительно
K
шифруемого блока T , чего требует обратимость процедуры шифрования. Как мы с вами
i
выяснили в предыдущих выпусках, обратимость преобразования в сочетании с его
криптостойкостью в ситуациях, когда один блок данных модифицируется с использованием
одного или нескольких дополнительных блоков данных легче всего обеспечить за счет
применения обратимых бинарных операций. Напомню, что бинарная операция “° ”
называется обратимой, если существует обратная ей операция “· ”, такая, что каковы бы не
были два блока данных X и Y, составляющие пару допустимых аргументов первой операции,
справедливо следующее соотношение:

(X °  Y) ·  Y = X.

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

В блочных режимах шифруемый блок первоначально модифицируется путем наложения на
него с помощью бинарной операции (“° ”) значения функции f, зависящей от всех
предыдущих блоков открытого (Ti ) и шифрованного (T'i ) текста, и, возможно, от параметра
инициализации (S), после чего полученное значение модифицируется с помощью
криптографического преобразования (EK ). Таким образом, зашифрование в блочных
режимах выполняется в соответствии со следующим уравнением:

T'i  = EK (Ti   °  f(T 1,T2,...,Ti –1,T' 1,T' 2,...,T'i –1,S)).

Тогда расшифрование в режимах этого типа выполняется по следующему уравнению:

Ti  = DK (T'i )  ·  f(T1,T2,...,Ti –1,T' 1,T' 2,...,T'i –1,S) ,
где через DK обозначена обратная EK процедура расшифрования в режиме простой замены, а
через “· ” – бинарная операция, обратная операции “° ”.

В потоковых режимах шифруемый блок модифицируется путем наложения на него с
помощью бинарной операции (“° ”) результата криптографического преобразования E
K
значения функции f , зависящей от всех предыдущих блоков открытого (T ) и шифрованного
i
(T' ) текста, и, возможно, от параметра инициализации (S). Таким образом, зашифрование в
i
потоковых режимах выполняется в соответствии со следующим уравнением:

T'i  = Ti   °  EK (f(T 1,T2,...,Ti –1,T' 1,T' 2,...,T'i –1,S)).

Тогда расшифрование в режимах этого типа выполняется по следующему уравнению:

Ti  = T'i  ·  EK (f(T 1,T 2,...,Ti –1,T' 1,T' 2,...,T'i –1,S)).

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

Fi  = f(T 1,T 2,...,Ti –1,T' 1,T' 2,...,T'i –1,S) и

Fj  = f(T 1,T 2,...,Tj –1,T' 1,T' 2,...,T'j –1,S), то

i   j  Fi    Fj .

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

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

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

1.Блочные режимы:

зашифрование:

T'i  = EK (Ti    f(T ,T ,...,T ,T' ,T' ,...,T' ,S));
i –1 i –1
1 2 1 2

расшифрование:

Ti  = DK (Ti )   f(T 1,T 2,...,Ti –1,T' 1,T' 2,...,Ti –1,S);

2.Потоковые режимы:

зашифрование:

T'i  = Ti    EK (f(T1,T2,...,Ti –1,T' 1,T' 2,...,T'i –1,S));

расшифрование:

Ti  = T'i    EK (f(T1,T2,...,Ti –1,T' 1,T' 2,...,T'i –1,S)).

Теперь сравним оба типа режимов, сравнение начнем с двух фундаментальных фактов,
которые, собственно, и определяют их свойства:

В блочных режимах зашифрование осуществляется применением
криптографического преобразования непосредственно к шифруемому блоку,
модифицированному значением рандомизирующей функции f, – в уравнении
зашифрования шифруемый блок Ti стоит внутри скобок криптографического
преобразования EK (...), тогда как в потоковых режимах зашифрование осуществляется
точно так же, как в потоковых шифрах, наложением на шифруемый блок некоторого
кода с помощью обратимой бинарной операции, и шифруемый блок Ti не фигурирует
в выражении для аргумента преобразования EK .

Для расшифрования в блочных режимах применяется криптографическое
преобразование D , обратное преобразованию E , использованному для
K K
зашифрования, тогда как при расшифровании в потоковом режиме используется то же
самое преобразование, что и при зашифровании. Из этого следует, вообще говоря,
весьма интересный вывод: для построения блочных режимов шифрования
необходимо обратимое криптографическое преобразование, тогда как для построения
потоковых режимов обратимость используемого криптопреобразования не требуется,
достаточно его стойкости. Это, в частности, позволяет реализовать такие режимы на
базе вычислительно необратимых функций, например, на базе MD5 и аналогичных
алгоритмов.

Из сказанного выше становится понятным, что названия “блочные” и “потоковые” режимы
имеет вполне простой и понятный смысл: шифр в блочном режиме ведет себя как обычный
блочный шифр: шифрованию могут подвергаться только полные блоки данных. Если
шифруемый массив данных содержит нецелое число блоков, это создает для такой схемы
определенные трудности – данный вопрос будет подробно рассмотрен ниже. Шифры же в
потоковом режиме являются в полном смысле слова потоковыми шифрами, и для них, в
частности, отсутствует проблема последнего блока. По своей сути потоковый режим есть не
что иное, как способ построения потокового шифра на базе блочного криптографического
алгоритма. В этом, собственно, и заключается фундаментальная разница между указанными
типами режимов, хотя, на первый взгляд, различия между ними могут показаться
незначительными, и их уравнения зашифрования похожи друг на друга:

T'i  = EK (Ti   Fi ) в “блочных” режимах,

T'i  = Ti    EK (Fi ) в “потоковых” режимах,

где F  = f(T ,T ,...,T ,T' ,T' ,...,T' ,S) для обоих типов режимов.
i i –1 i –1
12 1 2

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

В блочных режимах шифрование двух различных массивов информации на одном и том же
ключе с одним и тем же параметром инициализации S допустимо и не ведет к потере
криптографической стойкости. Собственно, по большому счету, в режимах этого типа
вполне можно обойтись и вовсе без синхропосылки. Конечно, если при этом два массива
данных T = (T 1,T 2,...,Tn ), и V = (V1,V2,...,Vn ) дают при зашифровании массивы шифротекста,
начальные отрезки которых совпадают, это говорит о том, что соответствующие начальные
отрезки исходных массивов также идентичны:

если T'i  = V'i для i = 1,2,...,m,

то Ti  = Vi для i = 1,2,...,m.

Если использованная при шифровании функция f такова, что ее значение не зависит от
предыдущих блоков открытого текста и шифротекста, а зависит только от количества
предшествующих блоков данных, то есть фактически от порядкового номера шифруемого
блока i, и параметра синхронизации S, т.е. если F  = f(S,i), то это свойство справедливо для
i
произвольных пар одинаковых блоков, занимающих в своих текстах одно и то же место, а не
только для тех, что находятся в начальных отрезках своих массивов:

T'i  = V'i      Ti  = Vi для любого i.
Вспомним, что в случае простой замены, т.е. когда шифруемый блок данных вовсе не
модифицируется перед тем, как быть подвергнутым зашифрованию, указанное свойство
выполняется для любых совпадающих блоков двух шифротекстов, в том числе и
занимающих разные позиции в своих массивах:

T'i  = V'j      T  = V для любых i,j,
i j

и, в частности,

T'i  = T'j      T  = T для любых i,j.
i j

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

В потоковых шифрах то же самое приводит к катастрофической потере стойкости.
Предположим, что два массива данных, T = (T ,T ,...,T ), и V = (V ,V ,...,V ), зашифрованы в
n n
12 12
потоковом режиме на одном и том же ключе K с использованием одного и того же параметра
инициализации S. Для простоты предположим, что для модификации шифруемых данных
используется операция побитового исключающего ИЛИ. Тогда

T' 1 = T 1   EK (f(S)),

V' 1 = V1   EK (f(S)), откуда следует, что

T' 1   V' 1 = (T 1   EK (f(S)))   (V1   EK (f(S))) = T 1   V1.

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

T'i  = V'i для i = 1,2,...,m.

Точно также, как и в случае блочных режимов, это позволяет установить тождественность
соответствующих отрезков открытого текста:

Ti  = Vi для i = 1,2,...,m.

Однако помимо этого будет также выполняться и приведенное выше соотношение, но
сформулированное не для первых блоков, а для первых несовпадающих блоков
соответствующих массивов данных:

T'm +1   V'm +1 = Tm +1   Vm +1.

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

T'i  = Ti    EK (f(i,S)),

V'i  = Vi    E (f(i,S)),
K

откуда следует, что

T'i    V'i  = Ti    Vi
для всех блоков шифруемых массивов, а не только для первых двух отличающихся, как это
было в общем случае. Последнее соотношение позволяет восстановить оба открытых
сообщения, причем тем легче, чем большей избыточностью они обладают. Данная ситуация
по сути представляет случай повторного использования одноразовой гаммы и влечет те же
самые катастрофические для шифра последствия. Вот почему для систем шифрования, в
которых используются потоковые режимы, необходимо обеспечивать уникальность
синхропосылки в случаях, когда возможно зашифрование нескольких массивов данных на
одном и том же ключе.

http://www.enlight.ru/ib/tech/crypto/part8.htm

<<

стр. 2
(всего 2)

СОДЕРЖАНИЕ