<4D F736F F D B B BB2D834A836F815B82D082C88C60202D B2E646F63>

Size: px

Start display at page:

Download "<4D F736F F D B B BB2D834A836F815B82D082C88C60202D B2E646F63>"

ゆきさはぎにわ
4 years ago
Views:

2 情報セキュリティの理論と技術サンプルページこの本の定価判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行当時のものです.

4 i IC IC IC IC 5 IC IC IC IC IC IC

5 ii. IC

6 iii a[j] a j a b a b (concatenation) a mod n a n a b (mod N) a b N a b a b a b (a XOR b) a b XOR EOR EXOR a A a A a/ A a A A B A B A B A B A \ B A, B A B A B A B (A AND B) A B A B (A OR B) A B A (NOT A) A A A C deg f(x) f(x) exp x e x F q (GF(q)) q gcd(a 1,a 2,...,a n ) a 1, a 2,..., a n G 1 G 2 G 1 G 2 G 1 G 2 G 1 G 2 G(E/F q ) F q E G G HD(a, b) a b HW(a) a K K K[X] K lcm(a 1,a 2,...,a n ) a 1, a 2,..., a n Len(a) a log x e log c x c N N = {1, 2,...} O f(n) =o(g(n)) lim n f(n)/g(n) =0 f(n) =O(g(n)) C>0 n f(n) C g(n) P(A) A

7 iv Q R Rz z tr(e) E Z Z/nZ n (Z/nZ) n λ(n) ϕ(n) x x x x 0x 16 ( ) m m

8 v AES ALU CBC CFB CMOS CPU CRT CRYPTREC CTR DEAL DES DESX DFA DH DPA DSA ECB ECC EEPROM FA FIB FIPS IC I/O LSB MOS MSB MISTY MAC MIPS NIST NBS nmos NSA NESSIE OAEP OFB PA Advanced Encryption Standard DES Arithmetic and Logic Unit Cipher Block Chaining Cipher FeedBack Complementary MOS Central Processing Unit Chinese Remainder Theorem CRYPtography Research and Evaluation Committees CounTeR Data Encryption Algorithm with Larger Blocks Data Encryption Standard DES extension Differential Fault Analysis Diffie-Hellman Differential Power Analysis Digital Signature Algorithm Electronic Code Book Elliptic Curve Cryptosystems Electrical Erasable and Programmable ROM Fault Analysis Focused Ion Beam ) Federal Information Processing Standards Integrated Circuit Input/Output Least Significant Bit Metal Oxide Semiconductor Most Significant Bit Matsui-Ichikawa-Sorimati-Tokita-Yamagishi Message Authentication Code Million Instructions Per Second National Institute of Standards and Technology National Bureau of Standards n-channel MOS National Security Agency New European Schemes for Signatures, Integrity, and Encryption Optimal Asymmetric Encryption Padding Output FeedBack Physical Analysis Power Analysis

9 vi pmos RAM ROM RSA SCA SHA SPA SSL TA Triple DES p-channel MOS Random Access Memory Read Only Memory Rivest-Shamir-Adleman Side Channel Analysis Secure Hash Algorithm Simple Power Analysis Secure Socket Layer Timing Analysis DES TDES, 3DES

10 vii

12 ix

13 x 4.2 DES DES DES Feistel DES MISTY MISTY MISTY AES AES AES ECB CBC CFB OFB CTR RSA RSA RSA RSA

14 xi p ρ p RSA (1) (2) RSA AES (SPA) (DPA)

15 xii RSA DES RSA DES

18 4.1 a b c d e f g h i j k l m d e f g h i j k l m n o p n o p q r s t u v w x y z q r s t u v w x y z a b c this is a pen. wklv lv d shq. 4.1 wklv lv d shq. this is a pen HAL wklv vjku uijt this sghr rfgq qefp pdeo ocdn nbcm mabl lzak kyzj jxyi iwxh hvwg guvf ftue estd drsc cqrb bpqa aopz znoy ymnx xlmw

19 e 4.1 e ! ( 2 88 )

20 4.2 DES f e d t DES DES (Data Encryption Standard) 1975 NBS (National Bureau of Standards) FIPS-46 (Federal Information Processing Standards) [37] 1977 DES IBM Lucipher

21 62 4. Lucipher Feistel 16 F Feistel F F DES IBM NSA (National Security Agency) NSA DES DES (Coppersmith) 2004 DES AES DES TripleDES 4.4 AES DES DES DES DES DES DES (1) DES DES 4.4 DES IP E S P IP 1 PC-1 PC-2 MSB 1,..., IP 20 FIPS MSB LSB 1

