RSA署名方式の安全性を巡る研究動向について

Size: px

Start display at page:

Download "RSA署名方式の安全性を巡る研究動向について"

かずひろえいさか
5 years ago
Views:

1 RSA RSA RSA RSA RSA RSA PSSRSA PSS RSARSA PSS RSA PSS RSARSA-PSS

2 RSARSA PKCS ISO ISO IPS ANS X RSARSA RSA RSA RSA RSA RSA RSA bit RSA RSA PSS RSA PSS RSA ISO PKCSVer

3 RSA PSS RSA PSS RSA RSARSA RSA RSA PSS RSA PSS RSA PSS RSA Rivest, Shamir, and Adleman RSA RSAp q n = p q p 1 q 1L L ee d=1(mod L) d (e, n)d

4 PKI public key infrastructure (e, n) d P C C P e, n d RSA P (e, n) C =P e mod nc C d P=C d mod n P M M S M S M S e mod n d S M d mod n en RSARSA MSS SM RSA M d S=M d mod nm SSM

5 e, nm=s e mod n S e, n M RSA d e, n RSA f f(m )=M e mod ne, nrsa RSARSA RSA f f 1 f 1 (M )=M d mod n f PC = f (P) =P e mod n f 1 C P = f 1 (C ) =C d mod n M f 1 S = f 1 (M ) =M d mod n S f f (S) = S e mod nm S RSARSA RSA RSA RSA RSA d RSA n d RSA n

6 n d RSA drsa RSA drsa drsa RSA n d n n nd RSA RSA n

7 n RSA RSA n drsa n d RSA RSA RSA RSA RSA RSA CNS

8 RSAn RSA RSA RSA n n n p q nn n n nn trial division nn k k k RSA n n ρ Pollardp 1Pollard Lehman n p 1 p q n ρ p 1 Lenstra Lenstra et al.p 1 Koblitz n = p qp q n

9 ρ p 1 p +1 ρ Pollard 1975 x 0 x i+1 = x 2 i +1(mod n) x a x b (a b)nn n x a x b n p p 1 p 1 Pollard 1974 nabb k(a k mod n) 1 n nn B kn

10 p+1p 1 p+1 Williams p q nlehman n t 0 t 02 nt 02 n = s 2 s t 0 s sn = t 2 i s 2 = (t i s)(t i +s) t i s t i +s n p 1 p+1 Lenstra n a x 1 y 1 b = y 12 x 13 a. x 1 (mod n) E Y 2 = X 3 +ax+b (mod n) E x 1, y 1 T k T k kt = (x k, y k ) = (c k /d k2, e k /d k3 ) d k nn nk En Y 2 =X 3 +ax+b O P,Q O=O P+O=O+P=P P= (x, y)=(x, y) ( P= (x, y)) P Q P+Q= R R PQ P=Q 2P= R R P

11 p 1p+1 n pp 1 p+1 p 1p+1 p T 2 = S 2 (mod n)t S Pomerance a n Q(x) = (x+α) 2 nq(x) x i Q(x i )p j Q(x i ) = p a 1 1. p a p a r r a j Q(x i ) Π Q(x i )=Πp2. a j j (mod n) Q(x i ) Q(x i ) T S = Π p a = ΠQ( x j i) j T 2 = S 2 (mod n) T ST ±S(mod n)t S T S n T+S nn A.K.A. K. LenstraH.W.H. W. Lenstra Manasse Lenstra et al.t S f (x)d f (x)= 0α α Z[α] Z[α] Z[α]Z[α] ϕ Z[α]Z/nZ ϕ : Z[α] Z/nZ a+bα a+bc (a b). a+bαz[α]a+bα = p 1.p 2.. p k p i Z/nZ

12 a+bc= ϕ (a+bα) =ϕ (p 1.p 2.. p k )=ϕ (p 1 ). ϕ (p 2 ).. ϕ (p k ) (mod n), a+bc = t ϕ (p 1 ). ϕ (p 2 ).. ϕ (p k )=s(s, t) s,t (Π t i ) 2 =(Π s j ) 2 (mod n) s, t s,tt=(π t i ) S=(Π s j ) T 2 = S 2 (mod n) T S T ±S (mod n) T S T S n T + S n n n = p. q O L O (exp(1/2 log n) ) L n (1; 1/2) ρ p p + O (exp(1/4 log n) ) O (q 1 ), q 1 p 1 O (q 2 ), q 2 p +1 L n (1; 1/4) O (exp(1/3 log n) ) O (exp( (1+o (1))(log n) 1/2 (loglog n) 1/2 ) ) O (exp( (1+o(1))(log n) 1/2 (loglog n) 1/2 ) ) L n (1; 1/3) L n (1/2; 1+o (1)) L n (1/2; 1+o (1)) O (exp((64/9) 1/3 +o (1))(log n) 1/3 (loglog n) 2/3 )) L n (1/3; (64/9) 1/3 +o(1)) O(k d )k d L n (r; c) = O (exp (clog n) r (loglog n) 1 r )). o(1) n

