МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Сибирский государственный университет науки и технологий
имени академика М.Ф. Решетнева»
Институт Информатики и телекоммуникаций
Направление Информационная безопасность
Профиль Безопасность автоматизированных систем
Кафедра Безопасности информационных технологий
ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА
Вид ВКР: бакалаврская работа
РАСПРОСТРАНЕНИЕ ПОНЯТИЯ КОРРЕЛЯЦИОННОГО ИММУНИТЕТА НА
СЛУЧАЙ ФУНКЦИЙ ТРЕХЗНАЧНОЙ ЛОГИКИ
Обучающийся
______
Руководитель
___________________
В.С. Курчатова
_____________
О.Н. Жданов
Ответственный за нормоконтроль ______________
Н.И. Чугунова
Допускается к защите
Заведующий кафедрой
______________
В.В. Золотарев
«______» _____________________ 20__ г.
Красноярск 2020
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Сибирский государственный университет науки и технологий
имени академика М.Ф. Решетнева»
Информатики и телекоммуникаций
Безопасности информационных технологий
УТВЕРЖДАЮ
Заведующий кафедрой
________ В.В. Золотарев
« ____ » _________ 20 ___ г
ЗАДАНИЕ
НА ВЫПУСКНУЮ КВАЛИФИКАЦИОННУЮ РАБОТУ
в форме бакалаврской работе
ОбучающийсяКурчатова Вера Сергеевна
Группа БКБ16-01 Направление
10.03.01
Информационная безопасность
Тема выпускной квалификационной работы Распространение понятия корреляционного
иммунитета на случай функций трехзначной логики
Утверждена приказом по университету от ____________№__________________
Руководитель ВКР – О.Н. Жданов, кандидат физико-математических наук, доцент кафедры
БИТ
Исходные данные для ВКР Научные статьи, интернет-ресурсы
Перечень разделов ВКР
1 Базовые определения трехзначной логики
2 Анализ требований и нормативной документации
3 Метод корреляционного иммунитета на случай трехзначныхфункций
Срок сдачи обучающимся первого варианта ВКР – « ___ » ______ 20__ г.
Срок сдачи обучающимся окончательного варианта ВКР – « ___ » _____ 20__ г.
Руководитель ВКР
_____________
Задание принял к исполнению
____
О.Н. Жданов
______
_
В.С. Курчатова
« ___ » _____________ 20__ г.
АННОТАЦИЯ
к бакалаврской работе
«Распространение понятия корреляционного иммунитета на случай
функций трехзначной логики»
Курчатова Вера Сергеевна
Ключевые слова: трехзначная логика, алгебраическая нормальная форма,
алгебраическая иммунность, корреляционный иммунитет, идеальные матрицы.
Целью данной работы является исследование корреляционного
иммунитета на случай трехзначных функций для их дальнейшего применения.
Данная цель определила необходимость постановки и решения основных
задач:
а) описать трехзначную логику;
б) рассмотреть понятие корреляционного иммунитета;
в) применить корреляционный иммунитет к трехзначной логики.
Предмет исследования – По результатам исследования предложен метод
корреляционного иммунитета на случай функций трехзначной логики.
Полученные результаты дают возможность лучше узнать о трехзначной логики,
что способствует возможности применения трехзначных функций в жизни.
Работа включает: 34 страницы, 15 таблиц, 53 формулы. Использованных
источников – 11.
3
СОДЕРЖАНИЕ
ВВЕДЕНИЕ .............................................................................................................. 5
1 БАЗОВЫЕ ОПРЕДЕЛЕНИЯ ТРЕХЗНАЧНОЙ ЛОГИКИ ................................. 6
1.1 Функции 3-значной логики. Аналог правила до Моргана ................... 6
1.2 Поля Галуа ............................................................................................ 10
1.3 Алгебраическая нормальная форма .................................................... 11
1.4 Аффинные и линейные функции трехзначной логики ...................... 13
1.5 Вывод .................................................................................................... 13
2 АНАЛИЗ ТРЕБОВАНИЙ И НОРМАТИВНОЙ ДОКУМЕНТАЦИИ ............. 15
2.1 Основные актуальные угрозы безопасности информации и причин
их возникновения ................................................................................................... 15
2.2 Требования к ключам и таблицам замен............................................. 16
2.3 Вывод .................................................................................................... 17
3 МЕТОД
КОРРЕЛЯЦИОННОГО
ИММУНИТЕТА
НА
СЛУЧАЙ
ТРЕХЗНАЧНЫХ ФУНКЦИЙ ............................................................................... 18
3.1 Алгебраическая иммунность 3-функций ............................................ 18
3.2 Корреляционный иммунитет 3-функций ............................................ 21
3.3 Корреляционный иммунитет 3-функций от двух переменных ......... 23
3.4 S-блоки с идеальными матрицами коэффициентов корреляции ....... 28
3.5 Вывод .................................................................................................... 32
ЗАКЛЮЧЕНИЕ ...................................................................................................... 33
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ .............................................. 34
4
ВВЕДЕНИЕ
В современном мире теория булевых функций занимает важное место.
Двухзначная логика используется во многих теоретических областях, так и в
прикладных. Цифровые устройства, системы искусственного интеллекта и
другие управляющие системы решают сложные задачи, выполняя
элементарные двоичные операции и храня данные в виде нулей и единиц.
Поэтому двухзначная логика до сих пор занимает доминирующее
положение. Но все меняется, возрастает сложность решаемых задач и,
следовательно, технических устройств. Таким образом, необходимо
применение многозначной логики.
Также, из-за массового внедрения вычислительной техники растет
количество информационных атак. Поэтому криптография подлежит изучению
и улучшению.
Чтобы добиться менее трудоемкого решения криптографических задач в
криптоанализе появился метод корреляционного иммунитета.
В связи с этим является актуальным рассмотрение корреляционного
иммунитета для трехзначных функций.
Таким образом, целью данной
работы
является
исследование
корреляционного иммунитета на случай трехзначных функций для их
дальнейшего применения.
Для достижения поставленной цели необходимо решить следующие
задачи:
а) описать трехзначную логику;
б) рассмотреть понятие корреляционного иммунитета;
в) применить корреляционного иммунитета к функциям трехзначной
логики.
5
1 БАЗОВЫЕ ОПРЕДЕЛЕНИЯ ТРЕХЗНАЧНОЙ ЛОГИКИ
Многозначная логика является одним из опытов расширения границ
осознания и формального описания логических связей реального мира.
Впервые Я. Лукашевич обратил внимание на многозначность, как способ
отображения информации в рассуждениях.
Многозначные логики появились в 20-х годах XX века в работах Поста и
Лукасевича. Несколько позднее было предложено ещё несколько многозначных
логик, таких как логика Бочвара, логики Гёделя, логика Клини. Изобретение
этих логик было мотивировано разными задачами. Так, Лукасевич и Бочвар
исходили из философских предпосылок, вводя третье значение в свои логики
для формализации неполного или противоречивого знания. Пост и Гёдель
руководствовались более техническими соображениями, когда обобщали
классическую логику в -значных системах. Клини же просто искал удобный
формализм для анализа понятия частично определённой рекурсивной функции.
Однако все эти логики объединяет важная отличительная особенность: в
них теоретически заложена концепция, которую называют истинностной
функциональностью. Согласно ей, всякое высказывание имеет некоторое
значение истинности, и это значение может быть однозначно вычислено
некоторой заранее определённой функцией по значениям входящих в это
высказывание подвысказываний.
Между многозначной и булевой логикой имеются рад отличий.
Например, хорошо известно, что при подстановке одной булевой функции в
другую сохраняется существенная зависимость от переменных, а для функций
k-значной логики при 𝑘≥3 аналогичное утверждение неверно.
Трехзначная логика (далее как 3 функция) – это один из видов
многозначной логики, её отображение имеет вид: {0, 1, 2}𝑘 {0, 1, 2}3 , где 0 –
лож, 1 – истина, 2 – неопределенность, а 𝑘 – количество переменных.
1.1 Функции 3-значной логики. Аналог правила до Моргана
Аналогичным функциям алгебры двузначной логики, можно определить
функции 3-значной логики. Значения переменных и самих функций берутся из
множества 𝔼3 = 0,1,2. Множество всех таких функций обозначается через ℙ3 .
6
Как и булевы функции, каждую функцию 𝑓(𝑥1, … , 𝑥𝑛 ) из ℙ3 можно задать
таблицей истинности (таблица 1.1).
Таблица 1.1Таблица истинности
𝑥1 … 𝑥𝑛
0…0
…
𝜎1 … 𝜎𝑛
…
2…2
𝑓(𝑥1 , … , 𝑥𝑛 )
𝑓(𝑥1 , … , 𝑥𝑛 )
…
𝑓(𝜎1 , … , 𝜎𝑛 )
…
𝑓(2, … , 2)
Так же можно обозначить некоторые элементарные функции для 3значной логики.
Таблица 1.2 Элементарные функции
𝑥 𝑦 max(𝑥, 𝑦) min(𝑥, 𝑦) 𝑥 + 𝑦(𝑚𝑜𝑑3)
0 0
0
0
0
0 1
1
0
1
0 2
2
0
2
1 0
1
0
1
1 1
1
1
2
1 2
2
1
0
2 0
2
0
2
2 1
2
1
0
2 2
2
2
1
𝑥𝑦(𝑚𝑜𝑑3)
0
0
0
0
1
2
0
2
1
𝑥⟘𝑦
0
0
0
1
0
0
2
1
0
𝑥→𝑦
2
2
2
1
2
2
0
1
2
𝑥 − 𝑦 𝑉3 (𝑥, 𝑦)
0
1
2
2
1
0
1
2
0
2
2
0
2
0
1
1
0
2
Пусть 𝑝3 (𝑛) – число всех функций 𝑓(𝑥1 , … , 𝑥𝑛 ) из ℙ3 . Количество
различных наборов значений переменных равно 3𝑛 . На каждом из этих наборов
функции 𝑓(𝑥1, … , 𝑥𝑛 )может принимать любое из 3𝑛 значений. Следовательно,
𝑛
всего таких функций будет 𝑝3 (𝑛) = 33 . Это число очень быстро растет,
например уже вℙ3 число функций от переменных 𝑥1 и 𝑥2 равно 𝑝3 (𝑛)= 19683.
Все основные понятия, такие, как формула над множеством функций, значение
формулы на наборе значений переменных, функция, реализуемая формулой,
существенная и несущественная переменные и др., вводится точно так же, как и
в двузначной логике, определения почти дословно повторяются. Однако,
переменные и функции принимают уже не два значения, а больше. В частности,
если известно значение 𝑥 из 𝔼3 , то нельзя определить значение 𝑦 из 𝔼3 только
на основе соотношения 𝑦 ≠ 𝑥. Это приводит к принципиальным отличиям ℙ3
от ℙ2 [8].
7
Известно, что при подстановке одной булевой функции в другую
сохраняется существенная зависимость от переменных. Покажем, что для
функций 3-значной логики аналогичное утверждение неверно.
Рассмотрим функцию 𝜑(𝑥1 , 𝑥2 ), заданную таблицей 1.3.
Таблица 1.3 Пример таблицы истинности
0
𝑥1
0
0
1
0
2
0
1
0
0
0
2
0
0
1
Функция 𝜑 принадлежит ℙ3 и принимает ненулевое значение только на
наборе (2,2). Поэтому функция 𝜑(𝑥, 𝜑(𝑦, 𝑧)) — константа 0, поскольку для
любых 𝛽, 𝛾 ∈ 𝔼3 выполняется неравенство 𝜑(𝛽, 𝛾) ≠ 2.
Рассмотрим следующие «элементарные» функции 3-значной логики [8]:
1. Константы 0,1,2.
2.
Тождественная функция 𝑥.
3.
Отрицания:
функции 𝑓(𝑥) = 𝑥̅ = 𝑥 + 1(𝑚𝑜𝑑 3) – отрицание Поста или
циклический сдвиг;
𝑓(𝑥) =∼ 𝑁(𝑥) = 𝑘 − 1 − 𝑥 – отрицание Лукасевича;
Эти функции являются обобщениями отрицания в ℙ2 . Функция 𝑁(𝑥)
является «зеркальным» отражением 𝑥. Она обозначается также ∼ 𝑥.
4. Характеристическая функция {2-го рода} 𝐼𝑖 (𝑥 ):
5.
𝐼𝑖 (𝑥 ) = {
6.
𝑘 − 1, если 𝑥 = 𝑖
0,если 𝑥 ≠ 𝑖
(1.1)
Характеристическая функция {1-го рода} 𝑗𝑖 (𝑥 ) = 0, 1, 2:
𝑗𝑖(𝑥) = {
1, если 𝑥 = 𝑖
0, если 𝑥 ≠ 𝑖
(1.2)
Эти функции являются аналогами функции 𝑥 𝜎 в ℙ2 .
8
7.
являются
Минимум: Функции 𝑚𝑖𝑛 (𝑥1 , 𝑥2 ) и 𝑥1𝑥2 (𝑚𝑜𝑑 3). Эти функции
обобщением
конъюнкции.
Функция 𝑚𝑖𝑛(𝑥1, 𝑥2 ) обозначается
также 𝑥1 ∧ 𝑥2 .
8.
Максимум:
Функция
𝑚𝑎𝑥 (𝑥1 , 𝑥2 ) .
Она
является
аналогом
дизъюнкции в ℙ2 и обозначается также 𝑥1 ∨ 𝑥2 .
Сложение по модулю 3: 𝑓(𝑥, 𝑦) = 𝑥1 + 𝑥2 (𝑚𝑜𝑑 3).
10. Умножение по модулю 3: 𝑓(𝑥, 𝑦) = 𝑥𝑦 (𝑚𝑜𝑑 3).
9.
11. Разность по модулю 3:
3 − (𝑦 − 𝑥 ), если 0 ≤ 𝑥 < 𝑦 ≤ 2
(𝑥 − 𝑦)𝑚𝑜𝑑 3 = {
𝑥 − 𝑦,если 0 ≤ 𝑦 ≤ 𝑥 ≤ 2
(1.3)
12. Усеченная разность 𝑥 ⊥ 𝑦:
𝑥⊥𝑦={
0,если 0 ≤ 𝑥 < 𝑦 ≤ 2
𝑥 − 𝑦, если 0 ≤ 𝑦 ≤ 𝑥 ≤ 2
(1.4)
13. Импликация 𝑥 ⊃ 𝑦:
𝑥⊃𝑦={
2,если 0 ≤ 𝑥 < 𝑦 ≤ 2
, 2 − 𝑥 + 𝑦, если 0 ≤ 𝑦 ≤ 𝑥 ≤ 2
(1.5)
14. Функция Веба:
𝜈𝑘 (𝑥, 𝑦) = (𝑚𝑎𝑥(𝑥, 𝑦) + 1)𝑚𝑜𝑑3.
(1.6)
15. Транспортизация чисел 𝑖 и 𝑗:
𝑥, если 𝑥 ∈ 𝑖, 𝑗
𝑡𝑖𝑗 (𝑥) = { 𝑗, если 𝑥 = 𝑖
𝑖, если 𝑥 = 𝑗
(1.7)
где 𝑡𝑖𝑗 (𝑥 ), 𝑖, 𝑗 ∈ 0, 1, 2 , 𝑖 ≠ 𝑗.
Теорема аналога правила де Моргана:
9
∼ (𝑥1 ∨ 𝑥2 ) = (∼ 𝑥1 ) ∧ (∼ 𝑥2 ) ∼ (𝑥1 ∨ 𝑥2 ) = (∼ 𝑥1) ∧ (∼ 𝑥2 )
(1.8)
Докажем ∼ (𝑥1 ∨ 𝑥2 ) = (∼ 𝑥1 ) ∧ (∼ 𝑥2 ).Два случая для 𝑥1, 𝑥2 ∈ 𝐸3
1)
𝑥1 ≥ 𝑥2 ; 𝑥1 ∨ 𝑥2 = 𝑥1 ∼ (𝑥1 ∨ 𝑥2 ) = 2 − 𝑥1 ∼ 𝑥1 =2 −𝑥1 ∼𝑥2 = 2 −
𝑥2 (∼𝑥1 ) ∧ (∼𝑥2 ) = 2 −𝑥1 ;
2)
𝑥1 < 𝑥2 ; ∼ (𝑥1 ∨ 𝑥2 ) = 2 − 𝑥2 (∼ 𝑥1) ∧ (∼ 𝑥2 ) = 2 − 𝑥2 .
Чтобы удостовериться в этих утверждений приведем пример:
∼ 𝑚𝑖𝑛 (𝑥, 𝑦) = 𝑚𝑎𝑥 (∼ 𝑥, ∼ 𝑦), но ̅̅̅̅̅̅̅̅̅̅̅̅
𝑚𝑖𝑛(𝑥, 𝑦) ≠ 𝑚𝑎𝑥 (𝑥̅ , 𝑦̅).
(1.9)
Упростим выражение, обозначив все элементы через 𝑓𝑖 : 𝑓1 = 𝑓2 и 𝑓3 ≠ 𝑓4 .
Теперь можно составить таблицу:
Таблица 1.4 Пример
𝑥
𝑦
𝑚𝑖𝑛(𝑥, 𝑦)
0
0
0
0
1
0
0
2
0
1
0
0
1
1
1
1
2
1
2
0
0
2
1
1
2
2
2
𝑓1
2
2
2
2
1
1
2
1
0
∼𝑥
2
2
2
1
1
1
0
0
0
∼𝑦
2
1
0
2
1
0
2
1
0
𝑓2
2
2
2
2
1
1
2
1
0
𝑓3
1
1
1
1
2
2
1
2
0
𝑥̅
1
1
1
2
2
2
0
0
0
𝑦̅
1
2
0
1
2
0
1
2
0
𝑓4
1
2
1
2
2
2
1
2
0
Исходя из таблицы 4, можно убедиться, что выражение получается
верным. Рассмотрим таблицу 4. Столбцы 𝑓1 и 𝑓2 совпадают, соответственно
выполняется равенство ∼ 𝑚𝑖𝑛 (𝑥, 𝑦) = 𝑚𝑎𝑥 (∼ 𝑥, ∼ 𝑦) , а 𝑓3 и 𝑓4 , разные,
̅̅̅̅̅̅̅̅̅̅̅̅
соответственно 𝑚𝑖𝑛(𝑥,
𝑦) ≠ 𝑚𝑎𝑥 (𝑥̅ , 𝑦̅) верно.
1.2 Поля Галуа
Для работы с информацией при кодировании и декодировании данных
все арифметические операции выполняются в полях Галуа. Применяется так
называемая полиномиальная арифметика или арифметика полей Галуа [2].
Таким образом, результат любой операции также является элементом данного
поля. Конкретное поле Галуа состоит из фиксированного диапазона чисел.
10
такое поле называется расширенным. 𝐺𝐹(𝑞) – обозначение поля Галуа, где 𝑞 =
𝑝𝑛 .
Для работы с цифровыми данными естественно использовать 𝑝 = 2 в
качестве
характеристики
поля.
При
𝑛=1
элементом
кодовой
последовательности будет бит, при 𝑛 = 8– 8 бит, то есть байт [3]. Однако в
данной работе используются с числа 3логики. В данном случае 𝑝 = 3, а при
𝑛 = 1 получаемтрит – минимальную целую единицу измерения количества
информации источников с тремя равновероятными сообщениями.
Таблица 1.5Операция сложения
+
0
1
2
0
0
1
2
1
1
2
0
2
2
0
1
Таблица 1.6Операция умножения
×
0
0
0
1
0
2
0
1
0
1
2
2
0
2
1
В таблицах 1.5 и 1.6 приведена арифметика полей Галуа для 3-логики.
1.3 Алгебраическая нормальная форма
Алгебраической нормальной формой 3-функции называется полином
Ф над 𝑍𝑞 степени 𝑑𝑒𝑔(Ф) < 𝑞 с коэффициентами 𝑎𝑖 ∈ {0,1,2} , содержащий
операции «Сумма по модулю 3» и «Умножение по модулю 3» [1].
Общий вид 3-функции с 𝑘 = 2 и 𝑁 = 9(рисунок 1.2)
𝑓 = {𝑓00 , 𝑓01 , 𝑓02, 𝑓10 , 𝑓11, 𝑓12, 𝑓20 , 𝑓21 , 𝑓22 }
(1.10)
Отсюда следует полином АНФ (рисунок 1.3)
𝑓(𝑥1, 𝑥2 ) = 𝑎00 + 𝑎01 𝑥2 + 𝑎02 𝑥2 2 + 𝑎10 𝑥1 + 𝑎11 𝑥1𝑥2 + 𝑎12 𝑥1𝑥2 2 +𝑎20 𝑥12 +
+𝑎21 𝑥12 𝑥2 + 𝑎22 𝑥12 𝑥2 2,
(1.11)
где, 𝑎𝑖𝑗 ∈ {0,1,2} искомые коэффициенты.
11
Чтобы связать искомые коэффициенты с таблицей
необходимо составить следующую систему уравнений:
истинности,
𝑓00 = 𝑎00 ;
𝑓01 = 𝑎00 + 𝑎01 + 𝑎02 ;
𝑓02 = 𝑎00 + 2𝑎01 + 𝑎02 ;
𝑓10 = 𝑎00 + 𝑎10 +𝑎20 ;
𝑓11 = 𝑎00 + 𝑎01 + 𝑎02 + 𝑎10 + 𝑎11 + 𝑎12 + 𝑎20 + 𝑎21 + 𝑎22 ;
(1.12)
𝑓12 = 𝑎00 + 2𝑎01 + 𝑎02 + 𝑎10 + 2𝑎11 + 𝑎12 + +𝑎20 + 2𝑎21 + 𝑎22 ;
𝑓20 = 𝑎00 + 2𝑎10 + 𝑎20 ;
𝑓21 = 𝑎00 + 𝑎01 + 𝑎02 + 2𝑎10 + 2𝑎11 + 2𝑎12 + +𝑎20 + 𝑎21 + 𝑎22 ;
{𝑓22 = 𝑎00 + 2𝑎01 + 𝑎02 + 2𝑎10 + 𝑎11 + 2𝑎12 + +𝑎20 + 2𝑎21 + 𝑎22 ;
Данную систему уравнений можно представить в виде матрицы:
𝐿−1
9
100000000
111000000
121000000
100100100
= 111111111 .
121121121
100200100
111222111
[121212121]
(1.13)
Так же для матрицы (1.13) обратная матрица будет выглядеть:
100000000
021000000
222000000
000200100
𝐿9 = 000012021 .
000111222
200200200
012012012
[111111111]
(1.14)
Чтобы найти искомые коэффициенты, можно воспользоваться одной из
формул:
12
𝐴 = 𝑓𝐿𝑛 , 𝑓 = 𝐴𝐿𝑛 .
(1.15)
Важно отметить, что для 3-функций матрицы прямого и обратного
преобразования АНФ не совпадают.
1.4 Аффинные и линейные функции трехзначной логики
Аналогично двоичному случаю, можно ввести понятия линейной и
аффинной функции, на основе которых вводится определение нелинейности.
Скажем, что линейной функцией называется трехзначная функция,
аналитически задаваемая как [13]
𝜑′ (𝑥0 , … , 𝑥𝑘−1) = 𝑎0 𝑥0 + 𝑎1 𝑥1 + ⋯ + 𝑎𝑘−1𝑥𝑘−1 (𝑚𝑜𝑑𝑞) =
= ∑𝑘−1
𝑖=0 𝑎𝑖 𝑥𝑖 (𝑚𝑜𝑑𝑞),
(1.16)
где 𝑎0 , 𝑎1 , … , 𝑎𝑘−1 ∈ {0,1, … , 𝑞 − 1}.
Тогда аффинной функцией называется функций аналитического вида [13]
𝜑(𝑥0 , … , 𝑥𝑘−1) = 𝑎0 𝑥0 + 𝑎1 𝑥1 + ⋯ + 𝑎𝑘−1𝑥𝑘−1 + 𝑏(𝑚𝑜𝑑𝑞) = ∑𝑘−1
𝑖=0 𝑎𝑖 𝑥𝑖 +
+𝑏(𝑚𝑜𝑑𝑞),
(1.17)
где 𝑎0 , 𝑎1 , … , 𝑎𝑘−1, 𝑏 ∈ {0,1, … , 𝑞 − 1}.
Можно заметить, что отличием вида аффинных функций от линейных
является присутствие члена 𝑏 . При этом, если 𝑏 = 0 , то функция является
линейной.
1.5 Вывод
В первой главе были рассмотрены общие понятия трехзначных функций
и некоторые отличия двухзначной и трехзначной логики. Также глава
включает: определение трехзначных функций, поля Галуа и преобразования в
алгебраическую нормальную функцию.
Можно кратко описать шаги
произвольным количеством переменных:
13
нахождения
АНФ
3-функций
с
а) найти матрицу обратного преобразования;
б) найти матрицу прямого преобразования;
в) вычислить искомые коэффициенты.
Далее будут приведен метод корреляционного иммунитета на случай
троичных функций.
14
2 АНАЛИЗ ТРЕБОВАНИЙ И НОРМАТИВНОЙ ДОКУМЕНТАЦИИ
2.1 Основные актуальные угрозы безопасности информации и
причин их возникновения
Рассмотрим угрозы, появление которых может быть обнаружено в
прикладном программном обеспечении. В банке угроз безопасности
информации ФСТЕК [9] для такого типа приложений можно выделить
следующие (таблица 2.1).
Таблица 2.1Угроза внедрения вредоносного кода в дистрибутив программного
обеспеченияУБИ.191 [2]
Описание угрозы
Угроза заключается в возможности осуществления
нарушителем заражения системы путем установки
дистрибутива, в который внедрен вредоносный код.
Данная угроза обусловлена слабостями мер антивирусной
защиты. Реализация данной угрозы возможна при:
применении пользователем сторонних дистрибутивов;
отсутствии антивирусной проверки перед установкой
дистрибутива
Источник угрозы
внутренний нарушитель с низким потенциалом;
внешний нарушитель с низким потенциалом.
Объект воздействия
Прикладное
программное
обеспечение,
сетевое
программное обеспечение, системное программное
обеспечение
Последствия реализации угрозы
нарушение конфиденциальности;
нарушение целостности;
нарушение доступности.
Согласно банку данных угроз безопасности информации ФСТЭК [9] для
криптографических алгоритмов существует следующая угроза – УБИ.003:
Угроза анализа криптографических алгоритмов и их реализации. Ее описание
представлено в таблице 2.2[2].
Было доказано существование атаки на шифр ГОСТ 28147-89, имеющей
сложность в 28 (256) раз меньше сложности прямого перебора ключей при
условии наличия 264 пар «открытый текст»/»закрытый текст». Данная атака не
может
быть
вычислительной
осуществлена
сложности.
на
Более
практике
того,
ввиду
слишком
знание 264
пар
высокой
«открытый
текст»/»закрытый текст», очевидно, позволяет читать зашифрованные тексты,
даже не вычисляя ключа. В большинстве других работ также описываются
атаки, применимые только при некоторых предположениях, таких как
15
определенный вид ключей или таблиц замен, некоторая модификация
исходного алгоритма, или же требующие все ещё недостижимых объёмов
памяти или вычислений.
Таблица 2.2 Описание угрозы УБИ.003
Описание угрозы
Угроза заключается в возможности выявления слабых
мест в криптографических алгоритмах или уязвимостей в
реализующем их программном обеспечении. Данная
угроза обусловлена слабостями криптографических
алгоритмов, а также ошибками в программном коде
криптографических средств, их сопряжении с системой
или параметрах их настройки. Реализация угрозы
возможна в случае наличия у нарушителя сведений об
применяемых в системе средствах шифрования,
реализованных в них алгоритмах шифрования и
параметрах их настройки
Источники угрозы
Внешний нарушитель со средним потенциалом
Объект воздействия
Метаданные, системное программное обеспечение
Последствия реализации угрозы
нарушение конфиденциальности;
нарушение целостности.
На данный момент в открытых источниках информация о наличии
применимых на практике атак, без использования слабости отдельных ключей
или таблиц замен, не обнаружена[9].
2.2 Требования к ключам и таблицам замен
Для программ, выполняющих генерацию ключей и шифрование,
уязвимым местами являются слабые ключи, которые переводят открытый текст
в себя или побитовую инверсию открытого текста, либо инвертируют часть
битов открытого текста, т. е. шифрования как такового не происходит.
Помимо этого, общепринятыми для всех блочных шифров требованиями
к ключам шифрования являются следующие:
ключ должен являться массивом битов, принимающих с равной
вероятностью значения 0 и 1 (для 3-логики 0,1,2);
между
битами
ключа
не
должно
быть
явной
или
легко
обнаруживаемой зависимости, иными словами, в массиве бит должны
отсутствовать статистические закономерности. Аналогично для тернарной
логики введем требование: между тритами ключа не должно быть легко
обнаруживаемой зависимости.
16
2.3 Вывод
В главе были рассмотрены основные угрозы, связанные с созданием
программного обеспечения, предназначенного для шифрования данных. На
основе результатов анализа этих угроз было принято решение добавить
критерий для ключей – проверка их разреженности. Требования для ключей
шифрования выдвинуты на основе известных методов атаки на шифры с
использованием современных компьютеров. Выдвинуты требования для таблиц
замен. Несмотря на то, что перечисленные выше требования относятся к
классическим (бинарным) методам шифрования, в главе 3 будут применяться
данные требования, расширенные для тернарной логики. Это обусловлено тем,
что в работе нас интересует «похожесть» значений, которые принимает трит, но
не важно, какая это разница – 1 или 2[2].
17
3 МЕТОД КОРРЕЛЯЦИОННОГО ИММУНИТЕТА НА СЛУЧАЙ
ТРЕХЗНАЧНЫХ ФУНКЦИЙ
Одним из приемов современного криптоанализа является использование
близости (относительно некоторой метрики) криптографических отображений к
отображениям, позволяющим свести исходную криптографическую задачу
кменее трудоемкой [4]. Яркими примерами этого являются корреляционный и
линейный методы криптоанализа. Одна из возможных характеристик,
показывающая эффективность этих методов, была названа нелинейностью
функции.
У любой функции есть два параметра: число переменных(𝑛) и степень
корреляционной иммунности(𝑚). Термин корреляционной иммунности можно
определить как: функция, выход которой не коррелирует с совокупностью
любых𝑚входов.
3.1 Алгебраическая иммунность 3-функций
Приведем пример алгебраической иммунности на случай 3-функций. Для
этого понадобиться полином АНФ (1.3), таблица истинности (табл. 1). Так же
будет присутствовать определение аннигилятор, что означает 𝑓 ∙ 𝑔 = 0 или
(𝑓 + {1,2}) ∙ 𝑔 = 0, где 𝑓, 𝑔 ∈ 𝑉𝑛 .
Зададим функцию
𝑓(𝑥1, 𝑥2 ) = 𝑥1 +𝑥2
(3.1)
Найдем для нее аннигилятор.
𝑔(𝑥 ) = 𝑎00 +𝑎10𝑥1 +𝑎01 𝑥2
(3.2)
𝑓(𝑥 ) ∙ 𝑔(𝑥 ) = (𝑥1 +𝑥2 )(𝑎00 +𝑎10 𝑥1 +𝑎01 𝑥2 ) = 0
(3.3)
18
Таблица 3.1Таблица истинности для𝑓(𝑥 ) ∙ 𝑔(𝑥 )
𝑓(𝑥 ) ∙ 𝑔(𝑥)
𝑥1 𝑥2
0
0
0
0
1
𝑎00 +𝑎01 = 0
1
0
𝑎00 + 𝑎10 = 0
1
1
𝑎00 +𝑎10 +𝑎01 = 0
2
0
𝑎00 +2𝑎10 = 0
0
2
𝑎00 +2a01 = 0
Из таблицы 3.1 следует, что 𝑎00 = 𝑎01 = 𝑎10 = 0.
Проверим и для функции(𝑓 + 1)
(𝑓 + 1) ∙ 𝑔(𝑥 ) = (𝑥1 +𝑥2 + 1)(𝑎00 +𝑎10 𝑥1 +𝑎01 𝑥2 ) = 0
(3.4)
Таблица 3.2Таблица истинности для (𝑓 + 1) ∙ 𝑔(𝑥)
(𝑓 + 1) ∙ 𝑔(𝑥)
𝑥1 𝑥2
0
0
𝑎00 =0
0
1
𝑎00 +𝑎01 = 0
1
0
𝑎00 + 𝑎10 = 0
Из таблицы 3.2 следует, что 𝑎00 = 𝑎01 = 𝑎10 = 0.
И последняя проверка для функции (𝑓 + 2)
(𝑓 + 2) ∙ 𝑔(𝑥 ) = (𝑥1 +𝑥2 + 2)(𝑎00 +𝑎10 𝑥1 +𝑎01 𝑥2 ) = 0
(3.5)
Таблица 3.3Таблица истинности для (𝑓 + 2) ∙ 𝑔(𝑥)
(𝑓 + 2) ∙ 𝑔(𝑥)
𝑥1 𝑥2
0
0
𝑎00 =0
0
1
𝑎00 +𝑎01 = 0
1
0
𝑎00 + 𝑎10 = 0
1
1
𝑎00 + 𝑎10 + 𝑎01 = 0
2
0
𝑎00 + 2𝑎10 = 0
0
2
𝑎00 + 2𝑎10 = 0
Из таблицы 3.3 следует, что 𝑎00 = 𝑎01 = 𝑎10 = 0.
Получается, что степени 1 для трехзначных функций не существует.
Тогда попробуем найти 𝑔 со степенью 2.
𝑔(𝑥 ) = 𝑎00 +𝑎10𝑥1 +𝑎01 𝑥2 +𝑎11 𝑥1 𝑥2 +𝑎20 𝑥12+𝑎02 𝑥2 2 = 0
19
(3.6)
𝑓(𝑥 ) ∙ 𝑔(𝑥 ) = (𝑥1 +𝑥2 )(𝑎00 +𝑎10 𝑥1 +𝑎01 𝑥2 +𝑎11𝑥1 𝑥2 +
+𝑎20 𝑥1 2+𝑎02 𝑥2 2 ) = 0
(3.7)
Так же составим таблицу истинности (рисунок 3.4).
Таблица 3.4Таблица истинности для(𝑓) ∙ 𝑔(𝑥 )
(𝑓) ∙ 𝑔(𝑥)
𝑥1 𝑥2
0
0
0
0
1
𝑎00 +𝑎01 + 𝑎02 = 0
1
0
𝑎00 + 𝑎10 + 𝑎20 = 0
1
1
𝑎00 + 𝑎10 + 𝑎01 + 𝑎11 + 𝑎20 + 𝑎02 = 0
2
0
𝑎00 + 2𝑎10 + 𝑎20 = 0
0
2
𝑎00 + 2𝑎01 + 𝑎02 = 0
1
2
0
2
1
0
2
2
𝑎00 + 2𝑎10 + 2𝑎01 + 𝑎11 + 𝑎20 + 𝑎02 = 0
В соответствии с таблицей 3.4 можно утверждать, что 𝑎01 = 𝑎10 = 0, так
же 𝑎02 = 𝑎20 исходя из 𝑓 (01), 𝑓 (02)и𝑓(10), 𝑓 (20) . Получим систему
уравнений, основываясь на 𝑓 (11)и𝑓 (22) : {
𝑎00 + 𝑎11 + 𝑎20 + 𝑎02 = 0
. Тогда
𝑎11 + 𝑎20 = 0
Можно сказать, что 𝑎02 = −𝑎00 = −𝑎11или 𝑎00 = 𝑎11 .
Тогда, 𝑛 = 2, 𝑑 = 2 , 𝑓 (𝑥 ) = 𝑥1 + 𝑥2 и 𝑔 будет выглядеть следующим
образом:
𝑔(𝑥 ) = 𝑎00 +𝑎00 𝑥1𝑥2 𝑎00 𝑥12 𝑎00 𝑥2 2 = 𝑎00 (1+𝑥1 𝑥2 𝑥1 2𝑥2 2 )
(3.8)
Подставим в 𝑓 (𝑥 ) ∙ 𝑔(𝑥) = 0:
𝑓(𝑥 ) ∙ 𝑔(𝑥 ) = (𝑥1 +𝑥2 )(1 + 𝑥1 𝑥2 𝑥12 𝑥2 2 ) = 0
Таблица 3.5Таблица истинности для(𝑓) ∙ 𝑔(𝑥 )
(𝑓) ∙ 𝑔(𝑥)
𝑥1 𝑥2
0
0
0
0
1
0
1
0
0
1
1
0
2
0
0
0
2
0
1
2
0
2
1
0
2
2
0
20
(3.9)
Следовательно, аннигилятором функции 𝑓 (𝑥 ) = 𝑥1 +𝑥2 является функция
𝑔(𝑥 ) = 1+𝑥1 𝑥2 𝑥12𝑥22 .
Для булевых функций алгебраическая иммунность при значении 2 не
допускает равенства корреляционного иммунитета нулю. Тогда если
3функции имеют высокую алгебраическую иммунность, они могут обеспечить
хорошую корреляционную иммунность. По возможности построение блоков
замен может происходить так: находим 3-функцию с высокой алгебраической
иммунностью, используем её значения, при этом переводя числа из троичного
представления, например, в двоичное. Тогда, можно сказать, что такой подход
может обеспечить наилучшие свойства блоков замен, по сравнению с булевым
подходом.
3.2 Корреляционный иммунитет 3-функций
Для начала введем понятие подфункции 3-функции.
Определение 3.1.Подфункцией 3-функции 𝑓(𝑥) , называется такая
функция𝑓′, полученная подстановкой в𝑓значений из множества {0,1,2} вместо
некоторых
переменных.
𝜎𝑖1 , … , 𝜎𝑖𝑠 вместо
Если
подставим
в
функцию
переменных 𝑥𝑖1 , … , 𝑥𝑖𝑠 соответственно,
𝑓
то
константы
полученная
𝜎 ,…,𝜎
подфункция обозначается как 𝑓𝑥𝑖 𝑖1,…,𝑥𝑖 𝑖𝑠 [12].
1
𝑠
Для определения независимости входа 3-функции от её входа и для
определения
корреляционного
иммунитета
воспользуемся
концепциейдисбаланса 3-функции, которая основана на преобразованиях
Виленкина-Крестенсона. Остановимся на этом понятии более подробно.
Коэффициенты преобразования Виленкина-Крестенсона можно найти для
вектора𝑡по следующей формуле
𝛺 = 𝑡𝑉′
(3.10)
где 𝑉′ матрица порядка 𝑁 , равная длине вектора 𝑡 , а апостроф обозначает
транспонирование.
21
Правило рекуррентного построения матриц Виленкина-Крестенсона𝑉3𝐿 (3
основание)
любого
порядка
в
символической
форме
представлено
в
формуле 3.11.
𝑉3𝐿−1
𝑉3𝐿 = [𝑉3𝐿−1
𝑉3𝐿−1
𝑧0
где 𝑉3 = [𝑧0
𝑧0
𝑧0
𝑧1
𝑧2
𝑉3𝐿−1
(𝑉3𝐿−1 + 1)mod3
(𝑉3𝐿−1 + 2)mod3
𝑉3𝐿−1
(𝑉3𝐿−1 + 2)mod3]
(𝑉3𝐿−1 + 1)mod3
(3.11)
𝑧0
𝑧2], а суммирование 𝑧𝑖 производится по модулю 3.
𝑧1
После построения матрицы Виленкина-Крестенсона в символической
форме осуществляется переход к экспоненциальной форме в соответствии со
следующими соотношениями 𝑧0 = 𝑒 𝑗0 , 𝑧1 = 𝑒 𝑗2𝜋/3, 𝑧2 = 𝑒 𝑗4𝜋/3.
Дисбаланс 3-функции представляет собой абсолютное значение первого
коэффициента
преобразования
Виленкина-Крестенсона,
то
есть
сумму
поэлементного произведения 3-функции на последовательность.
Определение 3.2.Пусть |𝑖| количество элементов 𝑖. Учитывая формулу
нахождения
модуля
комплексного
числа,
значение
дисбаланса
∆
последовательности над алфавитом {0,1,2} ↔ {𝑧0, 𝑧1, 𝑧2} определим как [11]:
2
√3
√3
∆𝑓 = √(1 ∙ |0| − 0.5(|1| + |2|))2 + ( |1| − |2|) .
2
Определение
3.3.Говорят,
что
(3.12)
2
выход
3-функции 𝑓(𝑥) является
независимым от группы своих входных переменных {𝑥𝑖 }, 𝑖 = 1, … , 𝑚, если при
подстановке вместо этих переменных любых констант 𝜎𝑖1 , … , 𝜎𝑖𝑠 ∈ {0,1,2} ,
дисбаланс полученных таким образом подфункций составляет ∆𝑓′ =
∆𝑓
3𝑚
[11].
Определение 3.4.Говорят, что 3-функция 𝑓(𝑥) является корреляционно
иммунной порядка 𝑚 ≤ 𝑘, если её выход является независимым относительно
любой группы их 𝑚 своих входных переменных, то есть дисбаланс всех её
подфункций 𝑘 − 𝑚переменных составляет ∆𝑓′ =
∆𝑓
3𝑚
Пример.Зададим 3-функцию порядка 𝑚 = 2
22
[12].
𝑓={
𝑥1 𝑥2 𝑥3 :000 001 002 010 011 012 020 021022
}
𝑓(𝑥1 𝑥2 𝑥3 ):021102210
(3.13)
∆(021102210) = √(1 ∙ 3 − 0.5(3 + 3))2 + (
Получается,
данная
функция
является
√3
3
2
−
√3
3)
2
2
=0
(3.14)
сбалансированной.
По
определение 3.4 для независимости данной функции от какой-либо из своих
переменных, необходимо, чтобы её подфункции, полученные путем
подстановки в данные переменные любых констант, были сбалансированы. Так
как 𝑚 = 2, то подфункций будет с 𝑘 − 𝑚 = 3 − 2 = 1 переменной.
000 001002
𝑓 (0,0, 𝑥3 ) = {
}
𝑓 (0, 𝑥2 , 0) = {
𝑓 (0,1, 𝑥3 ) = {
}
𝑓 (0, 𝑥2 , 1) = {
}
𝑓 (0, 𝑥2 , 2) = {
021
010 011012
102
020 021022
𝑓 (0,2, 𝑥3 ) = {
210
000 010020
012
001 011021
201
002 012022
120
000 100200
} 𝑓(𝑥1 , 0,0) = {
}
} 𝑓(𝑥1 , 0,1) = {
}
012
001 101201
201
002 102202
} 𝑓(𝑥1 , 0,2) = {
120
(3.15)
}
Проанализировав множество (3.7), можно сказать, что все подфункции
одной переменной 3-функции (3.5) имею нулевой дисбаланс (∆𝑓′ = 0). И так как
∆𝑓 = 0, то данная 3-функция является корреляционно-иммунной 2 порядка.
3.3 Корреляционный иммунитет 3-функций от двух переменных
Для анализа корреляционного иммунитеты порядка 𝑚 = 1 для 3-функций
двух переменных рассмотрим подфункции 𝑚 = 1 переменной, где таблица
истинности составляет 𝑛 = 3.
Рассмотрим полное множество 3-функций и мощность 𝐽 = 3𝑛 = 33 = 27
и определим возможные значения дисбаланса 3-функций в представленном
множестве [11].
∆
𝐽∆
0
6
√3
18
3
3
23
(3.16)
Получается, что корреляционно иммунными 1 порядка могут быть только
3-функции𝑁 = 9. В соответствии с определением 3.3 для одной переменной
получаем, что для двух переменных необходимо, чтобы дисбаланс был равным
∆𝑓 = 3𝑚 ∆𝑓′ = 31 ∆𝑓′ ∈ {0,3,9}.
Получились следующие результаты, приведенные в таблице 3.1.
Таблица 3.1Кардинальность 3-функциональных наборов с заданными корреляционными
свойствами [11]
3-функции
с
Функции,
Функции,
корреляционным
Корреляционный
независимые
от независимые
от
иммунитетом
иммунитет
переменной x1
переменной x2
порядка m 1
0 , J 1680
Количество
3216
216
12
функций
3 , J 4158
Количество
3972
972
216
функций
9, J 3
Количество
33
3
3
функций
Обозначим некоторые правила для метода синтеза таких 3-функций.
Правило 1. Синтез сбалансированных ( ∆= 0 ) 3-функцийдлины 𝑁 = 9 ,
которые независимы от значения 𝑥1 .
Рассмотрим тривиальную монотонно возрастающую последовательность
натуральных чисел 𝛼 = {012}. Сформируем на её основе множество
последовательностей длины 𝑁 = 9 мощности J1 62 36 по следующему
правилу
𝐴 = {𝑃𝑖 (𝛼 )𝑃𝑗 (𝛼 )𝑃𝑙 (𝛼 )}, 𝑖, 𝑗, 𝑙 = 1, … , 6,[12]
(3.17)
где 𝑃 операция применения одной из шести перестановок элементов
последовательности
{123} {231}
P {132} {312} .
{213} {321}
(3.18)
24
Если выбрать перестановки 𝑃𝑖 = 𝑃𝑗 = 𝑃𝑙 = {123} , то получим первую
последовательность, выход которой не зависит от входа 𝑥1
𝑇𝑙 = {012012012}.
(3.19)
Правило 2. Синтез сбалансированных (∆= 0) 3-функций длины𝑁 = 9,
которые независимы от входа𝑥2 [11].
Полное множество 3-функций, выход которых не зависит от входа 𝑥2 ,
может быть построено на основе полного множества 3-функций, выход
которых не зависит от входа 𝑥1 путем простой замены переменных.
Рассмотрим замену переменных 𝑥1 ↔ 𝑥2 на примере последовательности
(таблица 3.2).
Таблица 3.2 Последовательность 3-функций
0
1
2
3
00
01
02
10
𝑥1 𝑥2
0
1
2
0
𝑓(𝑥1 𝑥2 )
4
11
1
5
12
2
6
20
0
7
21
1
8
22
2
4
11
1
7
21
1
2
01
2
5
12
2
8
22
2
↓
𝑥2 𝑥1
𝑓(𝑥1 𝑥2 )
0
00
0
3
10
0
6
20
0
1
01
1
Перестановка 𝑃 = {0,3,6,1,4,7,2,5,8} подтверждает правило перехода от 3функций, выход которых не зависит от входа 𝑥1 ко множество 3-функций,
выход которых не зависит от входа 𝑥2 .
Правило 3. Синтез сбалансированных (∆= 0) корреляционно-иммунных 1
порядка для 3-функций длины𝑁 = 9 [11].
Это правило можно описать последовательностью с помощью следующих
шагов.
Шаг 1. Рассмотрим монотонно возрастающую последовательность
натуральных
чисел
𝛼 = {012} ,на
основе
которой
сформируем
6
последовательностей длины N 9 с помощью следующих правил
𝐴1 = {𝛼 ← (𝑖 + 0), 𝛼 ← (𝑖 + 1), 𝛼 ← (𝑖 + 2)}, 𝑖 ∈ {0,1,2};
[12]
𝐴2 = {𝛼 ← (𝑖 + 0), 𝛼 ← (𝑖 + 2), 𝛼 ← (𝑖 + 1)}, 𝑖 ∈ {0,1,2};
25
(3.20)
где символ 𝛼 ← (𝑖 + 0) обозначает оператор циклического сдвига вектора 𝛼
вправо на величину (𝑖 + 0).
Шаг 2. К последовательностям, полученным на 1 шаге, применяем
операцию замены символов {1 ↔ 2,2 ↔ 1}, таким образом, получая из каждой
корреляционно-иммунный 3-функции 2 корреляционно-иммунные 3-функции.
Правило 4. Синтез 3-функций длины 𝑁 = 9 дисбаланса ∆= 3 , выход
которых независим от входа 𝑥1 ивхода 𝑥2 [12].
Введем определение опорной 3-функции. Функция
𝑠(𝑔, 𝑋) = 𝑠𝑢𝑝𝑥∈𝑋 〈𝑥, 𝑔〉, 𝑔 ∈ ℝ𝑛 ,
(3.21)
где множество 𝑋 ⊂ ℝ𝑛 непустое и выпуклое, называется опорной функций
множества 𝑋.
Можно отметить, что полное множество 3-функций длины 𝑁 = 9 ,
которые независимы от входа 𝑥1 и имеет дисбаланс ∆= 3 может быть
синтезировано на основе 36 опорных 3-функций[11]
{001001022}
{001001112}
{001022001}
{001022022}
{001112001}
{001112112}
{002002011}
{002002122}
{002011002}
{002011011}
{002122002}
{002122122}
{011002002}
{011002011}
{011011002}
{011011122}
{011122011}
{011122122}
{022001001}
{022001022}
{022022001}
{022022112}
{022112022}
{022112112}
{112001001}
{112001112}
{112022022}
{112022112}
{112112001}
{112112022}
{122002002}
{122002122}
{122011011}
{122011122}
{122122002}
{122122011}
(3.22)
Каждая из опорных последовательностей (матрица3.22) может быть
представлена в виде конкатенации (операция подобная умножению, то есть
результат конкатенации объектов 𝐴 и 𝐵 является объект 𝐶 = 𝐴 ∙ 𝐵 , где
поочередно добавляются элементы объекта 𝐵 , начиная с первого, в конец
объекта A) трех подпоследовательностей следующим образом[11]:
𝐴 = {𝑎1 𝑎2 𝑎3 𝑎4 𝑎5 𝑎6 𝑎7 𝑎8 𝑎9 } = {𝛼𝛽𝛾},
𝛼 = {𝑎1 𝑎2 𝑎3 }, 𝛽 = {𝑎4 𝑎5 𝑎6 }, 𝛾 = {𝑎7 𝑎8 𝑎9 }.
(3.23)
На основе каждой опорной последовательностей (формула 3.23) могут
быть построены 27 новых последовательностей путем всех возможных
26
циклических сдвигов
подпоследовательностей 𝛼, 𝛽, 𝛾 ,путем
применения
следующей конструкции[11]:
𝐴 = {𝛼 ← 𝑖, 𝛽 ← 𝑗, 𝛾 ← 𝑙}, 𝑖, 𝑗, 𝑙 = 0,1,2.
Синтез
3-функций,
которые
независимы
(3.24)
от
входа 𝑥2 и
имеют
дисбаланс∆= 3, возможен на основе синтезированного полного множества 3функций, которые независимы от входа 𝑥1 и имеют дисбаланс ∆= 3 путем
замены переменных 𝑥1 и 𝑥2 согласно 3 правилу.
Правило 5.Синтез корреляционно-иммунных порядка 𝑚 = 1 3-функций
длины𝑁 = 9, которые имеют дисбаланс∆= 3[11].
Непосредственными вычислениями установлено, что полное множество
корреляционно-иммунных порядка 𝑚 = 1 3-функций длины 𝑁 = 9 , которые
имеют дисбаланс ∆= 3 может быть синтезировано на основе 72 опорных 3функций:
{001001112}
{001001220}
{001010211}
{001022202}
{001100121}
{001112001}
{001112112}
{001121100}
{001202022}
{001211010}
{001220001}
{001220220}
{002002110}
{002002221}
{002011101}
{002020122}
{002101011}
{002110002}
{002110110}
{002122020}
{002200212}
{002212200}
{002221002}
{002221221}
{010001211}
{010010121}
{010010202}
{010022220}
{010100112}
{010112100}
{010121010}
{010121121}
{010202010}
{010202202}
{010211001}
{010220022}
{011002101}
{011011122}
{011011200}
{011020110}
{011101002}
{011110020}
{011122011}
{011122122}
{011200011}
{011200200}
{011212221}
{011221212}
{020002122}
{020011110}
{020020101}
{020020212}
{020101020}
{020101101}
{020110011}
{020122002}
{020200221}
{020212020}
{020212212}
{020221200}
{022001202}
{022010220}
{022022100}
{022022211}
{022100022}
{022100100}
{022112121}
{022121112}
{022202001}
{022211022}
{022211211}
{022220010}
(3.25)
На основе каждой из 72 последовательностей (матрица3.25) могут быть
построены 3 последовательности в соответствии со следующим правилом[11]:
𝐴 = {𝑎𝑖 } = {(𝐴 + 𝑖)𝑚𝑜𝑑3}, 𝑖 = 0,1,2
Предложение 1.Множество идентичных 3-функций
27
(3.26)
{000000000}
{111111111},
{222222222}
(3.27)
составляют полное множество корреляционно-иммунных 1 порядка 3-функций
длины 𝑁 = 9 и они же совпадают с множеством 3-функций длины 𝑁 = 9 ,
которые независимы от входа 𝑥1 или 𝑥2 и имеют дисбаланс ∆=9.
3.4 S-блоки с идеальными матрицами коэффициентов корреляции
С точки зрения S-блоков наибольший интерес представляют собой 3функции. Проведенные исследования показали, что конструирование полного
множества S-блоков возможно на основе 44-х 3-функций, среди которых 12
функций, выход которых не зависит от входа 𝑥1 и еще 12 независимых от входа
𝑥2 (матрицы 3.28, 3.29 соответственно)
{012120120} {021021210} {102102210} {120012120} {201012201} {210021021}
{012201201} {021210021} {102210102} {120120012} {201201012} {210102102}
(3.28)
{002221110} {020212101} {101212020} {112001220} {200122011} {211100022}
{011122200} {022100211} {110221002} {121010202} {202010121} {220001112}
(3.29)
Кроме этого состав полного множества S-блоков длины 𝑁 = 9 ,
обладающих
идеальными
корреляционными
матрицами
входит
12
корреляционно-иммунных 3-функций порядка𝑚 = 1 (матрица 3.30), а также 8
функций общего вида (матрица 3.31)
{012120201} {021102210} {102021210} {120012201} {201012120} {210021102}
{012201120} {021210102} {102210021} {120201012} {201120012} {210102021}
{011221020} {020221011} {112100202} {202100112}
{020122110} {110122020} {202001211} {211001202}
(3.30)
(3.31)
На основе исследовании полного множества из 𝐽 = 264S-блоков длины
𝑁 = 9 , обладающих идеальными матрицами коэффициентов корреляции,
позволили сформулировать утверждение.
28
Утверждение 1. Условия идеальной матрицы коэффициентов корреляции
предполагают, чтобы хотя бы одна из его компонентных 3-функций была
независима от входной переменной 𝑥1 и хотя бы одна из его компонентных 3функций была независима от входной переменной 𝑥2 и по крайней мере один из
компонентов S-блока должен быть корреляционно иммунным порядка𝑚 = 1
[11].
Полное множество 𝐽 = 264S-блоков длины 𝑁 = 9 можно представить в
виде объединения пяти классов[11]:
1. S-блоки, у которых выход первой и второй компонентных 3-функций
являются независимы от входа 𝑥1 (мощность данного класса S-блоков
составляет𝐽 = 48).
{057624813} {156372480} {318426750} {462570138} {615237804} {750318426}
{057813624} {156480372} {318750426} {462138570} {615804237} {750426318}
{075264831} {237615804} {372480156} {480372156} {624057813} {813624057}
{075831264} {237804615} {372156480} {480156372} {624813057} {813057624}
{084273651} {264075831} {426318750} {516408732} {651273084} {831264075} (3.32)
{084651273} {264831075} {426750318} {516732408} {651084273} {831075264}
{138462570} {273084651} {408516732} {570462138} {732408516} {804237615}
{138570462} {273651084} {408732516} {570138462} {732516408} {804615237}
2. S-блоки, у которых выход первой и второй компонентных3-функций
являются независимыми от входа 𝑥2 (мощность данного класса S-блоков
составляет𝐽2 = 48).
{026875431} {145367820} {314758260} {451673208} {620578134} {745301286}
{028763541} {154376802} {341785206} {457013862} {628130574} {754310268}
{062857413} {206785341} {347125860} {473251608} {602587143} {826031475}
{068521743} {208673451} {374152806} {475031826} {608251473} {820367145}
{082736514} {260758314} {413857062} {514736082} {682103547} {862013457} (3.33)
{086512734} {268310754} {415637280} {541763028} {680215437} {860125347}
{134578620} {280637415} {431875026} {547103682} {734512086} {802376154}
{143587602} {286301745} {437215680} {574130628} {743521068} {806152374}
3. S-блоки, у которых первая компонентная 3-функции корреляционноиммунная порядка𝑚 = 1, а вторая компонентная 3-функция является функцией
общего вида (выход которой является корреляционно зависимым от каждого из
входов), (мощность данного класса S-блоков составляет 𝐽3 = 48).
29
{047581623} {173428650} {317284650} {472136805} {614257380} {742163508}
{056482713} {175406832} {326185740} {470158623} {623158470} {740185326}
{056824371} {238460715} {326851074} {517064832} {623581047} {814037562}
{074851326} {238604571} {371824056} {508163742} {641527083} {832406175}
{083527641} {247361805} {380257614} {508631274} {650428173} {832064517}
{083752416} {265307841} {380725146} {562037814} {650284317} {841307265}
{146725380} {265730418} {416752083} {562703148} {713482056} {805361247}
{148703562} {274631508} {418730265} {571604238} {715460238} {805136472}
(3.34)
4. S-блоки, у которых первая компонентная 3-функция является
функцией общего вида (выход которой является корреляционно зависимым от
каждого из входов), а вторая компонентная 3-функция является корреляционноиммунной порядка 𝑚 = 1 (мощность данного класса S-блоков составляет𝐽4 =
48).
{045783261} {162387540} {270468351} {450378261} {627510438} {708321546}
{054873162} {162873054} {270684135} {456312807} {627105843} {708213654}
{072486531} {180567342} {342567180} {531486072} {645123807} {816402357}
{072864153} {180675234} {348501726} {537420618} {654213708} {816024735}
{081576432} {234675180} {351468270} {540387162} {726501348} {834015726} (3.35)
{081765243} {243765081} {357402816} {546321708} {726015834} {843105627}
{135684270} {261378450} {432576081} {618420537} {735024816} {807312456}
{153864072} {261783045} {438510627} {618204753} {753204618} {807123645}
S-блоки,
укоторых
обе
компонентные
3-функции
являются
корреляционно-иммунными порядка 𝑚 = 1(мощность данного класса S-блоков
составляет 𝐽4 = 72).
{048561723} {165327840} {318750264} {462057813} {615480237} {750318264}
{048723561} {165840327} {318264750} {462813057} {615237480} {750264318}
{057462813} {183507642} {327165840} {480237615} {624138570} {705381246}
{057813462} {183642507} {327840165} {480615237} {624570138} {705246381}
{075426831} {237480615} {372156804} {516084732} {642183507} {813462057}
{075831426} {237615480} {372804156} {516732084} {642507183} {813057462} (3.36)
{084516732} {246381705} {381705246} {507183642} {651408273} {831426075}
{084732516} {246705381} {381246705} {507642183} {651273408} {831075426}
{138570624} {264318750} {426075831} {561048723} {723561048} {840327165}
{138624570} {264750318} {426831075} {561723048} {723048561} {840165327}
{156372804} {273408651} {408651273} {570624138} {732516084} {804372156}
{156804372} {273651408} {408273651} {570138624} {732084516} {804156372}
Очевидно, чтоS-блоки являются, наиболее, устойчивыми к корреляции
криптоанализа, так как их выход независим в то же время от каждой из
входных переменных. Эти S-блоки могут быть рекомендованы для
30
практического использования в приложениях, где требуется максимальная
независимость выхода криптографических структур от их ввода.
31
3.5 Вывод
В третьей главе были рассмотрены: понятие алгебраическойиммунности,
где приведен пример функции анигилятора, определение корреляционного
иммунитета и его реализации для случая с одной переменно и двух
переменных.
32
ЗАКЛЮЧЕНИЕ
Исследование 3-функций является актуальной темой, в которой многие
вопросы нуждаются в более глубокой доработке, например: корректирующие
коды, поиск слабых таблиц подстановок, адаптация программных средств,
ориентированных на работу с многозначной логикой.
В работе представлены примеры алгебраической иммунности и
корреляционной иммунноститрехзначных функций. А так же в первой главе
введены некоторые основные понятия, с помощью которых были реализованы
выше сказанные примеры.
33
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Жданов, О.Н. Метод синтеза алгебраической нормальной формы
функций многозначной логики / А.В. Соколов, О.Н. Жданов, О.А. Айвазян
Одесса, СибГАУ им. М.Ф. Решетнева С.70-73. Текст: непосредственный.
2. Неб, А.В. Исследование алгебраической степени нелинейности
подстановочных конструкций, основанных на нормальной форме функций
многозначной логики / А.В. Неб, О.Н. Жданов Красноярск, СибГАУ им. М.Ф.
Решетнева, 2018 С. 8-9. Текст: непосредственный.
3. Подсчет расстояния Хэмминга на большом наборе данных Текст:
электронный // URL: https://habr.com/post/211264/(дата обращения 13.02.2020).
4. Алексеёв,
математики/Е.К.
Е.К.
Теоретические
Алексеёв
основы прикладной
Москва:
Московский
дискретной
государственный
университет им. М. В. Ломоносова, 2011 С. 5-10. Текст: непосредственный.
5. Селезнева, С.Н. О сложности обобщенных полиномов k-значных
функций/С.Н. Селезнева, А.Б. Дайняк Москва, ВЕСТН. МОСК. УН-ТА. СЕР.
15.
ВЫЧИСЛ.
МАТЕМ.
непосредственный.
6. Халявин,А.В.
И
КИБЕРН.,
Оценка
2008
нелинейности
С.
34-35.
Текст:
корреляционно-иммунных
булевых функций / А. В. Халявин. Москва, Московский государственный
университет им. М. В. Ломоносова, 2011 С. 35-36.Текст: непосредственный.
7. Алексеев,Е.К.
минимальных
Классификация
корреляционно-иммунных
корреляционно-иммунных
булевых
функций
от
4
и
и
5
переменных / Е. К. Алексеев, Е. К. КарелинаМГУ им. М.В. Ломоносова,2015
С. 23-26. Текст: непосредственный.
8. Функции k-значной логики. Элементарные функции. Лемма об
аналоге
правила
де
Моргана
Текст:
электронный
//
URL:
https://3dstroyproekt.ru/(дата обращения 10.04.2020).
9. ФСЭК России: официальный сайт Текст: электронный // URL
http://bdu.fstec.ru/threat(дата обращения 11.04.2020).
10. Sokolov,A.V. Correlation immunity of three valued logic functions/
A.V. Sokolov, O.N. Zhdanov Odessa, National Polytechnic University С. 187188.Текст: непосредственный.
34
11. Соколов, А.В. Криптографические конструкции на основе функций
многозначной логики /А.В.Соколов, О.Н.Жданов Одесса, СибГАУ им. М.Ф.
Решетнева Текст: непосредственный.
35
Отзывы:
Авторизуйтесь, чтобы оставить отзыви хорошего настроения
удачи
успехов в конкурсе
Наверное было затрачено много времени и труда на работу
Продолжай свое исследование
Админам респект
Красиво написанная работа
Так держать
Молодец
Интересная работа!