ВЫСОКОСКОРОСТНЫЕ ГЕНЕРАТОРЫ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ НА ОСНОВЕ КЛЕТОЧНЫХ АВТОМАТОВ

  • Published on
    06-Apr-2017

  • View
    217

  • Download
    3

Embed Size (px)

Transcript

  • 2010

    2(8)

    004.421.5

    .. C

    . .. , . ,

    E-mail: b.sukhinin@gmail.com

    () - . , - , . - , - 25 / 100 .

    : , - , .

    () , -

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

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

    - (., , [3 5]; 3 -. . - ; {0, 1} - . ,

  • 35

    , , - , ; - . , , , , ; - .

    1. 1.1.

    , -

    . .

    f , 2s, s ( ). f , , - , . 0 = /2

    s.,

    , m

    Pr[m = 0] = Pr[m = 1] =1

    2.

    (m) s, m, .

    f , - , f (m),

    Pr[f((m)) = 1] = /2s = 0,

    Pr[f((m)) = 0] = 1 0.

    , m - (m). , - 0 = 1/2, .

    . 1 - . 1 000 - 37 11 9 ( 512). , 0 .

    1.2. [6] 1973 .

    . ,

  • 36 . . C

    . 1. -

    .

    -, . - MX MY . m(x,y) (x, y). , ,

    m(x,y) m((x mod MX),(y mod MY )).

    -.

    - . - (m(x1,y1),m(x2,y2)) m(x1,y1) m(x2,y2)

    (m(x1,y1),m(x2,y2)) = max(

    min(|x1 x2| ,MX |x1 x2|),min(|y1 y2| ,MY |y1 y2|)

    ).

    ,

    max = max

    (MX 1

    2

    ,

    MY 1

    2

    ).

    , . . MX MY ( , MX > MY ), . mt(x,y) (x, y) t; mt(x,y). t = 0 (0, 0) :

    m0(0,0) 1 m0(0,0)

  • 37

    ( , ).

    , . : . - ( ) , .

    (t) - :

    (t) =

    06x

  • 38 . . C

    . 2.

    . 3.

    1.3. .

    , - , . - ; .

    , :

    m(x,y) = m((x+TX),(y+TY )),

    TX 6 MX TY 6 MY . , , . TX TY ; .

  • 39

    . . 4 , 300 . , - 4 , . , , - .

    . 4.

    2. 2.1.

    , , . 5. ().

    De_lhqgucZ\lhfZl1

    JKEHK

    De_lhqgucZ\lhfZl2

  • 40 . . C

    2 - (34, 9). , - . , 63, 263 1 9,2 1018 ; - 32 8 (263 1) 2,4 1021 . .

    2 - , , -, - .

    2.2.

    - Altera Cyclone II (EP2C35F672C6); . 6. , . - .

    De_lhqgucZ\lhfZl1

    JKEHK

    De_lhqgucZ\lhfZl2

    IZfylvgZ

    djbklZee_

    IEBK

    Dhgljhee_j

    UART

    =_g_jZlhjIKIFbdjhko_fZIEBK

    256

  • 41

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

    -

    -, . - NIST, . - 25 /.

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

    1. Farmer D., Toffoli T., Wolfram S. Preface to Cellular Automata // Proceedings of an

    Interdisciplinary Workshop. Los Alamos, New Mexico, 1984. P. viixii.2. ., . . .: , 1991. 280 .3. Wolfram S. A New Kind of Science. Wolfram Media, 2002. 1192 p.4. Wolfram S. Cellular Automata // Los Alamos Science. 1983. No. 9. P. 221.5. Wolfram S. Cryptography with Cellular Automata // Proceedings of CRYPTO85. 1986.

    P. 429432.6. Feistel H. Cryptography and Computer Privacy // Scientific American. 1973. V. 228. No. 5.

    P. 1523.7. http://csrc.nist.gov/publications/nistpubs/800-22-rev1/SP800-22rev1.pdfNIST

    SP 800-22. A Statistical Test Suite for Random and Pseudorandom Number Generators forCryptographic Applications, revision 1.

Recommended

View more >