13 ρp 1p+1 nk ρ e 1/2.k e 1/3.k e 1/4.k ρ k L (L n (r; c) L exp (c. log n) exp (c. loglog n) r =1 r = 0 L L n (1/ 2;1+o(1)) L n (1/ 2;1+o(1)) L n (1/ 3; (64/ 9) 1/3 +o(1)) r Lr Shor Shor n RSA Lenstra and Verheul Silverman RSARSA RSA

14 RSA bitbit bit n n RSAn bit RSA RSA RSA FAQ /rsalabs/faq/3-1-5.html

15 RSA DES Lenstra and Verheul DESbit DES MIPS Blaze et al.des DES DES DESRSA DESMIPS MIPS bit MIPS RSA bit bit bit

16 Lenstra and Verheul 2001 Silverman Pentium bit

17 bit bit n RSA RSA RSA RSA mod n M 1 M 2 M 1 M 2 M 1 M 2 M 1 S(M 1 )M 2 S(M 2 ) RSA M 1. M 2 S(M 1.M 2 ) S(M 1.M 2 )=(M 1.M 2 ) d (mod n) = (M 1 ) d.(m 2 ) d (mod n) = [(M 1 ) d (mod n)].[(m 2 ) d (mod n)] (mod n) = S(M 1 ).S(M 2 ) (mod n). multiplicativity attack X MX MX.M(mod n) X

18 X MS(M) Y= X.M(mod n) YS(Y) S(M) mod ns(m) 1 S(Y) XS(X) S(Y).S(M) 1 = S(X.M).S(M) 1 (mod n) = S(X).S(M).S(M) 1 (mod n) = S(X) (mod n). X.M(mod n) X X M X.M(mod n) S(M 1 ) S(M 2 ) S(M 1. M 2 ) RSA SSL VerRSA Bleichenbacher

19 S (M) =M d mod n S (M) = (R(M)) d mod n R Y =X M (mod n) R (Y ) = R (X) R (M)(mod n) Y Y Y Z = R (X) R (M)(mod n) Z Z = R(Y ) Y X M S (M) =(H(M)) d mod n H H (Y ) = H (X) H (M) (mod n) Y H (Y ) Y S (M) =(T (M)) d mod n T T (Y ) = T (X) T (M)(mod n) Y n bit bit bit R R(Y) =R(X). R(M) (mod n), Y Z = R(X).R(M) (mod n) Y n bitz bit Z = R(Y) bit Y R(X).R(M) (mod n) bitbit Y

20 Y M R(M)= w. M + k w k w = 1 k= 0 w = 2 a k= 0 w = 1 k = 0 M w = 2 a k = 0 w M a bit 0 0 M = R (M) M 0 0 = R (M) w = 1 k = [ ] w = 2 a k = [ ] a bit a bit a bit M w M a bit M 0 0 = k M = k = = 101 M = R (M) M 101 = R (M) RSA RSA De Jonge and ChaumX. M(mod n) Y Y

21 Girault and Misarsky RSA X z z = k/w{1 (w. X + k)} mod n (w. X+ k)m = Y+Z (mod n), (M,Y) (M,Y) (w. X+ k) (w. M+ k) = (w. Y+ k) (mod n), R(X). R(M) = R(Y) (mod n) M Y ISO MisarskyISO ISO

22 H RSA H(Y) =H(X). H(M) (mod n), Y H(X). H(M) (mod n) H(Y)Y RSA Desmedt and Odlyzko MH MH(M) H(M) = p 1. p 2.. p k p i k M M S(M)S(M) S(M) =H(M) d mod n = p 1 d. p 2 d.. d p i (mod n) 1 i k p i dmod n d ( p i mod n) d p i mod n

23 bit RSARSA FDH n RSA-FDH RSA PSS PKCS VerPKCS ISO ISO PKCS RSA PKCS PKCSVer S/MIME PKCS PKCSVerPKCS RSA PSS S/MIME Secure Multipurpose Internet Mail ExtensionRSA data security Microsoft Outlook Express IETF Internet Engineer Task ForceS/MIME

24 PKCS RSA PSS M Hh bitsr8k bit MH(M) IDH(M)T(8t bit ) PS8(k t ) bitbit bitbit PS = [ ] 16 bit 8(k t 3) bit 8 bit SR = [PS T ] SR d S = SR d mod n Se S e mod n M H S e mod n SR ISO ISO nbit bitiso nbit

25 bitbit MU(M) S = U(M) d mod n MS More-data bit Padding field Hash field Trailer U(M) = M 848 bit SHA-1(M) Header 2 bitrecovery field Header U(M)bit More-data bit Padding field U(M) bit Recovery field bit Hash field(m)bit Trailer U(M) = S e mod nu(m) ISO M ISO n CNS Coron, Naccache, and Stern ISO bit CNS bit CNS

26 U(M)M U(M)a. n 2 8. U(M) M a nm H(M) a. n 2 8. U (M) U(M)bit U(M) = Mbit H (M) n bit an abitbit bit bit a. na. nbit ybit y bit x a.n= x(848 bit) y(176 bit) Mbit x a. n 2 8. U(M) bitbit a. n 2 8. U(M) = x(848 bit) y(176 bit) = x H(M) y [H(M) ] M M bit x bit z M 176 a. n 2 8. U(M) M M M M U(M) d mod n RSA

27 RSA PKCS

29 RSAn RSA RSA PSS RSA Bellare and RogawayPKCS RSA PSS RSA

30 RSA PSSPSSRSA RSA RSA RSA PSS RSA PSS RSA PSS RSA PSS RSA PSS RSA PSS RSA PSS RSA PSS RSA PSS RSA PSSRSA PSS RSA PSS RSA PSS RSA PSSRSA PSS Bellare and RogawayRSA PSS g 1 g 2 g RSA PSS RSA PSS

31 M (k bit)r (k r bit) k h bit hk h bit k r bit g 1 k h bit (k k r k h 1)bit g 2 S w= h (M r ), r = g 1 (w ) r, S = U(M) d mod n U(M) =(0 w r g 2 (w)). M (k bit)r (k r bit) k h bit hk h bit (k k h )bit g S w= h(m r ), r = g(w ) (r 0 0 ), S = U(M) d mod n U(M) =(0 w r )). M r M r h w h w g g 1 g 1 (w) g(w) r g 2 r 0 0 = = 0 w r * g 2 (w) 0 w r * RSA PSSRSA PSS g 1 g 2 g M R M NR RSA PSS RSA PSS M NR RSA PSSRSA PSS

