Русская Википедия:Абсолютно стойкий шифр

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

Математически понятие абсолютно стойкого шифра было введено Клодом Шенноном в 1945 году в работе «Математическая теория криптографии».

Вспомогательные понятия

Пусть <math>X</math> и <math>Y</math> — алфавиты открытого и шифрованного текста такие, что <math>|X| > 1,</math> <math>|Y| > 1,</math> <math>|Y| \geq |X| </math>.

Шифрование задаётся инъективным отображением <math>e_k:X\rightarrow Y</math>, дешифрование — отображением <math>d_k:e_k(X)\rightarrow X,</math> <math>k \in K = \{1, 2, ...,n\}</math>.

<math>E=\{e_k, k\in K\}, D =\{d_k, k\in K\}</math> — наборы правил шифрования и дешифрования.

Максимальное число <math>|E|=n</math> возможных отображений равно количеству размещений из <math>|Y|</math> по <math>|X|</math> (числу способов выбрать подмножества размером <math>|X|</math> в множестве <math>Y</math>, учитывая порядок элементов).

Возникновение очередного символа <math>x \in X</math>, выбор ключа <math>k \in K</math> (то есть выбор отображения <math>e_k</math>), получение шифротекста <math>y \in Y</math> реализуются с некоторыми вероятностями:

<math>P(X^l)=\{p_{X^l}(\vec{x}),

  \vec{x}\in X^l\}</math> — распределение вероятностей для открытого текста,

<math>P(K^l)=\{p_{K^l}(\vec{k}), \vec{k}\in K^l\}</math> — распределение вероятностей для комбинации номеров отображений,

<math>P(Y^l)=\{p_{Y^l}(\vec{y}), \vec{y}\in Y^l\}</math> — распределение вероятностей для шифротекста, где

<math>X^l, K^l, Y^l</math> — декартовы степени множеств <math>X, K, Y</math>, <math>l</math> — количество символов в открытом тексте.

Будем считать, что случайные величины, соответствующие появлению открытого текста <math>\vec{x}</math> и ключа <math>\vec{k}</math>, независимыми. Тогда:

<math>p_{Y^l}(\vec{y})=\sum_{}p_{X^l}(\vec{x}) p_{K^l}(\vec{k})</math>, где сумма ведётся по всем <math>\vec{x}</math> и <math>\vec{k}</math> таким, что <math>e_{\vec{k}}(\vec{x})=\bigl(e_{k_1}(x_1), ..., e_{k_l}(x_l)\bigr)^T=\vec{y}</math>.

<math>E^l, D^l</math> — множества правил шифрования и дешифрования (декартовы степени множеств <math>E,D</math>).

Учитывая, что не каждая комбинация символов длины <math>l</math> из алфавита <math>X</math> может появиться в открытом тексте, введём: <math>X^{(l)} = \{\vec{x}:p_{X^l}(\vec{x})>0\}, Y^{(l)} = \{\vec{y}:p_{Y^l}(\vec{y})>0\}</math>.

Шифр замены с неограниченным ключом — семейство шифров <math>S_H = \{S_{H}^{(l)}, l\in \mathbb N\}</math>, где <math>S_{H}^{(l)}</math> — представляет собой совокупность <math>X^{(l)}, K^l, Y^{(l)}, E^{l}, D^{l}, P(X^{(l)}), P(K^l), P(Y^{(l)})</math>, при этом <math>p_{K^l}(\vec{k})>0, \forall\vec{k}\in K^l</math>.

Длина ключа шифра замены с неограниченным ключом совпадает с размером открытого текста <math>l</math>.

Пусть <math>\tilde{K}</math> — конечное множество некоторых ключей (некоторых наборов натуральных чисел). Длина ключа из <math>\tilde{K}</math> может быть меньше <math>l</math>. Для каждого ключа из <math>\tilde{K}</math> можно задать правило детерминированного построения ключевого потока <math>\vec{k}=(k_1, ..., k_l)^T\in K^l</math>. Полученный таким образом набор ключевых потоков для всех ключей из <math>\tilde{K}</math> обозначим <math>K^{(l)}</math>. Например, для ключа <math>(k_1, ..., k_p)^T \in \tilde{K}, 1<p<l</math> в качестве ключевого потока можно взять периодическое повторение этого ключа <math>(k_1, ..., k_p, k_1, ..., k_p, ...)^T \in K^l</math>. Заметим, что <math>K^{(l)} \subseteq K^{l}</math>.

