13 билет по КМЗИ

13.tex

\documentclass[12pt]{article}
\usepackage[a4paper, total={7in, 10in}]{geometry}
\usepackage{ucs}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{array}
\usepackage{wrapfig}
\usepackage{mathtools}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\usepackage[utf8x]{inputenc}
\usepackage[T2A]{fontenc}


\renewcommand{\baselinestretch}{1.3} 

\title{Криптографические методы защиты информации}
\date{}
\author{}


\begin{document}

\section*{13. Расстояние единственности}


\textit{Пример:} Пусть мы знаем, что слово было зашифровано с помощью шифра Цезаря, в результате чего была получена криптограмма WNAJW. Можно подобрать ключ с помощью перебора. Построим таблицу. Видно, что дешифрование неоднозначно, т.к. мы можем получить слова RIVER и ARENA.

\begin{wraptable}{l}{0.25\linewidth}
\begin{tabular}{lllll}
Q & H & U & D & Q \\
R & I & V & E & R \\
S & J & W & F & S \\
. & . & . & . & . \\
Z & Q & D & M & Z \\
A & R & E & N & A \\
. & . & . & . & .
\end{tabular}
\end{wraptable}

Какова должна быть длина текста, чтобы это произошло? Возьмём криптограмму $c \in C$ и расшифруем её на всех ключах $k \in \mathcal{K}$. Получим $|\mathcal{K}|$ открытых текстов. 

Вероятность открытого текста быть «осмысленным» — ${2^{n H_L}}/{|\Sigma|^n}$, если его длина $n$. То есть, примерно $|\mathcal{K}|\frac{2^{n H_L}}{|\Sigma|^n}$ осмысленных текстов можно получить. 

При каком $n$ такой текст будет один? Решим неравенство
\begin{equation*}
|\mathcal{K}|\frac{2^{n H_L}}{|\Sigma|^n} \leqslant 1; 
\log{|\mathcal{K}|} + n H_L \leqslant n \log{|\Sigma|};
n \geqslant \frac{\log{|\mathcal{K}|}}{\log{|\Sigma|}- H_L}
\end{equation*}\\


\textbf{Расстоянием единственности криптосистемы} называется величина $N_0$ — наименьшая длина текста, при котором он дешифруется в среднем однозначно
\begin{equation*}
N_0 = \min \lbrace n | n \geqslant \frac{\log{|\mathcal{K}|}}{\log{|\Sigma|}- H_L} \rbrace
\end{equation*}\\

\textit{Пример 1:} Рассмотрим шифр простой замены для английского текста. Нам известно, что $R_L = 0,86$, $|\Sigma| = 26$, $|\mathcal{K}| = 26!$. По сути, $N_0 = \ceil*{\frac{\log |\mathcal{K}|}{R_L\cdot\log|\Sigma|}}$. 

Тогда $N_0 = \ceil*{\frac{\log 26!}{0.68\cdot\log26}} = \ceil*{\frac{88}{3,19}} \approx \ceil*{27,59} \approx 28 $. То есть, 28 — это верхняя граница, криптограммы меньшей длины взломать не получится. Для русского языка $N_0 = \ceil*{\frac{117}{0,72\cdot5}} \approx 33 $.\\

\textit{Пример 2:} Шифр Цезаря для английского текста. 
\begin{equation*}
N_0 = \ceil*{\frac{\log 26}{0.68\cdot\log26}} = \ceil*{\frac{1}{0,68}} \approx 2.
\end{equation*}
\end{document}