32 S w= h(m R r ), r = g 1 (w ) r, M R = g 2 (w ) M R, S = U(M) d mod n U(M) =(0 w r M R ) S w= h(m r ), r = g(w ) (r 0 01 M R ), S = U(M) d mod n U(M) =(0 w r ). M M M R M NR M R M NR r M R h r h w w g g 1 g 1 (w) r g 2 g 2 (w) M R r g (w) 0 01 M R 0 w = r * = M R * 0 w = r * RSA PSSR RSA PSSRIEEE P1363 Institute of Electrical and Electronics EngineersRSA PSSRh RSA PSS RSA PSS RSA PSSRM R RSA PSS IEEE Institute of Electrical and Electronic Engineers PIEEE

33 RSA PSSR RSA PSSR E(k E bit) bit HashID (16 bit) S w= h((0 0) 64 h(m) r ), r = g(w ) (0 01 r ), S = U(M) d mod n, U(M)= (0 r w E ) E(k E bit) bit HashID (16 bit) S w= h(( M R ) 64 M R h(m NR ) r ), r = g(w ) (0 01 M R r ), S = U(M) d mod n, U(M)= (0 r w E ) M M h M R M NR h (0 0) 64 h(m) r ( M R ) 64 M R h(m NR ) r h h g w g w g (w) 0 01 r g (w) 0 01 M R r = = 0 r * w E 0 r * w E (0 0) 64 bit ( M R ) 64 M R bit RSA PSS

34 RSA PSS PKCSVerISO CRYPTREC CRYPTREC Report CRYPTREC CRYPTREC CRYPTRECRSARSA PSS CRYPTREC Report RSA

35 RSA PSS RSA RSA PSS NESSIE New European Schemes for Signature, Integrity and Encryption Knudsen Biham NESSIE NESSIE RSA PSSRSA PSS PKCS Public-Key Cryptosystem StandardRSA PKCS PKCSRSA PKCS RSA PKCSVer RSA PSS ISO ISO ISO RSA PSS

36 RSARSA n RSA RSA PKCS PKCS PKCS ISO RSA PSS RSA RSA PSS RSA PSS RSA PSS RSA PSS RSA PSSRSA PSS

