Transcription

1 IMES DISCUSSION PAPER SERIES Discuss ssion Paper No. 97-J-11 INSTITUTE FOR MONETARY AND ECONOMIC STUDIES BANK OF JAPAN

2

3 IMES Discuss ssion Paper Series 97-J JEL : L86, Z00 * ** ( sakurai@csce.kyushu-u.ac.jp) NTT

4 ... 1 I (1)... 5 (2)... 5 (3)... 8 (4) (1) (2) II (1)RSA (2)Rabin (3) (1)ElGamal (2)EDLP DL (3)OAEP (4) (1)ElGamal (2)ESIGN (3)DSA (4)Fiat-Shamir (5)EDLP (6) III FP (1) (2)... 59

5 2 DLP, EDLP (1) (2) (3)EDLP

6 1 PGP(Pretty Good Privacy) RSA [1997] 1

7 2

8 I 1 common key cryptosystem public key cryptosystem 1976 Stanford Diffie and Hellman[1976] n C 2n n 2 LSI Mbps Mbps 3

9 M e E(e,M) d D(d,M) e E(e,M) d D(d,M) d e E C=E(e,M) M 2 M D(d,E(e,M))=M M E(e,D(d,M))=M ElGamal ESIGN one way function f f -1 C=f(M) f -1 (C) trapdoor trapdoor one way function f(,e) 2 4

10 f -1 (,d) d e d e d 2 (1) 1. A B M Step 1 Step 2 A B e B M C B B d B C M B A B B B (2) 1 D(M) 5

11 M D D(M) E M d A e A 1 X X E(X) RSA E(XY) = E(X)E(Y) II 1.(1) 2 Step 1 Step 2 Step 3 A M h d A S A (M, S) B B S A e A M h h(m) 6

12 M (M, S) M h S S h h(m) D E d A e A / Step 1 A ID ID A K PA 7

13 Step 2 Step 3 Step 4 ID A,K PA K S S AC A A M,S A ID A,K PA,S AC B B ID A,K PA,S AC K P A M,S A A K PA A (IDA,KPA) KSA KS (IDA,KPA,SAC) (IDA,M,SA, KPA,SAC) KP IDA A ID KPA A KPB B SAC (IDA,KPA) SA M A B KSB 3 (3) A B A k AB B B B A A k AB B 8

14 RSA Merkle public key distribution system Diffie-Hellman[1976] DH DH A B DH p Step 1 Step 2 Step 3 Step 4 A [0, p-1] X A Y A = X A mod p (1) Y A B B [0, p-1] X B Y B = X B mod p (2) Y B A A X K = Y A B mod p = X A X B mod p (3) B K p Y Y= X mod p X p DH DH DH intruder-in-the-middle-attack C Y A Y B Y C = X C mod p A B A B B A DH Station-To-Station Diffie-van Oorschot-Wiener[1992] 9

15 RACE 3 Integrity Primitives Evaluation (RIPE) Rabin COMSET Brandt et al.[1990] EKE Encrypted Key Exchange Bellovin and Merritt[1992] ID Shamir[1985] DH RSA E. Okamoto[1989] KPS Key Predistribution System 4 Matsumoto-Imai[1988] RSA DLP Girault[1991] (4) (blind signature) Chaum[1983] Chaum[1982] RSA ElGamal Camenisch et al.[1994] Zero Knowledge Interactive Proof; ZKIP Okamoto and Ohta[1990] 3 RACE(The Research and Development in Advanced Communication Technologies in Europe) EC IBC(Integrated Broadband Communication) 4 KPS Eudora MS excahnge 10

16 RSA A M B B RSA (e,n) d Step 1 Step 2 Step 3 Step 4 A r B (e,n) X = Mr e mod n (4) X B B (d,n) Y = X d mod n = M d r mod n (5) Y A A Y r -1 B S = M d mod n A S B S e = M mod n (6) Step 3 r -1 r -1 r = 1 mod n GCD(r, n) = 1 Euclid A B Chaum cut-and-choose-methodology 1 ZKIP DLP Brands[1993] RSA Abe-Fujisaki[1996] DLP Abe-Camenisch[1997] cut-and-choosemethodology 1 undeniable signature 11

17 Chaum and van Antwerpen[1990] Step 1 Step 2 Step 3 Step 4 A B S A B r A A r d A B B A e A A S A d A A disapproval protocol 1 fail-stop signature Pfitzman and Waidner[1990] group signature Chaum[1991] 12

18 Step 1 Step 2 Step 3 Step 4 Step 5 Step 2 Chaum[1991] blind decryption Micali[1993] [1996] 13

19 RSA Micali[1993] ElGamal [1995] 3 1 bit (1) (direct attack) (chosen plaintext attack) (chosen ciphertext attack) (adaptive chosen ciphertext attack) 14

20 fault-based attack 1 bit 1 bit 1 0 bit Anderson[1996] 1 bit RSA ElGamal (total break) (general break) partial break 1 bit 1 bit bit 1 bit semantically secure Goldwasser and Micali[1984] tampering 15

21 f C=E(M) M =f(m) C =E(M ) f C=E(M) M =f(m) C =E(M ) nonmalleable RSA Rabin RSA Rabin RSA Goldwasser- Micali Naor-Yung OAEP RSA OAEP (2) direct attack known message attack 16

22 chosen message attack adaptive chosen message attack total forgery universal forgery selective forgery existential forgery 1 17

23 Rabin OSS OSS ElGamal RSA DSA Naor-Yung Bellare-Goldwasser 18

24 II 3 Diffie-Hellman RSA RSA Factoring Problem FP 20 RSA FP FP RSA FP Discrete Log Problem DLP DLP ElGamal ElGamal Schnorr DSA DLP FP FP DLP FP DLP Rabin Rabin Williams Rabin Bellare- Goldwasser McEliece MI Ong-Schnorr-Shamir ESIGN Fiat-Shamir 19

25 ESIGN Fiat-Shamir ESIGN Fiat-Shamir ESIGN Fiat-Shamir 1980 Optimal Asymmetric Encryption Padding OAEP FP DLP Schnorr ElGamal elliptic curve DLP EDLP EDLP DLP EDLP EDLP FP DLP EDLP FP DLP 1 RSA 20

26 Rabin Rabin Williams Obscure MI (1)RSA RSA MIT Rivest, Shamir, and Adleman[1978] RSA FP 20 RSA RSA 20 RSA RSA A B [ ] B p q 5 n=pq p-1 q-1 l=lcm(p-1,q-1) GCD(e,l)=1 e ed=1 (mod l) d d (e, n) 5 Fermat Solovay-Strassen Solovay and Strassen[1977] Miller-Rabin Rabin[1976] Adleman-Rumely Adleman et al.[1983] Atkin-Morain Atkin and Morain[1993] Goldwasser-Kilian Goldwassr and Kilian[1986] Adleman-Huang Adleman and Huang[1992] 21

27 [ ] M C C = M e (mod n) (7) [ ] C M M = C d (mod n) (8) RSA n p q n p q M C M = C d (mod n) d n (n) = (p-1)(q-1) n n Miller[1976] Kocher[1996] timing attack Diffie-Hellman DSA Kocher FP 20 T(p) T(p) = exp ((1.901+o(1))(log p) 1/3 (log log p) 2/3 ) p,q p,q 22

28 p,q p,q p-q (p 1) (q 1) p +, p -, q +, q - (p + 1)(p - 1) (q + 1) (q - 1) GCD(p-1,q-1) 4 Fermat p-1 p+1 III 1. f(x) = x e mod n f m (x) = x (9) m x e,n,x Simmons and Norris[1977] p,q C m y=f m-1 (C) C n(=pq),e,c C p,q,e Rivest[1978] Williams and Schmid[1979] p,q,e RSA (i) p = a p + 1, q = b q + 1 p = a p + 1, q = b q + 1 p, q, p, q (ii) e l 1 (mod p q ) l p q Knuth[1979] Prob{x x k 1 (mod n)} 10-2l (10) 23

