楕円曲線暗号と RSA 暗号の安全性比較

Size: px

Start display at page:

Download "楕円曲線暗号と RSA 暗号の安全性比較"

さわたかひ
5 years ago
Views:

1 RSA, RSA RSA 7 NIST SP-7 Neal Koblitz Victor Miller ECDLP (Elliptic Curve Discrete Logarithm Problem) RSA Blu-ray AACS (Advanced Access Control System) DTCP (Digital Transmission Content Protection) RSA ECC Challenge RSA (ECDLP) E ( GF (p) y = x + ax + b GF ( n ) y + xy = x + ax + b) S S S T T = [d]s d Anomalous, Supersingular ECDLP Pollard ECDLP RSA (NICT) (SCIS ) RSA []

2 ヒストグラム...7. 度頻.. 頻度理論値 m ore データ区間 (-bit ) E S T (E, S, T ) T = [d]s d [, n ] ( n ) [u]s + [v]t = [u ]S + [v ]T u, v, u, v [v v ]T = [u u ]S d = (v v )(u u ) mod n ECDLP u, v, u, v (u u, v v ) Paul L H : S {,,..., L} L H f : S S f(x) = X + [a i ]S + [b i ]T, (H(X) = i) a, b,..., a L, b L [, n ] f S X f S {X, X,...} X i = f(x i )(i ) X X [u ]S + [v ]T S, T f X = f(x ) [u ]S + [v ]T S, T X i = [u i]s + [v i]t, (i ) S X i ( ) X s+t X t i s + t X i = X i s X i, X i s i X i = X i s [u i ]S + [v i ]T = X i = X i s = [u i s ]S + [v i s ]T [u]s + [v]t = [u ]S + [v ]T X i (E, S, T ) f

3 NIST SP-7 Security Parameter bit Block FFC IFC ECC (DSA,DH) (RSA) (ECDSA) TDES L = N = k = f = TDES L = N = k = f = AES- L = 7 N = k = 7 f = AES- L = 7 N = k = 7 f = AES- L = N = k = f = + L:, N:, k:, f: ANSI X. ECDLP n πn/ 7G MIPS {X, X,...} πn + θ Iteration [, ] Koblitz. ECDLP [, ] ECDLP µ = πn/ = %. % 7% /. NIST SP-7 ANSI X. [] ECDLP. MIPS Odlyzko.% MIPS [] Jaguar.7 FLOPS (.7 MIPS) [] ECDLP Jaguar

4 bit ( ) Report ECC RSA NIST [] Lenstra [] RSA Labs [7] 7 NESSIE [] IETF [] ECRYPT II [] ECDLP GNFS year ECC ECCK ECCp GNFS (ECC) (RSA). Pollard- ECDLP ECDLP

5 bit / bit / (Intel Core Quad CPU. GHz) (factor base) (relation) CPU Lanczos Wiedemann. -bit -bit iteration

6 処理回数 / 秒素体楕円曲線冪楕円曲線ビット数.% %... CPU Jacobian C Certicom Certicom Challenge ECCp- 7 ECC- (CPU MHz []) [] [] CPU bit 7 cycle (Pentium III) cycle [] ECC- Cell SPU 7cycle(

7 ( ) Koblitz (bit) (bit) (bit) ),7 cyle (bitslice ). [7] (NIST P-) 7 cycle (Athlon) [] / iteration function iteration function 7/( + ) = 77 cycle/iteration N 77 (N/) cycle/iteration. [] (ECC-, NIST-) 7

8 7 ( ) Athlon.GHz 7.. ( ) ( ) FLOPS ( ) 7cycle/iteration (Cell SPE GHz, Bitslice ) N 7 (N/) cycle/iteration Koblitz Koblitz. (+. ( ) +. (L [Gallant []])). 7 (N/) cycle/iteration. FLOPS % iteration ADD Koblitz Gallant [] Negation Map 77cycle/iteration bit 7cycle/iteration bit Koblitz. (FLOPS) ( Y = ) = / = π N / 77 (N/) /Y = π N / 7 (N/) /Y Koblitz = π N /N/. 7 (N/) /Y CRYPTREC Report. RSA

