Конахович Г.Ф., Климчук В.П., Паук С.М., Потапов В.Г. Защита информации в телекоммуникационных системах

Подождите немного. Документ загружается.

210

потому что даже при наименьших изменениях ключа (например, только в одном

бите) должен изменяться (и довольно существенно) каждый блок материала

ключа. [16]

Операции, в которых в качестве параметра V используется материал ключа,

называют перемешиванием с ключом или добавлением ключа (никакой связи с

арифметической операцией этот термин не имеет). Таких операций во время

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

решается одно из главных требований к шифрам — невосстановимость ключа.

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

неоднократно и разными способами, то такая информация будет необратима

относительно добавленной информации, хотя обратимость относительно первого

операнда останется.

Например, пусть X и К — четырехбитное исходное число и ключ соот-

ветственно (диапазон возможных значений 0...15 у каждого). Тогда формула

X' = ((x + k)X OR (k + 7))AND1111

где нижний индекс указывает на систему счисления, является обратимой от-

носительно X — по известным X' и К всегда можно восстановить X, однако

необратимой относительно К по известной паре X и X'.

Не существует аналитической формулы, которая бы вычисляла К через X и X'.

Конечно, всегда можно составить табличную зависимость, перебрав при

известном X все K и записав все полученные X', однако это легко сделать только

в гипотетическом примере из 16 возможных значений. На практике, при длине

ключа в 128 бит для решения этой задачи не хватит ни ресурсов памяти для

хранения, ни вычислительных возможностей ЭВМ. Таким образом,

многократное сложение материала ключа по сложной схеме является надежным

средством защиты блочных шифров от атаки по известным парам

"открытый/зашифрованный текст".

Третьим возможным значением параметра V является значение, вычисленное

от независимой части шифруемого блока. Этот метод лежит в основе схемы

блочного шифрования и носит название сети Файштеля. Операции,

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

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

Например, на каком-то промежуточном этапе на первый байт операцией XOR

накладывается значение пятого байта и т.д. Обратимость обеспечивается на том

основании, что на принимающей стороне алгоритм, подходя к дешифровке этого

места, уже "знает" значение пятого байта, которым производится наложение, и

повторным выполнением операции XOR восстанавливает первый байт.

Проблема возникла бы в том случае, если бы на первый байт наложили функцию

от этого же первого байта. Тогда, даже несмотря на потенциальную обратимость

операции, дешифрирующая сторона не смогла бы вычислить значение V зашла

бы в тупик.

Одной из наиболее распространенных схем блочных шифров является сеть.

Блочный шифр, построенный по такой схеме, состоит из многократных

211

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

называемых слоем.

Разбиение всего процесса шифрования на несколько однотипных слоев

позволяет [16]:

■ сократить размер программного кода использованием цикла;

■ унифицировать "алгоритмическую формулу" шифрования и, как

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

криптоатак;

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

мости (путем увеличения количества раундов);

■ ввести понятие ключей раунда, на которые разбивают материал ключа.

Некоторые из слоев не содержат в себе процедур смешивания с ключом.

Конечно, они выполняют функции обратимого смешивания данных внутри

блока или защищают блочный шифр от какого-нибудь конкретного класса

криптоатак. Такие слои выполняют свои преобразования всегда по одной и той

же схеме. В тех слоях, где в качестве параметров операций используется

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

из материала ключа — ключи раунда. Поэтому каждый такой слой выполняет

свое уникальное преобразование материала.

Одной из наиболее простых и ранних сетей является SP-сеть (SP-network),

каждый раунд которой состоит из двух слоев. Свое название эта сеть получила

от сокращения английских слов "substitution" (подстановка) и "permutation"

(перестановка). В слое подстановки над данными выполняются преобразования

класса сложения, исключающего ИЛИ, табличных подстановок, в качестве

параметров используются константы и материал ключа. В слое перестановки

биты (или изредка байты) меняются местами внутри блока обычно по

