On construction of perfect ciphers

Full Text

Пусть X, K, Y - конечные множества открытых текстов, ключей и шифрованных текстов соответственно. Обозначим через ΣB = (X, K, Y, E, D, P (X), P (K)) вероятностную модель шифра (см. [1]), где E и D - множества правил зашифрования и расшифрования соответственно. При этом предполагается, что априорные распределения вероятностей P (X) и P (K) на соответствующих множествах X и K независимы и не содержат нулевых вероятностей. Распределения P (X) и P (K) естественным образом индуцируют распределение вероятностей P (Y ) следующим образом: PX (x) · PK (k). PY (y) = (x,k)∈X×K Ek (x)=y Обозначим через K(x, y) множество всех таких ключей k ∈ K, для которых Ek (x) = y. Условная вероятность PY |X (y|x) определяется естественным образом: K(x, y) = ∅, k∈K(x,y) PK (k), PY |X (y|x) = 0, K(x, y) = ∅. ISSN: 2310-7081 (online), 1991-8615 (print); doi: http://dx.doi.org/10.14498/vsgtu1271 © 2014 Самарский государственный технический университет. Образец цитирования: С. М. Р а ц е е в, “О построении совершенных шифров” // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2014. № 1 (34). С. 192-199. 192 О построении совершенных шифров С помощью теоремы умножения вероятностей можно определить и условную вероятность PY |X (y|x): PX|Y (x|y) = PX (x) · PY |X (y|x) . PY (y) Напомним, что шифр ΣB называется совершенным по Шеннону [2], если для любых x ∈ X, y ∈ Y выполнено равенство PX|Y (x|y) = PX (x). Приведем эквивалентные, необходимые и достаточные условия совершенного по Шеннону шифра. Предложение 1. Для произвольного шифра ΣB следующие условия эквивалентны: (i) для любых x ∈ X, y ∈ Y выполнено равенство PX|Y (x|y) = PX (x); (ii) для любых x ∈ X, y ∈ Y выполнено равенство PY |X (y|x) = PY (y); (iii) для любых x1 , x2 ∈ X, y ∈ Y выполнено равенство PY |X (y|x1 ) = = PY |X (y|x2 ). Предложение 2 [1]. Пусть ΣB - совершенный по Шеннону шифр. Тогда для шифра ΣB будут выполнены следующие условия: (i) для любых x ∈ X, y ∈ Y найдётся такой ключ k ∈ K, что Ek (x) = y; (ii) для множеств X, Y и K справедливо двойное неравенство |X| |Y | |K|. Теорема 1 [3] (достаточные условия совершенного по Шеннону шифра). Пусть для шифра ΣB выполнены следующие условия: (i) |K(x, y)| = 1 для любых x ∈ X, y ∈ Y ; (ii) распределение вероятностей P (K) является равномерным. Тогда шифр ΣB является совершенным по Шеннону, причём распределение вероятностей P (Y ) будет являться равномерным и |K| = |Y |. Следствие (теорема К. Шеннона). Пусть ΣB - некоторый шифр, для которого выполнено равенство |X| = |K| = |Y |. Шифр ΣB является совершенным по Шеннону тогда и только тогда, когда выполнены следующие условия: (i) |K(x, y)| = 1 для любых x ∈ X, y ∈ Y ; (ii) распределение вероятностей P (K) является равномерным. Рассмотрим следующую задачу: по заданному множеству открытых текстов X0 и множеству ключей K0 с распределением вероятностей P (K0 ) (независимо от P (X0 )) однозначно определить, существует ли шифр ΣB = (X0 , K0 , Y, E, D, P (X0 ), P (K0 )), являющийся совершенным по Шеннону. Теорема 2. Для заданных X, |X| = n, K, |K| = m, P (K) существует совершенный шифр ΣB = (X, K, Y, E, D, P (X), P (K)) тогда и только тогда, когда выполнены следующие условия: 193 С. М. Р а ц е е в 1) существует n разбиений множества K, которые состоят из одинакового количества непустых частей: K = K11 ∪ K12 ∪ · · · ∪ K1s , K1i ∩ K1j = ∅, 1 i 1) инъективных отображений из U в V . Пронумеруем данные отображения: E1 , E2 , . . . , Er . Данные отображения называются простыми заменами. Обозначим Nr = {1, 2, . . . , r}. Опорным шифром замены назовём совокупность Σ = (U, Nr , V, E, D), для которой выполнены следующие свойства: 1) для любых u ∈ U и j ∈ Nr выполнено равенство Dj (Ej (u)) = u; 2) V = j∈Nr Ej (U ). При этом E = {E1 , . . . , Er }, D = {D1 , . . . , Dr }, Dj : Ej (U ) → U , j ∈ Nr . l-той степенью опорного шифра Σ назовём совокупность Σl = (U l , Nl , V l , E (l) , D(l) ), r 195 С. М. Р а ц е е в где U l , Nl , V l - декартовы степени соответствующих множеств U , Nr , V . Мноr жество E (l) состоит из отображений E : U l → V l ,  ∈ Nl таких, что для r любых u = u1 . . . ul ∈ U l ,  = j1 . . . jl ∈ Nl выполнено равенство r E (u) = Ej1 (u1 ) . . . Ejl (ul ) = v1 . . . vl ∈ V l , а множество D(l) состоит из отображений D : E (U l ) → U l ,  ∈ Nl , таких что r для любых v = v1 . . . vl ∈ V l ,  = j1 . . . jl ∈ Nl выполнено равенство r D (v) = Dj1 (v1 ) . . . Djl (vl ) = u1 . . . ul ∈ U l . Отметим важный момент. В ряде случаев не всякое слово длины l в алфавите U может появиться в открытом тексте. Поэтому обозначим через U (l) подмножество всех таких слов во множестве U l , появление которых в открытом тексте имеет ненулевую вероятность: U (l) = {u ∈ U l | PU l (u) > 0}. Тогда E (U (l) ). V (l) = ∈Nl r Пусть ψc - случайный генератор ключевого потока, который для любого натурального числа l вырабатывает случайный ключевой поток j1 . . . jl , где все ji ∈ Nr . Обозначим через Σl следующую совокупность величин: H Σl = (U (l) , Nl , V (l) , E (l) , D(l) , P (U (l) ), P (Nl )). H r r Шифром замены с неограниченным ключом назовём семейство ΣH = (Σl , l ∈ N; ψc ). H При этом независимые и не содержащие нулевых вероятностей распределения P (U (l) ) и P (Nl ) индуцируют распределения вероятностей на множестве V (l) : r PU (l) (u) · PNl (). r PV (l) (v) = (u,)∈U (l) ×Nl r E (u)=v Также определим условные вероятности PU (l) |V (l) (u|v) и PV (l) |U (l) (v|u): PV (l) |U (l) (v|u) = PNl (), r ∈Nl (u,v) r PU (l) |V (l) (u|v) = PU (l) (u) · PV (l) |U (l) (v|u) PV (l) (v) , где Nl (u, v) = { ∈ Nl | E (u) = v}. r r Говорят, что шифр ΣH является совершенным тогда и только тогда, когда для любого натурального l шифр Σl является совершенным по Шеннону. H Предложение 3. Для шифра ΣH следующие условия эквивалентны: 196 О построении совершенных шифров (i) для любого l ∈ N и любых u ∈ U (l) , v ∈ V (l) выполнено равенство PU (l) |V (l) (u|v) = PU (l) (u); (ii) для любого l ∈ N и любых u ∈ U (l) , v ∈ V (l) выполнено равенство PV (l) |U (l) (v|u) = PV (l) (v); (iii) для любого l ∈ N и любых u1 , u2 ∈ U (l) , v ∈ V (l) выполнено равенство PV (l) |U (l) (v|u1 ) = PV (l) |U (l) (v|u2 ). Теорема 3 [3] (достаточные условия совершенности шифра ΣH ). Пусть шифр замены ΣH обладает следующими условиями: (i) правила зашифрования E1 , E2 , . . . , Er шифра ΣH обладают тем свойством, что для любых u ∈ U, v ∈ V найдётся, и притом единственный, элемент j = j(u, v) ∈ Nr такой, что Ej (u) = v; (ii) распределение вероятностей P (Nr ) является равномерным. Тогда шифр ΣH является совершенным, причём для любого l ∈ N выполнено равенство |V (l) | = rl и распределение вероятностей P (V (l) ) будет являться равномерным. Теорема 4 Пусть для шифра ΣH выполнено равенство |U | = |Nr | = |V |. Шифр ΣH является совершенным тогда и только тогда, когда выполнены следующие условия: (i) правила зашифрования E1 , E2 , . . . , Er шифра ΣH обладают тем свойством, что для любых u ∈ U, v ∈ V найдётся, и притом единственный, элемент j = j(u, v) ∈ Nr такой, что Ej (u) = v; (ii) распределение вероятностей P (Nr ) является равномерным. Д о к а з а т е л ь с т в о следует из теоремы Шеннона и теоремы 3. Рассмотрим задачу построения совершенного шифра ΣH по заданному множеству «шифрвеличин» U и множеству Nr с распределением вероятностей P (Nr ). Теорема 5. Для заданных U, |U | = n, Nr , P (Nr ) существует совершенный шифр ΣH тогда и только тогда, когда выполнены следующие условия: 1) существует n разбиений множества Nr , которые состоят из одинакового количества непустых частей: Nr = K11 ∪ K12 ∪ · · · ∪ K1s , K1i ∩ K1j = ∅, 1 Д о к а з а т е л ь с т в о. Необходимое условие следует из теоремы 2. Достаточность. Пусть выполнены условия 1)-3) и пусть V - некоторое множество «шифробозначений», |V | = s. Составим матрицу зашифрования 197 С. М. Р а ц е е в над элементами множества V для опорного шифра Σ так же, как и в теореме 2. Зафиксируем некоторое натуральное l. Пусть a = a1 . . . al ∈ U (l) , b = b1 . . . bl ∈ U (l) , v = v1 . . . vl ∈ V (l) . Тогда l l PV |U (vi |ai ) = PV (l) |U (l) (v|a) = i=1 PV |U (vi |bi ) = PV (l) |U (l) (v|b), i=1 где второе равенство следует из теоремы 2. Поэтому из предложения 3 следует, что шифр Σl является совершенным по Шеннону. H

About the authors

Sergey M Ratseev

Ulyanovsk State University

Email: RatseevSM@mail.ru
(Cand. Phys. & Math. Sci.), Associate Professor, Dept. of Information Security & Control Theory 42, L. Tolstoy st., Ulyanovsk, 432017, Russian Federation

References

Supplementary files