Документ взят из кэша поисковой машины. Адрес оригинального документа : http://iisi.msu.ru/UserFiles/File/publications/mabit04.pdf
Дата изменения: Mon Apr 2 16:24:06 2012
Дата индексирования: Fri Feb 28 20:16:26 2014
Кодировка:

. .

2829 2004 .

2005

32.816 34

. 34 2829 2004 . -- .: , 2005. -- 384 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

: «-» «» « ""» « ""» «-» «» «» «- »

. . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Scott D. Stoller, Yanhong A. Liu. Security policy languages and enforcement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 32 65 91

2829 2004 .
. 119002, , ., 11. 01335 24.03.2000 . 15.09.2005 . 60 в 90/16. . 24 . . 500 . . «». 248640, . , . , 5.

99 118

« »
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

ISBN 5-94057-212-X

9 785940 572121 >

© , 2005. © , 2005.

4

5

. . , . . . . . . . . . . . . . . . . . . . . . . . . 141 . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 . . . MV2 . . . . . . . . . . . 156 . . . - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 . . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 . . , . . , . . . . . 177 . . . . . . . . 185 . . . YAQS -- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 . . . (n, m, k) - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 . . . VR . . . . . 209 . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 . . . (superimposed) . . . . . . . . . . . . . . . . . . . . . . . 217 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 . . , . . . « » . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 . . . p - 1 243

« »
. . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 . . . . . . . . . . . . . . 257 . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 . . . . . . . . . . . . . . . . . . . . . . . . . 273 . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 . . , . . , . . , . . , . . , . . . - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 . . , . . . : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 . . , . . . «Linux over » . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 . . , . . , . . . . . . . 326 . . , . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

6

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

, 28 2004 .
, . . . - (SUNY) , - . (Dr. Elizabeth D. Capaldi) . , - .-. , . . . : . . , . . , . . . . . . , . . . . . . . , . . . . . . , . . , . . . . . . . , . . , . . , . . . . . . , . . , . . . . Scott D. Stoller, Yanhong A. Liu. Security policy languages and enforcement. Tzi-cker Chiueh. Program semantic-aware intrusion detection.

8

9

, 29 2004 .
« » -- . . , . . . . , . . , . . . . . . . . . . . VR. . . . . . . . . . . . , . . . . . . , . . . « » . . . . . . . , . . , . . . . . . . MV2. . . . (n, m, k) - . . . . - . . . . , . . , . . . .

. . . . . . . YAQS -- . . . . p - 1. . . . . . . . side channel attack . . . . 3- . : . . . . . . . . . . , . . . Z2k . . . , . . . . . . . , . . . . . . . . . . . . (superimposed) . « » -- . . , . . . . , . . . . . . . . . . , . . . .

10

. . , . . . . E. Rich. An emerging perspective on the dynamics of insider cyber threats. . . . , . . , . . , . . , . . , . . , . . . - . . . , . . . : . . . . . H. G. Berg. A teaching Hospital Approach to identifying risks, research problems and teaching materials in information security. . . . , . . . «Linux over ». . . , . . , . . . . . . , . . , . . , . . . . . . . . . . . , . . . . . . . . . . . . . . , . . , . . . Linux: , , .

. .
!
« ». , . , . , . , , - -, - . , , . , , , . , , . , , , , . -

12

. .

...

13

- . . , , , , , , . , . , , , , . , . , . , - . , , , . , , , . , . , , . .

. . , , . « », , . -, , , . , , . 1. , . , - , . , , . 2. , , - ; , ; , , , , . .

14

. .

...

15

- . , , . . 3. -- , , . , , . 4. - , . - . . - , « ». 5. , , , , , . 6. , , . · ,

· -- , , , · , , -- , . , - . , , : « -- , , ». , . , , ( - , , , , ) , . . . - . - , , . (, - , ) - , - . , -

16

. .

...

17

() , . . , , , , , . , , . - , , - . , , . , . 9 2003 . . -- , : · ; · ; · . - , - , , .

- . . « », -. , , . -- , . . XXI . , , , . , , XXI , . , . . . , , , IT-- . , , .

. . , . .
. -- , . , , , () , , . , . m (. [1, . 126] ) . , () Z/mZ. , . , (. [1, . 125] ) . (, RSA -, . [1, . 310] ) , , . , , . . , , , , . - , - .
-2358.2003.9.

20

. . , . .

21

, , , . . , , , , , . . , , . , [43] , [27] [28] . S () , A () , Sn , An = {1, . . . , n}. , = {0, . . . , 2m - 1}. +, · 2m , , GF (2m) an-1 2n-1 + . . . + a1 2 + a0 , ai {0, 1}, (an-1 , . . . , a1 , a0) GF (2m) .

1.
. . . , , DES AES. . [40] [12] . , [40] , g Sn ( , n = 4 g ) Sn h, g Sn . , Sn , . [39] , Sn Sn An

1 n . 1 m [33] . , Sn . An Sn . n = 2m . . 1. 197576 . . . n, 2m - 2m < n - 1. [30] ( ) , 2m = n - 1, n. , , 2m = n An , PGL (2, p) p = 2m - 1 > 3. 2. n = 2m , 2m-2 -, An . (. . , ) . 3. .. 12 [7] , P = GF (2m) , g = (0, 1, . . . , 2m - 1) - h (P , ) GF (2) , S (P) . h : k в (n - k) k = 1, . . . , n. 4. , , DES AES, () , . [41] , [42] . , [38] , , DES , . Sn , An M , M. . n 64 ( ) [31] . [27] . , . . . . , . . n < 1000 (. . [28] ) .

22

. . , . .

. [29] ,
n2 n - -1 3 3

23

, , 2m , .

L (Sn , { g , h})

2. ,
, : L (G , M) -- G M, . . t , G = M1 . . . Mt ; d (G , M) -- G M, . . d , G d Ms . k- , , dk (M) -- k- M, . . r , Mr k- ( r ) . , L (G , M) dk (M) M G G . Sn An . . [12] , [17] . . 1. G = M -- , M, M2 , M3 , . . . G H , H -- G , M ; d (G , M) = [G : H ] [6] . 2. G M M [6] . 3. Sn An [37] , : An < G < Sn , G = M M-1 = M, max L (G , M) exp (n log n)
1/2

L (Sn , { g , h}) , 3n2 /4, [21] . : L (Sn , M) n2 , |M| = 2 ( n < 8, . [32] ) . 5. [21] , [29] , n log2 n, . M G , L (G , M) |M| . ( ) k- Sn ( k > 1) , . . [16] . [6] , [7] , [35] Sn , . Sn M 2- M. : L (Sn , M) d2 (M) · n.

4n 2 n 5 --. 3 2 6

3.
( , ) H S () , H |H | = ||. . , . , , , DES AES, . . . ,

(1 + O (1)) .

4. Sn g = (1, 2, . . . , n) , h = (1, 2) . . . [15] 2n2 .

24

. . , . .

25

2- , , H . , 2- H . , 2- Sn , n ( . ., ) . , 2- . [8] , 2- m fh, m -- (P , +) , f -- P = GF (2m) , f (x) = x - 1, x = 0, f (0) = 0, h Aut (P , +) . , AES. [6] , [7] D GF (2m) , m > 1, 2- 4- 5- m D , m -- , g = (0, 1, . . . , 2m - 1) . [9] 2- AES. 84n , n = 4, 6, 8, 5, 6, 7. : , , G1 , G2 , 2-. (. [7] ) . , 2-, : · n 23 pq , p , q -- ; · ; · 2- . , . : GH 2- ( ) G , H Sn .

4.
. , , , . , , , , . . , . [1820] . [18] . 1 , 2 , . . . -- G , (k) = 1 2 . . . k , M = { g G : 1 (g) > 0}, G = M , H -- G , M , d = [G : H ] . (ks) , ks N, , , s , ks j (mod d) j . G H . [19] , [20] , (k) , .

5.
-- , n -- n, -- , f (P , Q) -- f P Q . : , , -- 7 . I ( , f ) : , f , . . : P , Q f ( (P) , (Q)) f (P , Q) , (1)

26

. . , . .

27

S ( , f ) -- I ( , f ) , ( , f ) ( f ) . 1956 . . . , , [24] . f , : S ( , ) (a1 . . . an) = g1 (ah (1) ) . . . gn (ah (n) ) , gi S () , h Sn . , S (n , f ) = S () n Sn . , || > 4 S (n , ) S (n) . [4, 10, 11] I ( , f ) , S ( , f ) , : (1) 7 f 1 , 1 . : , f , k , , k = 2. , . . f = , . . . . . , - n , «» . n , , 2 .

6.
Fk (n) -- k- n , . . f : n n , || = k, G -- S (n) . G Fk (n) : Fk (n) : f Fk (n) , g S (n) f g (x1 , . . . , xn) = f (g (x1 , . . . , xn)) ; f1 G f2 g G f2 = f IG (f ) = { g G : f g = f }.
g 1

f G :

. , G -- n , Sn , S () n, GL (n, ) , AGL (n, ) , n -- (n , +) ; Sn -- . [ f ] G , f IG (f ) . ( 1988 .) [13] . [14] , H k N n f Fk (n) , IG (f ) H G = Sn . = f Fk (n) n · Sn n . AGL (n, ) , -- (. [22] ) = Z/m (. [14] ) . [2] AGL (n, R) · H , R -- , H -- . . , n, k G , . . . , 1997 . [34] . 6, 7, 8 , 6 , 4- . . , 7 8 [44] . . .

7.
, () .

. [ f ] G , f , G IG (f ) : | [ f ] G | = |G | · |IG (f ) |.

28

. . , . .

29

A1 X1 . . . An Xn An+1 = B , (2)
[1] . ., . ., . ., . . . ., , 2001. [2] . ., . . . , . 36, 1979. [3] . . , . , . 21, 6 , 1 9 8 2 , 6 2 7 6 4 6 . [4] . ., . ., . . , . . ., . 9, . 3, 1997, 319. [5] . . - . ., , 2003. [6] . . , . . ., . 1, 1997, 4366. [7] . . 2- . . ., . 3, 2000, 3752. [8] . . . , . 10, . 3, 2003, 634. [9] . . «Rijndael». , . 11, . 2, 2003, 634. [10] . . , . . ., . 11, . 2, 1999, 2039. [11] . . , . .., . 4, 2001, 1732. [12] . ., . . () . . . , . 8, 1999, 532. [13] . ., . ., . . k- . I. ., 1988. [14] . . (. ) , , 1981. [15] . . . , 2, 1968, 15. [16] . . . , 1, 1 9 7 1 , 4 3 4 4 . [17] . . . , 3, 1977, 115. [18] . ., . ., . . . . ., . 1, 1997, 85112. [19] . . . . .,

A1 , . . . , An+1 -- , X1 , . . . , Xn -- G . , , . -- . . , . , . . , (2) G , , (X1 , . . . , Xn) G . . (2) , . , [36] , [3] -- ( ) . X d = 1, X -1 gX = h . ax = b . . . [5] . , . . GF (p) exp (c + o (1)) (ln p) 1/3 (ln ln p) 2/3 . c . [25] , [26] , GF (p) . c 1,902 ( [26] ) . , - , -- .

30

. . , . .

31

. 3, 2000, 7394. [20] . . . .., . 3, 2000, 5372. [21] . . Sn , . . ., . 2, 1998, 1 1 2 1 5 0 . [22] . ., . . . , . 9, 1963, 6398. [23] . ., . ., . . . ., , 2004. [24] . . , . , . 2, 7093. [25] . ., . . GF (p) . , . 7, . 2, 2000, 387389. [26] . . GF (p) . . ., . 15, . 1, 2003, 2849. [27] . . . 1. . ., 1986. [28] . . . 1. ( 198195 .) . . ., . 2, 1998. [29] . . . . . , 5, 1 9 7 3 , 1 4 1 1 4 4 . [30] . . , 2m . , . 19, 2, 1973, 236247. [31] . . . , . 19, 3, 1973, 423457. [32] . . , . , 5, 1975, 5155. [33] . . . . ., . 3, 2000, 215234. [34] . . . . ., . 4, 2001, 273314. [35] . . , . . ., . 16, . 1, 114120. [36] . . . , . 6, 2, 1967, 111113. [37] Babai L., Seress A. On the diameter of Cayley graphs of the symmetric group. J. comb. Theory, v. A49, 1988, 175179. [38] Cambell K ., Wiener M. DES is not a group. Crypto'92, 512520. [39] Dixon J. D. The probability of generating the symmetric groups. Mat. Z.,

v. 110, 1969, 199205. [40] Piccard S. Sur les bases des groupes d'ordre fini. Neuchatel, 1957. [41] Wernsdorf R. The one-round function of the DES generate alternating group. Eurocrypt'92, 99112. [42] Wernsdorf R. The round function of RIJNDAEL generate the alternating groups. Fast software 2002, Leuven, Berlin, Preproceed., 272. [43] Wielandt H. Finite permutation groups. N.Y., 1964. [44] Xiang-Dong Hou. GL (m, 2) acting on Rm /R (m) . J. Discr. Math., v. 149, 1 9 9 6 , 9 9 1 2 2 .

33

. . , . . , . .
1.
, . , . , , . -- , , , , . (, , ) , . . , . , , , , , . , , . . : « . , ».

2.
, Crypto'83 [14] . - -

. , , , . . , , () . , Information Hiding: First International Workshop [13] , , , (embedded) . , , , : , (image) . . , , (hidden) . . , , , . . , , (cover, carriage) . -- . , , , . . , . , . [2] , [5] () [5] . . , , . , , . , , , , . , , -- .

34

. . , . . , . .

35

, , . . . , Emb Ext, . , = Emb (, , ) , -- = Ext (, ) . , , . Emb , , . , (, , ) , , Emb . . : · . , . , ; · . , , - , ; · Emb. , , . , , , . , , .

. , . : · . , ; · . . , , ; · . . . , . , . , , -- , . , : , . . (. 3) . « » : (covert) (subliminal) . , , . , . -- , . , . , . C -- , K -- , M -- S = {s = Emb (c , m, k) , s = | c C , m M, k K } -- . S C . , , , -

36

. . , . . , . .

37

. , , . (, ) . -, . «» , «» . , . , , () , . -- . , . . «» (subliminal) , , « ». , « » , « » . , . . , , , . , , . , , . - -

. , - , , . : . , . , , «», 0, «», 1. ? . , () (, ) . 3. . . 1. , , , , . , . -, . -, , . , . 2. , , . , , . , , , . . , , , , , -- . , , , -- .

38

. . , . . , . .

39

3.
. . -- . . «» , . . , , , . : · , , ( ) . , ; · , ( ) . . , . . . , . , (. ) . , , . . , . : - . . . . ,

( ) . . -- ; . , , , . . , . , -- . , , . , , , . , , ( , ) . , (. 5.3) , . (. [11] ) . . , . , , . (, , , ) . : 1. , . , , . , ( ) . , , , . 2. C = {c1 , . . . , cn } , . , , -

40

. . , . . , . .

41

C1 C , C2 C . , C , cn+1 , (. ) , . , , , C3 C2 . cn+1 . 1 , , , cn+1 . . , , . . . . , . -- , -- . , . . . , , , . , - , , (, , - ) . . , . , . , , . «» , , .

. , , , . 5. , , . . . . , , . , , . ? . , , () G , . , , , , , . . -- . G , , , . . , G . , , G . . 4.1. C , K M -- . ( , ) , C , K M . C , K M , , . R R. .

4. -
- , .

42

. . , . . , . .

43

k, K . m ( M) , s = Emb (c , m, k, r) , c r -- C R , . , s C . s , m Ext (s , k) . G (c , D) , D -- D, G -- C в D C . , D . () {Ac |c C }, Ac : C {0, 1}. , , C , ( S = Emb (C , M, K , R)) ( C = G (C , D)) . c -- , Ac (x) = 1 (Ac (x) = 0) , , , x C (, ) . , . , . , . , . ( C) . 4.2. - . [4] : ( ) . , (relative) ; . . , . . [15] . : . ,

(, ) . [3] [2] , (, ) . . X , Y Z -- X , Y Z . Ent (X) X . Ent (X |Y ) -- X Y . , Ent (X |Y ) Ent (X) , Ent (X |Y ) = Ent (X) , X Y . X Y X Y , REnt (X Y ) REnt (X Y ) =
x X

Pr{X = x } log2

Pr{X = x } . Pr{Y = x }

X Y X Y , X Y , -- X Y , . , REnt (X Y ) , X Y . , Pr{X = x } ( 0) Pr{Y = x } = 0 x X , REnt (X Y ) = +, . X Y Z : REnt ((X |Z) (Y |Z)) = Pr{Z = z } REnt ((X |Z = z) (Y |Z = z)) .

z Z

REnt ((X |Z = z) (Y |Z = z)) X Y Z = z , , REnt (X Y ) , Z = z . , REnt (X Y ) 0, REnt (X Y ) = 0 , X Y . REnt ((X |Z) (Y |Z)) 0, REnt ((X |Z) (Y |Z)) = 0 , (X |Z = z) (Y |Z = z) z Z . -- . 1 ( 4] . (Emb, Ext) [) · - , REnt (C S) ;

44

. . , . . , . .

45

· , 0- , . . C S . . . 2. (Emb, Ext) · - ( ) , REnt ((C |C) (S |C)) . 3 ( 15] . (Emb, Ext) [) · - ., Ent (M) - Ent (M|C , S) ; · ., 0- ., . . M (C , S) . 4.3. (Emb, Ext) - . [4] . , f X Y . REnt (f (X) f (Y )) REnt (X Y ) . (1) , 0 , log2 ( / (1 - )) + (1 - ) log2 ((1 - ) /) , ( , ) = log2 (1/) , log2 (1/ (1 - )) , 1, {0, 1}; / = 0; = 1.

, C , . . G . 2 ( 15] . (Emb, Ext) -- , [) . Ent (S |C) = Ent (C |S) = 0.

, , G .

5. -
, « ». , . , , , ( -- , -) . , , - . , , . - , 4, - , . , , , , , , , . . , () . . , . - . . , , ,

(1) , - . 1 ( 4] . (Emb, Ext) -- , -[) . (, ) . , = 0, , , - 2) . 2- . ( -

46

. . , . . , . .

47

, ? 5.1. N , n N -- . N N, n , = const, > 0, . C = {Cn }, Cn {0, 1}q , -- . q = q (n) -- . Cn . , - {0, 1}q . , , n Cn . 4. {cn }, cn Cn , , () , 1n ( n) cn . , . . , G -- , c Cn c = G (c) , c {0, 1}q . c -- . G . . G , l : N N , n G l (n) . c Cn r {0, 1}l (n) . c = G (c , r) . , G , . G . . . . , A, s {0, 1}q 0, 1. A (s) = 1, s , . . . A (s) = 0, s .

: N (0,1] . . c Cn , r R {0, 1}l c = G (c , r) . Pr{A (c ) = 1} (n) . r , A. , (n) -- , «» . , , « » , 1. ( , ) . , , , s , . , . . -- , s -- . 5 ( 1] . (Emb, Ext) [) G ( , ) , {cn }, {mn }, mn {0, 1}t (n) , {G (cn) } {Emb (cn , mn , k) }, k R {0, 1}n , . , {Dn } {Dn } , B , p n
x D

Pr {B (x) = 1} - Pr {B (x) = 1} < 1/ p (n) .
n

x D

n

Dn Dn q (n) . 1. {cn } , , , . , . , 5 -

48

. . , . . , . .

49

. , - , : . , (., , [15] ) . t (n) n + 1. , ( ) n. 5.2. 3 ( 1] . [) Emb, 5, . 3 . 6. {Dn } -- , Dn {0, 1} (n) . {Dn } (polynomially samplable) , Samp , Samp (1n) = Dn . 7 ( 10] . g : {0, 1}n {0, 1} (n) -- , [) . g , p {Dn } , 1. {Dn } { g (x) }, x R {0, 1}n , . 2. Ent (Dn) Ent (g (x)) + 1/ p (n) . Ent (Y ) Y . 3. . , 5, , . , [10] (. [12] ) , , . [10] , . , 5, G -- . g . {cn } -- -

. - () , 1n mn {0, 1}t (n) . x {0, 1}n -- g . g (x) = Emb (cn , mn , x) . , g . , Ent (g (x)) n. , 5 { g (x) }, x R {0, 1}n , {G (cn) } . , {G (cn) } r {0, 1}l . , {G (cn) } {Emb (cn , mn , k) }, k R {0, 1}n , mn R {0, 1}t (n) , . { g (x) }, x R {0, 1}n , {Emb (cn , mn , k) }, k R {0, 1}n , mn R {0, 1}t (n) . , {Emb (cn , mn , k) }, k R {0, 1}n , mn R {0, 1}t (n) , t (n) ( mn Emb (cn , mn , k) Ext) . t (n) n + 1, . 2. , , Emb . , , . , 3 : , Emb, . (, ) , , , , . , 5 G , . , G , . , , . , G (cn) Emb (cn , mn , k) , k R {0, 1}n , n. , , 5, . ,

50

. . , . . , . .

51

, . 8. G -- r {0, 1}l , r = r1 r2 , r1 {0, 1}l1 (n) , l1 (n) -- N N , l1 (n) < l (n) . G , Der , c r {0, 1}l , Der (G (c , r)) = r1 . , , . , l1 (n) t (n) . ( , ) . A, ( , ) . . A 1n mn {0, 1}t (n) , cn {0, 1}q (n) . , mn cn -- . A s {0, 1}q 0, 1. P1 (n) = Pr{A (s) = 1} , s = = G (cn , r) . r A. P2 (n) = Pr{A (s) = 1} , s = Emb (cn , mn , k) . P2 k A. , , , , , G Der. 9. (Emb, Ext) G ( , ) , A , p n , . , |P1 (n) - P2 (n) | < 1/ p (n) .

. , , . 4 ( 1] . , [) , ( , ) . . g : {0, 1}n {0, 1}t (n) -- . [10] , [12] . (Emb, Ext) . Emb (cn , mn , k) = g (k) mn . G , cn r = r , r R {0, 1}l (n) -t (n) . s = G (cn , r) . s () Emb. Ext Der, s . -- t (n) Der (s) . mn = g (k) . c : g (k) , k R {0, 1}n , . 5.3. , , , . -- , , , . , ( ) , , . , : «» , , . , .

52

. . , . . , . .

53

(, ) , . . , , , , . , , . , . , . , , c Cn -- , . G c = G (c) . , m , (Emb, Ext) -- , k -- . c , s = Emb (c , m, k) . c~ Sub c = Sub (c~ ) , . , {G (c) } {Sub (c ) }, c = G (c) . , , . . m. s , c1 , . . . , cu , G c1 , . . . , cu , , . -- . - , ( ) . , , c1 , . . . , cu ( !) . u , , , , V = {1, . . . , v }. , v . : , -

, . , . 10. (Emb, Ext) G - ( ) , : 1) (. 5) ; 2) Sub . s -- , , s , . . s = s , s = Sub (s) . Pr{ s & Ext (s ) = m} . , . 10 , , , m. , , , 10, . u R V c1 , . . . , cu , . , , « ». , . . , (u + 1) - . G -- , . (k1 , k2) , k1 , k2 {0, 1}n . g : {0, 1}n {0, 1}v ·l1 (n) -- . , l1 -- , G , Der (. 5.2) . g (k1) . v r1 , . . . , rv , l1 (n) . c1 , . . . , cu , c1 = G (c1 , r1) , . . . , cu = G (cu , ru) . Der r1 , . . . , ru g (k1) . , , l1 , . , , k2 , ,

54

. . , . . , . .

55

s , m, s . , u, . 5.4. . , : · () ; · , , . , , , . . , . : · ; · «», . . , , ; · . , ; · ; · , , . . , , , , . , (, , ) . , . n -- , u = u (n) -- . c1 , . . . , cu , n, i {1, . . . , u} ci

s = Emb (ci , m, k) , k -- , m -- . m , , t < n. ( , ) {c1 , . . . , ci -1 , ci , ci +1 , . . . , cu } {c1 , . . . , ci -1 , s , ci +1 , . . . , cu }. n , -- i , k, m, Emb. , i Emb. , 5. 11. D -- {0, 1}n X -- , {0, 1}n D . min- X Ent
min

(X) = min n (- log Pr{X = x }) .
x {0,1}

min- . 12. X Y -- . X Ent
Ren

(X) = - log Pr{X = Y }.

, min- Ent
Ren

(X) /2

Ent

min

(X)

Ent

Ren

(X) .

2. , , . 13. X = (X1 , . . . , Xu) {0, 1}nu (n, h) - , i = = 1, . . . , u z {0, 1}nu-n

56 Ent

. . , . . , . . (Xi |X1 , . . . , Xi , Xi , . . . , Xu = z) h.

5.5. « »

57

min

-1

+1

Entmin (Xi |X1 , . . . , Xi -1 , Xi +1 , . . . , Xu = z) -- min- Xi X1 , . . . , Xi -1 , Xi +1 , . . . , Xu = z . (n, n - 1/ p (n)) - , p -- . , (n, n) - nu. , (n, n - 1/ p (n)) - , . , , , s = ci , n. 5. p , (n, n - 1/ p (n)) , . [9] . -- (n, n - 1/ p (n)) - u , N = nu. u, N M n. 1. F : {0, 1}N в {0, 1}N {0, 1}M G : {0, 1}N {0, 1}M Y {0, 1}N , X {F (X , Y ) } {G (X) } . Pr{F (x , y) = G (x) } n. x R {0, 1}N , y {0, 1}N Y . 3. [9] (, , . .) (. . , ) . 5 . , . .

. [8] , , , , « ». , . , , , : , . , , (, , ) , . . . . - [8] . , , min- . . [8] . -- . C , H DH . H = s1 s2 . . . sl , , , . . PrDs1 . . . si-1 (si) > 0. , [8] , C M, H s , DH . 14. S = (Emb, Ext) , : 1. Emb k, m {0, 1} ( ) , H . , M. Emb s1 s2 . . . sl () .

58

. . , . . , . .

59

2. Ext k, H s1 s2 . . . sl . m {0, 1} . k R {0, 1}n , n -- . , l m, . w > 0 , l w l . . S n, C l RelS = min Pr{Ext (H , EmbM (H , m, k) , k) = m}. H m {0,1}l . k {0, 1}n Emb Ext M. , . -- , () C . O (H , · ) , (H , m) , m {0, 1} , H -- , . O l , Emb (H , m, k) , si , DH s1 . . . si-1 , s1 . . . sl . 15. W (t , d , q , l) - S , : 1. W t ( , Emb ) d . 2. W C , M. 3. , W , -- EmbM (·, ·, k) , O (·, ·) . W q l . 4. W . . W S n C AdvS (W ) = Pr W
M,EmbM (·,·,k)

W , -- k {0, 1}n . C (t , d , q , l) - W . 6. S -- 1 - , 1 - w . , , si Di . min- h, , Emb lw N M,
Ne l 2w
l

SecS (t , d , q , l) = 1 - max AdvS (W ) .

+ + R ,

, ,
2w (1/2 - - R) , e

R = 1/ (1 - 2h /|S |) . , 5, ( ) . , « » , , . .

6.
, , , . , , , , , .

= 1 - Pr W

M,O (·,·)

=1 .

60

. . , . . , . .

61

, . , . , - () . . «», . « » (information hiding) . , , , , . . -- , , , . -- , , . . , - , , , . , , , . , , . , , . , () , , , . . , «», , . , - , . . -

