Криптографические конструкции на основе функций многозначной логики

КРИПТОГРАФИЧЕСКИЕ 
КОНСТРУКЦИИ 
НА ОСНОВЕ ФУНКЦИЙ 
МНОГОЗНАЧНОЙ 
ЛОГИКИ

А.В. СОКОЛОВ
О.Н. ЖДАНОВ

Москва
ИНФРА-М
2020

МОНОГРАФИЯ

УДК 004.056(075.4)
ББК 32.973
 
С59

Соколов А.В.
С59  
Криптографические 
конструкции 
на 
основе 
функций 
многозначной логики : монография / А.В. Соколов, О.Н. Жданов. —
Москва : ИНФРА-М, 2020. — 192 с. — (Научная мысль). — 
DOI 10.12737/1045434.

ISBN 978-5-16-015667-5 (print)
ISBN 978-5-16-108056-6 (online)
Симметричные алгоритмы шифрования успешно применяются для 
защиты информации при передаче по открытому каналу. Классическим 
подходом к синтезу современных криптоалгоритмов и криптографических примитивов, на которых они основаны, является применение математического аппарата булевых функций. Авторы монографии показывают, что использование для решения этой задачи функций многозначной 
логики (ФМЛ) позволяет во многом улучшить стойкость криптоалгоритмов и расширить выбор используемых алгебраических конструкций. 
С другой стороны, изучение функций многозначной логики в криптографии ведет к лучшему пониманию принципов работы криптографических 
примитивов и появлению новых методов описания криптографических 
конструкций. 
В монографии приведены результаты теоретических и экспериментальных исследований свойств ФМЛ, представлены алгоритмы построения 
высококачественных S-блоков для симметричных алгоритмов шифрования, а также полноценные работоспособные образцы криптоалгоритмов, 
готовые к практической реализации.
Для студентов и преподавателей, а также всех интересующихся вопросами защиты информации.

УДК 004.056(075.4)
ББК 32.973

ISBN 978-5-16-015667-5 (print)
ISBN 978-5-16-108056-6 (online)
© Соколов А.В., Жданов О.Н., 
2020

Р е ц е н з е н т ы:
Быкова В.В., доктор физико-математических наук, доцент, профессор кафедры высшей и прикладной математики Сибирского федерального университета;
Казакова Н.Ф., доктор технических наук, заведующий кафедрой 
автоматизированных систем и кибербезопасности Одесской государственной академии технического регулирования и качества

Введение

Как известно, в настоящее время происходит интенсивное развитие информационных технологий. В частности, широкое распространение получила передача данных различного назначения по открытому (незащищенному) каналу. При этом актуальной является 
задача обеспечение конфиденциальности передаваемых данных.
Указанная задача решается применением блочных симметричных криптографических алгоритмов. Построение современных 
блочных симметричных шифров предусматривает итеративное использование криптографических примитивов. К таким криптографическим примитивам относятся следующие:
 
• Г-блок гаммирования;
 
• S-блок подстановки (блок замен, таблица замен);
 
• P-блок перестановки;
 
• Z-блок циклических сдвигов;
 
• A-блок аффинного (линейного) преобразования.
Сегодня уже общепризнано, что важнейшим компонентом любого блочного симметричного криптоалгоритма, обеспечивающим 
эффективность всего криптопреобразования, является S-блок.
Имеются два подхода к использованию S-блоков. Блоки замен 
можно выбрать один раз и сделать общими для всех пользователей 
данного алгоритма. Примерами являются алгоритмы AES, DES 
и подобные. Второй подход предполагает выбор каждой парой 
пользователей своего, секретного набора блоков замен. Примером 
реализации такого подхода является алгоритм ГОСТ 28147–89. 
Такой подход обеспечивает бо льшую гибкость криптоалгоритма 
и позволяет оперативно менять выбранные блоки замен, например, 
при появлении новых или обновлении существующих критериев 
криптографического качества. Сегодня к таким критериям криптографического качества относят следующие:
1. Алгебраическая степень нелинейности.
2. Расстояние нелинейности.
3. Корреляционная взаимосвязь выхода и входа S-блока:
a. максимум модуля элементов матрицы коэффициентов корреляции между выходными и входными векторами;
b. количество нулевых элементов в матрице коэффициентов 
корреляции.
4. Коэффициент распространения ошибки.
5. Периоды возврата S-блока в исходное состояние.
Все приведенные критерии явились результатом изучения реальных атак криптоанализа и, так или иначе, характеризуют качество реализации S-блоком двух базовых, введенных К. Шен

