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

Очевидно, что при выполнении алфавитных подстановок двухбуквенных пар (биграмм) на другие двухбуквенные пары, частотный анализ становится уже достаточно сложной задачей. В том случае, когда по некоторому закону изменяются наборы из 4, 8 или даже 16 символов, ни про какое частотное раскрытие шифров речи идти не может - объем шифротекста, необходимого для такой атаки, растет экспоненциально. Проблема, из-за которой такие схемы не были применены раньше, заключалась в отсутствии надежного и простого в применении алгоритма преобразований, который, в идеале, к тому же, зависит только от ключа шифрования. [16]

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

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

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

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

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

Перечень наиболее приемлемых преобразований и их условные обозначения на схемах представлен в табл. 5.2.

Таблица 5.2. Наиболее приемлемые преобразования и их условные обозначения на схемах

Несколько слов о табличных подстановках, занимающих отдельное место в криптографических преобразованиях... С помощью табличных подстановок (англ. "Substitute-box-S-box") реализуют наиболее общие законы изменения данных, которые часто не воспроизводятся ни аналитически, ни алгоритмически. В тех случаях, когда в шифрующем алгоритме необходимо реализовать функцию, которая достаточно сложна для микропроцессора или вообще не описывается алгоритмом, наиболее приемлемым решением является занесение ее значения в массив, хранимый в постоянной или оперативной памяти. Такое задание функции называют табличным.

Количество битов в исходном операнде называют разрядностью входа табличной подстановки, количество битов в результате - разрядностью выхода. В большинстве случаев табличные подстановки используются в качестве биэктивной (однозначно обратимой) функции - в этом случае разрядность входа и выхода совпадают. Чаще всего по такой схеме используются подстановки 4x4 (четыре на четыре) бита, 8x8 бит.

Обратное преобразование (S - Вох-1), если в нем есть необходимость, задают дешифрующей стороне также таблицей такого же размера. В том случае, когда от подстановок не требуют обратимости, вместе с традиционными применяются подстановки 4x8, 8x32 и некоторые другие.

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

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

Одним из неоспоримых преимуществ табличных подстановок является скорость в отношении к нелинейным операциям. Практически все представленные в табл. 5.2 операции, кроме умножения по модулю 2N+1 и табличных подстановок, имеют очень высокую линейную зависимость между входными и выходными значениями, а это очень плохо в смысле криптоустойчивости шифра к линейному криптоанализу. Для повышения устойчивости шифра к этому классу атак табличная подстановка намного лучше операции умножения по модулю 2n+1 , и на сегодняшний день она является наиболее приемлемым нелинейным преобразованием.

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

Таблица 5.3. Основные необратимые криптопримитивы

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

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

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

Не существует аналитической формулы, которая бы вычисляла К через X и X. Конечно, всегда можно составить табличную зависимость, перебрав при известном X все K и записав все полученные X, однако это легко сделать только в гипотетическом примере из 16 возможных значений. На практике, при длине ключа в 128 бит для решения этой задачи не хватит ни ресурсов памяти для хранения, ни вычислительных возможностей ЭВМ. Таким образом, многократное сложение материала ключа по сложной схеме является надежным средством защиты блочных шифров от атаки по известным парам "открытый/зашифрованный текст".

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

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

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

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

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

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

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

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

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

Одной из наиболее простых и ранних сетей является SP-сеть (SP-network), каждый раунд которой состоит из двух слоев. Свое название эта сеть получила от сокращения английских слов "substitution" (подстановка) и "permutation" (перестановка). В слое подстановки над данными выполняются преобразования класса сложения, исключающего ИЛИ, табличных подстановок, в качестве параметров используются константы и материал ключа. В слое перестановки биты (или изредка байты) меняются местами внутри блока обычно по фиксированной (независимой от ключа) схеме.

Более современной модификацией технологии сетей является KASLT - сеть с тремя слоями в каждом раунде. Первый слой - сложение ключа (Key Addition, KA) - выполняет смешивание данных с ключом раунда. Смешивание выполняется обычно какой-нибудь простой операцией: сложением или XOR. Второй слой - подстановка (Substitution, S) - выполняет алгоритмическую или чаще табличную подстановку для обеспечения нелинейных качеств шифра. Третий слой - линейное преобразование (Linear Transformation, LT) - выполняет активное обратимое смешивание данных внутри блока.

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

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

Независимые потоки информации, порожденные из исходного блока, носят название ветки сети. В классической схеме их две. Величины V1 носят название параметров сети. Обычно их роль выполняют материалы ключа. Функция F носит название образующей. Оптимальное количество раундов для сети Файштеля К - от 8 до 32. [16]

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

Более того, сеть Файштеля, в которой для наложения значения F используются операция XOR, симметричная. Исключающие ИЛИ обратимые своим же повторением, и потому инверсия последнего обмена веток делает возможным декодирование блока той же сетью Файштеля, но с обратным порядком параметров VI.

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

С незначительными доработками сеть Файштеля можно сделать и абсолютно симметричным шифром, то есть, таким, который выполняет функции шифрования и дешифрования одним и тем же набором операций. Модификация сети Файштеля с такими свойствами представлена на рис. 5.14.

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

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

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