Шифр замены с ограниченным ключом — семейство шифров <math>S_O = \{S_{O}^{(l)}, l\in \mathbb N\}</math>, где <math>S_{O}^{(l)}</math> есть та же совокупность, что и для определённого выше шифра с неограниченным ключом, в которой вместо <math>K^l</math> и <math>P(K^l)</math> используется множество <math>K^{(l)}</math> и распределение <math>P(K^{(l)})</math>.

Формальное определение

Пусть <math>p_{X^{(l)}|Y^{(l)}}(\vec{x}|\vec{y})</math> — вероятность, что было зашифровано сообщение <math>\vec{x}\in X^{(l)}</math> при регистрации шифротекста <math>\vec{y}\in Y^{(l)}</math>. Шифр называется абсолютно стойким, если выполнено:

<math>p_{X^{(l)}|Y^{(l)}}(\vec{x}|\vec{y})=p_{X^{(l)}}(\vec{x}) </math> <math>\forall \vec{x}\in X^{(l)}, \forall \vec{y}\in Y^{(l)}, \forall l\in\mathbb N </math>.

Другими словами, апостериорное распределение вероятностей <math>P_{X^{(l)}|Y^{(l)}}=\{p_{X^{(l)}|Y^{(l)}}(\vec{x}|\vec{y}), x\in X^{(l)}, y\in Y^{(l)}\} </math> совпадает с априорным распределением <math>P(X^{(l)})</math>. В терминах теории информации это означает, что условная энтропия сообщения при известном шифрованном тексте равна безусловной. Знание шифротекста <math>\vec{y}</math> не даёт криптоаналитику никакого полезного знания для получения <math>\vec{x}</math> (расшифровка возможна только полным перебором).

Основные свойства

Никакой шифр с ограниченным ключом <math>S_O</math> не является совершенным.

Шаблон:Hider(\vec{y}|\vec{x})=\sum_{\vec{k}\in K^{(l)}(\vec{x},\vec{y})}p_{K^{(l)}}(\vec{k})</math>, где <math>K^{(l)}(\vec{x},\vec{y})=\{\vec{k}\in K^{(l)}: e_{k_i}(x_i)=y_i, i=\overline{1,l}\}</math>.

Покажем, что для совершенного шифра верно: <math>|K^{(l)}(\vec{x},\vec{y})|\geq 1</math> <math>\forall \vec{x}\in X^{(l)}, \forall \vec{y}\in Y^{(l)}, \forall l\in\mathbb N</math>. Действительно, если бы <math>|K^{(l)}(\vec{x},\vec{y})|= 0</math> при некоторых <math>\vec{x}</math> и <math>\vec{y}</math>, то <math>p_{Y^{(l)}|X^{(l)}}(\vec{y}|\vec{x})=0</math>. Так как <math>p_{X^{(l)}|Y^{(l)}}(\vec{x}|\vec{y})=\frac{p_{X^{(l)}}(\vec{x})\cdot p_{Y^{(l)}|X^{(l)}}(\vec{y}|\vec{x})}{p_{Y^{(l)}}(\vec{y})}</math>, то <math>p_{X^{(l)}}(\vec{x})=0</math> ( <math>p_{X^{(l)}|Y^{(l)}}(\vec{x}|\vec{y})=p_{X^{(l)}}(\vec{x})</math> по определению абсолютной стойкости), что противоречит определению шифра с ограниченным ключом.

Теперь можно утверждать, что для совершенного шифра <math>|K^{(l)}|\geqslant |Y^{(l)}|</math>, так как для любого фиксированного <math>\vec{x}</math> существует ключ <math>\vec{k}</math> такой, что <math>e_\vec{k}(\vec{x})=\vec{y}</math>. Но это неравенство невозможно <math>\forall l\in \mathbb N</math>, так как множество <math>\tilde{K}</math> конечно, а <math>|Y^{(l)}|</math> неограниченно возрастает при росте <math>l</math> , ведь <math>|Y^{(l)}|\geqslant |X^{(l)}|, </math> <math>|X^{(l+1)}| > |X^{(l)}|</math>.

 |frame-style = border: 2px solid lightgray;
 |title-style = color: black; background-color: #eeeeee; font-weight: normal; text-align: left; 
 |content-style = color: black; background-color: white; text-align: left;

}} Если шифр совершенный, то <math>|X|\leq|Y|\leq|K|</math>.

Шаблон:Hider

Теорема Шеннона

Формулировка

Шифр с неограниченным ключом <math>S_H</math>, у которого <math>|X|=|Y|=|K|</math> является совершенным тогда и только тогда, когда:

