Cryptography – Key management – Key distribution
Reexamination Certificate
2011-08-02
2011-08-02
Revak, Christopher A (Department: 2431)
Cryptography
Key management
Key distribution
C380S030000, C380S280000, C708S492000
Reexamination Certificate
active
07991162
ABSTRACT:
A method and apparatus for accelerating scalar multiplication in an elliptic curve cryptosystem (ECC) over prime fields is provided. Multiplication operations within an ECC point operation are identified and modified utilizing an equivalent point representation that inserts multiples of two. Algebraic substitutions of the multiplication operations with squaring operations and other cheaper field operations are performed. Scalar multiplication can also be protected against simple side-channel attacks balancing the number of multiplication operations and squaring operations and providing novel atomic structures to implement the ECC operation. In addition, a new coordinate system is defined to enable more effective operation of ECC to multiprocessor environments.
REFERENCES:
patent: 5854759 (1998-12-01), Kaliski et al.
patent: 6038581 (2000-03-01), Aoki et al.
patent: 6202076 (2001-03-01), Aoki et al.
patent: 6252959 (2001-06-01), Paar et al.
patent: 6266688 (2001-07-01), Aoki et al.
patent: 6389442 (2002-05-01), Yin et al.
patent: 6415310 (2002-07-01), Takenaka et al.
patent: 6480606 (2002-11-01), Kurumatani
patent: 6714648 (2004-03-01), Miyazaki et al.
patent: 6721771 (2004-04-01), Chang
patent: 6738478 (2004-05-01), Vanstone et al.
patent: 6772184 (2004-08-01), Chang
patent: 6804782 (2004-10-01), Qiu et al.
patent: 6816594 (2004-11-01), Okeya
patent: 6826586 (2004-11-01), Chang
patent: 6873706 (2005-03-01), Miyazaki et al.
patent: 6876745 (2005-04-01), Kurumatani
patent: 6914986 (2005-07-01), Handschuh
patent: 6968354 (2005-11-01), Kaminaga et al.
patent: 7020281 (2006-03-01), Vadekar et al.
patent: 7043015 (2006-05-01), Lauter et al.
patent: 7046801 (2006-05-01), Okeya
patent: 7110538 (2006-09-01), Gallant et al.
patent: 7123717 (2006-10-01), Coron et al.
patent: 7162033 (2007-01-01), Coron
patent: 7177422 (2007-02-01), Akishita
patent: 7197527 (2007-03-01), Naslund et al.
patent: 7200225 (2007-04-01), Schroeppel
patent: 7215780 (2007-05-01), Lambert et al.
patent: 7233663 (2007-06-01), Sotoodeh
patent: 7236589 (2007-06-01), Lauter et al.
patent: 7240084 (2007-07-01), Gura et al.
patent: 7447310 (2008-11-01), Koc et al.
patent: 7602907 (2009-10-01), Zhu et al.
patent: 7676037 (2010-03-01), Jung et al.
patent: 7856101 (2010-12-01), Al-Gahtani et al.
patent: 2003/0142820 (2003-07-01), Futa et al.
patent: 2003/0206628 (2003-11-01), Gura et al.
patent: 2004/0001590 (2004-01-01), Eisentraeger et al.
patent: 2004/0158597 (2004-08-01), Ye et al.
patent: 2005/0036609 (2005-02-01), Eisentraeger et al.
patent: 2006/0056619 (2006-03-01), Billet et al.
patent: 2007/0050442 (2007-03-01), Takagi et al.
patent: 2007/0198824 (2007-08-01), Chen et al.
patent: 2007/0271323 (2007-11-01), Stein et al.
patent: 2008/0219437 (2008-09-01), Ebeid
patent: 2008/0219438 (2008-09-01), Ebeid
patent: 2009/0041229 (2009-02-01), Douguet et al.
patent: 2009/0067617 (2009-03-01), Trichina et al.
patent: 2009/0214025 (2009-08-01), Golic
patent: 2009/0287756 (2009-11-01), Lauter et al.
patent: 2010/0183142 (2010-07-01), Katagi et al.
patent: 1 296 224 (2003-03-01), None
patent: 1 443 393 (2004-08-01), None
patent: WO 00/59156 (2000-10-01), None
patent: WO 01/93014 (2001-12-01), None
patent: WO 02/01343 (2002-01-01), None
patent: WO 2006/092448 (2006-09-01), None
patent: WO 2007/025796 (2007-03-01), None
patent: WO 2007/045258 (2007-04-01), None
patent: WO 2007/048430 (2007-05-01), None
Liu, Shuang-Gen & Yu-Pu Hu, A Fast and Secure Elliptic Curve Scalar Multiplication Algorithm Over GF(p^m), Journal of the Chinese Institute of Industrial Engineers, vol. 26, No. 4, pp. 255-265 (2009).
K. Aoki, F. Hoshino, T. Kobayashi and H. Oguro, “Elliptic Curve Arithmetic Using SIMD,” ISC2001, vol. 2200 of Lecture Notes in Computer Science, pp. 235-247, Springer-Verlag, 2.
R, Avanzi, V. Dimitrov, C. Doche and F. Sica, “Extending Scalar Multiplication Using Double Bases,” Proc. AsiaCrypt'06, LNCS vol. 4284, pp. 130-144, 2006.
R. Avanzi, “Aspects of Hyperelliptic Curves over Large Prime Fields in Software Implementations,” in Workshop on Cryptographic Hardware and Embedded Systems (CHES'04), vol. 31.
R. Avanzi and F. Sica, “Scalar Multiplication on Koblitz Curves using Double Bases,” Technical Report No. 2006/067, Cryptology ePrint Archive, 2006.
R. Avanzi, “Side Channel Attacks on Implementations of Curve-Based Cryptographic Primitives,” Cryptology ePrint Archive, Report 2005/017, 2005. Available at: http://eprint.iac.
D. Bernstein, “Curve25519: New Diffie-Hellman Speed Records,” available at: http://cr.yp.to/talks.html.
D. Bernstein, “High-Speed Diffie-Hellman, Part 2,” presentation in INDOCRYPT'06, tutorial session, 2006.
M. Brown, D. Hankerson, J. Lopez and A. Menezes, “Software Implementation of the NIST elliptic curves over prime fields,” in Progress in Cryptology CT-RSA 2001 , vol. 2020 of Lecture Notes in Computer Science, pp. 250-265, Springer-Verlag, 2001.
O. Billet and M. Joye, “The Jacobi Model of an Elliptic Curve and Side-Channel Analysis,” Cryptology ePrint Archive, Report 2002/125, 2002. Available at: http://eprint.iacr.org/2002/125/.
O. Brier and M. Joye, “Fast Point Multiplication on Elliptic Curves through Isogenies,” Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, LNCS vol. 2643, pp. 43-50, Springer-Verlag, 2003.
B. Chevallier-Mames, M. Ciet and M. Joye, “Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity,” IEEE Transactions on Computers, 53(6), pp. 760-768, 2004.
M. Ciet, M. Joye, K. Lauter and P. L. Montgomery, “Trading Inversions for Multiplications in Elliptic Curve Cryptography,” in Designs, Codes and Cryptography. vol. 39, No. 2, pp. 189-206, 2006.
H. Cohen, A. Miyaji and T. Ono, “Efficient Elliptic Curve Exponentiation using Mixed Coordinates,” Advances in Cryptology—ASIACRYPT '98, vol. 1514 of Lecture Notes in Computer Science, pp. 51-65, Springer-Verlag, 1998.
J.S. Coron, “Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems,” in Workshop on Cryptographic Hardware and Embedded Systems (CHES), Springer-Verlag, pp. 292-302, 1999.
V. S. Dimitrov, G. A. Jullien, and W. C. Miller, “An Algorithm for Modular Exponentiation,” Information Processing Letters, 66(3):155-159, 1998.
V. Dimitrov, L. Imbert and P.K. Mishra, “Efficient and Secure Elliptic Curve Point Multiplication using Double-Base Chains,” Advances in Cryptology—ASIACRYPT'05, vol. 3788 of Lecture Notes in Computer Science, pp. 59-78, Springer-Verlag, 2005.
M. Ciet, G. Piret and J. Quisquater, “Several Optimizations for Elliptic Curves Implementation on Smart Card,” Technical Report, UCL Crypto Group, 2001.
C. Doche and L. Imbert, Extended Double-Base Number System with Applications to Elliptic Curve Cryptography, in Progress in Cryptology—INDOCRYPT 2006, LNCS 4329, pp. 335-348, 2006.
C. Doche, T. Icart and D. Kohel, “Efficient Scalar Multiplication by Isogeny Decompositions,” in Proc. PKC 2006, LNCS 3958, 191-206, Springer-Verlag, 2006.
K. Eisentraeger, K. Lauter and P. Montgomery, “Fast Elliptic Curve Arithmetic and Improved Well Pairing Evaluation,” in Topics in Cryptology—CT-RSA'2003, vol. 2612 of Lecture Notes in Computer Science, pp. 343-354, Springer-Verlag, 2003.
L. Elmegaard-Fessel, “Efficient Scalar Multiplication and Security against Power Analysis in Cryptosystems based on the NIST Elliptic Curves over Prime Fields,” Master Thesis, University of Copenhagen, 2006.
W. Fischer, C. Giraud, E.W. Knudsen and J.-P. Seifert, “Parallel Scalar Multiplication on General Elliptic Curves over Fp Hedged against Non-Differential Side-Channel Attacks,” in IACR ePrint archive, Report 2002/007, 2002. Available at: http://www.iacr.org.
J. Groβschädl, R. Avanzi, E. Savas and S. Tillich, “Energy-Efficient Software Implementation of Long In
Longa Patrick
Miri Ali
Garvey, Smith Nehrbass & North, L.L.C.
Kosowski Carolyn B
North Brett A.
Revak Christopher A
University of Ottawa
LandOfFree
Accelerating scalar multiplication on elliptic curve... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Accelerating scalar multiplication on elliptic curve..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accelerating scalar multiplication on elliptic curve... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2718167