close

Вход

Забыли?

вход по аккаунту

?

О построении совершенных шифров замены с неограниченным ключом.

код для вставкиСкачать
84 НАУЧНЫЕ ВЕДОМОСТИ
Серия: Математика. Физика. 2014. №12(183). Вып. 35
MSC 94A60
О ПОСТРОЕНИИ СОВЕРШЕННЫХ ШИФРОВ ЗАМЕНЫ
С НЕОГРАНИЧЕННЫМ КЛЮЧОМ
С.М. Рацеев, Н.П. Панов
Ульяновский государственный университет,
ул. Льва Толстого, 42, Ульяновск, 432017, Россия, e-mail: RatseevSM@mail.ru
Аннотация. Исследуется задача построения совершенных шифров по фиксированному
набору параметров.
Ключевые слова: криптография, информация, шифр, совершенный шифр.
К. Шеннон в 40-х годах 20-го века ввел понятие совершенного шифра, обеспечивающего наилучшую защиту открытых текстов. Такой шифр не дает криптоаналитику никакой дополнительной информации об открытом тексте на основе перехваченной
криптограммы. Данные шифры используются в тех случаях, когда наиболее важна
секретность передаваемой информации. В настоящей работе исследуется задача построения совершенных шифров замены с неограниченным ключом по фиксированному
набору параметров.
Все необходимые определения можно найти в работах [1, 2]. Пусть U — конечное
множество возможных «шифрвеличин», V — конечное множество возможных «шифробозначений». Пусть также имеются r (r > 1) инъективных отображений из U в V .
Пронумеруем данные отображения: E1 , E2 ,..., Er . Данные отображения называются
простыми заменами. Обозначим Nr = {1, 2, ..., r}. Опорным шифром замены назовем
совокупность Σ = (U, Nr , V, E, D), для которой выполнены следующие свойства:
1) для любых
u ∈ U и j ∈ Nr выполнено равенство Dj (Ej (u)) = u;
S
2) V = j∈Nr Ej (U).
При этом E = {E1 , ..., Er }, D = {D1 , ..., Dr }, Dj : Ej (U) → U, j ∈ Nr .
l-ой степенью опорного шифра Σ назовем совокупность
Σl = (U l , Nlr , V l , E (l) , D (l) ) ,
где U l , Nlr , V l — декартовы степени соответствующих множеств U, Nr , V . Множество
E (l) состоит из отображений E : U l → V l ,  ∈ Nlr , таких что для любых u = u1 ...ul ∈ U l ,
 = j1 ...jl ∈ Nlr выполнено равенство
