wbuzova_umk_met_i_sred_zash_kom_infor_2012
.pdf, -
.
(6.1) . -
p1, p2,..., pk ,
1, a2,..., ak , (6.1)
N p1a1 p2a2 pkak |
(6.2) |
.
- ,
. -
( ). : (a, b) = c, c —
b.
, ,
.
- , -
, . (a, b) = 1, -
m n : (am, bn) = 1.
. a b b > 0 (
(a, b) = (- a, - b), ). -
.
a = bq1 + r2, |
0 < r2 < b; |
|
b = r2q2 + r3, |
0 < r3 < r2; |
|
r2 = r3q3 + r4, |
0 < r4 < r3; |
(6.3) |
. . . |
. . . |
|
rn-2 = br n-1q n-1 + rn, |
0 < rn< rn-1; |
|
rn-1 = rnqn, |
|
|
qi,- , ri - ( 0).
r 2, r 3, . . . ,
. , (a,b) = (a,b) = (r2,b) =(r2, r3) = . . .
= (rn-1, rn) = rn, rn | rn- 1. b
-
.
( ) N1, N2, ..., Nn , .
[N1, N2, ..., Nn].
a,b |
a b |
. |
(6.4) |
|
|||
|
a,b |
|
|
.
(n) -
, n n.
31
|
1, |
n=1; |
|
|
(p-1), |
n=p; |
|
(n) |
( p a p a 1 ), |
n=pa; |
(6.5 ) |
k |
k |
|
|
|
(piai pkai 1 ) ; |
n= pia1 . |
|
|
i 1 |
i 1 |
|
p pi - , a ai - . |
|
||
: |
|
||
1. : |
|
|
|
• b) = ( ) • (b) ( , b) = 1. |
(6.6) |
||
2.
d n n :
(d) = n. |
(6.7) |
d|n |
|
. . . n - . -
b n ,
n.
b (mod n). (6.8)
a b (mod n) n| (a — b) ,
. n n , ,
. a = b ab .
:
1): a b b a;
2): a b, c d a c;
3): a b, c d a ± c b ± d;
4):
a b, c d a • c b • d.
:
5) , -
a • b (b • d)(mod n) a d(mod n) (b, n) = 1;
6) -
, : a b(mod n) a • d (b • d)(modn • d);
n
a • b (b • d)(modn) a d(mod b, n );
7) , -
, : a b(mod n1)
a b(mod n2) a b(mod[nl,n2]);
8)mod n , d
,n: b(mod n); b(mod d), d|n;
32
9)-
: b(mod n), = 1 • d, n = n1 • d b = b1 • d;
:
± b)mod m [ modm ± bmodm]modm ( );
• b)mod m [ mod m • b mod m]mod m ( );
• ( ± b)] mod m [ • mod m ± • b mod m] mod m ( -
).
, n r,
, Zi. , n
n :1, 2,3,..., (n-1).
, n : Z0, Z1, Z2, Z3,
-, Zn-1, n. Zi
, -
N = nq + r ; r < n; q = - «>,...,-2,-1,0,1,2,..., .
10), ,
, ;
11),
;
12).
. . - ,
- . |
|
ap a (modp). |
(6.9) |
p a, |
|
ap-1 1 (modp). |
(6.10) |
. , p a ,
, ) = 1, - 1 , 2 , 3 , . . . , ( - 1) .
p (p | ja , p | j, - p ).
, ) ,
ja k (mod p) j k (mod p). ,
- 1 . , 1, 2, 3, . . . , - 1 -
. ,
-1 1 2 3...(p -1) = • 2 • 3a...(p - 1) (1- 2 • 3...(p - 1))(mod p).
2, 3, . . . , - 1 -
. ,
ap-1 1 (mod p). ap (mod p).
, , | , 0 (mod p), -
, ap (mod p).
-
.
. n > 0 , ( , n) =1.
|
|
(n) = 1 (mod n), |
(6.11) |
(n) - . |
|
||
|
|
. r1, r2, . . . , rk (k = (n)) Z |
|
|
|
n. r1, r2, |
. . . , rk . - |
1, n |
|||
33
, mod n ( ri = rj, -
ri rj (mod n), , n) = 1) ( , n) = ( ri , n) = 1, ri , n) = 1). , (n) -
, n
r1, r2, . . . , rk .
r1 r2 . . . rk ( ar1 r2 . . . rk )(mod n), , ri, -
n, 1 (mod n).
(n) , . (m, n) = 1,
(mn) = (m) (n). , (1) = 1 (2) = 1.
-
, ,
.
. m1, m2, . . . , mr - -
, , : (mi, mj) = 1 i j.
x 1 (mod m1), 2 (mod m2), . . . , (mod m ) |
(6.12) |
- m1 m2. . . mr.
. -
. ki i = 1, . . . , r
m mi. , (ki mi) = 1, k
ni mi. = 1 k1 n1 + 2 k2 n2 + . . . + r r nr
. , m1 n2, . . . , nr k1 n1
1 (mod m1), 1 (mod m1).
.
, .
-
: , -
( ).
,
, , -
.
: 1[123-125]
: 14[348-366]
:
1.?
2.?
3.?
4.?
5.?
6., , -
.
7.?
34
7. . -
. -
.
1970-
. ( ) -
: -
- . -
.
, -
k .
.
-
.
-
7.1.
-
.
, - .
.
; -
. -
,
.
7.1 - -
:
1.-
, .
35
: —> , |
(7.1) |
D : —> |
|
.
. . , -
:
1.( , k )
.
2., ,
= ( ) |
(7.2) |
3. , k , |
|
|
|
= D k ( ). |
(7.3) |
4., ,
k .
5., ( , ), -
.
-
.
:
--
, -
, -
;
--
; -
( N -
2 * N ), ,
;
--
, , -
.
:
;
-, -
,
.
,
;
-.
36
. EIGamal -
. -
k, ( - 1).
= gk mod p, |
(7.4) |
b=yk mod p.
(a,b) . -
. ,b) |
|
= b/ax mod p |
(7.5) |
gkx (mod p) b/ k M/ax gxk M/gkx M (modp), -
.
.
, , -
.
-
, -
.
.
-
:
-Fp, - , > 3;
-F2m.
F .
> 3. ,
Fp, , ), Fp, y F , -
2 3 + ax + b (mod ), |
(7.6) |
a, b Fp 4 3 + 27b2 .
J(E), -
J(E) = 1728 |
4a3 |
(7.7) |
4a3 27b 2 (mod p) |
, b
J( ) :
3k(modp), b 2k(modp) ,
k= |
|
J (E) |
(mod p), J (E) 0 |
1728 |
(7.8) |
||
1728 |
J (E) |
||||||
|
|
|
|
||||
, ), (7.6), -
; - - y .
37
Q( , ) Q.
, |
- y- |
. |
|
F2m |
|
y2 + x3 + 2 + b |
(7.9) |
b.
E(F2m) , ), x F2m,F2m (7.9) b,
.
E(Fp),
E(F2m) -
.
( IEEE 1363).
ECES. ECES (Elliptic Curve Encryption Scheme)
, ,
:
-Fq;
-E(Fq);
-n;
-, ,
n.
-
:
-d, 1 < d<n - 1.
-Q = dP.
d, -
Q.
(
):
-i,
( 2L - 16 , L -
log2 q);
-: mi1 mi2;
-k, 1 < k< n - 1;
-1 ,y2) = k ;
-( 2, 2) = kQB;
-mi1, mi2 2 c1
2;
- : ( 1 , 1, 1 2).
(
):
-2, y2) = d( 1, y1);
-mi1, mi2 c1 2 2.
38
.
- -
, .
,
,
. -
, . -
, -
.
, -
,
, .
: 1[147-151], 3[138 - 162], 4[245-262]
: 13[133-158]
:
1.?
2.-
?
3.-
?
?
5.?
?
7.ECES?
8. ( ).
.
. n -.
( ).
. -
,
.
.
, .
, , -
.
-
.
«
»,
39
, -
. , , -
. -
, :
-( , -
–public-secret);
-,
-
, ;
--
.
-
.
– , , .
-
,
. -
, -
.
o
, :
-- , , -
( ) ;
--
;
-- , ,
;
-- -, ;
-- ,
.
, -
, , -
.
-
-
.
-
:
-, ,
;
40