, , , . , , - , . [6] . C ( ) . m , , C . , , . . : {0,1} [0, 1] x (x) = (n) : Q n0 : n n0 x {0, 1}n (x) < 1/Q (n) . 16. (Mark, Extract) , : · ( ) . C , k m, Markk (C , m) , , C . · ( ) . p , C , |Markk (C , m) | p (|C | + + |m| + |k|) . · () . C , k, m, Extractk (Markk (C , m)) = m. · () . C , Prk {Extractk (C) = } = (|C |) . · () . A S , C m Pr{A (Markk (C , m)) = C : C C & Extractk (C ) = m} -
k

- Pr S C (1|C |) = C : C C

= (|C |) .

k {0, 1}max (|C |,|m|) , C C , C C . , . , Mark Extract .

62

. . , . . , . .

63

16 , ( ) . , C k . , 16, . - , : , «» . , , , (, ) . , , , . 16, Markk (C , M) , C , . . , . , . , F , , . , « » Extract k. , , k , 105 в 106 . Extract, F , k ( !) , , Copyright. ? , k , ( ) Extract F () ? . , F ,

, , . : « , -- , . ., . .» , . , , , ( , ) , [6] . , , 16. Extract, , . 7 ( 6] . , [) ( 16) . 1 ( 6] . [) ( 16) .

[1] . . - . . 4- « », 19 25 2000 . .: « ». 1516. [2] Anderson R. Stretching the limits of steganography. Proc. 1st Intern. Workshop on Inform. Hiding, 1996, LNCS, v. 1174, 3948. [3] Anderson R., Petitcolas F. On the limits of steganography. IEEE J. on Selected Areas in Communications, 1998, v. 16, 4, 474481. [4] Cachin C. An information-theoretic model for steganography. Proc. 2nd Intern. Workshop on Inform. Hiding, 1998, LNCS, v. 1525, 306318. [5] Craver S. On public-key steganography in the presence of an active warden. Proc. 2nd Intern. Workshop on Inform. Hiding, 1996, LNCS, v. 1525, 355 368. [6] Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S., Ke Yang. On the (im) possibility of obfuscating programs. J. Kilian (ed.) . Advances in Cryptology -- Crypto'01. LNCS, v. 2139, Springer-Verlag, 2001, 118. . : http://www.math.ias. edu/~boaz/Papers/obfuscate.ps. [7] Diffie W ., Hellman M. New directions in cryptography. IEEE Transactions om Information Theory, IT-22 (6) , 1976, 644654. [8] Dedi N., Itkis G., Reyzin L., Russell S. Upper and lower bounds on blackbox steganography. Cryptology ePrint Archive (http//eprint.iacr.org) ,

64

. . , . . , . .

R ep o r t 2004/ 246. [9] Dodis Y ., Ong Sh. J., Prabhakaran M., Sahai A. On the (im) possibility of cryptography with imperfect randomness. Proc. 45th Symp. Found. of Computer Science, 2004, 196205. [10] Impagliazzo R., Levin L., Luby M. Pseudo-random generation from oneway functions. Proc. 21st Symp. on Theory of Computing, 1989, 1224. [11] Johnson N. F ., Jajodia S. Steganalysis of images created using current steganography software. Proc. 2nd Intern. Workshop on Inform. Hiding, 1998, LNCS, v. 1525, 273289. [12] Luby M. Pseudorandomness and cryptographic applications. Princeton, NJ, Princeton University Press, 1996. [13] Pfitzmann B. Information hiding terminology. Proc. 1st Intern. Workshop on Inform. Hiding, 1996, LNCS, v. 1174, 347350. [14] Simmons G. J. The prisoners' problem and the subliminal channel. Crypt o ' 8 3 , 1 9 8 4 , 5 1 6 7 . [15] ZЖllner J., Federrath H., Klimant H., Pfitzmann A., Piotraschke R., Westfeld A., Wicke G., Wolf G. Modeling the security of steganographic systems. Proc. 2nd Intern. Workshop on Inform. Hiding, 1998, LNCS, v. 1525, 344 354.

. . , . . , . .
1.
« E D , E D , . , , , - , , E (. . E ) , E . , . , E , , -, . -, : , , . , , , .» [11] . «» , , -, . E D , , -- . , , . , [11]
03-01-00880.

66

. . , . . , . .

67

( RSA, . . ) . , , - . , O, , P O (P) , : · ( ) . P O (P) , . . . · ( ) . P O (P) ( ) . · () . O (P) - . , , . O (P) P . P . P , . , O (P) , O. « » . -, , . -, -- , . . «» , . , .

· , (MAC, , ) . . · . , , . , , . · . , ( , , . .) . , , , , . · . , , , . , . , , , , . , . . , . , , , , : . , . , « ». , ,

68

. . , . . , . .

69

. . , , . , , . , , . , , , : ( , - , ) , .

, D . Supp D D .

3.
, , : , . . , , , . 3.1. , , - . , - , . , P , P , . , . , , [15] . . M e (M) . {0, 1} . L {0, 1} -- , M M , (, M M , , ) , e (M) L e (M ) L, . . L . 1 ( 15] . L [) , , . . L = , L = {0, 1} . , , « » [5] , . . [3] -- . 4, . 7.2, 3, [4] -- . 2, . 2.1, 2-39 () . . L ( ) , . , A

2.
. , , . , . . «» . A x , A (x) -- . « A (x) » A (x) . () A B , A B , . . x , A (x) = B (x) . , , A B , : x , . : N [0, 1] , k N n0 , n n0 , (n) < 1/nk . : {0, 1} [0, 1] x {0, 1}n (x) = (n) : : N [0, 1] , x {0, 1}n , (x) (n) . D X x D X X D . x R X

70

. . , . . , . .

71

M , , . . M M M , M M, , A M L . : «» - , , , BPP. , . , , . [8] , . [8] . 3.2. . : «, E , , -, ». , , . . , -, (learning theory) [16] . , , . C . . -- . c C ( , C , c) . c -- . , c C , C , -- . 4. . «», , , -- .

, « », «», « ». . [16] , , ( , ) . 5. « » . learning theory ( -- ) . -, «» , , , . -, (learner) , , ( adversary, ) . (teacher) , : , «», «» . , , , . , ( ) c , - , c , , , . - P . , P -, . . , , - , , . P P (, , ) . , . , , , ,

72

. . , . . , . .

73

, . , . , . P = {Pn }, Pn -- C, . , {0, 1}n x {0, 1}n C, , x = , 0n -- . , C, , (, = 0n) . - ( -- point function) . , C, , , , . x {0, 1}n C, (x) . , -, 0n , 2-n . , -, . -, , , ( , , ) . -, , -, , - , . , , . ; , , - . . . X -- , . X ( , C) , C {0, 1} , -- : C 2X . c C (c) X . { (c) |c C } , ( , C) -- . , c -- (, ) , C -- ,

X = {0, 1} . , c n , {0, 1}n , 1. , , (c) -- , c , (C) , . , (C) . , , . . ., . . . . . , () . , , . , , , , , . , , , . , . , : . , C c . : C = n 1 Cn X = n 1 Xn . c Cn , (c) Xn . n . Cn Xn . , Cn -- , n . c Cn (x , 1) , x Xn , c , (x , 0) , x Xn -- . : x Xn , -- . (x , c (x)) , c (x) (c) x . A, , .

74

. . , . . , . .

75

C -- c Cn . (membership queries) -- A, s , n > 0, s |c |. O , c Cn , D Xn , A. , A , : · . A x Xn O , c (x) . · . O (x , c (x)) , x D Xn . · . O y , y D Xn . A , . y , A ; b {0, 1} . 1. AO C , n, s > 0, c Cn D Xn Pr{b = c (y) } < . D A. C , , s , n 1/. [7] . 2. : · RSA; · , ; · , .

2 , . [7] . -- . [6] .

4.
, , , . . -, «». -- , (bit commitment) . -, «» , . . 3.2, , . : , , . . , , , , . . , : « P -- , . O P , . . .». , , . -, , . -, «» , ; . , : ,

76

. . , . . , . .

77

, (. [12] , ) . [8] , , « ». O , O (P) P , , P . - (« ») . P x ( ) P (x) . [8] -- , . . ( , , ) . 2 ( 8] . O [) , : · ( ) . M O (M) O M , , M, . . O (M) M. · ( ) . O (M) M. . . p , M O (M) , |O (M) | p (|M|) , M t x , O (M) x p (t) . · () . A S , M Pr{A (O (M)) = 1} - Pr S
M

· () . A S , C Pr{A (O (C)) = 1} - Pr S
C

1|

C|

=1

= (|C |) .

O , . , 2 : · () . A S , M Pr{A (O (M)) = (M) } - Pr S
M

1|

M|

= (M)

= (|M|) .

1|

M|

=1

= (|M|) .

3 ( 8] . O [) , : · ( ) . C O (C) O C , , C . · ( ) . p , C O (C) , |O (C) | p (|C |) .

, M O (M) , « ». 3. . [8] : . 3 ( 8] . ( [) 2) . . . - C, (. 3.2) . , C, , : C, . D, . C , C -- , D, 1, C () = , 0 -- . . O (C,) O (D,) . O (D,) (O (C, )) , 1 , , O (C,) . S C, D, . , C, . , , , C, D, . . ,

78

. . , . . , . .

79

[8] . - . 4 ( 8] . , [) ( 3) . [8] . 1. , . : «. . . ». 1 ( 8] . ( [) 3) . [8] . . . 4 ( 8] . [) {Hk }kN Hk (, , {0, 1}n (k) {0, 1}m (k) ) , : · Q , Hk Q (k) . , , Hk . · : kN Supp (Hk) {0, 1} , 1) (f ) f : S Pr S f 1k = (f ) - 1/2 = (k) ; 2) (f ) , f : A , f kN Supp (Hk) C f , A (C) = (f ) . 5 ( 8] . , [) . , { f } () , , f , (. . (f )) .

5 . : kN Supp (Hk) {0, 1} , . 1, 4, (f ) . , f , (f ) . , 4, (totally) . 6 ( 8] . , [) .

5.
, , 2 3. ; . 5.1. 2 3 . P . , P , () . , , P . . 7 ( 8] . [) , , TC0 . TC0 , , . . , , , MAJORITY .

80

. . , . . , . .

81

MAJORITY x1 , . . . , xk 1, xi , k/2, 0 -- . 5. TC0 -- , ( ) . , TC0 , . P . -- P , . , P -- , . [8] . , . , - , , «» f , , k (f ) , k -- . , « », . , , (f ) , , , k. , . . 8 ( 13] . , [) , . : C , . -- , .

, , , , . , [8] . . [13] , [8] -- . , [8] , ( ) , . , ( , , ) , , : · , ; · , , , , , ( ) . 5.2. « » , S - , , « ». , « », [17] . , « », -- . , O (P) P « » . , , O (P) , x P (x) , P x . , « », .

82

. . , . . , . .

83

2 . -- , S . S x , y , M x . , , , M, . , M. , , - , , M. , , , . -- . [17] «» ( ) , . . , . , 2, , S , Tr (M) . x (y , trM (x)) , y -- M x , trM (x) M . trM , M x . 6. O , : · ( ) . M O (M) O M , M . x1 , . . . , xu O (M) M , . ., O (M) (xi) = M (xi) i = 1, . . . , u. · ( ) . O (M) M. · () . A S , M Pr{A (O (M)) = 1} - Pr S
Tr (M)

9 ( 17] . , [) . 5.3. [8] , . . . , 2 . , , « » - , . , « ». , , . ( ) , , . . , , . [17] . ( ) . , , , . P0 , P , P0 . , P -- , RSA, . . , P0 , . S , 2 3, P0 . 2 .

1|

M|

=1

= (|M|) .

84

. . , . . , . .

85

7. O , : · ( ) 2. · () . A S , M, M , M M, Pr A O (M) , M = 1 - Pr S
M

S , M c0 {0, 1}n Pr{A [O (M) (c0) , M (c) ] = 1} - Pr S
n M (c0)

1|

M (c0) |

, M (c) = 1

=

1|M| , M = 1

= (|M|) .

A S , , O (M) 1|M| . , , M , S M. ( ) . -- . [8] . , , . , , . , , , , {0, 1}2n {0, 1}n «» . . , -- c0 , P . , C . , P , c0 . P -- , c . , {0, 1}n . c0 {0, 1}n P (c0) P . P n. 8. O , : · ( ) 2. · () A

c R {0, 1} . , , A S c0 . , , ( ) . , , , , .

= (|M (c0) |) ,

6.
. . , . , , , . , . «» «» , . , «» , . , , , , . , . , , , , 2, .

86

. . , . . , . .

87

, ( ) (. 3.2) . [14] . . . 6.1. , ( ) . . «» , , NP- . NP (., , [10] ) . , ( « ») , , . , , . [8] . , F : {0, 1} {0, 1} . , , , , F . . ( [1] , [2] ) . 10 ( 8] . , [) . 6.2. . - (. 3.2) - 8. [9] . «» , , . -

(hashing scheme) . , , -. , -- H , V . x H r H (x , r) . V x c , c - x , . . r , H (x , r) = c . - x , , - H (x , r) . y V x = y . x . Ix -- , z 1, z = x , 0 -- . : · A S , {Xk } ( Xk {0, 1}k) , , Pr{A (H (x , r)) = (x) } - Pr S
Ix

1|

x|

= (x)

= (k) ,

x Xk . , -- . , , . , , . [9] , -- . - [18] . (. . ) : . [14] - . , ,

88

. . , . . , . .

89

. . [14] « », . . F G , . A, F G ? . , A A = F · G , F F , G G . , , F G , A . 7. , , , . [19] , , . [19] -. . · () . {An } (n) = 1/nO (1) {Sn } (n, 1/) , n C Cn
C Pr{An (O (C)) = 1} - Pr Sn 1| C|

, , - , . : p {An } p (n) q , n, An , q (n) .

[1] ., . . .: , 1982. [2] . ., . ., . . . .: , 1999. [3] . . . 2- . .: , 1986. [4] . . .: , 1972. [5] . . . . . (.) . . III. . .: , 1982, 950. [6] Angluin D. Computational learning theory: survey and selected bibliography. STOC'24, 1992, 351369. [7] Angluin D., Kharitonov M. When won't membership queries help? STOC'23, 1991, 444454. [8] Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S., Ke Yang. On the (im) possibility of obfuscating programs. J. Kilian (ed.) . Advances in Cryptology -- Crypto'01. LNCS, v. 2139, Springer-Verlag, 2001, 118. . : http://www.math. ias.edu/~boaz/Papers/obfuscate.ps. [9] Canetti R. Towards realizing random oracles: Hash functions that hide all partial information. Crypto'97, 455469. [10] Chow S., Gu Y ., Johnson H., Zakharov V . An approach to the obfuscation of control flow of sequential computer programs. Information Security conference, LNCS, v. 2200, 2001, 144156. [11] Diffie W ., Hellman M. New directions in cryptography. IEEE Transactions om Information Theory, IT-22 (6) , 1976, 644654. [12] Goldreich O., Goldwasser S., Ron D. Property testing and its connection to learning and approximation. FOCS'37, 1996, 339348; . http: //theory.lcs.mit.edu/~oded/ggr.html. [13] Impagliazzo R., Rudich S. Limits on the provable consequences of one-way permutations. STOC'21, 1989, 4461.

=1

(n) .

, C , Cn C , n . 3 . -, , . . A, S . -, Sn 1/, , , , .

90

. . , . . , . .

[14] Lynn B., Prabhakaran M., Sahai A. Positive results and techniques for obfuscation. EUROCRYPT'2004, LNCS, v. 3027, 2004, 2039. [15] Rice H. Classes of recursively enumerable sets and their decision problems. Trans. Amer. Math. Soc., 74, 1953, 358366. [16] Valiant L. A theory of learnable. Comm. ACM, 1984, v. 27, 11, 1134 1142. [17] Varnovsky N. A note on the concept of obfuscation. : 6. . . . . -- .: , 2004, 127136. [18] Varnovsky N., Zakharov V . On the possibility of provably secure obfuscating programs. Proc. 5th Conf. Perspectives of System Informatics, 2003, 7 1 7 8 . [19] Wee H. On obfuscating point functions. Cryptology ePrint Archive (http: //eprint.iacr.org) , Report 2005/001. STOC New York: F O CS Computer = Proceedings of the Annual ACM Symposium on Theory of Computing. ACM Press. = Proceedings of the Annual Symposium on the Foundations of Science. Los Alamitos, CA: IEEE Computer Society Press.

. . , . .
, , . , .

1.
, , / : · ; · ; · . , , . . . , , , , . , , , , . 1970- , , , , , -

92

. . , . .

A в Q -- --

93

. , -- [1] , [2] , Take-Grant [3] , Biba [3] , Lowwatermark [3] , . , , , .

F в

(AL) в Q / - - Q / -- , , 1 2. , ( ) , . , ( «» (unwinding)) . ([4]) . , 1 2 1. : L H , , . . ( , , , ) . , , . [4] . [6] . , . «» , . , , [7] . , ( , ) ,

Q

2.
, , , [4] . V = (A, Q , ) , A Q -- ( , ) , : A в Q Q -- (. [5] ) . , V . : H L. H , L -- . V , L H V . . A = AL AH , , . , ( , ) . . -- , L, -- H . , . Q . q1 , q2 Q . , q1 q2 , , L. : Q Q /. F : A AL , . A , = a1 a2 . . . ak , F () = F (a1) F (a2) . . . F (ak) . a A. F (a) = ( ) , a AH , F (a) = a . , H L, : 1) : AL в Q / Q /, (L , [q ] ) = [ (L , q) ] ( [q ] , q) ; 2) :

94

. . , . .

95

, , , , . , .

3.
. -- [8] . [9] , : · S1 -- , S2 -- . S1 S2 . · S1 -- , S2 -- . S1 S2 . · S1 -- , S2 -- . S1 S2 , , . , . , , . ( -- ) . , , .

4.
. · (, , L H , ) .

· (, , - , ) . : · , , , « »; · , . , , . , , . , . , , , . [10] , [11] . ( -- ) . . , : 1) ; 2) ; 3) ; 4) ; 5) /. . , Linux 3, [12] . SSH 1 2, [13] . , . , / .

96

. . , . .

97

[14] . . (, [15] ) . . . , , «». . «» , , , . , , . ( ) [16] . , (, , ) , . , , , - [16] . . , . , ( valgrind (citevaseningalatenko:val, , -- ) . . [18] , () .

5.
(, , ) . L, c -- H . H L, . , , (, , .) . . [19] . [20] [21] , (, ) , .

6.
, : · , ; · , , ; · ; · , .

[1] McLean J. Reasoning about security models. Proc. of the 1987 IEEE Computer Society Symposium on Research in Security and Privacy, pp. 123 131, Oakland, CA, 1987. [2] Denning D. A Lattice Model of Secure Information Flow. Comm. of the ACM, Vol.19, 5, May 1976, http://www.cs.georgetown.edu/ ~denning/infosec/lattice76.pdf. [3] . ., . . . «», 1996.

98

. . , . .

[4] Moskowitz I. S., Costich O. L. A Classical Automata Approach to Noninterference Type Problems. Department of the Navy, Naval Research Laboratory, 1992, http://chacs.nrl.navy.mil/publications/CHACS/1992/ 1992moskowitz- foundations.pdf. [5] . ., . ., . . . .: , 1985. [6] . . . , . 4, 34. ., 1999. . 263270. [7] . . . « », , 2003. [8] Sandhu R. S., Coyne E. J., Feinstein H. L., Youman C. E. Role-Based Access Control Models. Computer, pp. 3847, February 1996. [9] . . . . [10] . ., . ., . . . «-2003», , 2003, . 2 3 7 2 3 9 . [11] . . . . . . , , 2003, . 91106. [12] Linux. http://www.securityfocus. com/archive/1/315635. [13] SSH. http:// openssh.org/security.html. [14] . ., ., . : model checking. .: , 2002. [15] . ., . ., . . . « », -., 2003, C. 33. [16] . . - . JetInfo, 67, 1997, http://www.jetinfo.ru/1997/6- 7/ 1/article1.6- 7.1997.html. [17] valgrind. http://valgrind.kde.org. [18] . . . JetInfo, 8, 1999, http://www. jetinfo.ru/1999/8/1/article1.8.1999.html. [19] . . () . JetInfo, 11, 2002, http:// www.jetinfo.ru/2002/11/2002.11.pdf. [20] . . . , . 10, . 1, 1998, . 39. [21] . . . , . 11, . 1, 1999, . 2428.

. . , . . , . . , . .

, , - ( -) , -- . , , , . . , . , . , . -, - . , ,
03-01-00248 04-07-90010 2004 .

100

. . , . . , . . , . .

. . .

101

. -, , , , , , , . -, - , , , , . , - , , , -- . , . , / , , , . . , , (Intrusion Detect System) (Intrusion Prevention System) . , , , , , . , , , .

· ; · ; · ; · . . , , , , () - . , 10-7 , , . , , . , , , . , .

2.
() : · - ; · . , - , , , , , , , . , -

1.
, : · ; · ;

102

. . , . . , . . , . .

. . .

103

. , , , , . : · , , , - ; · , , , - ; · , . , , , , . . , , , , . 90- . , : · , ,

; · « » ( ) , «» ( ) ; · - ; · ; · , . . 1 . ( ) , .

. 1. .

, , , , . . , -

104

. . , . . , . . , . .

. . .

105

, ( ) . , : · () , ; · , , ; · . , , [18] , . : · [1] , [3] , [4] ; · [5] ; · [7] ; · [8] .

, , . [9] (, ) . () , , , . , . , , [10] . , , . , , . , , . , , , . 3.2. () , [9] . , . , d (X) = w1 x1 + w2 x2 + . . . + wn xn + wn+1 , X = (x1 , x2 , . . . , xn) -- n- , W = (w1 , w2 , . . . , wn , wn+1) -- d (X) . k Ai , i = 1, 2, . . . , k, k di , i = 1, 2, . . . , k, ,

3.
3.1. , , , , , , . , .

106

. . , . . , . . , . .

. . . ,

107

: - , . [9] , n+1 d (X) = i =1 wi fi (X) , fn+1 (X) = 1, fi -- X . . Ai Zi , i = 1, . . . , k. : X Ai , Di (X) < D j (X) j , j = i ,
n

X Ai , di (X) > 0, j , j = i , d j (X)

0, i , j = 1, . . . , k.

X1 , D

1

= (x11 , . . . , x1n) , D1 ,

X2 , D2 = (x21 , . . . , x2n) , D2 , .................................... Xm , D
m

= (x

m1

, . . . , xmn) , D

m

,

2 i , j = 1, . . . , k, Di (X) = p =1 (x p - zi p) -- X = (x1 , . . . , xn) Zi = (zi 1 , . . . , zin) . , , . .

X j = (x j 1 , . . . , x jn) -- j - , D j -- , Y j -- , j - , j = 1, . . . , m. , , . , : · j max |D j - Y j | , -- ; ·
j

3.3. , , , , , . , , , , . , [11] . . xi , i = 1, . . . , n, i , n . , . x j = {x j 1 , x j 2 , . . . , x jn } n- , x ji -- i j , , , .

, , , , () , . , , , . , , . , . , . , , . , , . -- , . . . , , . j , j {1, . . . , N }, N -- ,

(D j - Y j)

2

.

108

. . , . . , . . , . .

. . .

109

n( ) : a j - i =j1 w ji x ji = 0, n (j) -- j , a j -- . ( ) [12] . , , , . [1315] > 0 f (x1 , x2 , . . . , xn) , -- , : N

f (x1 , x2 , . . . , xn) =
i =1

vi ·

1 , 1 + exp (- (wi 1 x1 + . . . + win xn))

vi -- , wi j -- j - , j = 1, . . . , n, i - , i = 1, . . . , N , , N -- . , . . , , , . N (n + 1) , N -- , (n + 1) -- , n- . n- , . , .

. (0, ) . (1 ) . 40 , -- 20 . (BP -- Back Propagation) [11] . , , . , , . . 2 1- 2- . {open, read, fork, exec}, 0.2%, -- 0.8%.

. 2. .

4.
. -

, , 1%. , 1% .

110

. . , . . , . . , . .

. . .

111

5.
(HBME, Hierarchical Boosted Mixture of Experts) [16] HME [17] , [18, 19] , . HBME . , HBME, . HBME (basic expert -- BE) , X = {xi , yi }. : 1) : i : i = 1, 2, . . . , n; E [xi , yi , F (xi) ] < ,

. 3. .

. 3 , . , , , : · : , , , , , , , ; · , , ; · , . , , .

E [xi , yi , F (xi) ] -- (xi , yi) , n -- ; -- ; 2) «» , , -- E [xi , yi , F (xi) ] < , n . «» , E [xi , yi , F (xi) ] < . nmin , , HBME, (auxiliary expert -- AE) . «» , HBME . «» nmin . . HBME (consistent expert -- CE) . , «» . ,

112

. . , . . , . . , . .

. . .

113

, . , , . , , , 10 . IBM- Intel Celeron 400 32 Windows 98.

6.
. 4. HBME.

«» . , HBME. HBME , (gate) , . HBME , , -- (. 4) . . . . x . HBME . HBME « , » (BP) . . HBME BP, . HBME BP. , , .

X = (x1 , 1/20 x1 (x1 , x2 ) : x
(i) (k) (i) 1

F (x1 , x2) , x2) : x1 [0, 1] , x2 [0, 1] . x2 :
(k) 2

=

i , i = 1, 20; x 20

=

k , k = 1, 20 . 20

, 0.05, .
( ( (x1i) , x2k) ) : x (i) 1

= 0.25 +

i , i = 1, 19; x 20

(k) 2

= 0.25 +

k , k = 1, 19 . 20

F , , HBME BP, () , . : · F (x1 , x2) (a) ; · F (x1 , x2) , HBME, (b) ; · F (x1 , x2) , BP, (c) ; · , HBME ( ) (d) . , HBME BP (t)

114

. . , . . , . . , . .

. . .

115

(1) (. 5, 6, 7, 8) (2) (. 9, 10, 11) . 1, (x1 [0.2, 0.4] x2 [0.2, 0.4] ) F (x1 , x2) = (x1 [0.6, 0.8] x2 [0.6, 0.8] ) ; 0 . d (x1 , x2) < 0.1252 ; 1, 0.6, 0.1252 d (x , x ) < 0.252 ; 1 2 F (x1 , x2) = 0.3, 0.252 d (x1 , x2) < 0.52 ; 0, 0.52 d (x1 , x2) . d (x1 , x2) = (x1 - 0.5) 2 + (x2 - 0.5) 2 .

(1)

(2)

. 9. a)

. 10. b) : 0.01, t

: 30.9 .

. 5. a)

. 6. b) : 0.03, t

: 10.8 .

. 11. d)

(2) BP , c) . HBME , BP, . , HBME , .

7.
, , , . , , .

. 7. c) : 0.04, t : 915.9 .

. 8. d)

116

. . , . . , . . , . .

. . .

117

, , . , , . . , , , HBME , , .

[6]

[7]

[8]

- . - . , . , .

[9] [10] [11] [12]

[13] [14] [15] [16] [17]

[1] . . Internet. .: « », 1997, 174 . [2] . ., . . . « », , 2527 1997 . . 173. [3] . ., . . . . « », , 1999, . 13, . 171182. [4] . ., . ., . . . , 12, 2000, . 104114. [5] . ., . .

[18] [19]