29 k 10 l log k n n l k p,q Knuth[1981] p-1 q-1 p,q (p q ) Rivest[1978] (i) p,q x x k = 1 (mod n) k p q 1/p q [1983] (10) m Rivest[1978] RSA (a) p q (b) (a) C p,q 1/p+1/q-1/pq (11) p q (a) 2/ n (b) 9 Blakley[1978], Blakley and Borosh[1979] RSA bit Chor and Goldreich[1984] 24

30 RSA bit RSA Boneh et al.[1996] RSA RSA x,y f(xy) = f(x) f(y) 25

31 6 Davida[1982], Denning[1984], Desmedt and Odlyzko[1985] M M r e M M = r e M mod n (12) M S = M d mod n (13) r M S r -1 = M d mod n (14) M M 1,M 2 M = M 1 M 2 mod n (15) d S 1 = M 1 mod n (16) d S 2 = M 2 mod n (17) M d S 1 S 2 = M mod n (18) 6 26

32 (15) RSA m n i = p i q i e i,d i (i=1,2,,m) p q p q m (e i,d i ) n = pq (e i,n) e i RSA Simmons[1983] #1 #2 M C 1 = M e 1 mod n (19) C 2 = M e 2 mod n (20) e 1 e

33 r s re 1 +se 2 = 1 r s r 0-1 (C 1 ) -r s C 2 = M re 1 +se 2 = M mod n (21) DeLaurentis[1984] n n d (a) n n n 1 b b 2 1 mod n (22) b 1 mod n (23) b+1 b-1 n n p,q n 1 b b c,k l c (n) = 2 k l (24) (n)= (p-1)(q-1) e 1 d 1 c,k l e 1 d 1-1 = c (n)= 2 k l (25) (b) (e 2,d 2 ) 28

34 e 1 e 1 d 1 =1 mod (n) d 1 (n) O(log 2 n) d 1 e 1 (n) d e 1 rd+se 1 = 1 r,s d (n) se 1 = 1 mod (n) e Coppersmith et al.[1996] e M Blum Liberherr Williams 3 #1, #2, #3 M C 1 = M 3 mod n 1 C 2 = M 3 mod n 2 C 3 = M 3 mod n 3 n 1, n 2, n M 3 mod n 1 n 2 n 3 M 3 n 1 n 2 n 3 M 3 mod n 1 n 2 n 3 M 3 3 M n 1, n 2, n 3 Coppersmith et al.[1996] 29

35 (c 1,c 2 ) (m 1,m ) m m m 2 = am 1 +b (26) e=3 c i = m i3 mod n (i=1,2) (27) m 1 b(c 2 +2a 3 c 1 -b 3 ) a(c 2 -a 3 c 1 +2b 3 ) 3a 3 bm 13 +3a 2 b 2 m 12 +3ab 3 m 1 = mod n 3a 3 bm 12 +3a 2 b 2 m 1 +3ab 3 = m 1 mod n (28) m 1,m 2 e m 1 e O(e log 2 e) e=32 m 2 m 1 k O((e+k) 3 k 2 ) Coppersmith et al.[1996] Boneh et al.[1996] tamper resistant device RSA Bao et al.[1996] bit bit M=C d mod n bit C 0 =C a0, C 1 =C a1, C 2 =C a2,..., C 511 =C a511 a i =2 i (i = 0,1,...,511) 30

36 bit M = C d mod n d511 d510 d0 = C 511 C 510 C i di C 0 mod n d= d 511 d d.... d i 0 d i 1 bit d i d511 d510 di d0 M = C 511 C 510 C i C 0 mod n M = di C i mod n M di C i i bit d i (2)Rabin RSA RSA Rabin[1979] RSA Rabin A B [ ] B p q n=pq 0 b n b (p, q) (n, b) [ ] M C C = M(M+b) (mod n) (29) [ ] M 2 M 2 +Mb-C = 0 (mod p) (30) M 2 +Mb-C = 0 (mod q) (31) Rabin RSA 2 n RSA Rabin 31

37 RSA RSA Rabin n n c,n x 2 = c mod n (32) x x y c = y 2 mod n c x 2 = y 2 mod n (33) x 1/2 x y x-y n p q y 2 c (= y 2 mod n) x y x x-y n Rabin Rabin M C M M ID 32

38 Rabin (30)(31) M 1/4 (3) Rabin MI Rabin Rabin Williams[1980] p,q Williams Rabin [1987] Williams Williams Rabin MI Matsumoto and Imai[1983,1988] [1982,1984,1985] obscure 1 Matsumoto-Imai[1983] Delsarte et al.[1985] 1988 Matsumoto-Imai[1988] 33

39 7 2 DLP ElGamal EDLP DL OAEP optimal asymmetric encryption padding (1)ElGamal ElGamal[1984] Diffie-Hellman DLP DLP FP ElGamal A B M [ ] B p x R Z* p p y = x mod p x (y, p, ) [ ] A k B y C 1,C 2 C 1 = k mod p (34) C 2 = My k mod p (35) [ ] B x M MC 1 xb = C 2 mod p (36) ElGamal DLP DLP (C 1,C 2 ) 7 Patarin[1995] 34

40 C 1 k C 2 y k C 1 k DLP DLP bit bit DLP Blum and Micali [1982] k k k (M a,m b ) (C a,c b ) M b C b = (37) M a C a M a C a C b M b ElGamal Zheng and Matsumoto[1996] k (C 1,C 2 ) C 2 M = mod n y k (2)EDLP DL 1985 F 8 EDLP DL Koblitz[1987], Miller[1986] DLP EDLP

41 EDLP EDLP 9 Certicom Next Siemens Thompson EDLP DL F q F q DL r r r r DLP EDLP DL ElGamal EDLP ECElG ECElG ElGamal A B m M m E(F q ) P E(F q ) [ ] B x R Z* p E Y =xp x E(F q ),P,Y [ ] A r E C 1 = rp (38) C 2 = M+rY (39) (C 1, C 2 ) B [ ] B x E C 2 -xc 1 = M (40) 9 EDLP 36