ноном, принципов шифрования — диффузии и конфузии. Данные 
показатели характеризуют, соответственно, уровень равномерности 
рассеивания избыточности входного текста по элементам шифртекста и уровень сложности взаимосвязей между элементами открытого текста, ключа и шифртекста. Поиск математических конструкций, обеспечивающих в криптоалгоритме высокий уровень 
диффузии и конфузии, продолжается, в этом направлении еще есть 
нерешенные задачи.
В связи с этим интересными являются результаты в области 
функций многозначной логики. Переход от двоичной логики к многозначной открывает новые возможности.
Так, например, при исследовании блока замен обычно представляют его в виде набора булевых функций. Мы далее показываем, 
что высокое криптографическое качество S-блока с точки зрения 
двоичной логики не всегда гарантирует его высокое криптографическое качество с точки зрения функций многозначной логики.
Например, S-блок, являющийся оптимальным с точки зрения 
строгого лавинного критерия в двоичном (булевом) смысле, вполне 
может быть неоптимальным с точки зрения строгого лавинного 
критерия в четверичном смысле.
Поскольку криптоаналитик может использовать потенциальную 
слабость такого S-блока, при конструировании криптоалгоритмов 
должен быть проведен всесторонний анализ криптографического 
качества, в том числе и с помощью функций многозначной логики. 
А это требует развития и обобщения теории и практики криптографии на пространство функций многозначной логики.
Отметим также, что использование функций многозначной 
логики (ФМЛ) в криптографии может быть полезным не только 
с точки зрения усовершенствования современных двоичных криптоалгоритмов, но является основой построения нового класса криптоалгоритмов многозначной логики, превышающих по качеству 
реализации концепций диффузии и конфузии свои двоичные аналоги.
Еще одним важным аргументом применения ФМЛ является 
соответствие реализуемой сегодня парадигме построения многоядерных процессорных устройств. Наконец, интересны перспективы 
соединения ФМЛ с квантовыми криптоалгоритмами.

Глава 1
АЛГЕБРАИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ 
БЛОКОВ ЗАМЕН

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

 

0
1

0
1

N

N
y
y
−

⎛
⎞
−
⎜
⎟
⎝
⎠

, 
 (1.1)

где первая строка —последовательность чисел от 0 до 
1
N − , вторая 
строка — последовательность {
}
iy
, состоящая из элементов первой 
строки, переставленных по заданному конструкторами S-блока закону. Нижнюю строку подстановки (1.1) назовем кодирующей последовательностью и обозначим 
{
}
i
Q
y
=
 [3].
Определение 1.1 [4]. S-блок подстановки называется биективным, если его Q-последовательность содержит все элементы последовательности 0,1,...,
1
N − .
Как известно, количество подстановок из N  элементов равно 
!
N .
Таким образом, число различных структур Q-последовательностей стремительно растет с ростом длины 
.
В современных криптоалгоритмах S-блоки могут использоваться и как самостоятельные элементы, и как части конструкций, 
которые называются таблицами замен. Строки таблицы замен называются узлами замен.
Техническая реализация S-блоков классических криптоалгоритмов состоит из дешифратора, который преобразует k-разрядный 
двоичный сигнал в одноразрядный сигнал по модулю 2k , системы 
внутренних связей (всего связей должно быть 2k ) и шифратора, 

который преобразует сигнал из одноразрядного 2k -ичного в k -разрядный двоичный (риc. 1.1).

Риc. 1.1. Реализация S-блока длины 
16
N =

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

1.1. ХАРАКТЕРИСТИКИ УСТОЙЧИВОСТИ ДВОИЧНЫХ БЛОКОВ 
ЗАМЕН К КРИПТОАНАЛИЗУ