фиксированной (независимой от ключа) схеме.

Более современной модификацией технологии сетей является KASLT — сеть

с тремя слоями в каждом раунде. Первый слой — сложение ключа (Key Addition,

KA) — выполняет смешивание данных с ключом раунда. Смешивание

выполняется обычно какой-нибудь простой операцией: сложением или XOR.

Второй слой — подстановка (Substitution, S) — выполняет алгоритмическую или

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

Третий слой — линейное преобразование (Linear Transformation, LT) —

выполняет активное обратимое смешивание данных внутри блока.

Как видим, в сравнении с SP-сетью тут сложение ключа вынесено в от-

дельный слой, разделены линейная и нелинейная части преобразований, а

смешивание данных выполняется с помощью линейных преобразований, ко-

торые быстро реализуются в программе.

Практически независимой от двух предыдущих разработок и очень попу-

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

сеть Файштеля (рис. 5.13). В каждом из ее раундов — только по одному слою,

то есть, все преобразования однотипные, однако сама структура преобразований

специфична: на некоторую часть блока, шифруемого обратимой операцией,

212

накладывается значение функции (возможно, необратимой), вычисленной от

другой части блока.

Независимые потоки информации, порожденные из исходного блока, носят

название ветки сети. В классической схеме их две. Величины V1 носят название

параметров сети. Обычно их роль выполняют материалы ключа. Функция F

носит название образующей. Оптимальное количество раундов для сети

Файштеля К — от 8 до 32. [16]

Сеть Файштеля является обратимой. Она имеет ту особенность, что даже если

в качестве образующей функции F будет использовано необратимое

преобразование, то и в этом случае вся цепочка будет восстановимым. Это

обусловлено тем, что для обратного преобразования сети Файштеля не требуется

вычислять функцию

1−

, и во время дешифрования вычисляется только прямое

значение F. Обратимость требуется только для операции наложения F на ветку,

которая шифруется в этом раунде, поэтому тут чаще всего используются

операции XOR и изредка — арифметическое сложение.

Более того, сеть Файштеля, в которой для наложения значения F исполь-

зуются операция XOR, симметричная. Исключающие ИЛИ обратимые своим же

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

декодирование блока той же сетью Файштеля, но с обратным порядком

параметров VI.

213

Отметим, что для обратимости сети Файштеля не имеет значения, является

количество раундов четным или нечетным. В большинстве реализаций сети

Файштеля прямое и обратное преобразования выполняются одним и тем же

фрагментом программного кода, который оформлен в виде процедуры, и

которому в качестве параметра передается вектор величины VI в исходном (для

шифрования) или в инверсном (для дешифрования) порядке.

С незначительными доработками сеть Файштеля можно сделать и абсолютно

симметричным шифром, то есть, таким, который выполняет функции

шифрования и дешифрования одним и тем же набором операций. Модификация

сети Файштеля с такими свойствами представлена на рис. 5.14.

214

Основная ее особенность заключается в обратном порядке во второй поло-

вине цикла. Необходимо отметить, что как раз из-за этой недостаточно иссле-

дованной специфики такой схемы ее используют в криптоалгоритмах с большой

осторожностью. Дело в том, что существует потенциальная возможность

ослабления зашифрованного текста обратимыми преобразованиями.

А вот модификация сети Файштеля для большего количества ветвей при-

меняют значительно чаще. Это в первую очередь связано с тем, что при больших

размерах шифруемых блоков (128 и больше бит) становится неудобно работать с

математическими функциями по модулю 64 и выше.

Как известно, основные единицы информации, обрабатываемые процес-

сорами на сегодняшний день, — это байт и двойное машинное слово (32 бита),

поэтому все чаще в блочных криптоалгоритмах встречается сеть Файштеля с

четырьмя ветвями. Для более быстрого смешивания информации между ветвями

применяются две модифицированные схемы, которые носят название тип 2 и

тип 3. За счет частичного объединения обработки потоков в двух последних

схемах, количество раундов у них лишь незначительно больше количества

раундов в сети Файштеля с двумя ветвями.

Далее рассмотрим практику блочного шифрования в хронологическом

порядке с начала его разработки в 70-х годах прошлого столетия. В 1980 году в

США был принят национальный стандарт шифрования данных DES (Data

Encryption Standard). Алгоритм работы этого стандарта представляет собой

классическую сеть Файштеля из 16 раундов с добавлением входной и выходной

перестановки битов, с разрядностью блока 64 бита и размерами ключа 56 бит.

Общая структура этого алгоритма представлена на рис. 5.15.

Общая формула для вычисления индексов в псевдокоде имеет вид (цикл по i

от 0 до 63):

[

]

(

)

(

)

(

)

(

)

[

]

534012012345

1||7 iiiiiiINiiiiiiOUT −−=

где запись Х

означает r-й бит в записи чисел X; "|" — конкатенация (сцепле-

ние) цифр в двоичной записи чисел. Прибавление материала ключа выполняется

только в сети Файштеля, поэтому только она выполняет шифрование данных.

Разрядность ключей раундов, применяемых в DES, равна 48 битам. Для

симметричности алгоритма шифрования/дешифрования в DES, как и в класси-

ческой сети Файштеля, выполняется дополнительный размен последнего обмена

ветвей. Это позволяет выполнять шифрование и дешифрование одним и тем же

программным кодом, осуществляя передачу ему в первом случае ключей ра-

ундов в прямом порядке

(

)

1510

,...,, kkk

, а во втором случае — в обратном. Общий

вид сети Файштеля алгоритма DES представлен на рис. 5.16.

Образующая функция сети в алгоритме DES состоит из четырех операций:

1. Перестановка бит / расширение блока с помощью повторений по

указанной схеме.

2. Наложение ключа раунда операцией XOR.

3. Табличные подстановки.

4. Перестановка бит.

215

216

Расширения входных данных выполняются на уровне битов путем записи

некоторых из них в выходной поток дважды. В результате из 32 битов об-

разуется 48-битный блок информации, совпадающий по размеру с ключом

раунда. Наложение ключа раунда выполняется операцией XOR с разрядностью

операции 48 бит.

Табличные подстановки, применяемые в DES, имеют разрядность 6x4 бит. 48-

битный блок данных после наложения ключа разбивается через свою табличную

подстановку, которая обозначается как

и т.д. В результате получаем 8

блоков по 4 бита в каждом: всего 32 бита — исходная разрядность

обрабатываемой ветки.

Заключительной операцией образующей функции является перестановка

битов внутри 32-битного блока, отвечающего за смешивание информации.

Общий вид одного раунда сети Файштеля алгоритма DES представлен на рис.

5.17

Расширение ключа (создание ключей раунда) выполняется в DES по сле-

дующей схеме. На основе 56 значащих битов из ключа на начальном этапе

образуются по отдельному закону два 28-битних вектора Со и Do. Эти законы

устанавливают последовательность выбора битов из ключа.

Институтом стандартизации рекомендовано во время сохранения ключа для

DES использовать простейшее помехоустойчивое кодирование: проверку

четности, — поэтому в каждом байте значащими являются только первые 7

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

двоичном коде каждого байта нечетно. Таким образом, при существующей

разрядности ключа в 56 бит он хранится в 64-битной структуре. Именно этим

объясняется появление в законе выбора битов для Со и Do номеров больше 56 и

отсутствие битов с номерами 8, 16, 24, 32, 40, 48, 56, 64 (они являются

контрольными, то есть, незначащими).

Для генерации каждого очередного ключа раунда k

векторы Со и Do цик-

лически сдвигаются влево на определенное количество разрядов. Для выбора 48

217

бит ключа i-го раунда, который был получен после циклического сдвига вектора

, объединяются, и из 56 битов полученного массива отбирают по отдельному

закону 48.

Анализируя принцип шифрования в DES, бросается в глаза значительное

количество битовых перестановок и выборок в алгоритме. И, это не удивительно,

потому что основной схемой проектировщиками планировалась только

аппаратная реализация. Этому подчинено и наложение ключа именно операцией

XOR, которая реализуется в этом случае наиболее просто и распараллелено, с

небольшим размером и минимальным количеством табличных подстановок.

Аппаратная реализация алгоритма в отдельной или встроенной микросхеме

позволяет добиться большой скорости шифрования при достаточно малых

устройствах. [16]

Единственным нелинейным элементом алгоритма является этап табличных

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

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

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

видов криптоанализа.

Алгоритм имеет некоторые специфические свойства, которые, по мнению

многих специалистов, не являются значительно уязвимыми. Первой

особенностью является закон: если

Y=EnCrypt(X, KEY),

то

Y' = EnCrypt(X', KEY')

где X' — побитная инверсия X; Y' — побитная инверсия Y; KEY' — побитная

инверсия KEY.

Второй особенностью является наличие среди множества 2

ключей четырех

слабых ключей (weak keys). Во время шифрования данных любым из этих

ключей среди 2

входных данных существует 2

блока, которые в результате

шифрования превращаются сами в себя, то есть, для них

EnCrypt(X, WEAK_KEY)=X.

Несмотря на то, что вероятность такого напрасного шифрования очень велика

(1/2 — для криптографии это очень большой риск), вероятность того, что сам

ключ окажется слабым, очень мала (1/2

). Это позволяет считать наличие

слабых ключей в DES скорее оригинальной особенностью, чем реальной

уязвимостью.

Хотя за много лет DES зарекомендовал себя надежным шифром, ему

пришлось уйти с рынка конкурентоспособных шифров. Это стало следствием его

ориентации на аппаратную реализацию и слишком малый размер ключа.

Стремительный взлет мощности вычислительной техники внес значительные

коррективы в направления развития криптографии. Наиболее простым

представителем семейства программно-ориентированных надежных блочных

шифров является TEA (Tiny Encryption Algorithm). Перевод этого названия на

русский язык может выглядеть как "крохотный криптоалгоритм". TEA — это

классическая сеть Файштеля из 64 раундов. Алгоритм оптимизирован под 32-

разрядный микропроцессор, размер блока — 64 бита.

218

Результат полученной функции накладывается на независимую ветвь

операцией "Сложение", поэтому восстановить исходный текст простым об-

ращением порядка ключей раунда не удается. Таким образом, алгоритм TEA

является примером несимметричной сети Файштеля, в которой для дешиф-

рования требуется реализовать отдельную достаточно простую процедуру. [16]

Существует также TEA: расширение ключа. Этот алгоритм использует 128-

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

Ключ разбивается на четыре 32-разрядных машинных слова

3210

,,, kkkk

. Во всех

четных (считая с 0) раундах в качестве 64-битного ключа раунда используется

пара (

,kk

), в нечетных — пара (

,kk

). В общепринятой схеме номер раунда

обозначается переменной i, количество раундов — r, компоненты ключа раунда

— как массив k[] (он использует проходную нумерацию по машинным словам —

в нулевом раунде используется k[0] и k[1], в первом — k[2] и k[3] и т.д.). В этом

случае общая формула создания 128 компонентов материала ключа для TEA

имеет следующий вид:

k[i] = k(i mod 4)

Алгоритм, который был разработан на смену DES, и, в отличие от TEA,

получил широкое применение, носит название IDEA (International Data

Encryption Algorithm — международный алгоритм шифрования данных). Пра-

вами на этот алгоритм владеет Швейцарский федеральный технологический

институт ETHZ (Swiss Federal Institute of Tehnology Zurich) и компания Ascom

Tech Ltd.

Алгоритм IDEA построен по схеме, которая похожа на сеть Файштеля и носит

название обобщенной сети Файштеля. Исходный блок данных длиной в 64 бита

