thesis.tex

\documentclass{bachelor_thesis}


\begin{document}

\theoremstyle{definition}
\newtheorem{algorithm1}{Алгоритм}[chapter]





\abstractUkr

Дипломну роботу виконано на 43 аркушах, вона містить 1 додаток та перелік посилань на використані джерела з 16 найменувань. У роботі наведено 3 рисунки та 4 таблиці.


Метою даної дипломної роботи є аналіз, уточнення та застосування методів дослідження марковських SP-мереж на стійкість до диференціального 
криптоаналізу.

Об’єктом дослідження є інформаційні процеси в системах криптографічного захисту.

Предметом дослідження є алгоритми оцінювання SP-мереж на стійкість до диференціального криптоаналізу.

В роботі проводиться уточнення та застосування методів для оцінки стійкості SP-мереж до диференціального криптоаналізу на прикладі шифру ДСТУ~7624:2014.

Основні результати роботи представлено у вигляді тез доповіді на
ХVІІІ Міжнародній науково-практичної конференції «Безпека інформації у інформаційно-телекомунікаційних системах» (Київ, 25-26 травня 2016 р.) та 
XIV Всеукраїнська науково-практична конференція студентів, аспірантів та молодих вчених «Теоретичні i прикладні проблеми фізики, математики та інформатики» (Київ, 26-28 травня 2016 р.).

Ключові слова: SP-мережа, диференціальний криптоаналіз, шифр ДСТУ~7624:2014, диференціальна ймовірність.


\abstractRU
Дипломную работу выполнено на 43 листах, она содержит 1 приложение и перечень использованных источников из 16 наименований. В работе приведены 3 рисунки и 4 таблицы.


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

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

Предметом исследования являются алгоритмы оценки SP-сетей на устойчивость к дифференциальному криптоанализу.

В работе проводится уточнение и применение методов для оценки устойчивости SP-сетей к дифференциальному криптоанализу на примере шифра ДСТУ ~ 7624:2014.

Основные результаты работы представлены в виде тезисов на
XVIII Международный научно-практической конференции «Безопасность в информационно-телекоммуникационных системах» (Киев, 25-26 мая 2016) и
XIV Международная научно-практическая конференция студентов, аспирантов и молодых ученых «Теоретические и прикладные проблемы физики, математики и информатики» (Киев, 26-28 мая 2016).

Ключевые слова: SP-сеть, дифференциальный криптоанализ, шифр ДСТУ~7624:2014, дифференциальная вероятность.


\abstractEng

The full extent of the thesis is 43 pages. It contains 1 appendice and 16 references. Four figures and 2 tables are given in the thesis.

The goal of this thesis is the analysis, specification, and application of research methods of Markov SP-networks for resistance to differential cryptanalysis.

The object of research is the information processes in cryptographic protection systems.

The subject of research is the assessment algorithms for SP-networks resistance to differential cryptanalysis.

In the presented thesis the Markov SP-networks resistance to differential cryptanalysis
is assessed, taking the DSTU~7624:2014 cipher as the illustrative example.

The main ideas of the thesis were published in the Proceedings of the ХVІІІ International Scientific and Practical Conference “Information and Communication Systems Security” (Kiev, 25-26 may 2016) and XIV All-Ukrainian Scientific and Practical Conference “Theoretical and Applied Problems of Physics, Mathematics, and Computer Science” (Kiev, 26-27 may 2016).

Keywords: SP-network, differential cryptanalysis, DSTU~7624:2014 cipher, differential probability.


\tableofcontents


\shortings
$V_{u}$ --- простір $u$-бітних векторів.
	
$(V_{u})^{m}$ --- простір $m$ бітних векторів з $u$-бітними координатами.
	
$wt(x)$ --- кількість не нульових елементів вектору $x$. 
	
$[P]$ --- дужки Айверсона: $[P]$ дорівнює 1, якщо P -- істинне, та 0, якщо P -- хибне.

$\overline{\sum_{x}}$ --- середня сума: якщо $x \in X$, то $\overline{\sum_{x}} \equiv \frac{1}{|x|}$. 


\intro
Одним із потужних методів сучасного криптоаналізу симетричних шифрів є диференціальний криптоаналіз, запропонований в 1991 
році Біхамом і Шаміром \cite{Shamir-biham1}. Стійкість до нього є одним з обовязкових критеріїв при розробці та аналізі сучасних блочних шифрів.
Задача доказової стійкості схем и шифрування до диференціального аналізу 
була сформульована К. Ніберг та Л.Р. Кнудсеном \cite{Knudsen}. В сучасній теорії 
розрізняють теоретичну та практичну стійкість до диференціального аналізу. Для 
дослідження практичної стійкості необхідно знайти диференціальну характеристику, 
що має найбільшу ймовірність, для дослідження теоретичної стійкості -- диференціал, 
що має найбільшу ймовірність. Хоча проведення атаки за допомогою високоймовірних 
диференціальних характеристик є найбільш легким і зручним способом криптоаналізу, але забезпечення практичної стійкості не 
гарантує стійкості в цілому.

Відповідна задача наразі не розв’язана в загальному виді, існуючі
моделі та методи застосовні лише в окремих випадках та часто повертають
неадекватні з точки зору практики результати. Отже, описана проблематика
вимагає глибоких та ретельних досліджень.

Метою даної роботи є розробка, аналіз, уточнення та застосування нових методів 
дослідження марковських SP-мереж на стійкість до диференціального 
криптоаналізу.

Для досягнення поставленої мети необхідно виконати такі основні завдання:
\begin{itemize}
	\item виконати аналіз структури марковської SP-мережі;
	\item дослідити методи побудови матриць верхніх меж імовірностей диференціалів;
	\item уточнити методи побудови матриць верхніх меж імовірностей диференціалів;
	\item реалізувати алгоритм знаходження верхніх меж імовірностей диференціалів та
експериментально знайти такі імовірності для шифру ДСТУ~7624:2014 та його модифікацій.
\end{itemize}

Об’єктом дослідження даної роботи є інформаційні  процеси  в  системах криптографічного захисту.

Предметом дослідження даної роботи є алгоритми автоматичного оцінювання стійкості марковських SP-мереж до диференціально криптоаналізу.

Методи дослідження: методи лінійної та абстрактної алгебри, теорії імовірностей, математичної статистики, комбінаторного аналізу, теорії кодування, теорії складності алгоритмів, методи комп’ютерного та статистичного моделювання.

Наукова новизна полягає в тому, що уточнені методи оцінки стійкості марковських SP-мереж на стійкість до диференціального криптоаналізу 
із урахуванням особливостей марковських перетворень та комбінування різних S-блоків.

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

Основні результати роботи представлено у вигляді тез доповіді на
ХVІІІ Міжнародній науково-практичної конференції «Безпека інформації у інформаційно-телекомунікаційних системах» (Київ, 25-26 травня 2016 р.) та 
XIV Всеукраїнська науково-практична конференція студентів, аспірантів та молодих вчених «Теоретичні i прикладні проблеми фізики, математики та інформатики» (Київ, 26-28 травня 2016 р.).



\chapter{ФОРМАЛЬНИЙ ОПИС SP-МЕРЕЖ}\label{ch:01}
В цьому розділі наведено теоретичні відомості та основні теоречні поняття з диференціального криптоаналізу.
Наведено формальний опис SP-мереж та теоретичні результати щодо стійкості SP-мереж. 
Розглянуто алгоритм шифрування ДСТУ~7624:2014 та наведені наявні оцінки стійкості цього алгоритму.  


\section{Сутність дифренціального криптоаналізу}
Диференціальний криптоаналіз відноситься до атак останнього раунду.
Оновною метою проведення аналізу є встановлення раундового ключа останнього раунду $k_{r}$.
Розглянемо схему атаки на ітеративний блочний шифр побудовану за допомогою диференціального криптоаналізу.

Нехай на просторі $(V_{u})^{m}$ задано деякі операції $\circ$ та $\bullet$ блочного вигляду які задають структуру абелевої групи. 
Нехай $L \colon(V_{u})^{m} \to (V_{u})^{m}$ -- лінійне перетворення (відносно операції $\circ$), тоді індексом розгалудження $L$ називається величина $B$:
\begin{equation*}
	B = B(L) = \min_{x \ne 0} \left \{wt(x)+wt(L(x)) \right \}.
\end{equation*}