. . « », , 2000, . 14, . 144154. . ., . . - , .« », , 2001, . 15. . ., . ., . . . . « , », , , 2003, . 136139. . ., . ., . . . « » (, 2003) . .: , 2004, . 352364. ., . . .: , 1978. A., . , . .: , 1978. Jain A., Mohiuddin J. Artificial Neural Networks: A Tutorial. Computer, March, 1996, p. 3144. Hampshir II J., Perlmutter B. A. Equivalence Proofs for Multy-Layer Perceptron Classifiers and the Bayesian Discriminant Function. Carnegie Mellon University, Pittsburg, 1997. Hornick, Stinchcombe, White. Multilayer Feedforward Networks are Universal Approximators. Neural Networks, 1989, v. 2, 5. Cybenko. Approximation by Superpositions of a Sigmoidal Function. Mathematical Control Signals Systems, 1989, 2. Funahashi. On the Approximate Realization of Continuous Mappings by Neural Networks. Neural Networks. 1989, v. 2, 3. . ., . . . : , 2, 2003. Jordan M. I., Jacobs R. A. Hierarchies of adaptive experts. In J. E. Moody, S. J. Hanson and R. P. Lipmann (Eds.) . Advances in neural information processing systems. San Mateo, CA: Morgan Kaufmann, 1992, 4, p. 985 992. Avnimelech R., Intrator N. Boosted Mixture of Experts: An Ensemble Learning Scheme. Neural Computation, 1999, 11, p. 483497. Schapire R. E. The Strength of weak learnability. Machine Learning, 1990, 5 (2) , p. 197227.

Security policy languages and enforcement

119

rization policies specify the roles that each user may adopt, and the permissions associated with each role.

Security policy languages and enforcement Scott D. Stoller, Yanhong A. Liu

1. Trust management policy languages
Datalog (Database Logic) [5], a classic rule-based query language for databases, is an attractive foundation for policy languages in decentralized systems. Datalog allows recursive definitions of relations, so it can express queries not expressible in relational algebra or relational calculus, but it does not allow construction of recursive data structures, so it consumes bounded resources. Trust management systems based on Datalog or extensions of it include Delegation Logic [7], SD3 (Secure Dynamically Distributed Datalog) [6], Binder [3], and RT (Role-based Trust-management) [8]. Datalog is an attractive basis for trust management languages for several reasons: 1. It is declarative and has a simple and well-studied semantics. Datalog statements can easily be translated into declarative English sentences. This helps ensure that users will be able to formulate security policies that accurately capture their intentions. 2. It allows authorization based on all properties of entities and requests, not only their identities. For example, this enables the above policy involving the CEO, manager, and subordinates to be stated directly and clearly in terms of attributes (e.g., is-a-manager) and relations (e.g., is-the-manager-of), instead of by enumerating the permissions of each person individually. 3. Application-specific relations can be defined, and recursive definitions are allowed. Recursive definitions arise naturally when hierarchical structure (e.g., of a computer network, or of an organization) is involved. 4. Queries are decidable in polynomial time. This includes compliance checking, which determines whether a given request is permitted by a given policy, and policy analysis problems, such as computing the meaning of a given policy (i.e., the set of all operations permitted by the policy). A significant obstacle to deployment of trust management systems with Datalog-based policy languages is the lack of suitable implementations of such languages. Simple Datalog interpreters are easy to implement but have poor performance, especially for programs containing recursive definitions. Development of an optimized implementation is a significant undertaking, and the result is a heavy-weight system, not easily deployed for trust management [8]. Worse yet, even in the best existing highlyoptimized logic programming systems, such as GNU Prolog and XSB (http://xsb.sourceforge.net/), the running time of a program can vary dramatically depending on the order of rules in the program or the

Introduction
As organizations grow larger and more complex, and as cybersecurity becomes an increasingly important concern, there are growing needs for languages that can express complex security policies of organizations and for efficient mechanisms to enforce the policies. An essential function of security policies is to control authorization, that is, to determine whether a request to access a resource should be permitted or denied. This paper considers two key aspects of security policy languages -- support for decentralized policy administration through "trust management", and support for scalable policy management through roles -- and techniques for the efficient implementation of these languages. The implementation techniques provide a basis for enforcing security policies expressed in these languages. Traditional ways of expressing authorization policies, such as access control lists, were developed to support authorization in centralized systems with a single administrator in control of all aspects of security policy for the entire system. They are generally adequate and widely used in that context, but they have serious deficiencies for enterprise-wide applications [2], which may have many administrative domains and varying trust relationships. Trust management systems are designed to support authorization in distributed systems [2]. The defining characteristic of trust management systems is support for decentralized security policy administration through delegation: an entity can authorize another entity to control specified aspects of security policy. For example, a company's chief executive officer (CEO) might allow each manager to control his subordinates' access to technical data, while the CEO retains complete control over everyone's access to the company's strategic plan. Role-based policy languages support scalable specification and management of policies in large systems [11], [4]. A role is an abstraction that represents a set of permissions, typically the permissions needed to perform the tasks associated with a position in an organization. Role-based autho-

120

Scott D. Stoller, Yanhong A. Liu

Security policy languages and enforcement

121

order of hypotheses within each rule. It is very difficult for users to determine which order will lead to more efficient execution, because the answer depends on implementation details. We are addressing these implementation challenges through development of a powerful method, described in [9], for (1) automatic transformation of specifications in Datalog-like languages into specialized algorithms and lightweight implementations, and (2) automated complexity analysis that provides time and space guarantees for the generated algorithms. The transformation is based on a general method for efficient fixed-point computation. The set of all facts derivable from a Datalog program corresponds to a fixed-point computation that repeatedly derives new facts from existing facts by using the rules, until no more new facts can be derived. Our transformation exploits three key ideas to compute the fixed point efficiently: (1) perform a minimum update in each iteration, i.e., add one new fact at a time; (2) maintain appropriate auxiliary maps (i.e., indices), based on the structure of the rules, and update them incrementally in each iteration; and (3) use appropriate combinations of indexed and linked data structures. The generated implementations have guaranteed optimal time complexity and associated space complexity, in the sense that only useful combinations of information that lead to the invocation of a policy rule are considered, and each such combination is considered exactly once. The method computes the worst-case time and space complexities, as formulas. These are independent of the order of rules and hypotheses, in contrast to previous methods. We are extending the method to handle query-driven (goal-directed) computation, incremental computation with respect to policy changes, and distributed evaluation.

2. Role-based policy languages
Role-based policy languages offer well-established advantages for policy management in large systems. They are widely used in role-based access control (RBAC) [11]. The roots of role-based access control include the notion of groups in UNIX and other operating systems. The growing importance of RBAC motivated the development and recent approval of an ANSI standard for it [4], [1]. The standard specifies sets of users, objects, operations, roles, and sessions, and over a dozen relationships built on top of these sets. The standard then specifies several dozen operations on them. Producing straightforward implementation of the standard in a highlevel language with good support for sets, such as the popular object-ori-

ented scripting language Python (http://www.python.org/), is relatively easy, but the straightforward implementation will have poor performance. Manual development of a high-performance implementation takes significantly longer and requires writing more complicated and less modular code, which consequently is also more difficult to maintain. To see why, note that it is often much more efficient to incrementally maintain a set (or a relation, which we regard as a set of tuples) than to compute it from scratch each time it is needed. In a straightforward implementation, a set used in one operation may be calculated from scratch in one place, in the code for that operation. To produce an efficient implementation, we must identify all operations that perform updates that may affect that set, and in their implementations insert code to incrementally maintain that set. This breaks the modularity (abstraction) of the straightforward design and implementation. More generally, this problem arises with all expensive computed quantities (not only sets), which we refer to as queries of the data from which they are computed. We are addressing this implementation challenge through development of a general and systematic method that supports the use of abstractions by allowing each component and operation to be specified in a clear and modular fashion and implemented straightforwardly in an object-oriented language [10]. The method then analyzes queries and updates in the straightforward implementation, cutting across the abstractions in the clear and modular specification. Finally, the method breaks through the abstractions and transforms the straightforward implementation into a sophisticated and efficient implementation that incrementally maintains the results of expensive queries with respect to all relevant updates. The main steps are to determine which queries should be incrementally maintained, which updates may affect each query, and, most challengingly, where to store and how to update each incrementally maintained value, based on a cost model. The transformations are expressed declaratively as incrementalization rules. The method can be used automatically, semi-automatically, or manually. We developed conservative analysis and transformations that can be fully automated. A semi-automatic version may use more aggressive analysis and transformations that rely on hints from the user. The method can be followed manually as a design methodology. We developed a prototype implementation of the method for Python. We applied the method in the development of efficient object-oriented programs in a number of example applications [10]. Here we discuss the application to RBAC. We created a straightforward implementation of the RBAC specification in Python, as a complete and executable specification. Overall, more than

122

Scott D. Stoller, Yanhong A. Liu

Security policy languages and enforcement

123

half of the operations involve expensive queries, i.e., queries that take more than constant time. We then applied our analyses and transformations to our straightforward implementation of core RBAC (core RBAC contains the majority of the sets, relations, and operations in the RBAC standard), to automatically incrementalize the expensive queries with respect to the updates. There are over a dozen expensive queries and over a dozen updates. Our method is able to optimize all expensive queries to take constant time except for a tradeoff that lets either CreateSession take constant time and CheckAccess (and SessionPermissions) take O (|Permissions|) time, or vice versa. In typical applications, CheckAccess is performed much more frequently than CreateSession, and thus the latter gives better performance, as confirmed in our experiments. For example, with 900 permissions, the average running time of CheckAccess, for the straightforward, the former incrementalized, and the latter incrementalized implementations are 0.342, 0.0345, and 0.000187 seconds, respectively, when measured on a dual-CPU 2.3 GHz Athlon XP computer with Python 2.3. Future research is needed on improved analysis of costs and frequencies of and dependencies between queries and updates, suitable languages for specifying incrementalization rules, and further optimizations for on-demand and concurrent computations. We are also investigating the design and implementation of role-based trust management languages.

[7]

[8]

[9]

[10]

[11]

Proc. 2001 IEEE Symposium on Security and Privacy, pages 106115. IEEE Computer Society Press, 2001. Ninghui Li, Benjamin N. Grosof, Joan Feigenbaum. Delegation logic: A logic-based approach to distributed authorization. ACM Transaction on Information and System Security, 2003. Ninghui Li, John C. Mitchell, William H. Winsborough. Design of a rolebased trust management framework. In Proc. 2002 IEEE Symposium on Security and Privacy, pages 114130. IEEE Computer Society Press, 2002. Yanhong A. Liu, Scott D. Stoller. From Datalog rules to efficient programs with time and space guarantees. In Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, pages 172183, Uppsala, Sweden, August 2003. Yanhong A. Liu, Scott D. Stoller, Yanni Ellen Liu, Michael Gorbovitski, Tom Rothamel. Design by building up and breaking through abstractions. Technical Report DAR-04-15, SUNY at Stony Brook, Computer Science Dept., September 2004. Ravi Sandhu, Edward Coyne, Hal Feinstein, Charles Youman. Role-based access control models. IEEE Computer, 29(2): 3847, 1996.

References
[1] American National Standards Institute, Inc. Role-based access control ANSI INCITS 359-2004. http://csrc.nist.gov/rbac/. [2] Matt Blaze, Joan Feigenbaum, John Ioannidis, Angelos D. Keromytis. The role of trust management in distributed systems. In Secure Internet Programming, volume 1603 of Lecture Notes in Computer Science, pages 185210. Springer-Verlag, 1999. [3] John DeTreville. Binder, a logic-based security language. In Proc. 2002 IEEE Symposium on Security and Privacy, pages 105113. IEEE Computer Society Press, 2002. [4] David F. Ferraiolo, Ravi Sandhu, Serban Gavrila, D. Richard Kuhn, Ramaswamy Chandramouli. Proposed NIST standard for role-based access control. ACM Transactions on Information and System Security, 4(3): 2 2 4 2 7 4 , 2 0 0 1 . [5] Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom. Database Systems: The Complete Book. Prentice-Hall, 2002. [6] Trevor Jim. SD3: A trust management system with certified evaluation. In

. .
A B , ( ) xi +1 = f (xi) , ( , ) -- yi = F (xi) , i = 0, 1, 2, . . . , f : A A, F : A B -- . |A| = K , A Z/K . K = 2n , A = B . f , F , x0 , . . . , , yi = F (xi) xi yi . xi -1 xi = f (xi -1) f xi -1 , F . yi = F (xi) : , , , F , . , , xi -1 xi ( , f ) -- . [1, Ch. 16] . , «» , -- , , , . . : [4] , «» ( ) , , ,

« »

126

. .

. . . 127 N Q1, , (1) k = log2 N . , 1111111100000111 (1) k = log2 n = 4, (1) k = 3. , {xi } , g -- (y , z) y + z , (y , z) yz , (y , z) (1 + 2y) z ( , , y (1 + 2y) -1) , -- (y , z) y AND z , (y , z) y OR z , «» (y , z) y XOR z , z NOT z , «» (, , ) -- s z 2s z , z z AND M M, 2s , z z mod 2s = z AND (2s - 1) ,2 . , Z/2k , , : , 2 = 1 XOR 3 = 2 AND 7 NOT 13 (mod 8) , 3-1 11 -5 (mod 16) , 3-1/3 311 3-5 11 (mod 16) . . g f Z/2n , «» «» g , . . . , f F , . . xi
+1

«» «» (crazy, !) , , . [4] , «» , «» . «» ( [4] ) , . . , , , , , , -- , , k-. «»; 1 , f (x) = 1 + x + 2 · (g (x + 1) - g (x)) , g (x) = 1 + 2 ·
x AND x 2 + x 3 OR x 4 6 3 + 4 · (5 + 6x 5) x XOR x
7+8x 8 / (9+10x 9)
7

.

, xi +1 f (xi) (mod 2n) , n · 2n , , . . k- (k = 1, 2, . . . , n) . 2n-1 . , « »: Q1 . , [13, Section 3.5, Definition Q1] 0 1 . . . N -1 N ,
(0 . . . k-1) 1 -k N 2 1 N

yi F

f

i mod m

(xi) (xi)

(mod 2n) ; (mod 2n) .

i mod m

(1)

0 < k log2 N , (0 . . . k-1) 0 . . . k-1 0 1 . . . N -1 . , k-, (k - 1) -, ,
1 , .

, 3 m fi m Fi , , , . . 4 , 2 , , . 3 . 4 : , f (x) = 1 + x + 2 · ( g (x + 1) - g (x)) , i i i gi (x) -, , .

128

. .

. . . 129 . , [6] , Z/2n , r - Z/2k , n = rk, , k. , xi
+1

n- . , fi Fi , m · 2n , 2n-1 + 1. , . m 3 (mod 4) -- , v0 (x) , . . . , vm-1 (x) w0 (x) , . . . , wm-1 (x) -- , . x0 {0, 1, . . . , 2n - 1} xi
+1

= fi

mod m

(xi) ; (xi) ,
r

yi = F

i mod m (r)

x = x (1) , . . . , x f j (x) = f
(1) j (1) j

zi = (1 + (xi) + 4 · wi

= (i mod m + xi + 4 · v

i mod m

(xi))

mod 2n ; mod 2n ,
(·) (·)

Z/2k ,
(r) j

mod m

( (xi)))

(x) , . . . , f

(x) , (x) ,

i mod m -- i m, -- , n- z {0, 1, . . . , 2n - 1} : , (0) = 0, (1) = = 2n-1 , (2) = 2n-2 , (3) = 2n-2 + 2n-1 . . {xi } n- ( {0, 1, . . . , 2n - 1}) m · 2n , m . , {xi } (, , 2n mn) , k- (0 < k n) 1/2k . {zi } m · 2n , {0, 1, . . . , 2n - 1} m . , {s (zi) : i = 0, 1, 2, . . . }, s - s (zi) (0 s n - 1) , 2n ( , 2n) , ( , {zi }) 2n-1 . . n- , , , n- 5 . n (, n > 64) ; , 32- , 232
5 , .

F j (x) = F

(x) , . . . , F

(r) j

f j , F j : Z/2k Z/2k -- k. , , , n = 256 8- 32- ; m · 2264 , s - s = 256 2255 . [5] [6] . , , [710] , . 2- , (. . ) ( ) . [9] , [8] . [24] 6 . , , [11] . [12] ,
6 [5] [6] , .

130

. .

( , , «» ) . , , . , NIST DIEHARD.

. .
-- , . , , , () , f , . «», , , . f , , , , , . , «» , , . , , . , , , . , . , , m n , n - m - 1. , , . , , . 20022003 (N. Courtois) -- [5] , [6] ,

[1] Schneier B. Applied Cryptography. John Wiley and Sons, 1996. [2] Klimov A., Shamir A. A new class of invertible mappings. In. Cryptographic Hardware and Embedded Systems 2002 (B. S. Kaliski Jr. et al., eds.) , Lect. Notes in Comp. Sci., Vol. 2523, Springer-Verlag, 2003, pp. 470483. [3] Klimov A., Shamir A. Cryptographic applications of T -functions. In: Selected Areas in Cryptography, 2003. [4] Klimov A., Shamir A. New Cryptographic Primitives Based on Multiword T -functions. 2004 (to appear) . [5] Anashin V . Pseudorandom Number Generation by p -adic Ergodic Transformations. 2004, http://arXiv.org/abs/cs.CR/0401030. [6] Anashin V . Pseudorandom Number Generation by p -adic Ergodic Transformations: an Addendum. 2004, http://arXiv.org/abs/cs.CR/0402060. [7] . . p - , II. , 14 (2002) , 4, . 3 64. http://arXiv.org/abs/ math.NT/0209407. [8] Anashin V . Uniformly distributed sequences over p -adic integers. Number theoretic and algebraic methods in computer science. Proceedings of the Int'l Conference (Moscow, JuneJuly, 1993, A. J. van der Poorten, I. Shparlinsky, H. G. Zimmer, eds.) , World Scientific, 1995, 118. [9] . . p - . . , 55 (1994) , 2, . 346. [10] Anashin V . S. Uniformly distributed sequences in computer algebra, or how to construct program generators of random numbers. J. Math. Sci. (Plenum Publishing Corp., New York) , 89 (1998) , No. 4, pp. 13551390. [11] Shamir A., Tsaban B. Guaranteeing the diversity of number generators. Information and Computation, 171 (2001) , pp. 350363. Available at http: //arXiv.org/abs/cs.CR/0112014. [12] Tsaban B., 2004 ( ) . [13] Knuth D. The Art of Computer Programming. Vol. 2: Seminumerical Algorithms. Third edition. Addison-Wesley, Reading, MA, 1998.

132

. .

. . .

133

c . , . , . . f , ( -- ) , g , f · g . . , , , . , , . [3] , [4] , , , . [3] . f , AI (f ) k , g k, f f + 1 (. . f · g = 0 (f + 1) · g = 0) . [6] n -- , , [n/2] . [3] -- , , -- . . , d n , d n , n . -- 0.27. , -- , d , , . , , , .

, . . [1] , [710] . , , , , , , . . , , , [2] . , f0 f1 , , f0 f1 , , , ( ( , , f0k) f1k) k. : 1. F f0 f1 , F -- f0 f1 . h F h F c AI (h ) AI (h) .

, , , k, ( ) , k. , , , d . , n, , , d , . [3] , n d ,
n n n · d -1 . , 8d 4d n, n - 3k (, ) , (1 + d / (n - d)) 9k , -- (1 + (d - 1) / (n - d)) 6k , d , n.

1

3

1

134

. .

. . .

135

, , [8] 2. , AI (h) = d , deg (h) = k, AI h
(k-1) (k-1)

[7]

d + 1.
(k-1)

h (k-1) F (k-1) , F (k-1) = 1. h --

. f0 , f1 . , , AI (h) ( n) ,

[8]

[9]

n -- h. ( n) , n -- , . , , -- .

[10]

2003, Proceedings, Lecture Notes in Computer Science, V. 2656, pp. 345 357, Springer-Verlag, 2003. Fedorova M., Tarannikov Yu. On the constructing of highly nonlinear resilient Boolean functions by means of special matrices. Progress in Cryptology -- Indocrypt 2001, Chennai, India, December 1620, 2001, Proceedings, Lecture Notes in Computer Science, V. 2247, pp. 254266, Springer-Verlag, 2001. Tarannikov Yu. On resilient Boolean functions with maximal possible nonlinearity. Proceedings of Indocrypt 2000, Calcutta, India, December 1013, 2000, Lecture Notes in Computer Science, V. 1977, pp. 1930, SpringerVerlag, 2000. Tarannikov Yu., New constructions of resilient Boolean functions with maximal nonlinearity. Fast Software Encryption, 8th International Workshop (FSE 2001) , Yokohama, Japan, April 24, 2001. Revised Papers, Lecture Notes in Computer Science, V. 2355, 2002, pp. 6677. Tarannikov Yu., Korolev P., Botev A. Autocorrelation coefficients and correlation immunity of Boolean functions. Proceedings of Asiacrypt 2001, Gold Coast, Australia, December 913, 2001, Lecture Notes in Computer Science, V. 2248, pp. 460479, Springer-Verlag, 2001.

[1] . . - . , . 11, .: , 2002, . 91148. [2] . . . . 2324 2003 . .: , 2004, . 160164. [3] Meier W ., Pasalic E., Carlet C. Algebraic attack and decomposition of Boolean functions. Proceedings of Eurocrypt 2004, Interlaken, Switzerland, May 26, 2004, Lecture Notes in Computer Science, V. 3027, pp. 474 491, Springer-Verlag, 2004. [4] Armknecht F . On the existence of low-degree equations for algebraic attacks. Cryptology ePrint archive (http://eprint.iacr.org/) , Report 2004/185, August 2004, 16 pp. [5] Courtois N. Higher order correlation attacks, XL algorithm, and cryptanalysis of Toyocrypt. Proceedings of 5th International Conference on Information Security and Cryptology (ICISC 2002) , November 2829, 2002, Seoul, Korea, Lecture Notes in Computer Science, V. 2587, pp. 182199, Springer-Verlag, 2002. [6] Courtois N., Meier W . Algebraic attacks on stream ciphers with linear feedback. Advances in Cryptology: Eurocrypt 2003, Warsaw, Poland, May 48,

. . 137 b Vk , fib , .,. .. ., .i,k b . 1 2 ( 2] . la f [) f Fn k, f k-. . . 1. : Vn Vn -- Vn , (X) = = (f1 (X) , . . . , fn (X)) , f1 , . . . , fn Fn . k (0 < k n) k f1 , . . . , fn . . , 1 s1 < . . . < sk n b Vk , m > k f
b (1) , . . . , b i1 s1 , . . . , sk
(k) (1) (k)

. .
(. [5] ) . , . , - . -- , [2] . . F2 -- . n N Vn = Fn . Vn : x, y -- 2 x (i) -- i - x; x, y -- x y. , n , Fn . X = {x (1) , . . . , x (n) } , f (X) f x (1) , . . . , x (n) Fn , . , , : f (x) . deg f -- f . f (x) = x, a b la,b . (1) (s) fi, . ,. .. ,. .is, 1 f (x (1) , . . . , x (n) ) (s n) , (1) , . . . , (s) x (i1) , . . . , x (is ) . - m m- ., , [1] . 1 ( 2] . f Fn k-[) , 0 k n - 1, 1 i1 < . . . < ik n,

= c1 , . . . , f

b (1) , . . . , b im s1 , . . . , sk

(k)

L = {u Vn : u (s1) = . . . = u (sk) = 0} L = = {v Vn : v (i1) = . . . = v (im) = 0} Vn . dim L = n - k > dim L = n - m, L b L c, c = (c1 , . . . , cm) . , . 1. f 2n M- la f = n. . M- (., , [1] ) : Vn Vn -- Vn Fn -- n .
n

= cm , ci {0, 1} (i = 1, m) .

f (x, y) = x, (y) (y) ,

x, y Vn ,

f (x, y) = x, (y) =
i =1

x (i) fi (y) ,

fi Fn -- (i = 1, n) . (X) , deg fi 1 i = 1, n, 1 l y l fi . , la f = n. f (x, y) (y) . y (n ) f -

138

. .

. . 139 , la f = la f3 (n-m) -7,1 . f3 (n-m) -7,1 . n n + 2. f1 (x1 , . . . , x f2 (x1 , . . . , x f f = (x = (x
n+2)

, . , x y , f f . , la f = n. -, , . , f M. = (f1 , . . . , fr) ,
r

=f =f

n,1

(x1 , . . . , x

i -1

,x

i +1

, ..., x
n+2

j -1

,x

j +1

, ..., x

n+2)

n+2)

n+1,2

(x1 , . . . , x

n+1)

n+3,1 n+4,2 n+3 n+3

x

,
n+2)

xi x j ,

f (X) = f

,

(X) =
i =1

x (i) fi x

(r +1)

, ..., x

(n)

x

(r +1)

, ..., x

(n)

.

(1)

2 ( 4] . f Fn (1) , p , r -- [) , n r > p 0, : Vn-r Vr wt ( (u)) p u Vn-r , -- Fn-r . f -- m- m p . 1. f , 2, la f n - r . . . , n - r < p m , , , , . 2. m- f , , , [3, § 6, 7] , la f
m+3 . 2

1) f1 (x1 , . . . , xn+2) f2 (x1 , . . . , x xn+4 1) f1 (x1 , . . . , xn+1) (x
n+3

,
n+2)

, la f
n+3,1

x

n+4) f2

(x1 , . . . , x

x

n+3

.

min{la f1 , la f2 } + 1 = min{la fn,1 , la f

n,2

} + 1.

1. k = 3 la f2,1 1. , la f k - 2 k , , [3] , m-
m+3 . 2

3, , m = 2k - 7, , la f

m+3 . 2

. , [3] . f
n

2 , , , ( ) . 2 . k k 3. fn,1 fn,2 , [3, §7, 30] , 2 (k - 2) .

f (x1 , . . . , xn) = f

3 (n-m) -7,1

(x1 , . . . , x

3 (n-m) -

7) i =3 (n-m) -6

xi ,

[1] . ., [2] . ., . ., . . . -- .: , 2004. . ., . . k-. -

f3 (n-m) -7,1 -- 3 (n - m) - 7 (. [3, § 6, 28, 29, 7] ) . n = 3k - 7, m = 2k - 7, k 3 -- .

140

. .

. 2324 2003 . -- .: , 2004, . 176178. [3] . . - . . . 11, -- .: , 2002, . 91148. [4] Carlet C. A Large Class of Cryptographic Boolean Functions via a Study of the Maiorana-McFarland Constructions. Advances in Cryptology: CRYPTO'02. Lect. Notes in Comput. Sci. V. 2442. -- New York: Springer-Verlag, 2002, pp. 549564. [5] Siegenthaler T . Correlation-immunity of Nonlinear Combining Functions for Cryptographic Applications. IEEE Trans. on Information Theory IT30 (5) : 776780, 1984.

. . , . .
-- [1] . [1] , [2] . . F2 -- , Vn = Fn -- 2 - F2 , Fn -- , Vn F2 . Fn Fn , n . deg (f ) (. . .) f Fn . x Vn f Fn wt (x) wt (f ) . dist (x , y) = wt (x y) x, y Vn , dist (f1 , f2) = wt (f1 f2) f1 , f2 Fn ( -- mod 2) . deg (f ) 1, f . Fn An . f Fn ; 1 i1 < . . . < i
k

n,

b = b (1) , . . . , b
(1)

(k) T
(k)

k Fn-k , 1. 0 k n - 1, 1 , f
b , ..., b i1 , . . . , ik
(1)

n fib , .,. . . .i,k b ., 1 f x (i1) = b (1) , . . . x (ik) = b (k) . f Fn k-,
k

Vk ,

i1 < . . . < i
(k)

n,

b = b (1) , . . . , b

(k) T

Vk

, deg f
b (1) , . . . , b i1 , . . . , ik
(k)

1.

( 02-01-00581 02-01-00687) .

, , 0- Fn (1) (2) (n) (1) (2) (n) : x x . . . x x x . . . x 1.

142

. . , . .

. . k = la f c or f = r .

143

2. la f f Fn k, f k-. f Fn la f n - 1. la f f GA (Vn) . 1.

, f wt (f ) = (2t + 1) 2s t , t 1 s . 1
(1)

i1 < . . . < i
(k)

k

n,

b = b (1) , . . . , b

(k) T

f (x) = f x (1) , x (2) , x (3) , x , la f = 1. 1 0 A= 0 0

(4)

=x

(1)

f (x) = f g (x) = f (Ax c) = x (1) x (4) · x (2) x (3) x (4) . , la f = la f g = 2. , , GA (Vn) . 3. f Fn - r , 1 r n, 1 j1 < . . . < jr wt f
(1)

g GA (Vn) g = (A, c) , 001 0 0 1 0 1 , c = . 0 0 1 1 001 0

·x

(2)

x

(3)

x

(4)

.

Vk r ,

, fib , .,. . . .i,k b An-k . , k ., 1 f - k wt f , wt f
b (1) , . . . , b i1 , . . . , ik
(k) (k)

=

wt ( f ) (2t + 1) 2s = , 2k 2k

b (1) , . . . , b i1 , . . . , ik

2t + 1. -

, wt f An-k 0, 2 , 2 . . Un -- Fn , 2n # Un = 2n-1 . Qn = Un Fn Un , . - :
n-1

b (1) , . . . , b (k) i1 , . . . , ik n-k-1 n-k

n,

a = a , ..., a
(r)

(1)

(r) T

a (1) , . . . , a j1 , . . . , jr
(r)

Vr

q n = # Qn =

s =0

(-1)

s

n s

2n-s 2n-s -

1

.

(1)

wt ( f ) = r, 2

, f ja , ., ...., . jr a Fn-r . 1 (. [3] )

qn . j = 1, 2, . . . , n M j Qn , g (x (1) , . . . , x (n) ) = g (x (1) , . . . , x
(j -1)

,x

(j +1)

N -- . , 3 , f Fn . . . 1. f Fn , cor f > 0, wt (f ) = 2i , i = 0, 1, . . . , n - 1. la f > cor f . . , k > 0 ,

cor f = max {r N : f -- - r },

deg (g ) = n - 1 g n -1 1. M j1 M j2 = , j1 = j2 #M j = 22 -n j = 1, 2, . . . , n, n -1 (2) qn n 22 -n . Qn i = 0, 1, . . . , n - 1, #Qni = qni . Qni = { f Qn : la f = i },
1

, . . . , x (n) ) x (j) ,

Qn = Qn0 Qn1 . . . Qn,n- qn = q
n0

(3) (4)

+q

n1

+ ... + q

n,n-1

.

144

. . , . .

. .

145

Qn0 , , qn0 = 2. qn,n-1 . . 2. f Fn la f = = n - 1 , f x (1) , . . . , x
(n)

la f > n - 2. , , Fn n - 1. , la f = n - 1. 1. qn,n-1 < 2n+1 . . , (5) . 2. limn qn,n-1 /qn = 0. . 1 (2) . {qni : i = 0, 1, . . . , n - 1} . , . 1. a) ( ) . n0 , n n0 (q t =
n0

=
i< j n

x (i) x

(j)

lab x (1) , . . . , x

(n)

,

(5)

lab x (1) , . . . , x (n) = i =1 a (i) x (i) b , a Vn , b F2 . . . f Fn la f = n - 1. (i1 , i2 , . . . , in) {1, 2, . . . , n} x (i1) = 0, . . . , x (in-2) = 0. , 2, x (in-1) x (in) , . , . . . f x (in-1) x (in) . (i1 , i2 , . . . , in) , . . . n (n - 1) /2 2. , . . . f x (j1) x (j2) x (j3) , j1 < j2 < j3 . n - 2 . x (i) = 0, i = j1 , j2 , j3 , x (j3) = 1. f 3 , x j1 x j2 x j3 , x j1 x j2 . 1, x (j1) x (j2) , . x (j1) x (j2) x (j1) x (j2) a (j1) x (j1) a (j2) x (j2) b , a (j1) , a (j2) , b F2 . la f = n - 2, . , x (j1) x (j2) x (j3) . . . f . (j1 , j2 , j3) , , . . . f 3. , . . . f 3, f (5) . . f Fn (5) . , 1 deg f i1 < . . . < i
n2

+q

n1

+ . . . + qnt) /q 1.

n

c,

n+1 , 0.5 < c 2

b) ( ) .
n

lim (q

n0

+q

n1

+ . . . + qnt) /qn = c ,

t =

n+1 , 0.5 < c 2

1.

. . -- , k Vn (·, k) : Vm Vm , Vm . (x, k) = y, x Vm ( ) , k Vn , y Vm ( ) . (f1 , f2 , . . . , fm) -- , y
(i)

: Vm в Vn Vm

n,

a = a (1) , . . . , a
(n-2) 2

(n-2) T

Vn-

2

=f

i

x (1) , . . . , x

(m)

, k (1) , . . . , k

(n)

,

i = 1, 2, . . . , m.

a (1) , . . . , a i1 , . . . , in-

= 2.

,

146

. . , . .

( S-) , ( ) . , - ( ) . , , m + n , Qm+n . f -- . 0.5 la f
m+n+1 . 2

. . , . . , . .

[1] . ., . ., . . k- . . 2324 2003 . -- .: , 2 0 0 4 , . 1 7 6 1 7 8 . [2] . . . . , 2829 2004 . [3] . ., . ., . . . -- .: , 2004.

- () , . , , , CD-. , . , . , , , . , , . , , . , , ( ) . . - . , , , . , . . , , . , .

148

. . , . . , . .

149

, , , , , , ? , -- , . 1200 /. 9,6 / . 300 /. ( ) . , , . «» -, . ? . , ( ) , () . . «1» , . , . -- . . -- , . . . , . . , , , ? , (. 1) . . , () .

: (0 1) ? , . . , , . . , .

. 1. .

, , . . 0 1. . ( . 1 . . , ? , . . -- -- . .

150

. . , . . , . .

151

, , , . . - : - . -- . , , . - , . 2 , , , . . . ,

44100 . 3 . 15 , . . 600 . (. . 1) . 2 , (. 2) . . . , 2 . (100%) 2 . (. 3) .

. 3. CD- .

. 2. 2 CD- .

, . , 2 m = (1/3) m, m . 2 (. 3) .

152

. . , . . , . .

153

, . , -- . . -- : · P. . -- () , · P -- , · P. -- . , , . 2 -- . , 2 . , . , . . .

, . : -- 1 1, 1 0, 0 1, 0 0; 0 1. , . 4. , . 1 1 0 0, . .

. 5. 0 0, 0 1, 1 0, 1 1 ; n 600 000, 15 .

. 4. 2 .

, . , , . 2 . , 1 1, 0 0 0 1, 1 0 . . 6.

154

. . , . . , . .

155

, . 4. - , , , . . , . , , . . , . , , - () .

. 6. .

, , , , . . . 1. , , , , . -- . 2. . : -- , , , , . 3. -

MV2

157

MV2 . .

MV2, . , , , , , , . , MV2 , . . , . MV2 , . -- -- MV2. , . MV2 (. [1] ) .

n n - r + 1 . c f -- y = c (x) , , y {0, 1}k , r + 1 k n - 1, f (x) = n - k, c (x) = y {0, 1}r , f (x) n - r n - r + 1. r Fn . [2] . r z = f (x) T = (c , f ) Fn , () : z 12 1 01 3 ... n-r n-r+1 02 1 . . . 0n-r -1 1 0n-r

0i i . . , (1) n- x (c , f ) , . MV2, M T = (c , f ) , M = = x1 x2 . . . xL xi {0, 1}n . c (M) , c (xi) , f (M) -- , f (xi) c (M) = c (x1) c (x2) . . . c (xL) ; f (M) = f (x1) f (x2) . . . f (xL) . (2) c (M) , f (M) -- M T = (c , f ) . r T = (c , f ) Fn , L C {0, 1} , Nc = #{M : c (M) = C } [3, . 215]
[L/r ] [ (L-rl ) / (n-r) ] k=0

MV2 :
n-1

T : {0, 1}

n

i =r +1

{0, 1} в {n - i }

i

{0, 1} в {n - r , n - r + 1} . (1)

r

Nc
l = [L/ (n-1) ]

(-1)

k

l k

L - (r - 1) l - (n - r) k - 1 . l -1

(3)

(1) T = - = (c , f ) . c : {0, 1}n n=r1 {0, 1}i -- i n , n-1 y i =r +1 {0, 1}i , y {0, 1}r 2 . f : {0, 1}n {1, 2, . . . , n - r + 1} --

r 1. T = (c , f ) Fn M = x1 . . . . . . xL , L xi , {0, 1}n . E (|c (M) |) E (| f (M) |)

E (|c (M) |) = n - 2 + 2r

-n+1

· L;

E (| f (M) |) = 2 - 2r

-n+1

· L.

(4)

158 3 7 , 1 6.

. . MV2, n = 8 r = 3, . . , () , () (1) [4] .

MV2

159

MV2
MV2: : M (8 в l bits) K ( 32 в 8 в 260 bits) P (C , F )

1. Ci -1 = Mix (Ci -1) -- ; 2. () Ri ; 3. Ri , j -- K ; 4. T j (Ci -1) = (Ci , Fi) -- T j Ci Fi ; 5. Ci = Ri Ci ; F = Fi F ; End. C = CP ; END. MV2, . , Lc P Ci Lc . MV2 [5] . . . MV2, -- , . , , . [4] , [5] . . . - . MV2 . , , AES [6] . MV2 , 1 {0, 1}i , i= :

:

: : (C , F ) K ( 32 в 8 в 260 bits) M (8 в l bits)

C , F -- . MV2 [7] . , MV2 . . . (1) , , . : BEGIN C0 = M; F = ; For i = 1; To i = P

160

. .

MV2

161

1. y1 {0, 1}i y2 {0, 1} j , y1 = (Y11 , Y12 , . . . , Y1i) , y2 = (Y21 , Y22 , . . . , Y2 j) , Yks {0, 1},

wt (·) -- , l = min{i , j } m = max{i , j }. , MV2 , MV2 . MV2 [4] , [5] .

wt (y1 , y2) = wt ((Y11 , . . . , Y1l ) , (Y21 , . . . , Y2l ) + m - l ,

(5)

: · -- ; · -- , ; · , ( , ) ; · , , ; · MV2 -- , , ; · MV2 ; · MV2 .

[3] . . . .: , 1982 . [4] . ., . ., . . MV2 // . 34. 2003. . 1 1 3 1 2 1 . [5] . ., . ., . . MV2 () // . 2 0 0 4 , 1 . . 7 7 8 8 . [6] Preneel B., Bosselaers A., Rijmen V ., Van Rompay B. Granboulan L., Stern J., Murphy S., Dichtl M., Serf P. Biham E., Dunkelman O., Furman V . Koeune F ., Piret G., Quisquater J-J., Knudsen L., Raddum H. "Comments by the NESSIE Project on the AES Finalists" [Electronic resource] . 2000. http://csrc.nist.gov/CryptoToolkit/aes/round2/comments/ 20000524- bpreneel.pdf. [7] Mischenko V . A., Zakharau U. U., Vilansky Y . V ., Verzhbalovich D. I. Method for encrypting information and device for realization of the method // International Publication Number: WO 00/65767. http://pctgazette. wipo.int/. 23 p.

[1] . . // . 2004. 5. 1. . 1 4 6 1 4 9 . [2] . ., . . // i i. . i.-. . 2004. 3. . 4753.

- . . .

163

- . .
R -- , R M -- m, n N, f : Mn M, f (0, 0, . . . , 0) = 0. f Rn (I , S , ) , I = M, S = M (n) , x2 x1 x2 . . . (1) (i , s) = i (s) = i . = . . x . xn f (x1 , . . . , xn) + i
n

x () M, x t x . ek (k 1, n) , i M (0, 0, . . . , i , . . . , 0) t M (n) , i k- , ek i -- ek i M. F : S S n , F (s) = k=1 ek yk (s) . yk (k 1, n) F . a M (n) ta a, - s s + a. i I i = ten i 0 , ten i = i 0 1 . - i-1 = 0 1 t-en i , B f Rn k,i | k 0, ord 0 - 1, i I ,
k k,i = 0 ten i -k 0 f

.

f (1) . . « » «». f Rn , f (x1 , x2 , . . . , xn)

x1 . . i (i I) S (M (n) ) . , S (M (n) ) -- , . G f i | i I < S (M (n) ) f - Rn . a I a 0 1 -1 , a 0 -1 G f . B f aI a 0 f Rn . , B f -- G f .
-2358.2003.9.

ta | a M (n) < S (M (n) ) . , f , f (x + y) = f (x) + f (y) x , y S . 1. f B f = . . . , a - M (n) b M (n) , 0 1 ta 0 = tb . , a = (a2 , . . . , an , a1) t , -1 x1 f1 (f (x1 , . . . , xn) + a1 , x2 + a2 , . . . , xn + an) x2 x2 + a2 - 0 1 ta 0 . = , (2) . . . . . xn xn + an f f
-1 1 -1 1

, f x1 :
-1 1

(f (x1 , x2 , . . . , xn) , x2 , . . . , xn) = f (f

(x1 , x2 , . . . , xn) , x2 , . . . , xn) = x1 .

g (x) - 0 1 ta 0 . : f
-1 1

(f (s) + a1 , x2 + a2 , . . . , xn + an) = g (s) , f (g (s) , x2 + a2 , . . . , xn + an) = f (s) + a1 .

f (s) . f , f (g (s) - x1 , a2 , . . . , an) = a1 .

164

. .

- . . .

165

- - b1 = f1 1 (a1 , a2 , . . . , an) , g (s) = x1 + b1 , . . 0 1 ta 0 = tb , t b = (b1 , a2 , . . . , an) . k,i . B f . , B f B f = . . B f = , a M (n) - b M (n) , 0 1 ta 0 = tb . a = (a2 , . . . , an , a1) t -- M (n) , b b1 . (2) :

f

-1 1

(f (s) + a1 , x2 + a2 , . . . , xn + an) = x1 + b1 , (3)

f (x1 + b1 , x2 + a2 , . . . , xn + an) = f (s) + a1 .

s M (n) . s = 0, f (b1 , a2 , . . . , an) = a1 . (4) y = (y1 , y2 , . . . , yn) M (n) . a1 = f (y1 , y2 , . . . , yn) , ai = yi i 2. f : (b1 , a2 , . . . , an) = = (y1 , y2 , . . . , yn) . (3) (4) f (s + y) = f (s) + f (y) s , y M (n) . , f . . [2] , R = M = Z2 , . , , . [2] : f 1. Rn , A1 , A2 , . . . , An R M, f (x1 , x2 , . . . , xn) = An (x1) + An-1 (x2) + . . . + A1 (xn) , k 1, n Ak (0) = 0. , . 1 . k 1, n fk f (0, . . . , 0, xk , 0, . . . , 0) , k-. , , -

, , . 1. f () , B f f1 , f2 , . . . , fn () . , R = M = GF (q) f , f Rn , . , f1 , f2 , . . . , fn , -. R = GR (q d , p d ) -- , G (x) R [x ] . [1] G (x) t G (x) | x t - 1. G (x) T (G) , G (x) G . G (x) , G , , T (G) = T G . f Rn R . f (x1 , x2 , . . . , xn) = an x1 + an-1 x2 + . . . + a1 xn , Rn G -- , N G , H < G . , N H , N H . , 4.1 3.1 [2] : f 2. R = GR (q d , p d ) , Rn -- - R , : f 1. Rn -- . 2. G f = N g , N -- ord g p . 3. G f , p . 2. R -- f 2. - Rn R M : f 1. Rn -- , 2. G f = N g , N -- 2-, 3. G f 2- . f (x) = x n - a1 x
n-1 f n-2

- a2 x

- . . . - an R [x ] .

166

. .

- . . .

167

G (x) GF (q) [x ] , . 4.2, 4.4 4.5 [2] : f 3. - Rn GF (q) : f 1. Rn . 2. G f 2- , . 3. G f 2- . f 4. R = M = GF (q) , n > 1, Rn -- -. 1) G f -- f S , Rn ; 2) , R = M = Z p , . f 5. R = M = GF (q) , Rn -- -. 1) G f f , Rn ; 2) , R = M = Z p , . [3] , , . , , , . . , , , . , [1] . : 3. R = M = Z p , f . :

f 1. Rn , f , f . 2. G f , . 3. G f . 4. G f , -- p -. 5. G f . f 2. Rn -- - Z p f n -- . Rn -- (2) (5) 3. . . .

[1] . ., . ., . . . .: , 2003. [2] . . - . , . 7, 2004. [3] . . .: . . ., 1962.

, . . .

169

, . .
n, m d . k r , 0 r < d , , n = kd + r . 1, 2, . . . , n S (n) . [1] u v , 1 u < v n, = (1 , 2 , . . . , n) S (n) , i j , i = u j = v , i > j . , u u + 1, 1 u n - 1. S (n) , (n) m, Sm . (l) Sk,r (d) -- = 1 2 . . . l 1 d , {1, 2, . . . , r } k + 1 , {r + 1, r + 2, . . . , d } k . (n) F : S (n) Sk,r (d) : = 1 2 . . . n S (n) , F () = = 1 2 . . . n d , i = i (mod d) , i = 1, . . . , n. . (n) F (Sm ) A (n, m, d) . (i1 , i2 , . . . , il ) , 1 l < n, {1, 2, . . . , n} , 1 i1 < i2 < . . . < il n. (l) Sk,r (d) (i1 , i2 , . . . , il ) , A (n, m, d) , i j = j j = = 1, 2, . . . , l . , (i1 , i2 , . . . , il ) , PosSel (i1 , i2 , . . . , il ) . d = 2 i {1, 2}, j {1, 2, . . . , l }. (l) Sk,r (2) Ni (j , ) i 1 j .

Y

max

( ) = max

Y (j , ) = N2 (j , ) - N1 (j , ) ,
j =0, ..., l

Y (0, ) = 0,
j =0, ..., l

Y (j , ) ,

Y

min

( ) =

mi n

Y (j , ) .

I (A) A, I (A) = 1, 0, A ; .
(l)

. Sk,r (2) , 1 l < n. 1) PosSel (1, 2, . . . , l) , Y
max

( ) + Y

min

A = (Ymin ( ) = 0) (Y (l , ) 2 (k - 1) - l - r) ; 2) , Y A = (Y (l , ) r) (Y
min max

( ) - I (A)

m,

PosSel (n - l + 1, n - l + 2, . . . , n) ( ) + Y
min

( ) - I (A)

m,

( ) + Y (l , ) > r)

, [3] . , , [3] .

(l + r - Y (l , )

2 (k - 1)) .

[1] . ., . ., . . . .: , 2003. [2] . . . .: , 1982. [3] . . , . . . ., 2004, . 11, . 1, . 123124.

. . .

171

. .
Ts , s GF (q) , q = p l . (i) (i) (i) i - x1 , x2 , . . . , xi , i = 1, s - 1, (i +1) (i +1) (i +1) (i + 1) - x1 , x2 , . . . , xi +1 : x j = x j + x j +1 , j = 1, i , , GF (q) . s - . Ts . s0 Ts0 , Ts . r 0 Ts0 s - Tr, r ( s - ) . Tr , Ts0 , . , Ts0 , 1- Tr. Tr log p r + 1 (p - 1) p j -1 , j -- , j 1, log p r . 0 1- Tr. . - -1 c . , 1. Tr j c p j , j 0, log p r . 2. Tr c . . k > 0 s > S ks s - s0 R , R = R (k) S = S (k) -- k .
(i) (i +1) (i +1)

q = 2 [1] . . 0 = k0 < k1 < k2 < . . . , K > 0 s > S (K ) : Ms () = 0,

Ks -

/

i =0

(ki s - i , ki s + i) ,

i , i 0 -- . , Ts Ks (ki s - i , ki s + i) , i 0, s .

[1] . ., . . . . . 11. . 2. . 245246. .: , 2004.

. . .173
| j () |2
=1

E =

. .
G -- , , 1 , . . . , s -- G . j (g) =Pr{ j = g }, g G , j = 1, . . . , s , p (g) = Pr{ = g }, g G , + j , j = 1, . . . , s . , , 1 , . . . , s , + j n j , j = 1, . . . , s . p (g) , g G , p (g) , g G , p (g) , g G ,
s

1 |G |

j

1 nj

х

1 - | p () |2 | j () |2
j

| j () |2

Ў2

,

(3)

p () -- p (g) G , G -- G (. . G) . , j (g) , g G , j = 1, . . . , s , . , (g) g G j N j j j (g) , g G , j = 1, . . . , s , n j + j , j . P (g) j (g) , , , P () () j j j . p (g) p (g) , p () mi n
p () =1 j

p () () - P () j j

2

+ 2 | p () |2 ,

mi n
p (g) j =1

p j (g) - P (g) 2 , j

(1)

: · p j (g) -- p (g) j (g) ; · P (g) = n j (g) /n j -- g n j ; · n j (g) -- , + j g , g n j (g) = n j , g G , j = 1, . . . , s ; · f (g) 2 = g G | f (g) |2 , f (g) -- g. p (g) p (g) , g G , = p - p 2. (2)

2 > 0. p (g) , (2) . E , (3) . , - = 1 - 2 + = = 1 + 2 , 1 , 2 -- G p (g) , g G , G ,
g

2. n j , N j , n j = o (N j) ,

1 = O (1) , j = 1, . . . , s , N j 2

p (g) - |G |-

12

= ,

(4)

. 1. s=1 | j () |2 = 0, G , j

|G |-1 (|G | - 1)
-1

.

174

. .

. . .175 1 = (11 , 12 , . . . , 1n) n , n = ds , s -- . G = { g0 , g1 , . . . , gd -1 }, g0 G , . = (1 , 2 , . . . , n) G (s , s , . . . , s) . ( [7] , . 225) . 1 . 1 , , 1 . = (1 , 2 , . . . , n) 1 1 G , . . i = 1i + 1i , i = 1, 2, . . . , n. = g G p 2 (g) , , (8) . 2 =
1 s

P- (g) P+ (g) , g G , - + , . R- =
g

P- (g) - |G |- P+ (g) - |G |-

12

, .

(5) (6)

R+ =
g

12

p (g) , g G , 1 2 (4) R- R+ . 3. R- R+ , (5) (6) , . R- R - , R- = R
-

|G | 2

2

-1

,

(7)

R- (5) . 4. ER
k -

E2

х

(x ( )) + E (X 2)

2

2

х
2k

(x ( ))

2

2

k

=

,

k = 1, 2, . . . ,

: · (. . = 1) G , 2 = 1; · , -1 , = -1 , G ; · x 2 ( ) , x 2 ( ) , ; · x 2 ( ) , x 2 ( ) , X 2 «-», , , |G | - 1 . , , G , |G | = d , Pr{ = g } = p (g) , p (g) = 1, p (g) 0. (8)
g G

(g) = ( (g) - s) / s , g G ; (g) -- g - . 5. 1 - 2 /d (8) , 2 (9) . [36] .

g G

( (g) - s) 2 =

2 (g) ,
g G

(9)

[1] . . . , . 34 (76) , . 1, 1954, . 8 9 1 2 6 . [2] . . . .: , 1978, 343 . [3] . . N -. - . . , . 5, . 2, 1998, . 245. [4] . .

176

. .
. . .: - , . 4, 2001, . 129148. . . . . .: - , . 7, 2003, . 114 125. . . . . .: , . 8, 2004 ( ) . . . . .: , 1977, 319 . . . , , . , . 43, . 2, 1998, . 397403.

[5]

[6]

. . , . . , . .

[7] [8]

1.
G -- #G = N , G -- . D G ZD G ZD () = (x) .
x D

D , [3] : 1, 1 ZD () (y -1) = N 0,
G

y D , y D . /

ZD () [3] : |ZD () |2 = (x) (y) =
G x ,y D x ,y D G

xy

-1

G

= N · #D . (1)

(1) . 1. D G , ZD () =
x D

(x) = 0

G , = 0 .

( 02-01-00581 02-01-00687) .

178

. . , . . , . .
G

. . .

179

. = 0 , (1)
2 G =0

|ZD () |2 (2)

H D , , H G (D) . . , AD

|ZD () | = #D (N - #D) .

= D. , D -- D --

, #D = N , , . . «» . «» : D G H < G , D x0 H x0 D . : A D = x G | (x) = 1 D . D = G | (x) = const x D , ZD () = 0 G , = 0 .

H H -- G (D) , A G (D) . , D ZD () , D= G

|ZD () | = #D .

, ZD () G D , . . D , G x0 D ZD ( ) = ZD () (x0) . , , A D . , 1 1, . 2. D G G , ZD () G : 0 #D .

, D -- G , A D -- G . 1. A D -- H G , . H G H G [1] , H H G G . D G G (D) = H < G | x
-1 0 - x0 1 D H

2.
. [2] . G = Vn -- n , D = {x Vn | f (x) = 1}, f (x) -- . ZD () = Z f () =
x: f (x) =1

x0 D .

H = G | (x) = 1 x H .

G = (-1)

,x

, x Vn ,

, x = 1 x1 + . . . + n xn , (-1) -
,x

=
f (x) + ,x

G (D) = D .

D H x0 D ,

=

1 2

, H H G (D) G (D) . , H G (D) , H - y D x0 1 y = 1, ,

2n-1 - 1 W f (0) , 2 = - 1 W () ,
2
f

xVn

(-1)

,x

xVn

(-1)

=

= 0; = 0,

180

. . , . . , . .

. . .

181

W f () -- -- , D = { Vn | = 0, |W f () | = 2n - W f (0) } {0}. (3)

Vn -- Vn , , . 2 . 1. f (x) - k , |W f () | Vn , = 0 0 2k+1 . 1 , . . . , k Vn -- D , (3) , x0 Vn -- f (x0) = 1, 1 , f (x) = 1, i , x = i , x0 , i = 1, . . . , k. , f (x) , 1 , x = 1 , x0 , .................. (4) k , x = k , x0 . , 1 . 3. f (x) f (x1 , . . . , xn) = ( 1 , x + x0 + 1) . . . ( k , x + x0 + 1) в в ( k+1 , x , . . . , n , x ) . (5) A D = {x Vn | i , x = 0, i = 1, . . . , k},

, (5) f (x) . , (5) , [67] . (x) f (x) , x Vn (x) f (x) = 0. . 2. f (x) (5) . f (x) 1 , x + + 1 , x0 , . . . , k , x + k , x0 , (y1 , . . . , yn-k) (. . ) . , f (x) , -- W f () . f (x) -- . 4. (x) f (x) , : 1) W f (0) + W (0) - W f + (0) = 2n ; 2) W f () + W () - W f + () = 0 Vn , = 0. . (-1) W
f (x) (x)

=

(-1) 0 + (-1)

f (x)

+ (-1) 2

(x)

- (-1)

f (x) + (x)

,

Vn
f

(5) f (x) · 1 , . . . , k -- , f (x) ; · k+1 , . . . , n -- 1 , . . . , k Vn ; · x0 Vn -- f (x) = 1; · (y1 , . . . , yn-k) n - k (5) f (x) .

() =

1 W0 () + W f () + W () - W 2

f +

() .

(6)

f (x) (x) 0 , : 1) W f (0) = 2n ; 2) W f (0) = 0 Vn , = 0, (6) . 4 1) W f ++1 (0) = 2n - (W f (0) + W (0)) ; 2) W f ++1 () = - (W f () + W ()) Vn , = 0.

182

. . , . . , . .

. . .

183

, f (x) (x) 0, W f (0) + W (0) 0, W f (0) + W (0) = 0 , f (x) + (x) 1. f (x) + 1 . 4 3. (x) = 1, 0, x L + x0 ; x L + x0 , /

2. f (x) (x) 0 f (x) , (x) -- -, f (x) + (x) + 1 0. f (x) + (x) + 1 -- - n/2. . 4 , , W W
f + +1

