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

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

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

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

Таким образом, мы рассмотрели базовые требования, в соответ­ ствии с которыми строятся современные шифры:

♦построение шифров из простых преобразований - перестано­ вок, подстановок, элементарных функциональных операций и чередование операций различного типа;

♦циклическая, итеративная структура алгоритма - одна итера­ ция состоит из нескольких простых преобразований, итера­ ции отличаются друг от друга только использованными клю­ чевыми элементами;

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

♦ использование ключа относительно небольшого размера и выработка из него массива ключевых элементов для шагов преобразования с помощью процедуры «развертывания» ключа.

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

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

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

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

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

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

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

7} +1 = д а д , (*), однако в отличие от последней она содержит некоторые указания на

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

♦преобразование должно быть обратимым - иначе расшифро­ вание будет невозможным;

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

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

Для определенности будем называть подобное преобразование

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

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

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

Функция J{Ti), используемая для выделения инвариантного от­ носительно преобразования блока данных как из самого преобразуе­ мого блока, так и из результата его преобразования, называется ин­ вариантом стандартного шифрующего преобразования или инва­ риантом стандартного шага шифрования, а функция Д/„АГ,), предназначенная для выработки блока данных, используемого для модификации шифруемого блока, из инварианта /,• и ключевого эле­ мента Ки называется функцией шифрования шага преобразования.

Сам шаг шифрования в шифрах, построенных в соответствии с из­ ложенными принципами, называется раундом шифрования или просто раундом.

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

[0|]_,=°И-1 + 1, fi - fn~i+1»

•Л = Jn-i+\-

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

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

Я ' - Я Ф Г , L' = L ®Г, У(Я, L) = Н (ВL.

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

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

f\ ~ fn’f l ~ in-X'"''f\nH.\ ~ fn+\-\n!2\

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

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

т

Рис. 29. Преобразования, используемые в шифрах наряду со стандартными шагами (раундами) шифрования

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

Г =(Л ,72,...,7У ,

T' =Ti> г„ T=(T\\T2\...,T Lf) ,

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

7(7) = /(Г ),

или

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

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

Т= (Я,7), |Я| = \Ц = I Г| = |7|/2 = N/2.