http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/
1 1 2011.9.29, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 1.1 1.1.1 DES MISTY AES 1.1.2 RSA ElGamal
2 1 1.2 1.2.1 1.2.2 1.3 Mathematica Mathematica Windows > > ( ) Mathematica 1.3.1 Mathematica file>open( new) ( ) Shift Enter 1 (1). 2 + 3 (2). 3 6 (3). 3 2
1.3. Mathematica 3 (4). sin π 4 In Out [ ] In[1]:= 2+3 Out[1]= 5 In[2]:= 3^6 Out[2]= 729 In[3]:= 3/2 3 Out[3]= - 2 In[4]:= Sin[Pi/4] 1 Out[4]= ------- Sqrt[2] 2 Mathematica ( ) (1). 30 (2). 27 11 ( 27 (mod 11) ) (3). 13 19 (mod 23) (4). 23x (mod 7) = 1 (23x 1 (mod 7) ) (5). 5040 (6). 45 ( 1 ) 45 In[5]:= Prime[30]
4 1 Out[5]= 113 In[6]:= Mod[27,11] Out[6]= 5 In[7]:= PowerMod[13,19,23] Out[7]= 2 In[8]:= PowerMod[23,-1,7] Out[8]= 4 In[9]:= FactorInteger[5040] Out[9]= {{2, 4}, {3, 2}, {5, 1}, {7, 1}} In[10]:= EulerPhi[45] Out[10]= 24 ( ) PowerMod[13,19,23] Mod[13^19,7l] PowerMod[13,19,23] PowerMod[23,-1,7] 23 5040 = 2 4 3 2 5 1 7 1 EulerPhi[45] φ(45) 1 (1). 200 (2). 13902 458 (3). 3493 234567 (mod 631) (4). 163x 1 (mod 17) (5). φ(40320) 1.4 ( )
1.5. 5 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 + 96 97 98 99 - = % ( ) 69 ( ) 12 30131612 1.5 1 3 (1). 4 (2). 25662197 (3). (4). 36265117, 64165210 (a) 4 (b) 4 [ ]
6 1 (c) 36 (5). 36265117 25662197 3 + 2 = 5, 6 + 5 = 1, 2 + 6 = 8, 6 + 6 = 2, 5 + 2 = 7, 1 + 1 = 2, 1 + 9 = 0, 7 + 7 = 4 51827204 64165210 89727307 (6). (51827204, 89727307) 1.5.1 4 ( ) 4, 2
7 2 2011.10.5, http://www.ss.u-tokai.ac.jp/ mahoro/2010autumn/crypto/ 2.1 2.2 ( 86 ) ( 3 ) A 1 B 2 C 25 Z ( ) 2 C C 2 A 6 6 6 ( )
8 2 2.2.1 26 19, 1, 4, 12, 14 ANGOU A 19 T N O G K O A U I TOKAI TOKAI ANGOU 5 TOKAI BOSEI TOKAI 18, 0, 18, 22, 0 2.2.2 20 190 (1). (2). (3).
2.2. 9 (4). 2.2.3 (1). 4 (2). 29 (3). 4 (4). 4 (1). 4 4971 (2). 4971 29 = 144159. (3). 144159 4 4159 (4). 4159 4971 4 29 4 4159 29 2069 = 60001.
10 2 2.2.4 29 4 2069 4 5 (1). 4 4971 29 4971 29 = 144159. (2). 144159 4 4159 2069 144159 2069 = 298264971. (3). 4971 4 4971 4971 29 2069 = 4971 60001 = 298264971. 4971 60001 4 4 4 9 7 1 2 9 4 4 7 3 9 9 9 4 2 1 4 4 1 5 9 1 4 4 1 5 9 2 0 6 9 1 2 9 7 4 3 1 8 6 4 9 5 4 2 8 8 3 1 8 2 9 8 2 6 4 9 7 1 144159 4 4159 144159 2069 = 298264971 4 4971
2.3. 11 2011.10.12, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 2.3 2.3.1 (1). (2). (3). 2.4 1 ( ) m, a, b q 1, q 2 0 r 1, r 2 < m { a = mq1 + r 1, b = mq 2 + r 2. r 1 = r 2 a b (mod m).
12 2 a b m ( ) m a b (mod m) a b m 6 { 31 = 13 2 + 5, 34 = 13 ( 3) + 5. 31 34 (mod 13). 31 ( 34) = 65 = 13 5. 2.5 Z/NZ 2 (Z/NZ) N Z/NZ = {0, 1, 2,, N 1}. 3 (Z/NZ ) Z/NZ x, y Z/NZ x + y x, y x + y N x, y Z/NZ xy x, y xy N 2.6 Z/NZ 7 Z/5Z 4 ( ) N φ(n) 1, 2,, N N ((a, b) = 1 a, b )
2.6. Z/NZ 13 2.1: 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 1 p n φ(p n ) = p n p n 1. ( ) 1 p n p p φ(p) = p 1 2 a, b (a, b) = 1 φ(ab) = φ(a)φ(b). ( ) p p, q φ(pq) = (p 1)(q 1) 3 N a Z/NZ. ax = 1 a φ(n) 1 ( ) N a N Z/NZ a φ(n) = 1.
14 2 2.6.1 RSA (1). p, q: (2). m = pq (3). φ(m) = (p 1)(q 1) (4). e: φ(m) (5). (m, e): (6). d: (ed 1 (mod φ(m)) d ) (7). M: ( ) (8). C = M e : 2.6.2 Mathematica (1). p = Prime[100], q = Prime[134] (100 134 ) (2). m = pq (3). n = (p 1) (q 1) (4). e: n (5). (m, e): (6). PowerMod[e, 1, n]: ( d ) (7). M: ( ) (8). PowerMod[M, e, m]: ( C ) 2.6.3 C d = (M e ) d = M ed = M 1 = M.
2.6. Z/NZ 15 2.6.4 Mathematica (1). M = PowerMod[C, d, m] 3 p = 233, q = 239, e = 101 d 2.6.5 RSA 4 [ ( )] N φ(n) 1, 2,, N N ((a, b) = 1 a, b ) 1 [ ] p n φ(p n ) = p n p n 1. 2 [ ] a, b (a, b) = 1 φ(ab) = φ(a)φ(b). ( ) p, q φ(pq) = (p 1)(q 1) 3 [ ] N a Z/NZ. ax = 1 (a, N) = 1 a φ(n) 1 [ ( )] N a N Z/NZ a φ(n) = 1. 4 p, q a Z/pqZ, a 0 n Z a nφ(pq)+1 = a
16 2 2.7 p, q M e φ(pq) = (p 1)(q 1) (m, e) = (pq, e) d x, y ex + φ(pq)y = 1 x (pq, e) d d 0 a Z/pqZ a ed = a ( y)φ(pq)+1 = a C = M e C d C d = (M e ) d = M ed = M 2.8 RSA RSA (m, e) = (pq, e) d m = pq pq m (m, e) d x, y ex + φ(pq)y = 1 φ(pq) φ(pq) = (p 1)(q 1) p, q m = pq m RSA
2.9. (Z/NZ) 17 2011.10.19, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 2.9 (Z/NZ) 1 N (Z/NZ) := {a Z/NZ (a, N) = 1} Z/NZ Z/NZ ( ) a, b Z/NZ (a, N) = 1 (b, N) = 1 (ab, N) = 1 1 Z/NZ (1, N) = 1 1 (Z/NZ). a Z/NZ ax + Ny = 1 a 1 (Z/NZ) Z/NZ 2 ( ) G n G x e G x n = e 1 p, q (Z/pqZ) x x φ(pq) = x (p 1)(q 1) = 1. ( ) (Z/pqZ) φ(pq), 1 2
19 3 2011.10.26, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 3.1 3.2
20 3 3.3 8 ( ) ( ) 9 ( ) ( ) (Word ) 10 ( ) 11 ( ) 3.4 ID
3.4. 21 3.4.1 ( ) 1bit 12 ( ) ID ID 4 5 3.4.2 MD-4 128 bit
22 3 MD-5 128 bit SHA-1 2 64 bit 160 bit SHA-256 2 64 bit 256 bit SHA-384 2 64 bit 384 bit SHA-512 2 64 bit 512 bit 3.5 3.5.1 ( 1) (1). K (2). ( ) r (3). r K t = C K (r) (4). t r ( 2) (1). K (2). ( ) r r K X = C K (r) (3). t r r r t = C K (r ) (4). t r r
3.6. MD5 23 2010.11.9, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 3.6 MD5 md5make MD5 3.6.1 MD5 (1). URL md5make http://www.vector.co.jp/soft/win95/util/se136327.html (2). md5make108a.lha ( Lhaca ) (3). ReadMe.txt (4). http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ crypto2008.pdf.lha (5). crypto2008.pdf.lha crypto2008 crypto2008.pdf, crypto2008.pdf.md5 2 (6). md5make.exe ( md5make ) (7). crypto2008.pdf *.md5 MD5 (8). crypto2008.pdf crypto2008.pdf.md5 crypto2008.pdf (9). crypto2008.pdf.md5 (16 32 ) Web
24 3 ( ) [MD5 ] MD5 MD5 SHA-1, SHA-256 ( ) MultiHasher MD5 SHA- 1 (1). URL MultiHasher_1.1_win32.zip http://www.abelhadigital.com/multihasher DOWNLOAD(Zip version) Mirror 1 (2). MultiHasher_1.1_win32.zip (3). MultiHasher.exe (4). Help 3.6.2 3.7 3.7.1 RSA (1). (e, m) d (2). M M d C (3). C e
3.8. man-in-the-middle 25 (4). M C ( ) RSA 6 RSA (e, m) = (34987, 262142950270493) = 1113 =4811318084824 3.8 man-in-the-middle 3.8.1 man-in-the-middle (1). A B K (2). C A B C B (3). C B A ( C ) (4). A A 3.9 man-in-the-middle
26 3 3.9.1 (1). A (e A, m A ) CA (2). CA A (e A, m A ) (3). CA (e CA, m CA ) d CA (4). CA (e A, m A ) d CA P KC A (5). B CA P KC A e CA (e A, m A ) ( )
27 4 2011.11.23, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 4.1 ( ) ( ) 13 (RSA ) RSA p, q m = pq e p, q, e p, q 4.2 ( ) ( ) ( )
28 4 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 1 4.3 4.3.1 (1). a, c, m Z (2). r 0 := a + c (mod m) (3). r n+1 := a r n + c (mod m) 4.3.2 (1). (2). (3). 1 (4). (2)
4.3. 29 4.3.3 (1). (2). (3). (4). 1 (5). (2)
31 5 2011.11.30, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 5.1 ( ) ( ) 5.2 ( ) ( )
32 5 ( ) 5.3 5.3.1
5.3. 33 5.3.2 IC X
35 6 2011.12.7, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 6.1 n n 6.1.1 1 n n 6.1.2 ρ (1). f(x) (2). x 1 (3). x i+1 = f(x i ) (mod n) (4). GCD(n, x 2i x i ) n 14 n = 2201 ρ f(x) = x 2 + 1. x 1 = 1 x 2 = 2, x 3 = 5, x 4 = 26, x 5 = 677, x 6 = 522, x 7 = 1762, x 8 = 1235. GCD(n, x 8 x 4 ) = GCD(2201, 1235 26) = 31.
36 6 2201 = 31 71. n 1 n n n ρ f(x) n x 2i x i f(x) x 2i x i 6.2 Z/NZ 5 ( ) G. G H G H a G a := {a n n Z} a 5 p Z/pZ (Z/pZ) a (Z/pZ) (Z/pZ) = a a 15 p = 7 a = 3 3 = {3 0 = 1, 3 1 = 3, 3 2 = 9 = 2, 3 3 = 27 = 6, 3 4 = 81 = 4, 3 5 = 5, 3 6 = 1} (Z/7Z) = 3 3 2 ( ) G G G e a G a G = e 16 ( ) p (Z/pZ) = p 1 (a, p) = 1 a p 1 1 (mod p).
6.3. 37 6.3 p 1 (p 1 ) (1). n (2). n n = pq, p,q > 1, Q (3). M = (p 1)m (p 1) (4). (a, n) = 1 a (a, p) = 1 a p 1 1 (mod p) (5). a M = a (p 1)m = (a p 1 ) m 1 m = 1 (mod p) (6). a M 1 0 (mod p) a M 1 p (7). M (n, a M 1) p n ( ) 17 p 1 p 1 (1). n = 2201 (2). a = 2, M (3). (n, a M 1) (4). (n, a 2! 1) = (2201, 3) = 1, (n, a 3! 1) = (2201, 63) = 1, (n, a 4! 1) = (2201, 16777216) = 1, (n, 2 2 5 1) = (2201, 1023) = 31. (5). 2201 = 31 71. 2201 = 31 71 p = 31 p 1 = 31 1 = 30 = 2 3 5 M = 2 5 = 10 p 1 = 30 M p 1 (n, a M 1) a M 1 (n, a M 1) = (n, a M 1 (mod n)) n 7 36863 p 1 a = 2, M 2!, 3!, 4!,
38 6 6.3.1 2 (1). m n (2). Q(x) := (x + m) 2 n (3). x = ±1, ±2, Q(x) (4). Q(x) x (5). Q(x) (6). t 2 Q(x) (7). s 2 (x + m) 2 (8). s 2 t 2 (mod n) (9). GCD(n, s ± t) n 18 n = 2201 2 n = 46.9148 m = 46. Q(x) := (x + 46) 2 2201 Q(1) := (1 + 46) 2 2201 = 8 = 2 3. Q(3) := (3 + 46) 2 2201 = 200 = 2 3 5 2. Q(1)Q(3) = 2 3 2 3 5 2 = (2 3 5) 2 = t 2. (1 + 46) 2 (3 + 46) 2 = 47 2 49 2 = s 2. GCD(n, s t) = GCD(2201, 2263) = 31. 2201 = 31 71.
6.4. 39 2011.12.14, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 6.4 12 19 mahoro@tokai-u.jp 24
40 6 6.5 ρ (1). p n (2). x 1, x 2,, x p, x p+1 mod p Z/pZ p x i, x j x i x j (mod p) i < j. (3). k = j i x i+1 x 2 i + 1 x 2 j + 1 x j+1 (mod p) x i+1 x j+1 (mod p) x i+t x j+t (mod p) (t = 1, 2, 3, ) (4). i kl l x kl x kl+k x kl+2k x kl+kl x 2kl (mod p) m = kl x 2m x m (mod p) (5). p m (6). x 2m x m 0 (mod p) GCD(n, x 2m x m ) p n n (7). x 2m x m n
6.6. 2 41 6.6 2 19 n = 29737 2 [ ] m = 29737 = 172 Q(x) := (x + 172) 2 29737 [Q(x) ] x 1 2 3 7 11 31 1 0 6 1 0 0 0 1 1 4 0 0 0 1 2 0 0 0 2 1 0 2 1 0 3 0 0 1 [Q(x) mod 2 ] x 1 2 3 7 11 31 1 0 0 1 0 0 0 1 1 0 0 0 0 1 2 0 0 0 0 1 0 2 1 0 1 0 0 1 Q(x) mod 2 mod 2 0 1 1 1 2 3 7 11 31 1 2 3 7 11 31 0 6 1 0 0 0 0 0 1 0 0 0 1 4 0 0 0 1 (mod 2) = 1 0 0 0 0 1 0 0 0 2 1 0 0 0 0 0 1 0 1 0 3 0 0 1 1 0 1 0 0 1 1 + 2 + 4 = 0 0 0 0 0 0 Q(1)Q( 1)Q( 2) = 5142528 = 8928 2 = t 2 Q(1), Q( 1), Q( 2) (1 + m) 2 (1 + 172) 2, ( 1 + 172) 2, ( 2 + 172) 2 s 2 = (1 + 172) 2 ( 1 + 172) 2 ( 2 + 172) 2 = 5029110 2 gcd(s t, n) = 131 gcd(s + t, n) = 227 n n = 131 227
43 7 2010.12.21, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2010autumn/crypto/ 7.1 g 2 x a = g x g a x x = log g a (a log g a ) x x ( ) g 2, p x a = g x (mod p) g x p p a p x a Ind x x = Ind g a (mod p) mod p g, a x
44 7 7.1.1 ElGamal p g (Z/pZ) g = (Z/pZ) a (Z/pZ) g x = a x x g, a x = Ind g a (Z/pZ) (mod p) g, a x [ ] (1). p, g, x, (0 < x < p) (2). (Z/pZ) (3). h = g x (4). (p, g, h) x [ ] (1). m m p (2). r, (0 < r < p) (3). c 1 = g r, c 2 = mh r (4). (c 1, c 2 ) [ ] (1). c 2 (c x 1) 1 m (2). c 2 (c x 1) 1 = mh r ((g r ) x ) 1 = mh r ((g x ) r ) 1 = mh r (h r ) 1 = m Elgamal g, h h = g x x