On construction of perfect ciphers

Abstract


K. Shannon in the 40s of the 20th century introduced the concept of a perfect cipher, which provides the best protection of plaintexts. Perfect secrecy means that cryptanalyst can obtain no information about the plaintext by observing the ciphertext. In the paper we study the problem of construction of perfect ciphers on a given set of plaintexts $X$, a set of keys $K$ and a probability distribution $P (K)$. We give necessary and sufficient conditions for a perfect ciphers on given $X$, $K$ and $P (K)$. It is shown that this problem is reduced to construction of the set of partitions of the set $K$ with certain conditions. As one of the drawbacks of the probability model of cipher are limitations on the power of sets of plaintexts, keys and ciphertexts we also study the problem of construction of substitution cipher with unbounded key on a given set of ciphervalues, a set of keys and a probability distribution on the set of keys.

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
42, L. Tolstoy st., Ulyanovsk, 432017, Russian Federation
(Cand. Phys. & Math. Sci.), Associate Professor, Dept. of Information Security & Control Theory

References

  1. А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин, Основы криптографии, М.: Гелиос, АРВ, 2005. 480 с.
  2. C. E. Shannon, “Communication Theory of Secrecy Systems” // Bell System Technical Journal, 1949. vol. 28, no. 4. pp. 656-715. doi: 10.1002/j.1538-7305.1949.tb00928.x.
  3. К. Шеннон, “Теория связи в секретных системах” / Работы по теории информации и кибернетике, М.: Иностранная литература, 1963. С. 333-369.
  4. С. М. Рацеев, “О совершенных имитостойких шифрах” // ПДМ, 2012. No 3. С. 41-46.
  5. А. Ю. Зубов, Криптографические методы защиты информации. Совершенные шифры, М.: Гелиос, АРВ, 2005. 192 с.
  6. С. М. Рацеев, “Об оптимальных кодах аутентификации” // Системы и средства информ., 2013. Т. 23, No 1, «Проблемы информационной безопасности и надежности систем информатики». С. 53-57.

Statistics

Views

Abstract - 28

PDF (Russian) - 5

Cited-By


PlumX

Dimensions

Refbacks

  • There are currently no refbacks.

Copyright (c) 2014 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies