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 []
ヒストグラム...7. 度頻.. 頻度理論値..........7.........7.........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
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. 7. 7. 77.. {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
bit ( ) Report ECC RSA NIST [] Lenstra [] RSA Labs [7] 7 NESSIE [] IETF [] ECRYPT II [] ECDLP GNFS year ECC ECCK ECCp GNFS 7 7 7 7 7 7 7 (ECC) (RSA). Pollard- ECDLP ECDLP
bit / bit / 7.. 7. 7.7 7. 7. 7..7 7. 7.77...77 7..... 7....7 (Intel Core Quad CPU. GHz) (factor base) (relation) CPU Lanczos Wiedemann. -bit -bit iteration
処理回数 / 秒 素体楕円曲線 冪楕円曲線 ビット数.% %... CPU Jacobian C Certicom Certicom Challenge ECCp- 7 ECC- (CPU MHz []) [] [] CPU bit 7 cycle (Pentium III) cycle [] ECC- Cell SPU 7cycle(
( ) Koblitz (bit) (bit) (bit).7...7. 7..... 7..7.7.7.7 77. 7.. 7. 7. 7....... 7. 7. 7. 7 7.7 7.7 7.7 ),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
7 ( ) Athlon.GHz 7.. ( ) ( ) FLOPS 7.7.. 7. ( ) 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
( FLOPS ) 7.7.. 7. ( FLOPS) ( ). 7....7. 7.... 7.7. 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
7 7 7 7 7 7 RSA RSA RSA FLOPS RSA AES (7 cycle/block []) 7 RSA7 ( ) ( ) RSA RSA 7 NIST SP-7
RSA RSA RSA7 RSA 数 トッビ円楕 素体 ( 上限 ) 素体 ( 下限 ) 冪 ( 上限 ) 冪 ( 下限 ) RSA7 RSA RSA RSA 解読計算量 ( の冪 ) RSA RSA ( ) RSA Koblitz 7 7 7 7 77 7 7 7 7 7 [] 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 ). http://www.certicom. com/pdfs/cert ecc challenge.pdf
[] 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,. http://www.ams.org/journals/mcom/--/s-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,. http://www.cacr.math.uwaterloo.ca/techreports//corr-.ps. [] 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 ). http://www.rsa.com/rsalabs/ node.asp?id= [] NESSIE, NESSIE Security Report, February,. http://www.cosic.esat.kuleuven. 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. http://www.apps.ietf.org/rfc/rfc7. 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. http://www.ecrypt.eu.org/documents/d.spa.7.pdf [] 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, /,. http://eprint.iacr.org// [7] D. Bernstein, Speed Reports for Elliptic-Curve Cryptography,. http://cr.yp.to/ ecdh/reports.html [],,,,, (SCIS ),. [],,,,, (SCIS ),. [],,,, RSA, (SCIS ),. [] TOP Supercomputing Sites,. http://www.top.org/ ( / ) ( / ) ( / ) ( / )
security white paper@ml.fujitsu.com