9 ( FLOPS ) ( FLOPS) ( ) CRYPTREC Report. Athlon.GHz GB 7 CRYPTREC Report Athlon.GHz ( ) ( ).GFLOPS (=. FLOPS) FLOPS L N (/, (/) / + C) L N (s, c) = exp(c(log(n) s log(log(n)) s ), (/) / =. C =., log =. RSA NIST SP-7 RSA

10 RSA RSA RSA FLOPS RSA AES (7 cycle/block []) 7 RSA7 ( ) ( ) RSA RSA 7 NIST SP-7

11 RSA RSA RSA7 RSA 数トッビ円楕素体 ( 上限 ) 素体 ( 下限 ) 冪 ( 上限 ) 冪 ( 下限 ) RSA7 RSA RSA RSA 解読計算量 ( の冪 ) RSA RSA ( ) RSA Koblitz [] A. Odlyzko, The Future of Integer Factorization, CryptoBytes, vol., no., pp.-,. ftp://ftp.rsasecurity.com/pub/cryptobytes/crypton.pdf [] Certicom, Certicom ECC Challenge, 7 (revised November ). com/pdfs/cert ecc challenge.pdf

12 [] ANSI, The Elliptic Curve Digital Signature Algorithm (ECDSA), ANSI X.-,. [] R. Gallant, R. Lambert, and S. Vanstone, Improving the Parallelized Pollard Lambda Search on Anomalous Binary Curves, Mathematics of Computation, vol., no., pp.- 7,. S-7---.pdf [] M. Brown, D. Hankerson, J. Lopez, and A. Menezes, Software Implementation of the NIST Elliptic Curves over Prime Fields, technical report, CORR -, University of Waterloo,. [] A. Lenstra and E. Verheul, Selecting Cryptographic Key Sizes, Journal of Cryptology, vol., no., pp.-,. [7] RSA Labs., A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths, RSA Labs Bulletin, no., April (Revised November ). node.asp?id= [] NESSIE, NESSIE Security Report, February,. be/nessie/deliverables/d-v.pdf [] H. Orman and P. Hoffman, Determining Strengths for Public Keys Used for Exchanging Symmetric Keys, IETF RFC 7/BCP, April. html [] D. Bernstein, Cuvre: New Diffie-Hellman Speed Records, Proceedings of PKC, LNCS, pp.7-, Springer-Verlag,. [] CRYPTREC, CRYPTREC Report,, March 7. [] T. Gueneysu, C. Paar, and J. Pelzl, Attacking Elliptic Curve Cryptosystems with Special Purpose Hardware, Proceesings of ACM SIGDA 7, 7. [] NIST, Recommendation for Key Management-part: General (Revised), SP-7, August 7. [] M. Matsui and J. Nakajima, On the Power of Bitslice Implementation on Intel Core Processor, Proceedings of CHES 7, LNCS 77, pp.-, Springer-Verlag, 7. [] ECRYPT II, ECRYPT Yearly Report on Algorithms and Keysizes (-), July. [] D. Bailey, B. Baldwin, L. Batina, D. Bernstein, P. Birkner, J. Bos, G. van Damme, G. de Meulenaer, J. Fan, T. Güneysu, F. Gurkaynak, T. Kleinjung, T. Lange, N. Mentens, C. Paar, F. Regazzoni, P. Schwabe, and L. Uhsadel, The Certicom Challenges ECC-X, IACR eprint Archive, /,. [7] D. Bernstein, Speed Reports for Elliptic-Curve Cryptography,. ecdh/reports.html [],,,,, (SCIS ),. [],,,,, (SCIS ),. [],,,, RSA, (SCIS ),. [] TOP Supercomputing Sites,. ( / ) ( / ) ( / ) ( / )

13 security white

1 2 1.1............................................ 3 1.2.................................... 7 1.3........................................... 9 1.4..

2010 8 3 ( ) 1 2 1.1............................................ 3 1.2.................................... 7 1.3........................................... 9 1.4........................................