Для количественного анализа устойчивости криптопреобразования используется их представление в виде структур, состоящих 
из булевых функций.
Кратко представим основные понятия и конструкции.
Определение 1.2 [6]. Булевой функцией называется отображение {0,1}
{0,1}
k →
, т.е. правило, сопоставляющее вектору из k  бит 
значение 0 или 1.
Рассмотрим способы задания булевой функции: табличный, векторный, аналитический.

1.1.1. Табличный способ определения булевых функций
Функция определяется таблицей, каждая строка которой задает 
значение функции при определенном наборе значений входных переменных. Число строк такой таблицы равно 2k .
Пример 1.1.
Булева функция (
)
0
1
2
,
,
f x
x x
 может быть задана следующей таблицей (табл. 1.1).

Таблица 1.1
Табличный способ задания булевой функции

x2
x1
x0
f(x0, x1, x2)

0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1

1.1.2. Векторный способ определения булевых функций
Функция задается в виде вектора, состоящего из значений булевой функции, выписанных в порядке возрастания аргумента, если 
его представить в виде числа от 0 до 2k–1. В самом деле, вместо k логических переменных x0, x1, ..., xk–1 в качестве аргумента функции 
можно использовать k-битное целое число

 

1
2
1
0
1
2
1
0
2
2
2
2 .

k
k
i
k
i
i
x
x
x
x
x
x

−
−
−
=
=
+
⋅ +
⋅
+
+
⋅
=
⋅
∑
(1.2)

Функция из Примера 1.1 в векторном виде будет представлена 
следующим образом: f(x0, x1, x2) = (01101001) (последний столбец 
табл. 1.1 выписан сверху вниз).

1.1.3. Аналитический способ определения булевых функций
Функция задается в виде формулы, выражающей зависимость 
значения функции от значений ее аргументов.
Функцию из Примера 1.1 в аналитическом виде можно представить следующим образом

 
(
)
0
1
2
0
1
2
,
,
f x x x
x
x
x
=
⊕
⊕
, 
 (1.3)

где ⊕  — операция сложения бит по модулю 2 (XOR).

Определим некоторые необходимые нам понятия [7].
Определение 1.3. Весом булевой функции называется количество наборов значений входных переменных, при которых она 
принимает значение 1. Иными словами, это число единиц в векторном представлении булевой функции. Так, вес функции из Примера 1.1 равен 4 (так как из 8 бит в векторе (01101001) — 4 единицы). Обозначается wt(f), например wt(01101001)=4.
Определение 1.4. Расстоянием между двумя булевыми функциями d(f1, f2) называется вес их побитовой суммы по модулю 2 
в векторном виде (число позиций в векторах, в которых значения 
функции различны).
Определение 1.5 [8]. Линейной называется булева функция 
аналитического вида

 
(
)

1

0
1
0
0
1 1
1
1
0
,
,
,

k

k
k
k
i
i
i
f x
x
a x
a x
a
x
a x

−

−
−
−
=
…
=
⊕
⊕…⊕
=∑
  (1.4)

где 
{
}
0
1
1
,
,...,
0,1
k
a a
a − ∈
 — произвольные логические значения 
(0 или 1). Множество всех линейных функций от k  переменных 
обозначим Lk.
Пример 1.2.
Построим все линейные булевы функции 2 переменных. 
Для этого нужно перебрать все различные комбинации битов 

{
}
0
1
,
0,1
a a ∈
:
1. 
(
)
0
1
0
1
0
0
1 1
0,
0
,
0
a
a
f x x
a x
a x
=
=
⇒
=
⊕
=
, или в векторном 
виде 
(
)
(
)
0
1
,
0000
f x x
=
.
2. 
(
)
0
1
0
1
0
0
1 1
0
1,
0
,
a
a
f x x
a x
a x
x
=
=
⇒
=
⊕
=
, или в векторном 
виде 
(
)
(
)
0
1
,
0101
f x x
=
.
3. 
(
)
0
1
0
1
0
0
1 1
1
0,
1
,
a
a
f x x
a x
a x
x
=
= ⇒
=
⊕
=
, или в векторном 
виде 
(
)
(
)
0
1
,
0011
f x x
=
.
4. 
(
)
0
1
0
1
0
0
1 1
0
1
1,
1
,
a
a
f x x
a x
a x
x
x
=
= ⇒
=
⊕
=
⊕
, или в векторном 
виде 
(
)
(
)
0
1
,
0110
f x x
=
.
Таким образом, множество линейных функций от 2 переменных  

