Системы блочного шифрования

УДК 519.1(075.8)
ББК 22.176
Ж85
Рецензенты: М.А. Басараб, С.В. Запечников
Ж85
Жуков А. Е.
Системы блочного шифрования : учеб. пособие по курсу
«Криптографические методы защиты информации» / А. Е. Жуков. — М. : Изд-во МГТУ им. Н. Э. Баумана, 2013. — 77, [3] с. :
ил.
ISBN 978-5-7038-3753-5
Рассмотрены основные понятия, используемые для описания работы блочных шифров, примеры типовых узлов, входящих в их конструкцию, а также наиболее распространенные схемы построения
блочных шифров. Для большинства вводимых терминов приведены
соответствующие англоязычные эквиваленты.
Для студентов кафедры ИУ-8 МГТУ им. Н.Э. Баумана, изучающих
курс «Криптографические методы защиты информации».
УДК 519.1(075.8)
ББК 22.176
ISBN 978-5-7038-3753-5
c
⃝МГТУ им. Н.Э. Баумана, 2013

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ
И ОПРЕДЕЛЕНИЯ КРИПТОГРАФИИ
Криптография является разделом прикладной математики, связанным с алгоритмами, схемами и протоколами, выполняющими
определенные задачи по обеспечению информационной безопасности при противодействии злоумышленника (нарушителя).
В последние десятилетия значение криптографии в жизни мирового социума существеннейшим образом возросло. Это произошло в результате появления и развития электронных носителей
данных, сетей связи, в том числе и глобальных, таких как Интернет, мобильных средств связи и электронной торговли. В наши
дни криптографические устройства входят в конструкцию многочисленных товаров массовой электронной продукции. Криптографические модули используют для осуществления аутентификации и шифрования (в конструкции банковских кредитных карт,
мобильных телефонов, при организации электронной торговли и
платных телевизионных каналов), контроля доступа (например,
в автомобильных противоугонных системах), системах платежей
(телефоны-автоматы или банкоматы) и т. д. Овладение механизмами криптографической защиты стало необходимым требованием
для современных инженеров в области информационных технологий.
Основными понятиями, лежащими в основе современных математических моделей в криптографии, являются понятия однонаправленной функции и однонаправленной функции с лазейкой.
Эти понятия являются фундаментальными не только для асимметричной криптографии, как принято думать, но и для всей криптографии в целом, включая классическую.
3

Однонаправленные функции
Функция f : X →Y называется однонаправленной (one-way
function), если для всех x ∈X можно легко вычислить ее значение
f(x), но в то же время для почти всех элементов y ∈Im(f) вычислительно трудно найти какой-либо элемент x ∈X, для которого
f(x) = y.
Однонаправленной функцией с лазейкой (trapdoor one-way
function) называется однонаправленная функция f : X →Y
со
следующим дополнительным свойством: если известна некоторая
дополнительная информация, называемая лазейкой (trapdoor), то
для любого элемента y ∈Im(f) можно эффективно найти такой
элемент x ∈X, что f(x) = y.
В разных математических моделях эти понятия нуждаются в
уточнении: что означает «легко», «трудно», «эффективно», «почти
для всех». Однако в данной работе ограничимся приведенными
выше нестрогими определениями.
По сути вся криптография базируется на понятии однонаправленности. Математическую основу криптографических алгоритмов образуют преобразования трех основных типов. Все они
являются однонаправленными функциями того или иного вида
(хотя в работе конкретных криптосистем могут использоваться и
другие математические преобразования и функции).
Обратимые криптографические преобразования
Обратимые
криптографические
преобразования
позволяют
обеспечить секретность, аутентификацию и целостность информации. Идея, лежащая в основе использования таких преобразований, состоит в применении к защищаемой информации некоторого
сложного преобразования. Основная задача такого преобразования — сделать информацию нечитаемой при несанкционированном
доступе.
Как правило, обратимое преобразование E : P →C применяется к открытому тексту x ∈P, где P — пространство открытых
текстов. Преобразование E зачастую называют шифрующим преобразованием, преобразованием шифрования или просто шифром;
4

результат этого преобразования E(x) = y ∈C — шифртекстом,
а множество C — пространством шифртекстов. Для того чтобы восстановить исходную информацию x, применяется обратное
преобразование D : C →P, D = E−1; тогда исходная информация
x = D(y) = E−1(y). По аналогии с E преобразование D называют
преобразованием расшифрования.
Для нарушителя, которому неизвестно преобразование D,
шифртекст y должен выглядеть как бессмысленный набор знаков; в идеале нарушитель, перехвативший шифртекст y, не должен
получить даже части исходной информации x ([4]). Таким образом, основным требованием к преобразованию Е является то,
что оно должно быть однонаправленной функцией. В этом случае преобразование E называют обратимым криптографическим
преобразованием.
Обратимые криптографические преобразования с ключом
Важнейшим для криптографии случаем являются обратимые
криптографические преобразования с ключом. Рассмотрим отображение E : P × K →C, где K — конечное множество, называемое
ключевым пространством, P и C — как и выше, пространство открытых текстов и шифртекстов. Отображение E можно рассматривать как семейство обратимых отображений {Ee : P →C, е ∈K},
определяемых параметром е ∈K — ключом шифрования. Множество обратных отображений объединяется в семейство отображений {Dd : C →P, d ∈K′}, определяемых параметром d, называемым ключом расшифрования. При этом для каждого е ∈K (ключа
шифрования) существует такой d ∈K′ (ключ расшифрования), что
Dd (у) = Dd (Ее (х)) = х для всех x ∈P.
Параметры e и d, задающие соответствующие пары взаимнообратных преобразований, образуют пары (е, d) (ключ шифрования — ключ расшифрования). Если при расшифровании используется ключ d′, отличный от истинного ключа расшифрования d,
получается случайный текст x′, существенно отличающийся от истинного текста x. Из этого следует, что отображение Ее является
однонаправленной функцией с лазейкой, причем роль лазейки выполняет ключ расшифрования d.
5