f + +1

f (x) , (-1) , x0 W f () = 2n .
L

4. . . , x + , = 0 f (x) (3) : |W f () | = 2 - W f (0) .
n

, 1 . 6. f (x) , (x) -- - n/2 f (x) + (x) 1, f (x) (x) . 3. f (x) -- 2r , (x) -- 2s . r 2, s r + 1, r = 1, s 3, f (x) (x) . . . 4 |2n - (W f (0) + W (0)) | = |W
1 2n
V f + +1

() 0, ±

(0) = 2n - 2n/

2+1

, = 0.

2n/2+1

(0) |

Vn

max |W () |,
s +r

f , . . W f (0) = 0, , |W f () | = 2n , . . f -- . 2r [8] , [4] : |W f () | : 0, 2n-r .

n

|W () | = 2n-s ·

1 · 2n-r · 22r = 2n- 2n

.

(7)

, W f (0) + W f (0) 4 . : 2n-
s

, , r = 0, . . , (3) . , . 5. . . f , . . W f () W () = 0 Vn , W
f +

(7) . (8) 2r >
2s + 2r =1+ 2s - 2r 2 2
s -r

|2n - (W f (0) + W (0)) | 2n - 2n-s - 2n-r . 2n - (2n-s + 2n-r) > 2n-s +r , (8)

2n-r - 2n-s < 2n-r < 2n-s + 2n-r .

(0) =

1 2n

W f () W () = 0.
V
n

2n - 2n-

s +r

> 2n-s + 2n-r ,

f , W f (0) + W (0) = 2n , 5.

s - r , , (7) .

-1

.

184

. . , . . , . .

. , , 1) r = 1, s = 2; 2) r = s .

[1] . . .: , 1984. [2] . ., . ., . . . .: , 2004. [3] .-. . .: , 1970. [4] Carlet C., Prauff I. E. On Plateaued Functions and their Constructions. Proc. FSE'2003. [5] Courtois N. T . Fast Algebraic Attacks on Stream Cipher with Linear Feedback. Proc. CRYPTO'2003, LNCS, v. 2729, pp. 176194, 2003. [6] Courtois N. T ., Meier W . Algebraic Attacks on Stream Cipher with Linear Feedback. Proc. EUROCRYPT'2003, LNCS, v. 2656, pp. 345369, 2003. [7] Meier W ., Pasalic E., Carlet C. Algebraic Attacks and Decomposition of Boolean Functions. Proc. EUROCRYPT'2004, LNCS, v. 3027, pp. 474 491, 2004. [8] Zheng Y ., Zhang X.-M. On Plateaued Functions. IEEE Trans. on Information Theory, v. 47, no. 3, pp. 12151223, 2001.

. .
(, , , ) . ax b ax b (mod p) , (mod q) , (mod pq) .

ax b

M = p1 1 . . . pk k , a (Z /MZ) . . . [1] . , , . 1. M {2, 4, p , 2 p } (p = 2) a (Z /MZ) , ax b (mod M) , b (Z /MZ) ordM b | ordM a. (Z /MZ) M. , Q (a, r) = (a (r) - 1) /r (mod r) -- , (r) -- ( (Z /rZ) ) . , , [2] (. 146, 5.12 5.15) . 2. 1. ( ) . (a, r) = = (b , r) = 1. Q (ab , r) Q (a, r) + Q (b , r) (mod r) .

, ax b (mod M) ,

186

. .

. . . = 0, q1 = 0, Q (a, p = 0 , a
p 1 -1

187
-1

2. R = r 2 / ( (r) , r) Q (x , r) . 3. a (Z / p Z) ( 1) . ord p a = (ord p a, p - 1) . . p = 2, . p -- . d = (ord p a, p - 1) , = ord p a. aord p a 1 (mod p ) , a , | ord , ord
p

) 0 (mod p

).

=1+ p

+

q3 ,

ord

p

a

p

a = p d (0

| (ord

a. , | p - 1,
p

1

(mod p) .

a, p - 1) = d .
0

p q3 . , ord p a = p 1 , = + , , p - -1 Q (a, p -1) . 1. p -- , a, b (Z / p Z) , > 1. ax b (mod p ) Q (a, p
-1

a = 1 + p q
p

- 1) . (p q0) ,

a b

) x Q (b , p
x

-1

)

(mod p

-1

),

(mod p) .

(1)

, p , a a , | d
p

=1+ p

+1

q

1

(p q1) . (p q2) .

=1+ p

+

q

2

d ,p

= 1, , =1+ p
+

(a a
p d

d p )

q

3

(p q3) .

1 (mod p ) , a
p

d | . 4. a p ( > 1) = p 1 , 1 = ( , p - 1) , 0 - 1. = 0, Q (a, p -1) 0 (mod p -1) , = 0, p - -1 Q (a, p -1) ( ) . . 3 a1 = 1 + p q1 , q1 = 0 p q1 . , a
p
-2

1

(mod p ) ,

. p Q (a, p -1) ( 2) , , , (1) . , , -, , -, a . , ord p a = p n1 1 ord p b = p n2 2 ((1 , p) = (2 , p) = 1; n1 , n2 - 1) . 1, , ord p b | ord p a, 2 |1 0 n2 n1 . 1 3, (1) , 2 | 1 , 1 . 4, , , 0 n2 n1 , p n1 . , (1) ord p a. 2. 5, a, b (Z /2 Z) . ax b (mod 2) Q (a, 2-2) x Q (b , 2-2) (mod 2-2) , ax b (mod 4) . . a (-1) a 5
a

(2)

(mod 2) ,

b (-1) b 5
2
-4

b

(mod 2) .

(p -1)

=1+ p
+-2

+-2

q2 ,

, 2, Q (a, 2-2) =
1 - ((-1) a 5a) 2-2

p q2 p q1 . , Q (a, p
-1

=

)=

1+ p

p

-1

q2 - 1

1 - (5a ) 2 2-2

-4

=

=p

-1

q2 .

= Q (5a , 2-2) = a Q (5, 2-2) ,

188 (2) : a Q (5, 2
-2

. .

. . .

189

, Q (5, 2-2) 52 - 1 / (2-2) (mod 2-2) -- (. [2] , . 148, 5.20) , a x b (mod 2-2) , . a, b (Z / p . . . p Z) , 2 p1 < · · · < pk . i = p i -- a pii , (pi , i) = 1. i j , i = p j i j i j , (p j , i j) = 1.

i

) x b Q (5, 2
-4

-2

)

(mod 2

-2

).

7. i = 1, ci = 1, ci -- : Q (a, p
i -1 ) i

a x

b

(mod 2) ,

, : (3) -- . 8. j {1, . . . , i - 1} : a. p j | i , (ba-c j )
i j p
max{i j - j ,0} j

x Q (b , p

i -1 ) i

(mod p

i -1 ) i

.

1 1

k k

ax b

(mod p1 1 . . . pk k ) , i

(3)

b. , : (3) -- . 9. i < k, i := i + 1, 6; : (3) -- . 3. (3) O (log3 M) O (log2 M) pi p j . . ax b (mod p1 1 . . . pk k ) x : a b (mod p1 1 ) , ........................ x a b (mod pk k ) . ax b (mod pi p j) .

1

(mod pii ) .

: a, b (Z / p . . . p Z) . : (3) . 1. p1 = 2, i = 1, 6. 2. 1 5, 3, c1 -- ax b (mod 21) . , : (3) -- ; 5. 3. c1 -- : Q (a, 21
-2 1 1 k k

, : (3) -- . 4. , : (3) -- . 5. i = 2. 6. : , : (3) -- . b i 1 (mod pi) . ac1 b (mod 4) .

) x Q (b , 21

-2

)

(mod 21

-2

).

2, 3, 4 p1 = 2 6 7 pi ( 1 2 1) . x j -- ax b (mod p j j ) ; j x j c j (mod p j ) (c j 2, 3 7 1 2) . . i = j 8 i > j , , pi > p j , (i , j) = pii i , p j j j = i , p j j (i , j) , , xi x
j j

xi x

j

(mod (i , j)) .

(mod (i , p j j )) , (mod (i , j)) .

xi x

190
min ( , )

. .

. . .

191

ij j , i , p j j = p j . , i j j , i , p j j = i j = p j , , xi x j (mod p j i j ) . x j c j (mod p j i j ) , ai j c j b i j (mod pii ) , 8a. i j > j , , xi x j (mod p j j ) ,

u, xi c j + u p j j (mod p j i j ) . , u Z a ai
j

i

j

c j +u p u

j j

p

j j

b

i

j

(mod pii ) , (mod pii ) .
j

b i j a-

i j c

j

I. ax b -- p q . II. : 1) ord p a | r ; 2) ordq a | s ; b 3) pq = 1. . , ax b (mod pq) , I . , I, , II. 1) , 2) (ord p a, ordq a) = 1, . 3) c1 c2 -- ax b (mod p) ax b (mod q) . ord p a ordq a . , 1, 2) , (ord p a, ordq a) = 2. a b (mod pq) c1 c2 (mod (ord p a, ordq a)) . 2 | ord p a 2 | ordq a, a -- p q . , c1 c2 (mod 2) . c1 c2 -- , b -- , , , , . b , b = b , pq = 1. p q
x

pi 3 (pi > p j 2) ord ai j p j = p j i j j , 1 , (b i j a-
i j c
j

-

)

p

i j - j j

8b. -- O (log3 M) (, -- i j -- O (log2 M) , -- O (log M) ; i O (log3 M) ) O (log2 M) pi p j . , p q -- , ( , . 1) . . 5. (ord p a, ordq a) = 1, ax b (mod , p q . . 4. p = 2r + 1, q = 2s + 1, (r , s) = 1, r , s -- . (4) , : ax b (mod pq) , (4) pq) -

( 8a) . , . . xi x j (mod (i , j)) ,

1

(mod pii )

[1] . . // , 2002, 8 , 3 , . 6 4 7 6 5 3 . [2] . . - -- .: , 2003.

-

YAQS --

193

YAQS -- . .
1.
, N Z, , , . . x y , u2 v
2

(. [2] ) k kN . k (2) (3) . 1981 . (. [9] ) (2) (QS) . f (x) = (x + s) 2 - N , s = N , x Z ( ) f (x) , (3) , . , , f (x) , . p (3) , p | , x p , = f (x p) 0 (mod p) . p B {x p + n p }, n Z , , f (x p + n p) 0 (mod p) . p B , = f (x) , , (3) . 1987 . (. [11] ) (MPQS) , (2) . . (. [9] , [1] ) , f (x) Z [x ] , f (x) = ax 2 + bx + c , = a f (x) (ax + b) 2 (mod N) , a (3) . , l , < al N . MPQS- ( ) . 1993 D f = b 2 - 4ac 0 (mod N) . = f (x)
2

(mod N) ,

= x + s .

(mod N) ,

gcd (u - v , N) > 1, gcd (u + v , N) > 1, . 1971 . (. [10] ) (1) , N . 1975 [5] . . , . [4] , , F 7. N n = 1, 2, . . . , (2) n n < 2 N n =
i 2 n n

u ±v

(mod N) .

(1)

(mod N) ,

p

i i

,n

,

i, n

Z,

i = 1, 2, . . . .

(3)

, (3) , B . (2) ( j , j) , j {1, 2, . . .}, u2 =
j

j

2

j

j

=v

2

(mod N) .

194

. .

YAQS --

195

HMPQS (. [7, 8] ) , f (x) = t 2 x 2 + 2sx +
s2 - N , t2

s 2 N (mod t 2) .

90- (NFS) . MPQS-, , , · , (2) , , . . fn+1 = F (fn) ; · f0 (x) ; · , , : < R N , R , ; · p fn+1 (x) 0 (mod p) fn (x) 0 (mod p) , n = 0, 1, . . . , ( ) , 1997 . , , , , .

, D f = kN , d = gcd (a, b , c) d < k. d 2 m = kN , m, d 2 | N . . 1. f (x) Z [x ] , f (x) = ax 2 + bx + c . , , , f ()
2

(mod N) .

{n }, n = 0, n = 0, 1, . . . , « », { fn (x) }, fn (x) Z [x ] , f0 (x) , fn (x) = an x 2 + bn x + cn , f
n+1

(x) = x 2 f

n

n +

1 , x

an , bn , cn Z, n = 0, 1, . . . .

(5)

{n }, n = -1, 0, 1, . . ., {n }, -1 0
2a0 0 + b 2 -1
0 2 -1

a0

(mod N) , (6)

(mod N) , n = 0, 1, . . .

n+1 = n+1 n + n-1 ,

2. «»
. 1. f (x) Z [x ] , f (x) = ax 2 + bx + c , a = 0, «», a N D f , gcd (a, N) = 1, gcd (b , N) = 1, gcd (c , N) = 1. D f = b 2 - 4ac 0 (mod N) . (4)

. 2. {n }, { fn (x) } {n } . n = 0, 1, . . . 1. , D
fn
+1

= D fn ,

2. fn (x) , 3. fn (n)
2 n

(mod N) .

, (2) .

196

. .

YAQS --

197

3.
. 1. f0 (x) Z, 0 , -1 , 0 p , B . 2. J , . 3. J . , (6) , , (2) (3) . 4. , 7. 5. n , (5) , fn (x) 6. fn (x) 0 (mod p) p B 2. 7. ( , ) , (1) N . .

x = f (x) (3) p B . P (f1) > P (f2) , (f1) < (f2) . , (f ) f (x) , , P (f ) . [3] , , MPQS (f ) [-3.186. . . - 0.5899] . , (f ) B . D f , (4) . f (x) = ax 2 + bc + c 0 (mod p) Df p = 1, (7)

4.
[3] . , , . [6] . . B , . . p , (3) , p = 2. (f ) =
p B

, a 0 (mod p) . , p | a, f (x) 0 (mod p) b 0 (mod p) , p | b , p | c . , p 2 | D f . , N , p 2 | k. (8)

(1 - q p)

log p , p -1 Df p Df p

( f ) R, = 1, = -1, 0.

, , (7) (8) . 50 256- , , D f = kN , k Z, 1 k 216 , (f ) [-6.005362. . . - 5.639775] k, [3] . (f ) k. , 2 , (fn+1) = (fn) , n = 0, 1, . . . , fn (x) (5) .

qp =

2, 0,

5.
MPQS- . , .

p = 2 q p = 2, a, c , q p = 0. P (f ) ,

198

. .

YAQS --

199

, . 3. { fn (x) }, n = 0, 1, . . . . p 1 n,2 fn (x) 0 (mod p) . 1,2 n+1 fn+1 (x) 0 (mod p), an+1 0 (mod p),
1,2 n+1

1 an (n,2 - n) an+1

(mod p) .

, , .

[7] Peralta R. A quadratic sieve on the n-dimensional cube. CRYPTO'92, Vol. 740 of Lecture Notes in Computer Science, Springer-Verlag, pp. 324 332, 1993. [8] Peralta R. Implementation of the hybercube multiple polynomial quadratic sieve. Preprint. [9] Pomerance C. The quadratic sieve factoring algorithm. EUROCRYPT'84, Vol. 209 of Lecture Notes in Computer Science, Springer-Verlag, pp. 169182, 1985. [10] Shanks D. Class number, a theory of factorization and genera. Proc. Symposium Pure Math., Vol. 20, 1971. [11] Silverman R. The multiple polynomial quadratic sieve. Mathematics Of Computation, Vol. 48, pp. 329339, 1987.

6.
n . fn (x) , : n , | fn (x) | , . . n = {x Z : y Z, y = x = | fn (y) | | fn (x) |}. , .

[1] . . - . .: , 2003. [2] . . . II, 3- . .: 2000. [3] Boender H. The number of relations in the quadratic sieve algorithm. Chapter 4. PhD Thesis, University of Leiden, 1997. [4] Kraitchik M. Theorie des Nombers. Tome II. Gautier-Villars, Paris, 1926. [5] Morrison M., Brillhart J. A method of factoring and factorization of F7 . Mathematics Of Computation, Vol. 29, 129, 1975. [6] Murphy B., Brent R. P. On quadratic polynomials for the number field sieve. Report of The Australian National University, August, 1997.

. . . 201 . (2) l1 , . . . , lM-1 . M -- (2) . , , (2) (3) : (1) (1) ai1 xi1 + . . . + ai1 +l1 +. . . +lM-1 xi1 +l1 +. . . +lM-1 b (1) , ...................................................... (k) (k) ai1 xi1 + . . . + ai1 +l1 +. . . +lM-1 xi1 +l1 +. . . +lM-1 b (k) .

. .
. [1, 2] , f (x) f (x1 , . . . , xn) = 1 , f (x2 , . . . , xn+1) = 2 , (1) ........................ f (xN , . . . , xn+N -1) = N .

(3)

1 , . . . , N f (x) , (1) -- . . . [2] . . , . i1 , i1 +l1 , . . . , i1 +l1 +. . . +lM-1 , f (xi1 , . . . , xin) , xi j (. [2] ) f (xi1 , . . . , xin) = i1 , f (xi1 +l1 , . . . , xin +l1) = i1 +l1 , (2) .................................... f (xi1 +l1 +. . . +lM-1 , . . . , xin +l1 +. . . +lM-1 ) = i1 +l1 +. . . +lM-1 , ,
(-2358.2003.9)

(2) [3] , [4] . , (3) , (2) i1 , i1 +l1 , . . . , i1 +l1 +. . . +lM-1 -- f (xi1 , . . . , xin) . , (3) -- , k- k - 1 [5] . k- [6] . , 3- k- , 3- . 3- . , . . , , . , , , . .

202
l = l 1 2 3 4 5 6 7 8 9

. .
10 > 10 (22)

2

24 36 40

36

20 28

24

4

4

, , , . , , , , .

. . , . .
1.
. [1] . . . 1.1. DES DES (Data Encryption Standard) 64- . 64- , 64- . ,

[1] . ., . ., . ., . . . . .: , 2001 ., . 266. [2] . . . , 1, 1. .: , 1994 ., . 3355. [3] . ., . . . , 1, 3. .: , 1994 ., . 389401. [4] . . . , 1, 3. .: , 1994 ., . 402457. [5] . . . 5, 1 « », , , , 1827 . .: , . 174176. [6] . ., . . k- . , « », . 2, 1, 2003 ., . 7 9 9 3 .

k -- 64- , (a, b) -- 64- . , , Dk2 Dk1 (a, b) . (k1 , k2) , (a, b) -- . Dk2 Dk1 (a, b) . , f -- . , DES f . 1.2. IDEA IDEA (International Data Encryption Algorithm) 64- 128- . 16- : --

(a , b ) = Dk (a, b) = (b , a f (b , k)) ,

204

. . , . .

. . .

205

, + -- 216 -- 216 + 1. DES , . B = C (B D + (A C) K1) K2 , A = A (B D + (A C) K1) K2 ,

A = B = C = K1 = 0, D : 2 + 1 -- ( ) , D D -- K2 . , D K2 -- D . , , K2 D D (2) , .
16

D = D (A C) K1 + ((B D + (A C) K1) K2) . D = D D K2 .

C = B (A C) K1 + ((B D + (A C) K1) K2) ,

(1)

, I , I [1, n] i I fi xI = (xi) , i I . . 3. f = (f1 , . . . , fn) -- , G f -- . C G f
i C

fi 0,

(4)

(2)

f . . 1. f = (f1 , . . . , fn) (fi L i 1, n) , .

2.
[2] 2n в 2n n. , . f1 = x1 + y1 + g1 (1 (x1 , y1) , . . . , n (xn , yn)) , f = x + y + g ( (x , y ) , . . . , (x , y )) , nn n 2 2 2 211 1 (3) ........................................... fn = xn + yn + gn (1 (x1 , y1) , . . . , n (xn , yn)) .

3.
, . fi = xi + yi , i 1, n. (f1 , . . . , fn) , fi = fi (x1 , . . . , xn) , 2. (f1 , . . . , fn) : (f1 , . . . , fn) (f1 + x1 , . . . , fn + xn) . , {xi + yi }, { fi (xi + yi) + xi } { fi (xi + yi) + yi } 3 . i 1, n.

1. (3) 1 , . . . , n , g = = (g1 , . . . , gn) . . . . . [3] . , . 2. f = (fi) , i [1, n]

[1] . . . . . , .: , 1963, . 333369. [2] . . . , .: 1999, . 4, . 34, . 307320. [3] . . . , .: 1998, . 3, . 34, . 2 6 9 2 8 0 . [4] Denes J., Keedwell A. D. Latin squares and their applications. Budapest, 1974.

(n, m, k) -. . .

207

f Fn,m .

(n, m, k) - . .
Vk = {x1 , . . . , xk }, xi {0, 1} -- k. Vn Vm Fn,m . f Fn,m m, n : f () = (f1 () , f2 () , . . . , fm ()) : Vn Vm , fi () : Vn {0, 1} j {1, . . . , m} f Fn,m (n, m, k) -, 1 i1 < . . . < ik n, a j {0, 1} j {1, . . . , k} f = (f1) a11,, ......,, iak , . . . , (fm) a11,, ......,, iak Fn-k,m i i k k a . n - k gia1, , ......, , ik k , 1 g Vn i1 , . . . , ik a1 , . . . , ak . , v Vm u Vn-k :
a gia1, , ......, , ik 1
k

J w = w (f , n, m, k) = wI (f ) , 0 |I | k, I 1, n, = J 1, m -- m k n L = L (n, m, k) = s =1 m i =0 i , E w -- s w . . m N, n , k (n) = o ( n) , Q = = Q (n, m, k) -- (w - Ew) /2n/2+m-2 , z (n) 2n/2+m-2 n=1 -- L (n, m, k) . z (n) :

|R (n, m, k) | = Pr{ f R (n, m, k) } = Pr{w = E w }, |Fn,m |

Pr w = Ew + z (n) 2

n +m - 2 2

=

1 exp - z T Q 2 2
n -1 2

-1 L

z +O
L

n4k+3 2n/2

т

=

(2) det Q
2

exp -

1х 2 exp

х

2

=

J 1,m I 1,m |I | k

| I | +m - 1 J zI

-

i I

х | I | +m - 2 J 2 zI \{i }

+O

n4k+3 2n/2

n - k nЎ m k (2 - 1) - L (n, m, k) m - log2 2 2

.
ln 2

(1)

(u) = v

= 2n-

k-m

.

, m N, n , k (n) = = o ( n) |R (n, m, k) | exp m2n -
n-k n (2m - 1) + 2 k

(. [5] [9] ) R (n, m, k) (n, m, k) - . [4] , f Fn,m (n, m, k) - , (n, s , k) - s = 1. J { j1 , . . . , j|J | } {1, . . . , m} = 1, m I {i1 , . . . , i|I | } J {1, . . . , n} = 1, n wI (f ) (f J ) 11,, ......,, 1|I | i i 1, . . . , 1 (f J ) i1 , . . . , i|I | f J = f j1 . . . f j|J | , i1 , . . . , i|I | . [1] f J J (n, 1, k) - , wI (f ) = 2n-|I |-1 I 1, n : 0 |I | k.

+ L (n, m, k) m - log2 2

ln 2 .

(2)

m = 1 [2] .

[1] . . - k . , . 3, . 2 (1991) . [2] . . . , . 12, . 1 (2000) .

208

. .

[3] . ., . . -- ( ) . , . 6 (1996) . [4] . ., . ., . . . .: , 2004. [5] . . - . , . 11 (2002) . [6] Cheon J. H. Nonlinear Vector Resilient Function. Crypto'2001, SpringerVerlag (2001) , pp. 458469. [7] Bierbrauer J., Gopalacrishnan K ., Stinson D. Bounds on Resilient Function and Orthogonal Arrays. Crypto'94, Springer-Verlag (1994) , pp. 247256. [8] Gopalacrishnan K ., Stinson D. Three Characterization of Non-binary Correlation-Immune and Resilient Function. 1997, www.eprint.iacr.org. [9] Gupta K . C., Sarcar P. Improved Construction of Nonlinear Resilient S-Boxes. Asiacrypt'2002, Springer-Verlag (2002) , pp. 466483.

VR . .
1996 RC4. ISAAC, IBAA, IA [1] , GI [2] . [3] RC4 -- VMPC. VMPC, VR, . VR = VR (m, r , k, l , (1 , . . . , r) , (1 , . . . , r)) m = 2n , n 2, r , k, l , l k < r , r (1 , . . . , r) , (1 , . . . , r) Z (m) . VR AVR = (Zm в Zm в Sm , Zm , Zm , FVR , fVR) , F
VR

t

: Zm в Zm в Sm Zm в Zm в Sm ,

f

VR

1

: Zm в Zm в Sm Zm .

g : i i + 1 (mod m) -- Sm µ ((1 , . . . , l ) , (1 , . . . , l )) : s s 1 g 1 . . . s l g l Sm , µs ((1 , . . . , l ) , (1 , . . . , l )) = s µ ((1 , . . . , l ) , (1 , . . . , l )) . t - (t = 1, 2, . . . ) VR. F
VR

vt = (it , jt , st) Zm в Zm в Sm .

1) it = it -1 + 1 (mod m) ; 2) jt = it µst ((1 , . . . , k) , (1 , . . . , k)) , l = jt -1 ; 3) st +1 [it ] = st [ jt ] , st +1 [ jt ] = st [it ] , st +1 [k] = st [k] k {it , jt }. / f zt = jt µst ((k+1 , . . . , r) , (
k+1 VR

, ...,

r -1

, 0)) .

VR : 1 = 1, 2 = 1, 3 = 1, 4 = 1, 5 = 2, 1 = jt -1 , 2 = 0, 3 = 1, k = 2, r = 4, . . 2 jt = it st g jt -1 st , zt = jt st gst .

210 ,

. .

s µ ((1 , . . . , l ) , (1 , . . . , l )) = g , s .
l =1 (1 , ..., l ) , (1 , ..., l )

1. g -- Sm , s Sm , m = 2n n - 1 -- . , g , s Sm , k n-1 n-k ! - 1) 2 / (2n !) . k=1 (2 2. i -- Zm ; 0, (m) - 1 , 1 , 2 1, (m) - 1 ; s Sm 2 (i , , 1 , 2) 2 (i , , 1 , 2) = = is 1 g s 2 . z = i g Zm Pr{2 = i g } - Pr{2 = z } , 1 = 2 Pr{2 = i g } - Pr{2 = z }
1 . m (m - 1)

. . , . . , . .
1.
, , ., , [2] , [12] . , , , [6] . , , , [12] , [10] . , «» (, ) , ( ) . , , [3] . «» : H0 , , x1 x2 . . . xt {0, 1} , H1 , ( 0301-00495) , INTAS (Grant 00-738) Royal Society, UK (grant ref: 15995) .

[4, 5, 6] , RC4 . 2 , VMPC s0 Sm , j0 = 0, i0 -- Zm , z1 . , RC4 .

m - 1 + (1) - 3 . m (m - 1)

[1] Jenkins R. J. ISAAC. Fast Software Encryption'96, LNCS, Springer, 2004. [2] . ., . . GI. '03 (, 2003) . [3] Zoltak B. WMPC one-way function and stream cipher. Fast Software Encryption'2004, LNCS, Springer, 2004. [4] Pudovkina M. Statistical weaknesses in the alleged RC4 keystream generator. 4nd International Workshop on Computer Science and Information Technologies (CSIT'2002) , Greece, Patras, 2002. [5] Fluhrer S., McGrew D. Statistical Analysis of the alleged RC4 keystream generator. Fast Software Encryption'2000, LNCS, Springer, 2000. [6] Mantin I., Shamir A. A practical attack on broadcast RC4. Fast Software Encryption'2001, LNCS, Springer, 2001.

212

. . , . . , . .

. . .

213