22 4.2 DES L 0 1,..., 32 R 0 33,..., 64 R 0 1 F F 48 RK i (i =0, 1,..., 15) F F 32 R 0 E RK S 1 S 8 S 6 4 S 32 P F F L 0 L L R 0 L 1 = R 0 R 1 = L IP 1 (1111) 2 (0000) 2 = ( ) 2 L 0 R 0 = IP(INPUT) { Li = R i 1 R i = L i 1 F (R i 1,RK i 1 ) { R16 = R 15 (i =1, 2,..., 15) L 16 = L 15 F (R 15,RK 15 ) OUTPUT = IP 1 (L 16 R 16 ) RK j j =15, 14,..., IP 1 IP

23 DES 4.5 DES

24 4.2 DES 65 L 0 R 0 = IP(INPUT) { Li = R i 1 R i = L i 1 F (R i 1,RK 15 (i 1) ) { R16 = R 15 (i =1, 2,..., 15) L 16 = L 15 F (R 15,RK 0 ) OUTPUT = IP 1 (L 16 R 16 ) 4.5 DES PC-1 PC-2 64 MSB 1,..., 64 PC DES 56 PC-1 MSB 1,..., C 0 1,..., 28 D 0 29,..., 56 C 0 D 0 PC PC RK 0 RK i (i =0, 1,..., 15) RK i (i =15, 14,..., 0) DES 4.3 Round #ofleft-rot (2) DES DES 21 8

25 66 4. (a) IP IP IP 4.4 IP IP (b) IP 1 IP 1 IP IP 1 IP IP(IP 1 (x)) = x

26 4.2 DES IP IP 1 (c) E E n n 1 n E

28 RSA RSA (Rivest) (Shamir) (Adleman) RSA 512 p q N = pq = N p q RSA RSA p q (p = q) N = pq n ϕ(n) = (p 1)(q 1) e 31 (e, N) N e 31 ϕ(n) λ(n) =lcm(p 1, q 1)

29 RSA 32 (e, N) N M M N C = M e mod N ed mod ϕ(n) =1 d C d mod N M ed =1+kϕ(N) k C d mod N =(M e ) d mod N = M ed mod N = M 1+kϕ(N) mod N = M (M ϕ(n) ) k mod N = M M C N C d mod N = M d N 32

30 5.1 RSA 107 (Z/N Z) C C d mod N (Z/N Z) (Z/pZ) (Z/qZ) M N M gcd(m, N) =1 N r N r p q N 1 ϕ(n) N =1 (p 1)(q 1) pq = p + q 1 pq 2 N N / RSA S = a d mod N RSA n d (d[n 1]d[n 2] d[0]) 2 (binary) a N d S = a d mod N [STEP 1] S =1 j = n 1 [STEP 2] j<0 S j 0 STEP 3

31 [STEP 3] S = S 2 mod N STEP 4 [STEP 4] d[j] =0 STEP 5 d[j] =1 S = Sa mod N STEP 5 [STEP 5] j = j 1 STEP 2 d =11= (1011) 2 d[3] = 1 d[2] = 0 d[1] = 1 d[0] = 1 a N S =1 j =3 S 1 1 d[3] = 1 S a S = a j =2 S N S = a 2 mod N d[2] = 0 j =1 S S = a 4 mod N d[1] = 1 a S = a 5 mod N S a S = a 11 mod N mod 11 d n S = S 2 mod N n S = Sa mod N d[j] (j =0,1,2,..., n 1) 1 RSA d d[j] 1 n/2 Len(d) S = S 2 mod N S = Sa mod N AB mod N A B N n (Montgomery) AB mod N n 2 n 2 Len(d) Len(d) n n 3 AB mod N

32 5.1 RSA 109 (a) 2 w -ary a(k) =a k mod N, k =1, 2,..., 2 w 1. w =2 a(1) = a mod N, a(2) = a 2 mod N, a(3) = a 3 mod N w n 34 n d w d =(d[(n/w) 1]d[(n/w) 2] d[0]) d[j] w w d = (100111) 2 2 d[2] = (10) 2 =2 d[1] = (01) 2 =2 d[0] = (11) 2 =3 2 w -ary 35 2 w -ary a N d w S = a d mod N [STEP 1] a(j) =a j mod N (j =1,2,...,2 w 1) S =1 j = (n/w) 1 [STEP 2] j<0 S j 0 STEP 3 [STEP 3] S = S 2 mod N w STEP 4 [STEP 4] d[j] =0 STEP 5 d[j] 0 S = Sa(j) modn STEP 5 [STEP 5] j = j 1 STEP 2 STEP 1 RAM (2 w 1) n [bit] 36 STEP w 35 2-ary 2 = bi ) 36 PC RAM IC w

33 w S = S 2w mod N STEP 3 STEP 4 AB mod N AB mod N n/w S = S 2 mod N w w n/w = n 1 n/w N(w, n) ( (w +1)n N(w, n) = = 1+ 1 ) n w w d 0 1 w 0 1/2 w ( N(w, n) = 1+ 1 ( 1 1 )) w 2 w n 1 N(w, n)/n w /24 (= ) 4/3 (=1.33 ) w 37 2 w 1 37 IC

34 5.1 RSA RSA AB mod N IC AB mod N (Sedlak) [50] Radix-4 [53] 1985 (P. L. Montgomery) [34] (1) AB mod N N mod 2 n 181 mod 2 3 =7 181 = ( ) = (1000) = (101) mod 2 3 mod 2 n n RSA N

35 mod N mod 2 n AB + MN = WR (5.1) R =2 n A B N R/2 <N<R M W RSA N N R N (5.1) (5.1) N ABR 1 W (mod N) (5.2) (5.1) n M W M ABN 1 (mod 2 n ) (5.3) M mod 2 n M n W ABR 1 mod N, ABR 1 mod N + N (5.4) A <N B <N M <R N <R AB + MN W = R < N 2 + RN R RN + RN < R =2N (5.4) 38 ABR 1 mod N + N W N 38 N n n N N N

36 5.1 RSA 113 AB mod N ABR 1 mod N Mont(A) = AR mod N Mont(A)Mont(B)R 1 mod N =(AR)(BR)R 1 mod N = ABR mod N =Mont(AB) R 1 mod N A AR 1 mod N ABR 1 mod N B =1 Mont(A) Mont(A)R 1 mod N = A R 2 mod N R 2 mod N =2 2n mod N n = 1024 = n = 2 11 B = R 2 mod N ABR 1 mod N AR 2 R 1 mod N = AR mod N (2) AB + MN = WR R =2 n M 5.3 AB

37 MN 0 M 5.4 W A B N (A =(A[n 1]A[n 2] A[0]) 2 ) W = ABR 1 mod N

39 TripleDES RSA

40 IC 6.1 (physical analysis) IC (side-channel analysis) IC (fault analysis) IC

41 R. (R. Anderson) [4] I (clever outsiders) II (knowledgeable insiders) I I III (funded organizations) III I IC II III I II

42 III IC III 54 IC 6.2 (physical analysis) IC II I (Kömmerling-Kuhn) [22]

43 (layout reconstruction) IC [11] (probe analysis) 0 1 ROM (micro surgery) surgery IC (FIB: focused ion beam) [18]

44 RSA n RSA y x mod N AB mod N n A B N A N B y mod N A x J J {1, 2, 3,...,n} A(J) n T =(A n 1 (J), A n 2 (J),..., A 0 (J)) x T =(A n 1(J), A n 2(J),..., A 0(J)) x T = T S = 1; For j = n-1 down to 0 S = S*S mod N; S = S*y mod N; If S(J) = Aj(J) then x [j] = 1; S = S ; 55 1

45 else x [j] = 0 End If End For x [j] x [j] =x[j] ε >0 j x [j] j 1 x [j 1] j ε =2 J J J 7 ε =2 7 = [18] IC III (1) IC 56 IC 56

46 (2) CPU (3) (4) IC 6.3 (timing analysis)

48 215 2 w -ary 109 AES 88 ALU 11 CBC 100 CFB 101 CTR 103 p , 137 p PKCS 123 ρ 134 RAM 11 ROM 10 RSA Factoring Challenge 142 RSA 105 DEAL 82 DESX 82 DES 61 DES 74 direct amplifier method 131 ECB 100 ECC 145 EEPROM 11 ElGamal 150 EME-OAEP 123 EME-OAEP 123 EME-OAEP 125 Feistel 80 I/O 9 MAC 104 MGF 124 MGF MISTY 82 MOV 146 OFB 102 oscillator sampling method 131 S 68 SSSA 146 T TripleDES (3DES)

49 , , LSB , , , ,

50 j , , , , , , ,

51 , ,

52 c FAX / / TEX / PrintedinJapan ISBN

untitled

untitled API API Part 1 10API 25 10API Part2 Copyright (c) 2004 NPO Page 2 Copyright (C) 2004 NPO JNSA 1 API API Wassenaar API Copyright (c) 2004 NPO Page 4 Copyright (C) 2004 NPO JNSA 2 56 512512 112 IC 1 I II