__________________________________
" "
,
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 * *
() ......... .
,
.............................. ( - ),
,
;
-
;
,
;
-
, --
;
, -
, , -
,
:
I.
() ,
() .
II.
,
() , -
-
() ,
.
III.
-
,
() ,
............... .
,
............................ , -
, -
() , -
, .
............................
.
-
.................
, , -
.
IV.
, ,
.
.
() -
,
.......................... .
V.
... ,
, , -
.
..........................
.
___________________________________________________
__________________________ (_____________)
..
___________________________________________________
__________________________ (_____________)
..
. . . . . . . . . . . . . . . . . . . . . . . . .
, ,
, -
-
.......................... .
1.
,
, ,
(
),
.
,
, -
-
,
.
2.
- (
), -
.
.58
/1/ ,
, ,
. ,
,
-
,
.
____________________
/1/ 31 1991 . (-
.
1991. N 26. .733). -
14 1992 . " -
-
" (
.
1992. N 30. .1800)
3 1992 . ( -
).
, ,
. -
, , -
, , ,
.., , (.2 .58
).
-
.
-
, --
, ,
, -
. ,
, .
-
, , , -
.
1974
, -
-
, -
- ./1/ .2 -
,
, ,
,
- .
, ,
--
, -
, .
____________________
/1/
29 1979 . N -1-4 " -
,
- .// -
. . 1989. .47-49.
, --
-
( , ..). -
-
, .9
29 1979 . N -1-4, , -
(, , -
, ..),
,
,
. ,
, :
,
,
,
,
, .
3. , ,
:
3.1. .6 -
, ,
, .
4 1991 . " -
"/1/ , -
, -
( ) -
( ).
.1 .20 -
/2/
, , , -
, -, -
( -
), -
, -
. , -
... ,
.
, .7
.27
,
,
,
_______________________________
1.
. 1991, N30, .1013;
. 1992, N34, . 1965. (
).
2. 5 1992.//
.1991, N16, .836. ( - )
. , -
,
(.157).
3.2.
.7 ,
..21 157 ,
, -
24
1992. /1/ .2 -
, -
.
.
,
, ,-
, , , -
,
, , , , -
, , -
,
.
, ,
(, , ,
,
) , , -
.
-
(.. , -
()
).
, -
, , -
, .
_________________________________
1. -
.1992, N30,
.1790. ( - ).
3.3. ,
V .157
. -
:
-, .2 .157 .25 -
-
-
, -
,
;
-, .5 .157 .26 -
,
:
)
;
).
-
;
). , -
, -
;
). -
.
, -
. ,
.3 .26 -
, -
-
,
, ,
.
3.4.
:
3.4.1. ...
,
. ,
... -
....
-
,
... , .. -
, -
, .
3.4.2. ,
... , .3.4.1 -
.... .7 , .21
.3
.
, -
.
, ,
.
,
... ,
, . 3.4.1.
... ,
(..
).
-
,
( )
.
, ..
.
, :
,
. -
,
, ,2
.
4. , -
... :
1) ;
2) , . 3.4
.
()
........................ .
I. .
1. (-
) -
, , .......
........................ , -
.
2. ()
,
.
.
3. -
:
.
,
,
( ), ,
, -
.
,
" " , , -
-
.
: - -
( ),
.
4. ()
( - ) -
() .
, ( -
), .
..................
.............. , .
5.
.
-
, .
II.
6. :
- (
);
-
;
-
;
- -
;
-
,
(
, );
- -
-
,
;
- -
(
) -
;
7. :
- , -
-
;
- ,
(
,
,
..);
- ,
-
;
- -
-
;
-
, -
;
- -
,
, -
-
, ;
-
, -
;
-
;
-
;
- -
.
- -
.
III.
8. ,
:
- ,
, , -
-;
-
, ,
;
-
;
-
;
-
;
: , -
:
- ;
- ;
- (
) ()
(
);
- ,
.
9.
, -
, ,
, - -
.
,
,
/ -
.
IV.
10. , -
, -
, :
,
-
;
;
-
, , ,
,
,
, -
-
, ,
, , -
-
.
11. ,
,
, , :
, ,
, -
;
-
, -
,
,
.
, :
-
-
;
, -
, - , -
,
;
- -
-
.
Last-modified: Fri, 11 Jul 1997 07:02:18 GMT