Key Sizes Selection in Cryptography and Security Comparison between ECC and RSA1. IntroductionClassification of cryptosystemsBasis of Security of Asymmetric Key CryptosystemsTime and Space required for FactorizationHistorical Factoring Records(Source: RSA bulletin board)Size Trends (Source: RSA bulletin board)Elliptic curve systemsCost Equivalent Key Sizes (Silverman, 2000)Max.Time of attack /2 x BudgetL (n)/ L(2512) = -------------------------------R. Silverman’s result (1999)Assumption: Pentium, 233 MHzFigure 1. For SDL and EC systems, suggested lower bounds for key sizesCOMPARING THE SECURITY OF ECC AND RSAConclusionConclusionReferencesReferencesKey Sizes Selection in Cryptography and Security Comparison between ECC and RSAProject: ECE 543Presented By: Vasant PatelSubmitted To: Dr. Kris Gaj1. Introduction• Why key size is important?– Security – Performance• What affect the security requirement?– Real value of data – Federal standards 1024 bit for RSA– Period of protection• Equivalence of attack efforts– computationally equivalent security vs. cost equivalent securityClassification of cryptosystems• Symmetric key cryptosystems• Asymmetric key cryptosystems1. Classical asymmetric systems 2. Elliptic curve systemsBasis of Security of Asymmetric Key CryptosystemsCryptosystem Basis of SecurityRSA FactorizationDL DLPECC EC DLPTime and Space required for Factorization• For NFS:– expected require time is proportional to L[n] = exp ( ( 1.9229 + o(1)) ( log n)1/3 (log log n) 2/3))The required space scale is = SQRT (L[n])Time SpaceL(2576)/L(2512) ~ 10.9 SQRT (L(2576)/L(2512)) ~ 3.3L(2640)/L(2512) ~ 101 SQRT (L(2640)/L(2512)) ~ 10.0L(2704)/L(2512) ~ 835 SQRT (L(2704)/L(2512)) ~ 29L(2768)/L(2512) ~ 6 x 103SQRT (L(2768)/L(2512)) ~ 77L(21024)/L(2512) ~ 7 x 103SQRT (L(21024)/L(2512)) ~ 2650L(22048)/L(2512) ~ 9 x 1015SQRT (L(22048)/L(2512)) ~ 9 x 103Historical Factoring Records(Source: RSA bulletin board)Year Size Number Who Method Hardware1970 39 2128+ 1 Brillhart/Morrison CFRAC IBM mainframe1978 45 2223– 1 Wunderlich CFRAC IBM mainframe1981 47 3225– 1 Gerver QS HP - 30001982 51 591– 1 Wagstaff CFRAC IBM mainframe1983 63 1193+ 1 Davis/Holdridge QS Cray1984 71 1071– 1 Davis/Holdridge QS Cray1986 87 5128+ 1 Silverman MPQS LAN Sun – 3’s1987 90 5160 + 1 Silverman MPQS LAN Sun – 3’s1988 100 11104+ 1 Internet MPQS Distributed1990 111 2484+ 1 Lenstra/Manasse MPQS Distributed1991 116 10142+ 1 Lenstra/Manasse MPQS Distributed1992 129 RSA –129 Atkins MPQS Distributed1996 130 RSA – 130 Montgomery GNFS Distributed1998 140 RSA – 140 Montgomery GNFS Distributed1999 155 RSA – 155 Montgomery GNFS DistributedSize Trends (Source: RSA bulletin board)0501001502001969 1974 1979 1984 1989 1994 1999 2004YearKey Size(Decimal Digits)Elliptic curve systems• Certicom challenge• In 1996 Special-purpose hardware design• Certicom:131-bit EC systems is currently infeasible to break using s/w and h/w attacks.Cost Equivalent Key Sizes (Silverman, 2000)Max.Time of attack /2 x BudgetL (n)/ L(2512) = ----------------------------------------------------300 x (100 + 0.5 Sqrt (L (n)/ L(2512)) x 64)Assumption: PIII, 500 MHz SymmetricKeybitsEC keybitsRSA keybitsTime toBreakMachines Memory56 112 430 > 5 minutes 105Trivial80 160 760 600 months 4300 4 GB96 192 1020 3 million yr. 114 170 GB128 256 1620 1016 Year 0.16 120 TBR. Silverman’s result (1999)Assumption: Pentium, 233 MHzKey Size EquivalentRSA/DSA ECC Symm. Arith. Op.428 110 51 5.5 x 1017512 119 56 1.7 x 1019768 144 69 1.1 x 10231024 163 79 1.3 x 10262048 222 109 1.5 x 1035RAM Required for NFSKey SizesIn BitsSieve memory Matrix Memory332 24 Mbytes 128 Mbytes428 64 Mbytes 2 Gbytes512 160 Mbytes 20 Gbytes1024 ~256 Gbytes ~100 GbytesFigure 1. For SDL and EC systems, suggested lower bounds for key sizesProgress9010011012013014015016017019821985198819911994199720002003200620092012201520182021YearsKey Sizes in BitsCOMPARING THE SECURITY OF ECC AND RSA• Hardness of Mathematical Problems• Study time period• Sub exponential algorithm for IFP• Only exponential algorithm for ECDLPConclusion• RSA more trusted• More implementations of RSA• ECC is grown-up technology• ECC used primarily in constrained environmentConclusionSecure Key Sizes:Factorization Discrete Log ECC Discrete LogANSI ≥1024 ≥1024 ≥160NIST 1024 ≥ L ≥ 512 • Generating Digital signature• ECDSA is faster, then DSA, and RSA• ECDSA is a few times faster then DSA• Verifying Digital signature– RSA is fastest (Several times faster than ECDSA and DSA)– ECDSA is faster than DSA (close)• RSA: Very fast verify, slow signing• ECDSA, DSA: Slow verify, fast signing• Encryption/ Decryption Comparison– RSA: Very fast encryption, slow decryption, slow key exchange (due to key pair gen.)– ECC: Slow encryption, faster decryption, much fasterReferences• A.K Lenstra, E.R.Verhul, “Selecting Cryptographic key sizes” Nov 14 1999.• RSA laboratories bulletin board.• R. Rivest, R. Silverman, Are ‘strong' primes needed for RSA? April 14,19917.• R.D. Silverman. Exposing the Mythical MIPS Year, IEEE Computer, August 1999, 22-26.• S. Contini, Public key algorithm selection for security application, RSA Lab, 1999.• M. Wiener, Performance comparison of public key cryptosystem, RSA Laboratories’Cryptobytes, v.4,no.1(1998), 1-5; also at www.rsa.com/rsalabs/pubs/cryptobytes.• Brent, R. Some parallel algorithm for Integer factorization.• www.bsa.org/policy/encryption/cryptographers_c.html, January 1996.• S. Cavallar, B. Dodson, A.K. Lenstra, B. Murphy, P.L. Montgomery, H.J.J. te Riele, et al. Factorization of a 512-bit RSA modulus, manuscript, October 1999.• www.counterpane.com/speed.html.• www.certicom.com/chal/ download/paper.ps, 1998.• D.B. Johnson, ECC, Future Resiliency and High Security Systems, March 30, 1999, available from www.certicom.com.• P.C. Kocher, Breaking DES, RSA Laboratories’ Cryptobytes, v. 5, no 2 (1999) ; also at www.rsa.com/rsalabs/pubs/cryptobytes.• A.K. Lenstra, A. Shamir, Analysis and optimization of the TWINKLE factoring device, manuscript, October 1999.• P.L. Montgomery, letter to the editor of IEEE Computer, August 1999.• A.M. Odlyzko, The future of integer factorization, RSA Laboratories’Cryptobytes, v.1, no.2 (1995), 5-12; www.research.att.com/~amo/doc/crypto.htmlor www.rsa.com/rsalabs/pubs/cryptobytes.• A. Shamir,
View Full Document
Unlocking...