<math>1.</math> <math>|K(x,y)|=1</math> <math>\forall x\in X, \forall y\in Y</math>, где <math>K(x,y)=\{k \in K: e_k(x)=y\}</math>, то есть для любого <math>x</math> и любого <math>y</math> существует только один ключ <math>k</math> такой, что <math>e_k(x)=y</math>;

<math>2.</math> <math>p_K(k)\equiv p(k)=\frac{1}{|K|}</math> <math>\forall k\in K</math>, то есть ключи должны быть равновероятны.

Доказательство

<math>(\Rightarrow 1)</math>

Так как <math>|Y|=|K|</math>, то из <math>|K(x,y)|\geq 1</math> следует, что при <math>k_1\neq k_2</math>следует <math>e_{k_1}(x)\neq e_{k_2}(x)</math> <math>\forall x\in X</math>.

<math>(\Rightarrow 2)</math>

Занумеруем ключи следующим образом при фиксированном <math>y</math>: <math>e_{k_j}(x_j)=y, j=\overline{1,|X|}</math>. Получим:

<math>p(x_j)=p(x_j|y)=\frac{p(y|x_j)\cdot p(x_j)}{p(y)}=\frac{p(k_j)\cdot p(x_j)}{p(y)}\Rightarrow p(k_j)=p(y)</math> <math>\forall j=\overline{1,|X|}</math>.

<math>(\Leftarrow 1, 2)</math>

Используем ту же нумерацию, что и в предыдущем пункте, считая <math>y</math> фиксированным. Применяя <math>1</math>:

<math>p(y)=\sum_{(x_j,k_j):e_{k_j}(x_j)=y}p(x_j)\cdot p(k_j)=\frac{1}{N}\cdot \sum_{j=1}^Np(x_j)=\frac{1}{N}</math>. Применяя <math>1</math> и <math>2</math>:

<math>p(x_j|y)=\frac{p(x_j)\cdot p(y|x_j)}{p(y)}=p(x_j)</math>. Получили определение абсолютной стойкости.

Общий вид

Исходя из теоремы Шеннона, правило шифрования шифра замены <math>S_H^{(l)}</math> при <math>l=1</math>, у которого <math>|X|=|Y|=|K|</math>, можно представить в виде латинского квадрата:

<math>K/X</math>	<math>x_1</math>	<math>...</math>	X\|}</math>
<math>k_1</math>	<math>e_{k_1}(x_1)</math>	<math>...</math>	X\|})</math>
<math>...</math>	<math>...</math>	<math>...</math>	<math>...</math>
X\|}</math>	X\|}}(x_{1})</math>	<math>...</math>	X\|}}(x_{\|X\|})</math>

При равновероятном использовании <math>k_1,...,k_{|X|}</math> система будет обладать абсолютной стойкостью. Практической реализацией такой системы, например, является шифр Вернама.

Замечание

Существуют абсолютно стойкие шифры, для которых количество символов в алфавите <math>|X|</math> открытого текста меньше <math>|Y|</math>. Например:

<math>K/X</math>	<math>x_1</math>	<math>x_2</math>
<math>k_1, p(k_1)=\frac{19}{80}</math>	<math>1</math>	<math>2</math>
<math>k_2, p(k_2)=\frac{3}{20}</math>	<math>1</math>	<math>3</math>
<math>k_3, p(k_3)=\frac{21}{80}</math>	<math>2</math>	<math>1</math>
<math>k_4, p(k_4)=\frac{1}{10}</math>	<math>2</math>	<math>3</math>
<math>k_5, p(k_5)=\frac{1}{8}</math>	<math>3</math>	<math>1</math>
<math>k_6, p(k_6)=\frac{1}{8}</math>	<math>3</math>	<math>2</math>

Абсолютная стойкость данного шифра легко проверяется по определению по формуле: <math>p(x|y)= \frac{p(y|x)p(x)}{\sum_{x'} p(x')p(y|x')}=\frac{p(x) \sum_{k} p(k)}{\sum_{x', k \in K(x',y)}p(x')p(k)}</math> .

Этот шифр остаётся абсолютно стойким для любого распределения <math>P(X)</math>.

См. также

Литература

Шаблон:Source
Шаблон:Книга
Зубов А.Ю. Криптографические методы защиты информации. Совершенные шифры. Шаблон:М.: Гелиос АРВ, 2005. — 160 с.

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Русская Википедия:Абсолютно стойкий шифр

Содержание