__________________________________ " " , 1993 . ----------- 1. ................................ 2. ................................ 3. ........ 4. ..................................................... 1. " " --------------------------------- 60-70 , . - . - . 1977 " " , , " ". - , () , () , - . "" - - "" - , . - - , - - - . - . 2. -------------------------------- - RSA, 1977 - : R.Rivest, A.Shamir, L.Adleman. - . - "" M. ("-") - ., " " . "" d n, ..,: d S = mod n - [M,S]. d. - e, e ? S = M mod n . , S - d, e d , n. n , 150-170 . "-" , RSA. . El Gamal T., A public-key cryptosysems and signature schme based on discret logarithms,IEEE Trans.Inform Theory, v.31 N4, pp. 469-472 (1985). - 4 , 1000 . 3. ----------------------------------------- - . . .- .., 1976 . x f(x) = a (mod p) , - , . - , , f(x), - . X X , a (mod p) . . - . . - Y . Y - . X Y , - . X Y X Y . , . , Y YX , . XY a , . . X X |X|->a -------------------------------------> a Y Y a <------------------------------------- a <-|Y| Y | YX| X | XY| |X|+a ->|a | |Y|+a ->|a | , , - . - , . RSA. " " RSA , . - RSA , - . , RSA , , - . - . - . , - ! RSA RSA . RSA - . , ! "-" - 1000 RSA. () "-" 200/. -286, DES. . 4. ------------------------------------------------------ ------------------------------------------- N+1 : N - . i = 1, 2,..., N. . (, ..). . - . . - . I . . II . () - . X Y . XY III . . XY IV . . V . . +====================+ +========================+ II . +-+ +-+ I I I I | |->| | I I I I +-+ +sign I I I I I I I III . X I I X II .I I X->a ------------------------> a I I Y I I Y I I a <------------------------ a <-Y I IIII . I I III .I I +-----+ I I +-----+ I I+-+ |+-+ | I I |+-+ | I I| |----->|| | |------ ---------------->|| | | I I+sign | |+sign| I I |+sign| I I | +-----+ I I +-----+ I I XY I I | IV .I I a I I | - XYI I I I | a I I I I | I I I I | I I I I +-+ | +-+ I I I I | |------>| | I I I I +sign +-+ I +====================+ +========================+ - . . , i x Xi . - , . , , . i +---+ +---+ +---+-+ Xi | Xi| | Xi| Xi | X1| | Xi->a ->|a |---------------------------->|a |--->a -->|a |1| | +-sign +-sign | | X2| | | | |a |2| |: |:| |: |:| | XN| | |a |N| +---+-+ | ----->| | +-------+ ----------------------|+---+-+| ----------------------|| X1| || ----------------------||a |1|| ----------------------|| X2| || ----------------------||a |2|| ----------------------||: |:|| ----------------------||: |:|| ----------------------|| XN| || ----------------------||a |N|| ----------------------|+---+-+| ----------------------+--sign-+ ||||||||| ||||||||| ||||||||| ||||||||| , - j, i - Xj j - Xj XiXj Xi . i . - XiXj i j . , , . j . , j, - , . - - XY (. " - "). , j . . , i, , , - . j , j. i, XiXj XiXj a . i XiX1 XiX2 XiXN N-1 , , ... ,a . - , . . i j : | * * * | i | * * * | s | * * * | j | j | i - , ( i) j - , ( j) j - j S - , i j j * - . , S i j, , j, . " j" - . | * * * | i | * * * | s | * * * | j | j | | i | " j" - | | | * * * | i | * * * | s | * * * | j | j | k | | | | i | | XY | (. " - | -.") | | XY a | * * * | i | * * * | s | * * * | j | j | k | sign | | | XY | , | . | | | * * * | i | * * * | s | * * * | j | j | k | | | | i - | Z W, - | | Z W | . - | ZW | . | | ZW | , - | j. | ZW a | * * * | i | * * * | s | * * * | j | j | k | sign | | | j - | ZW | , , - | i, - | , | XiXj | , - | | " j" | +---------------------+------------------------+ | * * * | i | * * * | s | * * * | j | j | +----------------------------------------------+ i Xi, j. i j , - . - - i j. " ", - , ., 37 - , . . " " " ". . - [ ] - , . , , , , . , , - , " " , - . - . . " " 1. () ............. 4 1.1. RSA....................................... 5 1.2. ................................ 7 1.3. " "................... 9 1.4. ..............11 2. ................................13 2.1. DES....................................14 2.2. 28147-89.........................15 2.3. "".....................16 2.4. .....................17 3. ........................19 3.1. - .........................20 3.2. .........................21 3.3. ""............22 3.4. ................................23 ..............................................24 ..............................................25 . " "...........................26 . "H "...29 . ...........35 . ..........40 . .....................47 1. () . . . [ 1 ] 1976 . , . , , , ( ), - , , - , -, . , - (, , ...) , . , , .. . , - " ", , - , , - . " " - . , - - ( " ") - - . 1.1. RSA. " RSA", 1977 - () - : R.Rivest, A.Shamir, L.Adleman [ 4 ]. , , n, , n = P*Q, e, d, 1