( H0) . 16 , (NIST) [6] . , [6] . , , [9] .

2.
, . « », -- « ». . A = = {a1 , . . . , aS }, -- , . : H0 -- (p (a1) = . . . = p (aS ) = 1/S) H1 = ¬H0 . H0 H1 x1 x2 . . . xn , n 1. « » A 1 S . xt x1 x2 , . . . , xn 1, xt = a; t +1 (a) = t (a) + 1, t (a) < t (xt ) ; (1) t t t (a) , (a) > (xt ) ,

. H0 , xi 1/S . ( ) 1, . . . , S r , r 2, A1 = {1, 2, . . . , k1 }, A2 = {k1 + 1, . . . , k2 }, . . . , Ar = {kr -1 + 1, . . . , kr }. x1 x2 . . . xn t (xt ) , t = 1, . . . , n, Ak , k = 1, . . . , r . nk (, nk = |{t : t (xt ) Ak , t = 1, . . . , n}|, k = 1, . . . , r) . , H0 , , «» t (xt ) Ak |A j |/S . , «» - , H0 = Pr{ t (xt ) Ak } = |A j |/S «» n1 , . . . , nr H1 = ¬H0 . , r x2 =
i =1

(ni - n (|Ai |/S)) 2 , n (|Ai |/S)

t -- x1 x2 , . . . , xt , t = 1, . . . , n, 1 . (, 1 = {a1 , . . . , aS }.) (1) . , 1 (a) -- «». x1 x1 x2 . . . xn a. i1 - , . . ( 1 (a) = i1) , a . ( (1) .) x2 . . -- H1 , A, 1/S , -

- x 2 2 (k - 1) H0 . {A1 , A2 , . . . , Ar }, , . , , . . . , . A = {a1 , . . . , a6 }, r = 2, A1 = {a1 , a2 , a3 }, A2 = {a4 , a5 , a6 }, x1 . . . x8 = = a3 a6 a3 a3 a6 a1 a6 a1 . 1 = 1, 2, 3, 4, 5, 6, 2 = 3, 1, 2, 4, 5, 6, 3 = 6, 3, 1, 2, 4, 5, . . . , n1 = 7, n2 = 1. , a3 a6 « » . . «» ( «») « » (1) S , , S . , , , -, (1) O (log S) . . « », [7] [1] (. [8] ) .

214

. . , . . , . .

. . .

215

«Move-toFront» (MTF) ) . . t (a) , , (1) . t+1(a) , a x1 . . . xt -1 xt . t t (a) - t (a) . « ».

3.
[6] . [6] , , . , / (block = 30) (block = 30) Frequency Block Frequency Cumulative Sums Runs Rank Longest Run of Ones Discrete Fourier Transform Non-overlapping Templates Overlapping Template Universal Statistical Approximate Entropy Random Excursions Random Excursions Variant Serial Lempel-Ziv Complexity SR G 19/20 18/20 1/0 0/0 1/2 1/0 20/20 1/0 1/1/2 1/0 1/0 3/2/2 2/2 0/1 0/ 1

: (SRG) DIEHARD (. 13, . http://stat.fsu.edu/diehard/) , (LCG) Xn+1 = (134775813Xn + 1) mod 232 , MT19937 [4] , SEAL [5] . 20 , (H0) 0.01. : 219 222 . 1. 219 , -- 222 . , , 19 20 20 20 . , - . , «» , , [6] .

[1] Bently J. L., Sleator D. D., Tarjan R. E., Wei V . K . A Locally Adaptive Data Compression Scheme. Comm. ACM, v. 29, 1986, pp. 320330. [2] Menzes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996. [3] Nechvatal J. and others. Report on the Development of the Advanced Encryption Standart (AES) . 2000, in: http://csrc.nist.gov/encryption/ aes/round2/r2report.pdf. [4] Matsumoto M., Nishimura T . Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator. ACM Transaction on Modeling and Computer Simulation, v. 8, pp. 330, 1998. [5] Rogaway P., Coppersmith D. A Software-Optimized Encryption Algorithm. In: Fast Software Encryption, Ross Anderson (Ed.) , Springer-Verlag, Lecture Notes in Computer Science, v. 809, pp. 5663, March, 1994. (see also: Journal of Cryptology, V. 11, n. 4, Autumn 1998, pp. 273287.) [6] Rukhin A. and others. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST Special Publication 800-22 (with revision dated May 15, 2001) , http://csrc.nist.gov/rng/ SP800- 22b.pdf. [7] . . . , . 16, 4, 1980, . 1621. [8] Ryabko B. Ya. A locally adaptive data compression scheme (Letter) . Comm. ACM, v. 30, N 9, 1987, p. 792. [9] Ryabko B., Monarev V ., Shokin Yu. Using Universal Coding Approach to Randomness Testing. IEEE International Symposium on Information The-

LCG 0/20 0/20 0/0 0/1 1/0 0/0 0/0 0/0 3/1/2 0/0 0/0 4/2/2 2/2 0/0 0/-

MT19937 0/0 0/0 0/0 0/0 0/0 0/0 0/0 1/1 0/1/1 0/0 1/1 2/2/2 2/2 1/1 0/-

SEAL 0/0 0/0 0/0 0/0 0/0 0/1 0/0 0/0 0/1/1 0/0 0/0 3/3/2 3/2 0/1 0/-

216

. . , . . , . .

ory, Proceedings, 2004, Chicago. [10] Ryabko B. Ya., Stognienko V . S., Shokin Yu. I. A new test for randomness and its application to some cryptographic problems. Journal of Statistical Planning and Inference, 2004, v. 123, n. 2, pp. 365376. [11] . ., . . . .: , 2004. [12] Schneier B. Applied Cryptography. N. Y.: Wiley, 1996.

(superimposed) . .
, , (2, q - 2) -, -- q - (2, r) - , r 1 q 2 (2, r) - ( 1) . . .

1.
A = {A1 , . . . , AT } [N ] = {1, . . . , N } (w , r) - (cover-free (w , r) -family) , :
w r

Ais
s =1 j =1

Ak

j

{i1 , . . . , iw }, {k1 , . . . , kr } [N ] ,

(1)

K (w , r) - A, (w , r) -. K A j . , K N T . N K, T . N , (w , r) T . -- , . . (w , r) - .
( 02-01-00687) NST ( CCR-0310632) 2004 .

, {i1 , . . . , iw } {k1 , . . . , kr } = .

218

. .

(superimposed) . . .

219

(., , [7, 3] , ) . . 4 .

A = {A1 , . . . , Aq }, A j = {a j ,1 , . . . , a j ,m } [N ] , -- (2, q - 2) - , A (k) (k) (k) (2, q - 2) - A (k) = {A1 , . . . , Aq } , A
(k) j

2.
2.1. , (2, q - 2) - R
(k) q

= {a

j ,1

+ (k - 1) N , . . . , a

j ,m

{1 + (k - 1) N , . . . , N + (k - 1) N }.
(k) (k )

+ (k - 1) N }

1 ( (2, q - 2) - Qq).
( |Rqk) | = q 2

= {{i + kq }, {i + kq , j + kq } | i , j = 1, . . . , q , i = j }, +
q 1

=

q +1 2

,

, k = k , As At = . 2 ( ). q - K (w , r) - (separating (w , r) -code) , y1 , . . . , yw K x1 , . . . , xr K, {y1 , . . . , yw } {x1 , . . . , xr } = , () i [n] = {1, . . . , n} , {y1, i , . . . , y
w, i

-- [kq + 1, (k + 1) q ] = {kq + 1, . . . , kq + q }. Cs = { (s + kq , j + kq) | j = 1, . . . , q }, |Cs | = q , -- (k) (k) Rq , {i , j } Rq , s + kq . (k) (k) k c Qq = {Cs | s = 1, . . . , q } (k) q +1 2 - Rq (2, q - 2) -, (0) (kq , (k + 1) q ] . Qq Qq . , C j Qq {1, . . . , q }. , Qq , N = q +1 2 ( ) . (k) (k) (k) (k) (k) Qq ={C1 , . . . , Cq }, As Rq , q (k) () . M Cs q . (( : T = q , N = |Rqk) | = q +1 , . [3, 4] .) 2 (k) 1. (2, q -2) - Qq (2, q -2) . (2, q -2) - N = q +1 2 q . . ,
( Csk) (k) (k)

K -- |A j | = m, -- q .

3 ( ). q - (2, r) - A = {A1 , . . . , Aq }, (2, q - 2) - , An (K) x = (x1 , . . . , xn) K, |Ax | = nq , (4)

} {x1, i , . . . , xr , i } = .

(3)

Nn = { (k - 1) + 1, . . . , N + (k - 1) N } = {1, . . . , nN }, , K A. ( T ) An (K) |K|, Nn ( ) |Nn | = nN . A = Qq , |Nn | = n q +1 . 2 1. K -- q - (2, r) - A = = {A1 , . . . , Aq }, |A j | = m, -- (2, q - 2) - , q . q An (K) (2, r) -, . . x, y K, x = y. , n=1 k {x1 , . . . , xr } K \ {x, y}. K (2, r) -. s , , (2) Ax Ay Ax1 . . . Axr .
( ( ( ( Axss) Ayss) Axs1),s . . . Axsr),s . ( ( ( ( Ax Ay = Ax1) Ay1) . . . Axn) Ayn) . n n 1 1

( ( ( Ax = Ax1) Ax2) . . . Axn) , n 1 2

(5)

( Csk)

= {s + kq , s + kq } {s + kq , s + kq }

( (Csk) 1

. . .

() Csk- q

2

) = , (2)

(xs {xs ,1 , . . . , xs ,r }) & (ys {xs ,1 , . . . , xs ,r }) . / / (6)

s {s1 , . . . , sq -2 } / s {s1 , . . . , sq -2 }. (k) (k ) , k = k , Cs Ct = .

220

. .

(superimposed) . . . 2 ( [9, 3]). q > 2r . RS
q ,q 2r

221

. . , 1969 . , . , 1 , (. [3, Proposition 2.1] , [4, Lemma 5] , [7] ) : 2. K q - (2, r) - n в |K| (n -- K) B -- (2, r) -, (, , B -- (2, r) -) N1 в q (q -- B) . K B (2, r) - nN1 в |K|. 6. , 2 , , B (2, r) -, K -- (2, r) -. 1 , B (2, q - 2) - A, r > q - 2 . , (2, r) - q - (2, r) -, q 2 r . , (2, r) - r q - (2, r) -, q q - (2, q - 2) - Qq . (2, r) -, , .

,

RS

n ,n 2r

=q

n +1 2r

,

(2, r) -. 1 ( 1 2). 2r < q . Q
q ,q

RS

q ,q 2r

(2, r) - q . (w , r) - K N log |K| . (8) R (K) = 2
N

3.
3.1. 3.1.1. - Fq = {1 , . . . , q } f = f (x) Fq [x ] a f = (f (1) , . . . . . . , f (q)) -- f . - (RSk,q -) , , a f , f k, . . RSk,q = {a f | deg f k}. (7)

(2, r) -, r = const 1, N , , 2 2, 1. K1 , . . . , Km , . . . , (2, r) - 1, , . (2, r) -, r = const 1, N , , 1 . . 2 . K1 -- (2, r) - N1 Km . qm -- , |Km | = Tm qm . Km+1 RS
q ,q 2r

Km ,

Nm+1 = qm Nm q [qm / (2r) ] +1 . , R (Km) . R (K) 1, , , R (Km+1)
log2 qm 1 R (Km) , 2r Nm 2r 1 2r
s

m .

(9)

s , R (Km+1) limm

q - RSk,q - (n, k, d) , n = q , d = n - k + 1 q .

,

(10)

R (Km) = 0.

222

. .

(superimposed) . . .

223

R (w , r) = lim
N

log2 T (N , w , r) , N

(11)

T (N , w , r) -- T N , w , r (., , [3, Section 3.5] ) . , (2, r) - ( ) . 3.2. (w , 1) - , 1, (w , 1) -. x, y Fn . x · y x, y q 3. Fq K (w , 1) - , x1 , . . . , xw K x1 . . . xw = 0. (13) . x1 , . . . , xw , x K, x {x1 , . . . , xw }. / , xi x xi {x1,i , . . . , xw ,i }, i = 1, . . . , n. x1 = x1 - x, . . . , xw = xw - x, K, (13) . , xi x, xi {x1,i , . . . , xw ,i }, (13) . / 4. K (2, 1) -, x, y K \ {0} wt (x + y) < wt (x) + wt (y) , (14) wt (x) -- x. . x · y = 0, x, y K \ {0}, , , wt (x + y) = wt (x) + wt (y) . 2 ( 9] . Fq K [) (2, 1) -, x K \ {0}
2n n < wt (x) < . 3 3

x · y = (x1 y1 , . . . , xn yn) .

(12)

, q - (w , r) - q = const, w > 1, n , . 2, , «» q = 2. , - , . . , (15) , R = 1 - H2 (1/3) = 0.0817042, (2, 1) -. , BCH- . . , (15) . , (2, 1) - . , , , , q - (w , r) - n (., , [1, Chapter 6] ) . «» - . q , w , r = const, n R (q , w , r) . , , , , . 1 13 [1] ( (w , r) -) 3. (w , r) - R (w , r) < Y (w , r) , Y (w , r) =
1 max log (1 - p w (1 - p) r - p t (1 - p) w) w + r - 1 0< p <1 2
-1

1 3

(16)

(15)

. x · y = 0, wt (x + y) = wt (x) + wt (y) > > 2n/3, .

. (17)

224

. .

(superimposed) . . .

225

, [3] R (w , r) R (w , r) . , R (2, 1) = 0.149. (16) 0.2075/3 = 0.0691667. R (2, 1) , (2, 1) -.

S . , r . 6. , N , a (N ) = max |Nz |
z Z

(19)

4.
(. [2, 5, 7] ) . 1. ( , ) Z , |Z | = T . Z Fn . q Z K Fn . q 2. L = {k | N } , . , N . , L N . , N N = |N |. 3. Lz = {k1, z , . . . , ksz , z } L -- z Z , () . , Lz Nz = { (1, z) , . . . , (sz , z) } N . Nz Ax (. (4)) . 4. Lz,z z, z Z Lz Lz . Lz, z Nz,z = Nz Nz . , Nz, z (. (5))
n

T . , N -- , . , ( ) (2, q - 2) - Qq a (Qq) = q , Qq ,n (K) a (Qq ,n (K)) = qn.

[1] Cohen G. D., Schaathum H. G. Asymptotic Overview on Separating Codes. Report No 248, May 2003, Bergen, Norway. [2] Mitchell Ch. J., Pipper F . C. Key storage in secure network. Discrete Applied Mathematics, 21, 215228, 1988. [3] D'yachkov A., Vilenkin P., Macula A., Torney D. Families of finite sets in which no intersectin of l sets is covered by the union of s other. J. of Combinatorial Theory, S. A 99, 195218, 2002. [4] Hyun Kwang Kim, Lebedev V . On optimal superimposed codes. [5] Quinn K . A. S. Some constructions for key distribution pattens. Designs, Codes and Cryptography, 4, 177191, 1994. [6] Quinn K . A. S. Bounds for key distribution pattens. J. Cryptology, 12, 227 239, 1999. [7] Stinson D. R. On some methods for unconditionally secure key distribution and broadcast encryption. Designs, Codes and Cryptography, 12, 215243, 1997. [8] MacWilliams F . W ., Sloane N. W . A. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1977. ( : . . , . . . . , . .: , 1979.) [9] Sagalovich Yu. L. On separating systems. Problemy Peredachi Informatsii, 30, 1435, 1994 (in Russian) . [10] . . , (w , r) -. , . 39, 4, 310, 2003. [11] . ., . . , (w , r) -. , . 40, 3, 1 3 2 0 , 2 0 0 4 .

Nz Nz = Ax Ay =

j =1

(Ax j Ay j ) .

(18)

5. , {Nz | z Z } (2, r) -, , (2, r) -. , , , S N , |S | r , z, z S , . . / z, z , Lz, z , -

. . .

227

x = (x1 , . . . , xn) u = (u1 , . . . , un) -- n F 2 . x u -- ,

. .
, . . , 16 4, 5 6. h 4h , , 2h 2h+1 - 2.

n

x, u =
i =1

xi ui ,

F 2 . x + u x u F 2 . f F n , 2 W f (u) =
x F
n 2

(-1)

f (x) + u,x

.

u F n W f (u) 2 . , 2n -- . (-1) f (x) = 2-n uF n W f (u) (-1) u,x uF n W f2 (u) = 22n . f 2 : nl (f ) = 2n-1 -
1 max |W f (u) |. 2 uF n 2
2

F n , n 2 F 2 -- 0 1, 0 1 2. n wt (x) x F 2 x . wt (f ) n f F 2 -- x F n , f (x) = 1. 2 f , wt (f ) = wt (f 1) = 2n-1 (. . 0 1 ) . x x , i - . x i , x i - , i = 1, . . . , n. xi f , x x , i - , f (x ) = f (x ) . d (x , x ) x x , x x . f F n 2 d (f , l) , l n F 2 f nl (f ) . f f , f 0 1 .

S f u, W f (u) = 0, f . -, ±2n/2 . - n, -- . - 2n-1 - 2 (n/2) -1 n n. , : 0 ±2c c . - (, , - ) , , (, m- 2n-1 - 2m+1) . (x) = = 2-c W f (x) . x F n (x) 2 : 0, -1 1. S f u,

228

. .

. . .
1

229

W f (u) = 0, . , (x) = -1, T - , , (x) = 1, T + . , 4n-c . - c = n/2 |S f | = 2n , . ( - .) , ., , [1] , [4] , [8] . u F n 2 f u f (u) = x F n (-1) f (x) + f (x +u) . 2 Du f = f (x) + f (x + u) f u. u F n , Du const, 2 f . , f F n . 2 ( ) . E -- F n . E 2 , E F n . E 2 F n , E . 2 k k, . , . , k {k, k - 1}. (., , [5] ) , f n - k. u F n , Du 1, k = k + 1. 2 , k = k. [2] [3] . f f , , . f f , , . , . , , f wt (f ) ,

wt (f ) = 2n-1 - W f (0) , 2 0 , , f . , . , f f , f f . F n 2 4h 4h , F k . 2 , k > 2h, f F n 2 4h f F k 2 4h , n - k . , k = 2h W f (0) = 0 ( f -) . k = 2h W f (0) = 0, , , f k + 1 . , , , (, ) . , , k . . 4h , k, 4h , k = k, k = k + 1. , . , 4h 2h, 4h . 1 , , 0. 4 -

230

. .

. . .

231

2. [7] , , -, . 16 ( ) [6] , [5] 16 ( , n - 4 ) k k 9. , 16 4, 5 6. , h 4h , , 2h 2h+1 - 2. 1. f , |S f | = 16. k S f k 6. 2. s , 2h s 2h+1 - 2 4h s . . 16 4, 5 6. 3. f , |S f | = 4h . k S f k 22h-1 - 2h-1 + h. - . h = 2 3 . . h 4h 2h+1 - 2.

[4] . . . VIII « » (26 2004 .) . .: - - , 2004. . 431435. [5] Carlet C., Charpin P. Cubic Boolean functions with highest resiliency. Proceedings of 2004 IEEE International Symposium on Information Theory (ISIT 2004) . Chicago, USA, June 2004. P. 497. Full version is submitted to IEEE Transactions on Information Theory. [6] Kasami T ., Tokura N., Azumi S. On the weight enumeration of weights less than 2.5d of ReedMuller codes. Information and Control. Vol. 30 (4) . April 1976. P. 380395. [7] Pei D., Qin W . The correlation of a Boolean function with its variables. Progress in Cryptology -- Indocrypt 2000. Lecture Notes in Computer Science. V. 1977. Springer-Verlag, 2000. P. 18. [8] Zheng Y ., Zhang X.-M. Plateaued functions. Proceedings of ICICS 1999. Lecture Notes in Computer Science. V. 1726. Springer-Verlag, 1999. P. 284300.

[1] . . . VIII « » (26 2004 .) . .: - - , 2004. . 424426. [2] . ., . ., . . . .: - , 2004. [3] . . - . . . 11. .: , 2002. . 91148.

233

. .
, S . H S , H .

G H = { g } (H - G ) , L (g , S) . 3. G , H pokS (G H) S G . G , S H .

2.
4. G H < G H - G . 5. H V (V , U) V U (H) = mini , j H (i , j) , (i , j) -- i j (V , U) . 1. S H -, S -- S , S [2, 3] , | S : ( S H) | -- S H S . 1 . 2. g H -, pok g H = | g : ( g H) |. pokS H S H S . , pokS H = 1, S H = , pokS H = 2, S H = S . pokS H = ( S H) | S : ( S H) |,

1. ,
-- , S -- , S = {s1 , s2 , . . . , s p }, S p = |S | > 0; G < S . L (g , S) g G S [1] . 1. S H = , H S ( pokS H) H S , pokS H = min g G L (g , S) . S H = , pokS H = . 2. G H -, G H = , H - () , G H -- ( G H ) . G H -, G H = . 3. G H -, H - G ( H - G) S G H S , pokS (G H) . G = S , pokS (G H) = pokS H . , , , S : 1. H - G . 2. G H ( ) H - G S .

3.
«» , . . g , g . 6. G H = , H - G , g G H , g G H . H - G ( G H) H --

234

. .

235

G . g n. 1. g H -, g t H , t {1, . . . , n}, , g d H , d = (t , n) . , g H g d H d D (n) n. 7. n1 , . . . , nm -- , m 1. ni , i {1, . . . , m}, M = = {n1 , . . . , nm } ( M-) , ni M, ni . M- , prm M. 8. g H -, (H , g) - , {d D (n) : g d H }. (H , g) - (H , g) . , (H , g) - d n , g d H g H d . / (H , g) D (n) : (H , g) = prm{d D (n) : g d H }. 3. g , H -, g t H , t (H , g) - , g H = gt .
t (H , g)

9. f g G g - f , g G . g g t , t {1, . . . , n}, g - f g (t) : {1, . . . , n} Y , f g (t) = f (g t ) . 10. g - f g (t) () D (n) , , t {1, . . . , n} , ( , n) (t , n) , f ( ) f (t) (f ( ) f (t)) . 11. f () G , g G g - f g (t) () D (ord g) . () G , , f (g) = (ord g) -1 ( f (g) = ord g) . f : G Y , f (g) . g G , y Y f (g) y (f (g) y) , G (f y) (G (f y)) . 4. f () G , y Y G G (f y) - (G (f y) -) . G H -, () G f , G H = G (f y) (G H = G (f y)) y Y .

[1] . . , . . « », . 1, .: , 1997, . 4366. [2] ., . . .: , 1971, 248 . [3] ., ., . . .: , 1974, 456 .

H - g , | (H , g) | = 1. . g H - (H , g) = {t1 , . . . , tr }. pok g H = min{t1 , . . . , tr }.

4.
f , G Y , |Y | > 1.

237 1. dom L (g) = {l1 , . . . , ld }, d > 1, :

. .
[1] G . , , . (X) -- X , g (X) . , ord g = n g ki li , i = 1, . . . , m. L (g) g , L (g) = {l1 , . . . , lm }. 1. li L (g) , i {1, . . . , m}, li L (g) . , L (g) , L (g) dom L (g) . : dom L (g) = {l1 , . . . , ld }, 1 d m. 2. g d -, |dom L (g) | = d > 1, , |dom L (g) | = 1. X U . U - G , G < < (X) . G U -, L (e) = (1) , , e G U . f (g) = |dom L (g) |, f -- , (X) . 1. f (X) , G (X) U -. M M . g (U , g) - , g U , 1.

k k n = p1 1 . . . ps s ,

k k li = p1 i1 . . . ps is ,

p1 , . . . , ps -- , k1 , . . . , ks -- , ki 1 , . . . , kis -- , i = 1, . . . , d , k j = = max{k1 j , . . . , kd j } j = 1, . . . , s . (U , g) = prm ({u1 , . . . , ud }) , i = 1, . . . , d ui = p j = 1, . . . , h wi j = 1, ki j < k j ; 0, ki j = k j . G g t , S ,
wi 1 k1 1

... p

wih kh h

1. U -, . 2. g U = t prm({u1 , ..., ud }) pok g U = min{u1 , . . . , ud }. G , S = {s1 , . . . , s p }, : pokS U

: P r -- r P q , GL (r , q) -- P r , -- P r , G -- P r , G -- G , UG -- G . 2. G GL (r , q) -, G GL (r , q) G UG .

min{ (U , s1) . . . (U , s p) }.

[1] . . . -04.

« ». . . (s + 1) - P = (p
i1 , . . . , is , is s +1

239
+1

),

« » . . , . .
1.
xt A = {0, 1, . . . , N - 1}, t N -- [1] . -- , x1 , . . . , xn A n H0 ({xt } -- () , . . x1 , x2 , . . . A) H1 . [2] : 1) , ; 2) «» ; 3) . H1 , . H1 , {xt }. «» « » («long-memory time series») [3, 4, 5, 6] .

p

i1 , . . . , is , is

+1

= P{xt = i

s +1

|x

t -1

= is , . . . , x

t -s

= i1 },

i1 , . . . , i

A.

s , «» . [3] MTD-, . (s , r) r , [5] : p
i1 , . . . , is ,is
+1

=q

0 im0 , . . . , im0 ,is
1 r

+1

,

i1 , . . . , i

s +1

A,

(1)

: r {1, . . . , s } -- ; -- s - 1 = m0 < m0 < . . . < m0 s , () (r 1 2 ) ; Q 0 = (q 01 , ..., jr , jr+1) , j1 , . . . , jr +1 A -- (r + 1) - j . : Xn = (x1 , . . . , xn) An -- n > s ; Js As -- ; St (Xn ; Mr) = (x
t +m 1 - 1

M0 = m0 , . . . , m0 M r 1 r

, ..., x

t +mr -1)

-- r - Mr M, t {1, . . . , n - s + 1}, I (A) {0, 1} -- A;
n-s

: An в M Ar

r

+1

(Jr

+1

; M r) =
t =1

I{St (Xn ; Mr) = Jr

+1

}

-- (r + 1) - Jr +1 Mr +1 = (Mr , s + 1) . 1. Mr = M0 min Jr Ar r +1 (Jr +1 · ; Mr) > 0, r () Q 0 : Q = Q (Mr) = (qJr+1 (Mr)) , q
Jr
+1

(Mr) = r

+1

(Jr

+1

; Mr) /r

+1

(Jr

+1

2. s - r (s , r)
(, F , P) -- ; xt A = {0, 1, . . . . . . , N - 1}, t N -- s - (s , N N)

· A. 2. M0 r : Mr = arg maxMr M Ir +1 (Mr +1) , Ir +1 (Mr +1) n .

· ; Mr ) ,

Jr

+1

Ar

+1

,

240

. . , . .

« ». . . Xn ; S (P) =
i1 , . . . , is
+1

241

3. (s , r) M0 M r , Mr , Q -- : n (s , r) O (N r +1 s r -1) . . 0 Mr - Mr ,
P

p
A

2 i1 , . . . , is , is

+1

Q - Q0.

P

3.
[6] : (2) xt = µt xt -t + (1 - µt) t , t > s ,

-- P ; F (P) -- P , {i1 = . . . = is = is +1 } {i1 = is +1 , . . . , is = is +1 } 5. = 1, n (2) , (3) , , :
n

i =
t =1

xt ,i

/n,

i A;

= arg min F P - P ( , , ) ;
[0,1)

{t : t > s }, {t : t > s }, {µt : t > s }, {x1 , . . . , xs } -- : P{t = i } = i , P{t = j } = j , i A, t > s,
i A i