Нехай $V_{q}$ простір з операціями $\circ$ та $\bullet$. $E$ -- ітеративний блоний шифр.
$E = F_{1,r-1} \times f_{r}$ -- композиція перетворень, де $f_{r}$ -- останній раунд,
$F_{1,r-1}$ -- всі інші раунди. $(X,X^{'})$ -- пари відкритих текстів, для яких 
$X^{'}=X \circ a$ для фіксованого $a$. $(Y,Y^{'})$ -- відповідні парам відкритих текстів, для яких
$Y = F_{1,r-1}(X), Y^{'} = F_{1,r-1}(X^{'})$. Для деякого $b$ виконується $Y^{'} = Y \bullet b$ для деякого $a$
з високою імовірністю $p$ $(p \gg 2^{-q})$. 

Побудуємо статичний розпізнавач для ключа $k_{r}$:
\begin{enumerate}
	\item Накопичуємо деяку кількість пар випадкових відкритих текстів $(X,X^{'})$
	таких, що $X^{'}=X \circ a$ та відповідних їм пар шифртекстів $(C,C^{'})$;
	\item Розшифровуємо пари $(C,C^{'})$ на один раунд та одержуємо $(Y,Y^{'})$, для кожного кандидата в ключі $k$;
	\item Перевіряємо імовірність гіпотези $Y^{'} = Y \bullet b$, якщо імовірність близька до 
	$p$, то ключ вгадано вірно;
\end{enumerate}

Також можна поудувати структурний розаізнавач: із значень $(C,C^{'})$ та припущення, що 
$Y^{'} = Y \bullet b$, для кожної пари обчислюємо можливі значення ключа $k_{r}$. Коли одне із
значень почне домінувати атака припиняється.

Для SP-мереж, в яких додавання із ключем зазвичай відбувається за допомогою операції $\oplus$,
продуктивним є підхід Біхама та Шаміра~\cite{Shamir-biham1,Shamir-biham2}. В цій роботі розглядались пари текстів із фіксованою різницею відносно 
операції $\oplus$. Вивчення диференціального криптоаналізу із використанням інших операцій майже не проводилось.

Біхам та Шамір показали, що для успішного розпізнавання необхідно $O(p^{-1})$ відкритих текстів.

Основні теоретичні поняття диференціального криптоаналізу наведені нижче.

Диференціал булевої функції $f$ відносно операції ($\circ$,$\bullet$) -- це пара двійкових векторів 
$(a,b)$, для яких існує значення $x$ таке, що виконується співвідношення:
\begin{equation*}
	f(x \circ a) \bullet (f(x))^{-1}=b,
\end{equation*}
де через $(f(x))^{-1}$ позначено елемент, обернений до $f(x)$ відносно операції~$\bullet$.

Імовірність диференціала булевої функції $f$ відносно операції ($\circ$,$\bullet$) визначається
за такою формулою:
\begin{equation*}
	d^{f}(a,b)=\sum_{x}[f(x \circ a) \bullet (f(x))^{-1}=b]
\end{equation*}

Поняття введені Ковальчук~\cite{Kovalchuk} наведені нижче.

Середня за ключами імовірність диференціала булевої функції $f_{k}$ відносно операції ($\circ$,$\bullet$) в точці $x$:
\begin{equation*}
	d^{f_{k}}(x,a,b)=\sum_{k}[f_{k}(x \circ a) \bullet (f_{k}(x))^{-1}=b]
\end{equation*}
  

Максимальна диференціальна імовірність параметризованої ключем функції $f_{k}$, враховуючи всі точки входу:
\begin{equation*}
	MDP(f_{k}) = \max_{a \ne 0,b,x} d^{f_{k}}(x,a,b).
\end{equation*}

Середня за ключами імовірність диференціалу $(a,b)$ параметризованої ключем функції~$f_{k}$:
\begin{equation*}
	EDP^{f_{k}}(a,b) = \overline{\sum_{x}} d^{f_{k}}[k](a,b).
\end{equation*}

Максимальна середня імовірність диференціала $(a, b)$ булевої функції $f_{k}$:
\begin{equation*}
	MEDP(E) = \max_{a \ne 0,b}EDP^{f_{k}}(a,b).
\end{equation*}

Нехай $E$ – ітеративний блочний шифр, що складається з послідовних
раундових перетворень $f_{k_{1}}^{(1)}, f_{k_{2}}^{(2)}, f_{k_{3}}^{(3)},...,f_{k_{r}}^{(r)}$. Раундові ключі $k_{i}$ вважаються
незалежними та рівномірно розподіленими.

Диференціальна характеристика шифру $E$ – послідовність бітових
векторів $\Omega$ ($\omega_{1},\omega_{2},\omega_{3},...,\omega_{r}$) , де всі $\omega_{i} \in V_{q} \backslash \{0\}$. 
Диференціальна характеристика розглядається як послідовність змін даних між раундами під час
шифрування, тобто якщо подати на вхід два повідомлення $X_{0}$ та $X_{0}^{'}$ такі, що
$X_{0} \circ (X_{0}^{'})^{-1} = \omega_{0}$, то матимемо $X_{1} \circ (X_{1}^{'})^{-1} = \omega_{1}$, $X_{2} \circ (X_{2}^{'})^{-1} = \omega_{2}$,..., $X_{r} \circ (X_{r}^{'})^{-1} = \omega_{r}$. 
З формальної точки зору диференціальною характеристикою шифру може бути
довільна послідовність ненульових двійкових векторів потрібної довжини.

Середня за ключами імовірність диференціальної характеристики $\Omega$ в
точці $X_{0}$:
\begin{equation*}
	DP^{E}(\Omega,X_{0}) = \overline{\sum_{k_{1}}} \overline{\sum_{k_{2}}} \overline{\sum_{k_{3}}}...\overline{\sum_{k_{r}}} \prod_{i=1}^{r} [f_{k_{i}}^{(i)}(X_{i-1} \circ \omega_{i-1}) \circ (f_{k_{i}}^{(i)}(X_{i-1}))^{-1} = \omega_{i}].
\end{equation*}

Середня імовірність диференціальної характеристики $\Omega$:
\begin{equation*}
	EDP^{E}(\Omega)=\overline{\sum_{X}}DP^{E}(\Omega,X). 
\end{equation*}


В сучасній теорії, вслід за Кандоюта~\cite{Kanda} і Кнудсеном~\cite{Knudsen}, розрізняють теоретичну та практичну стійкість до 
диференціального аналізу. Блочний шифр є теоретично стійким до диференціального аналізу, якщо виконується нерівність:
\begin{equation*}
	MEDP(E) \leq 2^{-c},
\end{equation*}
для деякого порогового значення $c$.

Блочний шифр є практично стійким до диференціального аналізу, якщо виконується нерівність: 
\begin{equation*}
	\max_{\Omega}EDP^{E}(\Omega) \leq 2^{-c},
\end{equation*}
для деякого порогового значення $c$. 


Теоретична стійкість показує, що складність проведення
диференціальної атаки із використанням багатораундових диференціалів в
середньому складатиме щонайменше $2^{c}$ операцій, а практична стійкість -- що
складність проведення диференціальної атаки із використанням невеликої
кількості диференціальних характеристик складатиме щонайменше
$2^c$ операцій. 

Практична стійкість шифру гарантує захист від найпоширенішого
та (на наш час) самого потужного методу проведення диференціального
аналізу, однак не гарантує стійкості в цілому. Втім, оскільки атака із
використанням диференціальних характеристик є відносно легкою в
проведенні, обидва параметри (як теоретичної, так і практичної стійкості) є
важливими. В наш час, з огляду на наявні обчислювальні потужності, шифри
вважаються стійкими при $c \geq 80$ .

Аналіз неможливих диференціалів використовує для побудови
атаки диференціали із імовірністю 0 (тобто диференціали, які ніколи не
виникають під час шифрування). Аналіз неможливих диференціалів показує
важливість оцінювання диференціалів шифру не тільки зверху, але й знизу;
однак, на відміну від класичного диференціального аналізу, для цього методу
не існує формальної теоретичної моделі, яка дозволяє будувати аналітичні
оцінки стійкості. Наявні методи пошуку неможливих диференціалів
фактично виконують автоматичне конструювання шляхом перебору всіх
можливих раундових диференціалів та знаходження несумісних шаблонів
між ними. Втім, використання в алгоритмах шифрування нелінійних
перетворень із максимально вирівняними диференціальними ймовірностями
в цілому підвищує стійкість до даного виду аналізу.


\section{Верхні межі ймовірностей існування нетривіальних диференціалів та диференціальних характеристик SP-мереж}
SP-мережею будемо називати ітеративний блочний шифр виду:
\begin{equation*}
	E_{k}(X) = F_{K_{r}}(F_{K_{r-1}}(...(F_{K_{1}}(X)))),
\end{equation*}
де $K=(K_{1},..,K_{r}) \in (V_{u})^{mr}$ -- ключ шифрування, а $F$ раундове перетворення, яке визначається таким чином:
\begin{eqnarray*}
	F: (V_{u})^{m} &\times& (V_{u})^{m} \to (V_{u})^{m}, \\
	F(X,K) & = & f(X \bullet K), \\	
	f(X) & = &L(S(X)),
\end{eqnarray*}
де $f$ -- раундова функція, $S = (s_{1},...,s_{m})$ -- рівень нелінійних підстановок, в якому всі $S$ блоки $S_{i}: V_{u} \to V_{u}$ -- бієктивні, $L:(V_{u})^{m} \to (V_{u})^{m}$ лінійне перетворення (відносно операції $\circ$). 

Основні результати щодо теоретичної стійкості SP-мереж викладені у серії робіт Хонга, Канга, Парка та ін.~\cite{Kang,Hong,Park}. Одержані цими
дослідниками оцінки справедливі лише для шифрів, марковських відносно операції $\oplus$. Зокрема, Хонг та ін. показали~\cite{Hong}, що для двораундової SP-мережі $E$, в якій перетворення $L$ є лінійним відносно $\oplus$, задається у вигляді
матриці та має максимальний індекс розгалуження $B = B(L) = m + 1$ або майже
максимальний індекс розгалуження $B = B(L) = m$, має місце оцінка:
\begin{equation*}
	\forall x \forall a \forall b \ne 0: d^{E}(x,a,b) \leq D^{B-1},
\end{equation*}
де $D = \max_{i} MDP(s_{i})$. 

Канг та ін. показали~\cite{Kang}, що перетворення, яке задається
у вигляді $(0, 1)$-матриці, не може мати максимального індексу розгалуження.
Також у~\cite{Hong} стверджувалось, що одержана Хонгом оцінка справедлива для
перетворень із довільним індексом розгалуження, однак наведене доведення
містить помилки. 

Парк та ін. одержали більш точну оцінку стійкості для марковських SP-мереж за більш м’яких умов, ніж Хонг та ін.~\cite{Park} Позначимо для
двораундової SP-мережі $E$
\begin{eqnarray*}
	Q(s_{i}) & = & \max \{ \max_{b} \sum_{a}(d^{s_{i}}(a,b))^{B},\max_{a} \sum_{a}(d^{s_{i}}(a,b))^{B} \}, \\
	Q(E) & = & \max_{i}Q(s_{i}).
\end{eqnarray*}

Тоді, якщо перетворення $L$ із індексом розгалуження $B$ є лінійним
відносно $\oplus$, то справедлива оцінка:
\begin{equation*}
	\forall x \forall a \forall b \ne 0: d^{E}(x,a,b) \leq Q(E).
\end{equation*}

Зокрема, оскільки виконується нерівність $Q(E) \leq D^{B-1}$ , з оцінки Парка
випливає оцінка Хонга для довільного значення індексу розгалуження.
Зауважимо, що, на відміну від результатів Хонга, для доведення оцінки
Парка важлива лише лінійність $L$ відносно $\oplus$; для інших операцій ця оцінка
вже не справедлива. Також Парком було уточнено оцінки стійкості для AES-подібних шифрів;
у~\cite{Park}
використовувалась доволі складна техніка доведення, однак в подальшому
було знайдено більш просте доведення через каскадне представлення AES-подібного шифру.
Користуючись результатами Парка, Келіхер у серії робіт~\cite{keliher}
запропонував алгоритм обчислення ще більш точної оцінки верхньої межі
для нетривіальних диференціалів багатораундових AES-подібних SP-мереж.

\section{Приклад SP-мережі: алгоритм шифрування ДСТУ~7624:2014}
Новий стандарт шифрування ДСТУ~7624:2014~\cite{dstu2014} був розроблений колективом харківських криптографів на основі алгоритму шифрування «Калина»~\cite{kaluna}. 
Він прийшов на заміну міждержавному стандарту ГОСТ~28147-89 (гармонізованому як ДСТУ~ГОСТ~28147:2009~\cite{dstu2009}). 

Алгоритм ДСТУ~7624:2014 побудований на основі AES-подібної SP-мережі. Він перетворює блоки вхідного тексту довжиною 128, 256 або 512 біт у відповідні блоки шифртексту, за допомогою ключа довжиною 128, 256 або 512 біт. Розмір ключа може бути рівний розміру блоку, або може бути вдвічі більший за розмір блоку. Кількість раундів шифрування визначається довжиною ключа. 
	
	\begin{figure}[!htb]
    \centering
    \includegraphics[scale=0.9]{PNG/DSTU.png}%
    	\caption{Блок-схема алгоритму шифрування ДСТУ~7624:2014.}\label{fig:DSTU}
  	\end{figure}
	
	Вхiдний блок даних розташовується у матрицi стану;
на кожному раундi шифрування над матрицею стану
виконуються такi операцiї:
\begin{itemize}
	\item додавання iз раундовим ключем;
	\item нелiнiйна замiна ($SubBytes$);
	\item зсув рядкiв ($ShiftRows$);
	\item перемiшування стовпчикiв ($MixColumns$).
\end{itemize}



	Після останнього раунду відбувається додаткове забілювання даних із окремим раундовим ключем. На першому раунді та після останнього раунду ключі додаються до матриці стану із використанням операції додавання за модулем $2^{64}$, а в усіх інших раундах використовується побітове додавання. 
	Це схематично зображено на~рис.~\ref{fig:DSTU}. 
	
	
	Нелінійна заміна байт матриці стану відбувається за допомогою чотирьох підстановок $\pi_{0}$, $\pi_{1}$, $\pi_{2}$, $\pi_{3}$ зафіксованих у стандарті. Перемішування стовпчиків відбувається шляхом множення на циркулянтну матрицю над полем $GF(2^{8}$); це перетворення має максимально можливий індекс розгалуження $B = 9$.

	

\section{Оцінки стійкості алгоритму шифрування ДСТУ~7624:2014}
У роботі Яковлєва~\cite{YakovlevITKI} були наведені такі оцінки стійкості шифру ДСТУ~7624:2014:

  \begin{table}{|c|c|c|}{Уточнені оцінки верхніх меж імовірностей диференціалів та лінійних апроксимацій алгоритму шифрування ДСТУ 7624:2014}{table:comp32}
 	\hline
 	{Розмір блоку} & {Імовірності диференціалів} & {Імовірності лін. аппроксимацій} \\
 	\hline
 	128 біт & $2^{-87,992}$ & $2^{-83,7}$ \\
 	\hline 
 	256 біт & $2^{-175,984}$ & $2^{-167,4}$ \\
 	\hline
 	512 біт & $2^{-351,968}$ & $2^{-334,8}$ 
  \end{table}

В роботі~\cite{kisa} було наведено таке твердження:

Для шифру ДСТУ~7624:2014 з випадковими та рівноймовірними раундовими ключами, з довжиною блоку $n$ біт та $r$ раундами шифрування. Тоді при $r \geq 6$ для будь-якої бінарної операції $\circ$ на множині $V_{n}$ виконується нерівність:

\begin{equation*}	 
	 \max_{\alpha,\beta \in V_{n} \setminus \{0\}}\{d^{(\zeta_{[1,r-1]})}(\alpha,\beta)\} \leq 
	 \begin{cases}
	 2^{-80}, & \text{якщо $n=128;$}\\ 
	 2^{-160}, & \text{якщо $n=256;$}\\
	 2^{-320}, & \text{якщо $n=512.$}
	 \end{cases}\qquad
\end{equation*}	
де $d^{s}(a,b)$ імовірність  диференціалу $(a,b)$ для S-блоку $s$. $QD^{*}$ -- уточнена оцінка $QD$.
\begin{equation*}
	QD(s,B) = \max_{a,b \ne 0} \{ \sum_{c} (d^{s}(a,c))^{B},\sum_{c} (d^{s}(c,b))^{B}\}, 
\end{equation*}

У роботі Яковлєва~\cite{YakovlevITKI} було наведено обчислення величин $QD$ для імовірностей диференціалів та лінійних апроксимацій та
величин $QD^{*}$ (уточнення $QD$) для імовірностей диференціалів S-блоків алгоритму шифрування ДСТУ~7624:2014. 
Результати отримані Яковлєвим, наведені у~таб.~1.2.

\begin{table}{|c|c|c|}{Значення параметрів $QD$ та $QD^{*}$ S-блоків шифру ДСТУ~7624:2014.}{table:comp}
	\hline
	S-блок & $QD$ & $QD^{*}$ \\
	\hline
	$\pi_{0}$ & $2^{-43,98}$ & $2^{-43,996}$ \\
	\hline
	$\pi_{1}$ & $2^{-43,93}$ & $2^{-44,169}$ \\
	\hline 
	$\pi_{2}$ & $2^{-44,69}$ & $2^{-44,823}$ \\
	\hline 
	$\pi_{3}$ & $2^{-44,85}$ & $2^{-44,882}$ 
	\end{table}


\section*{~~~~~~~~Висновки до розділу~\ref{ch:01}}
В даному розділі проведено аналіз опублікованих результатів, відбір та узагальнення теоретичних
відомостей, необхідних для подальшого дослідження; також в розділі викладено принципи побудови диференціальної
атаки на ітеративний шифр. На основі проведеного аналізу встановлено, що існуючий математичний апарат дозволяє адекватно оцінювати стійкість
марковських симетричних блочних шифрів. Визначення теоретичної та практичної стійкості SP-мереж вимагає знаходження
нових, та суттєвої переробки існуючих підходів до створення відповідних
математичних моделей та методів їх оцінювання, в залежності від конкретної
структури шифруючого перетворення.


\chapter{ФОРМАЛІЗОВАНИЙ МЕТОД ОЦІНКИ СТІЙКОСТІ SP-МЕРЕЖ ДО ДИФЕРЕНЦІАЛЬНОГО КРИПТОАНАЛІЗУ}\label{ch:02}
Даний розділ присвячено дослідженню теоретичної та практичної стійкості SP-мереж до диференціального
криптоаналізу, зокрема побудові алгоритмів автоматичного оцінювання верхніх меж диференціальних імовірностей та
диференціальних характеристик для SP-мереж. Враховуючи особливості структури SP-мереж, в даному розділі розглядаються 
диференціали за операцією $\oplus$.

У 2001-2003 роках Л. Келіхер разом із В. Мейєром та С. Таваресом
розробив декілька складних, але елегантних методик обчислення параметрів
стійкості шифру AES до лінійного криптоаналізу, що одержали назву алгоритмів
КМТ1 та КМТ2 відповідно. Згодом Келіхер переніс цю методику на
диференціальний криптоаналіз, а потім адаптував її для обчислення параметрів
стійкості алгоритму шифрування Camellia, який побудовано на основі схеми
Фейстеля. 

Алгоритми Келіхера для розрахунків використовували відомості про
повний розподіл диференціальних імовірностей S-блоків та шляхи проходження
активних байтів через лінійні перетворення. Розрахунки Келіхера дозволили
уточнити верхні оцінки для імовірностей диференціалів для вказаних шифрів:
$2^{-111}$ для AES (проти аналітичного значення $2^{-96}$) та $2^{-55}$ для Camellia (проти
аналітичного значення $2^{-28}$).

Слід зазначити, що методики Келіхера застосовні лише для алгоритмів
шифрування, що є марковськими відносно операції $\oplus$, і при цьому вони
переускладнені для досягання більшої ефективності обрахунків. В даному розділі
наводяться більш прості методики визначення верхніх меж імовірностей
диференціалів, опубліковані в~\cite{NDR} та уточнені мною, що застосовні для довільних немарковських блокових шифрів,
побудованих із використанням S-блоків на основі структур SP-мереж.

\section{Алгоритми побудови оцінок стійкості немарковських SP-мереж до диференціального криптоаналізу}

В основі алгоритмів лежить ідея Келіхера~\cite{keliher}, а саме: заміна точних значень різниць $\alpha$, $\beta$ на так звані «шаблони». Для заданого $\alpha \in V_{n} \equiv (V_{u})^{m}$ визначимо шаблон  $T\alpha = \widehat{\alpha} \in V_{m}$ за таким правилом: $\widehat{\alpha}_{i} = 0$, якщо $\alpha_{i} = 0$ та $\widehat{\alpha}_{i} = 1$, якщо $\alpha_{i} \ne 0$. 
Використовуючи шаблони, ми можемо побудувати для кожного $r$ матрицю верхніх меж імовірностей диференцiалiв ($UB^{[r]}[\widehat{\alpha},\widehat{\beta}]$) таку, щоб для довільних векторів $\alpha$, $\beta$ виконувалась рівність:
\begin{equation*}
	d(\alpha,\beta)^{[r]} \le  UB^{[r]}[\widehat{\alpha},\widehat{\beta}],
\end{equation*}
під $d(\alpha,\beta)^{[r]}$ маємо на увазі імовірність $r$-раундового диференціалу $(\alpha \beta)$. 

Нехай $L$ -- лінійне перетворення алгоритму шифрування. Для того, щоб встановити кількість векторів $\gamma$, які відповідають таким умовам:  $T\gamma = \widehat{\gamma}$ та $T(L(\gamma)) = \widehat{\beta}$, вводимо допоміжну матрицю $W[\widehat{\alpha},\widehat{\beta}]$:
\begin{equation*}
	W[\widehat{\alpha},\widehat{\beta}] = \left \arrowvert \left \{ x \in V_{n}: Tx=\widehat{\alpha}, T(L(x)) = \widehat{\beta} \right \} \right \arrowvert.
\end{equation*}

Матриця $W$ показує кількість способів отримати із заданого вхідного шаблону $\widehat{\alpha}$ заданий вихідний шаблон $\widehat{\beta}$ для лінійного перетворення $L$. 
Таким чином, маємо наступну оцінку:
\begin{equation*}
	d(\alpha,\beta)^{[r]} \le \sum_{\widehat{\gamma}}UB^{[r-1]}[\widehat{\alpha},\widehat{\gamma}] \cdot W[\widehat{\gamma},\widehat{\beta}] \cdot p^{wt(\widehat{\beta})},
\end{equation*}  
де $p=\max(MDP(s_{i}))$.

Підсумуючи наведене вище, наведемо два алгоритми обчислення
верхніх меж диференціальних імовірностей для немарковських SP-мереж які були наведені в~\cite{NDR}. Ці
алгоритми виступають аналогами алгоритмів КМТ1 та КМТ2.

\begin{algorithm1}
Обчислення верхніх меж імовірностей диференціалів SP-мережі без використання точних значень розподілів диференціальних імовірностей S-блоків.

Вхід: SP-мережа $E$, кількість раундів $r$.

Вихід: матриця верхніх меж $UB^{[r]}[*,*]$.

Передобчислення: матриця $W[*,*]$, число $p=\max(MDP(s_{i}))$.
\begin{enumerate}
	\item  Для всіх шаблонів $(\widehat{\alpha},\widehat{\beta})$ встановити $UB^{[2]}[\widehat{\alpha},\widehat{\beta}]=\min \left \{p^{B-1},p^{wt(\widehat{\beta})} \right \}$.
	\item  Для $t = 3, 4, ... r$ виконати такі кроки:
	\begin{enumerate}
		\item Для всіх шаблонів $\widehat{\beta}$ виконати такі кроки:
		
			Встановити:
			\begin{equation*}			
			 M = \min_{\widehat{\gamma}}UB^{[t-1]}[\widehat{\gamma},\widehat{\beta}].
			\end{equation*}
			Для всіх шаблонів $\widehat{\alpha}$ встановити:
			\begin{equation*}
				UB^{[t]}[\widehat{\alpha},\widehat{\beta}]=\min\left\{M, \sum_{\widehat{\gamma}}UB^{[t-1]}[\widehat{\alpha},\widehat{\gamma}] \cdot W[\widehat{\gamma},\widehat{\beta}] \cdot p^{wt(\widehat{\beta})} \right \}. 
			\end{equation*}
		
	\end{enumerate}
	\item Повернути матрицю $UB^{[r]}[*,*]$.
\end{enumerate}
\end{algorithm1}




 
\begin{algorithm1}
Обчислення верхніх меж імовірностей диференціалів SP-мережі із використанням точних значень розподілів диференціальних імовірностей S-блоків.

Вхід: SP-мережа $E$, кількість раундів $r$.

Вихід: матриця верхніх меж $UB^{[r]}[*,*]$.

Передобчислення: матриця $W[*,*]$, число $p=\max(MDP(s_{i}))$, розподіли $u_{i}(A) (A=\overline{1,m})$.
\begin{enumerate}
	\item  Для всіх шаблонів $\widehat{\alpha},\widehat{\beta}$ встановити:
\begin{equation*}	 
	 UB^{[2]}[\widehat{\alpha},\widehat{\beta}]=\min \left \{\sum_{i=1}^{W[\widehat{\alpha},\widehat{\beta}]} u_{i}(wt(\widehat{\alpha})) \cdot u_{i}(wt(\widehat{\beta})), p^{wt(\widehat{\beta})} \right \}.
\end{equation*}	
	\item  Для $t = 3, 4, ... r$ виконати такі кроки:
	\begin{enumerate}
		\item Для всіх шаблонів $\widehat{\beta}$ виконати такі кроки:
		
			Встановити:
			\begin{equation*}
			 M = \min_{\widehat{\gamma}}UB^{[t-1]}[\widehat{\gamma},\widehat{\beta}].
			\end{equation*}			
			Для всіх шаблонів $\widehat{\alpha}$ встановити:
			\begin{equation*}
				UB^{[t]}[\widehat{\alpha},\widehat{\beta}]=\min \left \{M, \sum_{\widehat{\gamma}:W[\widehat{\gamma},\widehat{\beta}]>0}UB^{[t-1]}[\widehat{\alpha},\widehat{\gamma}] \cdot \sum_{i=1}^{W[\widehat{\gamma},\widehat{\beta}]} u_{i}(wt(\widehat{\beta})) \right \}. 
			\end{equation*}
		
	\end{enumerate}
	\item Повернути матрицю $UB^{[r]}[*,*]$.
\end{enumerate}
\end{algorithm1}


\subsection{Передобчислення матриці $W$}
Нагадаємо, що, за визначенням, елементи матриці $W[\widehat{\alpha},\widehat{\beta}]$ дорівнюють:
\begin{equation*}
	W[\widehat{\alpha},\widehat{\beta}] = \left \arrowvert \left  \{ x \in V_{n}: Tx=\widehat{\alpha}, T(L(x)) = \widehat{\beta} \right \} \right \arrowvert.
\end{equation*}

Найпростіший спосіб знаходження $W[\widehat{\alpha},\widehat{\beta}]$ -- це безпосередній перебір всіх
можливих $x$ та обчислення відповідних шаблонів від входу та виходу. Цей метод
безвідмовно працює для невеликих довжин вхідних векторів, але вже для $n=64$
він стає обчислювально невиконуваним. Також, безпосередній перебір може стати в нагоді, коли лінійне 
перетворення розпадається на декілька незалежних відображень.


Лінійне перетворення $L:V_{n} \to V_{n}$ задано матрицею $L$ над $V_{u}$. Через матрицю $L_{\widehat{\alpha},\widehat{\beta}}$ позначимо таку підматрицю матриці $L$, 
яка розташована на перетині тих стовпчиків, для яких $\widehat{\alpha}_{i} = 1$, та тих
рядків, для яких $\widehat{\beta}_{i} = 0$. 
Через $W_{\ge}[\widehat{\alpha},\widehat{\beta}]$ позначимо кількість розв'язків рівняння $L_{\widehat{\alpha},\widehat{\beta}} \cdot z = 0$. Звідси маємо: 
\begin{equation*}
	W_{\ge}[\widehat{\alpha},\widehat{\beta}] = (2^{u})^{wt(\widehat{\alpha})-rank(L_{\widehat{\alpha},\widehat{\beta}})}.
\end{equation*}

Якщо лінійне перетворення задається $MDS$-матрицею, можна значно спростити підрахунок $W_{\ge}[\widehat{\alpha},\widehat{\beta}]$. 
Так як довільна підматриця $MDS$-матриці є невиродженою, то ранг будь-якої довільної підматриці $MDS$-матриці буде рівний $rank(L_{\widehat{\alpha},\widehat{\beta}})=min(wt(\widehat{\alpha}),wt(\widehat{\beta}))$. 
Звідси випливає рівність:
\begin{equation*}
	W_{\ge}[\widehat{\alpha},\widehat{\beta}] = (2^{u})^{wt(\widehat{\alpha}) -min(wt(\widehat{\alpha}),wt(\widehat{\beta}))}.
\end{equation*}

Із значень $W_{\ge}[\widehat{\alpha},\widehat{\beta}]$ знаходяться значення $W[\widehat{\alpha},\widehat{\beta}]$ за допомогою формул включення-виключення:
\begin{eqnarray*}
	W'[\widehat{\alpha},\widehat{\beta}] & = & \sum_{k=0}^{wt(\widehat{\alpha})} \sum_{\substack{\widehat{c}:\widehat{c} \prec \widehat{\alpha},\\ wt(\widehat{c})=k}}
	(-1)^{wt(\widehat{\alpha})-k} \cdot W_{\ge}[\widehat{\alpha},\widehat{c}], \\
	W[\widehat{\alpha},\widehat{\beta}] & =  & \sum_{k=0}^{wt(\widehat{\beta})} \sum_{\substack{\widehat{c}:\widehat{c} \prec \widehat{\beta},\\ wt(\widehat{c})=k}}
	(-1)^{wt(\widehat{\beta})-k} \cdot W'[\widehat{c},\widehat{\beta}],
\end{eqnarray*}
де символом $\prec$ позначено відношення домінування на бітових векторах.

\subsection{Обчислення границь розподілів імовірностей диференціалів комбінацій активних S-блоків}

Нехай $u_{i}(A) (A=\overline{1,m})$ -- послідовності верхніх
меж ненульових імовірностей диференціалів комбінацій з $A$ активних $S$-блоків, які
відсортовані у порядку спадання. Ці послідовності обчислюються як A-мірна згортка відсортованих розподілів імовірностей
диференціалів задіяних $S$-блоків.

Для деякого зафіксованого $\alpha \in V_{u}$ розглянемо всі $\beta \in V_{u}$. Пронумеруємо ветори $\beta \ne 0$ так, щоб послідовність $d_{\alpha,i}=d^{S_{k}}(\alpha,\beta_{i})$ була незростаючою.
Таким чином $u_{i}(1)=\max_{\alpha \ne 0}d_{\alpha,i}$. Тоді послідовність $u_{i}(1)$ є незростаючою.

Послідовність $u_{i}(A)$ обчислюється за індукцією:
\begin{enumerate}
\item обчислюється згортка послідовностей $(v_{i}(A))=(u_{i}(A-1)) \oplus (u_{i}(1))$;
\item $(u_{i}(A))$ -- відсортована послідовність $(v_{i}(A))$.
\end{enumerate} 

Послідовність $u_{i}(A)$ можна подати за допомогою списків $\{ p_{j}(A),N_{j}(A)\}$, де $p_{j}$ -- значення імовірностей $u_{i}(A)$, а $N_{j}(A)$ 
кількість входжень значень $p_{j}$ у $u_{i}(A)$. Тоді обчислити згортку $(u_{i}(A-1)) \oplus (u_{i}(1))$ можна так:
\begin{enumerate}
	\item обчислються всі можливі значення добутків $p_{l}(A-1) \cdot p_{t}(1)$;
	\item значення добутків відсортовуються та залишаємо тільки неповторювані у послідовність $p_{j}(A)$;
	\item для одержаних значень послідовності $p_{j}(A)$ обчислюємо:
	\begin{equation*}
		N_{j}(A)=\sum_{l,t}N_{l}(A-1) \cdot N_{t}(1),	
	\end{equation*}
	де $l,t$ такі, що $p_{j}(A)=p_{l}(A-1)p_{t}(1)$.
\end{enumerate}


\begin{algorithm1}
Обчислення $\sum_{i=1}^{W[\widehat{\alpha},\widehat{\beta}]} u_{i}(wt(\widehat{\alpha})) \cdot u_{i}(wt(\widehat{\beta}))$.

Вхід: значення $\widehat{\alpha},\widehat{\beta}$.

Вихід: значення суми.

Передобчислення: значення $W[\widehat{\alpha},\widehat{\beta}]$, розподіли $u_{i}(wt(\widehat{\alpha}))$ та $u_{i}(wt(\widehat{\beta}))$ подані в вигляді списків  $\{ p_{i}(A),N_{i}(A)\}$ та  $\{ p_{j}(A),N_{j}(A)\}$ відповідно.

$sum := 0, W := W[\widehat{\alpha},\widehat{\beta}],i := 1, j := 1$
\begin{enumerate}
	\item $m = \min \{ N_{i},N_{j}\}$
	\item Якщо $m \leq W$ тоді:
	\begin{enumerate}
		\item $sum := sum + p_{i} \cdot p_{j} \cdot m;$
		\item якщо $N_{i} \leq N_{j}$ тоді:
			
		$i:=i+1;$
		
		$N_{j} := N_{j} - m;$
		
		інакшке:
		
		 $j:=j+1;$
		
		$N_{i} := N_{i} - m;$
		
	\end{enumerate}
	\item інакше:
	\begin{enumerate}
		\item $sum := sum + p_{i} \cdot p_{j} \cdot W;$
		\item повернути $sum;$
	\end{enumerate}
	\item $W := W - m.$
\end{enumerate}
\end{algorithm1}

\subsection{Властивості матриці $UB$}
Слід зазначити, що метою обчислення матриці верхніх меж імовірностей диференціалів SP-мережі є не тільки отримання аналітичних результатів щодо теоретичної (доказової) стійкості до диференціального криптоаналізу.
Так як значення матриці визначають верхні оцінки меж імовірностей диференціалів, то там, де диференціал рівний нулю -- диференціал неможливий.
Тобто кількість нулів в матрці $UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$ дає можливість провести аналіз неможливих диференціалів. 
Аналіз неможливих диференціалів являється альтернативною версією класичного диференціального криптоаналізу.

Також матриця $UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$ має такі властивості:
\begin{enumerate}[1)]
	
	\item $UB^{[t]}[0,0] = 1$;
	\item перший рядок рівний $0$ (крім елемента $UB^{[t]}[0,0]$);
	\item перший стовпчик рівний $0$ (крім елемента $UB^{[t]}[0,0]$).

\end{enumerate}



\section{Особливості застосування алгоритмів до алгоритму шифрування ДСТУ~7624:2014}
Ми розглядаємо алгоритм шифрування ДСТУ~7624:2014 з розміром блоку 128 біт.  
Для ДСТУ~7624:2014 перетворення $MixColumns$ задається матрицею розмірності $8 \times 8$. Проте лінійне перетворення перетворює 16 бітні вектори в 16 бітні вектори, тому для обрахунку вводиться нова матриця $W_{full}[\widehat{\alpha},\widehat{\beta}]$. $W_{full}[\widehat{\alpha},\widehat{\beta}]$ обраховується з передобчисленої матриці $W$:
\begin{equation*}
	W_{full}[\widehat{\alpha},\widehat{\beta}] = W[\widehat{c_{1}},\widehat{\beta_{1}}] \cdot W[\widehat{c_{2}},\widehat{\beta_{2}}],  
\end{equation*}
де $\widehat{c} = ShiftRows(\widehat{\alpha})$, а індекси 1 та 2 відповідають першим 8 бітам та наступним 8 бітам вектору відповідно.
	 
ДСТУ 7624:2014 відноститься до класу марковських SP-мереж тому ми уможемо уточнити формулу для обчислення матриці меж імовірностей двораундових диференціалів 
алгоритму обчислення верхніх меж імовірностей диференціалів SP-мережі без використання точних значень розподілів диференціальних імовірностей S-блоків. 
Матриця $UB^{[2]}[\widehat{\alpha},\widehat{\beta}]$ буде мати вигляд:
\begin{equation*}
	UB^{[2]}[\widehat{\alpha},\widehat{\beta}] = 	
	\begin{cases}
		\min \left \{p^{B-1},p^{wt(\widehat{\alpha})},p^{wt(\widehat{\beta})} \right \}, & wt(\widehat{\alpha})+wt(\widehat{\beta}) \ge B\\
		0, & \text{в інших випадках,}
	\end{cases}\qquad
\end{equation*} 		 
	 а матриця $UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$ буде мати вигляд:
\begin{equation*}
	UB^{[t]}[\widehat{\alpha},\widehat{\beta}]=\min \left \{M, \sum_{\widehat{\gamma}}UB^{[t-1]}[\widehat{\alpha},\widehat{\gamma}] \cdot W_{full}[\widehat{\gamma},\widehat{\beta}] \cdot p^{wt(\widehat{\beta})} \right \}. 
\end{equation*}

Для алгоритму обчислення верхніх меж імовірностей диференціалів SP-мережі із використанням точних значень розподілів диференціальних імовірностей S-блоків
мариця $UB^{[2]}[\widehat{\alpha},\widehat{\beta}]$ буде мати вигляд:
\begin{equation*}	 
	 UB^{[2]}[\widehat{\alpha},\widehat{\beta}]=\min \left \{\sum_{i=1}^{W_{full}[\widehat{\alpha},\widehat{\beta}]} u_{i}(wt(\widehat{\alpha})) \cdot u_{i}(wt(\widehat{\beta})), p^{wt(\widehat{\alpha})}, p^{wt(\widehat{\beta})}, p^{B-1} \right \},
\end{equation*}	
а матриця $UB^{[t]}(\widehat{\alpha},\widehat{\beta})$ буде мати вигляд:
\begin{equation*}
	UB^{[t]}[\widehat{\alpha},\widehat{\beta}]=\min \left \{M, \sum_{\widehat{\gamma}:W_{full}[\widehat{\gamma},\widehat{\beta}]>0}UB^{[t-1]}[\widehat{\alpha},\widehat{\gamma}] \cdot \sum_{i=1}^{W_{full}[\widehat{\alpha},\widehat{\beta}]} u_{i}(wt(\widehat{\beta})) \right \}. 
\end{equation*}
Також оцінка може бути покращена якщо замість $p^{B}$ брати $QD$ (значення $QD$ наведені у таб.~1.2). Тобто:  
\begin{equation*}
	UB^{[2]}[\widehat{\alpha},\widehat{\beta}] = 	
	\begin{cases}
		\min \left \{p^{B-1},QD,p^{wt(\widehat{\beta})} \right \}, & wt(\widehat{\alpha})+wt(\widehat{\beta}) \ge B\\
		0, & \text{в інших випадках,}
	\end{cases}\qquad
\end{equation*} 
для алгоритму 2.1,
\begin{equation*}	 
	 UB^{[2]}[\widehat{\alpha},\widehat{\beta}]=\min \left \{\sum_{i=1}^{W_{full}[\widehat{\alpha},\widehat{\beta}]} u_{i}(wt(\widehat{\alpha})) \cdot u_{i}(wt(\widehat{\beta})), p^{wt(\widehat{\alpha})}, p^{wt(\widehat{\beta})}, p^{QD} \right \},
\end{equation*}	
для алгоритму 2.2.

Як відомо нелінійна заміна байт матриці стану відбувається за допомогою чотирьох підстановок зафіксованих у стандарті $\pi_{0}$, $\pi_{1}$, $\pi_{2}$, $\pi_{3}$,
тому обчислення розподілів $u_{i}(A)$ буде виглядати дещо інакше. Як уже описувалось вище, ми працюємо з 16-бітними векторами.
\begin{enumerate}[1)]
\item Вхідний вектор розбивається на чотири 4-бітні ветори;
\item кожному біту з цих чотирьох векторів ставиться в відповідність підстановка (першому -- $\pi_{0}$, другому -- $\pi_{1}$, третьому -- $\pi_{2}$, четвертому -- $\pi_{3}$);
\item для кожного ненульового біта обчислюється розподіл $u_{i}(A)$. Загальний розподіл буде виглядати як згортка обчислених раніше $u_{i}(A)$. 
\end{enumerate}
Тобто формула для матриці $UB^{[2]}[\widehat{\alpha},\widehat{\beta}]$ буде мати вигляд:
\begin{equation*}	 
	 UB^{[2]}[\widehat{\alpha},\widehat{\beta}]=\min \left \{\sum_{i=1}^{W_{full}[\widehat{\alpha},\widehat{\beta}]} u_{i}(\widehat{\alpha}) \cdot u_{i}(\widehat{\beta}), p^{wt(\widehat{\alpha})}, p^{wt(\widehat{\beta})} \right \},
\end{equation*}	
для матриці $UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$ аналогічно:
\begin{equation*}
	UB^{[t]}[\widehat{\alpha},\widehat{\beta}]=\min \left \{M, \sum_{\widehat{\gamma}:W_{full}[\widehat{\gamma},\widehat{\beta}]>0}UB^{[t-1]}[\widehat{\alpha},\widehat{\gamma}] \cdot \sum_{i=1}^{W_{full}[\widehat{\alpha},\widehat{\beta}]} u_{i}(\widehat{\beta}) \right \}. 
\end{equation*}
  
\section{Оцінка складності та труднощі в реалізації алгоритмів}
В даному підрозділі будуть описані оцінки складності підрахунків та передобчислень даних алгоритмів та описані складності в розрахунку даних алгоритмів при застосуванні їх до 
шифру ДСТУ~7624:2014 з розміром блоку 128 біт. 



\subsection{Передобчислення матриці $W$}
Обчислення значень $W_{\ge}[\widehat{\alpha},\widehat{\beta}]$ в загальному випадку зводиться до обчислення всіх підматриць матриці
$L_{\widehat{\alpha},\widehat{\beta}}$. Всього $L_{\widehat{\alpha},\widehat{\beta}}$ -- $2^{2m}$. Складність знаходження рангу матриці методом Гауса оскладає 
$O(m^{3})$ операцій віднімання дробових чисел. Таким чином, складність обчислення занчень $W_{\ge}[\widehat{\alpha},\widehat{\beta}]$ -- $O(m^{3} \cdot 2^{2m})$. 

Якщо в основі лінійного перетворення розглядуваного алгоритму шифрування лежить $MDS$-матриця, то обчислення всіх значень $W_{\ge}[\widehat{\alpha},\widehat{\beta}]$ займає $O(4^{m})$ 
операцій побітового зсуву. Обчислення значень $W_{\ge}[\widehat{\alpha},\widehat{\beta}]$ може бути розпаралелене за параметром $\widehat{\alpha}$.

Для передобчислення $W[\widehat{\alpha},\widehat{\beta}]$, також необхідно перебрати $2^{2m}$ значень, складність обчислень $O(2^{m})$ операцій додавання цілих чисел.
Обчислення значень $W[\widehat{\alpha},\widehat{\beta}]$ може бути розпаралелене за параметром $\widehat{\alpha}$.
	 
Складність передобчислення послідовності верхніх меж ненульових імовірностей диференціалів $u_{i}(A)$ є відносно невеликою. Труднощі, які можуть виникнути в ході обрахунку, це -- похибки 
округлення та/або переповнення. 
 
\subsection{Обчислення матриці $UB$}
Для підрахунку матриці верхніх меж імовірностей $t$-раундових диференціалів $UB^{[t]}(\widehat{\alpha},\widehat{\beta})$ необхідно перебрати всі вектори $\widehat{\alpha}$
 та $\widehat{\beta}$ (це $2^{16} \times 2^{16}$ значень). Також необхідно мати обраховану матрицю $UB^{[t-1]}(\widehat{\alpha},\widehat{\beta})$. Складність алгоритму (якщо ми маємо обраховану $UB^{[t-1]}(\widehat{\alpha},\widehat{\beta})$) -- $O(2^{16})$ операцій множення дробових чисел.
Значення матриці $W_{full}$ (порядку близько $2^{128}$) значно більші за стандартні типи данних ЕОМ. 

Для зберігання $UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$ необхідні значні ресурси памяті (32 GB на одну матрицю, а таких матриць $8$). Оцінка складності обрахунку однієї матриці -- $O(2^{42})$ операцій множення дробових чисел. 

\section*{~~~~~~~~Висновки до розділу~\ref{ch:02}}
В даному розділі були наведені та уточнені алгоритми обчислення
верхніх меж імовірностей диференціалів для SP-мереж. Алгоритми, що пропонуються, 
враховують особливості структури
блокового шифру, характеристики лінійних перетворень, які використовуються
під час шифрування, та граничні значення для розподілів імовірностей
диференціалів окремих S-блоків шифру. 

Складність алгоритмів у більшості
випадків є достатньою для реалізації на персональних комп'ютерах. Очікується,
що пропоновані алгоритми дозволять для конкретних шифрів підсилити відомі
аналітичні результати щодо теоретичної (доказової) стійкості до диференціального криптоаналізу, 
отримати кількості неможливих диференціалів, що в свою чергу, характеризує 
стійкість до аналізу неможливих диференціалів.


\chapter{РЕЗУЛЬТАТИ ЕКСПЕРИМЕНТАЛЬНИХ ДОСЛІДЖЕНЬ}\label{ch:03}
В даному розділі будуть наведені результати експериментальних досліджень, а саме: застосування уточненого алгоритму 2.1 та уточненого
алгоритму 2.2 до модифікованого (спрощеного) шифру ДСТУ 7624:2014 та до алгоритму шифрування ДСТУ 7624:2014 з розміром блоку 128 біт.
В якості результата очікуємо оцінку верхніх меж імовірностей диференціалів та кількості нулів в матриці верхніх меж імовірностей диференціалів
($UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$).


\section{Передобчислення матриці $W$}
Так як в лінійне перетворення ДСТУ 7624:2014 задається $MDS$-матрицею, передобчислення матриці $W$ виконувалось за такими формулами:
\begin{eqnarray*}
	W_{\ge}[\widehat{\alpha},\widehat{\beta}] & = & (2^{u})^{wt(\widehat{\alpha}) -min(wt(\widehat{\alpha}),wt(\widehat{\beta}))}, \\
	W'[\widehat{\alpha},\widehat{\beta}] & = & \sum_{k=0}^{wt(\widehat{\alpha})} \sum_{\substack{\widehat{c}:\widehat{c} \prec \widehat{\alpha},\\ wt(\widehat{c})=k}} 
	(-1)^{wt(\widehat{\alpha})-k} \cdot W_{\ge}[\widehat{\alpha},\widehat{c}], \\
	W[\widehat{\alpha},\widehat{\beta}] & = & \sum_{k=0}^{wt(\widehat{\beta})} \sum_{\substack{\widehat{c}:\widehat{c} \prec \widehat{\beta},\\ wt(\widehat{c})=k}}
	(-1)^{wt(\widehat{\beta})-k} \cdot W'[\widehat{c},\widehat{\beta}].
\end{eqnarray*}

Результуюча матриця виявилась розрідженою. Діаграма відносної кількості нульових елементів до ненульових елементів показана на рис.~\ref{fig:zeros}. 

Ця властивість значно спрощує обрахунок матриць верхніх меж імовірностей диференціалів. Ми можемо винести в передобчислення ті $\alpha$ і $\beta$, для яких $W[\alpha,\beta] \ne 0$.


  
  \begin{figure}[!htb]
    \centering
    \includegraphics[scale=0.7]{PNG/zeros.png}%
    \caption{Діаграма відносної кількості нульових елементів до не нульових.}\label{fig:zeros}
  \end{figure}


Таких значень $\alpha$ і $\beta$ -- $40 \% $. Тим самим ми пришвидшуемо роботу алгоритмів обрахунку верхніх меж імовірностей диференціалів на $60 \% $. Ці результати справедливі 
для будь-якої SP-мережі, лінійне перетворення якої задається $MDS$-матрицею $8 \times 8$.

\section{Оцінювання стійкості модифікованого (спрощеного) шифру ДСТУ~7624:2014} 
Для попереднього дослідження була обрана модифікація алгоритму шифрування ДСТУ~7624:2014.
Розмір блоку був зменшений до 64 біт. Лінійне перетворення задається $MDS$-матрицею $4 \times 4$. Раунд шифрування не змінився:
\begin{itemize}
	\item додавання iз раундовим ключем;
	\item нелiнiйна замiна ($SubBytes$);
	\item зсув рядкiв ($ShiftRows$);
	\item перемiшування стовпчикiв ($MixColumns$).
\end{itemize}
Зсув рядкiв ($ShiftRows$) зсуває відповідні блоки вдвічі меншого розміру.
Підстановки $\pi_{0}$, $\pi_{1}$, $\pi_{2}$, $\pi_{3}$ залишились без змін. 

Для обрахунку був обраний~алг.~2.2. з уточненими формулами, тобто:
\begin{eqnarray}	 
	 UB^{[2]}[\widehat{\alpha},\widehat{\beta}] & = & \min \left \{\sum_{i=1}^{W_{full}[\widehat{\alpha},\widehat{\beta}]} u_{i}(\widehat{\alpha}) \cdot u_{i}(\widehat{\beta}), p^{wt(\widehat{\alpha})}, p^{wt(\widehat{\beta})},p^{B-1} \right \}, \\
	 UB^{[t]}[\widehat{\alpha},\widehat{\beta}] & = & \min \left \{M, \sum_{\widehat{\gamma}:W_{full}[\widehat{\gamma},\widehat{\beta}]>0}UB^{[t-1]}[\widehat{\alpha},\widehat{\gamma}] \cdot \sum_{i=1}^{W_{full}[\widehat{\alpha},\widehat{\beta}]} u_{i}(\widehat{\beta}) \right \}. 
\end{eqnarray}	
Також були проведені розрахунки за такими формулами:
\begin{eqnarray}	 
	 UB^{[2]}[\widehat{\alpha},\widehat{\beta}] & = & \min \left \{\sum_{i=1}^{W_{full}[\widehat{\alpha},\widehat{\beta}]} u_{i}(\widehat{\alpha}) \cdot u_{i}(\widehat{\beta}), p^{wt(\widehat{\alpha})}, p^{wt(\widehat{\beta})},p^{QD} \right \}, \\
	 UB^{[t]}[\widehat{\alpha},\widehat{\beta}] & = & \min \left \{M, \sum_{\widehat{\gamma}:W_{full}[\widehat{\gamma},\widehat{\beta}]>0}UB^{[t-1]}[\widehat{\alpha},\widehat{\gamma}] \cdot \sum_{i=1}^{W_{full}[\widehat{\alpha},\widehat{\beta}]} u_{i}(\widehat{\beta}) \right \}. 
\end{eqnarray}	

Для обчислення $\sum_{i=1}^{W[\widehat{\alpha},\widehat{\beta}]} u_{i}(wt(\widehat{\alpha})) \cdot u_{i}(wt(\widehat{\beta}))$ використувався Алгоритм 2.3.

Були отримані такі значення верхніх меж в залежності від номеру раунду (для формули~3.1), результати наведені в таб.~3.1.
Для формули (3.3) в таб.~3.2.
Також було підраховано кількість нульових диференціалів, результати наведені в таб.~3.3.


\begin{table}{|c|c|}{Значення верхніх меж в залежності від номеру раунду (формула 3.1).}{table:comp2}
	{\hline
	Номер раунду & Значення верхньої межі імовірності диференцiалiв \\
	\hline}
	2 & $2^{-20}$ \\
	\hline
	3 & $2^{-33.1688}$ \\
	\hline
	4 & $2^{-33.1688}$ \\
	\hline
	5 & $2^{-33.1688}$ \\
	\hline
	6 & $2^{-33.1688}$ \\
	\hline
	7 & $2^{-33.1688}$ \\
	\hline
	8 & $2^{-33.1688}$ \\	
	\hline
	9 & $2^{-33.1688}$ \\
\end{table}

\begin{table}{|c|c|}{Значення верхніх меж в залежності від номеру раунду (формула 3.3).}{table:comp6}
	{\hline
	Номер раунду & Значення верхньої межі імовірності диференцiалiв \\
	\hline}
	2 & $2^{-23.6131}$ \\
	\hline
	3 & $2^{-33.1688}$ \\
	\hline
	4 & $2^{-33.1688}$ \\
	\hline
	5 & $2^{-33.1688}$ \\
	\hline
	6 & $2^{-33.1688}$ \\
	\hline
	7 & $2^{-33.1688}$ \\
	\hline
	8 & $2^{-33.1688}$ \\	
	\hline
	9 & $2^{-33.1688}$ \\
\end{table}

\begin{table}{|c|c|}{Кількість нульових диференціалів в залежності від номеру раунду.}{table:comp3}
	{\hline
	Номер раунду & Кількість  диференцiалiв \\
	\hline}
	2 & 56190 \\
	\hline
	3 & 12800 \\
	\hline
	4 & 900   \\
	\hline
	5 & 0  \\
	\hline
	6 & 0  \\
	\hline
	7 & 0  \\
	\hline
	8 & 0  \\	
	\hline
	9 & 0  \\
\end{table}

З результатів, наведених у таб.~3.2, можна зробити висновок, що починаючи з 5 раунду нульові диференціали відсутні. 
Модифікований алгоритм шифрування ДСТУ~7624:2014 є стійким до аналізу неможливих диференціалів.
З результатів, наведених у таб.~3.1, можна зробити висновик, що алгоритм 2.2 шифрування дає грубіші оцінки ніж очікувалось.

\section{Оцінювання стійкості шифру ДСТУ 7624:2014 з розміром блоку 128~біт}
Обрахунки проводились за допомогою алг.~2.1. з уточненими формулами тобто:
\begin{eqnarray*}
	UB^{[2]}(\widehat{\alpha},\widehat{\beta}) & = & 	
	\begin{cases}
		\min \{p^{B-1},p^{wt(\widehat{\alpha})},p^{wt(\widehat{\beta})} \}, & wt(\widehat{\alpha})+wt(\widehat{\beta}) \ge B\\
		0, & \text{в інших випадках,}
	\end{cases}\qquad \\
	UB^{[t]}(\widehat{\alpha},\widehat{\beta}) & = & \min \left \{M, \sum_{\widehat{\gamma}}UB^{[t-1]}(\widehat{\alpha},\widehat{\gamma}) \cdot W_{full}[\widehat{\gamma},\widehat{\beta}] \cdot p^{wt(\widehat{\beta})} \right \}. 
\end{eqnarray*}

Використовуючи властивість розрідженості матриці $W$ для кожного $\alpha$ були обраховані всі $\beta$ для яких $W_{full}[\alpha,\beta] \ne 0$.

Слід зазначити, що це передобчислення займає $1,7$~GB памяті. 

Також підрахунок $UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$ був розпаралелений за параметром $\widehat{\alpha}$.

Обрахунок однієї матриці $UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$ займав близько 20 годин на процесорі Intel® Core™ i5-3230M CPU @ 2.60GHz $\times$ 4 під операційною системою Ubuntu~15.10 з компілятором GCC версії 5.3.1.

Отримана оцінка межі імовірностей диференціалів -- $2^{-40}$. Також було підраховано кількість нульових елементів матриці $UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$.

Графік кількості нулів в залежності від матриці $UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$ наведений на рис.~\ref{fig:zerosDSTU129}.

\begin{figure}[!htb]
    \centering
    \includegraphics[scale=1]{PNG/zerosDSTU129.png}%
    \caption{Графік кількості нулів в залежності від матриці $UB^{[t]}[\widehat{\alpha},\widehat{\beta}]$.}\label{fig:zerosDSTU129}
  \end{figure}
  
З графіка наведеного на рис. 3.1 можна зробити висновок, що починаючи з 4 раунду неможливі диференціали відсутні. 
Тобто алгоритм шифрування ДСТУ~7624:2014 є стійким до аналізу неможливих диференціалів.
З отриманої оцінки верхніх меж імовірностей диференціалів можна зробити висновок, що алгоритм 2.1 дає грубіші оцінки ніж очікувалось.  
  
\section*{~~~~~~~~Висновки до розділу~\ref{ch:03}}
В цьому розділі наведені основні результати роботи, а саме
верхні межі імовірностей диференціалів та кількості нульових диференціалів для різних раундів. 
Висновком з цих оцінок є те, що уточнені алгоритми дають грубу оцінку ($2^{-33.1688}$ для модифікованого шифру ДСТУ~7624:2014 та 
$2^{-40}$ для ДСТУ~7624:2014 з розіром блоку 128-біт). Нульові диференціали відсутні починаючи з $5$ раунду.

		

\conclusions
В результаті виконання даної роботи було проаналізовано структуру SP-мережі, 
як приклад було розглянуто алгоритм шифрування ДСТУ~7624:2014.

Було досліджено методи побудови матриць верхнiх меж iмовiрностей диференцiалiв для SP-мереж.

Було уточнено методи побудови матриць верхнiх меж iмовiрностей диференцiалiв для маркіських SP-мереж.

Програмно реалізовано алгоритми для знаходження верхнiх меж iмовiрностей диференцiалiв для маркіських SP-мереж.
Данний алгоритм було використано для знаходження верхнiх меж iмовiрностей диференцiалiв шифру ДСТУ~7624:2014 та його модифікації.

Отримані результати свічать про те, що уточнені алгоритми дають грубу оцінку ($2^{-33.1688}$ для модифікованого шифру ДСТУ~7624:2014 та 
$2^{-40}$ для ДСТУ~7624:2014 з розіром блоку 128-біт),що пов'язано, швидше за все, із використанням MDS-перетворень. 

Результати роботи дозволяють досліджувати існуючі та створювати нові надійні алгоритми
шифрування на основі марковських SP-мереж.

В подальшому планується провести більш детальне дослідження особливостей марковських перетворень та комбінування різних S-блоків
для уточнення відповідних оцінок стійкості.
	

\begin{thebibliography}
	\bibitem{dstu2014} Інформаційні технології. Криптографічний захист інфомації. Алгоритм
  симетричного блокового перетворення: ДСТУ 7624:2014. --- Держспоживстандарт України, 2014. --- 238~{\cyr\cyrs.}

	\bibitem{dstu2009} Системы обработки информации. Защита криптографическая. Алгоритмы
  криптографического преобразования: ДСТУ ГОСТ 28147:2009. --- Держспоживстандарт України, 2008. ---  28~{\cyr\cyrs.}

	\bibitem{kaluna} Горбенко~І.~Д. Перспективний блоковий
  симетричний шифр «калина» – основні положення та специфікація.~/ І.~Д.~Горбенко В.~І.~Долгов, Р.~В.~Олійников~{та ін.}~// Прикладная радиоэлектроника. --- 2007. --- {\cyr\CYRS.}~195--208.

	\bibitem{keliher}  Keliher~L. Toward provable security against differential and linear cryptanalysis for camellia and related ciphers~/ L.~Keliher. Режим доступу ---  http://ijns.femto.com.tw/contents/ijns-v5-n2/ijns-2007-v5-n2-p167-175.pdf.

	\bibitem{Park} Park~S. On the security of rijndael-like  structures against differential and linear cryptanalysis~/ S.~Park, S.H.~Sung, S.~Chee, E.J.~Yoon, J.~Lim~// Advances in Cryptology, ASIACRYPT  2002. --- 2002. --- Vol. 2501. --- P.~176--191.

	\bibitem{Kang} Kang~J.S. Practical and provable security against differential and linear cryptanalysis for  substitution-permutation networks~/ J.S.~Kang, S.~Hong, S.~Lee, O.~Yi, C.~Park, J.~Lim~// ETRI Journal. --- 2001. --- no.~23. --- P.~158--167.	
	
	\bibitem{Hong} Hong~S. Provable security against differential and linear cryptanalysis for the spn structure~/ Hong~S~// Fast Software Encryption. – FSE’00  Proceedings. --- 2001. --- P.~273--283.
	
	\bibitem{Shamir-biham1}  Biham~E. Differential cryptanalysis of des-like cryptosystems~/Biham~E., A.~Shamir~//Journal of Cryptology. --- 1991. --- Vol.~4, no.~1. --- P.~3--72.
	
	\bibitem{Shamir-biham2}  Biham~E. Differential cryptanalysis of the full 16-round des~/Biham~E., A.~Shamir~//Advances in Cryptology – CRYPTO’92. --- 1993. --- P.~487--496.
	
	\bibitem{Kanda} Kanda~M. Practical security evaluation against differential and linear cryptanalyses for feistel ciphers with spn round function~/Kanda~M.~//Selected Areas in Cryptography. -- SAC 2000, Proceedings. --- 2001. --- P.~324--338.

	\bibitem{Kovalchuk} Ковальчук~Л.В. Обобщенные марковские шифры: построение оценки практической стойкости относительно дифференциального криптоанализа~/ Ковальчук~Л.В.//Математика и безопасность информационных технологий. Материалы конференции в МГУ 25 – 27 октября 2006. --- 2007. --- {\cyr\CYRS.}~595--599.

	\bibitem{kisa} Ковальчук~Л.В. О криптографических свойствах нового нацинального стандарта шифрования украины~/Ковальчук~Л.В.~//Кибернетика и системный анализ. --- 2016. ---  \CYRT.~52, {\cyr\textnumero}~3. ---  {\cyr\CYRS.}~16--32.

	\bibitem{YakovlevITKI} Яковлєв~С.В. Уточнені оцінки стійкості алгоритму шифрування ДСТУ 7624:2014 до диференціального та лінійного криптоаналізу~/Яковлєв~С.В.~//Інформаційні технології та комп'ютерна інженерія. --- 2015. --- {\cyr\CYRS.}~176--178.
	
	\bibitem{dis_Yakovliev} {Яковлєв~С.В.} Аналітичні оцінки стійкості немарковських симетричних блочних шифрів до диференціального криптоаналізу : кандидатська дисертація~/ Яковлєв~С.В.  --- К.: НТУУ «КПІ», 2016. --- 160~{\cyr\cyrs.}
	
	\bibitem{NDR} НДР «Дослідження та застосування сучасних математичних методів окремих перетворень у системах криптографічного захисту інформації» (шифр «Мокрель»), держ. реестр №0115-004118. --- К.: НТУУ «КПІ», 2016. ---  103~{\cyr\cyrs.}
	
	\bibitem{Knudsen} Knudsen~L.R. Practically secure feistel cipher~/ Knudsen~L.R.~//Software Encryption. -- FSE’94, Proceedings. --- 1994. ---  P.~211--221.
\end{thebibliography}


\append{Лістинг програми}


\listing{Kalyna.cpp --- реалізація алг. 2.1, алг. 2.2, алг 2.3, предобчислення $W$.}{SRC/Kalyna/Kalyna.cpp}





\end{document}