(
) (
) (
) (
)
{
}
2
0000 ; 0101 ; 0011 ; 0110
=
L
.

Определение 1.6 [2]. Аффинной называется булева функция 
аналитического вида

 
(
)

1

0
1
0
0
1 1
1
1
0
,
,
,

k

k
k
k
i
i
i
f x
x
a x
a x
a
x
b
a x
b

−

−
−
−
=
…
=
⊕
⊕…⊕
⊕
=
⊕
∑
 (1.5)

L

,

,

,

,

где 
{
}
0
1
1
,
,...,
,
0,1
k
a a
a
b
−
∈
 — произвольные логические значения. 
Множество всех аффинных функций от k переменных обозначим 
Ak.
Как нетрудно заметить, единственным отличием общего аналитического вида аффинных функций от линейных является наличие 
свободного члена b, при этом если b = 0, то функция является линейной, а при b = 1 функция в векторном виде является побитовой 
инверсией соответствующей линейной функции (при тех же значениях коэффициентов 
0
1
1
,
,...,
k
a a
a − ).
Таким образом, множество всех аффинных функций от 
k переменных есть объединение множества всех линейных 
функций от k переменных и множества их побитовых инверсий 

{
}
:
k
k
k
f
f
=
∪
∈
A
L
L
.

Пример 1.3.
Построим все аффинные булевы функции от двух переменных. 
Для этого нам нужно объединить уже построенное в Примере 1.2 
множество всех линейных булевых функций от двух переменных 
с множеством их побитовых инверсий

(
) (
) (
) (
) (
) (
) (
) (
)
{
}
2
0000 ; 0101 ; 0011 ; 0110 ; 1111 ; 1010 ; 1100 ; 1001
=
A
.  (1.6)

Теперь мы можем от общего представления S-блока (1.1) перейти к наиболее употребительной интерпретации S-блока, к «рабочему» представлению.
Определение 1.7. Блоком замен 
1
2
k
k
×
 бит называется отобра
жение {
}
{
}
1
2
0,1
0,1
k
k
→
, т.е. отображение, однозначно сопоставля
ющее любому входному вектору из 
1k  бит выходной вектор из 
2k  
бит.
Нетрудно заметить, что блок замен есть не что иное, как набор
из 
 булевых функций, каждая из которых задает зависимость 
определенного бита на выходе S-блока от значений битов на входе. 
Для определения криптографического качества S-блоков подстановки целесообразно сначала представить полученный S-блок подстановки в виде его компонентных булевых функций 
,
0,1,...,
1
iF i
k
=
− ,
см. табл. 1.2.

A
L
L

Таблица 1.2
Двоичное представление компонентных функций

X
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1
x
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

2
x
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1

3
x
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1

4
x
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1

Q
15 14 13
11
6
12
9
2
5
10
4
8
0
1
3
7

1F
1
0
1
1
0
0
1
0
1
0
0
0
0
1
1
1

2
F
1
1
0
1
1
0
0
1
0
1
0
0
0
0
1
1

3
F
1
1
1
0
1
1
0
0
1
0
1
0
0
0
0
1

4
F
1
1
1
1
0
1
1
0
0
1
0
1
0
0
0
0

1.2. ОБЗОР ОБЩИХ МЕТОДОВ ПОСТРОЕНИЯ 
И ТЕСТИРОВАНИЯ БЛОКОВ ЗАМЕН 
ДЛЯ БЛОЧНЫХ ШИФРОВ

Существует ряд общеизвестных критериев [1, 2] для проектирования устойчивых к дифференциальному криптоанализу узлов 
замен для любых блочных шифров.

1.2.1. Алгебраическая степень нелинейности

Каждая функция из множества Fk имеет единственное представление в виде алгебраической нормальной формы (АНФ), в отечественной литературе распространен также термин «полином Жегалкина» [9]. Рассмотрим основные методы построения полиномов 
Жегалкина.
Перевод вектора f  двоичных значений булевой функции 
в вектор a  двоичных коэффициентов полинома Жегалкина можно 
задать путем умножения нижней треугольной матрицы 
k
L  

на вектор-столбец 
T
f
 по модулю два