close

Вход

Забыли?

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

?

О построении совершенных шифров.

код для вставкиСкачать
?????. ???. ???. ????. ??-??. ???. ???.-???. ?????. 2014. ? 1 (34). ?. 192?199
??? 519.72
? ?????????? ??????????? ??????
?. ?. ??????
??????????? ??????????????? ???????????,
??????, 432017, ?????????, ??. ?. ????????, 42.
?. ?????? ? 40-? ????? XX ???? ???? ??????? ???????????? ?????, ??????????????? ????????? ?????? ???????? ???????. ????? ???? ?? ???? ??????????????? ??????? ?????????????? ?????????? ?? ???????? ?????? ?? ??????
????????????? ????????????. ? ?????? ??????????? ?????? ?????????? ??????????? ?????? ?? ????????? ????????? ???????? ??????? X, ?????? K
? ????????????? ???????????? P (K) ?? ????????? ??????. ?????????? ????????, ??????????? ?????????? ??????????, ?????????? ?? ??? ???????? X,
K, P (K) ??????????? ????. ????????, ??? ?????? ?????? ???????? ? ?????????? ?????? ????????? ????????? K ? ????????????? ?????????. ??? ??? ?????
?? ??????????? ????????????? ?????? ????? ???????? ???????????, ????????????? ?? ???????? ???????? ???????? ???????, ?????? ? ???????????
???????, ? ?????? ????? ??????????????? ?????? ?????????? ????????????
????? ?????? ? ?????????????? ?????? ?? ????????? ????????? ???????????, ?????? ? ????????????? ???????????? ?? ????????? ??????.
???????? ?????: ????, ??????????? ????, ????? ??????, ????????????? ????????????.
????? 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 ) ????????? ???????:
X
PY (y) =
PX (x) и PK (k).
(x,k)?XОK
Ek (x)=y
????????? ????? K(x, y) ????????? ???? ????? ?????? k ? K, ??? ??????? Ek (x) = y. ???????? ??????????? PY |X (y|x) ???????????? ????????????
???????:
P
K(x, y) 6= ?,
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.
doi: 10.14498/vsgtu1271.
???????? ?? ??????: ?????? ?????????? ?????? (?.?.-?.?.), ??????, ???. ??????????????
???????????? ? ?????? ??????????.
E-mail address: RatseevSM@mail.ru
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| 6 |Y | 6
6 |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 6 i < j 6 s,
K = K21 ? K22 ? и и и ? K2s ,
K2i ? K2j = ?,
1 6 i < j 6 s,
...
K = Kn1 ? Kn2 ? и и и ? Kns ,
Kni ? Knj = ?,
1 6 i < j 6 s;
2) Kit ? Kjt = ?, 1 6 i < j 6 n, t = 1, . . . , s;
3) ??? ????? 1 6 i < j 6 n, t = 1, . . . , s ????????? ?????????
X
X
PK (k) =
PK (k).
k?Kit
k?Kjt
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ?????????????. ????? ??? X, K, P (K) ????????? ??????? 1)?3). ????? Y = {y1 , . . . , ys } ? ????????? ????????? ??????????? ???????, ??? s ? ????? ???????? ?????? ?? ??????? 1). ???????? ???????
???????????? ??????? mОn, ??? ?????? ????????????? ?????????? ????????? K, ? ??????? ? ?????????? ????????? X, ????????? ???????. ? i-???
??????? (i = 1, . . . , n) ?????? ??????? ? ???????, ??????????????? ?????????? ????????? Kij , ???????? ??????? yj , j = 1, . . . , s. ??????? 2) ? ???? ??????
???????????, ??? ??? ??????? ???????????? ??????????? ????? ????????
???????????? ?????????????. ? ?? ??????? 3) ???????, ??? ??? ?????? t =
= 1, . . . , s ? ????? 1 6 i < j 6 n ????? ????????? ?????????
X
X
PY |X (yt |xi ) =
PK (k) =
PK (k) = PY |X (yt |xj ).
k?Kit
k?Kjt
???????, ???????? ??????????? 1, ?????????? ???? ????? ???????? ??????????? ?? ???????.
?????????????. ????? ??? ???????? X, K, P (K) ?????????? ??????????? ?? ??????? ???? ?B ?? ?????????? ??????????? Y = {y1 , . . . , ys }.
????????? ??? ??????? ?????
Kit = {k ? K | Ek (xi ) = yt },
i = 1, . . . , n,
t = 1, . . . , s.
???????, ???
PY |X (yt |xi ) =
X
PK (k).
k?Kit
?? ??????????? 1 ? 2 ???????, ??? ??? ???????? Kit ????? ????????? ??????? 1)?3). ??????. ????? X = {x1 , x2 }, K = {k1 , k2 , k3 , k4 } ? ????????????? ???????????? ?? ????????? K ????? ???
K
k1
k2
k3
k4
P (K) 1/8 1/4 3/8 1/4
194
? ?????????? ??????????? ??????
? ???? ?????? ????? ????????? ??? ????????? ????????? K ????
K = {k1 , k2 } ? {k3 } ? {k4 },
K = {k3 } ? {k1 , k4 } ? {k2 },
???
{k1 , k2 } ? {k3 } = {k3 } ? {k1 , k4 } = {k4 } ? {k2 } = ?.
??? ???? ????? ????????? ?????????
PK (k1 ) + PK (k2 ) = PK (k3 ),
PK (k3 ) = PK (k1 ) + PK (k4 ),
PK (k4 ) = PK (k2 ).
?? ??????? 2 ??? ?????? X, K, P (K) ????? ????????? ??????????? ????.
????? Y = {y1 , y2 , y3 }. ???????? ??????? ???????????? ????????? ???????:
KX x1 x2
k1
y1 y2
k2
y1 y3
k3
y2 y1
k4
y3 y2
????? ?????????? ???? ????? ???????? ??????????? ?? ???????.
???????????? ????????????? ?????? ????? ?B ????????? ?????????????
? ???????? ????????? ???????? ??????? X ???? ?????????????????? ? ????????? ???????? ???????? A, ????? ??????? ?????????? ????????? ???????
???????????? ??????????. ? ?????? [4] ?????????? ?????? ?????? ?????? ?
???????????? ? ?????????????? ??????, ??? ???????, ? ?????????, ?? ????????? X ????? ??????????? ?? ?????????????. ????????? ? ????? ??????
???? ?????? ? ???????????? ?????? ??????????? ?? ???????? (??. [4]),
??? ????? ???????????? ???? ?????? ? ?????????????? ??????. ????? ?????????????? ?????? ????? ??? ???????? ???????, ????????, ??? ?????????
??????? ?????? ??????????? ?????? ? ??????????? ????? ??????????????,
??????? ? ???????? ? ??????? [3, 5].
???????? ?????? ??????? ?????.
????? 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) ),
195
?. ?. ? ? ? ? ? ?
??? 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 ,
? ????????? 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 ???? ?lH ???????? ??????????? ?? ???????.
??????????? 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 6 i < j 6 s,
Nr = K21 ? K22 ? и и и ? K2s ,
K2i ? K2j = ?,
1 6 i < j 6 s,
...
Nr = Kn1 ? Kn2 ? и и и ? Kns ,
Kni ? Knj = ?,
2) KX
6 i < j 6 n, t = 1, . . . , s;
it ? Kjt = ?, 1X
3)
PNr (k) =
PNr (k), 1 6 i < j 6 n,
k?Kit
1 6 i < j 6 s;
t = 1, . . . , s.
k?Kjt
? ? ? ? ? ? ? ? ? ? ? ? ? ?. ??????????? ??????? ??????? ?? ??????? 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) .
?????
PV (l) |U (l) (v|a) =
l
Y
i=1
PV |U (vi |ai ) =
l
Y
PV |U (vi |bi ) = PV (l) |U (l) (v|b),
i=1
??? ?????? ????????? ??????? ?? ??????? 2. ??????? ?? ??????????? 3 ???????, ??? ???? ?lH ???????? ??????????? ?? ???????. ?????? ??????????/ REFERENCES
1. ?. ?. ???????, ?. ?. ?????, ?. ?. ???????, ?. ?. ??????????, ?????? ????????????, ?.: ??????, ???, 2005. 480 ?. [A. P. Alferov, A. Yu. Zubov, A. S. Kuz?min,
A. V. Cheremushkin, Osnovy kriptografii [Foundations of Cryptography], Moscow, Helios,
Association of Russian Universities, 2005, 480 pp. (In Russian)]
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; ?. ??????,
??????? ????? ? ????????? ????????? / ?????? ?? ?????? ?????????? ? ???????????,
?.: ??????????? ??????????, 1963. ?. 333?369.
3. ?. ?. ??????, ?? ??????????? ???????????? ??????? // ???, 2012. ? 3. ?. 41?46.
[S. M. Ratseev, ?About perfect imitation resistant ciphers?, Prikl. Diskr. Mat., 2012, no. 3,
pp. 41?46. (In Russian)].
4. ?. ?. ?????, ????????????????? ?????? ?????? ??????????. ??????????? ?????, ?.: ??????, ???, 2005. 192 ?. [A. Yu. Zubov, Kriptograficheskie metody zashchity
informatsii. Sovershennye shifry [Cryptographic methods of information protection. Perfect
codes], Moscow, Helios, Association of Russian Universities, 2005, 192 pp. (In Russian)]
5. ?. ?. ??????, ??? ??????????? ????? ??????????????? // ??????? ? ???????? ??????., 2013. ?. 23, ? 1, Ф???????? ?????????????? ???????????? ? ?????????? ??????
???????????╗. ?. 53?57. [S. M. Ratseev, ?On optimal authentication code?, Sistemy i
Sredstva Inform., 2013, vol. 23, no. 1, pp. 53?57. (In Russian)].
????????? ? ???????? 22/X/2013;
? ????????????? ???????? ? 27/I/2014;
??????? ? ?????? ? 27/I/2014.
198
On Construction of Perfect Ciphers
MSC: 68P25, 94A60
ON CONSTRUCTION OF PERFECT CIPHERS
S. M. Ratseev
Ulyanovsk State University,
42, L. Tolstoy st., Ulyanovsk, 432017, Russian Federation.
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.
Keywords: cipher, perfect cipher, set of keys, probability distribution.
Received 22/X/2013;
received in revised form 27/I/2014;
accepted 27/I/2014.
ISSN: 2310-7081 (online), 1991-8615 (print); doi: http://dx.doi.org/10.14498/vsgtu1271
Е 2014 Samara State Technical University.
Citation: S. M. R a t s e e v, ?On Construction of Perfect Ciphers?, Vestn. Samar. Gos. Tekhn.
Univ., Ser. Fiz.-Mat. Nauki [J. Samara State Tech. Univ., Ser. Phys. & Math. Sci.], 2014,
no. 1 (34), pp. 192?199. doi: 10.14498/vsgtu1271. (In Russian)
Author Details: Sergey M. Ratseev (Cand. Phys. & Math. Sci.), Associate Professor, Dept. of
Information Security & Control Theory.
E-mail address: RatseevSM@mail.ru
Документ
Категория
Без категории
Просмотров
5
Размер файла
563 Кб
Теги
построение, совершенный, шифров
1/--страниц
Пожаловаться на содержимое документа