E (u) = Ej1 (u1 )...Ejl (ul ) = v1 ...vl ∈ V l ,
Серия: Математика. Физика. 2014. №12(183). Вып. 35 85
НАУЧНЫЕ ВЕДОМОСТИ
а множество D (l) состоит из отображений D : E (U l ) → U l ,  ∈ Nlr , таких что для
любых v = v1 ...vl ∈ V l ,  = j1 ...jl ∈ Nlr выполнено равенство
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} .
Тогда
V (l) =
[
E (U (l) ) .
∈Nlr
Пусть ψc — случайный генератор ключевого потока, который для любого натурального числа l вырабатывает случайный ключевой поток j1 ...jl , где все ji ∈ Nr . Обозначим
через ΣlH следующую совокупность величин:
ΣlH = (U (l) , Nlr , V (l) , E (l) , D (l) , P (U (l) ), P (Nlr )) .
Шифром замены с неограниченным ключом назовем семейство
ΣH = (ΣlH , l ∈ N; ψc ) .
При этом независимые и не содержащие нулевых вероятностей распределения P (U (l) )
и P (Nlr ) индуцируют распределения вероятностей на множестве V (l) :
X
PV (l) (v) =
PU (l) (u) · PNlr ().
(u,)∈U (l) ×Nlr
E (u)=v
Также определим условные вероятности PU (l) |V (l) (u|v) и PV (l) |U (l) (v|u):
PV (l) |U (l) (v|u) =
X
∈Nlr (u,v)
PNlr (),
PU (l) |V (l) (u|v) =
PU (l) (u) · PV (l) |U (l) (v|u)
,
PV (l) (v)
где Nlr (u, v) = { ∈ Nlr | E (u) = v}.
Говорят, что шифр ΣH является совершенным, если для любого натурального l и
для любых u ∈ U (l) , v ∈ V (l) выполнено равенство PU (l) |V (l) (u|v) = PU (l) (u).
Предложение 1 [2]. Для шифра ΣH следующие условия эквивалентны:
(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);
86 НАУЧНЫЕ ВЕДОМОСТИ
Серия: Математика. Физика. 2014. №12(183). Вып. 35
(iii) для любого l ∈ N и любых u1 , u2 ∈ U (l) , v ∈ V (l) выполнено равенство
PV (l) |U (l) (v|u1 ) = PV (l) |U (l) (v|u2 ).
Предложение 2 [2]. Пусть шифр замены с неограниченным ключом ΣH является
совершенным. Тогда для данного шифра будут выполнены следующие свойства:
(i) для любого натурального числа l и любых u ∈ U (l) , v ∈ V (l) найдется такой
ключевой поток  ∈ Nlr , что E (u) = v;
(ii) для любого натурального числа l справедливо двойное неравенство
|U (l) | ≤ |V (l) | ≤ |Nlr | = r l .
Теорема 1 (достаточные условия совершенности шифра ΣH [3]). Пусть шифр замены Σ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) | = r l и распределение вероятностей P (V (l) ) будет являться равномерным.
Теорема 2 [2]. Пусть для шифра Σ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 ) является равномерным.
Приведем также критерий совершенных шифров замены с неограниченным ключом
в классе шифров с равномерным распределением вероятностей на множестве Nr .
Теорема 3 [4]. Пусть для шифра ΣH выполнены неравенства |U| ≤ |V | ≤ |Nr | и
распределение вероятностей P (Nr ) является равномерным. Шифр ΣH является совершенным тогда и только тогда, когда выполнены следующие условия:
(i) для любых u ∈ U и v ∈ V найдется такое j ∈ Nr , что Ej (u) = v;
(ii) для любых u1 , u2 ∈ U, v ∈ V выполнено равенство |Nr (u1 , v)| = |Nr (u2 , v)|.
Рассмотрим задачу построения совершенного шифра ΣH по заданному множеству
«шифрвеличин» U и множеству Nr с распределением вероятностей P (Nr ): по заданным
U, Nr , P (Nr ) требуется определить, найдутся ли такие V , E, D, для которых шифр ΣH
являлся бы совершенным.
Теорема 4. Для заданных U, |U| = n, Nr , P (Nr ) существует совершенный шифр
ΣH тогда и только тогда, когда найдется такое натуральное число s и n разбиений
множества Nr
Nr = K11 ∪ K12 ∪ ... ∪ K1s ,
K1i ∩ K1j = ∅,
1 ≤ i < j ≤ s,
Серия: Математика. Физика. 2014. №12(183). Вып. 35 87
НАУЧНЫЕ ВЕДОМОСТИ
Nr = K21 ∪ K22 ∪ ... ∪ K2s ,
K2i ∩ K2j = ∅,
1 ≤ i < j ≤ s,
(1)
...
Nr = Kn1 ∪ Kn2 ∪ ... ∪ Kns ,
Kni ∩ Knj = ∅,
1 ≤ i < j ≤ s,
для которых выполнены следующие условия:
1) Kit ∩ Kjt = ø, 1 ≤ i < j ≤ n, t = 1, ..., s;
2) для любых 1 ≤ i < j ≤ n, t = 1, ..., s выполнено равенство
X
X
PNr (k) =
PNr (k).
k∈Kit
k∈Kjt
Достаточность. Пусть для U, Nr , P (Nr ), найдется такое s и n таких разбиений
(1), для которых выполнены условия 1), 2). Пусть V = {v1 , ..., vs } — некоторое множество «шифробозначений», где s — число непустых частей из (1). Составим матрицу
зашифрования размера r × n для опорного шифра, где строки пронумерованы элементами множества Nr , а столбцы — элементами множества U, следующим образом. В i-м
столбце (i = 1, ..., n) данной матрицы в строках, пронумерованных элементами множества Kij , поставим элемент vj , j = 1, ..., s. Условие 1) в этом случае гарантирует, что
все простые замены Ej , j ∈ Nr , полученного шифра являются инъективными отображениями. А из условия 2) следует, что для любого t = 1, ..., s и любых 1 ≤ i < j ≤ n
будут выполнены равенства
X
X
PV |U (vt |ui ) =
PNr (k) =
PNr (k) = PV |U (vt |uj ) .
k∈Kit
k∈Kjt
Поэтому, учитывая предложение 1, полученный опорный шифр Σ будет являться совершенным по Шеннону.
Покажем, что для любого l ∈ N шифр ΣlH является совершенным по Шеннону.
Зафиксируем некоторое натуральное l. Пусть a = a1 ...al ∈ U (l) , b = b1 ...bl ∈ U (l) , v =
v1 ...vl ∈ V (l) . Тогда
PV (l) |U (l) (v|a) =
l
Y
l
Y
PV |U (vi |ai ) =
i=1
PV |U (vi |bi ) = PV (l) |U (l) (v|b) .
i=1
Поэтому из предложения 1 следует, что шифр ΣlH является совершенным по Шеннону.
Необходимость. Пусть для заданных U, Nr , P (Nr ) существует совершенный шифр ΣH
со множеством «шифробозначений» V = {v1 , ..., vs }. Обозначим для данного шифра
Kit = {j ∈ Nr | Ej (ui ) = vt } ,
Понятно, что
PV |U (vt |ui ) =
i = 1, ..., n,
X
j∈Kit
PNr (j) .
t = 1, ..., s .
88 НАУЧНЫЕ ВЕДОМОСТИ
Серия: Математика. Физика. 2014. №12(183). Вып. 35
Из предложений 1 и 2 следует, что для множеств Kit будут выполнены равенства (1) и
условия 1), 2). Следствие 1. Пусть для заданных U, Nr , P (Nr ) существует совершенный шифр.
e |U|
e ≤ |U|, и для заданных Nr , P (Nr )
Тогда для любого множества «шифрвеличин» U,
существует совершенный шифр ΣH .
Следствие 2. Для заданных U, |U| = n, Nr , P (Nr ), V , |V | = s, существует совершенный шифр ΣH тогда и только тогда, когда найдется n таких разбиений (1), для
которых выполнены условия 1 и 2 предыдущей теоремы.
Следствие 3. Для заданных V , |V | = s, Nr , P (Nr ) существует совершенный шифр
ΣH тогда и только тогда, когда найдется такое n и такие разбиения (1), для которых
выполнены условия 1 и 2 предыдущей теоремы.
Следствие 4. Для заданных Nr , P (Nr ) существует совершенный шифр ΣH тогда и
только тогда, когда найдутся такие n и s, n ≤ s, и такие разбиения (1), для которых
выполнены условия 1 и 2 предыдущей теоремы.
Пример. Пусть U = {u1, u2 }, N4 = {1, 2, 3, 4} и распределение вероятностей на
множестве N4 имеет вид
N4
1
2
3
4
P (N4 ) 2/7 1/7 3/7 1/7
В этом случае можно построить два разбиения множества N4 вида
N4 = {1, 2} ∪ {3} ∪ {4},
N4 = {3} ∪ {1, 4} ∪ {2}
с условиями
PN4 (1) + PN4 (2) = PN4 (3),
PN4 (3) = PN4 (1) + PN4 (4),
PN4 (4) = PN4 (2).
По теореме 4 для данных U, N4 , P (N4) можно построить совершенный шифр ΣH . Пусть
V = {v1 , v2 , v3 }. Составим матрицу зашифрования следующим образом:
N4 U u1
1
v1
2
v1
3
v2
4
v3
u2
v2
v3
v1
v2
Тогда полученный шифр ΣH будет являться совершенным.
Рассмотрим теперь такой несложный критерий.
НАУЧНЫЕ ВЕДОМОСТИ
Серия: Математика. Физика. 2014. №12(183). Вып. 35 89
Предложение 3. Для заданных U и V можно построить совершенный шифр ΣH
тогда и только тогда, когда |U| ≤ |V |.
Если шифр ΣH является совершенным, то неравенство |U| ≤ |V | следует из предложения 2.
Обратно, пусть для U и V выполнено неравенство |U| ≤ |V |. Обозначим r = |V |,
n = |U|. Составим матрицу A порядка r × n над множеством V следующим образом:
в каждом столбце матрицы A каждый элемент множества V встречается ровно один
раз, а в каждой строке нет повторяющихся элементов (напомним, что такая матрица
называется латинским прямоугольником и построить его можно, например, так: каждый следующий столбец является циклическим сдвигом на одну позицию предыдущего
столбца). Пусть матрица A будет матрицей зашифрования опорного шифра для шифра
ΣH , а распределение вероятностей на множестве Nr равномерно. Тогда из теоремы 1
следует, что шифр ΣH является совершенным. Пусть (Ω = Nr , FNr , PNr ) — вероятностное пространство. Зафиксируем v ∈ V . Обозначим через Nr (v) следующее множество:
Nr (v) = {j ∈ Nr | v ∈ Ej (U)} .
Под обозначением Nr (v) будем также понимать событие (Nr (v) ∈ FNr ), заключающееся в том, что при случайном выборе элемента j ∈ Nr «шифробозначение» v можно
расшифровать правилом расшифрования Dj : v ∈ Ej (U). Тогда событию Nr (v) будут
благоприятствовать все элементы из множества Nr (v), и только они. Поэтому
P (Nr (v)) =
X
PNr (j) .
j∈Nr (v)
Если канал связи готов к работе и на приеме установлены действующие ключи, но
в данный момент времени никакого сообщения не передается, то в этом случае противником может быть предпринята попытка имитации сообщения. Тогда вероятность
успеха имитации каждого символа передаваемого сообщения определяется следующим
образом:
Pim = max P (Nr (v)) .
v∈V
Если же в данный момент передается некоторое сообщение, то противник может заменить некоторые символы этого сообщения, например некоторый символ v ∈ V на
v ∈ V , отличный от v. При этом он будет рассчитывать на то, что на действующем
e
ключе «шифробозначение» ve будет успешно расшифровано. Пусть «Nr (e
v) | Nr (v)» —
событие, заключающееся в попытке подмены «шифробозначения» v «шифробозначением» ve. Применяя теорему о произведении вероятностей, получаем, что
P
P (Nr (v) ∩ Nr (e
v ))
j∈N (v,e
v ) PNr (j)
P (Nr (e
v) | Nr (v)) =
= P r
,
P (Nr (v))
j∈Nr (v) PNr (j)
90 НАУЧНЫЕ ВЕДОМОСТИ
Серия: Математика. Физика. 2014. №12(183). Вып. 35
где Nr (v, e
v) = Nr (v) ∩ Nr (e
v). Тогда вероятность успеха подмены «шифробозначения»
будет вычисляться по следующей формуле:
Ppodm = max P (Nr (e
v) | Nr (v)) .
v,e
v ∈V ,
v6=v
e
Теорема 5 [2]. Для шифра ΣH справедливы неравенства
Pim ≥
|U|
,
|V |
Ppodm ≥
|U| − 1
.
|V | − 1
При этом Pim = |U|/|V | тогда и только тогда, когда для любого v ∈ V выполнено
равенство P (K(v)) = |U|/|V |. Также Ppodm = (|U| − 1)/(|V | − 1) тогда и только тогда,
когда для любых v, ve ∈ V , v 6= e
v , выполнено равенство
P (K(e
v) | K(v)) = (|U| − 1)/(|V | − 1) .
Далее везде предполагается, что для любого натурального l выполнены равенства
l
U (l) = U l , V (l) = V l . Обозначим через Pim
вероятность успеха имитации сообщения для
l
l
шифра ΣH , а через Ppodm (s) — вероятность успеха подмены в сообщении длины l ровно
s символов для шифра ΣlH , где s ≤ l. Из определения вероятностей Pim и Ppodm следуют
такие равенства:
l
l
Pim
= (Pim )l , Ppodm
(s) = (Ppodm )s .
Предложение 4. Пусть для шифра ΣH (с матрицей зашифрования опорного шифра из теоремы 4) выполнены равенства (1) и условия 1 и 2 теоремы 4. Тогда
l
Pim
=
l
Ppodm
(t) =
где
n · max
1≤i≤s
X
k∈K1i
PNr (k)
!l
,
!t
P
P
(k)
N
1
r
k∈K ∩K
· max P i j
,
n 1≤i,j≤s
P
(k)
N
r
k∈K
i6=j
1i
Ki =
n
[
Kji ,
i = 1, ..., s .
j=1
Пусть V = {v1 , ..., vs }, 1 ≤ i ≤ s. Тогда из условий 1 и 2 теоремы 4 следуют такие
равенства:
!
X
X
P (Nr (vi )) =
PNr (k) = n ·
PNr (k) ,
k∈K1i ∪...∪Kni
k∈K1i
Серия: Математика. Физика. 2014. №12(183). Вып. 35 91
НАУЧНЫЕ ВЕДОМОСТИ
поэтому
Pim = n · max
1≤i≤s
Далее, пусть 1 ≤ i, j ≤ s, i 6= j. Тогда
P
P (Nr (vj ) | Nr (vi )) =
поэтому
Ppodm
k∈Ki ∩Kj
P
k∈Ki
X
PNr (k) .
k∈K1i
PNr (k)
PNr (k)
=
P
n·
k∈Ki ∩Kj
PNr (k)
k∈K1i
PNr (k)
P
P
1
k∈K ∩K PNr (k)
= · max P i j
. n 1≤i,j≤s ,
k∈K1i PNr (k)
,
i6=j
Предложение 5. Пусть для шифра ΣH выполнены равенства (1) и условия 1 и 2
теоремы 4. Для шифра ΣH достигаются нижние границы для вероятностей имитации
и подмены
t
n l
n−1
l
l
, Ppodm (t) =
,
Pim =
s
s−1
где n = |U|, s = |V |, тогда и только тогда, когда для любых 1 ≤ i < j ≤ s выполнены
следующие равенства:
X
k∈K1i
1
PNr (k) = ,
s
X
PNr (k) =
k∈Ki ∩Kj
n(n − 1)
.
s(s − 1)
Доказательство следует из теоремы 5 и предложения 4. Литература
1. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии /
М.: Гелиос АРВ, 2005. – 480 с.
2. Зубов А.Ю. Криптографические методы защиты информации. Совершенные шифры /
М.: Гелиос АРВ, 2005. – 192 с.
3. Рацеев С.М. О совершенных имитостойких шифрах // Прикладная дискретная математика. – 2012. – 17; №3. – C.41-47.
4. Рацеев С.М. О совершенных имитостойких шифрах замены с неограниченным ключом // Вестник Самарского государственного университета. Естественнонаучная серия. –
2013. – 110;№9/1. – C.42-48.
ON CONSTRUCTIONS OF PERFECT CODES OF SUBSTITUTION
WITH UNBOUNDED KEY
S.M. Ratseev, N.P. Panov
Ulyanovsk State University,
Lev Tolstoy St., 42, Ulyanovsk, 432017, Russia, e-mail: RatseevSM@mail.ru
Abstract. The problem of constructing perfect codes on a fixed set of parameters is studied.
Key words: cryptography, information, code, perfect code.
Документ
Категория
Без категории
Просмотров
4
Размер файла
131 Кб
Теги
построение, замена, неограниченных, совершенный, ключом, шифров
1/--страниц
Пожаловаться на содержимое документа