разбивается на 4 ветви — все операции в IDEA выполняются в 16-битной

арифметике. Затем в каждом из 8 раундов над ветвями и материалом ключа

выполняется в специально подобранной очередности три операции сложения,

исключающее ИЛИ и модифицированное умножение. Модифицированное

умножение обозначают на схемах символом "*". Длина ключа алгоритма

составляет 128 бит.

Модифицированное умножение представляет собой обычное умножение по

модулю 65537 (2

+1) с двумя условиями. Во-первых, если какой-либо из

множителей равен 0, то перед умножением он заменяется на 2

. Во-вторых, если

число после взятия модуля равно 2

, то оно заменяется на 0.

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

■ отображает пару 16-разрядных чисел на 16-разрядное число;

■ обратима (по известному результату и одному из множителей возможно

однозначно определить второй множитель).

Для достижения симметричности шифрования/дешифрования после восьми

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

такого дополнения разработчики добились того, что для дешифрования в IDEA

используется та же самая процедура, однако в качестве 52 компонентов

материала ключа ей передаются специальным образом модифицированные

компоненты.

219

Далее кратко остановимся на единственном из официально изданных со-

ветских блочных шифров, который со временем был раскрыт и заменен более

современным. Этот ГОСТ 28147-89 в 1989 году был принят государственным

стандартом блочного шифрования и использовался многими специалистами по

защите информации. [16]

ГОСТ 28147-89 оперирует 64-битным блоком данных, осуществляя шиф-

рование с помощью 256-битного ключа. Структура криптоалгоритма пред-

ставляет собой классическую сеть Файштеля из 32 раундов с двумя ветвями.

Расширение ключа выполняется по очень простой схеме. 256-битный ключ

разбивается на восемь 32-битных машинных слов. Они нумеруются с

по

32 компонента материала ключа применяются в следующем порядке:

К[0]...К[31] = К

...К

... К

В последней, четвертой секции 8 машинных слов ключа записывают в

обратном порядке. Для дешифрования (по особенностями симметричной сети

Файштеля) используют тот же код, однако в обратном порядке ключей раунда.

Недостаточная длина ключа DES, его ориентация на аппаратную реализацию

и, как следствие, использование на практике большого количества

малоизвестных криптоалгоритмов вынудило правительство Соединенных Шта-

тив объявить конкурс на криптостандарт блочного шифрования начала нового

века. Конкурс получил название AES (Advanced Encryption Standard) -

"улучшенный стандарт шифрования".

Требования к новому стандарту были следующими:

■ шифр должен быть блочным;

■ шифр должен иметь длину блока, равную 128 битам;

■ шифр должен поддерживать ключи длиной 128, 192 и 256 бит.

Победителем стал алгоритм RIJNDAEL. Этот блочный шифр развивает

нетрадиционную для последнего десятилетия структуру: прямоугольные

KASLT-сети. Эта структура получила свое название из-за того, что шифруемый

блок представлен в виде прямоугольника (4x4 или 4x6 байт), и затем над ним

построчно, по столбцам и побайтно выполняются криптопреобразования. [16]

KASLT — это аббревиатура английских терминов Key Addition (сложение

ключа), Substitution (табличная подстановка) и Linear Transposition (линейное

перемешивание). Это — шифр с вариативным размером блока и длиной ключа.

Единственное требование к этим параметрам: их кратность 32 битам. Размер

блока в дальнейшем определяется как Nbx32, длина ключа — как Nkx32.

Количество раундов сети, необходимых для устойчивого шифрования, зависит

от этих двух параметров.

Согласно требованиям Nb = 4 (то есть, 4x4 байта), однако потенциально шифр

может работать и с большими по размеру блоками.

Перед началом раундов KASLT-сети на блок накладывается операцией XOR

первая порция материала ключа. Раунды, кроме последнего, состоят из

повторения четырех операций: табличной подстановки, циклического сдвига

строк, линейного перемешивания столбцов и сложения материала ключа. В