= arg min S P - P ( , , ) , . ( , , ) ( , , ) . (2) , (3) , H0 = {{xt } } : H0 = { = 0, i = N -1 , i A}. H0 , H1 = H 0 , n = 2 l ( , , ) + n ln N ( n ) (0, 1) : d = d (x1 , . . . , xn) = {0, n < ; 1, n }, (6) -- - N . .

= 1;
s j =1 j

, [6] xt , . 4. xt , (2) , (3) , s c : P = (pi1 , . . . , is , is+1) ,
s

P{µt = 1} = 1 - P{µt = 0} = , t > s , P{x1 = i } = . . . = P{xs = i } = i , i A.

j {1, . . . , s },

t > s,

= 1,

s = 0;

(3)

p

i1 , ..., is , is

+1

= (1 - ) is

+1

+
j =1

j

is

- j +1

, is

+1

,

i1 , . . . , i

s +1

A, (4)

[1] . ., . . . ., . . . .: , 2001. [2] . ., , . ., . . . : , 2003. [3] Raftery A. E. A model for high-order Markov chains. Journal of the Royal Statistical Society, B, vol. 47, no. 3, 1985, pp. 528539. [4] . ., . . -, . , . 15, . 3, 2003, . 149159.

jk -- . 1. :
s n s

l ( , , ) =
t =1

ln xt +
t =s +1

ln (1 - ) xt +

j
j =1

x

t-j

,x

t

.

(5)

: P ( , , ) -- , (4) ; P -- ,

242

. . , . .
1 , 2 0 0 4 , . 4 0 4 1 . ries generated by mixtures, I, 1 , 2 , 1 9 7 8 , p p . 9 5 1 0 5 , 2 2 2

[5] . . r - . , . 48, [6] Jacobs P. A., Lewis P. A. W . Discrete time se II. Journal of the Royal Statistical Society, no. 228.

p - 1 . .
, -- , . [8] .
r

m=
i =1

p

i

i

.

v (n) -- n. p - 1, p -- , [1] . p - 1, . , s (n) log n s (m) . v>t (n) n, t . N (M) -- M. . (0, 1/3) t = exp ln x (1-) / (2e)

pi - 1, i = 1, . . . , r . , . m, . s = s (m) m. s (m) m p - 1. s (m) [9] . [3] , [6] , o (x) n, n x , (1 - ) ln ln n < v (n) < (1 + ) ln ln n,

244

. .

p - 1
cx 1 1- ln ln x ! k- 2

245

Np

x v (p - 1) [ (1 - ) ln ln x , (1 + ) ln ln x ] , v
>t

ln y

2

1- ln ln x ! 2
p t i =1

в
1 (p i )
(1-) /2 ln ln x

(p - 1) > v (p - 1)

1 2

=

x x = +o ln x ln x

. <

в

p < x i =1

1 (p i )

k- (1-) /2 ln ln x

<

. M = {p x | v (p - 1) [ (1 - ) ln ln x , (1 + ) ln ln x ] }.

k [ (1 - ) ln ln x , (1 + ) ln ln x ] .
cx в 1- ln ln x ! ln2 y 2 1 в (ln ln x + c1) k (ln ln t + c2) k!
k [ (1-) /2 ln ln x , (1+3) /2 ln ln x ]

(1-) /2 ln ln x

7.2 188 [7] N (M) = x /ln x + o (x /ln x) . , N pM x , y = e l n x /l n l n x , . : v
t

(p - 1) > v (p - 1)

1 2

=o

x . ln x

c1 , c2 . , 1 = (1 - 3) /2 > 0 :
cx ln2 y 2e l n l n t + c 1 - ln ln x
2 (1-) /2 ln ln x k (1-1) ln ln x

189 [7] , p p - 1 o (x /ln x) . ,
p-1 -- < n x r , rn + 1 -- < N r< n

(ln ln x + c1) k!

k

191 [7] .
cx ln ln2 x ln
1-

x

Np

x

p,

ln2 x

2e l n l n t + c 1 - ln ln x

2

1/2 ln ln x

,

n, n < x /y , v t (p - 1) > v (p - 1) /2, v (p - 1) [ (1 - ) ln ln x , (1 + ) ln ln x ] . 4.2 54 [7] s = 2. <
xn < cx 2x (n) n ln n 1 (n) ln2 x n

t o (x /ln x) . , , , . . c Nn x (n) >
cn ln ln ln n

= x + o (x)

<

cx ln2 y

1 . (n)

. , N (n , n . (n) = n
p |n

x | v (n) [ (1 - ) ln ln x , (1 + ) ln ln x ] ) = x + o (x) .
1 p
v (n)

n. (. [7] , 4.1 28) .

1-

n
i =1

1-

1 pi

=n
p p
v (n)

1-

1 p

>

246

. .

4.1 28 [7] c1 > c1
n ln pv
(n)

>

c2 n cn > . ln (v (n) ln v (n)) ln ln ln n

[1] Erd s P. On the normal number of prime factors of p - 1 and some related problems concerning Euler's -function. Quart. J. Oxford, 6 (1935) , 205 213. [2] Boer B. Diffie-Hellman is as strong as discrete log for certain primes. Lect. Notes. Comp. Sci., 403 (1988) , 530540. [3] Hardy G. H., Ramanujan S. The normal number of prime factors of a number n. Quart. J. of Math., 48 (1917) , 7692. [4] Maurer U. M. Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms. Crypto'94, 271281. [5] Sacurai K ., Shizuya H. Relationships among the computational powers of breaking discrete log cryptosystems. Eurocrypt'95, 341355. [6] TurАn P. On a theorem of Hardy and Ramanujan. J. Lond. Math. Soc., (2) , 30 (1929) , 93111. [7] . . -- .: , 1967, 511 . [8] . . -- . ., . ., . 2230. [9] . . p - 1. -03, . 218220.

. . , . .
. , Middleware (MW) . MW , . FIPA -- , , , , . , , . . . . 1. . 2. . 3. . 4. . 5. . 6. . 7. . 8. . 9. . . --
, 04-01-00089.

« »

250

. . , . .

251

, . , , «» . , , Open Agent Architecture () , SRI [9] . High Low. High «» Low, Low - High, . High, Low , «» [1] . , , : 1) «» ; 2) «» . -- , . . [5] , [8] . , , . High , Low , «» [2] . , , «» . () Open Agent Architecture, SRI. , , . «» . : 1) -; 2) -; 3) .

-- . , , . , «black board» . . . -. . , . - . , - - , , , . , . , , . . , , . . , , -. , , , - . - - , , , , , . . , . . . , , . .

252

. . , . .

253

. 1. , , , . -, , , , , «» . , . - , . . 2. . 3. . , . . 1. - . 2. - . (, , , ) . . , . . . , . . . 1. . « » -

, . . . 2. , . . , «» . 3. ( ) -. 4. , , . 5. - . SRI , , , , [9] . , , «» , , , , , . . , , . , , . , , . , , , . - . . -

254

. . , . .

255

. , - , , . , . - . , , - , . , . (, IPsec .) . , , , [3] , [4] , [6] , [7] . , , - . - ( -) , . () , . . -, . (-) . . , , , . , . , , . , - . . ,

- . , , , - -, . , . , -. , , . , - , «» . , «» . . : 1) ; 2) ; 3) . «» . , SRI .

[1] . ., . . // . . . « ». : , 2000. . 4041. [2] . ., . . // . .: , 2000. . 7. . 1 . 1 8 5 1 8 7 . [3] . ., . . // XXX I « , -

256

. . , . .
, , . IT+SE'2003 ( ) » (1928 ) . -, 2003. . 181184. . ., . . , // . 2003. . 15 . 2. . 4 0 4 6 . . . () // Jet Info: - « », 2002. 14 (114) . . 311. . . , // . .: « », 2004. 5. Grusho A., Timonina E. Construction of the Covert Channels // International Workshop «Information Assurance in Computer Networks. Methods, Models, and Architectures for Network Security» (MMM-ACNS-2003) . St. Petersburg: Springer, 2003. LNCS 2776. P. 428431. A Guide to Understanding Covert Channel Analysis of Trusted Systems, National Computer Security Center. NCSC-TG-030. Ver. 1, 1993. Martin D. L., Cheyer A. J., Moran D. B. The Open Agent Architecture: A Framework for Building Distributed Software Systems.

[4]

[5] [6]

. .

. . , - , , . . , , - , . , - () .
( N 04-01-00167) ( N 3.2/03) .

[7]

[8] [9]

258

. .

. . .

259

- DDoS- .

1.
, . , . , , , , : 1) -; 2) . - . - (, ) . . - , -- , , , , (, «» , () , .) , , , , « » .

, , , - , -. : · , ( , , ) ; · ; · ; · ; · , ; · , . . ( ) . , , () , , , , . . [1] , [2] [3] . . , -- . : 1) ; 2) ;

260

. .

. . .

261

3) ( «» ) . . : , ; , ; , , . . , [4] . : , . - . . , , . , . RDF DAML+OIL. MASDK («Multi-agent System Development Kit» [5] ) () , , JADE.

DDoS- , . DDoS-. DDoS , (, , ) . . , . DDoS- , , . « » «», DDoS-, , . IP- . : 1) , ( -- , , MULTOPS) ; 2) , ( , DoS-) ; 3) ( , TCP/IP- ) ; 4) ( Web-) .

3. -
DDoS- «», «», , , «» , «» [6] . «» . DDoS- , . . -

2.
DDoS- : «Part of»; «Kind of»; «Seq of». «Example of» . -

262

. .

. . .

263

, , . , . : 1) , 2) , 3) . . DDoS- . «», . - . , . ( ) , , , . « ». , . . - () , . () . () . , . () «» . () . - , . ()

. - () , , , . : 1) ; 2) , , , ; 3) . , .

4.
Java, Visual C++, MASDK JADE , , DDoS- [5] , DoS- [7] , [7] . DDoS- JADE Java. DDoS-, . , «», «», , , «». «» -- , -. DDoS-, . DDoS- :

264

. .

. . .

265

1) -, ; 2) - . . , , (, , , , .) , .

tems (CEEMAS 2003) . Prague, Czech Republic. Proceedings. Multi-Agent Systems and Applications III // Lecture Notes in Artificial Intelligence. Springer-Verlag, V. 2691. 2003. [5] Gorodetski V ., Karsayev O., Kotenko I., Khabalov A. Software Development Kit for Multi-agent Systems Design and Implementation // Lecture Notes in Artificial Intelligence. 2002. V. 2296. [6] . . . // -2004. IX . . 2. .: , 2004. [7] Gorodetsky V ., Kotenko I., Karsayev O. The Multi-agent Technologies for Computer Network Security: Attack Simulation, Intrusion Detection and Intrusion Detection Learning // The International Journal of Computer Systems Science & Engineering. 2003. 4.

. « ». DDoS- . , . . , , , .

[1] Cohen P. R., Levesque H. J. Teamwork // Nous. 1991. 25 (4) . [2] Grosz B., Kraus S. Collaborative Plans for Complex Group Actions // Artificial Intelligence. 1996. N 86 (2) . [3] Tambe M., Pynadath D. V . Towards Heterogeneous Agent Teams // Lecture Notes in Artificial Intelligence. V. 2086. Springer Verlag, 2001. [4] Kotenko I. Teamwork of Hackers-Agents: Modeling and Simulation of Coordinated Distributed Attacks on Computer Networks // The 3rd International/Central and Eastern European Conference on Multi-Agent Sys-

267

. . , . .
, , , . (, ) , . , , , . . : 1) ; 2) ; 3) () . A B -- . A B . A ( ) B . A () B . {Id (A) / Aut (A) , Id (B) , }, Id (A) / Aut (A) -- A, Id (B) -- B , -- B . . . , [0, 1] . (A, B) D (A, B) ,
, 04-01-00089.

B A. , , B , D () . . D () B . , B , . D (A, B) D () , B . D (A, B) < < D () , A . D () D (A, B) . , , . A, . . . . , - , . B , , . . A F , B . F A, B . , A B , B . B , B . G , -- , .

268

. . , . .

269

G , , , . . . ? ? 1. , , , F . 2. , . B . , [0, 1] . U () -- B , U -- . U () /U -- . D () , , D () =
U () . U

. . , . . A, B C , , . z C A' s d d d xd y d d d © B x = D (B , A) , y = D (C , B) z = D (C , A) . A C , z < x , z < y . A A, A B , B C , , A B C C A, , A C . z min (x , y) . , C A G , , : G = (A, B , C , . . . , D (A, B)) . 1. C , B1 , B2 , . . . , Bn , A C , E1 , E2 , . . . , E m , A

D (A, B) : · A B ; · A; · , A; · , ; · B . D (A, B) B B . . , [0, 1] , . , , , .

-- C A.

270

. . , . .

271

. , [0, 1] x [0, 1] , D () = x . min (D (C , B1) , D (B1 , B2) , . . . , D (Bn , A)) = = min (D (C , E1) , D (E1 , E2) , . . . , D (Em , A)) . . A D () . min (D (C , B1) , D (B1 , B2) , . . . , D (Bn , A)) = D () , C A C , B1 , B2 , . . . , Bn , A. min (D (C , E1) , D (E1 , E2) , . . . , D (Em , A)) < D () ,

C A C , E1 , E2 , . . . , Em , A. . min (D (C , B1) , D (B1 , B2) , . . . , D (Bn , A)) min (D (C , E1) , D (E1 , E2) , . . . , D (Em , A)) . 1 . . , , , . , . , G . D (A, B) = x , D (B , A) = x A, B . - . , [0, 1] x [0, 1] , D () = x . G .

2. D (A, B) G . . G 1. G . , , . , . . . G , . . G , G [1] . 2 . . , , , 0 1, . . , G , , , . . , . , , , . . , , . , , . . 1. , . , , , F ( ) .

272

. . , . .

2. G . 3. , .

. .
[1] , , GRID.

[1] . ., . ., . ., . . . .: , 1990, 384 .

1.
. . . . [1] 1. A B C , GRID . B ( ) A. B () A. {Id (B) /Aut (B) , Id (A) , (Id (B)) }, Id (B) /Aut (B) -- B , Id (A) -- A, (Id (B)) -- A. . L, . · A, B C DCA (B) : C L A B , B C . · A C T DTA () : T L, A.
1 [1] .

274

. .

. . .

275

, B A DCA (B) DTA ( (Id (B)) , , A B . [1] DCA (B) DTA ( (Id (B)) . , , . B , . . .

, . , ( ) . : · G = (C , E) -- , .

3. «»
, «» . P = pi , i = 1, . . . , n pi , p1 = B , pn = A, . 1. B A P , pi , p j P DCA (pi) DCA (p j) i j . 2. GA G A, A GA B GA B A GA A . 3. GA G C G C GA / C A G r = (D , B) , D (GA \ A) , B GA r G , r GA . . 1 ( ). A GA G , GA l L , DTA () = l . GA r = (D , B) , D (GA \ A) , B GA , DCA (D) DCA (B) , , -- . . , , , DCA . . , : r = (D , B) , D (GA \ A) , B GA DCA (D) > DCA (B) .

2.
[1] . : , . , ( , ) . 1. -- . , , -- . 2. -- , , , - , , , , . , , , : DCA (C) > DCA (B) B = C = A, B , A. , C

276

. .

. . .

277

D A B . , B A. , DCA (D) DTA () > DCA (B) . , {Id (D) / Aut (D) , Id (A) , (Id (D)) } B , . . 1 DCA GA . . . . 1. A « » , A . , «» ( «» ) c DC , . 2. A « » A , ( A ) A . , DC . , . . , , , , . , , .

GRID-, G = (C , E) DCA (B) , DTA ( (Id (B)) A, B C , U (G , DC , l) , l L , l : U (G , DC , l) = min { a C , c C : DCv (c)
| C | , C C

l }.

4. GRID
GRID, . . · -- , , . · -- , , .

, GRID-, . , : · U l [lmin , lmax ] , · U (G , DC , lmin) 1, · U (G , DC , lmax) |C |. [lmin , lmax ] . U . 1. U . -- U (G , DC , lmin) = |C |, . 2. U , -- U 1 |C | . , . 3. U - «». , U GRID-, , , . , , , -- , . , , . 4. l , Gl , , GRID , l . U (G , DC , l) Gl . DCA (B) = ai , i [1, n2 ]

278

. .

A, B C , {a j }, j [1, n2 ] , j -- i a j a j +1 . , l [a j , a j +1) Gl , U (G , DC , l) . l U (G , DC , l) Gl . , (. [2, . 167] ) , , .

. . , . .

- () , , . . , , , [1] , , [2] . « ». [3] . . - . - .
( 04-01-00167) , ( 3.2/03) FP6 .

. · , , , , , . · GRID .

[1] . ., . . . . [2] . . .: , 1988.

280

. . , . .

. . .

281

. , , , . , . , , , , .

Declipped «» f [t1 , t2) . Happens Initiates: , : t1 < t2 ¬ Clipped (t1 , f , t2) , ¬ HoldsAt (f , t2) Happens (a, t1) Terminates (a, f , t1) HoldsAt (f , t2) Happens (a, t1) Initiates (a, f , t1) Declipped (t1 , f , t2) Happens (a, t1) t1 t < t2 Initiates (f , t2) .

1.
, : 1) -- , , 2) , 3) -- . 1.1. , Happens, Terminates Initiates . · Happens (a, t) «», a t . · Initiates (a, f , t) «», a t , f t ( t) . · Terminates (a, f , t) «», a t , f t ( f t) . HoldsAt (f , t) «», f t . InitiallyTrue (f ) InitiallyFalse (f ) f 0. 1.2. Clipped (t1 , f , t2) «», f [t 1, t 2) . Happens Terminates: Clipped (t1 , f , t2) Happens (a, t1) t1 t < t2 Terminates (f , t2) .

¬ HoldsAt (f , t) InitiallyFalse (f ) ¬ Declipped (0, f , t) , InitiallyTrue (f ) InitiallyFalse (f ) .

t1 < t2 ¬ Declipped (t1 , f , t2) , HoldsAt (f , t) InitiallyTrue (f ) ¬ Clipped (0, f , t) ,

2. ILOG JRules
ILOG JRules [4] [5] , API Java-. , . Java-, . ILOG JRules : ( ) , . , , Java JRules. :
when { ECTimePoint(?t1: time); ECTimePoint(?t2: time; time > ?t1); ECHappens(?e: eventName; ?t: time; time > ?t1; time <= ?t2); ECFluent(?f: name); ECTerminates(eventName equals ?e; fluent equals ?f; time == ?t); not ECClipped(fluent == ?f; time1 == ?t1; time2 == ?t2); } then { assert ECClipped {

282
fluent = ?f; time1 = ?t1; time2 = ?t2; } }

. . , . .

. . .

283

t1 t2 , f. (t1, t2] . , e, f. , (then) ECClipped , ( 7) .

, , , . , , .

4.
, . ILOG JRules. . ILOG JRules SPIN, NuSMV.

3.
. , . ( ) ( ) . , , . , . , , . , , -- . RBAC. RBAC, , . -

[1] Kowalski R. A., Sergot M. J. A Logic-Based Calculus of Events. New Generation Computing, 4: 6795, 1986. [2] Bandara A., Lupu E., Russo A. Using Event Calculus to Formalize Policy Specifications and Analysis. In IEEE 4th International Workshop on Policies for Distributed Systems and Networks, pages 2639, June 2003. [3] Miller R, Shanahan M. The Event Calculus in Classical Logic. Linkoping Electronic Articles in Computer and Information Science, 4 (16) , 1999. [4] ILOG JRules. http://www.ilog.com/products/jrules/. [5] JSR-000094 JavaTM Rule Engine API. http://www.jcp.org/aboutJava/ communityprocess/review/jsr094/.

. . .

285

. .
-- (DAC) (RBAC) . - .

- , . , , , , . , , , () , . .

1.
, 70- , , -- . ( -- Linux, Solaris, Windows 2000) . , Department of Defense Trusted Computer System Evaluation Criteria [3] , [4] . : , . , , -- , -- , . , , . : ( , ) . , , , . , . , ,

, . , , , . , . , , . - , OASIS Standard eXtensible Access Control Markup Language (XACML) , OASIS Open [6] . , - . . (MAC) , (DAC) (RBAC) . 70- . , , ,

286

. .

. . .

287

( ) . UNIX «» (root) , . . 1. : · S , ; · O , ; · A, ; · M S в O в A, ( A) . a s o , (s , o , a) M. (s , o , c) M, M (t , o , a) t S a A \ {c , ct }. (s , o , ct) M, c ct . , «» « », . , , , : o ! s : (s , o , c) M ( ! -- ) . , , , ( ) ( , ) . , , , . , , .

2.
, ( ) , , . , -

. . RSBAC Linux ( Linux, , RBAC -- ) , Solaris 8 [5] . sudo, UNIX- , ( sudo [5] ) . , , , . , root, ( / ) , « ». , . , , , - (, , ) . ( ) . , , , , . (, , ) , , ( : , , . .) , (, « » « », « » -- ) . , , . , , ( , -- ) . -

288

. .

. . .

289

. , . , , . , , , , , , , . . 2. : · U , ; · R , AR , (, R AR = ) ; · P , AP , (, P AP = ) ; · PA P в R , APA AP в AR , ; · UA U в R AR , AUA U в AR , ; · RH R в R , ARH AR в AR , , . p u, r , r R : (u, r ) UA, r r , (p , r) PA, (r) , (r) . . , . , , [1] . -- -- -- . : a p UAa p U в R AR , PAa p P в R APAa p AP в AR . , a p u r , (u, r) UAa p , r p , (p , r) PAa p . , -

, . , . , . .

3.
, , - . , - , . , , . 3.1. . . , US : U S c PA : P O в A . US . , u U p , US (u) PA (p) , , s US (U) (o , a) , - US 1 (s) ( - ) PA 1 (o , a) . . O = {o }, S = U {u0 } ( u0 -- , U) , A = P . M : (u, o , p) M r , r r : (u, r) UA, (p , r ) PA. , u0 . US PA : US (u) = u, PA (p) = (o , p) .

290

. .

. . .

291

. u p . , r , r r : (u, r) UA, (p , r ) PA. , US (u) = u p o (, ) , ( PA (p) = (o , p)) . , u (u = u0) p o , r , r r : (u, r) UA, (p , r ) PA, u p . 3.2. ( ) : . , , . , SU : S U PA : P O в A. s a o , SU (s) - ( ) PA 1 (o , a) , u SU (S) - p , SU 1 (u) PA (p) , s a o s , SU (s) UA AUA, - SU (s ) PA 1 (o , a) . . U S , , SU -- . o ai A \ {c , ct } ro , ai owno ownt . , ai A \ {c , ct } : o · po ,ai , ai o ; : · granto , ai , ro , ai ; · granto , c , owno ownt . o , ro , ai po , ai , owno granto , ai ai , ownt -- granto , c . o

. : o ownt owno , . o PA : p = po , a , PA (p) = = (o , a) , p = granto , a , PA (p) = (o , c) , p = granto , c , PA (p) = (o , ct) . : a o , ro , ai , c , owno , ct , ownt . o .

, . , , , ( ) . , , , , , , , .

[1] Ravi S. Sandhu, Edward J. Coyne, Hal L. Feinstein, Charles E. Youman. Role-Based Access Control Models. IEEE Computer, 29, 2, 3847. [2] David Ferrariolo, Richard Kuhn. Role-Based Access Control. Proceedings of 15th National Computer Security Conference, 1992, 554563. [3] Department of Defense Trusted Computer System Evaluation Criteria. DoD, DoD 5200.28-STD, 1985. [4] A Guide To Understanding Discretionary Access Control In Trusted Systems. National Computer Security Center, 1987. [5] RBAC in the Solaris Operating Environment. Sun Microsystems, 2001 [6] eXtensible Access Control Markup Language (XACML) Commitee Specification. OASIS Open, 2003.

-. . .

293

1.

. . , . . , . . , . . , . . , . .
[1] - . - .

[1] , , , ( , ) , , , -- , . , , , ( [2] ) . (, , [3] ) , . , - ; , . .

. , , , -- - . . , . : · : , ; · , ; · , . - , , , , . , , - , . [4] . - - , , . , , , , . (, .) - [5] . , . -

294

. . .

-. . .

295

. 18 . 12 . , , -- . , , .

2.
[6] . « .» , , , , , , , , . , . , «» . , - , . . -- [7] , . . . , , . , , , , -- . -- -

/, , . , , , ( ) . , , ( ) -- . , , ( ) , . [8] , , , , , . - , , «» . . - . , , ( ) . , . , , ( ) , ( [9] ) . , -- , . -- . , , , . , , . , , , .

296

. . .

-. . .

297

. . . , . . , , , . , , , . . -- , . , ( ) -- , , , (. [10] ) . , . , , , , . . , ( [11] ) . , , , , . . . , , . , «» -

. IEEE Std 802.11i [12] . [5] . (, , ) , . , . , .

-- . , -- . .

[1] . . . « » (-03) . .: , 2004, 12 . [2] Lee S. C., Davis L. B. Learning from Experience: Operating System Vulnerability Trends. IEEE IT Pro, January/February 2003, 8 pp. [3] Linux . http://www.nsa.gov/selinux/. [4] . ., . . . . . . . .: , 1999, 11 . [5] . ., . . -- . . . II. , 1993, 21 . [6] . ., . ., . ., . . -

298

. . .
2000. « » (-03) . .: , 2004, 13 . Bell D. E., La Padula L. J. Secure Computer Systems: Mathematical Foundations and Model. Technical Report M74244. The MITRE Corporation, 1973. Schell R. R. Information Security: Science, Pseudoscience, and Flying Pigs. Proceedings of the 17th Annual Computer Security Applications Cinference (ACSAC 2001) . IEEE, 2001, 12 pp. Weissman C. MLS-PCA: A High Assurance Security Architecture for Future Avionics. Proceedings of the 19th Annual Computer Security Applications Cinference (ACSAC 2003) . IEEE, 2003, 11 pp. Ganger G. R., Nagle D. F . Better Security via Smarter Devices. Proceedings of the Eighth Workshop on Hot Topics in Operating Systems (HotOSVIII'01) . IEEE, 2001, 6 pp. Bryant E., Early J., Gopalakrishna R., Roth G., Spafford E. H., Watson K ., Williams P., Yost S. Poly Paradigm: A Secure Network Service Architecture. Proceedings of the 19th Annual Computer Security Applications Conference (ACSAC 2003) . IEEE, 2003, 10 pp. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Medium Access Control (MAC) Security Enhancement. IEEE, 2004.

[7]

[8]

: . . , . .

, . , . () . , . . , . , , , , , , . . , . . , - , . -- . , . , , . .

[9]

[10]

[11]

[12]

300

. . , . .

. . .

301

, . , , , . , , « -- ». , , , , . , . , , «».

. , - . , , « -- -- ».

2.
. () , . , . . : 1) , ; 2) , ; 3) , , ; 4) , ; 5) , . , : , ; , . , , , , . , .

1.
, . () [1] [3] . , . , « -- -- ». . -, . , , , . , , ,

302

. . , . .

. . .

303

, . : 1) , , ; 2) , ; 3) , .

, , [2] . , , . .

4.
. , -- , , . . , , . , « ». , 15408, . , , , , ( -- ) , . () , . , -

3.
, , . , . . : , ; , , ; - , . . : , ; .

304

. . , . .

. . .

305

, . «» , . , , IP (HUB) , . , - . , «» , . - , . «, , » « , » . , IEEE 802.3 Ethernet, . TCP/IP - , , .

1, 702.

. , .