Таким образом, основное требование к преобразованию Ее —
оно должно быть однонаправленной функцией с лазейкой относительно преобразования х в у, при этом роль лазейки исполняет
ключ расшифрования d. В этом случае преобразование Ее называют обратимым криптографическим преобразованием с ключом.
Симметричные и асимметричные обратимые криптографические преобразования с ключом. Все обратимые криптографические
преобразования с ключом подразделяются на два класса: симметричные и асимметричные.
Если ключ расшифрования d обратимого криптографического преобразования совпадает с ключом шифрования e (и тогда
K = K′) или может быть легко получен из e, преобразование называют симметричным криптографическим преобразованием. Если же ключи шифрования и расшифрования различны, более того, вычислительно трудно получить один ключ из
другого, то соответствующее преобразование называют асимметричным криптографическим преобразованием. Соответственно
криптосистему,
использующую
обратимое
криптографическое
преобразование, называют в первом случае симметричной криптосистемой (криптосистемой с секретным ключом, одноключевой криптосистемой), а во втором — асимметричной криптосистемой (криптосистемой с открытым ключом, двуключевой
криптосистемой).
Использование криптографических преобразований с ключом
дает возможность сделать алгоритм шифрования E и алгоритм
расшифрования D открытыми (несекретными); стойкость криптосистемы будет основываться на секретности ключей (обоих в случае симметричной криптосистемы и только одного в случае асимметричной криптосистемы). Этот подход составляет суть принципа Керкхоффа (Kerckhoffs’s principle): стойкость криптосистемы
должна обеспечиваться секретностью используемых ключей, а не
секретностью самих алгоритмов шифрования и расшифрования. В
частности, для асимметричной криптосистемы ключ шифрования
можно сделать открытым (известным всем участникам информационного процесса), что позволяет решить проблему распределения ключей, являющуюся одним из узких мест для больших информационных сетей.
6

Необратимые криптографические преобразования
В глобальном смысле основная задача таких преобразований —
обеспечение целостности информации. При этом они осуществляют преобразование сжатия информации, отображая последовательность произвольной, но конечной длины в последовательность
фиксированной длины (digest).
Пусть A — конечное множество (конечный алфавит), обозначим
Am = A × . . . × A; элементами множества Am являются все упорядоченные наборы длиной m, образованные элементами множества A. Обозначим через A∗=
∞
∪
m=0 Am множество упорядоченных
наборов произвольной длины, образованных элементами множества A.
Рассмотрим отображение
h : A∗→H = An.
Отображение h может обладать следующими свойствами:
1) однонаправленностью (one-wayness, preimage resistance): для
почти всех значений y ∈H вычислительно трудно найти хотя бы
один такой элемент x′ ∈A∗, что h(x′) = y (y может быть получен
из неизвестного нам x, не обязательно совпадающего с x′);
2) слабой устойчивостью к коллизиям (weak collision resistance,
2nd-preimage resistance): если задан произвольный элемент x ∈A∗,
вычислительно трудно найти еще один такой элемент x′ ∈A∗,
x′ ̸= x, что h(x′) = h(x);
3) сильная устойчивость к коллизиям (strong collision resistance,
collision resistance): вычислительно трудно найти два разных элемента x, x′ ∈A∗, x′ ̸= x, для которых h(x′) = h(x) (здесь в отличие
от предыдущего пункта мы независимы в выборе элементов x и x′).
Отображение называют необратимым криптографическим,
если оно в обязательном порядке удовлетворяет свойству 1, т. е.
является однонаправленной функцией, и, возможно, удовлетворяет
свойствам 2 и 3.
7

Криптографические генераторы псевдослучайных
последовательностей
Во многих криптографических примитивах используют генераторы псевдослучайных чисел. Обычным требованием к генераторам псевдослучайных чисел является статистическая неотличимость порожденных ими последовательностей от случайных равновероятных; для проверки этого разработаны многочисленные
статистические тесты. Криптографические генераторы псевдослучайных последовательностей, кроме того, должны обеспечивать
и непредсказуемость — невозможность предсказания очередного
знака выходной последовательности, порождаемой криптографическим генератором с вероятностью, существенно отличной от
равновероятной, даже если нарушителю известны все предыдущие
знаки этой последовательности.
Генератором псевдослучайных последовательностей называют отображение
R : Ak →AT ,
которое отображает последовательность длины k элементов множества A в последовательность длины T ≫k элементов того же
множества. Аргумент отображения R называют входом генератора (seed), образ R — выходом генератора, или псевдослучайной
последовательностью.
Генератор псевдослучайных последовательностей R называется криптографическим генератором псевдослучайных последовательностей, если он удовлетворяет следующим свойствам:
– выходная последовательность должна «выглядеть» cлучайной, т. е. генератор должен проходить все известные статистические тесты на случайность;
– генератор должен быть непредсказуемым, т. е. обеспечивать
невозможность вычислительно предсказывать значение очередного знака выходной последовательности с вероятностью, существенно отличной от равновероятной, даже при знании алгоритма
выработки выходной последовательности и значений ее предыдущих знаков.
Из последнего свойства следует, что такое отображение R является однонаправленной функцией.
8