42 M m m 0 m l E(F q ) M 10 ECElG EDLP DL EDLP DLP EDLP DLP MOV Menezes-Okamoto-Vanstone[1991] EDLP E(F q ) EDLP Pohlig-Hellman T(q) T(q) = O ((#E(F q )) 1/2 ) ECElG 10 m E(F q ) M k 0 kl q 1 i k i x m,i =mk+i p r-1 x m,i i =0 a i p i (0 a i p-1) a i x m,i F q F p r-1 r-1 i =0 a i X i F q x m,i f(x m,i ) F q i x m,i =x m, x m m E(F q ) M = (x m, f(x m ) 0.5 ) 1 i k i f(x m )(x m =mk+i) 1/2 m E(F q ) (1/2) k E(F q ) M x x m x m x m -1 m = k m 37

43 ECElG DH Sakurai and Shizuya[1995] ECElG ElGamal ElGamal 2 1 Zhen and Matsumoto[1996] (3)OAEP I 3.(1) Bellare and Rogaway[1995] OAEP optimal asymmetric encryption padding Goldwasser-Micali[1984] Goldwasser-Micali Goldwasser-Micali Blum, Feldman, and Micali[1988] noninteractive zero-knowledge proof NIZK 11 Naor-Yung[1990] NIZK Naor-Yung Damgard[1992] Zhen and 11 zero-knowledge interactive proof ZKIP 38

44 Seberry[1993] Dolev, Dwork, and Naor[1991] Bellare and Rogaway[1993] OAEP Bellare and Rogaway[1995] RSA OAEP SET 12 OAEP m {0,1} n f(m0 k1 ) G(r) r H(m0 k1 G(r)) f G H r bit 0 k1 Bellare and Rogaway[1995] OAEP f RSA G H SHA Secure Hash Algorithm 13 SHA OAEP (4) McEliece 12 SET(Secure Electronic Transactions) VISA Mastercard SET de facto standard 13 SHA NSA National Security Agency MD 39

45 Merkle-Hellman[1978] Merkle-Hellman Merkle-Hellman Merkle-Hellman Merkle[1978] Graham- Shamir Graham-Shamir Shamir[1980] Chor-Rivest Chor-Rivest[1984] Shamir[1978] Shamir n c n a = (a 1,a 2,,a n ) c = a t m = a i m i (41) i 2 m = (m 1,m 2,,m n ) M n NP NP NP 14 Merkle-Hellman a i a 1 + +a i-1 (i=2,,n) n P n NP NP NP NP NP NP 15 n 40

46 Shamir[1982] n Graham-Shamir Lagarias and Odlyzko Lagarias[1984] Brickell [1983] LLL 16 Merkle-Hellman Adleman[1982] Brickell[1982] Shamir Odlyzko[1984] LLL Chor-Rivest Schnorr and Hörner[1995] McEliece McEliece[1978] Goppa NP McEliece McEliece GF(2) 1 McEliece RSA 2 19 bit 500,000bit 2 Norzhik and Turkin[1991] McEliece 16 Merkle-Hellman Shamir[1982] Lenstra[1981] Merkle-Hellman LLL Lovasz Lenstra 41

47 3 DLP ElGamal Schnorr DSA FP ESIGN ZKIP Fiat-Shamir EDLP Ong-Schnorr-Shamir NIZK Bellare-Goldwasse I 3.(2) FP DLP OAEP RSA ESIGN RSA ESIGN Bellare and Rogaway[1996] FP DLP Schnorr Fiat-Shamir ElGamal Pointcheval and Stern[1996] correlation-free one-way hash function FP DLP Fiat-Shamir Okamoto[1993] (1)ElGamal ElGamal ElGamal[1984] DLP DLP FP ElGamal RSA 2 ElGamal Schnorr DSA ElGamal RSA RSA 42

48 ElGamal p 17 FP DLP RSA ElGamal A B M [ ] A p x R Z* p y = x mod p p x y, p, [ ] A k r r = k mod p (42) A x r, k t M-xr t = mod p-1 (43) k A B M S = (r, t) [ ] B A y M = y r r t mod p (44) ElGamal DLP y, p, y = x mod p x ElGamal (y, p, ) x ElGamal DLP DLP 10 FP FP 17 Fermat p-1 p x 43

49 RSA ElGamal DLP Schirokauer[1993] Adleman[1994] T(q) T(q) = exp((1.922+o(1))(log q) 1/3 (loglog q) 2/3 ) ElGamal DLP ElGamal A x A M r t M t r S = (r, t) M M S = (r, t) t = log r M y -r mod p r y r r t = M mod p (45) M = log y r r t mod p r = i y j mod p (46) t = -rj -1 mod p-1 (47) M = -r i j -1 mod p-1 (48) 0 i p-2, 0 j p-2, GCD(j, p-1)=1 M ElGamal DLP 44

50 ElGamal ElGamal k p, k ElGamal k k k k M, S = (r, t) x M - k t x = mod p-1 (49) r x k (M 1, r, t 1 ), (M 2, r, t 2 ) y r r t1 = M1 mod p (50) y r r t2 = M2 mod p (51) k k(t 1 - t 2 ) = M 1 -M 2 mod p-1 (52) k x p, p, Bleichenbacher[1996] ElGamal p -1 = nq n b t = (mod p) b = lq 0 l n 45

51 t M (r, t) M F p * r = b, s = tm (mod q) M y r r -s t = M - t M /t = 1 (r, s) M F p b F p b F p p-1 q p-1 = qn b q b = lq (l {1,,n-1}) 1 t q-1 = b t (mod p) n b ElGamal F p r p-1 q r q ElGamal DSA r = b DSA Zheng and Matsumoto[1996] k M S = (r, t) M-kt x = mod p-1 r 46

52 (2)ESIGN ESIGN NTT Okamoto[1990] 18 FP ESIGN Okamoto et al.[1993] A M B [ ] A p,q p q n = p 2 q, k 3 (p, q) (k, n) [ ] A Z pq * x h(m)-(x k mod n) w = (53) pq w = mod p (54) kx k-1 s = x+ypq (55) A B M s [ ] B A k h(m) s k mod n h(m)+2n 2/3 (56) ESIGN 18 Okamoto[1986,1987] ESIGN Shamir Vallée et al.[1988] 47

53 ESIGN RSA n p 2 q s p,q p,q {s j j=1,,j} {t j t j = (s k mod n)-h(m), j=1,,j} p,q s x p,q x s n = p 2 q (57) k h(m)-( x j mod n) w j = (j=1,,j) (58) pq w j y j = mod p (j=1,,j) (59) kx j k-1 s j = x j +y j pq (j=1,,j) (60) (3J+2) (3J+1) {x j } Z pq * {s j } Z n * {s j } p,q {t j } Z pq {t j } pq {t j } {t j } pq {t j } ESIGN FP RSA RSA n 48

54 ESIGN n=p 2 q n q q s exp(-(log n)/3) s k = h(m) mod n (61) RSA ESIGN k 4 ESIGN Okamoto and Shiraishi[1985] k 2 Brickell and delaurentis[1986] k=3 k=2 Shamir ESIGN k,p,q,n k: 8,16,32,4,128,256,512,1024 p,q: 192 bits n: 576 bits 49

55 Shamir k=3 Brickell and delaurentis[1986] k 4 ESIGN k=2 Shamir h(m) h(m) s 2 mod n h(m)+2n 2/3 s r x 2rx-h(M)+r 2 mod n 2n 2/3 (1 x n 1/3 ) (62) x n 2/3 h(m) mod n [0, n] r x s = r+x k=3 Brickell and delaurentis r = [n/3](i.e., r = n/3+a for a 1/2) r z = h(m)-r 3 mod n z 1/3 3 x (i.e., x = z 1/3 +b for b 1/2) s = r+x h(m) s 3 = r 3 +3r 2 x+3rx 2 +x 3 mod n = r 3 +3(n/3+a) 2 x+3(n/3+a)x 2 +z+3z 2/3 b+3z 1/3 b 2 +b 3 mod n = h(m)+3a 2 x+3ax 2 +3z 2/3 b+3z 1/3 b 2 +b 3 mod n = h(m) mod n 2n 2/3 (63) n/3 k 4 ESIGN Brickell and delaurentis[1986] ([N 1/k ]) k -N = O(N k-1/k )O(N 2/3 ) (64) k 4 (Vallee et al.[1988a,1988b], Girault et al.[1989]) k 4 50

56 M 1,M 2,,M t s 1,s 2,,s t k s i = h(m i ) mod n (i=1,,t) (65) n RSA n 10 M 0 {s i i=1,,t} m 0 s k mod n m 0 +2n 2/3 s k s i mod n = m i ( m i = h(m i ), i=1,,t) RSA m 0,m 1,,m t k m i s i mod n m i +2n 2/3 m 0,m 1,,m t (3)DSA ElGamal 2 Schnorr[1989] ElGamal DLP p p-1 q ElGamal 2 p 2 q Schnorr q DLP p DSA Schnorr ElGamal NIST 19 [1992] NIST National Institute of Standards and Technology 1987 Computer Security Act FIPS 1980 Executive Order 51

57 ElGamal Schnorr DSA RSA Hoster et al.[1995] Miyaji[1996] DSA Miyaji[1996] A M B [ ] A p, p- 1 q x R Z q y = g x mod p g q x y, g, p, q [ ] A k R Z q r r = (g k mod p) mod q (66) A x r, k t h(m)+xr t = mod q (67) k A B M S = (r, t) [ ] B A y r = (g h(m)/t y r/t mod p) mod q (68) DSA DSA y g g q y = g x mod p (69) NSA National Security Agency 52

58 p Gordon q Pohlig-Hellman III 2. DSA M r t M t r S = (r, t) M M S = (r, t) t, z qz+r = (g h(m) y r ) 1/t mod p (70) p DLP r, z (qz+r) t y -r = g h(m) mod p (71) r r t y -r = g h(m) mod p (72) M, z (qz+r) t y -r = g h(m) mod p (73) p DLP M,r,t r = (g h(m) y r ) 1/t mod p (74) M Vaudenay[1996] 53

59 ElGmal k k k ElGamal Bleichenbacher[1996] (4)Fiat-Shamir Fiat-Shamir Fiat-Shamir[1986] challenge and response Fiat-Shamir Fiat-Shamir[1986] Fiat-Shamir RSA 100 [ ] A p q n=pq k Z k-bit h s Z n v=s 2 mod n n, f s [ ] A k h=(e 1 e k )=f(m,x 1,,x k ) A y i =r i s ei mod n 1 =(x 1,,x k ) 2 =(y 1,,y k ) ( 1,h, 2 ) m [ ] B m ( 1,h, 2 ) h = f(m, 1 ) (75) y i = r i s ei mod n for i (76) Fiat-Shamir 54

60 correlation-free one-way hash function Okamoto[1993] (5)EDLP EDLP ECElG ECSS ECDSA ECSS IEEE 20 Institute of Electrical and Electronic Engineers ECDSA IEEE ANSI 21 (American National Standards Institute) DLP ECElG ElGamal ECSS Schnorr ECDSA DSA EDLP DLP FP DLP ECSS ECDSA EDLP DLP EDLP DLP MOV Menezes-Okamoto- Vanstone[1991] EDLP E(Fq) EDLP Pohlig-Hellman T(q) T(q) = O((#E(Fq)) 1/2 ) 20 IEEE ANSI IEEE IEEE 21 ANSI 1918 ANSI ISO 55

61 ECElG ECDSA #E(Fq) q Miyaji[1996] ElGamal DSA k k k (6) Ong-Schnorr- Shamir Bellare-Goldwasser Ong-Schnorr-Shamir Ong et al.[1984] Ong-Schnorr-Shamir Ong and Schnorr[1984] n 2 2 x 2 +ky 2 = m mod n (77) Pollard Ong et al Pollard[1987] Estes et al.[1986] Ong-Schnorr-Shamir 56

62 Ong et al. 4 Bellare-Goldwasser Bellare and Goldwasser[1990] NIZK 22 R NIZK NIZK R Bellare-Goldwasser Feige and Shamir [1990] Dwork and Naor [1994] RSA 2 5 RSA 22 Naor and Yung[1989] Rompel[1990] 57

63 III FP DLP EDLP RSA Rabin Rabin Williams ESIGN Fiat-Shamir FP ElGamal DSA Schnorr DLP DL ECElG ECDSA ECSS EDLP 1 FP RSA Rabin Rabin Williams ESIGN Fiat-Shamir FP (1) n p O(p) p n z n z p=gcd(n,z) n p m, n min(m, n) 5 Lamé Euclid 1 z n p n 58

64 O(p 1/2 ) Pollard[1975] p-1 p-1 Pollard[1974] p+1 p 1 Guy[1975] p-q Fermat Brillhart[1981] p-1 Lenstra[1987] Montgomery[1987] 2 2 s 2 = t 2 mod n s t z=s±t GCD(n, z) Morrison-Brillhart[1975] Schroeppel[1977] 2 Pomerance[1983] Silverman[1987] Lenstra et al.[1990] L p [a, b]=exp((b+o(1))(log p) a (loglog p) 1-a ) (78) o(1) 0 (2) p-1 p+1 Fermat 2 p p-1 p 1 Pollard[1974] n p p-1 p-1 n p p-1 M p-1 = p i ei, p i M (79) p-1 M -smooth p n a GCD(a, n) = 1 GCD(a, p) = 1 Fermat 1 a p-1 = 1 mod p (80) p-1 K a K =1 mod p p a K -1 59

65 n GCD(a K -1, n) p-1 K Pollard[1974] p-1 p-1 p-1 q p-1 = q p i ei, p i M, e i m i, q M (81) p i ei k a k = b b q = 1 mod p 1 GCD(b j -1, n) n j n n p p+1 p+1 = q p i ei, p i M, e i m i, q M (82) p-1 p+1 Guy[1975] Fermat Fermat Fermat's factoring method Fermat p-q Brillhart[1981] p,q p-q Fermat Fermat n = pq, p q x =(q+p)/2 y =(q-p)/2 x 2 -y 2 = n (83) (x, y) = ([n], 0) (x, y) r = x 2 -y 2 -n (84) 0 (x, y) (p, q) (x+1) 2 = x 2 +2x+1 A = 2x+1,B = 2y+1 x x+1 r r+a, A A+2 y y+1 r r-b, B B+2 Fermat 2 Pomerance[1983] 2 k 2 = l 2 mod n k l 2 quadratic sieve method 60

66 Pomerance[1983] k 2 = l 2 mod n k l Q(x) = (x+m) 2 -n, m=[n 1/2 ] (85) x = 0, 1, 2, Q(x) Q(x) Q(x) p j Q(x) v Q(x) Q(x) d1 dr Q(x) = p 1 p r mod n (86) p 1,,p r v v-smooth Q(x) S a1 ar Q(x) = p 1 p r mod n (87) a j (j=1,,r) k = (x+ m) mod n (88) l = p j aj/2 mod n (89) k 2 = l 2 mod n GCD(k+l, n) GCD(k-l, n) n (94) Pomerance[1983] 2 T(n) T(n) = L n [1/2, 1.061] Silverman[1987] Q(x) 2 b 2-4ac = kp k 2 ax 2 +bx+c k, l 23 T plural (n) T plural (n) = L n [1/2, 1.020] Rivest Scientific America 129 Lenstra

67 p-1 p-1 Z p * p-1 p-1 k Z p * a k =1 p-1 Z p * F p E(F p ) a P E(F p ) p-1 k E(F p ) k E(F p ) kp=o n E(F p ) p-1 p-1 p-1 p T(p) = L p [1/2, 1.414] n=pq p q T(n) = L n [1/2, 1.020] 2 24 n f Z n [X] Z n k m n= f(m) f=0 C K K =Q( ) O =Z[ ] K Z[ ] Z n f( ) f(m) mod n c+d O K c+d m Z smooth 24 [1987] 62

68 smooth B Q B O K 1 O K c+d K N(c+d ) N(c+d ) = (-d) f(-c/d) (c i, d i ) c i +d i m -smooth c i +d i -smooth c i +d i m c i +d i (c i, d i ) (c i +d i m) = s 2 (c i +d i ) = t 2 GCD(s 2 t 2, n) n 2 DLP, EDLP (1) DLP DLP G g G a H= g G g x =a x DLP 2 H= g G H H log g a H log g H G=F* q (q=p k ) G log g a index calculus method F q log g F q 63

69 Shanks[1972] Pohlig-Hellman[1978] Pollard[1978] Adleman[1979] Coppersmith[1984] ElGamal[1985] Coppersmith-Odlyzko-Schroeppel[1986] Gauss DLP Gordon[1992] Schirokauer[1993] Adleman[1994] F q (q=p k ) k (log p) 1/2- Schirokauer L p k[1/3,(64/9) 1/3 ] L p k[1/3,(64/9) 1/3 ] (log p) 1/2- k (log p) 2 L p k[1/2,c] Schirokauer et al.[1996] (2) EDLP DSA q Pohlig-Hellman[1978] F q Gordon[1992] Pohlig-Hellman Pohlig-Hellman[1978] H= g G n n O(log n)-smooth O(log 2 q) n = #H = # g n y-smooth k n = q i ei, q 1 q k y (90) i=1 x = log g a Z n n e1 ek Zn Zq 1 Zq k (91) log g a log g a Z n Zq i ei i 64

70 e-1 x = b j q j, b j Zq (92) j=1 b j (0 j e-1) Step 1: a n/q =g n/q Step 2: i =g n/q i i=0,1,... b 0 =i e 1 Step 3: a 1 = a g -b0 i n/q2 = a 1 q 2 = q 2 i b 1 =i Step 4: a 2 = a 1 g -b1q i n/q3 = a 2 q 3 = q 3 i b 2 =i b e-1 O( e i (log n+q i )) n n O(log n)-smooth O((log n) 2 ) H G n O(log n)-smooth G=H=Z* p p-1 O(log p) p-1 Pohlig-Hellman[1978] F p Q H= g G F p log g a Step 1: F p Q F p Q : g r mod p g r Step 2: v-smooth {p 1,, p n 0 p i v} Q g F p g r mod p v-smooth r g r a1 an mod p = p 1 p n F p r mod p-1 = a 1 log g p a n log g p n n {log g p i } 65

71 Step 3: yg t mod p v-smooth t F p yg t mod p = p 1 b1 p n bn log g y = b 1 log g p b n log g p n mod p - t Adleman[1979] G=H=Z* p DLP u=l p [1/2,0] Step 1 b i g bi b i g bi Step 1 Step 2 L p [1/2,c](c 0) DLP EDLP F p Q E(F p ) E(Q) E(Q) Gordon G=H=Z* p Adleman[1979] Gordon[1992] 2 Z p p p p f Z p [X] x,y p 1/k y k f(x/y)=0 (mod p) O K = Z( ) 66

72 F p T special (p) T special (p) = L p [2/5, 1.005] F p T G (p) = L p [1/3, 3 2/3 ] = L p [1/3, 2.080] k F p k (log p) 1/2- Schirokauer[1996] T S (p k ) T S (p k k ) = L p [1/3, (64/9) 1/3 ] = L p k[1/3, 1.922] Adleman-Lenstra k F p k (log p) 2 Adleman[1994] Schirokauer (3)EDLP EDLP 1: 2: MOV E(F q ) EDLP DLP F q 1 EDLP Pohlig-Hellman[1978] Pollard[1978] Schoof[1985] Schoof[1985] Schoof 6 (Charlap-Coley-Robbins [1991] ) 67

73 1 1 Menezes- Vanstone[1990] Morain[1991] F 2 F p F Menezes-Okamoto-Vanstone[1991] MOV MOV-reduction EDLP DLP MOV Weil Weil pairing 6 DLP Menezes-Vanstone[1990] Beth- Schaefer[1991] Miyaji[1993] F 2 MOV E(F q ) EDLP F q DLP p F p EDLP MOV DLP Deuring[1941] 68

74 MOV Schoof[1995] 27 3 Koblitz[1991] Meier- Staffelbach[1993] GF(2 l ) Frobenius P (anomalous elliptic m curve) Miyaji[1994] Miyaji[1994] Koyama- Tsuruoka[1992] #E(F p )=p P P x 0 F p P P x,y #E(F p ) P m 3 FP DLP EDLP 27 Lercier and Morain[1995] 69

75 10 20 II FP p-1 Fermat DLP EDLP Pohlig-Hellman DLP Gordon EDLP MOV FP DLP Schirokauer Gordon EDLP Pohlig- Hellman Coppersmith Adleman-Lenstra Rivest 28 1 MIPS MIPS 250MIPS PC , = 800 MIPS PC Rivest 5 MIPS Rivest 20% 33% 45% 30 Type I 28 Garfinkel[1995] 29 1MIPS MIPS Odlyzko [1995] 70

76 Type II Type III 3 Type I 1 Type II 10 Type III 1, FP Adleman-Lenstra L p [1/3,1.922]=exp(1.922(log p) 1/3 (loglog p) 2/3 ) DLP Schirokauer Gordon k L p [1/3,1.922]=exp(1.922(log p k ) 1/3 (loglog p k ) 2/3 ) EDLP Pohlig-Hellman exp(0.5log p) MIPS 800 MIPS MIPS 20% 33% 45% 5 Type I 1 Type II 10 Type III 1,000 71

77 MIPS YEAR MY 5 5 [ MY] FP & DLP EDLP E E E E E+05 1, E+12 1, E+17 2, E+21 5 FP DLP 1,024 bit EDLP 176 bit FP DLP 2,048 bit EDLP 232 bit FP 1,024 bit EDLP 160 bit FP 2,048 bit EDLP 224 bit 72

78 5 6 Type III Type II 6 5 [ ] FP & DLP EDLP E E E E E-01 1, E+06 1, E+11 2, E+15 FP DLP 512 bit FP-512 DLP-512 Type III Type II EDLP-160 Type III 73

79 [ ] FP & DLP EDLP E E E E E E E E E E-04 1, E E+03 1, E E+08 2, E E+18 FP-512 DLP Type I FP-1024 DLP Type III EDLP Type III EDLP

80 [ ] FP & DLP EDLP E E E E E E E E E E-06 1, E E+01 1, E E+06 2, E E+10 FP-1024 DLP Type III EDLP Type II EDLP

81 [ ] FP & DLP EDLP E E E E E E E E E E-02 1, E E+04 1, E E+09 2, E E FP DLP 1,536 bit EDLP 200 bit FP DLP 2,048 bit EDLP 240 bit EDLP 5 EDLP 76

82 FP DLP EDLP FP DLP EDLP 1, FP DLP 2,048 bit EDLP 240 bit EDLP FP DLP FP DLP 240 bit EDLP FP DLP DNA 77

83 RSA (D) Vol.J66-D No.8 pp A Vol. J70-A No. 11 pp NTT R&D Vol. 44 No RSA 1997 SCIS 97-15C IT GF(2) IT Obscure IT (A) Vol. J71-A No. 7 pp ElGamal 1997 SCIS 97-7B

84 1997 SCIS 97-6A pp SCIS 96-7C 1996 Abe, M. and E. Fujisaki, How to date blind signatures, Advances in Cryptology Proceedings of ASIACRYPT 96, Lecture Notes in Computer Science, Vol. 1163, pp , Springer-Verlag, Adleman, L. M., A subexponential algorithm for the discrete logarithm problem with applications to cryptography, Proceedings of FOCS,,pp , and R. L. Rivest, How to break the Lu-Lee (COMSAT) public-key cryptosystem, MIT Laboratory for Computer Sience, July 1979., C. Pomerance, and R. S. Rumely, On distinguish prime numbers from composite numbers, Ann. of Math., Vol. 117, pp , and M. A. Huang, Primarity testing and abelian varieties over finite fields, Lecture Notes in Math., Vol. 1512, Springer-Verlag, 1992., The function field sieve, Algorithmic Number Theory, Lecture Notes in Computer Science, Vol. 877, pp , Springer-Verlag, Alex, W., B. Chor, O. Goldreich, and C. P. Schnorr, RSA/Rabin bits are 1/2+1/poly(log N) secure, Proceedings of the IEEE 25th Symposium on the Foundations of Computer Science, pp , Anderson, R., A serious weakness of DES, November news:cmm risko@chirom.cs1.sri.com Atkin, A. O. L. and F. Morain, Elliptic curves and primality proving, Math. Comp., Vol. 61, pp , Bao, F., R. Deng, Y. Hang, A. Jeng, T. H. Nagir, and D. Narashimaharu, A new attack to RSA on tamerproof devices, October 1996, < aa01599@aquarius.iss.nus.sg> Bellare, M., S. Goldwasser, New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs, Advances in Cryptology Proceedings of CRYPTO 89, Lecture Notes in Computer Science, Vol. 435, pp , Springer-Verlag, and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the First Annual Conference on Computer and 79

85 Communications Security, ACM, and, Optimal asymmetric encryption, Advances in Cryptology Proceedings of EUROCRYPT 94, Lecture Notes in Computer Science, Vol. 950, pp , Springer-Verlag, Bellovin, S. M. and M. Merritt, Encrypted key exchange: Password-based protocols secure against dictionary attacks, Proceedings of the 1992 IEEE Computer Society Conference on Research in Security and Privacy, pp , Beth, T. and F. Schaefer, Nonsupersingular elliptic curves for public key cryptosystems, Advances in Cryptology Proceedings of EUROCRYPT 91, Lecture Notes in Computer Science, Vol. 547, pp , Springer-Verlag, Blakley, B. and G. R. Blakley, Security of number theoretic public key cryptosystems against random attack (Part I), Cryptologia, Vol. 2, No. 4, pp , 1978a. and, Security of number theoretic public key cryptosystems against random attack (Part II), Cryptologia, Vol. 3, No. 1, pp , 1978b. and, Security of number theoretic public key cryptosystems against random attack (Part III), Cryptologia, Vol. 3, No. 2, pp , 1979a., Rivest-Shamir-Adleman public key cryptosystems do not always conceal messages, Computers and Mathematics with Applications, Vol. 5, pp , 1979b., Safeguarding cryptographic keys, Proceedings of the National Computer Conference, Vol. 48, pp , American Federation of Information Processing Societies, 1979c. Blaze, M., W. Diffie, R. L. Rivest, B. Schneier, T. Shimomura, E. Thompson, and M. Wiener, Minimal key lengths for symmetric ciphers to provide adequate commercial security, A Report by an Ad Hoc Group of Cryptographers and Computer Scientists, January Bleichenbacher, D., Generating ElGamal signatures without knowing the secret key, Advances in Cryptology Proceedings of EUROCRYPT 96, Lecture Notes in Computer Science, Vol. 1070, pp , Springer-Verlag, Blum, M. and S. Micali, How to generate cryptographically strong sequences of pseudo random bis, Proceedings of FOCS, pp , 1982., P. Feldman, and S. Micali, Non-interactive zero-knowledge proof systems and applications, Proceedings of the 20-th Annual ACM Symposium on Theory of Comupting, pp , Boneh, D., R. A. DeMillo, and R. J. Lipton, A new breed of crypto attack on Tamperproof tokens cracks even the strongest RSA Code, September 1996, available at 80

86 Brands S., An efficient off-line electronic cash system based on the representation problem, Texcnical Report, CS-R9323, CWI, April Brandt, J., I. B. Damgard, P. Landrock, and, T. Pederson, Zero-knowledge authentication scheme with secret key excahnge, Advances in Cryptology Proceedings of CRYPTO 88, Lecture Notes in Computer Science, Vol. 403, pp , Springer-Verlag, Brickell E. F. and J. DeLaurentis, An attack on a signature scheme proposed by Okamoto and Shiraishi, Advances in Cryptology Proceedings of CRYPTO 85, Lecture Notes in Computer Science, Vol. 218, pp , Springer-Verlag, and A. M. Odlyzko, Cryptanalysis: A survey of recent results, in G. J. Simmons, ed., CONTEMPORARY CRYPTOLOGY The Science of Information Integrity, IEEE Press, Brillhart, J., D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of b n 1 up to high powers, Contemporary Mathematics, Vol. 22, American Mathematical Society, Providence, Charlap, L. S., R. Coley, and D. P. Robbins, Enumeration of rational points on elliptic curves over finite fields, Manuscript, Chaum, D., Blind signatures for untraceable payments, Advances in Cryptology Proceedings of Crypto 82, pp , Plenum Press, 1983., Security without identification: transaction system to make big brother obsolete, Communications of the ACM, Vol. 28, No. 10, pp , 1985., Zero-knowledge undeniable signatures, Advances in Cryptology Proceedings of EUROCRYPT 90, Lecture Notes in Computer Science, Vol. 473, pp , Springer-Verlag, 1991a., Group signatures, Advances in Cryptology Proceedings of EUROCRYPT 91, Lecture Notes in Computer Science, Vol. 547, pp , Springer Verlag, 1991b. Coppersmith, D. Fast evaluation of logarithms in fields of characteristic two, IEEE Transactions on Information Theory, Vol. IT-30, pp , 1984., A.M. Odlyzko, and R. Schroeppel Discrete logarithms in GF(p), Algorithmica, Vol. 1, pp. 1-15, 1986., M. Franklin, J. Patarin, M. Reiter, Low-exponent RSA with related messages, Advances in Cryptology Proceedings of EUROCRYPT 96, Lecture Notes in Computer Science, Vol. 1070, pp. 1-9, Springer-Verlag, 81

87 1996. Damgard, I., Towards practical public key cryptosystems secure against chosen ciphertext attacks, Advances in Cryptology Proceedings of CRYPTO 91, Lecture Notes in Computer Science, Vol. 576, pp , Springer-Verlag, Davida, G. I., Chosen signature cryptanalysis of the RSA(MIT) public key cryptosystem, Technology Report TR-82-2, Univ. of Wisconsin Department of Electrical Engineering and Computer Science, October DeLaurentis, J.M., A further weakness in the common modulus protocol for the RSA cryptosystem, Cryptologia, Vol. 8, No. 3, pp , Delsarte, P., Y. Desmedt, A. Odlyzko, and P. Pret, Fast cryptanalysis of the Matsumoto-Imai public key scheme, Advances in Cryptology Proceedings of EUROCRYPT 84, Lecture Notes in Computer Science, Vol. 209, pp , Springer-Verlag, Denning, D. E., Digital signatures with RSA and other public key protocols, Commun. ACM, Vol. 27, pp , Deuring, M., Die typen der multiplikatorenringe elliptischer funktionenkorper, Abh. Math. Sem. Hamburg, Vol. 14, pp , Diffie, W. and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, Vol.IT-22, pp , November 1976., P. C. van Oorschot, and M. J. Wiener, Authentication and authenticated key exchanges, Designes, Codes and Cryptography, Vol.2, pp , Dwork, C. and M. Naor, An efficient existentially unforgeable signature scheme and its applications, Advances in Cryptology Proceedings of CRYPTO 94, Lecture Notes in Computer Science, Vol. 839, pp , Springer-Verlag, ElGamal, T. E., A public key cryptosystems and a signature scheme based on discrete logarithm, Advances in Cryptology Proceedings of CRYPTO 84, Lecture Notes in Computer Science, Vol. 197, pp , Springer-Verlag, 1985., A subexponential-time algorithm for computing discrete logarithms over GF(p 2 ), IEEE Transactions in information Theory, Vol. IT-31, pp , Estes, D., L.M. Adleman, K. Konpella, K.S. McCurley, and G.L. Miller, Breaking the Ong- Schnorr-Shamir signature schemes for quadratic number fields, Advances in Cryptology Proceedings of CRYPTO 85, Lecture Notes in Computer Science, Vol. 218, pp. 3-13, Springer-Verlag, Feige, U. and A. Shamir, Witness indistinguishable and witness hiding protocols, 82

88 Proceedings of STOC, pp , Fiat, A. and A. Shamir, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology Proceedings of CRYPTO 86, Lecture Notes in Computer Science, Vol. 263, pp , Springer-Verlag, Garfinkel, S., PGP: Pretty Good Privacy, O Reilly & Associates, Inc., Girault, M., Self-certified public keys, Advances in Cryptology Proceedings of EUROCRYPT 91, Lecture Notes in Computer Science, Vol. 547, pp , Springer-Verlag, Goethals, J. M. and C. Couvreur, A cryptanalytic attack on the Lu-Lee public-key cryptosystem, Philips J. Res., Vol. 35, pp , Goldwasser, S. and S. Micali, Probabilistic encryption, Journal of Computer and System Sciences, Vol. 28, No. 2, pp , and J. Kilian, Almost all primes can be quickly certified, Proceedings of STOC, pp , 1986., S., S. Micali, and R. Rivest, A digital signature scheme against adaptive chosen message attack, SIAM J. Comput., Vol. 17, No. 2, pp , Gordon, D. M., Strong primes are easy to find, Advances in Cryptology Proceedings of EUROCRYPT 84, Lecture Notes in Computer Science, Vol. 209,pp , Springer-Verlag, 1985., Designing and detecting trapdoors for discrete log cryptosystems, Advances in Cryptology Proceedings of CRYPTO 92, Lecture Notes in Computer Science, Vol. 740,pp , Springer-Verlag, 1993., Discrete logarithm field in GF(p) using the number field sieve, to appear in SIAM Jounal on Discrete Math. Guy, R. K., How to factor a number, Proceedings of 5th Manitoba Conference on Numerical Mathematics, pp , Harper, G., A. Menezes, and S. Vanstone, Public-key cryptosystem with very small key length, Advances in Cryptology Proceedings of EUROCRYPT 92, Lecture Notes in Computer Science, Vol. 658, pp , Springer-Verlag, Hastad, J., On using RSA with low exponent in a public-key, Advances in Cryptology Proceedings of CRYPTO 85, Lecture Notes in Computer Science, Vol. 218, pp , Springer-Verlag, Horster, P., H. Petersen, and M. Michels, Meta-ElGamal signature schemes based on the 83

89 discrete logarithm problem and their applications, Advances in Cryptology Proceedings of ASIACRYPT 94, Lecture Notes in Computer Science, Vol. 917, pp , Springer-Verlag, Knuth, D., The art of computer programming, Vol. 2, (seminumerical algorithms), Addison- Wesley, Koblitz, N., Elliptic curve cryptosystems, Mathematcs of Comuptation, Vol.48, pp , 1987., Cm-curves with good cryptographic properties, Advances in Cryptology Proceedings of CRYPTO 91, Lecture Notes in Computer Science, Vol. 576, pp , Springer-Verlag, Korzhik, V. I. and A. I. Turkin, Cryptanalysis of McEliece s public-key cryptosystem, Advances in Cryptology Proceedings of EUROCRYPT 91, Lecture Notes in Computer Science, Vol. 547, pp.68-70, Springer-Verlag, Koyama, K. and Y. Tsuruoka, Speeding up elliptic cryptosystems by using a signed bunary window method, Advances in Cryptology Proceedings of CRYPTO 92, Lecture Notes in Computer Science, Vol. 740, pp , Springer-Verlag, Lenstra, A. K., H. W. Jr. Lenstra, M.S. Manasse, and J.M. Pollard, The number field sieve, Annals of Mathematics, Vol. 126, pp , Lenstra, H. W. Jr., Integer programming with a fixed number of variables, Univ. of Amsterdam Tech. Report, Vol , April 1981., Factoring Integers with elliptic Curves, Annals of Mathematics, Vol. 126, pp , Lercier, R. and F. Morain, Counting the number of point on elliptic curves over finite fields: starategies and performances, Advances in Cryptology Proceedings of EUROCRYPT 95, Lecture Notes in Computer Science, Vol. 921, pp , Springer-Verlag, Matsumoto, T. and H. Imai, A class of asymmetric cryptosystems based on polynomials over finite rings, Proceedings of IEEE International Symposium on Information Theory, pp , September and, On the key distribution system: A practical solution to the key distribution problem, Advances in Cryptology Proceedings of CRYPTO 87, Lecture Notes in Computer Science, Vol. 293, pp , Springer-Verlag, and, Public quadratic polynomial-tuples for efficient signatureverification and message-encryption, 84

90 McEliece, R. J., A public-key cryptosystem based on algebraic coding theory, Deep Space Network Progress Report, pp , Jet Propulsion Laboratory, Meier, W. and O. Staffelbach, Efficient multiplication on certain nonsupersingular elliptic curves, Advances in Cryptology Proceedings of CRYPTO 92, Lecture Notes in Computer Science, Vol. 740, pp , Springer-Verlag, Menezes, A. and S. Vanstone, The implementation of elliptic curve cryptosystems, Advances in Cryptology Proceedings of AUSCRYPT 90, Lecture Notes in Computer Science, Vol. 453, pp. 2-13, Springer-Verlag, 1990., T. Okamoto, and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, Proceedings of STOC, pp , Merkle, R. C. and M. E. Hellman, Hiding information and signatures in trapdoor knapsacks, IEEE Transactions on Information Theory, Vol.IT-24, No.5, pp , September Micali, S., Fair public key cryptosystems, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass.; MIT/LCS/TR-579.b; November Miller, V. S., Use of elliptic curves in cryptography, Advances in Cryptology Proceedings of CRYPTO 85, Lecture Notes in Computer Science, Vol. 218, pp , Springer-Verlag, Miyaji, A., Elliptic curve cryptosystems immune to any reduction into the discrete logarithm problem, IEICE Transactions on Fundamentals, Vol.E76-A, No. 1, pp , 1993., Elliptic curves suitable for cryptosystems, IEICE Transactions on Fundamentals, Vol.E77-A, No. 1, pp , 1994., A message recovery key signature scheme equivalent to DSA over elliptic curves, Advances in Cryptology Proceedings of ASIACRYPT 96, Lecture Notes in Computer Science, Vol. 1163, pp. 1-14, Springer-Verlag, Montgomery, P. L., Speeding the Pollard and elliptic curve methods of factorization, Math., Comp., pp , Moore, J. H., Protocol failures in cryptosystems, in G. J. Simmons, ed., CONTEMPORARY CRYPTOLOGY The Science of Information Integrity, IEEE Press, Morain, F., Building cyclic elliptic curves modulo large primes, Advances in Cryptology Proceedings of EUROCRYPT 91, Lecture Notes in Computer Science, Vol. 547, pp , Springer-Verlag, Naor, M. and M. Yung, Universal one-way hash functions and their chosen ciphertext 85

91 attacks, Proceedings of STOC, pp , and, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of STOC, pp , National Institute for Standards and Technology, Specifications for a digital signature standard, Federal Information Processing Standard Publication 186, 1991., The digital signature standard, Com. of the ACM, Vol.35, No.7, pp.36-40, Odlyzko, M., The future of integer factorization, Proceedings of Multimedia and Information Security, JAIST, pp , Ohta, K. and T. Okamoto, A modification of the Fiat-Shamir scheme, Advances in Cryptology Proceedings of CRYPTO 88, Lecture Notes in Computer Science, Vol. 403, pp , Springer-Verlag, Okamoto, E. and K. Tanaka, Keu distribution based in identification information, Electronics Letters, Vol.7, No.4, pp , May Okamoto, T. and A. Shiraishi, A fast signature scheme based on quadratic inequalities, Proceedings of the 1985 Symposium on Security and Privacy, IEEE, pp , April 1985., Fast public-key cryptosystems using congruent polynomial equations, Electronics Letters, Vol. 22, No. 11, pp , 1986., A fast signature scheme based on congruential polynomial operations, IEEE Transactions on Information Theory, Vol. 36, No. 1, pp , and K. Ohta, Divertible zero-knowledge interactive proofs and commutative random self-reducibility, Advances in Cryptology Proceedings of EUROCRYPT 89, Lecture Notes in Computer Science, Vol. 434, pp , Springer-Verlag, 1990., Provably secure and practical identification schemes and corresponding signature schemes, Advances in Cryptology Proceedings of CRYPTO 92, Lecture Notes in Computer Science, Vol. 547, pp , Springer-Verlag, 1993., A. Fujioka, and E. Fujisaki, An efficient digital siganture scheme based on an elliptic curve over the Ring Zn, Advances in Cryptology Proceedings of CRYPTO 92, Lecture Notes in Computer Science, Vol. 547, pp , Springer-Verlag, and K. Ohta, Survey of digital signatures, Proceedings of the Third Symposium on: State and Progress of Research in Cryptography, pp , Fondazone Ugo Bordoni, Ong, H. and C.P. Schnorr, Signatures through approximate representations by quadratic forms, Advances in Cryptology Proceedings of Crypto 83, Plenum 86

92 Press, 1984.,, and A. Shamir, An efficient signature scheme based on polynomial equations, Proceedings of the 16th Annual Symposium on the Theory Computing, pp , Phitzmann, M. and M. Waidner, Formal aspects of fail-stop signature, Fakultät für Informatic, University Karlsruhe, Deutschland, Report 22/29, Pohlig, S. and M. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Transactions on Information Theory, Vol. 24, pp , Pointcheval, D. and J. Stern, Security proofs for signature schemes, Advances in Cryptology Proceedings of EUROCRYPT 96, Lecture Notes in Computer Science, Vol. 1070, pp , Springer-Verlag, Pollard, J.M., Theorems on factorization and primality testing, Proceedings of Camb. Philos. Soc., Vol. 76, pp , 1974., A Monte Carlo method for factorization, BIT, Vol. 15, pp , and C. P. Schnorr, An efficient solution of the congruence x 2 +ky 2 =m (mod n), IEEE Transactions on Information Theory, Vol. IT-33, No.5, pp , September Pomerance, C., The quadratic sieve algorithm, Lecture Notes in Computer Science, Vol. 209, pp , Rabin, M. O., Probabilistic algorithms, Algorithms and complexity-new directions and recent results, Academic Press, 1976., Digitalized signatures and public-key functions as intractable as factorization, M.I.T. Laboratory for Computer Science, Technical Report MIT/LCS/TR-212, Rivest, R. L., A. Shamir, and L. Adleman, A metohd of obtaining digital signatures and public key cryptosystems, Communications of the ACM, Vol. 21, No. 2, pp , 1978a., Remarks on a proposed cryptanalytic attack on the MIT public-key cryptosystem, Cyrptologia, pp.62-65, 1978b. Rompel, J., One-way functions are sufficient for secure signatures, Proceedings of STOC, pp , Sakurai, K. and H. Shzuya, Relationships among the computational powers of breaking discrete log systems, Advances in Cryptology Proceedings of EUROCRYPT 95, Lecture Notes in Computer Science, Vol. 921, pp , Springer-Verlag,

93 Schneier, B., APPLIED CRYPTOGRAPHY, John Wiley & Sons, Inc., Schirokauer, O., D. Weber, and T. Denny, Discrete Logarithms: The Effectiveness of the Index Calculus Method, Algorithmic Number Theory, Lecture Notes in Computer Science Vol. 1122, Springer-Verlag, pp , Schnorr, C. P., Efficient signature generation for smart cards, Advances in Cryptology Proceedings of CRYPTO 89, Lecture Notes in Computer Science, Vol. 435, pp , Springer-Verlag, and H. H. Hörner, Attacking the Chor-Rivest cryptosystem by improved lattice reduction, Advances in Cryptology Proceedings of EUROCRYPTO 95, Lecture Notes in Computer Science, Vol. 921, pp. 1-12, Springer-Verlag, Schoof, R., Elliptic curves over finite fields and the computation of square roots mod p, Mathematics of Computation, Vol. 44, pp , Shamir, A. and R. E. Zippel, On the security of the Merkle-Hellman cryptographic scheme, IEEE Transactions on Information Theory, Vol. IT-26, No.3, pp , May 1980., Identity-based cryptosystems and signature schemes, Advances in Cryptology Proceedings of CRYPTO 84, Lecture Notes in Computer Science, Vol. 196, pp , Springer-Verlag, Shanks, D., Class number, a theory of factorization, and Genera, Proceedings of Syposium Pure Mathematics, AMS, Silverman, R. D., The multiple polynomial quadratic sieve, Math, Comp., Vol. 48, pp , Simmons, G. J. and M. J. Norris, Preliminary comments on the MIT public-key cryptosystem, Cryptologia, Vol.,No., pp , October 1977., A weak privacy protocol using the RSA crypto algorithm, Cryptologia, Vol.7,No.2, pp , April Stinson, D. R., CRYPTOGRAPHY Theory and Practice, CRC Press, Solovay, R. and V. Strassen, A fast Mote-Carlo test for primarity, SIAM J. Comp., Vol. 6, pp , Vallée, B., M. Girault, and P. Toffin, How to break Okamoto s cryptosystem by reducing lattice values, Advances in Cryptology Proceedings of EUROCRYPT 88, Lecture Notes in Computer Science, Vol., pp , Springer-Verlag, van Oorschot, P.C., A comparison of practical public key cryptosystems based on integer 88

94 factorization and discrete logarithms, in G.J. Simmons, ed., CONTEMPORARY CRYPTOLOGY The Science of Information Integrity, IEEE Press, Vaudenay, S., Hidden collisions on DSS, Advances in Cryptology Proceedings of CRYPTO 96, Lecture Notes in Computer Science, Vol. 1109, pp , Springer-Verlag, Von zur Gathen, J., D. Kozen, and S. Landau, Functional decomposition of polynomials, Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, pp , IEEE Press, Williams, H. C. and B.K. Schmid, Some remarks concerning the MIT public-key cryptosystem, BIT, 19, pp , 1979., A modification of the RSA public-key encryption procedure, IEEE Transactions on Information theory, Vol. IT-26, pp , 1980., Some public-key crypto-functions as intractable as factorization, Advances in Cryptology Proceedings of CRYPTO 84, Lecture Notes in Computer Science, Vol. 196, pp , Springer-Verlag, Wiener, M.J., Cryptanalysis of short RSA secret exponents, IEEE Transactions on Information theory, Vol. IT-36, No. 3, pp , Zheng, Y. and J. Seberry, Practical approaches to attaining security against adaptively chosen ciphertext attacks, Advances in Cryptology Proceedings of CRYPTO 92, Lecture Notes in Computer Science, Vol. 740, pp , Springer-Verlag, and T. Matsumoto, Breaking smart card based ElGamal signature and its variants, presented at the rump session in ASIACRYPT 96, available at yuliang/pubs/a96-rump.ps.z 89

95 1 1.1 a,b b 0 a = qb+r 0 r< b q, r r b a residue r=0 a b b a a b b a a, b LCM(a, b) a, b GCD(a, b) n (a-b) a b (mod n) a b n congruent congruence = 1 p 1 p prime number 1 n Euclid Euclid Step 1: m,n n 0 :=m; n 1 :=n Step 2: n i-1 :=q i- n i + n i+1 0 n i+1 n i (1,2,...) Step 3: n i+1 =0 d:=n i i Step p R p ={0, 1,, p-1} residue class R n GCD(a i, p) = 1 reduced residue class R p p (p) Euler Euler's function (p) = p Euler GCD(a, q) = 1 a (q) = 1 mod q 90

96 Euler Fermat 1.2 Fermat GCD(a, p) = 1 p a p-1 = 1 mod p Chinese remainder theorem 1.3 m 1, m 2,,m k M=m 1 m 2 m k x = d 1 mod m 1 x = d 2 mod m 2 x = d k mod m k Z M x 2 = a (mod p) a p quadratic residue a p quadratic non-residue p a p (a p) = +1-1 Legendre p (a p) = a (p-1)/2 (mod p) (a p) (ab p) = (a p)(b p) a = b (mod p) (a p) = (b p) p, q (p q)(q p) = (-1) (p-1)(q-1)/4 (-1 p) = (-1) (p-1)/2 1 (2 p) = (-1) (p+1)(p-1)/8 2 91

97 2 G G a,b G a b G G (G, ) 2.1 (G, ) (G, ) group a,b,c G (a b) c = a (b c) e G a G e a = a e = a e a G a b = b a = e b b a G 2 a,b a b = b a G Abelian group + additive group multiplicative group 1 a a -1 infinite group finite group G G order G S S G subgroup , (R,+, ) ring (R,+) (R {0}, ) x,y,z G x (y+z) = x y+x z (y+z) x = y x+z x Abelian ring +, Z Q R C n Z n Z,Q,R,C 2.3 R a 0 a b = 0 b 0 R 92

98 a zero divisor 2.4 R integral domain Z,Q,R,C Z n n n 2.5 R a 0 a b = 1 b R a 2.6 (F,+, ) field (F,+, ) x (F {0}, ) (x 0) x -1 Q,R,C Z 1 p Z p F (F,+, ) (F,+, ) finite field Galois Galois field F q(=p n ) q(=p n ) F,G F G q(=p n ) GF(q) F q 93

99 i.e., f(x,y) 3 f(x,y)=0 ( f / x=0 f / y=0) elliptic curve 3.2 p p 3 F q (q = p r ) {(x,y) y 2 = x 3 +ax+b (mod q) } (a, b F q ) 4a 3 +27b 2 0 O F q (x, y) 3.3 F q 2 P=(x 1, y 1 ) Q=(x 2, y 2 ) P+Q=(x 3, y 3 ) (a) Q O P + Q = Q + P = P (b) Q = -P x 2 =x 1 (mod q) y 2 =-y 1 (mod q) P + Q = Q + P = O (c) Q -P x 3 = {(y 2 - y 1 )/(x 2 - x 1 )} 2 -x 1 -x 2 (mod q) y 3 = {(y 2 - y 1 )(x 1 - x 3 )}/(x 2 - x 1 )- y 1 (mod q) (d) Q =P x 3 = {(3x 2 1 +a)/(2y 1 )} 2-2x 1 (mod q) y 3 = {(3x 2 1 +a)(x 1 - x 3 )}/2y 1 - y 1 (mod q) mod q P Q 2 x F q E(F q ) E(F q ) # E(F q ) Hasse 3.1 Hasse E(F q ) # E(F q ) 94

100 q-2q 1/2 +1 # E(F q ) q+2q 1/2 +1 E(F q ) n 1,n 2 (n 1 n 2 ) E(F q ) (n 1,n 2 ) n 2 n 1 q-1 E(F q ) # E(F q )= n 1 n 2 E(F q ) n 1 95