37 RSA Bellare, Mihir, and Phillip Rogaway, The exact security of digital signatures How to sign with RSA and Rabin, Proceedings of EUROCRYPT 96, LNCS 1070, Springer-Verlag, 1996, pp , and, PSS: Provably Secure Encoding Method for Digital Signature, Submission to IEEE P1363, Blaze, Matt, Whitfield Diffie, Ronald L. Rivest, Bruce Schneier, Tsutomu Shimomura, Eric Thompson, and Michael Wiener, Minimum key Lengths For Symmetric Ciphers To provide Adequate Commercial Security, A Report By An Ad Hoc Group Of Cryptographers And Computer Scientists, January Bleichenbacher, Daniel, Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS#1, Proceedings of CRYPTO 98, LNCS 1462, Springer-Verlag, 1998, pp Buchmann, Johannes A., Introduction to Cryptography, Springer-Verlag, Coron, Jean-Sebastin, Optimal security proofs for PSS and other signature schemes, ( David Naccache, and Jacques Stern, On the Security of RSA Padding, Proceedings of CRYPTO 99, LNCS 1666, Springer-Verlag, 1999, pp Davis, James A., and Diane B. Holdridge, Factorization using the quadratic sieve algorithm, Proceedings of CRYPTO 83, Springer-Verlag, 1983, pp De Jonge, Wiebren, and David Chaum, Attacks on Some RSA Signatures, Proceedings of CRYPTO 85, LNCS 218, Springer-Verlag, 1986, pp Desmedt, Yvo, and Andrew M. Odlyzko, A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, Proceedings of CRYPTO 85, LNCS 218, Springer-Verlag, 1986, pp

38 Girault, Marc, and Jean-Francois Misarsky, Selective Forgery of RSA Signatures Using Redundancy, Proceedings of EUROCRYPT 97, LNCS 1233, Springer-Verlag, 1997, pp Institute of Electrical and Electronics Engineers, IEEE P1363a/D9 (Draft Version 9) Standard Specifications for Public Key Cryptography: Additional Techniques, June 2001., Std : Standard Specifications for Public Key Cryptography, August Jonsson, Jakob, Security Proofs for the RSA-PSS Signature Scheme and Its Variants, ( Koblitz, Neal, A Course in Number Theory and Cryptography, Springer-Verlag, Lehman, Richard S., Factoring large integers, Mathematics of Computation, Vol.28, 1974, pp Lenstra, Arjen K., Hendrik W. Lenstra, Jr., Mark S. Manasse, and John M. Pollard, The number field sieve, Proceedings of ACM Annual Symposium on Theory of Computing, 1990, pp , and Eric R. Verheul, Selecting Cryptographic Key Sizes, Journal of Cryptology, Vol.14, No.4, Springer-Verlag, 2001, pp Lenstra, Hendrik W., Jr., Factoring Integers with Elliptic Curves, Annals of Mathematics, Vol.126, 1987, pp Menezes, Alfred J., Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptology, CRC Press, Misarsky, Jean-Francois, A Multiplicative Attack Using LLL Algorithm on RSA Signatures with Redundancy, Proceedings of CRYPTO 97, LNCS 1294, Springer-Verlag, 1997, pp , How (Not) to Design RSA Signature Schemes, Proceedings of PKC 98, LNCS 1431, Springer-Verlag, 1997, pp Pollard, John M., Theorem on factorization and primality testing, Mathematical Proceedings of the Cambridge Philosophical Society, Vol.76, 1974, pp , A Monte Carlo method for factorization, BIT, Vol.15, 1975, pp Pomerance, Carl, Analysis and comparison of some integer factoring algorithms, in Number Theory and Computers, Math. Centrum Tracts, No.154, Part I and No.155, Part II, 1983, pp Rivest, Ronald L., Adi Shamir, and Leonard Adleman, A method of obtaining digital signatures and public key cryptosystems, Communications of the ACM, Vol.21, No.2, 1978, pp RSA Laboratories, PKCS#1 v1.5: RSA Cryptography Standard, 1993., PKCS#1 v2.0: RSA Cryptography Standard, 1998., PKCS#1 v2.1: RSA Cryptography Standard, 2001., RSA-PSS Signature Scheme with Appendix, Submission to the NESSIE project, September Shor, Peter, Algorithms for Quantum Computation: Discrete Logarithms and Factoring, Proceedings of 35th Annual Symposium on Foundations of Computer Science, 1994, pp

39 Silverman, Rovert D., A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths, RSA Laboratories Bulletin, No.13, April 2000 (Revised November 2001). ( Silverman, Joseph H., and John Tate, Rational Points on Elliptic Curves, Springer-Verlag, Williams, Hugh C., A p+1 method of factoring, Proceedings of CRYPTO 83, Springer-Verlag, 1983, pp

ICカードに利用される暗号アルゴリズムの安全性について：ENV仕様の実装上の問題点を中心に

ICカードに利用される暗号アルゴリズムの安全性について：ENV仕様の実装上の問題点を中心に IC IC IC ICIC EMVEMV IC EMVIC EMV ICEMVRSAkey TDES TDES-MAC E-mail: masataka.suzuki@boj.or.jp NTTE-mail: kanda.masayuki@lab.ntt.co.jp IC IC IC IC EMV JCCA ICJCCA ICEMV EMVIC EMV EMV EMVEMVCo EMV EMV EMVICIC