[1] Vladimir Zaborovsky. Multiscale Network Processes: Fractal and p -Adic Analysis. Proceedings of 10th International Conference on telecommunications (ICT'2003) , University of Haute Alsace, Colmar, France, 2003. [2] . ., . ., . ., . . . « (-03) », . . . , 2324 2003 . [3] Vladimir Zaborovsky, Yuri Shemanin, Jim A. McCombs, Alex Sigalov. Firewall Network Processors: Concept, Model and Platform. Proceedings of International Conference on Networking (ICN'04) , Guadeloupe, 2004.

307

. .

, . , , , . , , , , , . , . , , , , , . . [1] , [2] . , , , . ,

( -- [1] [3] ) , .

1.
1.1. , () , , . , . , , . , . , ( ) . , «» , . , [1] , [2] , . 1. , . , , ( ) .

308

. .

309

. 2. , . , , , . , . [1] , [2] . 1.2. . . , ( ) , : · , ; · , «» ; · ; · ; · , ; · , ; · , , - ; · , ; · .

, , , : · ; · ; · ; · , . . . , () , . 1.3. , . 1. . , . 2. . . 3. . . 4. . , , . 5. . (

310

. .

311

) . 6. . , « » . 7. . () (, , .) , . , , , . : · , ; · , , ; · , , . , ( ) , . - .

. , . n n , . «» x . f (x) , f -- , , : · , f (x) , ; · , ( , ) . . , f . , , n f . , x «» x . « » , , . . x . 2.2. , , . , , , , , , .

2.
2.1. -- [4] [8] , , , , . ,

312

. .

313

, d - . d n = 2d , d - . , a1 , a2 , . . . , ad , fi 0 1. a1 , a2 , . . . , ad b1 , b2 , . . . , bd , i , ai = bi . , d = 2, , d = 3, -- . , / , «--», , . « » [1] . , , . . 2.3. . / . , . , , , , . , , , . . , , . . . «». ,

(FS -) , . , « » . (By -) « » . By - . . . , -- , . , , . . , «» , , «» (. ., , «») . , : · ; · «» («» ) . , . : · ; · ; · ; · ; · ; · «» . , , ( ) , ( ) .

314

. .

315

, . . , . ., «» . , , ( ) , , , , ( ) . , -- . . , () , , . , . . . , «» («» ) . ( ) . , , . ., ( ) , . «» , , , «» , , . . , ,

«» , . , , , . t -, «» t . . , , . , , . «» , . , , , , , . , , , , . ( ) , . , « » ( 1/2) ( , ) . . ( ) , . ( ) . , , () , , , , . , () , ,

316

. .

317

, . . . . -, - . -, , . : · , ; · ( , , ) ; · (, ) . , . TP -. . . . , ( ) . , . .

3.
3.1. , () . () ( ) . i i + 1 . -

, () . «--», (k) ( 1k) , k . , «--» ( ) , «--» ( xi) , «--» ( ) . i j / , i j . ( ) i j . i , , i «--» . , r i ( ) , i i j , i j . , . i i , i = 1, . . . , n, . n- P = (1 , 2 , . . . , n) . t -, t . i : , , , i , , i . 3.2. [7] . ( ) . ,

318

. .

. . D , . 4.2.

319 .

() . , ( ) . . , . . . . , , TP -. ( ) . , . , , , . , . , , ( ) , «» . ( ) [7] .

4.
4.1. n , . . . , . . . . -

t ( ) . , , n - t , t ( ) . . , D , , n - t , C . -- ( ) C , , C C . ( : C 0 ) . C . , . , «» . , , . , , «» [9] .

. -

320

. .

, , . [1] , [2] . , , , : · ; · ; · ; · ; · . , - . , , , .

«Linux over » . . , . .
, , . , , -- Linux, .

[1] . . . .: , 2003, 212 . [2] . . . 2004, 450 . http: //www.cryptography.ru. [3] . . , . . 1997. 12 (3637) . . 1214. [4] Yao A. C. Protocols for secure computations (extended abstract) . Proc. 23rd IEEE Symp. on Foundations of Computer Science (FOCS'82) . 1982. P. 160164. [5] Yao A. C. How to generate and exchange secrets. Proc. 27th IEEE Symp. on Foundations of Computer Science (FOCS'86) . P. 162167. [6] Goldreich O., Micali S., Wigderson A. How to play any mental game. Proc. 19th ACM Symposium on Theory of Computing (STOC'87) . P. 218229. [7] Micali S., Rogaway Ph. Secure computation. Lecture Notes in Computer Science. Advances in Cryptology -- CRYPTO'91. V. 576. P. 392404. [8] Beaver D. Foundations of secure computing. Lecture Notes in Computer Science. Advances in Cryptology -- CRYPTO'91. V. 576. P. 377391. [9] Ben-Or M., Canetti R., Goldreich O. Asynchronous secure computation. Proc. 25th Annual ACM Symposium of Computing (STOC'93) . P. 5261.

1.
, ( «») , ( «») . , , -- . . , . . . , , «Linux over ». -

322

. . , . .

. . .

323

, . Linux, . Linux, . Linux, , . , Linux. , Linux. , Linux .

(, ) . , , . , , -- .

3.
Linux , . , Linux , . , Linux , Linux Linux Linux . IA-32. 1. Linux. Linux ( , Linux -- ) . Linux . 2. Linux Linux. Linux Linux . 3. Linux . Linux. , , . , , , . , Linux , Linux , , .

2. Linux
Linux, , : Linux, Linux Linux. Linux : · , ; · , Linux. Linux Linux. Linux , / . , Linux, , Linux , , , , .

324

. . , . .

. . .

325

4. Linux. Linux 3- , , , , , . , : « » -- « Linux» -- « Linux», .

4.
Linux Linux. , Linux Linux, Linux 2.4, , . Linux.

· , . · , , Linux, , . · Linux, «Linux over » , Linux. · -- Linux .

5.
Linux, Linux, , Linux. , Linux , , Linux. , , , Linux. , .

6.
Linux :

. . .

327

. . , . . , . .

. , , , . . , [1] . , . , -- , . [2] .

. . , , . , . , , . . (IP-, , . .) [3] . S = (X , V , R) , , (X , V ) (X , R) . , . , [4] . Internet - , , . , , .

1.
, , () . : (misuse detection) . , . . , . , , . , , . ( ) -

2.
, . , , , , . , [5] . . . ,

328

. . , . . , . .

. . .

329

, , . . [5] . . . AS (t) = (X , V , R) [2] , v j ri j (t) i (t) , . x1 xn , [6] . -- . : «» «». «» 1. 1, k := 1; 2. p , k, «». j (t) j ( k p) ( ) . 3. k := p ; , , 2. «» 1. 1, K = {1} -- ; 2. k K , k, . j (t) j ( k) ( ) . K := . K , . 3. , , 2. . 1, 1 2 : , 3 ; , ( ) 0.1 ( ) .

. 1. . .

( ) . : |X | = 20, |V | = 62, |R | = 500. -- . -- . , . [t , t + 10] t (0, 50) . . 1 , , -

. 2. . .

330

. . , . . , . .

. . .

331

.

.

3.
[7] . 1. . , , , . ( ) . , , . , . 2. , . S = (X , V , R) , X -- , V -- , R -- , , . X V , R . 3. . X -- , V -- . , . , . : X , V R .

[1] . ., . ., . . . . , , 4, , 2002, . 2535. [2] . . . , 2002. [3] . ., . . -: . http://space.iias.spb.su/ai/doc/ CAI- 2002- 2.pdf. [4] . ., . . . , , . 4, , 2002, . 175179. [5] . -- ! http://www.bytemag.ru/ Article.asp?ID=2030. [6] . ., . ., . . . Proceedings of 8th International Conference «Problems of Operation of Information Networks» (Bishkek, 2229 August 2004) , , . 2, . 258263. [7] Popkov V . K ., Sokolova O. D. Covering in Hypernet. CSIT'2000, Ufa, Russia, p. 1213.

(, .) , , .

. . .

333

. . , . . , . . , . .

, , , , . . . , . . : , , , ( ) «» . . [1] [8] , , . (A. Shooman) ( , , ) . , , , ( ) . . :

, , -- . , , .

1.
( -- ) . [1] ( [9] ) : R (G) = i j R (G (ei j)) + (1 - i j) R (G \ {ei j }) , (1)

G (ei j) -- , ei j , ( ) i j , G \ {ei j } -- , G ei j . R (G) = i R (G (vi)) + (1 - i) R (G \ {vi }) , (2)

G (vi) -- , ei j , vi , i , G \ {vi } -- , G vi . ( 0) , , . . , , . [10, 12, 13] , , . . , 2. . 1. G k e1 , e2 , . . . , ek 1 , 2 , . . . , k s t . G

334

. . , . . , . . , . .

. . .

335

e1 , e2 , . . . , ek 1 , 2 , . . . , k ,
k k

R (G) =
j =1

j · R (G (e1 , . . . , ek)) +

i =1

(1 - i)

j =i

j · R (G \ {e1 , . . . , ek }) (3)

k

R (G) =
i =1

i · R (G1) · R (G2) .

(6)

est
k k

R (G) = (1 + st - 1 st ) в R (G (e1 , . . . , ek))

j +
j =2

st i =2

(1 - i)

j =i

j

в

k j =2

k

+ (1 - 1 - st + 1 st ) в R (G \ {e1 , . . . , ek , est })

j + (1 - st)

i =2

(1 - i)

j =i

j

в (4)

. (1) ek , ek-1 , . . . , e1 (, , est ) , . , G , e , , R (G) = · R (G \ {e }) . , , . ei j i j 1, , , - 2, . . . 2.

(5) , . : , «» , , , «». () . , , , 2. , , . , , . 2.1. [5] 1 2 , 2, , , , . , 2, p=
p1 p2 p1 p2 = , 1 - (1 - p1) (1 - p2) p1 + p2 - p1 p2

2.
, , [11] . , , , - . G1 G2 ( ) , G , G , G1 G2 k R (G) = R (G1) · R (G2) . (5)

(7)

() r = p1 + p2 - p1 p2 . (8)

k > 2, [13] , [14] : 2. G1 (n, m) k e1 , e2 , . . . , ek 1 , 2 , . . . , k .

336

. . , . . , . . , . .

. . .

337

G1 (n, m)
k k

R G1 (n, m) =
i =1

i i =1

i

-1

- k + 1 R G2 (n - k + 1, m - k + 1) ,

(9) G2 (n - k + 1, m - k + 1) G1 (n, m)
k -1

=
i =1

-1 i

-k+1

.

(10)

2.2. [15] , , 2: 3. G G1 G2 , x y . R (G) = R (G1) R (G2) + R (G1) [R (G2) - R (G2) ] + R (G2) [R (G1) - R (G1) ] , (11) Gi Gi , x y . , , (6) .

ґ , . , , . [13] 4- , [16] 5- . 4. . ( ) , -- . , . , , .

4.
, . , P = i j , . , ( , , ) , . . . , [9] , [12] . , . () , , . , , , (V1) . , , , , V1 V2 = V \ V1 V1 V2 = V \ V1 \ V (C) C , V (C) -- ( -

3.
(1) , (3) (4) , : 1. . . 2. . , k e1 , . . . , ek 1 , . . . , k ,
k k

R (G) =
i =1

i

1+
i =1

1- i

i

.

(12)

3. . , .

338

. . , . . , . . , . .

. . .

339

) . . 2. , , . ei j (vi v j) 1, deg (vi) + deg (vi) - k + 1, k -- , ( , ) . ( (2) ) [17] . . . , , . , ґ , . , : , .

4 ) , , -- , 0.22 . -- 28 , -- 0.16 . 0.08 . 1. n в m , n m , ( ) . . Intel Celeron 1800 MHz. 4 4 4 4 6 6 . 8 9 10 9 16 25 12 16 20 24 24 30 -- 4319 5 35279 47 322559 489 88 0.06 21263 15 > 8700000 > 30 . 234 0.16 1071 0.8 4338 3 16407 12 20222 16 212776 184 1433 3 10868 24 92763 232 8 0.01 303 0.4 149147 157 15 0.02 39 0.05 97 0.16 230 0.4 67 0.12 208 0.36

5.
. -- , , [2] . , , 4 4 Pentium III 800 MHz, 47 [2] ( , -

3в3 4в4 5в5 в3 в4 в5 в6 в4 в5

1. .

ARPANET 58 71 . . 7705 0.22 , -

340

. . , . . , . . , . .

. . .

341

2 (11) 7359 0.17 . [18] 10 8- 12- , , - . , . .

[11]

[12]

[13]

[14]

[15]

[1] ., . . . .: . ., 1960. . 1. . 109148. [2] Yubin Chen, Jiandong Li, Jiamo Chen. A new algorithm for network probabilistic connectivity. Military Communications Conference (MILCOM 1999) . Proceedings. IEEE 1999. Vol. 2. P. 920923. [3] . . . . 1964. . 1 7 . . 3 7 . [4] . ., . . . . 1971. . VII, . 4. . 7 8 8 1 . [5] Shooman A. M. Algorithms for network reliability and connection availability analysis. Electro/95 International. Professional Program Proceedings. 1995. P. 309333. [6] . . . (-7) . , 1982. . 36. [7] . . . . . 1965. . XXVI, 3. . 567574. [8] . . . . . . . 1975. 5. . 161165. [9] . . /3. (, ) . , 1982. 32 . ( . . . ; 356) . [10] . ., . . [16]

[17]

[18]

. . 2 . ./. . « (-2000) . , 2000. . 6769. . ., . . - . . . . , (ICS-NET'2001) . ., 2001. . 200204. . ., . . . . . . « , », -, , 1820 2002 . -, 2002. . 5. . 140147. Rodionova O. K ., Rodionov A. S., Choo H. Network Probabilistic Connectivity: Exact Calculation with Use of Chains. ICCSA-2004, Springer LNCS, Vol. 3046. P. 315324. . . . XXX « , , », , , 2003. . 215217. . . . . . . , 2004. . 134141. . . 5- . «-2004». « ». , 2004. . 113116. . . . . 8- . . « » ( «-2004») . -, 2004. . 2. . 213216. . . . . . « »: . -2004. 2004. . 3. . 157160.

343

. .
. , , -- . , ( , , . .) . , . - , () [1] . , , . (35 ) , . , . ( , TCP -- FIN RST, ICMP Host Unreachible) . , . , .

, , () , , , . , . -, « », -, , , , -, «» . , . . , , . , , . , . . () . ( ) . , , , . «» . () «» IP . [2] « ». . , . (, , ) . , IP , TCP UDP , ICMP

344

. .

345

. . Internet , RFC. RFC, . . . [1] , , 24 « » IP, 38 TCP, 2 UDP 9 ICMP. , , . Slammer, 2003 [3] . (!) UDP 376 1434, Microsoft SQL Server 2000 Microsoft Desktop Engine (MSDE) 2000. Microsoft ISS , , , , , , , . , UDP , . . HTTP, Web- . , . «» URI, HTTP , / , . RFC 850, 1123 2616. HTTP, NAT (HTTP File Name Translation) . , Web- -

, Web-. , TCP intersept Cisco [4] . ( ) , , . . , . , ( ) . last in -- first out. , . · ( ) . · . · . · . ( ) . , , ( ) . , , (, , ) . (, ) . , , , . ( ) . , « » . , , . , , HTTP,

346

. .

GET POST. , . , . . , , .

. . , . .
. , . , , .

[1] Beyond IDS: Essentials of Network Intrusion Prevention. Top Layer Networks, 2002. [2] Handley M., Kreibich C., Paxson V . Network Intrusion Detection: Evasion, Traffic Normalization, and End-to-End Protocol Semantic. Proc. USENIX Security Symposium, 2001. [3] CERT Advisory CA-2003-04 MS-SQL Server Worm. [4] Managing Cisco Network Security. Syngress Publishing, 2002.

, , . , . . -- C- . , ( , -- -- ) . ; . ITS4 [1] , LCLint [2] , «» . -- ; -

348

. . , . .

. . .

349

, ( ) , strcpy, sprintf, gets C. . , . , , . -- ( ) ( ) ( , , -- ) . , D. Wagner [3] N. Dor [4] . , , . -- , , . , , ( ) , . [3] . [4] . . (, , ) . , , . , .

1.
. -, , -- . -,

. -, , . , [3] [4] , , , . . C. . : · I -- ; · II -- ; · III -- . I , C , -- . , . II . () , . . II : , . III . II III , . I -- , . , / . « -» -

350

. . , . .

. . .

351

- -- . . : · ; · ; · ; · ; · ( , , ) ; · -. arr_min index < arr_max, arr_min arr_max , arr , , index -- , . , arr_min arr_max . ( ) , , . , , . C- . : · ; · ; · ; · , . -- , . , -

( «+» «-», ) . , , , . . , (, «x = a[i]») . . , «x = unknown», unknown . , , . -- -- « », , . , ( ) . . 1 ( a) 0 . . . 99 0 ... + 100 . . . + - . . . +

, a [0] , . . . , a [99] , , {0, 1, 2, . . . }. , 100- , . . . 2 ( b) 0 . . . b_max - 1 0

, b , {0, 1, . . . , b_max}, 0. b_max

352

. . , . .

. . .

353

b. ( '\0' ) , . . . , . , , . . . , . -- . , -- . II. {I } -- , (, «» ) . , «minimal_set_method», [5] , , , , . {I }. , , , . . . . , , , ( - ) . «» -.

. , - . , , . : ( -- ) . () . -. -- -- : , , > 0. , , . .

2.
, . , , . -- (, «» ) . . . 1. G ( , -) , · V -- , |V | 2. F0 , F1 ( ) . , F . · E -- . V \ F 2. F0 1, 0, F1 0.

354

. . , . .

. . .

355

7. , , : (if) (for, do, while) . 2. M V G A M, . 1. G M , . 2. (B , C) (C , B) , B V \ M, C M \ A. , A X M. 8. , M = {A} , (A, A) . , X M, X = A M. , Y V \ M {A} (V \ M) . 3. A , . 9. F0 , , F1 . , , , . . . A -- , M -- , B , C -- A ( (A, B) , (A, C)) . 1. B , C M. 2. L1 , L2 , B C , A, . 3. V \ F . . 1. . B , C M. X M \ A, (A, A) / . , G M , A. . B , C M, , A F1 : M M.

2. . , B M, C M. / L1 L2 . . B , C -- B , C L1 , L2 . , B , C , B , C = A, B M, C M, / , . , B , C A M, B C . , 2 . 3. ( -- ) . , A -- B MA , B -- A MB (A = B) . A, B MA MB . A MB . , B MA , MA MB . F1 MA MB , / A F1 . A -- B , B -- C . A = B B = C , , A = B B = C . MA , MB , MC -- A, B , C . , A = C . , C MA . 1 2 : L, B C , MB , A. , L MA \ A, X -- : X MA \ A, X = B , Y -- . / Y MA \ A. 2 2 X MA . , X = A. . , L , , C MA . . 2.1. , , G -- . : FV V -- , |V \ (FV F ) | = = n -- , F0 , F1 . LG (A, B) -- G , A B . . A, B |LG (A, B) | 2n . (1)

356

. . , . .

. . .

357

. , B «» , ( H) , A V LG (A, B) = LH (A, B) . H (1) , . X -- , Y , Z -- . X = Y X = Z , (X , X) . , A B . X = Y , X = Z L X B . , (X , Y ) . , X B , (X , Z) . : L -- . L, L . L1 , L1 , B . , L1 , L1 A ( L, L ) . , 2 , . . X (X , Z) . X B , , A B . , H , . 10. (1) -- . n , n + 2 . E E E F0 E E ··· E F1 E

/ . for, while, do, if, continue, break, goto. -, , goto . . ...... l1: for(;; ++i) for(;; ++j) for(;; ++k) if (i+j+k % 2) goto l1; else goto l2; l2: ...... , for , goto , for-, . , , goto . -, for-, while- . , , break, , , . do- . · do { < > } while (<>); while- . , , ( break) . · : . , . if, if-else. . , , , , -

, , , , F0 F1 2n . 2.2. , . C, -

358

. . , . .

. . .

359

«» . , ( 2 ) , goto, break, continue. continue, break. continue , , . continue, break , , . , , 1. , . . if, for, while, break, continue N1 , N2 , N3 , N4 , N5 . n n N1 + N4 , N2 , N3 , N5 , , , , , 2N1 +N4 . . , . . , , , .

[1] Viega J., Bloch J. T ., Kohno T ., McGraw G. ITS4: A Static Vulnerability Scanner for C and C++ Code. Proceedings of the 16th Annual Computer Security Applications Conference, 2000, p. 257. [2] Larochelle D., Evans D. Statically Detecting Likely Buffer Overflow Vulnerabilities. Proceedings of the 10th USENIX Security Symposium, 2001, p p . 1 7 7 1 9 0 . [3] Wagner D., Foster J., Brewer E., Aiken A. A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities. Proceedings of the 2000 Network and Distributed Systems Security Conference, February 2000, pp. 3 17. [4] Dor N., Rodeh M., Sagiv M. Cleanness Checking of String Manipulations in C Programs via Integer Analysis. In the 8th International Symposium on Static Analysis, July 2001, pp. 194212. [5] . ., . . . .

, . . , , , .

. . .

361

. .
() , . , , , ( Java) . . (Security Reference Monitor) . , , , , . , , (. . ) (. . ) . , , ( ) . , , . , , . , «» , . . , . :

· , ; · ; · . : · , , ; · , ; · , . , , «», Java. Java-. , « » . . , . , , . : · ; · , . : · , ; · . , , , , , . ( «» , -

362

. .

. . .

363

) , «» , . «» , . , . . . , , . , ( ) . ( ) . . , , . . . . , . «». , . . -- , . , , . , .

-- . , . : , , , , . . . , : , , , , . , , . , , . . . , , «» . «» : · ; , , , , . . , ; · -- ; · . : 1. , , . -

364

. .

, . 2. , . , . , , , «». , . , . « . . » : · (, ) ; · (, ) , . . «», . «» - , Windows 2000 Windows XP.

«-» : 117192 ., , 1. ./ (095) 932-8958; 939-2096. E- mail:yava@softline- m.com

«-» -- , -- . : · , call, IP- ; · , ; · -; · ; · , , -; · (SMT) . «-» . , , «» () . «». , . . . -- . IP-. IP , .

IP-. IPsec. : 1. : 28147-89 ( ) , 3DES, ( ) ; 2. : 34.11 ( ) , SHA-1 (SHA-256, SHA-384, SHA-512) ( ) , 1176.1-99 ( ) ; 3. : 34.10-2001 ( ) , 34.310-95 ( ) , 1176.2-99 ( ) ; 4. ; 5. ( -) .

« » () 2002 . , . , , () , () , , - . , , . , : · ; · () ; · , , ; · , , () . , , , , , , , . , , . -

, . , , . , « »: · · «» · « - » · « . .» · «-» · « » · «» · «» · « ""» · « » · «» · «- » · « » · «» · «» · «» · «» · «» · «» · « » · · «» · «» · « » · «» · «» · « » · «» · «-» · «- » · « », . · «» · «-» · « ""» · « ""»

· · · · · · ·

« ""» « ""» « ""» «» « ""» « ""» « "", . - » · « . . . » · « », . -

: 125438, , 4- ., . 15, « ""», /: +7 (095) 156-7102 : +7 (095) 154-6155, 782-3357, http://www.azi.ru, e- mail:azi@azi.ru

«»
«» . , . Doctor Web. Doctor Web, , . Doctor Web , . . , . Doctor Web . , Doctor Web « », «Virus Bulletin». Virus Bulletin 2002, Virus Test Center 2002, , Doctor Web . Doctor Web , , . Doctor Web , (, « ») . , Doctor Web , , MS WinWord Excel, , , Internet, .

-- «» . Doctor Web . «» « » Doctor Web . Nero Ahead Doctor Web «» CD-R. StopSign Acceleration Doctor Web on-line . Mail.ru, , , , Doctor Web . iDuba.net -- Doctor Web . 2002 Virus Chaser, Doctor Web. Doctor Web , , . , , . Doctor Web , , , «», , , , , , , . «» , , Doctor Web , .
«» : 119991 , . 40, H, 103 .: (+7-095) 135-6253, 137-0150, ./: (+7-095) 938-2970 E-mail: antivir@DialogNauka.ru WWW-: http://www.DialogNauka.ru, FidoNet: 2:5020/69

« ""»
« ""» ( «») 40 . , . «» , , , . , : · , -, ; · « » RU 0001.030001 1- ; · , ; · (BIOS) ; · , ( ) ; · ; · ; · ; · ; · ; · ; · ;

, , , , , . , , . , - . 440601, . , . , 9, .: (841-2) 56-39-16, : (841-2) 56-23-71, -mail: atlas@sura.ru http://www.atlas.sura.ru : 771 5027275 583602001 . : 440601, . , . , 9 /c 40 502 810 648 000 110 518 8624 . / 30 101 810 000 000 000 635 045 655 635 73.10 08 859 495

« ""»
« ""» , , . «» « , » « », 30.3.02.

, , , - . « ""» , , . « ""», , 40 , - , . « ""» : 125438, , 4- ., 15 .: 154-80-21, ./: 154-14-18 E-mail: korv@a5.kiam.ru

« ""»
1. -, - , . 2. . 3. . 4. , - - . 5. ; - . - . - - « ""» , , - , - .

«-»
-
- 2000 . -- (Public Key Infrastructure) . - , , , () , .

HTTP (S) . TLS 1.0 (RFC 2246) , CSP . 2003 - 40 000 CSP TLS, . « » - « ». , , . 43753, « » 2. - , : · · · · · ; ; ; «» ( ) ; « » ( ) ; · « » « " "»; · « » «-»;

«» CSP Microsoft -- Cryptographic Service Provider (CSP) . CSP , , , , . CSP Windows, Solaris (Intel, Sparc) Linux, Free BSD, AIX. « TLS» TLS -

· «» « »; · «» « »; 30 . 2001 - « , , X.509 CMS», , , . 2002 . . 57 IETF (Internet Engineering Task Force) - (Internet-Drafts) , . . IETF: http://www.ietf.org/internet- drafts/ draft- leontiev- cryptopro- cpcms- 00.txt http://www.ietf.org/internet- drafts/ draft- chudov- cryptopro- cptls- 00.txt http://www.ietf.org/internet- drafts/ draft- leontiev- cryptopro- cppk- 00.txt , CSP : CSP , .

- - , . : · - , , ; · , ; · , . - « ». 2002 / 15, 16, 17. 2003 / 5, 7. 2001 - (http://ca. cryptopro.ru) , . 10 , , , , .

127018, , , 38 : (095) 933 1168 : (095) 933 1168 http://www.CryptoPro.ru E-mail: info@CryptoPro.ru

· RSA Keon 6.5, RSA Security () ; · Unicert 5.1, Baltimore Technologies () ; · , .

· ; · - ; · .

«»
«» -- . «» . , . , «» , - - , , . , , , . «» , , , , - . : · , ; · ; · ; · ; · ; · ; · - ;

«» -- , , , , () , , , , , , , , , «», , , «», «», «», « » . -- , , , , , - , , . , , , . 2 .: (095) 777 7577 () : (095) 777 7576 E-mail: rnt@rnt.ru http://www.rnt.ru

· ; · , ; · ; · ; · . · , ; · , , ; · , , ; · ERP-. , , , .

, , . - (), . , , . .

, : · -; · -. · (ERP), , (EAM) ; · - (ITSM); · ; · . -

, 121609, , , 23. .: (095) 729-51-99, : (095) 729-59-80, e-mail: info@sys.ncc.ru, http:\\www.systematic.ru

«- »
«- » ( ) 1997 . - : · , , , , ( « » «») . · , , - () , . - , , «» ( 484) , «» ( 484) «. » ( 484, 448) . , , , . : · . · - - , . · . VISA MasterCard ( ) , HSM 7000, . (812) 590 7381, (812) 590 7381, E-mail: erkin@nevsky.net, http://www.rczi.spb.ru