Далее рассмотрим практику блочного шифрования в хронологическом порядке с начала его разработки в 70-х годах прошлого столетия. В 1980 году в США был принят национальный стандарт шифрования данных DES (Data Encryption Standard). Алгоритм работы этого стандарта представляет собой классическую сеть Файштеля из 16 раундов с добавлением входной и выходной перестановки битов, с разрядностью блока 64 бита и размерами ключа 56 бит. Общая структура этого алгоритма представлена на рис. 5.15.

Расширения входных данных выполняются на уровне битов путем записи некоторых из них в выходной поток дважды. В результате из 32 битов образуется 48-битный блок информации, совпадающий по размеру с ключом раунда. Наложение ключа раунда выполняется операцией XOR с разрядностью операции 48 бит.

Табличные подстановки, применяемые в DES, имеют разрядность 6x4 бит. 48битный блок данных после наложения ключа разбивается через свою табличную подстановку, которая обозначается как S0, S1 и т.д. В результате получаем 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 (они являются контрольными, то есть, незначащими).

Для генерации каждого очередного ключа раунда ki векторы Со и Do циклически сдвигаются влево на определенное количество разрядов. Для выбора 48

бит ключа i-го раунда, который был получен после циклического сдвига вектора CiDi, объединяются, и из 56 битов полученного массива отбирают по отдельному закону 48.

Анализируя принцип шифрования в DES, бросается в глаза значительное количество битовых перестановок и выборок в алгоритме. И, это не удивительно, потому что основной схемой проектировщиками планировалась только аппаратная реализация. Этому подчинено и наложение ключа именно операцией XOR, которая реализуется в этом случае наиболее просто и распараллелено, с небольшим размером и минимальным количеством табличных подстановок. Аппаратная реализация алгоритма в отдельной или встроенной микросхеме позволяет добиться большой скорости шифрования при достаточно малых устройствах. [16]

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

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

Стремительный взлет мощности вычислительной техники внес значительные коррективы в направления развития криптографии. Наиболее простым представителем семейства программно-ориентированных надежных блочных шифров является TEA (Tiny Encryption Algorithm). Перевод этого названия на русский язык может выглядеть как "крохотный криптоалгоритм". TEA - это классическая сеть Файштеля из 64 раундов. Алгоритм оптимизирован под 32разрядный микропроцессор, размер блока - 64 бита.

Алгоритм IDEA построен по схеме, которая похожа на сеть Файштеля и носит название обобщенной сети Файштеля. Исходный блок данных длиной в 64 бита разбивается на 4 ветви - все операции в IDEA выполняются в 16-битной арифметике. Затем в каждом из 8 раундов над ветвями и материалом ключа выполняется в специально подобранной очередности три операции сложения, исключающее ИЛИ и модифицированное умножение. Модифицированное умножение обозначают на схемах символом "*". Длина ключа алгоритма составляет 128 бит.

Модифицированное умножение представляет собой обычное умножение по модулю 65537 (216+1) с двумя условиями. Во-первых, если какой-либо из множителей равен 0, то перед умножением он заменяется на 216. Во-вторых, если число после взятия модуля равно 216, то оно заменяется на 0.

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

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

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

Для достижения симметричности шифрования/дешифрования после восьми раундов над ветвями выполняется дополнительное преобразование. С помощью такого дополнения разработчики добились того, что для дешифрования в IDEA используется та же самая процедура, однако в качестве 52 компонентов материала ключа ей передаются специальным образом модифицированные компоненты.

Далее кратко остановимся на единственном из официально изданных советских блочных шифров, который со временем был раскрыт и заменен более современным. Этот ГОСТ 28147-89 в 1989 году был принят государственным стандартом блочного шифрования и использовался многими специалистами по защите информации. [16]

ГОСТ 28147-89 оперирует 64-битным блоком данных, осуществляя шифрование с помощью 256-битного ключа. Структура криптоалгоритма представляет собой классическую сеть Файштеля из 32 раундов с двумя ветвями.

В последней, четвертой секции 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 первая порция материала ключа. Раунды, кроме последнего, состоят из повторения четырех операций: табличной подстановки, циклического сдвига строк, линейного перемешивания столбцов и сложения материала ключа. В

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

Наложение материала ключа выполняется операцией XOR. Материал извлекается из массива расширенного ключа К последовательно по четыре 32битных блока в каждом раунде. При наложении ключа прямоугольная матрица рассматривается как 4 столбца с 32-битными записями в каждом (см. рис. 5.18).

Табличная подстановка 8x8 бит выполняется с помощью одной таблицы S над каждым из 16 байтов независимо. После подстановки каждый байт помещается на свое исходное место в прямоугольной матрице (рис. 5.19).

Подстановка S имеет алгоритмическую запись, однако в большинстве случаев ее удобнее хранить уже вычисленной в виде массива из 256 байтов.

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

Поточные шифры | Защита информации в телекоммуникационных системах | Асимметричная криптография и цифровая подпись


Защита информации в телекоммуникационных системах



Новости за месяц

  • Ноябрь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс