2011 11 16 ( ) 2011 11 16 1 / 30
1 UTF 10 2 2 16 2 2 0 3 Youtube ( ) 2011 11 16 2 / 30
4 5 ad bc = 0 6 7 (a, b, a x + b y) (c, d, c x + d y) (1, x), (2, y) ( ) 2011 11 16 3 / 30
8 2 01001110 10100011 ( ) 2011 11 16 4 / 30
01001110 + 10100011 11101101 mod 2 11101101 + 10100011 01001110 8 2 ( ) 2011 11 16 5 / 30
2,000 ( ) ( ) 2011 11 16 6 / 30
( ) 2011 11 16 7 / 30
( ) https ( ) ( ) 2011 11 16 8 / 30
p p 0 1, 2,..., p 1 p p = 11 11 2 2 2, 4, 8, 5, 10, 9, 7, 3, 6, 1 0 10 p = 7 2 2, 4, 1 6 3 3 3 3, 2, 6, 4, 5, 1 6 ( ) 2011 11 16 9 / 30
p p x x, x 2, x 3,..., x p`1 = 1 1, 2, 3,..., p 1 ( 1 x ) x k p 1 x k(p`1) = (x p`1 ) k = 1 p a p a p`1 1 (mod p) Fermat p = 6, a = 5 5 5 5 (mod 6) p = 6 ( ) ( ) 2011 11 16 10 / 30
n 1, 2, 3,..., n n φ(n) n = 20 1, 3, 7, 9, 11, 13, 17, 19 φ(20) = 8 n 1, 2,..., n 1 n φ(n) = n 1 p a p a p`1 1 (mod p) n a n a (n) 1 (mod n) n = 20 a = 3 3 8 1 (mod 20) ( ) 2011 11 16 11 / 30
Euclid n, m n < m n, m 1 n = 0 m 2 m n m 0 m, n n, m 0 (1) m, n d mx + ny = d x, y m, n d = 1 mx + ny = 1 x, y ( ) 2011 11 16 12 / 30
n = 39, m = 171 171 39 = 4 15, 39 15 = 2 9, 15 9 = 1 6, 9 6 = 1 3, 6 3 = 2 0 3 m, n ( ) 2011 11 16 13 / 30
171 39 4 = 15, 39 15 2 = 9, 15 9 1 = 6, 9 6 1 = 3, 6 9 15 39 22 171 5 = 3. ( ) 2011 11 16 14 / 30
RSA Rivest, Shamir, Adleman 3 1977 1 ( ) p, q 2 n = pq, L = (p 1)(q 1) 3 L L e 4 de 1 (mod L) d (3) (4) Euclid (e, n) d ( ) 2011 11 16 15 / 30
n = pq, L = (p 1)(q 1), de 1 (mod L) n M M e (mod n) n = pq 1, 2,..., n n p q q p 1 p + q 1 φ(n) = pq p q + 1 = (p 1)(q 1) = L a n = pq a L 1 (mod n) ( ) 2011 11 16 16 / 30
n = pq, L = (p 1)(q 1), de 1 (mod L) mod n d M M n = pq M L 1 (mod n) de = Lt + 1 (t ) M de (M L ) t M M (mod n) M e d d ( ) 2011 11 16 17 / 30
n = pq, L = (p 1)(q 1), de 1 (mod L) M n = pq M p, q p M q M q`1 1 (mod q) de = Lt + 1 M de (M q`1 ) (p`1)t M M (mod q) M de M p, q M de M (mod n) d d ( ) 2011 11 16 18 / 30
d e d e e = 1000 e = 512 + 256 + 128 + 64 + 32 + 8 2 e = 1111101000 M M 2, M 4, M 8, M 16,... M 1000 = M 512 M 256 M 128 M 64 M 32 M 8 e = 65537 = 2 16 + 1 ( ) 2011 11 16 19 / 30
p, q p = 11, q = 13 n = 11 13 = 143, L = 10 12 = 120 e = 7 7d 1 (mod 120) d = 103 M = 9 M 7 4782969 48 (mod 143) 48 103 9 (mod 143) M ( ) 2011 11 16 20 / 30
n M e n = pq L = (p 1)(q 1) de 1 (mod L) d n = pq n ( ) p, q (n ) n = pq M e M ( ) ( ) 2011 11 16 21 / 30
( ) p, q p 2002 Agrawal, Kayal, Saxena 3 ( ) 2011 11 16 22 / 30
Fermat p p p 0 ( ) 2011 11 16 23 / 30
( ) ( ) 2011 11 16 24 / 30
( ) x f ( ) f(x) 2 1024 ( ) 1 f(x) 2 y f(x) = y x 3 x 1, x 2 f(x 1 ) = f(x 2 ) ( ) 2011 11 16 25 / 30
RSA RSA M e d M ed M (mod n) M d M d e M de M d M m = f(m) m e M f(m) m de ( ) 2011 11 16 26 / 30
Diffie-Hellman p p {1, 2,..., p 1} = {x, x 2,..., x p`1 } x x p 2 k y = x k p 2 r x r y y r = x kr x r k x rk ( ) 2011 11 16 27 / 30
p x, x k x r k x kr mod p x y y = x k k x, y 1, 2,..., p 1 ( p x ) ( ) 2011 11 16 28 / 30
p = 11 x = 2 {x, x 2, x 3,..., x 10 } {1, 2,..., 10} k = 4 2 4 5 (mod 11) r = 6 2 6 9 (mod 11) 9 4 5 (mod 11) 5 6 5 (mod 11) ( 5 ) ( ) 2011 11 16 29 / 30
( ) / ( ) / ( ) 2 ( ) 2011 11 16 30 / 30