close

Вход

Забыли?

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

?

Птицин Н. - Приложение теории детерминированного хаоса в криптографии (2002).pdf

код для вставкиСкачать
Кафедра «Системы Обработки Информации и Управления»«
Факультет «Информатика и Системы Управления»
Московский Государственный
Технический Университет им. Н. Э. Буамана
Institute of Simulation Sciences
Faculty of Computer Science and Engineering
De Montfort University, Leicester
ПРИЛОЖЕНИЕ ТЕОРИИ
ДЕТЕРМИНИРОВАННОГО ХАОСА
В КРИПТОГРАФИИ
Николай Птицын
np@beep.ru
Москва
2002
?????????
????????? ?????? ????????? ?????????? ?????? ?????????????????? ????? (?????????? ????????) ? ???????????? ????????????. ??????????? ??????????? ????? ???????????? ? ?????????????????? ????????? ?? ?????????????? ? ???????????? ???????. ????????????? ??????????? ???? ????? ???????? ?????????? ????? ??????? ??? ???????????????? ???????????????? ? ????????? ????????, ????????????, ??????????, ?????????, ???????????, ?????????????????. ??????????? ??? ??????? ? ????????????? ?????????? ?????????? ??????? ? ????????????: (1) ????????????? ???????????
?????? ??? ?????? ?????????? ? ????????? ??????? ? (2) ???????? ???? ? ???????????? ?????? ?????????. ??????????? ????? ?????????? ? ????????? ??????????? ?????? ? ??????????? ??????????????? ???????????. ??????????? ?????????? ?????????? ?????? ?
?????? ???????? ? ????????????? ??????????????? ??? ??????????
??????????????? ???????????.
This paper studies the application of deterministic chaos to digital
cryptography. The fundamental relationship between the properties of
chaotic and cryptographic systems is considered at the theoretical and
practical layers. The theoretical background upon which this relationship
is based, includes discussions on chaos, ergodicity, complexity, randomness, unpredictability, incompressibility. Two approaches to the finitestate implementation of chaotic systems are considered: (i) floating-point
approximation of continuous-state chaos; (ii) binary pseudo-chaos. An
overview is given of existing chaos-based encryption algorithms along
with their strengths and weaknesses. Exactly solvable and one-step unpredictable chaotic systems are described in the context of pseudo-random
generators.
1
??????????
?????????
1
??????????
2
?????? ???????????
5
??????? ?????????
7
1 ???????? ???????? ? ???????????
1.1 ???????????? . . . . . . . . . . . . . . . . . . .
1.1.1 ????????????????? ??????? . . . . . . .
1.1.2 ?????????? ? ???????????? . . . . . .
1.1.3 ????? ?????????? . . . . . . . . . . . .
1.1.4 ??????????????? ????????? . . . . . . .
1.1.5 ??????????? ? ?????????? . . . . . . .
1.2 ???? ? ???????????? . . . . . . . . . . . . . . .
1.2.1 ???????????? ??????? . . . . . . . . . .
1.2.2 ??????????? ??????? . . . . . . . . . . .
1.2.3 ?????????? ???????? . . . . . . . . . .
1.2.4 ?????????? . . . . . . . . . . . . . . . .
1.2.5 ???????????? ? ??????????? ???????
1.2.6 ???????? ???? . . . . . . . . . . . . . . .
1.3 ??????????? . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
10
10
11
12
16
16
18
18
18
20
21
21
22
23
2 ???????????, ?????????, ????
2.1 ???????????? ????? . . . . . . . . . . . . . . . . . . .
2.2 ?????????-??????????? ?????? . . . . . . . . . . . . .
2.2.1 ?????????????? ?????? ???????? . . . . . .
2.2.2 ??????????????? ????????? . . . . . . . . . . .
2.2.3 c-??????????? ? ??????????????? ???????????
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
26
29
29
31
31
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.3
2.4
2.5
2.6
2.2.4 ???????????? ????????? . . . . . . . . .
?????????-?????????????? ?????? . . . . . .
2.3.1 ???????? ??????????? . . . . . . . . . .
2.3.2 ???????? ??????? . . . . . . . . . . . .
2.3.3 ??????????? ???????? ? ????????? . .
???????? ? ????????? ??????????? ?????? . .
2.4.1 ????????? ???????????? ?????????
? ?????????? ???????? . . . . . . . . .
2.4.2 ???????? ???????????-????? . . . . . .
2.4.3 ????????? ?????????? . . . . . . . . . .
????????????????? . . . . . . . . . . . . . . . .
2.5.1 ????????????? ???????? . . . . . . . . .
2.5.2 ????????????? ??????? . . . . . . . . .
2.5.3 ??????????????? ????????? . . . . . . .
2.5.4 ???????? ??????????????? ???????????
??????????????? ?????????
?? ???? ??????????? ??????? . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
32
32
32
33
34
34
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
34
35
36
37
37
38
39
40
. . . . . . . . . . .
41
3 ???????????? ??????????
3.1 ???? ? ?????????? . . . . . . . . . . . . . . . . . . . .
3.1.1 ????? ??????? . . . . . . . . . . . . . . . . . .
3.1.2 ?????????? ???????? . . . . . . . . . . . . . .
3.2 ?????????? ?? ????
?????????? ? ????????? ??????? . . . . . . . . . . .
3.2.1 ????? ???????? . . . . . . . . . . . . . . . . .
3.2.2 ????????? ???????????? ????????? . . . . . .
3.2.3 ?????????????? ???????? . . . . . . . . . . .
3.2.4 ????????????? ???????? . . . . . . . . . . . .
3.2.5 ?????????? ?????????????? . . . . . . . . . .
3.2.6 ?????????????? ???? . . . . . . . . . . . . .
3.2.7 ?????? ??????????? ????? . . . . . . . . . .
3.2.8 ??????? ? ????????????? ???????????????
? ?????? ???????? . . . . . . . . . . . . . . .
3.3 ???????? ?????????? . . . . . . . . . . . . . . . . . .
3.3.1 ????? ???????? . . . . . . . . . . . . . . . . .
3.3.2 ?????????? ?????????? ?????????????? . . .
3.3.3 ????????? ???????? . . . . . . . . . . . . . .
3.3.4 ?????????? ?????????????? ?????? . . . . .
3.3.5 ?????????? ? ???????????? ?????????????? .
3
. . . . . . . .
. . . . . . . .
. . . . . . . .
44
44
45
46
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
47
49
50
51
56
57
58
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
60
62
62
63
64
65
67
4 ??????????
4.1 ????????????? ?????? . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 ???????????? ?????? . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 ?????????? ?????? . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
69
70
71
??????????
73
?????????? ?????????
79
4
?????? ???????????
1.1
1.2
1.3
1.4
1.5
1.6
1.7
2.1
2.2
2.3
2.4
????????????? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
????? ?????????? ???????? ????????? ??? ?????? ??????????
? ????????????. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
?????????? ??????? ?????????????. ?????? ???? ?????????
??? ?????? ????????? ??????????, ?????? ????????? ?????????? ???????? ???????? ?????, ? ?????????????? ? ??????????.
??????? ???????????? ????????????? ????? ???????? N . ??????????? ???? ????????? ?? ???? ?????? ??????????. . . . . . . .
?????????? ????????? ?????????????. (a) ?????????? c ???? ??????? ????? ????????? ?????? p ? ???????? ????????? x (??????,
1991); (b) ?????????? c ???? ????? ???????? n (????, 1999; ????????, 2000); (c) ?????????? c ???? ?????????????? ?????????
??????? ????? p ???????? (???????, 1996). . . . . . . . . . . . . .
????????? ??????????? ???????: (a) ????????? ????????????; (b) ??????? ????????????. . . . . . . . . . . . . . . . . . . . . . . . . . . .
?????????? ????: ???????? ???????????????? ? ????????? ???????? (a) ? ?????????????? ?????????????? (b) ?????????? ?? ????????? ?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
?????? ??????? ????????? ??????????? ? ????????????????? ??????. ??????????? ??????? ????? ????? ??????? ??????????? ???????, ??? ????? ??????????? ?????????? ??????? (?????). ? ????????????????? ???????? ????????? ???????????? ??? ????????????
? ????????????, ????? ???????????? (??????). . . . . . . . . . . .
???????? ???????????, ?????????????????, ??????????????? ??????????? ? ????????????? ?????? ???????. . . . . . . . . . . . . .
????? ????????????????? . . . . . . . . . . . . . . . . . . . . . . .
??????????? ???????? ?? ????????? . . . . . . . . . . . . . . . . .
???????????? ?????????????? ??? p = 1279 ? q = 255. . . . . . . .
5
11
12
13
14
19
22
24
27
28
36
42
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
3.12
3.13
3.14
3.15
3.16
3.17
3.18
???????? ??????????? ? ????????????????? ??????. . . . . . . . . 45
?????? ????????????????? ??????. (a) ???????? ? ??????????????? ?????? (?? ???????? ??? ????????????); (b) ???? ???????
?????? (???????? ??? ?????????? ?????); (c) ????????? ?????????? ????? (???????? ??? ???????? ?????). . . . . . . . . . . . . . 46
?????????? ???????? ? ??????????? (a) ? ????????????????? (b)
???????? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
?????????? ??????????? ??????? (????????????? ????????) ? ?????????? ?????????????????? ??????? ? ????????? 64 ????. ?????? ?????????? ??????????? ?? ?????? ????????. ?????????? ??????????? ??????? ???????? ??? ?????? ??????? ??????????????
???????. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
??????????? ? ??????? ????? ????? (Lmin ? Lavg ?????????????)
? ????????????? ??????? ? ??????????? ?? ???????? ?????????? b
(? ?????). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
???????????? ??????? ????????????? ?????????? ????, ??????????? ??????????????? ????????, ?? (???????? ?????) ? ?????
(???????? ?????) ????????????. ???????? ????? ?????? ?? ??????????? ????? ????????????? ?? ??????? (?2, 2). . . . . . . . . 51
????????????? ???????? ??? r = 0.99. . . . . . . . . . . . . . . . . 52
????????? ??? ?????????? ? ????????????? ??????? ??? x0 = 0.34
? r = 0.99. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
?????????? ????????????? ???????. ???????? ???????????????
????????? ??????????? ??? r = 1. . . . . . . . . . . . . . . . . . . . 53
?????????? ??????????? ??????? ?????. . . . . . . . . . . . . . . 53
??????? ????????????? ??????? ??? n = 5. . . . . . . . . . . . . . 54
????????? ????????????? ????????? ? ????????????? ???????. ???????? ????????? X ?? ???????????? X0 ? X1 ? X ????????? ???????????? ?????? ?? ??????? ???????????? ?????????, ??????? ????????????? ?????????? ?????????????????? ??????????. . . . . . . . 55
?????????? ??????????????. . . . . . . . . . . . . . . . . . . . . . . 56
????????????? ????? ?????????? . . . . . . . . . . . . . . . . . . 57
????????????? ?????????????? xn+1 = f (xn ) . . . . . . . . . . . . 61
?????????? ?????????? ??????????????. . . . . . . . . . . . . . . . 64
?????????? ?????????????? ??????. . . . . . . . . . . . . . . . . . 65
????? ???????? ?????????????? ?????? c ?????????? ? = {0.25, 0.5, 0.25},
??????????? ? ??????????? [76]. . . . . . . . . . . . . . . . . . . . 66
6
??????? ?????????
?????? ??????? ??????? ??????, ? ??????? ??????? ?? ??????????? ?? ???????????? ??? ????????, ?????????? ???????????? ??? ????????????????? ??????.
??? ??????? ????? ? ??????? ??????? ???? ???????????? ???????, ???? ?
????????? ???????? XX ????, ?? ? ??? ??? ??????? ? ??? ?? ?????? ?? ?????? ?
????? ???????????, ???????, ???????, ????????, ?? ? ? ???????????? ????????.
??? ?????? ???????? ????????????? ?????? (?? ????. synergeia ? ?????????? ????????, ??????????????) ??? ????????? ? ?????? 70-? ????? ????????
??????? ?. ???????. ??????? ??? ???????????? ???????? ??????? ??????? ????????????, ????? ??????? ???? ????????? ????? ??????????????? ? ????????? ???????????, ???????????? ? ?????????? ????????????? ????????? ? ???????????????? ???????? ? ??????? ????????????? ???????? ????????? ???????: ??????????, ??????????, ?????????????, ?????????? ? ?. ?. ????????????
??????? ? ??????????? ???????? ??????? ???????????? ? ???????? ???????
?????????? ??????? ? ????????? ??????? [13, 15].
??????? «???????????????????» ? «????» ? ???????1 ??? ??????????????2
?????? ?? ?????? ?????? ??????? ????? ???????????????? ?? ??????. ??????????? ????????????? ? ?????? ???????????????? ? ??????????????????, ????
? ? ?????? ?????????????????? ? ????????????????????. ????????? ??????
???????? ??????? «????????????????? ????» ? ??? ?????????????? ??????.
????? ??????? ? ???????????????????, ????????????? ????????-???????????? ?????. ???? ?????? ????????? ????????? ??????? ? ????????? ?????? ???????, ?? ??? ?????????? ?????????? ????????? ??????? ? ???????. ? ????????????????? ???????????? ??????? ????????? (?. ?. ???????????? ??????????
??????????? ??????????) ?????????? ?? ??????? ?? ?????????? ????????? (??????????????????) ??????.
?????? ????????? ???????????? ??????? ?? ?????????? ? ???????????. ??1
???? ? ??????????, ??????????? [22].
??????, ??????????????? ???? 8?7 ??. ?? ?. ?., ??????? ????????? ???? (????. cha?os, ??
cha?ino ? ???????????, ???????) ? ????? « ????????». ?????? ?????????? ????????????? ??????????? ?????, ?? ??????? ???????????? ???????????? ??? ???????????? [22].
2
7
???????? ??????? ???????? ???????????, ?? ???? ????? ?????????? ?? ???????? ????????, ? ??????? ???????????? ? ????????? ??????????? ?????????
(?????????????). ????????, ??????????? ???????, ???????????, ? ????? ?????????? ????????? ?? ???????. ??????????? ??????? ???????? ??? ??????????
???????????????? ????????????????? ? ????????? ????????, ?? ???? ????????? ????????? ?????????? ????????? ??????? ???????? ? ????????????? ????????? ?? ???? ??????????. ????????? ? ????????? ???????? ??????????? ??????????????? ?? ???????. ??? ??? ???????? ??????????? ?? ????? ????????
????????? ??????? ? ?????????? ?????????, ?????? ??? ???????????? ??????
????????? ?? ????????????? ??????. ????? ???????, ????????? ????????????????? ??????????? ??????? ????? ???? ??????????? ?????? ???????????? (???
?????? ????????? ??????? ????????? ?????????????, ???????????? ??????????????? ??????????? ?????????? ?????????? ? ?????? ??????? ????????????
?????????). ????????????????? (??? ????????????) ?????? ?????????? ????
??????, ????????? ??????????? ???????, ???? ???? ???????.
??????? ?????????????? ?????? ?????????????????? ????? ???????? ??????????????? ??????? ?????????????? [17, 6, 19, 21]. ??????????? ????????, ???
????????? ????????? ??????????? ?????? ??????? ?? ? ??????? ????? ???????? ??????? ? ?? ? ??????? ??????????, ? ? ???????????????? ??????????????. ????????????? ????????? ???????????? ????????? ???????? ???????????
????????, ????????? ??????, ????????? ????? ??????????????? ???, ?????????
???????? ?????, ????????????? ???????? ? ????????? ????????.
? ???? ??????, ????????????????? ??????? ?????? ?? ???????? ??????????? ? ???????????? ?????????? ??? ???????????? ? ????????????? ??????
? ???????? ?? ??????? ?????. ??????????? ? ????????????????? ??????? ????????????? ?? ?????????????? ??????. ? ? ????????????, ? ? ?????????? ???????? ?????????????? ?????????? ?????????????? ??????????. ? ????? ???????, ??? ?????????????? ??????????????? (??????????? ???????????), ? ?????? ???????, ??? ?????? ???? ??????????? ??????????????? ??? ???????? ???????????. ????? ???????, ?????????????? «????????????????? ????» ??????
«????????» ??? ????????????. ? ???? ??????, ?????????? ????? ??????????
???????? ???? ????? ?? ???? ???????????????? ??????? ? ?????? ?????.
?????? ?????????????? ???????????, ????? ????????, ??? ? ?? ???????????? ?????? ????????????????? ? ??????????? ??????? ???? ??????. ???, ??? ?
?????? 1950 ??. ???? ??????, ???? ?? ??????????? ?????? ?????????????? ?????
? ??????????? ????????????, ? ????? ???? ???????? ????????????? ? ????????? ???????? ????? ????????????? ? ?????????? ??????: «Good mixing
transformations are often formed by repeated products of two simple noncommuting
8
operations. Hopf 3 , has shown, for example, that pastry dough can be mixed by such a
sequence of operations. The dough is first rolled out into a thin slab, then folded over,
then rolled, and then folded again, etc. . . »4 [79] ??????????????? ????????????????? ???????? ?????????? ? ?????????????? ?????????????? ????? ?????????
??????????? ? ???? ??????.
??????, ???????? ???????????? ???? ??????? ????? ??????????? ??????????? ???????, ?????? ? ????????????? ??????????? ?????? ????? ? ?????????
?????????????? ???????. ??????????? «??????????????? ????» ? ?????????
????????????? ? ?????????????? ???? ?????? ????? ???????? ?????? ???????????? ???????????? ???????. ?????? ????????????? ???????????? ???? ?????? ??????????, ??????????? ??????????? ????? ????? ??????????. ? ??????? ???????, ??? ??????????? ?? ??????? ???????? ??????????? ?????????????
??????????????? ???????????? ???? ?????????? (??????? ? ??? ???? ??????? ????? ?????????), ?, ???????, ?????????????? ?? ???????? ?? ???????????? ?????????? ? «??????????» ?????????????? ???????, ???????, ????????
????? ????????? ???? ???????????? ????? ???????????????.
????? ???????? ???????? ????????? ?? ????? ?????????? ??????? ????????, ????? ????????????? ??????, ????????? ? ????? ?????????? ???????, ????????????? ??????????? ? ?????? ? ???????? ????????. ???, ?????? ????? ????
?????? ???????? ????? ????? ?????????? ?????? ?????????????????? ?????
? ????????????. ?????? ?????? ??? ????????? ????????? ?????? ?? ??????,
???????? ??? ?????????? ??????????. ?? ????????? ??????????????? ? ???????? ???? ????, ? ??? ?? ????????, ??? ??? ???????????? ?????????????????
??????? ????? ??????????????? ? ?????? ???????????????? ??????? (?? ???? ???
?????????? ???????????? ???????).
3
????, ?.?.?. (1902?1983), ??????????? ?????????, ?????? ???????????? ????? ? ??????
???????????? ? ?????????.
4
??????? ??????????? ?????????????? ????? ???????? ??? ?????? ????????????? ?????????? ???? ??????? ??????????????? ????????. ???? ????????, ???????, ??? ????? ?????
???? ??????? ??? ?????? ?????????????????? ????? ????????. ??????? ????? ???????????
? ?????? ??????? ?????, ????? ???????????? ???????, ????? ????? ??????????? ? ??????
????? ? ????????????, ? ??? ?????. . .
9
????? 1
???????? ???????? ?
???????????
? ????? ??????????????? ??????????? ????? ?????????????????? ????????? ?
????????????? ????????? ? ?????? ?????????????????? ?????. ????????????
??????? ??????? ?? ???????????? (?. ??????? [77], ?. ???????? [69]) ? ?????????? ???????? (??. ?. ??????? [11], ?. ?. ?????? [12], ?. ?. ????? [9]).
1.1
????????????
???????????? ?????????? ????????? ?????? ?????????? ????? ?? ??????????????. ???????????? ?????? ?????? ??????????????????, ??????????????, ??????????? ? ??? ?????? ? ???? ?????????. ???????????? ???????????? ???????
?????? ?????????? ??????, ?????????? ??????? ? ?????????????, ????????
???????? ???????. ???????????? ?????? ??????? ????????????????? ??????,
? ?????????, ??????????? ?????? ? ??????????????????? ???????????? ?????? (??? ?????? ?????). ??????????? ? ??? ?????? ??????????, ?????????
?????????????? ?????? ??????? ???????????? ? ?????????????.
1.1.1
????????????????? ???????
? ??????? ??????, ????????????????? ??????? ???? ??? ??????????????, ?????????????? ?????? ?????????? (?????????? ??????????????? ???????), ??
???? ???????????? ????????????? ??????? ??????????, ???????? ??????, ?????????????? ? ?????? ?????????. ? ???????? ?????, ????????????? ????????????
????? ?????????-??????????? ????????, ????????????????? ? ?????????.
10
x0
k
x = f (x,k)
x1, x2, ...
x
???. 1.1. ?????????????
? ????? ?????????????? ??????, ????????????? S = hX, Y, K, f i ???? ????????? ?????????????? ?????????? f : X ЧK ? Y , ???????????? ?? ??????????
???????? ????????? X, ?????????????? ????????? Y ? ?????? K. ?????????
x ? X ???????? ????????? ???????? ??????????. ? ???????????? ???????????? ????????? X = Y =? {0, 1}? , K ? {0, 1}? , ? ?????????????? f ??????
??? ?????? ????????? (?????????), ???????????? ?? ?????? ???????? (?????? 2.2.1).
?????????????? f ????? ??????????????? ? ???????? ???????? ?????????????????? ????????? (???. 1.1). ????? ????????????? ?????????? ?????????????????? ????????? x0 , x1 , . . . , xi , . . ., ??? xi = f (xi?1 , k) = f i (x0 , k), x0 ? X, k ? K.
??? ?????????????????? ?????????? ??????????? ??? ??????? ???????. ??? ?????????? ???????????? ????????? ?????????? ??????? x0 ? ?????????? k.
???????????????? ?????????????? ????????? ??????? ? ?????????? ?????????? ????????? ?????????? ???????????? ??????? f ????? ????????? ? ??????? ? ???????? ??????, ??????????? ??????????????? ?????, ?????????????
????????. ????? ??????? ???????? ??????????? ????????????? ? ???????
??????.
????? ???????, ??? ?????????????? ? ????? ?????? ????? ???????? ???????????? ??????? hf, X, Ki ? ?????????? ???????? f , ????????????? ????????? X ? ????????????? ?????????? K. ??? ????? ???????? ????, ??????????
? ?????????????? ??????????? ????????????? ? ?????? ?????????? ???????????? ?????? ??? ???????????, ???????????? ? ??????????.
1.1.2
?????????? ? ????????????
? ???????? ??????????, ?????????? ??????, ????? ????????????? ?????????
????????? p. ?????????, ?????????? ??? ?? ???????? ??????? (plaintext), ????
11
???. 1.2. ????? ?????????? ???????? ????????? ??? ?????? ?????????? ?
????????????.
?????????????????? ????????
p = {p1 , p2 , . . . , pn | pi ? P} ,
??? ??????? P ???? ???????? ????????? ????????, ???????????? ??? ??????????? ??????????. ? ???????????? ??????????????, P = Z2 = {0, 1} (????????
???????). ????? ????????????? ??????? ?? ???????? ??????, ?. e. P = Z256 .
???????? ?????????? ???? ????????????????? ?????????????? E : P ? ЧE ?
?
C , ??? C ? ??????? ???????????, ? E ? ????????? ?????? ??????????, ??
????
c = E (p, e) = Ee (p), p ? P, c ? C, e ? E.
???????? ???????????? ???? ???????? ?????????????? D : C ? Ч D ? P ? , ??? D
? ????????? ?????? ????????????, ?? ????
p = D(c, d) = Dd (c),
p ? P, c ? C, d ? D.
??????, C = P ? {0, 1}? ? E = D = K ? {0, 1}? .
?? ???. 1.2 ???????????? ???????????? ????? ?????????? ???????? ????????? ??? ?????? ??????????/????????????.
1.1.3
????? ??????????
??????????? 1. ????? ?????????? (??????, ????) ???? ????????? ????
S = hE, D, P, C, Ki ,
12
x
N = const
c=xN
f(x)
x0=p
0
16
n
???. 1.3. ?????????? ??????? ?????????????. ?????? ???? ????????? ???
?????? ????????? ??????????, ?????? ????????? ?????????? ???????? ???????? ?????, ? ?????????????? ? ??????????. ??????? ???????????? ????????????? ????? ???????? N . ??????????? ???? ????????? ?? ???? ?????? ??????????.
??? E : P ? Ч K ? C ? ? D : C ? Ч K ? P ? , ????? ??? ??? ??????? ????? e ? K
?????????? ?????????? ???? d ? K ? Dd = Ee?1 , ?? ????
?p ? P, e ? K, ?d ? K : p = D E (p, e) , d .
???????????, ????? ???????? ??????????? E, D ? ??????????? P, C ? K.
??????????? ????????? ???? ?????????? ???????? ?? ???, ??? ??? ???????? ?????????? (????????????) ???????? ?????????, ?? ???? ????????????
???????????????. ??????? ????? ????? ???????????? ???? ???????????? ??????? ? ?? ????? ????????????? ????????. ? ??????????? ?????????? ???????????
?????????????? ??????? ???????? ? ????? (??????? ????????).
???????????? ? ????????????? ?????
????????? ???????????? ? ????????????? ????? ??????????. ? ???????????? ?????? (??? ?????? ? ????????? ??????) ?????????? ???? ? ??? ?? ????
??? ?????????? ? ????????????, ?. ?. p = D (E (p, k) , k), k = e = d (???
?? ???? d ?????? ??????????? ?? e). ? ????????????? ?????? (??? ?????? ?
???????? ??????) ????? e ? d ?? ?????????, ? ?? ?????? (??? ???????????
?????????) ????? ??????????? ?????????? ???????? ?????? ??? ????.
??????? ? ????????? ?????
?????? ????????? ????????????? ???????? ??????? ? ????????? ?????. ??????????? ??????? ????? ??????????? ? ???, ??? ?????????? ??????????????
13
(b)
x
x
(a)
f(x)
c1=x1+p1
p2=xn2
x0
c2=x2+p2
x0
c3=x3+p3
n
p1=xn1
f(x)
p3=xn3
c1=n1-n0 c2=n2-n1 c3=n3-n2
n
x
(c)
f(x)
x0
c1=xn1
c2=xn2
c3=xn3
n 0 n 1= n 0+ p 1 n 2= n 1 + p 2 n 3= n 2 + p 3
n
???. 1.4. ?????????? ????????? ?????????????. (a) ?????????? c ???? ???????
????? ????????? ?????? p ? ???????? ????????? x (??????, 1991); (b) ?????????? c ???? ????? ???????? n (????, 1999; ????????, 2000); (c) ?????????? c
???? ?????????????? ????????? ??????? ????? p ???????? (???????, 1996).
14
??????. ?????? ???? ????????? (???????????) ?????????? ?? ??????. ?????????? ????? ????????? ?????? ????? ????????????? ? ?????????? ????? ???????????. C ?????? ???????, ???????? ????? (??? ?? ?????????? ?????? ?????????) ??????????? ????? ???????? (??????) ?????? ? ????? ???????????, ??????
?????????????? ??????? ?? ????????? ???????. ?????????? ??????? (?????)
?????? ????? ????????? ??????????? ? ????????? ??????? (?????) ???????????.
??? ??? ??????????, ????? ?????????? ????? ????????????? ? ????? ?????? ?????????? ????????. ??????????? ????????? ?? ???????????? ??????.
1) ?????????? ???????? ????????? ?????????????? ????? n-???????? ?????????? ????????? ???????????? ??????? f (???. 1.3). ????? n ??????????? ? ???????? (?????, n = 16). ?????? ???????? ????????? ????????????? ? ????????? ?????????, ?? ???? xi+1 = f (xi ). ?????????? ????????? ????????????? ???????? ????? (x0 = p), ? ?????????????? ?????????
??????????? ?? ?????????? (c = xn ).
2) ????????? ????? ????? ?????????? ? ????? ?????? ????????????? ?????????? (???. 1.4). ?? ????????????? ?????? ???????? ??, ??? ???? ?????????? «??????» ????? ???????????, ?? ???? ?????????? ?????? ?????????
?????? ??????? ?? ???????? ????????? ?????????????. ????? ???????? ??
???????????, ? ??????? ?? ?????? ????????? ??????.
??????? ??????? ? ???????? ????????????, ???????????? ???? ? ????? ????,
????? ??????????? ? ????? 3.
???? ???????
?????????? ????????? ?????? ???????? ???? ??????? [69]. ?????????? ?????????????? ????? ????????? ???????? ?? ?????? 2 ????????? ?????? ? ???????? ??????????????????.
ci = pi ? ki
???????????? ?????????? ????????? ???????????? ?????:
pi = ci ? ki ,
??? ??? pi ? ki ? ki = pi .
?? ???. 1.4 (a) ???????????? ??????????? ????? ??????????. ??????????
????????????????? ??????? f ????????????? ???????? ??????????????????. ????? ?????? ???????? ?????????? ?????????? ci = pi + xi (???????????? pi =
ci ? xi ).
???? ???????? ?????????????????? k = {ki } ???????? ??????? ?????????,
?? ???? ??????? ?????????? ??????????? ?????????. ???????? ??????? ??????????? ? ????????? ???????????? ????? ??????????? ? ????? 2.
15
1.1.4
??????????????? ?????????
???? ?????? [78] ???????, ??? ???????????? ????? ?????????? (????????,
???? ???????) ?????????? ????????? ?????? ? ??? ??????, ???? ???????? ?????????????????? k ????? ??????????? ????? ????????????? (??????? ????????) ? ?? ??????? ????? ????? ????? ????????? ????????? p (????????, ? ??????
???????????? ????????). ?? ???????? ????? ????? ???????????? ? ??????????
?????? ??????????????. ?????? ??? ?????????? ??? ?????????? ??????????????? ??????????????????. ??????????????? ?????????????????? «???????» ??????????, ?? ???? ?? ????? ????????????? ?? ????? ???? ?????????? ???????
?? ???????????? ?????? (?????????? ??????????????? ??????????). ? ??????
???????, ??????????????? ?????????????????? ??????????? ????????? ????????????????? ??????????? ?? ????????? ????? (??????), ??? ????? ??????????????. ????? ??????, ??????????? (????????????????) ?????? «?????????????»
?? ???? ??????????????????.
??????????????? ?????????? ?????? ??????????? ???? ? ??????????? ????????????. ??? ??? ???????? ?????????????????? ?????????????? ?????? ?????????? ?????????? ? ??????? ?????????? ????? ?????????, ???????? ??????
??? ?????????. ????? ??????????????? ?????????????????? ???????????? ? ???????? ?????????? ?????????????????? ??????????????. ????? ??????? ??????????????? ????????? ?????? ??? ??????? ????????????????? ??????????????.
???????? ?????????? ???????, ?? ????? ????????????? ???????????????
????????? ??? ???????????? ???????. ?? ???. 1.1 ???????????? ???????, ??????????? ?????????????????? ?????. ????? ??????????????????, ??????? ?????
???? ????????????? ????????, ???????? ?????????? ?????????? x0 ? ?????????? k.
?????? ??????????? ? ???????????? ???????, ???????????? ??? ????????? ???????? ???????????????????, ???????? ????????????????? ? ?????????????????. ? ????????? ???????? ?? ?????????? ??? ??????? ? ????? ??????
?????? ????? ? ?????????? ????????. ?????????? ??????????? ???????????????? ?????????? ???????????? ? ????? 2.
1.1.5
??????????? ? ??????????
??????? ????????? ???????? ?????????????????? ????????? ????????? ????????? ?????????????? ?????????????? ?????????????????? ??????????????. ??????, ??? ??? ???? ????????, ? ???????????? ?????????? ???????????????
??????????????????, ??????? ????????? ????? ?????????? ?? ???????? ??????
«?????????????» ? ??????????. ??? ??? ???????? ?????, ??? ???????, ????????
????????? ?????????????, ???????????? ?????????? ???????????? ??????????
16
??? ??? ??????? ?????????? ? ?????????????? ????????? ?????????. ???????????? ????????? ????? ???? ???????? ??? ?????? ??????? ??????????.
??????????? ????????? ??????????????? ???, ??? ????????? ???? ?? ??????
??? ????, ???????? ? ??????? ????????? ??? ??????.
???? ????????? ?? ????? ???? ????? ?? ?????????????? ????????, ??, ???????? ???????, ?????????? ???????????? ??? ??????? ??????? ??? ???????
????????????:
??????????? (confusion) ????????????, ??? ?????????????? ???????? ?????????
?????? ?? ??????? ? ???????????. ??? ??????? ??????????? ??????????
?????? ???????? ?????????, ?? ???? ???? ???????????????.
?????????? (diffusion)
1) ? ?????? ??????, ?????????? ????????????, ??? ????????????? ??????? ?????????????????? ?????? ????????????? ? ?????????? ????????? ?????????????????? ??????????? (??? ?????????? ????? ? ???
?? ??????). ??????? ???????, ????? ??????? ????????? ?????? ?????? ?????? ?? ??? ???????? ??????????? ??????? ???????????????
???????. ???, ????????? ?????? ???? ????????? ?????? ????????? ?
????????? ???????? ????? ???????????.
2) ? ?????? ?????, ?????????? ????????????, ??? ??????? ????? ??????????? ????? ? ?????????? ?????? ???????????. ??????????, ?????? ??? ????? ?????? ?????? ?? ?????? ??? ??????????? ??????? ??????????????? ???????. ??? ?? ???????? ?????? ????? ?????
? ??? ????????????, ??? ??? ? ????????? ?????? ??????????????
????? ??????????? ?????????? ???? ????, ??? ????? ????? ???????
?????.
???? ?????? ? ????? ???? ?????????? ? ???????????? ??????? ??????.
???????????? ??????? ???????? ???????? ????????? ???????? ???? ??????????? (??????, substitution) ? ????????????? (permutation). ??? ? ????????????
????????? DES ???? ??????????? ??? ?????? ?????? ??????????? (s-box) ?
????????????? (p-box). ?????????, ??? ???? ???????????? ???????????? ???????????, ? ???? ????????????? ? ??????????. ? ???????? ?????, ??? ????????
???????????? ????????????????? ??????????? ??? ?????? ?????? ? ?????? ?????. ????????????? ???????? ??????????? ????????? ???????? ????????????
???????????? ??????? ?????????????.
17
1.2
1.2.1
???? ? ????????????
???????????? ???????
???????????? ??????? ???????????? ????????? ? ???????????? ??????? S =
hX, K, f i, ????????? ?? ??????????, ????? ???? ?????? ????????????????
??????????
dx
= f (x, k) , x ? X ? Rd , k ? K ? RdK ,
dt
??? f : X Ч K ? Y ? ??????? ??????-???????, X ? ???????????? ????????? ?
K ? ???????????? ??????????? ??????????. ??? ??????? ?????????? ???????
x0 ??????? ????????????? ??????? ????????????? ? ?????????????? ???????
x(t, x0 ), ??? x (0, x0 ) = x0 [11]. ?????? ?t (t, x0 ), ??????????????? ????? ???????, ?????????? ???????????.
???????????? ??????? ???????????? ????????? (??????????? ???????) ????? ???? ?????? ???????????? ????????
xn+1 = f (xn , k) ,
xn ? X ? Rd , k ? K ? RdK , n = 0, 1, 2, . . .
(1.1)
??? xi ? ?????????? ????????? ???????. ?????????? ? (i, x0 ) ???????????? ?????
?????????????????? x0 , x1 , x2 , . . . ????? ????????, ??? ????????? (1.1) ??????
?? ????????????????? ???????????? ???????, ???????????? ? ??????????????? ???????????, ??????? ?????? ? ??. (??. ???. 1.1?1.4): ? ???????????? ? ?
????????????????? ???????? ?? ????? ???? ? ???????????? ???????????????
??????????, ????????? ?? ?????????.
???? ?? ????? ???????? ???????? k ? ???????????? ??????? hX, f i ? ???????????? ??????? f (x). ????????? n-???????? ?????????? f (x) ????? ?????????? ? ????
xn = f ((· · · f (x0 ) · · · )) = f n (x0 ) , x0 , xn ? X.
1.2.2
??????????? ???????
??????????????? ???????? ????????? ????????? ??? ??????? ??????????? ??????????? ????????? ??????? [30]. ? ?????????, ??????????? ???????? ???????? ??? ???????????? ???????? ? ?????????????? ?????????????? ? ???????????????? ? ????????? ????????.
??????????? 2 (??????????? ???????). ???????????? ??????? hX, f i ?????????? ???????????, ???? ??????????? ???????:
1) ??????? f : X ? X ????????????? ??????????? ?? ????????? ??????????? ????????? X ? Rd , ???? ??? ????? ???????? ???????? U, V ? X
18
(a)
(b)
y
y
X
i=0
i=n
x
x
i
???. 1.5. ????????? ??????????? ???????: (a) ????????? ????????????; (b) ??????? ????????????.
?????????? n ? 0, ????? ???
f n (U ) ? V 6= ?.
2) ??????? f ????????????? ? ????????? ????????, ???? ?????????? ? >
0, n ? 0, ????? ??? ??? ?????? x ? X ? ??? ??????????? Hx ???? y ? Hx
??? ????????
|f n (x) ? f n (y)| > ?.
??????? ???????, ???????????? ??????? ?????????? ???????????, ???? ???
?? ?????????? ??????????, ?? ?????? ?????????? ? ?????? ????? ???????? ???????????? (???. 1.5)1 .
?????????????, ????????????? ? ??????? 1.1, ?? ????? ??????????? ??????
?? ??????????? ???????: ?????????????? ?????????????? ??????????, ? ?????
???????, ??? ?????????? ????????? ????????????? ? ??? ????????, ??????? ????????? ???????? ??????????, ?, ? ?????? ???????, ??? «????????» ????? ???????????? ????????? ???????????. ???????????????? ? ????????? ????????
????????????? ???????????????? ????????????? ? ???????? ?????? ??? ??????
1
?? ???. 1.5 ??????? ???????? ?????????? ??????? ? ?????????? ???????????. ????, ???
????????? ??????? ?? ????? ???? ??????????? ? ??????????? ????????????. ? ?????????
?????? ????? ??????????? ?????????? ????????? ?? ? ??????????? ??????????? ?????. ????????, ??????????? ??????? ? ???????????? ??? ? ????? ????? ???? ???????????? [10]. ???
????????? ?? ????????? ? ???????? ??????????? ???????, ?????????? ?????????? ???? (1.1),
? ??????? ?????????? ???????????? ????? ?????????????????? ?????????? ????????.
19
???????????????? ?????????? (??. ?????????? ? ??????? 1.1.5). ????? ???????,
? ? ?????? ?????, ? ? ???????????? ?? ????? ???? ? ?????????, ? ???????
????????? ????????? ????????? ??????? ???????? ? ???????????? ?????????? ?? ???? ??????????.
1.2.3
?????????? ????????
? ??????????? ??????????? ??????? (2) ?? ????? ??????? ????????????????
? ????????? ????????. ?????????? ???????? ?(x0 ), ???????????? ??? ??????
????? x0 ? X, ???????? ????? ????????????????, ?? ???? ????????????? ????????
????????????????? ?????????? ??????????, ??????????? ? ??????????? x0 [17].
??? ?????????? ???????
|f n (x0 + ?) ? f n (x0 )| = ? · en?(x0 ) ,
??? ? ? ????????? ?????????? ?? ?????????? ????????? x0 , ? n ? ????? ???????? (?????????? ?????). ? ????? ??????, ? ??????? ?? ????????? ???????
x0 , ??????? ?????????? ??????????? ????????. ??? ??????, ??????????? ????
(1.2.5), ? ???????? ?????????? ??? ???? ??????????. ???????????, ??????????
???????? ????? ????????? ??? ??????
n
f (x0 + ?) ? f n (x0 ) 1
(1.2)
? (x0 ) = lim lim log n?? ??0 n
?
???
n
n
Y
0
0
1X
1
f (xk )
? (x0 ) = lim
log f (xk ) = lim log
n?? n
n?? n
k=1
(1.3)
k=1
??? ??????? k, ??????????? f 0 (xk ) ?????????? ??? ?????? ?????????? ???????
f ?? ????????? ? ??????????? ????????? ? xk ?? xk+1 . ?????? ????? ???????? ???????? ????????? ??????????? ????? n ???????? ? ?????????? ????????
??????????? ?????????? ? ??????? ??????????? ??????? n. ????????????? ???????? ?????????? (? > 0) ???? ????????? ???????????? ????????? ???????.
??? d-?????? ??????? ?? ????? ????? ? = {?1 , . . . , ?d } ? ????? ???????
?????????, ??????? ??????????? ?? ?????????? ?? ??????????? ?????? [70].
??? ????? ?????????? (????????) ??????????, ????? ???????? ???????????
??????????? ???????? ???????????-????? hKS , ??????? ????? ??????????? ?
????? 2.
? ??????? ????????????, ?????????? ???????? ???????? ????? ????????????????? ????????????? ???????. ??? ?????? ?, ??? ?????? ???????? ????????? ??? ?????????? ???????? ??????? ?????????? ??? ?????????? ??????????.
20
1.2.4
??????????
??????????? (?? ???. bifurcus - ???????????) ?????? ???????? ??????? ????????????? ???????? ?? ??????????? ????????? ? ???????????? ? ?????????? ????????? ???????????? ?????????. ????????, ???????? ??????????? ????????
????? ?? ????? ?????????? (???. 3.9). ? ?????? ?????????? ?????????? ???????? ????? ?????????? ????????? (????????). ? ??????????? ????????? ????????
?????????? ??? ???? ? ????, ? ???????? ? ???????????? ?????? ???????.
? ????????????????? ??????????? ????? ???????? ???????????? ????????? ?????????? ????????????????? ???????. ???? ???????? ???????????? ? ???????? ?????, ?? ??? ???????????? ?????????? ?????? ?????? ???????????????
???????????? ??????.
1.2.5
???????????? ? ??????????? ???????
????? ???????????? ??????? S = hX, f i ????? f -???????????? ???? µ, µ (X) <
?, ?? ????
?A ? ? (X) ,
µ (A) = µ f ?1 (A) ,
??? ? (X) ???? ?-??????? ????????? ??????????? X. ????? f -???????????? ???? ??????????? ???? ?????? c ???????? ????????? ????????????? g (x), ???????????? ?????????? ?????????????? ??????????? g1 ? g2 :
0 < g1 < g (x) < g2 ,
R
??? ?A ? ? (X) , µ (A) = A g (x) dx. ???? g1 ?????? ? g2 , ?? ???? µ ?????? ?
???????????? ?????? ?????????????.
???????????? ??????? ?????????? ????????????, ???? ?????????? ??????
??????????? ???????????? ?????????, ?? ????, ??? ?????? ?????????? ????????? A, f -????????????? ???????????? ???? µ, ????? ???? µ (A) = 0, ????
µ (X \ A) = 0 [12]. ???????????? ?????????????, ??? ???????????? X ?? ?????
???? ????????? ?? f -???????????? ????????????? ? ???????????????? ????????????. ? ????? ?????? ????????????, ??? ???????? ???????????? ???????????? ???????????? ?????? ????????????? ??????? ???????? (brute-force ? ?????
?????? ?????), ??? ??? ?????????????? ?????? ????? ????? ?? ????? ???????????? ????????? X ? ?? ????? ???????????? ????????? «??????????????» ?????????????. ???????? ?????????? ????? ??????? ? ???????????? ???????????
??????????.
???????????? ??????? ?????????? ???????????, ???? ????????? ???????
µ (f ?n (C) ? P )
µ (C)
?C, P ? ? (X) ,
lim
=
.
n??
µ (P )
µ (X)
21
???. 1.6. ?????????? ????: ???????? ???????????????? ? ????????? ????????
(a) ? ?????????????? ?????????????? (b) ?????????? ?? ????????? ?.
???? µ (X) = 1 (???? µ ?????????????), ??
lim µ f ?n (C) ? P = µ (C) µ (P ) .
n??
??????????? ???????? ?????????????, ??? ?? ????? P , ??????? ???????? ? C
????? n ?????????????? f , ?????????????? ??????????????? ??????? C ? X
(? ?????? ???? µ). ????? ????, ???????????? ?????????????? f ?????? ?????
????????? C ????????????? ??????????? ?? P (??????????????). ??????? ???????, ??????????, ? ??????? ? x0 ? X ????? n ? ? ???????? ????? ??????????
? ???????????? ?????? ????? ? ????? ? ??? ?? ????????????. ? ????????, ???
?????????????? ????????? ????????? xn ? ???????????? ???????? n, ?????????
????????? x0 ????? µ-????????????? [61]. ????? ???????, x0 ? xn ???????????
?????????????? ???????????? (??. ????? 2).
1.2.6
???????? ????
?? ???? ??????????? ? ??????????? ????????? ???????? ??????????? ?????? ?
d-?????? ????????????? ?????????, ???????????? ?? ????????? ?????????????? ?????. ??????, ???????????? ???????????? ????????? ?? ?????????? ????????, ? ??????? ????????? ??????? ???????????? ???????? (????????) ???????????????????. ????????????? ????????? ???????? ?????? ???????? ????????? ???????? ??? ?????????? ?????????.
? 1998 ????????? (Waelbroeck) ? ??????? (Zertuche) [83] ?????????? ??????
22
??????????? ????? ??? ???????? ??????. ?????????? ???????????? ?????????
? = {?|? ? Z?2 } ,
Z2 = {0, 1} .
????????? ??????? ? ? ? ?????? ??????????????????? ???????? (?????)
? = ?(1)?(2) . . . ?(i) . . . ?(n).
???????????? ????? ??? ???????? ?????? ???????? ?????????? ??????????
dH (?, ?0 ) ?
n
X
?(i) ? ?0 (i) ,
i=1
?? ???? ????? ???, ??????? ?? ????????? ? ??????? ? ? ?0 . ??????, ? ???????
n ? ? (??? ??????????? ?????) ?????????? ?????????? ?? ????? ????????
????????? ???????????? ?. ??? ??????????? ?????? ?????? ?????? ????
Nn (?) = ?0 ? ?|?(i) = ?0 (i), ?i < n ,
??? n = 1, 2, 3 . . .. ?????, ??????????? ????? ????? ???????? ? Rd ?? ?:
??????????? 3 (???????? ????, [83]). ????? ?????? ?????????? ?????????
A ? ? ? ??????????? f : A ? A. ???????? ??????? hA, f i ?????????? ???????????, ???? ????????? ??? ???????:
1) ??????? f ???????? ????????????? ???????????? ?? ????????? A, ??
????
??? ????? ???????? ??????????? U, V ? A ?????????? n ? Z ?????, ???
f n (U ) ? V 6= ? (???. 1.6-b)2 .
2) ??????? f ???????? ?????????????? ? ????????? ???????? ?? ????????? A, ?? ???? ??? ????? ?????? ? ? A ? ????????? Nm(?) ??????????
n, k ? N ? ?0 ? Nm (?) ? A , ????? ??? f k (?0 ) ?
/ Nn f k (?) (???. 1.6-a).
????? ???????, ??? ?????????? ???????? ?????? ??????????? ??????? ????? ???? ?????????? ?? ???????? ? ????????????. ??? ?? ????? ?????? ??????? ?????????? ????????, ???????????? ??????????, ????????????, ??????????
? ?. ?. ? ????? 3 ?? ?????? ?? ????????, ??? ???????????? ????????????? ?????
??????????????? ??? ????????? ????? ? ???????????? ?????? ?????????.
1.3
???????????
?? ??????????? ????????? ??????? ?? ???????????? ? ??????????? ????????.
???????????? ????????????? (????? ??????????, ??????????????? ??????????) ????? ????????????? ??? ???????????? ???????, ?????????????? ?????????????? ?????????? (????. 1.1).
2
???? n < 0 ? ??????? f ?? ????? ????????, ?? ??????? f n (U ) = {? ? A|f ?n (?) ? U }.
23
???. 1.7. ?????? ??????? ????????? ??????????? ? ????????????????? ??????.
??????????? ??????? ????? ????? ??????? ??????????? ???????, ??? ?????
??????????? ?????????? ??????? (?????). ? ????????????????? ???????? ????????? ???????????? ??? ???????????? ? ????????????, ????? ????????????
(??????).
??????? 1.1. ??????????? ????? ????????? ???????? ? ?????? ????? ? ????????????
????????????
?????? ?????
??????????? ???????
????????????????? ???????
? ?????????? ??????????????
? ?????????? ??????????????
? ???????? ????? ?????????
? ??????????? ????? ?????????
? ??????????? ????? ????????
? ???????? ????? ????????
????????? ?????????
???????? ?????
?????????????? ?????????
??????????
????????? ??????? ? ?????????
????
??????????????? ????????????? ??????- ???????????
???? ? ????????? ?????????
???????????????? ? ????????? ??????- ??????????
?? ? ??????????, ??????????
24
????? ????????????, ??? ????????? ???????? ??????????? ?????? (???????????????? ??????????? ??????????, ????????????, ??????????) ???????? ????????? ? ???????????? (? ?????????, ??? ?????????? ????? ???? ??????????). ? ????? 2, ?? ???????? ?????????? ??? ????????, ????????? ??????? ?????? ????????? ? ?????? ???????????.
? ????? ?????? ???????? ? ???????? ????????, ????? ????????????? ? ??????? ????? ?????????? ??????????????? ????????:
1) ???????????? ??????? ?????? ????????? ????? ???????????? ?????????????? (n < ?), ? ?? ????? ??? ?????? ????? (???????????? ? ???????????)
??????? ??????????????? ????????? ??????? (n ? ?).
2) ???????????? ??????????? ??????? ???????????? ????????? ????????
(??????????) ???????? ????????????, ??????? ????? ????? ??????? ??????????? (?? ???? ???????? ?????????). ? ????????????, ?? ????????
???????????? ??? ????????? ?????????? ??????????? ?????????? (???
?????? ??????? ??????????? ???????????????) ? ???????? ? ?????????????? ? ?????? ????????????? (???. 1.7).
3) ?????, ??? ? ???????????? ???????????? ??????????????? ??????? ?
???????? ?????? ?????????, ? ???????????? ????????? ??????????? ??????? ?????????? ?? ??????????? ????????? ??????????? ??? ??????????
????????. ????? ???????, ??? ?????? ?????, ????????????? ?? ?????????? ???????? ?????????????. ????????? ????? ????????????? ?????
(???????????) ? ?? ?????????? ? ???????????? ????? ??????????? ? ????? 3.
25
????? 2
???????????, ?????????, ????
??????? ???????????, ?????????????????, ????????? ? ???????? ???????? ?????????????? ??????? ????????????. ????? ???????, ??? ???????? ????? ????????????? (????????, ???? ?????????? ??? ?????? ??????) ???????? ? ?????????? ?????? ??????????????, ??????? ???? ?? ? ?????? ??????? ?????????????
??? ???????? ???????????.
????????? ????? ???????? ? ????????? ??? ??????? ?? ?????????? ??????????? ???????. ??????? ????? ???????? ?????????? ?????????? ????????????????? ??????????????????? ?? ???? ??????????? ? ??????????? ???????.
2.1
???????????? ?????
??? ????????????????? ???????? ????? ???????? ????????? ?????? ????????????? ? ????????????? (??????????????? ?????????, ????) ??? ?????????
?????????????????? ?? ????????? (??????????). ???????? ?? ????????, ?????????????? ????? ???????????????? ??? ??? «???????????????», «?????????»,
«???????». ??? ?????????? ?? ????? ??????????? ????? ??????? ??? ???????
? ??????????? ?????????
????????? ???????????? (perfect security) ??????? ????? ????? ?????? ?
??? ??????, ???? ?? ????????? ????????????? ??? ???????? ???????????
(???????????????). ??? ?????????????, ??? ??? ????????? ?????? (?????????)
????????????? ? ?? ??????? ?? ?????????? ?????????. ??????? ???????, ?????????????????? ????????? ??????????????? ??????????? ??????? ?????????????
??????????? ? ?? ????? ?????????? (?????????). ??????? ?????????? ????????????????? ???????????? ???????? ???????????. ??? ??, ??????? ?????????
?????????????????? ????? ?????????? ????? ?????. ?????????? ?????? ???? ????? ???? ??????????? ???????, ? ??????? ??????????? ???????? ???????
26
???. 2.1. ???????? ???????????, ?????????????????, ??????????????? ??????????? ? ????????????? ?????? ???????.
(????????, ????????? ??????? ? ????????? ?????).
? ???????? ????, ????????????????? ??????? ???????????? ????????? ???????????? ????????????, ??????? ? ???????????? ??????? ??????, ??? ????????? (? ???? ???????????????? ? ????????????? ????????????????). ??????? ??????????? ? ????????????????? ?????????? ?????????????? ?? ????????????????? ? ?????????????? (??????????????) ?????????????????. ??????????????? ?????? ?? ????? ???? ??????? ?? ??????? ?????????? ???????
??? ?????? ????????? ?????????????? ??????? ???????? ???????????. ??????????, ????????? ????????????? ???????????????? ??????? ?? ????? ????
??????????? ??????????????? ?????????? ???????????. ????? ????????, ???
??????????????? ??????, ???????? ????????????? ???????????????.
?????? ? ?????????????? ???????? ??????? ?? ????? ????????????? ??????????????? ?????????. ?????????? ????????? ????????????? ??????? ?????????????????. ?????? ?????????? ?????????????? ?????????, ???? ??????
????? ???????? ???????????? ????????? (????? ???????????? ??????), ??????? ??? ?????????, ?? ?????? ??????? ??????? (????? ??????????????????). ??
???????????, ?????????????? ????????? ?????? ?????????, ??? ?? ????????
???????? ???????????? ? ?????????.
???????, ??????? ????????? ?????? ???????? ?????????????? ????????? ?
??????????????? (???. 2.1). ??????, ??????? ????????????????? ? ??????????????? ??????????? ???????????: ??????????????? ?????? ????????? ?????????? ???????????, ?? ??????? ??????????? ?? ????? ????????? ???? ?????????
27
???. 2.2. ????? ?????????????????
? ??????????? ??????????????????. ??????? ???????, ??? ??????????? ??????????????? ?????????????????? ?????? ????????, ? ??? ??????????????? ?
????????????? ??????????. ? ?????? ???????, ?????? ?????????????, ??? ?????????????? ????????? ?????????????????? ?????????????? ??? ?????????????
??????????????. ?????????????? ????????? ?????? ????? ???? ?????????? ???
?????? ????????????? ??????.
?????????????????? ?????????? ?????????????????, ???????? «??????????
???????????????», ?? ???? ????? ?????????????? ??????? ?????? ? ???????????
??????????? ?? ???????. ????? ????? ????? ??????????? ?????????? ???????????? ????????? ????????????? ?????????, ??????? ?????????????, ????????, ??????? ? ????????, ?????? ??? ????????????. ??????????????? ???????????? ?? ????? ???. 2.2 (?? ???? ????? ????????????????? ??? ???????????) ????? ??????? ????? ???????? ??? ???????? (?????????-??????????????
??????) ? ??????????????? ????????? (?????????-??????????? ??????). ???????????? ???????? H ?????????? ??????? ?????? ???????? ? ???????. ???????? ???????????? ?????? ????????? ??????? (?????? ??????????? ??????????????????? ?????????) ? ???????? ??????????? ?? ???????????. ????????????
???????? ???? ???????? ??? ?????????? ????? ????????? ??????? ??????????? ????? ??? ?????? ?????????????. ????????? K, ????? ??????, ???? ?????
??????????? ?????????, ???????? ????????? ???????. ??????????, ???????,
??????????????? ???????? ?????????? ???????? ? ?????????, ????? «??????
??????????????». ??? ????????? ?????????????? ????? ????????, ??? ???????? ? ????????? ????????????? ???????.
????? ????? ?? ???? ????? (???. 2.2) ???????? ????????????????? ?????
???????????? ???? (????????, ???????, ?????????) ???????? ????????????
????????????, ???????????? ?????????? ????????? ? ??????????? ??????????
«??????? ???????????? ???????». ??? ?? ?????, ?? ???? ??????????????? ??-
28
?????? ????? ?????? ??????????? ??????, ??? ? «?????? ?????????» ???????
???????????????? ????????. ??????????? ??????????? ??????? ?? ????? ?????????????? ? ??????????, ??? ??? ??? ?? ??????????????. ? ?????? ???????, ????????? ?????? (??? ??????????? ???????) ??? ?????? «?????????????»
????? (????????, ?????????? ??? ? ???????? ????? ??????????) ?????? ???????????? ??? ???????.
????????????????? ????, ? ??????? ??? ??? ???? ? ??????? 1.2.2 ? ??????? ?? ?????????? ????????? ? ??????????, ????? ????? ??????????? ?
???????????? ????????? ?????????. ????????, ????? ??????? «????? ????????????», ??? ???????????? ????, ?? ????? ?????????????? ?????????. ??? ??????
??????????? ????? ?????? ?? ?????????? ???????? ???????????-????? (??????????????? ? ??????????? ???????? ? ??????????????? ??????????) ? ??????, ??? ????????????????? ???? ????? ????????? ?????????????? ?????????
??????????????????. ????? ????, ? ??????????? ???????, ??????? xn , xn+k , xn+2k , xn+3k . . .
???????? ?????????????? (k ? ?) ?????????, ?? ???? ? ??????????? k ?????
??????? ????? ??? ????? ????????.
2.2
2.2.1
?????????-??????????? ??????
?????????????? ?????? ????????
????? ???????????? ?????????? ????????? ?? ?????? ?????????????? ????????? [5, 66, 16]. ??????? ?????? ???????? 1 ??????? ?? (1) ???????????????
?????, (2) ??????????? ??????? ? (3) ????? ?????????? ? ???????? ??????
?????????. ????????? ?????? ???
T = hS, A, ?, F, q0 i ,
??? S ? ???????? ????????? ?????????; A ? ???????? ??????? ????? (? ????? ??????, A = {0, 1}); ? ? ???????? ????????? ?????? ???? ? : S Ч A ?
S Ч A Ч {L, N, R}; F ? S ? ????????? ?????????????? ?????????; ? q0 ? S
? ????????? ?????????. ????????? {L, N, R} ???????? ??????????? ???????
??? ??????????? ???????: ????? (L), ?? ????? (N ) ? ?????? (P ). ?????????????
?????? T ?????????? ?????? hs, ?, ii, ??? s ? S ? ??????? ????????? ??????,
? ? A? ? ?????? ?? ?????, ? 1 ? i ? |?| ? ??????? ??????? ?? ?????, ????????????? ? ?????? ????? ?????.
????????????? ?????? ?????????? ????????? ???????: (1) «????????»
??????? ?????? ? ? A? ? ???????? ?????; (2) ??????????? ??????? ? ?????? ????? ?????????; ? (3) ????????? ?????????? ????????? s = q. ?? ???? ???? ??????,
1
??????, ???? ??????? (1912?1954) ? ?????????? ?????????.
29
? ???????????? ? ????????? ?, ?????? ????????: (1) ???????? ??????? ????????? s; (2) ???????? ?????? ?????, ???????, ?? ??? ??? ???? ????????; (3) ???????? ??????? ?????? ??? ???????. ???????, ??? ?????? ?????????? ?????? ?, ????
?????????? ????? ?????????????????? ?????? ?1 , ?2 , . . . , ?i , . . . , ?m , ?i ? ? (???
m ? ????? ?????? ??????), ??????? ????????? ?????? ?? ?????????? ????????? s0 ? ?????????? ?????????????? ????????? s ? F . ?????? ?? ??????????
??????, ???? ??? ??????? ?? ????????? ? ?????????? ?????????????? ?????????
(???? ??????????????? ? s ?
/ F , ???? ?????????????).
??????? ?????? ?????? ???????? ????? ???? ????????? ?????????? ?????????, ????????: (1) ??????????????? ????? ?????????? ?? ?????, ??????????? ? ???? ??????; (2) ?????????? ????? ?????????? ?? n-?????? ???. ?????
????????, ??? ??? ??????????? ?????? ????? ???? ???????? ?????????????
???????.
?????? L ?????????? ????????? ????? (????) ???????? ????? ?? ????????
A. ???????, ??? ?????? ?????????? ???? L, ???? ??? ?????????? ??? ????? ? ? L
? ?? ?????????? ? ?
/ L.
????????????????? ?????? ???????? ????? ??????????? ??????? ???????? ? : S Ч A ? S Ч A Ч {L, N, R}, ?? ???? ?? ?????????? ???? ?????? ? ?????????? ????? ?????? S Ч A. ????????, ??????????????????? ?????? ????? ?????
????????????? ??????? (????????? ?????????? ?????????? ????????).
???? ?????????? ??????? p (l), ??????? ???????????? ?????? ????? ??????
?????? (m < p (l)) ? ??????????? ?? ??????? ?????? ????? l (??? ???? ?????????? ??????? l), ?? ?????? ???????? ??????????????. ?????, ??????????????
??????????????? ?????????????????? ???????? ????????, ???????? ?????
P, ? ?????, ?????????????? ??????????????? ???????????????????? ???????? ? ????? NP.
????????????? ?????? ? ??? ????????????????? ?????? ????????, ?????????? ?????????????? ??????, ?? ??????? ???????????? ????????? ?????. ??????????? ??????, ?????? ????? ??????????? ???????????? ?????? ? ?????????
?? ??? ???? ???????? ? ??????????? ?? ?????????? ??????????. ?????????????
?????? ???????? ?????????? ???? L, ???? ??? ?????? ?????????? ????? (« 1 ?
??????????» ??? «0 ? ?? ??????????») ? ???????????? ????? ??? 2/3, ??? ??????????? ??????? ? ???????????? ? ??????????? ??????? ????????????? ?????????
???? ?????????? ?????.
????? BPP ???????? ?????, ?????????????? ?????????????? ????????
???????? ? ?????????????? ???????????? ?? ????? ??????.
?????? ?????????????? ?????, ?????? ????????, ????? ????????? ? ? ????
?????????? (??? ???? ???????? ?????? ???????????? ?? ?????). ????? ???????,
????????? (???????????? ??????) ???????? ?????????? ??????????, ? ?????????
30
???????????? ?????? ?????? ??? ???????? ??????????????????.
2.2.2
??????????????? ?????????
? 1964 ???? ?????? ?????????? ?????????? ????????? ?????????? ??????????????? ????????? ???????? ?????????????????? ??? ????? ?????????? ????????? ??? ????????????? ?????? ????????, ????????? ???????????? ??? ?????? (? ?????? ?? ????????????? ? ????????? ?????????? ? ????? ????????????
?????? ?.?????? ? ?.?????????).
??????????? 4. ??????????????? ????????? KM (?) ???????? ?????????????????? (??????) ? ? {0, 1}n ?? ????????? ? ?????? ???????? M ???? ????? l(?)
????? ????????? ????????? ?, ??????? ????????? ??? ??????????????????, ??
????
KM (?) = min l(?).
?:M (?)=?
?????????? ???????, ??? ?????????? ????????????? ?????? ???????? U ,
??????? ???????????? ??????????, ????????????? ? ?? ???????????? ??????
M , ?????? ????????? ????????? ?, ??????????? ??? ?? ?????? ?? U , ???????
?? M ? ?? ??????? ?? ?. ?????????????, ??????????????? ????????? KM ??
????????? ? ????? ?????? M ??????? ?? ?????????? ????????? KU (S) ??
????????????? ?????? U ????????????
KU (S) ? KA (S) + CA ,
(2.1)
??? CM ? ????????? ?????????, ??????????? ?? ? [24]. ????? ???????, ? ?????????? ???????????? ????? ???????? ???????? ? ?????????? ??????, ???????
K(?) = KU (?).
? ?????????, ?????? ?????????? ????????? ? ??????????? ????? (???
?????????????? ????, ??? ?????????, ?????? ?????????, ?? ??????????) ??????????? ???? ??????????? ????????????. ??? ?? ????? ????????????? ?????????? ?????? ??????????? ????? ?????. ????????? ?? ??????????? ??????????
?????? ?????? ? ????????? ?????? ??????.
2.2.3
c-??????????? ? ??????????????? ???????????
?????? ?n ????? n ?????????? ??? ????????? ????????? c (c-??????????),
???? K(?n ) ? n ? c. ??????????? ?????? (c = 0 ??? ????) ?????????? ?????????????? ???????????????? ??? ?????????????? ??????????.
31
2.2.4
???????????? ?????????
??? ??????????? ?????? ?? (??? ???????????????? ??????????) ????????? ??????????? ???????????? ?????????, ?? ???? ??????
c(?? ) = lim
n??
K(?n )
.
n
(2.2)
? ???? (2.1) ???????????? ????????? c(?? ) ??????????? ???????????? ?????? ?????????????? ??????. ????????, ??? ??? ???????? ????????? K(?? ) (????????, ??? ???????????????? ??????????), c ???????????? ? ????. ??? ???????
????????? ??????????????????, ????? ????????? ????? ????? ??????, ?????????????, c = 1. ?????? ??????, c > 0 ?????? ? ??? ??????, ???? ? ?????????
?????????? ??????????. ? ??????????? ??????? ??? ?????????? ?????, ?????, ???? ????????? ????????? ??????? ?????????? ?????? (??? ?????????????????
?????????), ???? ????????? ??????????? ???????? ?? ??? ? ???????? ?????? ??????????.
2.3
?????????-?????????????? ??????
?????????????? ????????????? ????????????? ??? ????????? ???????? ??????????. ? ???????? ?????????????, ?? ?????????? ? ?????????????? ????????
??????????? ? ???????? ???????????? ????????????????? ???????? (??????,
??? ?????????). ? ????????? ??????????????, ?????????? ?? ?????????? ??
????????? ?????????????????? ? ?? ???????? ??????? ???????? ??????????
??? ???????????????.
?????????? ??? ????????? ??????? ? ??????????????? ??????? ???????????????????. ? ?????? ?????????? [78] ?? ??????? ? ?????????????? ?????????
???? ???????????????????, ??????????? ?????????? (???????????).
????????, ?????? ??????, ??????? ?????????????? ???????? ????? ?????????? ?????????????????? (??????). ?? ?????? ? ?????? ??????????????? ?????????, ?????????? ? ?????????? ???????.
? ?????? ???????????? ????????????? ??? ??????? ??????????? ??????????????.
2.3.1
???????? ???????????
????????? ????????????? (??) ????????? ?????? ? ?? ????????? ?????????
???????
L = {?j }, ?j ? {0, 1}? ???? ??????? Pr : L ? [0, 1] ??? ???????
P
??L Pr (?) = 1. ??? ????????? ????? L, ????????? ????????????? ?????? ??-
32
?????? ?????????? ???????? Pr (?j ), ??????? ???????????????? ??? ??????????? ????????? ?????? ?j .
??????????? 5. ?????????????????? ? ?????????? ??????? ????????? ???
???????????????, ???? ??? ????? ????? n > 0 ? ??? ????? ???????? ?n , ?n ? ?,
??????????? Pr(?n ) = Pr(?n ).
?????? ????????? ??????? ????????? ?????????????????? ???????? ??????
?????????? ??????????, ?? ???? ??? ?????? ??????? si ? ?, ???????? ??????????? Pr(si |si?1 , si?2 , . . .) = Pr(si ). ??????? ???????, ????? ?????? ??????? ?????? ? ?????????? ????????, ?? ????? ???????? ??????????? ????????? ???????????? ?????????? ???????.
2.3.2
???????? ???????
???? ?????? ??????? ??????? ????????, ????????????? ????????? ? ?????????????, ?? ??????????? ?????? ? ?????? ???????? ? ????????? ?????????? [78].
???????? ???????? ????? ?????????? ??????????, ??????????? ??? ???????????? ??????????? ????????? ??????? ????? ???? ?????????. ??????? ???????,
???????? ???????? ????? ?????? ???????? ? ???????. ? ????????????? ???????????? ??? ?????????? ??????? ???????????????? ????????????? ??? ????????
???????????.
???????? n-??????? ?????????????????? ?n ?????????? ???
X
Hn = ?
(2.3)
n Pr (?n ) log Pr (?n ),
??{0,1}
??? Pr : {0, 1}n ? [0, 1] ? ??????? ????????? ????????????? ? ?? ?????????
n-??????? ?????. ???????? ???????? Hn ???????????, ????? Pr (?n ) ????????
??????????? ?????????? ????????????? (?? ???? ?????? ?n ??????? ????????).
???????? ???????? hn ?????????? ??????? ?????????? ??????????, ??????????? ? (n + 1)-?? ????????, ??? ???????, ??? n ?????????? ??????:
Hn+1 ? Hn , n ? 1
hn = hn+1|n =
H1 ,
n=1
??????? ???????, hn ????????????? ??????? ???????????????? ??? ???????????? (n + 1)-??? ???????. ??? ??? ?????? ? ?????????? ???????? (??????????
???????) ?? ????? ????????? ???????????????? ????????, ??????? Hn ?? ??????? ? hn+1 ? hn .
??? ????????????? ????????? ??????????, ?????????? ??????
hSh = lim hn = lim
n??
n??
33
Hn
.
n
(2.4)
? ??????, ???? ?????????????????? ? ?????? ?????????? ????????? k-???
???????, ?? hn = hSh ??? ???? n ? k. ?????????? ?????????????????? k-???
??????? ??????????????? ???, ??? ??????? (i-??) ?????? ??????? ?????? ?? k
?????????? ????????, ?? ????
Pr(si |si?1 , si?2 , . . .) = Pr(si |si?1 , si?2 , . . . , si?k ),
2.3.3
si ? ?.
??????????? ???????? ? ?????????
?????????? ???????, ??? ??? ???? ???????? ???????, ??? ??????? ??????
???? ?? ?????????? ??????????. ????????? ??????? ???????????? ???????? «?????????? ?????????» ???????. ????????? ?????? ???? ????????? ???? ?????????????????? ????????. ????????, ???, ??? ?????? ????????? ????????? ???????
? ??????????? ??????, ??? ?????? ????????? ? ??????? ??????????????????.
??????? ?????????????? ???????? ???? ??????????????????, ?? ????? ?????????? ???????? ??????? ? ??????? ?? ?????????????????. ????? ???????, ????????? ? ???????? ?????????????, ??? ?????????????????.
????? ?????????????? ???????? ????? ?????????????????? ????????? ? ??????????? ?????????? ???? ???????????????????, ??????????? ??????????? (??
???? ??????? ?????????), ?? ????? ???????? ? ?????????????? ????????? ???????? ? ?????????.
????? ????????, ???
1
hKn i
=
,
(2.5)
lim
n?? Hn
ln 2
P
??? hKn i =
?n ?{0,1}n Pr(?n )K(?n ). ????? ??????? ??????? ????????? hKn i
?????????????? ??????????????? ???????? ??????? ? ????????????? ln 2.
?????????, ??? ????????? ????? ???????? ?? ??????? ???????-??????????
[29].
2.4
2.4.1
???????? ? ????????? ??????????? ??????
????????? ???????????? ?????????
? ?????????? ????????
?????????? ??????????? ??????? S = hX, f i c f -???????????? ?????????????
????? µ (??. ?????? 1.2). ????? ?????? ????????? ? ???????????? ????????? X
?? m ????????????????? ???????????, ?? ????
? = {X1 , X2 , ..., Xm } :
i=m
[
Xi = X,
i=1
34
Xi ? Xj = ?, ?i 6= j.
??????? ???????????? Xi ????????????? ?????????? ?????????????, ?????? si ? A. ??????? ? ?????? ????????? ? ? ?????????? ???????? ????????:
? (x) = {si ? A|x ? Xi }.
?????????? ?(x0 ), ??????? ????? ????????? ???????????? Xi , ????????? ?????????? ?????????? ? = {sk }. ????????? ????????? ???????, ?????????????
?????? ? ???? ?? ???????????? ???????? ? ????????? ?????????? ??????????? (??????? ????? ? ?????? ?????????). ?????, ????????? ????????? ?????????? ????? ? ???????????? ???????? ? ???????? ??????????, ??????????
?????????? ?????????.
2.4.2
???????? ???????????-?????
?????????? ?????????? ???????? (?????? 1.2.3) ???? ?????? ??????????????
?????????? ? ???, ??? ?????? ?? ?????? ??????????? ????????????? ????????? ??????? ? ???????? ???????. ? ???? ??????, ????? ???????? ?????? ?????
???? ???????? ???????????-????? hKS [9]. ???????? hKS ????????? ?????????? (???????? ?????????) ? ??????? ?? ????? ????????? ?? ????????.
????? ????????? ? = {X1 , X2 , ..., Xm } ?????? ??????????? ????????? ???????????. ??????? ??????? ????????? x, ??????????? ????? ?????????? ?????? ??? ???? ??? x ? Xi ., ?????? ?(Xi ) : x ? Xi .
???????? n-?????????? ?????????? ?n ? An ?? ????????? ? ??????
X
Hn? = ?
Pr (?n ) log|A| Pr (?n ),
?n
??? Pr (?n ) ? ??????????? ????????? ?????????? ????????? ?n . ???????? ???????? (n + 1)-??? ??????? (??? ????????? ?????????????? ?????????? ?n ) ?????
(
?
Hn+1
? Hn? , n ? 1
?
h?n = hn+1|n =
?
H1 ,
n=1
???????? ????????? ? ??????
1 ?
H .
n?? n n
h? = lim h?n = lim
n??
???????? ???????????-????? ???? ?????? ??????? ??????? h? ?? ?????????
???? ????????? ?????????
(2.6)
hKS = sup h? .
?
35
???. 2.3. ??????????? ???????? ?? ?????????
???????? hKS ????? ???? ??? ?????????? ??????, ???????????? ? ??????? ??? ??? ?????????????????? ????? ? ?????????? ??? ?????????
????????.
P
???????? hKS ??????? ? ???????????? ???????? (hKS =
1?d?D ?d ) ? ??????????????? ????????? ??????? T , ?? ??????? ????? ??????????? ?????????
??????????? ??????? [29].
2.4.3
????????? ??????????
????????? ?????????? ? ??????? ? x1 ??? ????????? ????????? ????????? ?
?????????? ???
1
C ? (x1 ) = lim sup
min K(?n ),
n?? n ?n ?[?(x)]n
??? [?(x)]n = ?n |f j?1 (x1 ) ? Xj ? K(?n ) ? ??????????????? ????????? ?????????? ??????.
????????? ?????????? ? ??????? ? x1 ????
C(x1 ) = sup C ? (x1 )
?
.
??????????? 6. ?????????? ? ??????? ? x1 ?????????? ?????????????? ?????????, ???? ??? ????? ????????????? ?????????
c(x1 ) > 0
.
36
??????? ?.?????? ? ?.????? ?????????? ??????????? ???????? ?? ????????? (???. 2.3):
??????? 1. ??????????????? ??????????? ??????????, [29, 58]) ????? (?
?????? ???? µ) ??? ???? x ? X, ?????????? ?????????? ?????????????? ???????? ? ?? ????????? ??????
c(x) =
hKS
,
ln 2
(2.7)
????, ???????? ?? ??, ??? ?????????? ??????????????? ??????????? ???????? ?????? ??????????? ??????????, ????? ??? ?????????? ?????? ?????????
????????, ??????????? ???????????? ?????????, ?????????????? ????????.
??????????????? ??????????? ?? ???????? ??????????? ???????? ??? ?????????????????. ???? ???? ?? ?????????? ?????????????????? ?????????, ????????????? ??????????????????, ???????? ?????????? ????????????? ??????, ??????? ????????????? ????????? ? ??????? ???????????? ??????, ??? ?????????
?????. ?????????, ?????? ?????????????? ????????????????? ? ?????????
???????.
2.5
2.5.1
?????????????????
????????????? ????????
?????????? ????????????? ???????? ? = {Pri }i?N , ??? Pri ? ????????? ????????????? ????? ?? ????????? {0, 1}l(i) , l(i) ? ????????? ???????, ????????
????? ??????, ? i = {1, 2, . . .}. ???????? ??????????? ????????????? ?0 =
{Pr0,i }i?N ??? ?????? i ? N ? ????? ?, ? ? {0, 1}i ????????????? ?????????
Pr0,i (?) = Pr0,i (?).
??? ?????? «??????? ???????????» ???????????? ??????????????????, ?????????? ???????? ?? ????????????? ???????? ? ????????? ??????????? ?????????????. ??????, ?? ????????, ?????????? ??? ???????????? ??????? ?????????????????? ????????????? ??????. ??????? ???????? ??????? ?????????????? ?????????????. ????????????? ???????? ????????????? ???????????, ???? ??? ??????????? ?????????????? ?????????? ??????????? ???? ???????????????????, ??????? ????? ?????????? ?????????? ?????????????? ???????
????????:
??????????? 7 (?????????????? ?????????????, [89, 46, 58]). ????? ??????
????????????? ???????? ?1 = {Pr1,i }i?N ? ?2 = {Pr2,i }i?N , ???????????????
?????????? N. ?????????? ????????????? ?????????????? ?????? T , ?????
?????????? ??????. ?? ???? ???????? ????: ?????? i ? ?????? ?. ?????????
PrT1 (i) ??????????? ????, ??? ??? ??????????? ?? ???? ??????? i ? ?????? ?
37
? ???????????? ? ?????????????? Pr1,i , ???? T ?????? 1. ??????????, PrT2 (i)
???? ??????????? ????, ??? ??? ??????????? ?? ???? ??????? i ? ?????? ? ?
???????????? ? ?????????????? Pr2,i , ???? T ?????? 1. ????? ???????? ?1 ?
?2 ?? ???????? ????????? p(i), ???? ??? ???? ?????????????? ?????? T ?
??c????? ???????? i ? N ??????????? ???????????
T
Pr1 (i) ? PrT2 (i) < 1 .
p(i)
??????????? 8 (?????????????????, [89, 46, 58]). ????????????? ????????
? = {Pri }i?N ?????????? ???????????????, ???? ??? ?????? ??????????????
???????? p(i), ? ?? ??????? ?? ???????? ??????????? ????????????? ?0 =
{Pr0,i }i?N .
??????????? 9 (??????????????? ????????????? ????????, [89, 46, 58]). ?????
????? ????????????? ???????? ? = {Pr1,i }i?N . ????? ????????????? ?????????????? ?????? T ???????? ?? ????? ?????? i ? ?????? ?, ? ?????? ???? ???,
?????????? ????????. ????? ??????? bit (?, r) ?????????? r-? ??? ?????????????????? ?, ? pref (?, r) ?????????? ??????? ?? r ???, ?? ???? pref (?, r) =
bit(?, 1) bit(?, 2) . . . bit(?, r). ???????, ??? ?????? T ????????????? ?????????
??? ?, ???? ??? ????????? ???????? p(i) ? ?????? i,
Pr (M (i, pref (?, r)) = bit(?, r + 1)) ?
1
1
+
2 p(i)
??? ?????? ? ?????????? ???????? ? ???????????? ? Pr1,i , a ????? r ? ? ???????????? ? ??????????? ?????????????? ?? ????????? {0, 1, . . . , l (?) ? 1}. ???????,
??? ???????? ? ?????????????, ???? ?? ?????????? ????????????? ?????????????? ?????? M , ??????? ????????????? ????????? ??? ?.
??????? 2. [28, 46, 58] ????????????? ???????? ? ????????????? ????? ?
?????? ?????, ????? ? ?????????????.
2.5.2
????????????? ???????
????????????? ??????? ? ?????? ?????? ????????????????? ??????. ???????????, ????????????? ???????? ?????????? ???????, ??????? ?????? ??????????? ? ?????? ??????????? (? = f (?)), ?? ?? ????? ???????????? ?????????
????????? ?????????????? ?. ?. ?????????????? (? = f ?1 (?)). ?????? ?????
?????????? ??????? ? ????????? ?????????????? ?????????? ????????????????? ????????????? ????????????? ???????.
???????, ??? ????????????? ??????? ????????? ????? (???????????? 1 : 1),
???? ??????? ????? ???????? ??????? ????? ??????? ????? ?????????. ?????
38
??????? ????????????, ????????, ? ??????????????? ???????????. ???? ??????? ????? ???????? ????????????? ??????? ????????? ??? ????? ????? ?????????, ?? ??? ?????????? ???-????????. ???, ???-??????? ???????????? ???
???????? ??????? ??? ???????? ??????????? ???????.
??????????? 10 (???????????? ???????). ??????? f : {0, 1}? ? {0, 1}? ?????????? ?????????????, ????
1) ?????????? ????????????????? ?????????????? ?????? ????????, ??????? ?????? ?? ?????? f (?) ??? ??????????? ?? ???? ?;
2) ??? ????? ????????????? ?????????????? ?????? M , ??? ?????? ???????? p(n) ? ?????????? ???????? n ? N
Pr(M (f (?), 1n ) ? f ? 1(?)) <
1
,
p(n)
??? ?????? ? ?????????? ????????? ??????? ?? ????????? {0, 1}n ? ???????????? ? ??????????? ??????? ?????????????. ???????? 1n ???????????? ????? ?????? ?????? M ????????? ?? ????? ???????? ?????????.
?????? ????????? ?????????? ???????????????? ?????????? ???????? ??????? ???? (hard-core) [28, 46, 58]. ???????? b ??????? f (?) ?????????? ???????
?????, ???? ?? ????? ???????????, ?? ?????? ??????????? ?? f(x).
??????????? 11 (??????? ????). ????? f : {0, 1}? ? {0, 1}? ? f : {0, 1}? ?
{0, 1}. ???????? b ?????????? ??????? ????? ??????? f , ????
1) ?????????? ????????????????? ?????????????? ?????? ????????, ??????? ?????? ?? ?????? b(?) ??? ??????????? ?? ???? ?;
2) ??? ????? ????????????? ?????????????? ?????? ???????? M , ???
?????? ?????????????? ???????? p(n) ? ?????????? ???????? n ? N
Pr(M (f (?), 1n ) = b(?))) <
1
1
+
,
2 p(n)
??? ?????? ? ?????????? ????????? ??????? ?? ????????? {0, 1}n ? ???????????? ? ??????????? ??????? ?????????????.
??????? 3. (????????????? ???????? ????, [89, 65, 46]) ???? ?????????? ????????????? ???????, ?? ?????????? ???????????? ??????? ? ??????? ?????.
2.5.3
??????????????? ?????????
??????????????? ???? ??????????????? ??????????? ? ???????????? ???? ????????? ? ??????? 1.1.4. ???????????, ??????????????? ??????????? ?????????? ??????????? (?????????????????) ????????, ???????, ???????? ?? ?????
???????? ?????????????????? (????), ? ????????????? ????? ??????? (??????
??????????? ????? ???????) ??????????????? ??????????????????.
39
??????????? 12 (??????????????? ?????????, [28, 46]). ????? ??????? l :
N ? N ????????????? ??????? l(n) > n ??? ???? n ? N. ???????????????
????????? ? ????????????? ???????? l(n) ???? ????????????????? ?????????????? ???????? G ?? ?????????? ??????????:
1) ??? ????? ? ? {0, 1}? ????? ????? ????????? |G (?)| = l (|?|)
p(n)
2) ????????????? ???????? ? = G (Prn0 ) ? ?0 ????????????? ??????????? ??? ???????????? ???????? n.
??????? 4. (?????????? ???????????????? ??????????, [89, 46]) ????? f ?
????????????? ???????, ??????????? ?????, ? ???????? b ? ??????? ???? f .
????? G(?) = b(?)b(f (?)) . . . b(f l(|?|)?1 (?)) ???? ??????????????? ????????? ?
????????????? ???????? l.
??????? 5. (????????????? ???????????????? ??????????, [54, 50, 46]) ??????????????? ?????????? ?????????? ????? ? ?????? ?????, ????? ??????????
????????????? ???????.
??????? ????????, ??? ??????????????????, ??????????? ???????????????
??????????? ????? ????? ?????? ?? ??????????? ????????? ?????????????, ??????, ??? ????? ????????????? ?? ???????? ?? ??????????? ?????????.
2.5.4
???????? ??????????????? ???????????
???????????? ??????? ???????????? ???????? ?????? ???????? ???????????, ????????? ???????????????? [57, 69, 74, 23]. ?? ?????????????? ???????????
???????????????? ??????????, ??????? ??????, ?????????? ????????? ????????? ?? ????????. ??????? «?????????» ????????????????? ?????????? ????????????????, ??? ?????? ?????? ??????, ?????????? ?????????? ?? ???????????? ?????????????. ???, ???????????? ???????? ?????????? ? ??????????
(NIST) ??? ??????????? 16 ??????. ??????? ???????? ?????? ?? ???:
??????????? ????. ?????????? ?????? ? ????? ? ?????????????????? ??????
???? ?????????????? ?????.
????????? ????. ????????? ????????????? ???????? m-??????? ?????? (?????,
m = 4) ?????? ???????? ??????????? (??????????? ? ??????? ????????????? ?2 ).
???? ????????. ???????? ????? ???????? ?????????, ????????? ?????? ?? ?????
??? ?????? ?? ?????? (0, 1, 00, 11, 000, 111, . . .). ????? ????? ???????? ?????? ??????????????? ????????? ??????????????????, ?? ???? ????? ???? ???????? ???????? ?????? ????? ????? 1 ???, ???? ???????? ?????? ?????
????? 2 ????, ???? ??????? ?????? ????? ????? 3 ???? ? ??? ?????.
????? ????? ???????????? ??? ????? ??? ?????? ????????????????? ??????????? ??????.
40
2.6
??????????????? ?????????
?? ???? ??????????? ???????
????? ???????????? ??????? hX, f i ???????? f -???????????? ?????????????
????? µ ? ???????? ??????????? ? ??????????? (??? ????????????? ????????????). ?????????? ????????? ???????????? ????????? X ?? ??? µ-??????????????
????????????????? ????????????, ?? ????
? = {X0 , X1 } :
µ(X0 ) = µ(X1 ) = 1/2,
X0 ? X 1 = ?
? ?????? ?????? ??????????? ???????, ????????? x ? X0 ????????????? ??????? «0», ? ????????? x ? X1 ? ??????? «1». ?????????? ????????? ??????????
??????? ?????????????????? ? ?? ?????????? ????????? (??????) x0 ? X. ????????? ?????????, ??? G : X ? {0, 1}? . ?????
G(x) = ? = {si }i=1,2,... ,
x ? X,
si ? {0, 1}.
?????????? (Szczepankski) ? ?????????? (Kotulski) [82, 61] ????????, ???
G ????? ?????????????? ??? ????????? ?????????????? ????????? ???????????????????.
????????? ??????? ??????????, ??? ?? ????????? ????????? ??????? ????????? ?????????? ????????? ?????????????????? ? ???????????? 1:
??????? 6. (???????????? ??????????, [82]) ??? ?????? ?????? x ? X,
µ G?1 (?) = 0
.
? ???? ????????????, ????? ????? ? ?????????????????? ????? ????? ?????? (?? ???? ????? ???????? ??????????? ????). ??????, ???????????? ???????
????????-??????? [9] ????? ???? ???????????? ? ????
n?1
Z
1X
?X0 dµ = µ(X0 ),
?X0 f i (x) =
n?? n
X0
lim
i=0
n?1
Z
1X
i
lim
?X1 f (x) =
?X1 dµ = µ(X1 ),
n?? n
X1
i=0
??? ?X0 , ?X1 ? ???????????? ??????? X0 ? X1 . ??? ??? µ(X0 ) = µ(X1 ) = 1/2,
?? ??????? ????? ????? ? ?????? ????????? ? n/2.
??????? 7. (????????????, [82]) ??? ?????? ?????? x ? X, ????? ?????? ?
????? ? ?????????????????? ? ?????????????? ?????.
41
xn+1
255
0
0
xn
255
???. 2.4. ???????????? ?????????????? ??? p = 1279 ? q = 255.
??????????? ???????? ???????????? ??????? ????????????? ??????????????? ????????????? ????? ??????????????????:
??????? 8. (??????????????? ?????????????, [82]) ??? ?????? ?????? x ?
X ? ?????? n = 1, 2, . . . ???????? ???? s(n?1)k ? snk (??????????????? ???
????????? ????????) ?????????????? ?????????? ? ??????????? k, ?? ????
lim µ f ?nk?k (X0 ) ? f ?nk (X1 ) = µ f ?nk (X0 ) · µ f ?nk (X1 )
k??
?
lim µ f ?nk?k (X1 ) ? f ?nk (X0 ) = µ f ?nk (X1 ) · µ f ?nk (X0 ) .
k??
????? ???????, ? ??????????? k, ?????????????????? ??????? ?????????????????? sk , s2k , . . . , snk , . . . ????? ????????? ? ??????-???????. ?????????? ??
k ?????????????? f ????????? ? ???? ???????????????? ???????: ?? ???? ????????? ????????????? ?????????? ??????????? ?????????????? (? ??????? ??????????) ???????????? xnk ?? x(n?1)k ?????????? ??? ??????? ? ???????????
k. ?????? ???????????? ??? ????? ???????????, ???? ??????????? ????????
?????????????? f ??????????.
????????? ???????????? ????????? ? = {X0 , X1 } ????????? ??????? ???????? ???? ? ??????????? ????????? ??????? (???????????) ? ????. «???????
????» ????? ???? ?????? ???????? (? ????? ????), ??? ????? ???????? ???? ?
???????.
??????
?????????? ???????????? ?????????????? (???. 2.4)
xn+1 = rxn mod q,
42
??? x0 ? [0, q] , r = p/q > 1, ? p ? q ????????????? ?????. ?????????????? ???????? ??????????? ??? ???? r ? ????? ? = hKS = log r > 0. ??????? ??????????
?????????????? ?????? ???????????? ? ??????? ????????????. ????????????
???????? ???????????? ????????? (Linear Congruental Generator, LCG) ?????
???????????? ????????
xn+1 = (Axn + C) mod M,
??? xn ? {0, 1, . . . , M } ? A, C, M ? ?????????????? ?????, ?????????? ????????????? [57]. ????? ???????? ????????? ???????? ????? ? ???????????? ? ??????:
? ???????? ??????????????, ????????? ??????? ??????? ?????? ?????????????
(???????????? ?? ??????? ??????, ????????, ????????????? ??? ??????????? ? ???????), ? ????? ????? ????????? ?? ????????? ?????????? ?????????
(???????? mod).
???????? ? ??????? ???????? ??????????? ?????????????????? {yn }?
1 ????????? ????????????? ??????? H : R ? [0, 1] ? ???????? 1. ?????, ????????,
H (x) = sin2 (?x). ????? ??????????????????
{yn }?
1 = {y1 = H(x1 ), y2 = H(x2 ), y3 = H(x3 ) . . .}
???? ???????? ??????????? [58]. ??????? H ?????? ???? ???????? ????, ???????
xi ? yi .
??? ??????? p ? q, ?????????????????? {yn }?
1 ?????????????? ? ???? ???:
??? ?????? yn ? {yi }?
???????????
??????????
????????
yn+1 ?????????? ???1
????????? ????? q ?????????, ? ??????????? ??????????? ???????? yn?1 ?????????? ???????????? ????? p ????????? [58].
???????? ??????? ?????????????????? ?? {yn }?
1 ????? ????? ????????? X
?? ??? ?????????????? ????????????. ????????? ??????? ?????????
0, x ? X0 = (0, 1/2]
?(x) =
1, x ? X1 = (1/2, 1)
????? ???????? ?????????????????? ??????????
s1 = ? (y1 ) ,
s2 = ? (y2 ) ,
s3 = ? (y3 ) , . . .
????? ???????, ??????? ??????????? ?????????????? f c ???????????? ???????????, ?????????? ?????????????? H ? ??????? ????????? ?, ?? ?????
??????? ??????????????? ??????????.
43
????? 3
???????????? ??????????
? ????? ??????????? ????? ????????????????? ??????, ??????????? ?? ???? ???????????? ????????????? ???????????? ? ????????? ????? (??? ???????????
???????????), ? ??? ?? ???? ????????? ?????? ?? ???????????????.
3.1
???? ? ??????????
? ?????????? ????? ?? ??????????? ?????? ???????????????? ??????????, ???????????? ?? ???? ??????????? ???????, ? ???????, ??? ????????? ????? ????????? ??????????? ?????????????? ????????? ??????????????????. ????? ????,
??????? ?? ???? ??????????????????? ????? ???? ?????????????? ??????????.
??????, ?? ??? ??? ???? ??? ? ??????????? ???????? ? ??????????? ?????? ?????????. ???????????, ??????????? ????? ??????? ????? ??? ?????? ??????????? ??????????. ???, ?????? ???????????? ????? ????? ??????? ????????? ???
??????????? ??????????? ? ?????????? ?????????? [7, 3, 32, 60, 34, 88, 80],
????????, ? ????? ?????. ? ????? ?. ?. ??????? ? ????????? ???????????
??????????? ? ????????????????? [56] ???????????? ????????????? ?????? ?
?????????, ??????? ??? ????????????? ?????????????. ? ????????? ??????
??????? ???????? ???????????? ???????? ?????????? ?????? ????? ? ???????????? ????????????, ??????? ?????????? ????? ?? ???????????????.
????? ??????, ??? ??????????? ??????? ?? ????? ???? ??????????? ?? ?????? ? ???????? ?????? ?????????. ?????? ??????????? ????????? ???????
?? ?????? ????????? ? ?????-???? ?????????? ?????????? ??????????. ? ????????? ?????? (????????, ? ?????????? ??????????) ?????????? ????????????
? ??????????? ??????. ??? ???????????? ?????? ????? ???????? ?????????????? (????????????) ??????????????? ?????. ????????????? ? ??? ??? ????
??????? ???????? ???????? ???????? ??????? ?? ????????? ?????????, ?? ? ???44
???. 3.1. ???????? ??????????? ? ????????????????? ??????.
???? n ? ? ???? ?????????????? ???????????? ??????????? (?? ???? ?????????? ?????? ?????????? ? ??????????? ???????? ???????). ????? ????????
???????????? ????????????? ????????????.
????????? ????????????????? ??????? ????? ??????????? ?????????? ?? ???????? ??????????? ???????. ?????????????, ????? ?????????? ???????? ? ????????????????? ??????????? ??????? ?? ?? ????????????? ????? ???????.
????? ????????????????? ??????? ????????? ????????????? ??????????????? (???????????????) ?????????????????? (???. 3.1)? ?????????????? ??????
?? ???? ?????? ???? ????, ???, ???????, ? ??? ??????????? ??????. ?? ??????????? ????, ??????????????? ?????????? ?????? ???????????? ??? ?????? ?????? (?????? 2.5.4).
3.1.1
????? ???????
??? ?????????? ????????????????? ???????????? ????? ????? ??????????? ?
??????? ????? ??????????? ??????. ?????? ?????? ???????????? ??????????? ?????? ?????????? ? ????? ??????:
? ?????? ?? ???????? ?????? ?????? ?????? ??? ??? ????? ? ???????????
????????? (???. 3.2-a).
? ??? ????????? ?????? ? ??????????????? ??????????? ??????? ?????45
(a)
(b)
(c)
???. 3.2. ?????? ????????????????? ??????. (a) ???????? ? ??????????????? ?????? (?? ???????? ??? ????????????); (b) ???? ??????? ?????? (???????? ???
?????????? ?????); (c) ????????? ?????????? ????? (???????? ??? ????????
?????).
?????????????? ???????? ???? ??????? ?????? ?????????? ????? ??? ???????????? ????????? (???. 3.2-b).
? ??? ??????? ?????? ????? ??????? ???????? ?????????? ????? (???. 3.2-c).
???????????? ????? ????? ? ???????????? ?????? ???????? ?? ????? ??????? ???????; ? ????????? ??????, ???????? ???????????? ?????? ????????? ?????? ? ???????? ?????????????.
3.1.2
?????????? ????????
? ????????????????? ???????? ????????? ??????? ?????????? ???????? ??????
????? ?, ?????????????, ????? ???????? ???????? ?. ??????? ????????????????
??????????? ??????????, ???????????? ????????????
en? =
|f n (x0 + ?) ? f n (x0 )|
,
?
(3.1)
??? n ? ?, ? ? 0, ????? ?? ????? ???? ?????????? ? ? ?. ????? ???????,
???? ???????? ???????? ????? (3.1) ??????????? ?? ????????? ???????? hdi/?,
??? hdi ? ??????? ?????????? ????? ??????? ? ????????? ??????????, ?? ????
d = |x ? x0 |. ?? ???. 3.3 ???????? ??????? «??????????» ?????????????????
???????: ?? ?????? ????????? ??????????? ???????????????? ????, ????? ?
???????? ?????????? ? ????????????.
46
???. 3.3. ?????????? ???????? ? ??????????? (a) ? ????????????????? (b) ????????
3.2
3.2.1
?????????? ?? ????
?????????? ? ????????? ???????
????? ????????
?????????? ? ????????? ??????? (???) [52] ???????? ???????? ??????? ???????? ? ????????????? ??????????? ?????? ?? ??????????? ???. ????????????? ????? ? ????????? ??????? ????????? ??????? ?????????????? ????? ?
??????? ?????? ? ????????? ???????? ?????????.
?????????????? ????? x ????? ???? ???????? ??? ??????????? ??????????
????? ? ???????? ????????????? bm bm?1 . . . b1 . a1 a2 . . . as , ??? ai , bj ? ????,
bm bm?1 . . . b1 ????????????? ????? ?????, ? a1 a2 . . . as ? ??????? ????? ?????.
??? ??????????? ? ???????? ?????????, ?????? ???????????? ??????? xn+1 =
f (x), ?? ????? ????????
xn+1 = roundk (f (xn )) ,
??? k ? s ? roundk (x) ???? ??????? ??????????, ???????? ???
roundk (x) = bm bm?1 . . . b1 . a1 a2 . . . ak?1 (ak + ak+1 ) .
47
???. 3.4. ?????????? ??????????? ??????? (????????????? ????????) ? ?????????? ?????????????????? ??????? ? ????????? 64 ????. ?????? ??????????
??????????? ?? ?????? ????????. ?????????? ??????????? ??????? ????????
??? ?????? ??????? ?????????????? ???????.
L
100000
avg
90000
80000
70000
60000
50000
40000
30000
min
20000
10000
b
0
5
10
15
20
25
30
???. 3.5. ??????????? ? ??????? ????? ????? (Lmin ? Lavg ?????????????) ?
????????????? ??????? ? ??????????? ?? ???????? ?????????? b (? ?????).
48
????? ?? ??????? ????????????? ??????????? ???????????? ?????? ???????? ?????????? ?????? ??????????. ??????? roundk (x) ??????????? ?? ?????? ????????, ? ?????? ????????????? ? ??????????? ??-?? ????????????????
??????? ? ????????? ????????. ?????????? ???????? ? ??????????????????
?????? ?????????? ????? ??????. ????????, ?? ???. 3.4 ???????????? ?????????
???? ???????? ? ?????????????????? ???????. ??? ???? ?????????? ????????1 , «. . . ????? ?????? ? ??????? ???????? ? ???????? ?????? ? ???????.
???????????? ?????????? ??????????? . . . » ????? ???????, ??? ??????? ??
???????? ?????????? ???????????? ??????????? ??????????? ???????.
?????? ????????????? ???????????????? ?????????, ??????????????????
??????? ????? ????????? ?????? «???????» ???????? ??? ? ?????? ??????????.
????? ?????? ????? ???? ?????????????? ???????? ? ???????????? ????? ?????????????? ???????, ??? ? ???????????? ???????????. ?? ???. 3.2 (a) ??????? ???????? ??????? ?????? ???-?????????????. ????????, ??? ? ??????????
?????????? ?????????, ?????????? ???????????? ??????? ??????????? ?????????
? ?????? ? ????????? ????????????? ?????????. ???, ?? ?????? ???????????? ???????? ??????????, ???????????? ????????? ???????, ????? ????? ??????????
???????, ?? ?? ?????? ???? ????????; ? ? ?????? ?????????? ?? ????, ??????????? ????????? ????????????. ?? ???. 3.5 ???????????? ?????????? ??????????
????????????? ??? ????????? ????????? ??????????. ??? ?????, ??????? ????? ?????? ??????????????, ? ??????????? ???????? ????? ???? ??? ???????
????????.
?????? ???????? ? ???-??????????????? ??????? ? ???, ??? ?????????
????????? (?????????? ? ???????????) ?????????? ????????? ????????? ?????????? ?????????????? ??????? ? ????????? ????????????? ?????????? ?
?????? ?????????. ??? ??? ??????????? ?????????? ?????? ????????????? ? ????????, ????? ????????, ??? ??????????? ????????? ??????????, ?????????????
?? ????????? ??????????, ???????? ??????????????.
?? ?????? ?? ????????????? (????? ???????????? ??????????), ?????? ?????????????? ????????? ? ?????????? ??????? ????????????????? ??????? ??
???? ???-????????????? ??????????? ???????. ???? ??????????? ????? ??????????? ?????? ? ???? ??????????.
3.2.2
????????? ???????????? ?????????
????? ? ????????? ??????? ????? ????????? ???????? ??????, ??????????
????????? ?????????????. ?????????????, ?????????? ??? ??????????????????
1
??????, ??????, ???????????? ??????????, ?????????? ?????? ??????????? ??????? ?
?????? ?????????? ??????????? ????????? ? 1960 ?.?.
49
????? ?? ????? ?????????? ???????????. ????? ?????????? ?????????? ?????????????? ??? ? ?????? ??????? ????????? (?????? 2.4.1), ? : X ? {0, 1}m , ???
X ? ????????? ????? ? ??????? ? ????????? ???????. ?????????? ?????? ?
?????? ?????????? ????????? ????.
????? ???????, ???????????? X ??????????? ?? ??? ?????????????? ???????????? X0 ? X1 , ??????? ????????????? ???????? ? ? ???????? ??? 0 ??? 1.
??????? ??????? ???????? X = X0 ?X1 ????? ?? ??????????? (?? ???? ?????????
?????????? x ?
/ X0 ?X1 ????? ??????????????? ?????? ??????). ????? ????, ??????? ?????? ????????? ?? ????? ???????? ????????? ?????????????? ????????
???????? ?????????????????? ??? ?? ???????????? ?? ??????? ???????????? ?????????, ??????? ?? ????????????? ????????????????? ??????????? (???. 3.12).
????? ??????????? Xi ????? ???? ?????? 2 (????????, 4, 8, 16 . . .). ????? ??
???? ???????? ????????? ????? ??????????? ?? ????, ? ????????? ??????????????? ????? (m = 2, 3, 4 . . .). ????????, ??? ?????????? m ???????? ??????????????? ??????????, ??? ??? ??????????? ???????? «???????? ????» ? ??????????
?????.
3.2.3
?????????????? ????????
? 1983 ????? et. al. [38] ????????? ???????????? ??????????? ??????? ???????? ??? ????????????? ????????? ????????? ?? ???????? (??????????)
???. ???????????? ???????, ??????????? ?? ???? ???????? ????????, ?????
???
xn+1 = x2n ? 2,
xn ? (?2, 2) .
(3.2)
????????? ??? x0 , x1 , x2 , . . . ???????? ???????????, ??????, ????????? ????????
xn ?????? ?????????? (xn 6= ?1, 0, 1). ????????????, ??? ?????? ???????? ???????? x0 ? (2, 2), ?????????? ?? ?????? ? ??????????? ?????????, ??? ??????
??????? ? ???-?????????????. ???, ??? ???????? ? 40 ??? ??????? ????? ??????????? ?????? ?????????? 105 ????????.
?????????? ????????? ??? {xn } ???????? ?? ??????? ??????????????????
??????????. ? ?????????, ????????? ????????????? Pr(xn ) ?? ???????? ???????????, ??? ???????? ?? ???. 3.12. ?? ????? ??????????? ???????? ??????????????
???????? ??????????????????, ???????? ?????????????? ??????????????
x 4
n
arccos
? 2.
(3.3)
?
2
?????????????? ?????????????? (3.3) ????????? ???????? xn ?? ????? ????????? ? ???????? ????????????? Pr(xn < x). ??????? ??????????????????
??????? ????????????? ?????????????????? yn ???? ?????? ? ??????. ?? ???. 3.6
yn =
50
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
-2
CDF x
CDF y
-1.5
-1
-0.5
0
0.5
1
1.5
2
???. 3.6. ???????????? ??????? ????????????? ?????????? ????, ???????????
??????????????? ????????, ?? (???????? ?????) ? ????? (???????? ?????) ????????????. ???????? ????? ?????? ?? ??????????? ????? ????????????? ??
??????? (?2, 2).
???????? ????? ???????? ??????? Pr(xn < x), ? ???????? ????? ? ???????
Pr(yn < y).
??????, ?????????????????? yn ?? ???????? ???????????????, ?? ?????? ??
??, ??? ?????? ??????? ????????????? ????????????? ???????????? ??????.
?????????????? ?????????????? (3.3) ?? ????????? ???????? ??????? ????????? ? ?????????????????? xn , ??????? ????????????? ????????????????? ??????????????? (3.3). ?? ???? ???????? ??????????? Pr(xn |xn?1 , xn?2 , . . .) ???????? ???????????? ? ????????? ?????????? ????????????? ??????????????????
yn . ???????, ??????????? ????? ?????????? ?????????????????? ????? ????
????????? ????? ???????? ????????????? ?????? (?????? 2.6).
????? ?????????? ?????????????? ???????? ??? ????????????????? ?????????? ???? ???????? ?????????? ??????????????? (????????, [53]).
3.2.4
????????????? ????????
????????? ????????????? ???????? ???????????? ?????????????? ????????.
?????, ? 1976, ??????? ?????????? (Mitchell Feigenbaum) ?????????? ???????
????????? ??? ?????????? ????????????? ???????. ???????????? ??????? ?????? ?????????? (???. 3.7)
xn+1 = 4rxn (1 ? xn ) ,
51
(3.4)
x n+1
xn
xn
???. 3.7. ????????????? ???????? ??? r = 0.99.
n
???. 3.8. ????????? ??? ?????????? ? ????????????? ??????? ??? x0 = 0.34 ?
r = 0.99.
52
???. 3.9. ?????????? ????????????? ???????. ???????? ??????????????? ????????? ??????????? ??? r = 1.
???. 3.10. ?????????? ??????????? ??????? ?????.
??? x ? (0, 1) ? r ? (0, 1).
??? ????????? ???????? ???????????? ????????? r, ??????? ???????? ???????????. ?????????? ?????????? ???????? ??? ?????????? ? ??????? ? x0
???????????? ??????????
N
1 X
? (x0 ) =
log |r (1 ? 2xn )|.
N
n=1
??????? ????????? ????????, ????????, ??? r = 0.9 ???? ? (0.5) ? 0.7095.
???? ????????, ??? ??????? ????????? ????????? ???, ??????? ???????
??????????????? (???. 3.8). ?????????????? ????????? ??????????? (???. 3.9)
?????????? ?????????? ???????? xn ??? x ? ? ??? ????????? ???????? ??53
xn+5
1
0
0
xn
1
???. 3.11. ??????? ????????????? ??????? ??? n = 5.
??????? r. ? ??????????? r ????? ????? ?????????? ????????????? ? 1 ?? 2, 4,
8 ? ??? ????? ?? ?????????????. ??????????????, ??? ? ??????? r ? 1 ???????
??????????????, ?? ???? ??? ??????????? ?????? ???????? r ? ?????????? ??????? n ?????????? ??????????? xn ?? x0 , ?, ????????, ?? xn ? ???????????? x0 .
??????? ????????, ??? ??????? ??? ????? ?????????? ????????????? ???????
????? ???? ???????? ? ????????????? ???? [61]. ???, ??? r = 1
?
xn = sin2 (2n arcsin x0 ) .
(3.5)
??? n = 1 ????? ???????? ?????????????? (3.4).
????? ???????, ????????? xn ????? ???? ?????????? ?? x0 ??? ??????????
n ????????. ?? ???. 3.11 ???????????? ???????? x5 = f 5 (x0 ). ? ???????????
n ????? ?????????? ????? ?????, ???????? ????????? ???? ????????????????
? ????????? ????????. ?????? ?????????? ?????? ? ?????? ?????????????
???????? ????? ??????????? ? ??????? 3.2.8.
?????? ???????????? ???-????????????? ?????????? ??????? ? ?????????????? ?????????? ???????? ????????????? ??????????? ?????????? ? ??????? ????????? ???????????. ?? ???. 3.7 ?????, ???, ????????, xn = 0.2 ?
xn = 0.8 ???????????? ? ???? ? ???? ???????? xn+1 . ? ??????? ? ???????????
?????? ?????????, ??????????? ?????? ?????????? ?????????? ??????. ????????,
? ??????? ? ???????????, ??????????? ?????????? ????? (?????) ?????????? ?????????? ????????????, ??? ????????? ??????????? ???????????? ??????.
?????? et al. [27] ?????????? ???????????? ????????????? ??????????????
(3.4) ??? ????????? ?????????????????? ????? ? ??????? ? ????????? ???????.
54
3000
2500
2000
1500
?0?
1000
?1?
500
0
0
0.2
0.4
0.6
0.8
1
???. 3.12. ????????? ????????????? ????????? ? ????????????? ???????. ???????? ????????? X ?? ???????????? X0 ? X1 ? X ????????? ???????????? ??????
?? ??????? ???????????? ?????????, ??????? ????????????? ?????????? ?????????????????? ??????????.
??? ?????????????????? ????????????? ? ????? ????? ??? ?????? ?????????
???????????? ?? ??? ?????????????? ????????????, ??? ???????? ?? ???. 3.12.
?????????? ??????? ?????????????????? ???????????? ?? ?????? 2 (XOR) ?
???????? ??????? (??. ???? ???????, ?????? 1.1.3). ????????? ??????? (????????? x0 ? ????????? r) ???????????? ????? ????????? ????.
??? ??? ???? ????????, ????? ?????? ? ????? ? ????? ??????????????????
???????????? ?????????, ?? ??????? ????????? ?????? ?? ??????????????? ?
?????????????. ????? ????, ????? ????? ??? ????????? ?????? ????? ????
??????????? ????????? [84, 55].
????? [68] ???????? ????????????? ?????????????? ??? ?????????????????
?????:
r
1
xn+1 = (r + 1)
+ 1 · xn (1 ? xn )r , r ? (1, 4) .
r
????????? ??????? ????? ????? ???????????? ????????? ????????? ??? ???????? ????????? ???????????? ????????? r (???. 3.10). ????? ???????, ??????????? ????????????? ???????????? ?????? hx0 , ki. ? ?????????, ????????
?????? ???????????? ????????, ???????????? ???-??????????? (???????? ??????, ??????? ??????????).
55
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
a
0.4
0.6
0.8
1
???. 3.13. ?????????? ??????????????.
3.2.5
?????????? ??????????????
?????????? ?????????? ?????????????? ?????? ????????
a · xn , 0 ? xn ? a
xn+1 =
,
1?xn
a < xn ? 1
1?a ,
(3.6)
??? ???????? a ?????? ???????? ??????? ????? ??????? (???. 3.13).
?????????? ?????????? ???????? ??????? ?? ????????? a ? ????????????
???????????? ? (a) = ?a ln (a) ? (1 ? a) ln (1 ? a) ????? ??? ???? x0 ? (0, 1) [64].
????????, max ? (a) ? 0.693 ??? a = 0.5.
a?(0,1)
?????????? ??????? ????? ????????????? ??????? [61]
xn =
1
arccos (cos 2n ?x0 ) .
?
(3.7)
??????? et al. [49] ?????????? ??????? ????? ?????????? (???. 1.3) ?? ????
????????????? ??????????? ??????????????
a · xn ,
rn = 0
xn+1 =
,
n ? [1, N ] .
(3.8)
(a ? 1) xn + 1, rn = 1
??? ri ? {ri }N
1 ? a ? [0.4, 0.6]. ????????? ???? ??????? ?? ????????? a (? ??????? ? ????????? ???????) ? N -??????? ?????? {ri }N
1 . ?????????? ??????????
????? N -???????? (N = 75) ?????????????? ????? ????????? ?????? ? ??????????. ?????? ????? ????????? ?????? ? 64 ????, ??????????? ? 147 ???. ?????
56
???. 3.14. ????????????? ????? ??????????
???????, N ????????????????? ?????????????? ???????????? 2N ????????? ????????? ?????????? ?????? ????? ??????.
??? ????? [26] ???????, ???? ???? ????? ???? ????? ???????? ??? ?????
? ????????? ???????? ???????, ? ????????? ????? ??? ????????? ????????
?????? ?????????? K = 238 .
3.2.6
?????????????? ????
???????????? [72] ????????? ???????????? m ?????? ??????????? ?????? ???
????????? ??????????. ????????? ????????? ??????? ??? m ?????? ????????
??????. ?? ?????? ??????? ????????? ????? xn ? ??????? ? ????????? ???????, ?? ???????? ??????????? ???? ??? bn , ????? ???? ??? m ????? ???????????
? ???? ??? b ????????? XOR. ?????????? ??? b ???????? ?? ????? ??????????. ??????? ??????????? ??? ????????? «???????????? ????????» ???????????
?????.
????? ???????????? ????? ???? ??????? ????????? ???????:
1) ????????? ????? ?????? ??????? ????? ??????????? ? ?????????? ????????. ??????? ???????, ??????????? ??????? ????? ???????? ????????
??? ?????? ?????? q-?? ????????. ??? ????????? (???????????) ??????? ?????????? ????? ?????????? ?????????????????? (?????? 2.6).
2) ????? ??????????? ?????? ????? ???? ??????????????? ? ????????????
??????? ????? (??? ??????).
3) ??????? ????? ???????????? ? ???????????? ? ????????? ????????? ???-
57
?????, ????????? ?? ????? (???. 3.14).
? ?????? ????????? 1, ????????????????? ??????? ???????????? ?????
???????? ? ???? ???????
? 1
xn+1 = f1 (x2n , k 1 ),
b1j = ?1 (x1qj )
?
?
? 2
xn+1 = f2 (x2n , k 2 ),
b2j = ?2 (x2qj )
···
···
?
?
? m
m ), bm = ? (xm )
xn+1 = fm (xm
,
k
m qj
n
j
bj = b1j ? b2j ? . . . ? bm
j ,
???
f1 , f2 , . . . , fm ? ???????????? ???????, ???????????? ? ??????? ?????? ?????;
m
1 2
m
hx10 , k 1 , x20 , k 2 , . . . , xm
0 , k i ? ????????? ???????; bj , bj , . . . bj ? ???????? ????
?????? ? (n = qj)-?? ?????? ???????; bj ? ???????? ??? ??????????.
??????????????? ????????? ?? ?????????? (1)-(3) ??? ?????????? ? ?????????? ? ?????? ???? ??????. ??? m = 5 ? q > 20 ???????? ??????????????????
?????????? ??????????? ?? ?????????. ??? ?? ????? ??????? ????????? ? ??
???? ????????????? ??????? ????????????? ???? ??????? ???. ? ?????????,
??????????? «??????????» ?????? ? ?????????? ?????????? ? ????. ??? ?? ???????? ? ???????????? ????????? ???? ??????? ??-?? «m-???????? ??????????????», ?? ???????? ????? ????????? ??????????????? ??????????.
3.2.7
?????? ??????????? ?????
??????? et. el. [45] ?????????? ??????????? ????????? ???? ?? ?????? ??????????????
x
1 a
f (x) = a +
x ? (0, 10) , a ? [0.29, 0.40] .
x
?????? ???????? ?????????? ?????????? ????????? x0 ? ????????? a. ?????
n0 = 200 ????????? ????????, ??????? ??????? ???? ????????? ?????? p1 ?
???-?????????? c1 = f n0 +p1 (x0 ) (32,64,128 ???), ?? ???? ?????????????? f
??????????? ??? (p1 ? [0, 255]) ???. ??????????? ????? ????????? ?????? ????????? ? ??????? ??? ?? ?????????? (???. 1.4-c):
ci = f n0 +
Pi
k=1
pi
(x0 ) .
???????????? ????? ????? ?????????? ????????: (1) ???????????? (8 ?
10-?? ???????) ?????????? ??????? ??????????? ?? ????????? ? ???????? ???????; (2) «??????????» ??????????, ?????????? ?????? ?????????????? ?? ????
???.
58
???????? [25] ? ???? [87] ?????????? ????????? ??????? ??????????, ? ??????? ???????? ????? ?????????? ?????? ????????. ???????????? ????????? X
??????????? ?? m ????????????????? ??????????? {X1 , X2 , ..., Xm } (??????????? X ????????? ??? ????????). ??????? ???????????? ????????????? ?????????? ?????? ????????? ??????. ????? ????????????? ????????? ?????????
????????, ??????? ???????? ??????, ??????? ?????????? n0 ????????. ????? ???
??????? ????????? ?????? ????????????? ? ?????????????????? ????? ?????,
?????? ????? ???????? ??? ?????????? ???????????????? ????????????:
ci = ni ? ni?1 ,
i = 1, 2, . . . ,
??? pi = ? (Xi ) , f ni ? Xi . ?? ???. 1.4-b ???????? ?????????? ?????????????
?? ????????? ????????. ??? ??????? ????? ?????????? ????? ???? ????????? ????? ???????? ?????????????? ?????????? (????????, ??????????? ?????
????????).
????????, ??? ????????????? ????????????? ???????? ????????????? ? ??????????? ???-?????? ??? ?????????? ?????????????? ??????????: (1) ??????? ????????? ??????????? ???????????? ???????? ci = ni ? ni?1 , ??? ??? ??
????? ???????? ?????; (ii) ?????????? ? 2-3 ???? ??????, ??? ???????? ?????.
?? ????????? ???????????? ?????? ???????? ? ????? ? ?????? ??? ?????????????? ? ???????????????. ??????????? ?????? ??? ????? ????????? ??????
? 4 ????, ? ????? ??????????? ? 10 ???. ? [51] ?? ????????? ????????????
??????? ??????????? ????????????: ??????? ?????????, ????????????? ?????????? ? ??????????????? ?????????.
?????????? et el. [62, 63] ??????????? ????? ?????????? ?????? ? ????? ?
???????????? ? ?????????? ???????? ???????????? ???????? ??? ????????????????? ??????. ?????????? ?????????? ????????????????? ?????, ? ???????
?????????? ?????????????? m-??????? ?????????? ????????? ??????????????
f ?1 (???????????? ? ????????????), ? ???????????? ? m-??????? ??????
??????????????? f . ???? ???????? ? ????????? ???????? x0 ? k. ??????????
f ? f ?1 ?????????????? ??? ?????? ???. ? ???????? ??????? ??????????? ??????? ?????????? ????????????? ??????? ????????? ??????????????? ???? ?
????????. ??????? ???????? ????? ????????????? ? ??? ?????????? ? ????,
???????????? ??????????? ????.
??? ?????????? ????????????????? (????? ?????????, ????????????, ?????????) ????? ???????????? ??????? ???????????????? ????????? ????? ???????? ??????? ? ???????????. ????????, ???? [71] ????????? ????????????
59
?????? ?????? ??? ?????????? ??????
2
dx
dx
dx
d2 x
s ign
? ?2 s ign
? ?21 x ? ?23 x2 =
m 2 ? ?2
dt
dt
dt
dt
?2
= L 0 cos (?0 t) ? ?21 e?21 t ? ?22 e?22 t ,
2?
??????? ????????????? ??????? ??????? ? ?????????????? ?????? ?21 ? ?23 .
?????? ????? ????????????
????? ????????????? ????, ????????? ?? ??????? ?
?????????? L ?02 /2? ? ???????? ?????, ???????? ???????????????? ???????????.
?? ??????? ??????, ?? ????? ????? ??????? ?? ??????????? ? ???? ????????
????????? ?????????? (?? ?????? ???? ?? ???????? ??????). ??? ???????????,
??????? ???????, ??????? ????????? ??????????????? ? ????????????? ?????????????? ????????? ??????????.
3.2.8
??????? ? ????????????? ???????????????
? ?????? ????????
? ?????????? ???????? ?? ??? ??????????? ?????? ??????? ??? ????????????? ? ?????????? ??????. ?????? (?????????????) ??????? ????????? ????????? ???????????? ???? xn ?????????????????? ????? ?? ????????? ??????? x0 ,
????? n-??????? ?????????? ???????????? ???????. ?????? ??????? ????????? ???????? ?????????? ?????? ? ??????????? ???????? ???????? ??????????.
?? ???. 3.4 ?????, ??? ??????????? ????????? ?????????????????? ????????????? ???????, ?????????? ??? ?????? ???????????? ? ?????? ??????????.
??????????? ??????????? ??????, ????????????? ????????????? ? ????????????, ????? ?????? ???????. ?????? ???? ???? ?? ????????????? ? ??????
?????????? ?, ????????, ???? ?? ??? ???????? ?????????????. ????, ??? ??????? ?????????? ????????????, ???? ??????? ????????????????? ???????? ?????
???????? ????? ??????? ??????????.
?????? ??????? ??? ???????????? ??????? ????? ???? ???????? ? ?????
[47, 61]
xn = ? (?T ?n ) ,
(3.9)
??? ? (t) ? ????????????? ??????? ? ???????? T ; ? ? ????? ?????; ? ? ? ????????? ?????????????? ????????, ???????????? ????????? ??????? ?? ?????????
x0 = ? (?T ) .
??????? ???????? ???????????, ???? ? = ln ? > 0.
60
???. 3.15. ????????????? ?????????????? xn+1 = f (xn )
?????????? ??????? ? ?????? ????????, ???????? ??????????
xn = sin2 (???n ) .
(3.10)
?????????????? f : xn ? xn+1 ??? ????? ??????? ???????????? ??????????
?
xn+1 = sin2 (? arcsin xn ) .
(3.11)
? ??????? ?? ??????, ??????????????? ?????, ?????????????? xn+1 = f (xn )
????? ????? ???? ?????????????, ? ?????????, ????? ? ? ?????????????? ?????.
??????????????? ????????????, ??? ????????? ???????? xn ????? ??????????????? ?? ????, ? ????????? ????????? ??????????? ????????? xn+1 . ?? ???. 3.15
??????????? ?????? ?????????????? ?????????????? (3.10) ??? ? = ? 1/3 .
??????????? ??????? ? ?????? ???????? ? ????????????? ???????????????
???????????? ??????? ??????? ??? ????????????. ? ????? ???????, ?????? ??????? ????????? ???????? ?????? ? ????????????? ????? ??????????????????,
?????????? ???????????? ????????? ???????? (???????). ? ?????? ???????,
???????? xn?1 ? xn+1 ?? ????? ???? ????????? ?? xn , ?? ???? ????????? ?????
???? ??????????????? ? ???? ???.
??????? xn = ?(?, ?, n) ?????? ???? ????????????????, ?? ???? ?????????? ????????? ??????? x0 ?? xn ?????? ???? ??????????? ???????????.
61
????????? 3.10 ???????????? ? ? ? ??? ????????? xn ????? ???????????? ????????? ???????. ?????????????? xn ? ?????? ? ???????????? ? ?????????? (X0 , X1 )
???? ????? ???????? ????????????????, ??? ??? ??????? ? ??????? ??????? ??????????. ??????, ????????????????? ??????, ??? ????????? ?????????? ?????????? ??????? ????? ??????? ??????????????? ????????????.
?????????? ??????? ??????? ????? ???????? ???????? «???????????????????». ??????? ???????? ????????????? ?? ????????? ??????? ??????? (??????????, ??????????? ? ???????), ? ????? ????????? ? ???????? ???????????? ????????? (??? ?????? ????????????? ???????, ????????, sin, mod). ??? ????????
? ????, ??? ????? ??????????????????, ??????? ????? ???????? ?? ?????? ?
???????? ????????? ??????????, ???? ??????????. ????? ???????, ???????????
??????? ? ?????? ???????? ???? ????? ???? ???? «????????» ???????????????. ????? ????, ??? ??????? n ? ?????????? ????????????? ?????????? ????????????? ???????????, ?????????????????? ????? ??????????? ?????????? ??
??????????? ? ????????? ???????? ????????.
?????????? et al. [61] ?????? ??? ?????? ?? ????????????????? ??? ?????????
????????? ??????????? ?????? ? ?????? ???????? ? ????????????? ??????????????? (? ?????????, (3.10)). ?????? ??????? ?? ????????? ????????? ??????????? ????????? ??????????????? ?????, ?????????? ???????????? ???????????
????????????. ? ?????????, ?????????????? ???????? ?????????????????? ?????? ???????? ? ??????????? ?? ????????? ???????. ?????? ?????????? ????????????????? ??????? ? ?????? ???????? ? ???????????? ??????? ??????????????? ????????????.
3.3
3.3.1
???????? ??????????
????? ????????
? ??????? 1.2.6 ?? ???? ??????????? ?????????? ??????????? ???????, ???????????? ?? ????????? ??????????? ???????? ????? ?. ?????????????? ?????
??????? ?????? ???????? ???????? f : ? ? ?.
????????????????? ??????? ????????? ? ???????????? ????????? ?? ???????? ????? ?, ???????? ????? ????????????, ?????????? ??????????????????.
???????? ????????????????? ??????? ?? ????????? ????????? ????????? ???????????????? ??????????????, ?? ??? ?????????? ??????? ??????????? ??????? ?????????? ???????? ????????????? ?????????.
??????????
??? ???????? ????????????????? ???????
?????????? ????????
m
hA, f i, A ? ?m |? ? {0, 1}
c ???????? ????? ????????? 2m ????????????
??????????
62
1
log dH f n (?0 ) , f n ?00
n?? n
0
??? ?0 ? A ?????, ??? dH (?0 , ?00 ) = 1.
? «???????» ????????????????? ??????? ? n-??????? ??????????, ????????
?????????? (? ??????? ? x0 ? x00 , ????? ??? dH (x0 , x00 ) = 1) ???????????????
??????????, ? ???????, ?? hdH i = m/2 (???. 3.3-b).
??? ?????? ???????????? ??????? ? ???????? ?????? ?????????, ????????????????? ??????? ???????? ?????????????. ????????? ?????, ? ??????? ?????????? ????? ???? ??????, (?? ????? ????? ????? ????????? ???????????? ?????????),
???????? ?????????. ????????, ????????? ? ???????? ???????? ?????? (LFSR)
? (?0 ) = lim
xn = (c1 xn?1 + c2 an?2 + · · · + ck an?k ) mod 2
??? ???????????? ????????? ????????????? ci ???????? ????????? [75].
?????? ???????? ????????????????? ??????? ????? ??????, ????? ???????
??????? ?? ????????? ???????. ???, ??? (Fog, [40]) ?????????? ??? ??????????
?????????????? RANROT. ??? ?????????????? ?????????? ?? ????????????? ??????????? ?????????? ???, ??? ????? ?????????????? ?????:
xn = (xn?j + xn?k ) mod 2b rotr r,
??? xn ? {0, 1}b , r ? [0, b/2) ? ????? j, k ?????????? ? ???????????? ? ????????? ?????????. ????????? ???????? ???????? ?????????????? ??????????
? ???????? ????????????? ??????????????? ??? ??????????? ??????????. ???
??? ???? ????????, ?????????? ????? ?????? ?????? ???, ??? ?????????? ??????????? ????????? ?????????. ??? ??????? ????????? ?????? ??????????? ?
??????????? ????????? ???? ?????? (?? 1000 ????????) ????? ??????? ??????
?????????????????? ??????????.
3.3.2
?????????? ?????????? ??????????????
?????? et al. (Masuda, [67]) ??????????? ????????????? ?? ???? ?????????? ?????? ??????????? ??????????? ?????????????? (???. 3.16)
( M jA X ,
k 1?X?A ,
F (X) =
M
M ?A (M ? X) + 1 , A < X ? M
??? X, A = 1, 2, ..., M ? bc , de ? ?????????? ? ??????? ? ??????? ?????? ??????????????. ????????? ??????? ????????????? ???????? ???????? ???????, ?
?????????????? ????????? ?????????? ??????????. ?????? ???????? ????????
63
???. 3.16. ?????????? ?????????? ??????????????.
A. ?????????????? ??????????? N ???. ????? ??????? ??????????? ????????
N , ??? ??????? ??????? ?????????? ????????? ?????? ????????? ? ????????????????? ?????????????.
3.3.3
????????? ????????
???????? (Wolfram, [86]) ??????? ???????? ?????????? ????????? ???????
??? ????????? ??????????????? ?????. ????????? ??????? ???????????? ???????? ?????? (?????)
b = (b (1) , b (2) , . . . , b (n)) ? {0, 1}n .
???????????? ??????? f : {0, 1}n ? {0, 1}n ?????? ??????????
b(i) = b(i) ? 1 xor b(i) or b(i + 1) ,
??? ???? 1 ? i ? n. ?????? ??? ????????? ???????????, ?? ???? b (n + 1) = b (1).
??? ???????? ??????????? ???????????, ? ?? ????? ???????? ?????? ???? ???
bk , k ? [0, n].
?????? (Ritter, [75]) ????????, ??? ?????????????????? ?????? ?????????? ???????? ???????????????, ??????, ????? ??????? ??????????? ? ??????????????.
??? ???????????? ??????? ?????????? ??????????, ????????? ?? ???????? ??????????? ? ??????????? ?????????? ?? ????? ?????????? (???????? ??? ??????? ???????? ???????).
???????? (Gutowitz, [48]) ?????????? ??????? ??????? ????? ??????????
?? ???? ????????? ?????????. ???? ????????? ?????? (512 ???) ?????????????
? ???? ??????????? ????????? ???????? ??????? (578 ???). ???? (1088 ???),
????????? ?? ???? ?????? ?????????? ??? ?????? ????? ??????????, ??? ?????????? ????????? ????-?????. ???????????? ??? ????????, ?????? ?? ???????
64
1
nk
...
n2
0
n1
n2
...
nk
0
1
n1
???. 3.17. ?????????? ?????????????? ??????.
???????? ??? ???????????. ? ???? ???????, ?????? ??????????? ???????? ???? ??????????? (s-box) ? ????????????? (p-box). ????? ???????, ??? ????? ?????????? ???????????? ??????????????? ??? ???????????, ? ??? ?? ????????
?????????? ? ????????????????? ?????????????.
3.3.4
?????????? ?????????????? ??????
????????????? ? ????????? ?????????????? ?????? ???? ????????? ????????????? ? ???????????? ??? ???????? [79]. ?? ?????????? ????????? ???????
?? ???? ??????????? ?????????????? ??????, ??? ?? ?????????? ???????? ???????????.
?????????? ????? ????? ??????????? ?? ???????????? ?????? ? ????????????
? ?????????? ? = {n1 , n2 , ..., nk }. ?????? ?????? ?? ??????????? ?????????????
?? ????? ??????? ????????, ? ?? ????????? ????????? ?? ???????? ?????? ni ,
??? ???????? ?? ???. 3.17.
??????? ?? ???? ?????????????? ?????? ????????? ???????????????? ???????????????? ?? ????????? ? ????????? ???????? ? ????????? (????????? ?).
???, ????? 6 ????????, ???????????? ???????? ?? ?????????????? (???. 3.18).
?????????? ?????????????? ?????? ????? ???? ??????????? ??? ??????
????????? ??????????. ????? ???????????? ??????? T? ?????? ?? ??????? ??
N ?????????:
T? : {0, 1}N ? {0, 1}N
????? ????? ????? {n1 , n2 , ..., nk } ?????????? ???, ??? ?????? ????? ni ?????
??? ??????? N ? ?????? n1 + n2 + ... + nk = N . ?????????????? T? ?????? ?????
65
???. 3.18. ????? ???????? ?????????????? ?????? c ?????????? ?
{0.25, 0.5, 0.25}, ??????????? ? ??????????? [76].
=
??????? ???????? ??????? ? ???????????? (r, s):
N
N ni
N
T? (r, s) =
(r ? Ni ) + s mod ,
s ? s mod
+ Ni ,
ni
ni N
ni
??? r, s ? {1, 2, ..., N } , Ni = n1 + n2 + ... + ni , i ? {1, 2, ..., k} ? Ni ? r < Ni + ni .
?????????????? T? ???????????? ?????? ??????????? ????????????, ?? ?? ?????? ?????????????? ???????? ????????? ??????. ????? ???????, ? ??????? ?????
?????????? ?????????????? ?????? ????? ???????????? ??? ??????????? ????
???????????? (p-box), ? ??? ???? ??????????? (s-box) ?????????? ?????????????? ??????????????, ?????????????? ???????????.
???????? (Scharinger) [76] ? ??????? (Fridrich) [42] ??????????? ???????
????? ?????????? ?? ???? ?????????? ??????. ????????????? ???????, ???
????????????????? ??????? ????????? ?????????? ???????????? ????? ???????? ???????, ????????, ???????? ???????????. ? ??????? ???????? ??????????
????????, ??????? ???????? ????????? ??????????????? ?????? ?? ???????????. ??? ??????????????? ?????????????? ?????????? ??????????????? ????????????? ??????????? ??? ????? ?????????? ????????. ?????????? (?? ???? ???????????? ??????????? ????? ?????? ????? ????????? ?????? ? ????? ?? ????
??????????????????? ???????????) ?????????????? ??? ?????? ???????? ???????? ? ???????? ???????? ?????? (LFSR) [75]. ??????????? (Cappelletti, [31])
?????????? ?????????? ?????????? ????? ?????????? ????????? ?? ???? ??????????????? ??????????.
66
3.3.5
?????????? ? ???????????? ??????????????
??????????? ????????????????? ??????? ???????????? ????? ???????? ??????????, ?? ???? ??????? ? ???????????? «??????????? ????????» ? ?????????????? ??????????????? ?? ????????? ??????? ?????.
??????????????? ??????????
? ??????? 2.6 ?? ??? ???????, ??? ??????? ???????? ???????????? ????????? ??????????????? ????? ???????? ?????????? ???????? ??????????? ??????? ?? ???? ????????????? ??????????????. ??????, ?????? ????????????????
? ????????? ????????, ????????????????? ????????? ?????????? ????????????
??? ????? ?????? ?????????? ? ?????????????? ?????????????????? ?????????????? xn+1 = f (xn ). ? ???????????? ???????????? ??? ?????????????????
??????????? ?? ???? ?????????????? ????????? ?????? ? ?????? ?????.
????????, ????????? Blum-Blum-Shub [69, 75] ???????? ?? ???????? ?????????? ???????? ????? ?? ?????????. ???????????? ??????? ?????? ??????????
xn+1 = x2n mod M,
??? M = pq, p, q ? ??????? ?????, ???????????? 3 mod 4. ???????? ??? ?????????? bn = ?(xn ), ??? ?(xn ) ? ???????????????? ???????, ?????? ??????????
???? xn .
???????????? ?????? ????? ???? ??????? ? ? ?????????? ????????:
1) ??????? ????????????? ? ????????? ??????????????, ?????????????? ?
???????????? ?????????.
2) ?????????? ?????????? ????? ???????????, ??????????? ?????????????? ?????????? ?????????????? ????????? ?????????????????? (????????????? ????????? ?????????? ??? ???????? ???????????).
???????????? ??????? ?????
??????? ??????? ????? ???????????? ????? ???????????? ?????????? ???????????, ??????????? ??????????????. ??????????????? ??? ?? ??????? ????? ?????????? ??????? (Rijndael, [73])2 . ??????? ???????? ????????????,
????????????, ??????? ??????. ????????? ????????????? ?????? ?????????
???????? (????????) ?????. ????????? ????????? ??????? ???????? ????????
???????. ??????????????? ???????????? ??????? ????? ??????:
2
???????? ??????? ? 2001 ???? ?????? ? ???????? ????????? AES (Advanced Encryption
Standard), ????????????? ?????????? ??????, ???????????????????? ?????????? ????????????? ???. ????????, ?????? ?????????? ??-????? ? ? ???????????? ???????.
67
1) ????? ??????????? (s-box), ????????????? ??? ?????? ????????? ?????????????????? ? ????????? ?????????????? (?????????, ??????, ??????
???????? ? ?????? ????? ? ?????????);
2) ????? ????????????? (p-box), ?????????? ??????????? ????? ????? ?
???????????? ????????;
3) ????? ???????? ? ???????????? ?????? (round key). ?? ???? ? ????????? ??????? ??????????? ??????????????? ???????, ??????? ???????????? ??? ?????? ????????? ????????????????? ??????????.
??? ??????????????? ???????????? ??????? ??????????? ? ????????? ???????
N > 10 ???. «?????? ???????????» (?????? ??? ????????? ?????? ? ?????
?????? ?? ?????? ??? ???????????) ??????????? ??? ????? ???? ????????.
?????????????? ????????? ???????? ????????????.
68
????? 4
??????????
4.1
????????????? ??????
1) ?????????? ??????????????? ??????????? ????? ??????????????????
? ???????????? ?????????. ? ??? ? ????? ?????????????? ????????????
?????????????? ?????????? ? ???????????? ? ????????? ????????????????? ???????. ???????????????? ? ????????? ???????? ? ??????????, ? ????? ????????????, ????????? ??????????? ? ?????????? ? ???
????????????????? ??????, ???????????? ????????.
2) ? ?? ?? ????? ?????????? ??????????????? ???????? ????? ????????????? ? ??????? ?????: (1) ???????????? ??????? ??????? ? ????????
?????? ?????????, ? ?????? ????? ? ??????????? ????????????; (2) ???????????? ??????? ????????? ????????? ????? ???????? (n < ?), ? ??????
????? ? ??????????????? ????????? ??????? (n ? ?); (3) ????????????
??????? ????????????? ??????????????? ???????, ? ?????? ????? ? ??????? ?????? ??????? ???????????????.
3) ??????????? ??????? ???????? ?????????????? ????????? ? ?? ?????
???? ????? ??????????? ??????????? ???? ? ??????????? ?????????????? ?????????. ? ?????? ???????, ??????????? ??????? ????? ???? ??????????? ????????????? ???????.
4) ??????? xk , x2k , . . . xnk , . . . ?? ?????????????????? x1 , x2 , x3 , . . ., ?????????? ??? ?????? ???????????? ? ???????????? ?????????????? ?????
???? ?????????????? ?????????, ?? ????, ? ??????????? k ???????? x(n?1)k
? xnk ????? ??? ????? ??????????.
5) ??????????? ??????? ? ?????? ???????? xn = ? (x0 , n) ? ????????????? ??????????????? xn+1 = f (xn ) ????????? ???????? ?????????????
??????????????? ??????????????????. ????????????? ?????????? ?? ??-
69
?? ????? ???????, ???????? ??, ??? ???????????? ??????? xn ????? ????
?????? ???????? ?????????? ?? ??????????????. ??????????? ???? ?????????????????? ???????? ? ????????? ???????? x0 ? ??????????????
f.
4.2
???????????? ??????
1) ?????????? ??????????? ??????, ?????????????????? ??? ?????? ?????????? ? ????????? ??????? (???), ? ???????????? ?? ???????????
?????? ?? ?????????. ????? ??????? ????? ?????????? ????? ? ?????
????????????? ????? ?????? (????????, ? ????????????? ? ????????
???????? ??? ???? ? ????????? ?????). ???? ?? ?????????? ???????????
??????? ?????????????? ???????? ????? ? ??????????????? ?? ?????????. ??????????? ???????, ??????????? ?? ???? ???????????? ?????????? ??????? (????????, x2 , sin(x), log(x)) ????? ???????? ????????????? ??????????????, ?? ???? ????? ????? ?????????????, ????? ?????????
?? ????????????.
2) ??? ??????????? ????????????????? ??????? (????? ??????????, ??????????????? ??????????, ???-???????) ????? ??????? ????????? ?????????????????? ?????????. ????? ??????? ???????? ???????? ???????????? ???????? (??? ???????? ???????) ?? ???????? ????????? ?????????
(??????? ?????). ????????????? ???????? ???????????? ???????????????? ??????????????? (????????????????? ? ????????? ????????) ? ?????????????? ???????????????. ????????????? ???????? ? ?????????? ?
????????????? ????????????????? ??????????????????.
3) ???????? ????????????????? ??????? ????? ????? (a) ???? ??? (b) ????????? ?????. ? ????????? ??????, ???????? ????????, ????? ??? ??????
????? (b1) ?????????? ??? (b2) ?????? ?????. ??????????? ????? ??????????? ?????? (? ????? ??????, ?????????? ??????? ?????????????
???? ?????) ? ?????? ????????????? ? ??????? ??????? ??????? ??? ?????? ?????????? ???????.
4) ??????? ????? ?????????? (????????, DES, AES) ????? ???????????? ????? ???????????? ????????? ????????????????? ??????????????. ??
????????? ???????? ???????? ????? ??????? ? ???????????????, ????????????????? ?????????????? ?? ???????????, ??????? ???????????? ???????????? ??????????? ? ??????????.
5) ??????? ??????????????? ?????????? (????????, RSA) ????????? ??
????????????? ???????? ?? ?????? ????? (?????????? ???????? ?????
?? ??????? ?????????). ?? ?????? ??????????? ?????? ?? ????? ????-
70
??????, ?? ????, ??????? ??????? ? ?????????? ???????????:
?? ???? ????????????????? ??????????? ??????? ? ?????? ????????
? ????????????? ???????????????. ? ????? ?????? ?????????????,
????? ????????? ???????, ??? ??? ????????? ???????? ????????????
??????? ?????????????????? ??? ?????????? ??????????????. ??????? ??????? xn = ? (x0 , n) ?????? ???? ????????????????, ??
???? ?????????? ?????? (????????? ??????? x0 ? ?????) ?? ?????????????????? x1 , x2 , . . . ?????? ???? ??????????? ?? ????????????.
?? ???? ????????????????? ??????????? ???????, ? ??????? k-???????
?????????????? xk = f k (x0 ) ????????????? ?????????????? ??? ??????????? ????????? (?????) ? ?????????? ??????? k. ?????, ???????
?? ??????????? ????????????? ????????? xnk+1 , xnk+2 , . . . , xnk+(k?1) ,
????????? ????? ???????? ?????????????? ????????? ?????????????????? xk , x2k , · · · , xkn , · · ·
6) ??????????, ??????????????? ?????????? ????????? ?? ????????? ????????? ???????????? ?????????????? ? «???????????????????». ??????? ????????? ??????? ????????????? ?? ????????? ??????? ????????????
(??????????, ??????????? ? ???????), ? ????? ????????? ? ???????? ???????????? ????????? (??? ?????? ????????????? ??????? mod ). ??? ???????? ?????? ??????? ? ?????? ?????, ????????, ? ???????? ?? ???? ????????????? ?????????????? ??? ?????????????? ??????.
7) ???????????? ? ?????? ?????????? ? ? ?????? ??????? ??????? ???????
???????????? ? ?????? ? ???-?????????????????? ???????? ? ????, ???,
???????? ?? ?????????? ????????????? ??????, ?????????????????? ??????????? ?????????? ?? ??????????? ? ???????????, ?????? ????? ???????
?????????????? ? ??????? ?? ????????? ???????.
4.3
?????????? ??????
??????????? ????????????? ??? ?????????? ???????????? ????????:
1) ????? ? ?????? ????????????????? ??????? ???????? ?????????????????
?????? ? ?????? ???????? ? ??????????????? ????????????? ?????????;
2) ????? ??????? ?????????????? ????????????????? (?????????????????)
??????????? ? ????????????????? ??????;
3) ????? ???????, ??? ??????? ??????????? ? ????????????????? ???????
???????? ??????????? ? ????????????????? ? ????????? ??????????????;
4) ???????????? ????????? ???????????, ? ??????? ? ???????? ????????? ??-
71
???????????????? ????????????? ????? ??????? ?????? ?????????.
5) ?????????? ??????? ???? ?????????? ?? ???? ???????? ????????????????? ?????? ? ??????? ??????????? ? ??????? ?????????? ???????????????.
72
??????????
[1] ?. ?. ????????, ??????????? ? ?????????? ????????: ????? ??????? ?
?????? ?????????, ???????????. ????? ????????. ??? 3. ?.: ???-?? ???.
2000.
[2] ?. ?. ??????, ?. ?. ????????, and ?????????? ?. ?., ??????????? ? ???????? ????????, ????????? ????, 2001.
[3] ?. ?. ???????? and ?. ?. ?????????, ??????????? ?????????? ??????????? ????????? ?? ???? ?????? ??????? ?????????????, ????????????????
??????? (1998), no. 15.
[4] ?. ?. ?????????? and ?. ?. ???????, ??????????? ???????? ??????????
????????, ????????? ????, 2000.
[5] ?. ???? and ?. ???????, ?????????????? ?????? ? ?????? ????????
??????, ???, ??????, 1982.
[6] ?. ??????? and ?. ????????, ???????? ????????. ????????., ???, 1990,
// Exploring complexity. An introduction. G. Nicolis, and I. Prigogine. W. H.
Freeman and Company, New York.
[7] ?. ???????? and ?. ???????, ????? ??????? ? ??????? ??????? ? ???????? ????? ? ???????????? ?????: ???????????? ????, ???????????
(2001), no. 46.
[8] ?. ?. ??????, ?????? ????, ??, 1953.
[9] ?. ?. ?????, ??????????? ???????? ???????????? ??????, ?????????,
??????, 1995.
[10] ?. ?. ????????, ????????????????? ????, ??????????? ??????????????? ?????? (1997), no. 6, 70?76, http://www.nsu.ru/materials/ssl/text/
metodics/anishenko.html.
[11] ??. ?. ???????, ???????????? ???????, ???, ??????, 1999.
[12] ?. ?. ??????, ?????? ?? ???????????? ??????, ???, ??????, 1999.
[13] ?. ?. ???????, ? ??????? ???????????, ???????????. ????? ????????.
(??????), vol. 3, ???-?? ???, 2000.
[14] ?. ?. ?????? (ed.), ???????? ? ????????????, ?????, ??????, 2000.
[15] ?. ?. ????????, ??????????? ? ?????????? ????????: ????? ??????? ?
73
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
?????? ?????????, ???????????. ????? ????????. (??????), vol. 3, ???-??
???, 2000.
?. ?. ??????????, ????? ??????????, ???????????? ?.-??????????????
????????????, 2001.
?. ??????, ????????????????? ????. ????????, ???, ??????, 1988, // H.
G. Schuster, Deterministic chaos: an introduction, VCH, Weinheim, 1988.
?. ????????, ?????????? ????????, ?????? ????????????? ????? ? ??????????? (??????????? ? ??????????), ??????????? (1998), no. 47, http:
//www.cplire.ru/win/InformChaosLab/chaoscomputerra/Loskutov.html.
?. ????????, ????? ??????????????. ?????, ???? ? ????? ??????, ???,
??????, 1999, // I. Prigogine, The end of certainty. Time, chaos and the new
laws of nature, The Free Press, New York, 1997.
?. ????????, ????????????????? ???? ? ?????????????? ??????????,
????? ? ????? (2001), no. 5, http://nauka.relis.ru/cgi/nauka.pl?07+
0105+07105044+HTML.
?. ??????, ????????, ????, ????????? ??????. ????????? ?? ???????????? ???, ???, ??????, 2001, // M. Schroeder, Fractals, Chaos, Power Laws.
Mintutes from an infinite paradise, W. H. Freeman and Company, New York.
??????? ????????? ?????????????, ????????? ????????????, 1969?1978,
http://www.rubicon.ru/.
A statistical test suite for the validation of random number generators and
pseudo random number generators for cryptographic applications, NIST, 2001,
http://csrc.nist.gov/rng/rng2.html.
?. H. ??????????, ?????? ?????????? ? ?????? ??????????, ?????, ??????, 1987.
M. S. Baptista, Cryptography with chaos, Physics Letters A 240 (1998), no. 1?2,
50?54.
E. Beham, Cryptanalysis of the chaotic-map cryptosystem, Proc. of EUROCRYPT?91, 1991, http://citeseer.nj.nec.com/175190.html.
M. E. Bianco and D. Reed, An encryption system based on chaos theory, US
Patent No. 5048086, 1991.
M. Blum and S. Micali, How to generate crytographically strong sequences of
pseudo-random bits, SIAM Journal of Computations 13 (1984), no. 4, 850?864.
G. Boffetta, M. Cencini, M. Falcioni, and A. Vulpiani, Predictability: a way to
characterize complexity, 2001, http://www.unifr.ch/econophysics/.
R. Brown and L. O. Chua, Clarifying chaos: examples and counterexamples,
IJBC 6 (1996), no. 2, 219?249.
L. Cappelletti, An fpga implementation of a chaotic encryption algorithm, Master?s thesis, Universita Degli Studi di Padova, 2000, http://www.lcappelletti.
74
f2s.com/Didattica/thesis.pdf.
[32] J. M. Carroll, J. Verhagen, and P. T. Wong, Chaos in cryptography: the escape
from the strange attractor, Cryptologia 16 (1992), no. 1, 52?72.
[33] Y. H. Chu and S. Chang, Dynamic cryptography based on synchronized chaotic
systems, Electronic Letters 35 (1999), no. 12.
[34]
, Dynamic data encryption system based on synchronized chaotic systems,
Electronic Letters 35 (1999), no. 4.
[35] F. Dachselt, K. Kelber, and W. Schwarz, Chaotic coding and cryptoanalysis,
citeseer.nj.nec.com/355232.html.
[36] F. Dachselt, K. Kelber, J. Vandewalle, and W. Schwarz, Chaotic versus classical
stream ciphers ? a comparative study, 1998, citeseer.nj.nec.com/article/
dachselt98chaotic.html.
[37] W. Ebeling, L. Molgedey, J. Kurths, and U. Schwarz, Entropy, complexity, predictability and data analysis of time series and letter sequences, 1999, http:
//citeseer.nj.nec.com/395066.html.
[38] T. Erber, T. Rynne, W. Darsow, and M. Frank, The simulation of random
processes on digital computers: unavoidable order, Journal of Computational
Physics (1983), no. 49, 349?419.
[39] M. J. Feigenbaum, The universal metric properties of nonlinear transformations,
J. Stat. Physics (1979), no. 21, 669?706.
[40] A. Fog, Chaotic random number generators, 1999, http://www.agner.org/
random/theory/.
[41] J. Fridrich, Discrete-time dynamical systems under observational uncertainty, J.
Appl. Math. Comp. (1993), no. 83, 181?207.
, Symmetric ciphers based on two dimension chaotic map, IJBC 8 (1998),
[42]
no. 6, 1259?1284.
[43] J. Fridrich and J. Geer, Reconstruction of chaotic orbits under finite resolution,
J. Appl. Math. Comp. (1995), no. 80, 129?159.
[44] P. Gacs, Lecture notes on descriptional complexity and randomness, Computer Science Department, Boston University, 2001, http://cs-pub.bu.edu/
faculty/gacs/Home.html.
[45] J. B. Gallagher and J. Goldstein, Sensitive dependence cryptography, 1996, http:
//www.navigo.com/sdc/.
[46] O. Goldreich, Introduction to complexity theory, Lecture Note, Department of
Computer Science and Applied Mathematics, Weizmann Institute of Science,
Israel, 1999.
[47] J. A. Gonza?lez and R. Pino, Chaotic and stochastic functions, Physica 276A
(2000), 425?440.
[48] H. Gutowitz, Cryptography with dynamical systems, ESPCI, Laboratoire
75
[49]
[50]
[51]
[52]
[53]
[54]
[55]
[56]
[57]
[58]
[59]
[60]
[61]
[62]
[63]
d?Electronique, Paris, France, 1995, http://www.santafe.edu/~hag/crypto/
crypto.html.
T. Habutsu, Y. Nishio, I. Sasase, and S. Mori, A secret key cryptosystem by iterating chaotic map, Proc. of EUROCRYPT?91, 1991, http://link.springer.
de/link/service/series/0558/bibs/0547/05470127.htm, pp. 127?140.
J. Hastad, Pseudo-random generators under uniform assumptions, Proceedings
22nd Annu. ACM Symp. on Theory of Computing, 1990, pp. 385?404.
M. K. Ho, Chaotic encryption techniques, Master?s thesis, Department of Electronic Engineering, City University of Hong Kong, 2001, http://personal.
cityu.edu.hk/~50115849/ces/.
S. Hollasch, Ieee standard 754: floating point numbers, 1998, http://research.
microsoft.com/~hollasch/cgindex/coding/ieeefloat.html.
J. Hosack, The use of chebysev mixing to generate pseudo-random numbers,
Journal of Computational Physics (1986), no. 67, 482?486.
R. Impagliazzo, L. Levin, and M. Luby, Pseudo-random generation from oneway functions, Proc. 21st Annu. ACM Symp. on Theory of Computing, 1989,
pp. 230?235.
E. A. Jackson, Perspectives in nonlinear dynamics, Cambridge University Press,
1991.
M. P. Kennedy, R. Rovatti, and G. Setti, Chaotic electronics in telecommunications, CRC Press, 2001.
D. Knuth, The art of computer programming - seminumerical algorithms, vol. 2,
2nd ed. Addison-Wesley: Reading, Massachusetts, 1981.
L. Kocarev, Chaos and cryptography, 2001, http://rfic.ucsd.edu/chaos/
ws2001/kocarev.pdf.
L. Kocarev, Chaos-based cryptography: a brief overview, Circuits and systems 1
(2001), no. 3, 6?21.
L. J. Kocarev, K. S. Halle, K. Eckert, and L. O. Chua, Experimental demonstration of secure communications via chaotic synchronization, IJBC 2 (1992),
no. 3, 709?713.
Z. Kotulski, J. Szczepan?s, K. G?rski, A. G?rska, and A. Paszkiewicz, On constructive approach to chaotic pseudorandom number generators, Proc. of the Regional Conference on Military Communication and Information Systems, vol. 1,
CIS Solutions for an Enlarged NATO, RCMIS, 2000, http://www.ippt.gov.
pl/~zkotulsk/CPRBG.pdf, pp. 191?203.
Z. Kotulski and J. Szczepan?ski, Discrete chaotic cryptography. new method
for secure communication, Proc. NEEDS?97, 1997, http://www.ippt.gov.pl/
~zkotulsk/kreta.pdf.
Z. Kotulski and J. Zczepanski, On the application of discrete chaotic dynamical
76
[64]
[65]
[66]
[67]
[68]
[69]
[70]
[71]
[72]
[73]
[74]
[75]
[76]
[77]
[78]
[79]
[80]
systems to cryptography. dcc method, Biuletyn Wat Rok XLVIII (1999), no. 10,
111?123, http://www.ippt.gov.pl/~zkotulsk/wat.pdf.
D. Lai, G. Chen, and M. Hasler, Distribution of the lyapunov exponent of the
chaotic skew tent map, IJBC 9 (1999), no. 10, 2059?2067.
L. A. Levin, One-way function and pseudorandom generators, Combinatorica 7
(1987), no. 5, 357?363.
L. Lova?sz, Computation complexity, Lecture Notes, http://ftp.cs.yale.edu/
pub/lovasz.pub/.
N. Masuda and K. Aihara, Finite state chaotic encryption system, 2000, http:
//www.aihara.co.jp/rdteam/fs-ces/.
R. Matthews, On the derivation of a chaotic encryption algorithm, Cryptologia
(1989), no. 13, 29?42.
A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of applied
cryptology, CRC Press, 1996, http://www.cacr.math.uwaterloo.ca/hac/.
V. I. Oseledec, A multiplicative ergodic theorem: Lyapunov charcteristic numbers
for dynamical systems, Trans. Mosc. Math. Soc. 19 (1968), no. 197.
N. Paar, Robust encryption of data by using nonlinear systems, 1999, http:
//www.physik.tu-muenchen.de/~npaar/encript.html.
V. A. Protopopescu, R. T. Santoro, and J. S. Tolliver, Fast and secure encryption-decryption method, US Patent No. 5479513, 1995.
V. Rijmen and J. Daemen, Rijndael algorithm specification, 1999, http://www.
esat.kuleuven.ac.be/~rijmen/rijndael/.
T. Ritter, Ciphers by ritter, 1991, http://www.ciphersbyritter.com/.
, The efficient generation of cryptographic confusion sequences, Cryptologia (1991), no. 15, 81?139, http://www.ciphersbyritter.com/ARTS/
CRNG2ART.HTM.
J. Scharinger, Secure and fast encryption using chaotic kolmogorov
flows, Johannes Kepler University, Department of System Theory, 1998,
http://www.cast.uni-linz.ac.at/Department/Publications/Pubs1998/
Scharinger98f.htm.
B. Schneier, Applied cryptography, second edition, John Wiley & Sons, Inc, 1996,
ISBN 0-471-12845-7, http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/
appl_cryp.htm.
C. E. Shannon, A mathematical theory of communication, Bell System Technical
Journal 27 (1948), no. 4, 379?423, 623?526.
, Communication theory of secrecy systems, Bell System Technical Journal 28 (1949), no. 4, 656?715.
M. I. Sobhy and A. E. D. Schehata, Secure e-mail and databases using chaotic
encryption, Electronic Letters 36 (2000), no. 10.
77
[81] M. Svensson and J. E. Malmquist, A simple secure communications system utilizing chaotic functions to control the encryption and decryption of messages,
Project report for the course ?Chaos in science and technology?, Lund Institute of Technology, Dept. of physics, Subdept. of mathematical physics, 1996,
http://www.efd.lth.se/~d92ms/chaoscrypt.html.
[82] J. Szczepan?ski and Z. Kotulski, Pseudorandom number generators based on
chaotic dynamical systems, Open Systems & Information Dynamics 8 (2001),
no. 2, 137?146, http://www.ippt.gov.pl/~zkotulsk/open.pdf.
[83] H. Waelbroeck and F. Zertuche, Discrete chaos, 1998, http://papaya.nuclecu.
unam.mx/~nncp/chaos98.ps.
[84] D. D. Wheeler, Problems with chaotic cryptosystems, Cryptologia (1989), no. 12,
243?250.
[85]
, Supercomputer investigations of a chaotic encryption algorithm, Cryptologia (1991), no. 15, 140?150.
[86] S. Wolfram, Random sequence generation by cellular automata, Advances in
Applied Mathematics (1986), no. 7.
[87] W. K. Wong, Chaotic encryption technique, City University of Hong Kong,
Department of Electronic Engineering, Hong Kong, 1999, http://kitson.
netfirms.com/chaos/.
[88] C. J. Wu and Y. C. Lee, Observer-based method for secure communication of
chaotic systems, Electronic Letters 36 (1999), no. 22.
[89] A. C. Yao, Theory of applications of trapdoor functions, Proc. of IEEE Symp.
on Foundations of Computer Science, 1982, pp. 80?91.
78
?????????? ?????????
????????????, 10
???????????, 10
?????????????, 10
?????? ????????, 29
?????????????????, 30
???????????????????, 30
?????????????, 30
?????????????????, 27
??????????, 26
???????????????, 31
??????????????, 27
?????????????, 27, 31
?????????????
???????????????, 41
??????????? ???????, 15
????????????? ???????, 38
??????????? ?????, 38
??????, 11
???????? ?????, 11
????????? ?????????????, 32
??????????????????
???????, 34
?????????????? ?????????, 31
??????? ?????????, 33
???????????????, 37
?????? ???????????, 65
??????????????
????????, 50
?????, 55
?????????? ??????????, 63
?????????? ????????, 64
???, 47
??, 32
????? ???, 26
??????????, 21
????????????, 12
???????????? ???????
????????, 22, 62
????????????, 21
???????????, 18
???????????, 18
? ?????? ????????, 60
???????????, 21
?????????? ????????, 20
????????? ???????????, 62
????????, 28, 33
???????????-?????, 35
???????, 33
????????, 33, 35
????????????, 21
????, 18, 27
????????, 22, 62
???????????, 18
?????????? ??????????, 22
???-???????, 38
????? BPP, 30
????? NP, 30
????? P, 30
????????? ???????, 64
????, 12
??????? ????, 39
????????????, 10
79
????, 30
???????????, 16
?????? ??????, 10
?????????????, 51
?????????????, 60
??????????, 56
??????, 65
RANROT, 63
??????????, 27, 44
???, 47
??????????????? ?????????, 16, 39
?????????????????, 27
????????? ????, 40
??????????? ????, 40
???? ????????, 40
??????????, 16
????? ??????????, 12
?????????? ????????, 35
?????????, 27, 28
???????????????, 31
????????????, 32
??????????????????, 31
??????????, 36
???????????, 27
???????????????, 27, 28, 31
???????????????, 41
????????, 26, 33
????, 12
???????, 15
?????????????, 13
???????, 13
???????????, 44
??????????????, 57
?????????, 13
????????????, 13
??????????, 12
??????????, 12
??????????, 11, 18
????????????? ????????, 37
???????????, 37
???????????????, 38
???????????????, 38
80
0.6
0.8
1
???. 3.13. ?????????? ??????????????.
3.2.5
?????????? ??????????????
?????????? ?????????? ?????????????? ?????? ????????
a · xn , 0 ? xn ? a
xn+1 =
,
1?xn
a < xn ? 1
1?a ,
(3.6)
??? ???????? a ?????? ???????? ??????? ????? ??????? (???. 3.13).
?????????? ?????????? ???????? ??????? ?? ????????? a ? ????????????
???????????? ? (a) = ?a ln (a) ? (1 ? a) ln (1 ? a) ????? ??? ???? x0 ? (0, 1) [64].
????????, max ? (a) ? 0.693 ??? a = 0.5.
a?(0,1)
?????????? ??????? ????? ????????????? ??????? [61]
xn =
1
arccos (cos 2n ?x0 ) .
?
(3.7)
??????? et al. [49] ?????????? ??????? ????? ?????????? (???. 1.3) ?? ????
????????????? ??????????? ??????????????
a · xn ,
rn = 0
xn+1 =
,
n ? [1, N ] .
(3.8)
(a ? 1) xn + 1, rn = 1
??? ri ? {ri }N
1 ? a ? [0.4, 0.6]. ????????? ???? ??????? ?? ????????? a (? ??????? ? ????????? ???????) ? N -??????? ?????? {ri }N
1 . ?????????? ??????????
????? N -???????? (N = 75) ?????????????? ????? ????????? ?????? ? ??????????. ?????? ????? ????????? ?????? ? 64 ????, ??????????? ? 147 ???. ?????
56
???. 3.14. ????????????? ????? ??????????
???????, N ????????????????? ?????????????? ???????????? 2N ????????? ????????? ?????????? ?????? ????? ??????.
??? ????? [26] ???????, ???? ???? ????? ???? ????? ???????? ??? ?????
? ????????? ???????? ???????, ? ????????? ????? ??? ????????? ????????
?????? ?????????? K = 238 .
3.2.6
?????????????? ????
???????????? [72] ????????? ???????????? m ?????? ??????????? ?????? ???
????????? ??????????. ????????? ????????? ??????? ??? m ?????? ????????
??????. ?? ?????? ??????? ????????? ????? xn ? ??????? ? ????????? ???????, ?? ???????? ??????????? ???? ??? bn , ????? ???? ??? m ????? ???????????
? ???? ??? b ????????? XOR. ?????????? ??? b ???????? ?? ????? ??????????. ??????? ??????????? ??? ????????? «???????????? ????????» ???????????
?????.
????? ???????????? ????? ???? ??????? ????????? ???????:
1) ????????? ????? ?????? ??????? ????? ??????????? ? ?????????? ????????. ??????? ???????, ??????????? ??????? ????? ???????? ????????
??? ?????? ?????? q-?? ????????. ??? ????????? (???????????) ??????? ?????????? ????? ?????????? ?????????????????? (?????? 2.6).
2) ????? ??????????? ?????? ????? ???? ??????????????? ? ????????????
??????? ????? (??? ??????).
3) ??????? ????? ???????????? ? ???????????? ? ????????? ????????? ???-
57
?????, ????????? ?? ????? (???. 3.14).
? ?????? ????????? 1, ????????????????? ??????? ???????????? ?????
???????? ? ???? ???????
? 1
xn+1 = f1 (x2n , k 1 ),
b1j = ?1 (x1qj )
?
?
? 2
xn+1 = f2 (x2n , k 2 ),
b2j = ?2 (x2qj )
···
···
?
?
? m
m ), bm = ? (xm )
xn+1 = fm (xm
,
k
m qj
n
j
bj = b1j ? b2j ? . . . ? bm
j ,
???
f1 , f2 , . . . , fm ? ???????????? ???????, ???????????? ? ??????? ?????? ?????;
m
1 2
m
hx10 , k 1 , x20 , k 2 , . . . , xm
0 , k i ? ????????? ???????; bj , bj , . . . bj ? ???????? ????
?????? ? (n = qj)-?? ?????? ???????; bj ? ???????? ??? ??????????.
??????????????? ????????? ?? ?????????? (1)-(3) ??? ?????????? ? ?????????? ? ?????? ???? ??????. ??? m = 5 ? q > 20 ???????? ??????????????????
?????????? ??????????? ?? ?????????. ??? ?? ????? ??????? ????????? ? ??
???? ????????????? ??????? ????????????? ???? ??????? ???. ? ?????????,
??????????? «??????????» ?????? ? ?????????? ?????????? ? ????. ??? ?? ???????? ? ???????????? ????????? ???? ??????? ??-?? «m-???????? ??????????????», ?? ???????? ????? ????????? ??????????????? ??????????.
3.2.7
?????? ??????????? ?????
??????? et. el. [45] ?????????? ??????????? ????????? ???? ?? ?????? ??????????????
x
1 a
f (x) = a +
x ? (0, 10) , a ? [0.29, 0.40] .
x
?????? ???????? ?????????? ?????????? ????????? x0 ? ????????? a. ?????
n0 = 200 ????????? ????????, ??????? ??????? ???? ????????? ?????? p1 ?
???-?????????? c1 = f n0 +p1 (x0 ) (32,64,128 ???), ?? ???? ?????????????? f
??????????? ??? (p1 ? [0, 255]) ???. ??????????? ????? ????????? ?????? ????????? ? ??????? ??? ?? ?????????? (???. 1.4-c):
ci = f n0 +
Pi
k=1
pi
(x0 ) .
???????????? ????? ????? ?????????? ????????: (1) ???????????? (8 ?
10-?? ???????) ?????????? ??????? ??????????? ?? ????????? ? ???????? ???????; (2) «??????????» ??????????, ?????????? ?????? ?????????????? ?? ????
???.
58
???????? [25] ? ???? [87] ?????????? ????????? ??????? ??????????, ? ??????? ???????? ????? ?????????? ?????? ????????. ???????????? ????????? X
??????????? ?? m ????????????????? ??????????? {X1 , X2 , ..., Xm } (??????????? X ????????? ??? ????????). ??????? ???????????? ????????????? ?????????? ?????? ????????? ??????. ????? ????????????? ????????? ?????????
????????, ??????? ???????? ??????, ??????? ?????????? n0 ????????. ????? ???
??????? ????????? ?????? ????????????? ? ?????????????????? ????? ?????,
?????? ????? ???????? ??? ?????????? ???????????????? ????????????:
ci = ni ? ni?1 ,
i = 1, 2, . . . ,
??? pi = ? (Xi ) , f ni ? Xi . ?? ???. 1.4-b ???????? ?????????? ?????????????
?? ????????? ????????. ??? ??????? ????? ?????????? ????? ???? ????????? ????? ???????? ?????????????? ?????????? (????????, ??????????? ?????
????????).
????????, ??? ????????????? ????????????? ???????? ????????????? ? ??????????? ???-?????? ??? ?????????? ?????????????? ??????????: (1) ??????? ????????? ??????????? ???????????? ???????? ci = ni ? ni?1 , ??? ??? ??
????? ???????? ?????; (ii) ?????????? ? 2-3 ???? ??????, ??? ???????? ?????.
?? ????????? ???????????? ?????? ???????? ? ????? ? ?????? ??? ?????????????? ? ???????????????. ??????????? ?????? ??? ????? ????????? ??????
? 4 ????, ? ????? ??????????? ? 10 ???. ? [51] ?? ????????? ????????????
??????? ??????????? ????????????: ??????? ?????????, ????????????? ?????????? ? ??????????????? ?????????.
?????????? et el. [62, 63] ??????????? ????? ?????????? ?????? ? ????? ?
???????????? ? ?????????? ???????? ???????????? ???????? ??? ????????????????? ??????. ?????????? ?????????? ????????????????? ?????, ? ???????
?????????? ?????????????? m-??????? ?????????? ????????? ??????????????
f ?1 (???????????? ? ????????????), ? ???????????? ? m-??????? ??????
??????????????? f . ???? ???????? ? ????????? ???????? x0 ? k. ??????????
f ? f ?1 ?????????????? ??? ?????? ???. ? ???????? ??????? ??????????? ??????? ?????????? ????????????? ??????? ????????? ??????????????? ???? ?
????????. ??????? ???????? ????? ????????????? ? ??? ?????????? ? ????,
???????????? ??????????? ????.
??? ?????????? ????????????????? (????? ?????????, ????????????, ?????????) ????? ???????????? ??????? ???????????????? ????????? ????? ???????? ??????? ? ???????????. ????????, ???? [71] ????????? ????????????
59
?????? ?????? ??? ?????????? ??????
2
dx
dx
dx
d2 x
s ign
? ?2 s ign
? ?21 x ? ?23 x2 =
m 2 ? ?2
dt
dt
dt
dt
?2
= L 0 cos (?0 t) ? ?21 e?21 t ? ?22 e?22 t ,
2?
??????? ????????????? ??????? ??????? ? ?????????????? ?????? ?21 ? ?23 .
?????? ????? ????????????
????? ????????????? ????, ????????? ?? ??????? ?
?????????? L ?02 /2? ? ???????? ?????, ???????? ???????????????? ???????????.
?? ??????? ??????, ?? ????? ????? ??????? ?? ??????????? ? ???? ????????
????????? ?????????? (?? ?????? ???? ?? ???????? ??????). ??? ???????????,
??????? ???????, ??????? ????????? ??????????????? ? ????????????? ?????????????? ????????? ??????????.
3.2.8
??????? ? ????????????? ???????????????
? ?????? ????????
? ?????????? ???????? ?? ??? ??????????? ?????? ??????? ??? ????????????? ? ?????????? ??????. ?????? (?????????????) ??????? ????????? ????????? ???????????? ???? xn ?????????????????? ????? ?? ????????? ??????? x0 ,
????? n-??????? ?????????? ???????????? ???????. ?????? ??????? ????????? ???????? ?????????? ?????? ? ??????????? ???????? ???????? ??????????.
?? ???. 3.4 ?????, ??? ??????????? ????????? ?????????????????? ????????????? ???????, ?????????? ??? ?????? ???????????? ? ?????? ??????????.
??????????? ??????????? ??????, ????????????? ????????????? ? ????????????, ????? ?????? ???????. ?????? ???? ???? ?? ????????????? ? ??????
?????????? ?, ????????, ???? ?? ??? ???????? ?????????????. ????, ??? ??????? ?????????? ????????????, ???? ??????? ????????????????? ???????? ?????
???????? ????? ??????? ??????????.
?????? ??????? ??? ???????????? ??????? ????? ???? ???????? ? ?????
[47, 61]
xn = ? (?T ?n ) ,
(3.9)
??? ? (t) ? ????????????? ??????? ? ???????? T ; ? ? ????? ?????; ? ? ? ????????? ?????????????? ????????, ???????????? ????????? ??????? ?? ?????????
x0 = ? (?T ) .
??????? ???????? ???????????, ???? ? = ln ? > 0.
60
???. 3.15. ????????????? ?????????????? xn+1 = f (xn )
?????????? ??????? ? ?????? ????????, ???????? ??????????
xn = sin2 (???n ) .
(3.10)
?????????????? f : xn ? xn+1 ??? ????? ??????? ???????????? ??????????
?
xn+1 = sin2 (? arcsin xn ) .
(3.11)
? ??????? ?? ??????, ??????????????? ?????, ?????????????? xn+1 = f (xn )
????? ????? ???? ?????????????, ? ?????????, ????? ? ? ?????????????? ?????.
??????????????? ????????????, ??? ????????? ???????? xn ????? ??????????????? ?? ????, ? ????????? ????????? ??????????? ????????? xn+1 . ?? ???. 3.15
??????????? ?????? ?????????????? ?????????????? (3.10) ??? ? = ? 1/3 .
??????????? ??????? ? ?????? ???????? ? ????????????? ???????????????
???????????? ??????? ??????? ??? ????????????. ? ????? ???????, ?????? ??????? ????????? ???????? ?????? ? ????????????? ????? ??????????????????,
?????????? ???????????? ????????? ???????? (???????). ? ?????? ???????,
???????? xn?1 ? xn+1 ?? ????? ???? ????????? ?? xn , ?? ???? ????????? ?????
???? ??????????????? ? ???? ???.
??????? xn = ?(?, ?, n) ?????? ???? ????????????????, ?? ???? ?????????? ????????? ??????? x0 ?? xn ?????? ???? ??????????? ???????????.
61
????????? 3.10 ???????????? ? ? ? ??? ????????? xn ????? ???????????? ????????? ???????. ?????????????? xn ? ?????? ? ???????????? ? ?????????? (X0 , X1 )
???? ????? ???????? ????????????????, ??? ??? ??????? ? ??????? ??????? ??????????. ??????, ????????????????? ??????, ??? ????????? ?????????? ?????????? ??????? ????? ??????? ??????????????? ????????????.
?????????? ??????? ??????? ????? ???????? ???????? «???????????????????». ??????? ???????? ????????????? ?? ????????? ??????? ??????? (??????????, ??????????? ? ???????), ? ????? ????????? ? ???????? ???????????? ????????? (??? ?????? ????????????? ???????, ????????, sin, mod). ??? ????????
? ????, ??? ????? ??????????????????, ??????? ????? ???????? ?? ?????? ?
???????? ????????? ??????????, ???? ??????????. ????? ???????, ???????????
??????? ? ?????? ???????? ???? ????? ???? ???? «????????» ???????????????. ????? ????, ??? ??????? n ? ?????????? ????????????? ?????????? ????????????? ???????????, ?????????????????? ????? ??????????? ?????????? ??
??????????? ? ????????? ???????? ????????.
?????????? et al. [61] ?????? ??? ?????? ?? ????????????????? ??? ?????????
????????? ??????????? ?????? ? ?????? ???????? ? ????????????? ??????????????? (? ?????????, (3.10)). ?????? ??????? ?? ????????? ????????? ??????????? ????????? ??????????????? ?????, ?????????? ???????????? ???????????
????????????. ? ?????????, ?????????????? ???????? ?????????????????? ?????? ???????? ? ??????????? ?? ????????? ???????. ?????? ?????????? ????????????????? ??????? ? ?????? ???????? ? ???????????? ??????? ??????????????? ????????????.
3.3
3.3.1
???????? ??????????
????? ????????
? ??????? 1.2.6 ?? ???? ??????????? ?????????? ??????????? ???????, ???????????? ?? ????????? ??????????? ???????? ????? ?. ?????????????? ?????
??????? ?????? ???????? ???????? f : ? ? ?.
????????????????? ??????? ????????? ? ???????????? ????????? ?? ???????? ????? ?, ???????? ????? ????????????, ?????????? ??????????????????.
???????? ????????????????? ??????? ?? ????????? ????????? ????????? ???????????????? ??????????????, ?? ??? ?????????? ??????? ??????????? ??????? ?????????? ???????? ????????????? ?????????.
??????????
??? ???????? ????????????????? ???????
?????????? ????????
m
hA, f i, A ? ?m |? ? {0, 1}
c ???????? ????? ????????? 2m ????????????
??????????
62
1
log dH f n (?0 ) , f n ?00
n?? n
0
??? ?0 ? A ?????, ??? dH (?0 , ?00 ) = 1.
? «???????» ????????????????? ??????? ? n-??????? ??????????, ????????
?????????? (? ??????? ? x0 ? x00 , ????? ??? dH (x0 , x00 ) = 1) ???????????????
??????????, ? ???????, ?? hdH i = m/2 (???. 3.3-b).
??? ?????? ???????????? ??????? ? ???????? ?????? ?????????, ????????????????? ??????? ???????? ?????????????. ????????? ?????, ? ??????? ?????????? ????? ???? ??????, (?? ????? ????? ????? ????????? ???????????? ?????????),
???????? ?????????. ????????, ????????? ? ???????? ???????? ?????? (LFSR)
? (?0 ) = lim
xn = (c1 xn?1 + c2 an?2 + · · · + ck an?k ) mod 2
??? ???????????? ????????? ????????????? ci ???????? ????????? [75].
?????? ???????? ????????????????? ??????? ????? ??????, ????? ???????
??????? ?? ????????? ???????. ???, ??? (Fog, [40]) ?????????? ??? ??????????
?????????????? RANROT. ??? ?????????????? ?????????? ?? ????????????? ??????????? ?????????? ???, ??? ????? ?????????????? ?????:
xn = (xn?j + xn?k ) mod 2b rotr r,
??? xn ? {0, 1}b , r ? [0, b/2) ? ????? j, k ?????????? ? ???????????? ? ????????? ?????????. ????????? ???????? ???????? ?????????????? ??????????
? ???????? ????????????? ??????????????? ??? ??????????? ??????????. ???
??? ???? ????????, ?????????? ????? ?????? ?????? ???, ??? ?????????? ??????????? ????????? ?????????. ??? ??????? ????????? ?????? ??????????? ?
??????????? ????????? ???? ?????? (?? 1000 ????????) ????? ??????? ??????
?????????????????? ??????????.
3.3.2
?????????? ?????????? ??????????????
?????? et al. (Masuda, [67]) ??????????? ????????????? ?? ???? ?????????? ?????? ??????????? ??????????? ?????????????? (???. 3.16)
( M jA X ,
k 1?X?A ,
F (X) =
M
M ?A (M ? X) + 1 , A < X ? M
??? X, A = 1, 2, ..., M ? bc , de ? ?????????? ? ??????? ? ??????? ?????? ??????????????. ????????? ??????? ????????????? ???????? ???????? ???????, ?
?????????????? ????????? ?????????? ??????????. ?????? ???????? ????????
63
???. 3.16. ?????????? ?????????? ??????????????.
A. ?????????????? ??????????? N ???. ????? ??????? ??????????? ????????
N , ??? ??????? ??????? ?????????? ????????? ?????? ????????? ? ????????????????? ?????????????.
3.3.3
????????? ????????
???????? (Wolfram, [86]) ??????? ???????? ?????????? ????????? ???????
??? ????????? ??????????????? ?????. ????????? ??????? ???????????? ???????? ?????? (?????)
b = (b (1) , b (2) , . . . , b (n)) ? {0, 1}n .
???????????? ??????? f : {0, 1}n ? {0, 1}n ?????? ??????????
b(i) = b(i) ? 1 xor b(i) or b(i + 1) ,
??? ???? 1 ? i ? n. ?????? ??? ????????? ???????????, ?? ???? b (n + 1) = b (1).
??? ???????? ??????????? ???????????, ? ?? ????? ???????? ?????? ???? ???
bk , k ? [0, n].
?????? (Ritter, [75]) ????????, ??? ?????????????????? ?????? ?????????? ???????? ???????????????, ??????, ????? ??????? ??????????? ? ??????????????.
??? ???????????? ??????? ?????????? ??????????, ????????? ?? ???????? ??????????? ? ??????????? ?????????? ?? ????? ?????????? (???????? ??? ??????? ???????? ???????).
???????? (Gutowitz, [48]) ?????????? ??????? ??????? ????? ??????????
?? ???? ????????? ?????????. ???? ????????? ?????? (512 ???) ?????????????
? ???? ??????????? ????????? ???????? ??????? (578 ???). ???? (1088 ???),
????????? ?? ???? ?????? ?????????? ??? ?????? ????? ??????????, ??? ?????????? ????????? ????-?????. ???????????? ??? ????????, ?????? ?? ???????
64
1
nk
...
n2
0
n1
n2
...
nk
0
1
n1
???. 3.17. ?????????? ?????????????? ??????.
???????? ??? ???????????. ? ???? ???????, ?????? ??????????? ???????? ???? ??????????? (s-box) ? ????????????? (p-box). ????? ???????, ??? ????? ?????????? ???????????? ??????????????? ??? ???????????, ? ??? ?? ????????
?????????? ? ????????????????? ?????????????.
3.3.4
?????????? ?????????????? ??????
????????????? ? ????????? ?????????????? ?????? ???? ????????? ????????????? ? ???????????? ??? ???????? [79]. ?? ?????????? ????????? ???????
?? ???? ??????????? ?????????????? ??????, ??? ?? ?????????? ???????? ???????????.
?????????? ????? ????? ??????????? ?? ???????????? ?????? ? ????????????
? ?????????? ? = {n1 , n2 , ..., nk }. ?????? ?????? ?? ??????????? ?????????????
?? ????? ??????? ????????, ? ?? ????????? ????????? ?? ???????? ?????? ni ,
??? ???????? ?? ???. 3.17.
??????? ?? ???? ?????????????? ?????? ????????? ???????????????? ???????????????? ?? ????????? ? ????????? ???????? ? ????????? (????????? ?).
???, ????? 6 ????????, ???????????? ???????? ?? ?????????????? (???. 3.18).
?????????? ?????????????? ?????? ????? ???? ??????????? ??? ??????
????????? ??????????. ????? ???????????? ??????? T? ?????? ?? ??????? ??
N ?????????:
T? : {0, 1}N ? {0, 1}N
????? ????? ????? {n1 , n2 , ..., nk } ?????????? ???, ??? ?????? ????? ni ?????
??? ??????? N ? ?????? n1 + n2 + ... + nk = N . ?????????????? T? ?????? ?????
65
???. 3.18. ????? ???????? ?????????????? ?????? c ?????????? ?
{0.25, 0.5, 0.25}, ??????????? ? ??????????? [76].
=
??????? ???????? ??????? ? ???????????? (r, s):
N
N ni
N
T? (r, s) =
(r ? Ni ) + s mod ,
s ? s mod
+ Ni ,
ni
ni N
ni
??? r, s ? {1, 2, ..., N } , Ni = n1 + n2 + ... + ni , i ? {1, 2, ..., k} ? Ni ? r < Ni + ni .
?????????????? T? ???????????? ?????? ??????????? ????????????, ?? ?? ?????? ?????????????? ???????? ????????? ??????. ????? ???????, ? ??????? ?????
?????????? ?????????????? ?????? ????? ???????????? ??? ??????????? ????
???????????? (p-box), ? ??? ???? ??????????? (s-box) ?????????? ?????????????? ??????????????, ?????????????? ???????????.
???????? (Scharinger) [76] ? ??????? (Fridrich) [42] ??????????? ???????
????? ?????????? ?? ???? ?????????? ??????. ????????????? ???????, ???
????????????????? ??????? ????????? ?????????? ???????????? ????? ???????? ???????, ????????, ???????? ???????????. ? ??????? ???????? ??????????
????????, ??????? ???????? ????????? ??????????????? ?????? ?? ???????????. ??? ??????????????? ?????????????? ?????????? ??????????????? ????????????? ??????????? ??? ????? ?????????? ????????. ?????????? (?? ???? ???????????? ??????????? ????? ?????? ????? ????????? ?????? ? ????? ?? ????
??????????????????? ???????????) ?????????????? ??? ?????? ???????? ???????? ? ???????? ???????? ?????? (LFSR) [75]. ??????????? (Cappelletti, [31])
?????????? ?????????? ?????????? ????? ?????????? ????????? ?? ???? ??????????????? ??????????.
66
3.3.5
?????????? ? ???????????? ??????????????
??????????? ????????????????? ??????? ???????????? ????? ???????? ??????????, ?? ???? ??????? ? ???????????? «??????????? ????????» ? ?????????????? ??????????????? ?? ????????? ??????? ?????.
??????????????? ??????????
? ??????? 2.6 ?? ??? ???????, ??? ??????? ???????? ???????????? ????????? ??????????????? ????? ???????? ?????????? ???????? ??????????? ??????? ?? ???? ????????????? ??????????????. ??????, ?????? ????????????????
? ????????? ????????, ????????????????? ????????? ?????????? ????????????
??? ????? ?????? ?????????? ? ?????????????? ?????????????????? ?????????????? xn+1 = f (xn ). ? ???????????? ???????????? ??? ?????????????????
??????????? ?? ???? ?????????????? ????????? ?????? ? ?????? ?????.
????????, ????????? Blum-Blum-Shub [69, 75] ???????? ?? ???????? ?????????? ???????? ????? ?? ?????????. ???????????? ??????? ?????? ??????????
xn+1 = x2n mod M,
??? M = pq, p, q ? ??????? ?????, ???????????? 3 mod 4. ???????? ??? ?????????? bn = ?(xn ), ??? ?(xn ) ? ???????????????? ???????, ?????? ??????????
???? xn .
???????????? ?????? ????? ???? ??????? ? ? ?????????? ????????:
1) ??????? ????????????? ? ????????? ??????????????, ?????????????? ?
???????????? ?????????.
2) ?????????? ?????????? ????? ???????????, ??????????? ?????????????? ?????????? ?????????????? ????????? ?????????????????? (????????????? ????????? ?????????? ??? ???????? ???????????).
???????????? ??????? ?????
??????? ??????? ????? ???????????? ????? ???????????? ?????????? ???????????, ??????????? ??????????????. ??????????????? ??? ?? ??????? ????? ?????????? ??????? (Rijndael, [73])2 . ??????? ???????? ????????????,
????????????, ??????? ??????. ????????? ????????????? ?????? ?????????
???????? (????????) ?????. ????????? ????????? ??????? ???????? ????????
???????. ??????????????? ???????????? ??????? ????? ??????:
2
???????? ??????? ? 2001 ???? ?????? ? ???????? ????????? AES (Advanced Encryption
Standard), ????????????? ?????????? ??????, ???????????????????? ?????????? ????????????? ???. ????????, ?????? ?????????? ??-????? ? ? ???????????? ???????.
67
1) ????? ??????????? (s-box), 
Документ
Категория
Без категории
Просмотров
13
Размер файла
2 226 Кб
Теги
криптография, 2002, птицин, pdf, хаоса, детерминированного, теория, приложение
1/--страниц
Пожаловаться на содержимое документа