Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
2002-12-09
2009-02-03
Revak, Christopher A (Department: 2131)
Cryptography
Particular algorithmic function encoding
Public key
C380S028000, C708S490000, C708S650000, C713S174000, C713S180000
Reexamination Certificate
active
07486789
ABSTRACT:
In scalar multiplication method using a Montgomery-type elliptic curve, a high-speed elliptic curve calculation device effectively uses a table that stores coordinates of certain scalar multiple points like points multiplied by exponentiation of two to a certain point G and so forth. The elliptic curve calculation device receives an arbitrary integer k of n bits and outputs scalar-multiplied points against a point G on a Montgomery-type elliptic curve E on a finite field F that is given in advance. The elliptic curve calculation device includes a calculation procedure generation unit that generates a calculation procedure that addition on the elliptic curve E with either of G, 2 *G, 22*G., . . . , 2n−1*G as the first addition element is repeated and a scalar multiplication unit that calculates the scalar-multiplied points k*G by repeating addition on the elliptic curve E, referring to a table memorizing unit that stores values (coordinates) of exponentiation of two against the point G and complying with the generated calculation procedure.
REFERENCES:
patent: 6035041 (2000-03-01), Frankel et al.
patent: 6088453 (2000-07-01), Shimbo
patent: 6263081 (2001-07-01), Miyaji et al.
patent: 6466668 (2002-10-01), Miyazaki et al.
patent: 6480606 (2002-11-01), Kurumatani
patent: 6666381 (2003-12-01), Kaminaga et al.
patent: 6721771 (2004-04-01), Chang
patent: 6738478 (2004-05-01), Vanstone et al.
patent: 6748410 (2004-06-01), Gressel et al.
patent: 6772184 (2004-08-01), Chang
patent: 6816594 (2004-11-01), Okeya
patent: 2003/0156714 (2003-08-01), Okeya
patent: 11-102158 (1999-04-01), None
patent: 2002-207424 (2002-07-01), None
Wu, Huapeng. “Montgomery Multiplier and Squarer For A Class of Finite Fields”. May 2002. Relevant pp. 521-529. IEEE Transactions on Computers, vol. 51, Issue 5. Found on the World Wide Web at: http://ieeexplore.ieee.org/iel5/12/21690/01004591.pdf?tp=&isnumber=21690&arnumber=1004591&punumber=12.
Bednara, M. Daldrup, M. Teich, J. von zur Gathen, J. Shokrollahi, J. “Tradeoff Analysis of FPGA Based Elliptic Curve Cryptography”. May 2002. Relevant pp. 797-800. IEEE ISCAS, 2002. vol. 5. Found on the World Wide Web at: http://ieeexplore.ieee.org/iel5/7897/21767/01010824.pdf?tp=&isnumber=21767&arnumber=1010824&punumber=7897.
D. Hankerson, et al., entitled “Software Implementation of Elliptic Curve Cryptography Over Binary Fields”, Cryptographic Hardware and Embedded Systems. 2nd International Workshop, Ches 2000, Worchester, MA, Aug. 17-18, 2000 Proceedings, Lecture Notes in Computer Science, Berlin: Springer, DE, vol. 1965, Aug. 17, 2000, pp. 1-24, XP001049125.
T. Hasegawa, et al., entitled “A Practical Implementation of Elliptic Curve Cryptosystems Over GF(P)on a 16-Bit Microcomputer”, Public Key Cryptography. International Workshop on Practice and Theory in Public Key Cryptography, Feb. 5, 1999, pp. 182-194, XP000998747.
P.L. Montgomery, “Speeding the Pollard and Elliptic Curve Methods of Factorization”, Math. of Comp. vol. 48, No. 177, pp. 243-264, 1987.
Efficient Exponentiation on Montgomery-Type Elliptic Curves, Proceedings of the 2002 Symposium on Cryptography and Information Security, vol. I of II, p. 515-519, Jan. 29, 2002.
On the Power of Multidoubling in Speeding Up Elliptic Scalar Multiplication, Lecture Notes on Computer Science, vol. 2259, p. 268-283, 2001.
Two Algorithms for Modular Exponentiation Using Nonstandard Arithmetics, The Institue of Electronics Information and Communication Engineers, vol. 93, No. 525, p. 11-17, Mar. 18, 1994, CSDB No. 1999-00644-002.
European Office Action mailed Dec. 21, 2007 for European Application No. 02 026 894.2-1243.
K. Okeya and K. Sakurai, “Efficient Elliptic Curve Cryptosystems from a Scalar Multiplication Algorithm with Recovery of the y-Coordinate on a Montgomery-Form Elliptic Curve”, CHES 2001, Third International Workshop Proceedings, May 14-16, 2001, Paris, France, pp. 126-141.
Y. Tsuruoka and K. Koyama, “Fast Computation Over Elliptic Curves E(Fqn) Based on Optimal Additional Sequences”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Engineering Sciences Society, Tokyo, Japan, vol. E84-A, No. 1, Jan. 2001, pp. 114-119.
Okeya et al., “A Scalar Multiplication Algorithm on a Montgomery-form Elliptic Curve”, The 2001 Symposium on Cryptography and Information Security, vol. I of II, p. 305-310, Osio, Japan, Jan. 23-26, 2001 w/ English Abstract.
Futa et al. “Efficient exponentiation on Montgomery-type elliptic Curves”, The 2002 Symposium on Cryptography and Information Security, Jan. 29 - Feb. 1, 2002 w/ English Abstract.
Futa et al. “Efficient exponentiation on Montgomery-type elliptic Curves (2)”, The Institute of Electronics Information and Communication Engineers, vol. 102, No. 212, p. 123-129, Jul. 12, 2002 w/ English Abstract.
Futa et al. “Efficient exponentation on Montgomery-type elliptic Curves (2)”, IPSJ SIG Notes, vol. 2002, No. 68, p. 267-273, Jul. 18, 2002 w/ English Abstract.
Futa Yuichi
Ohmori Motoji
Avery Jeremiah
Panasonic Corporation
Revak Christopher A
Wenderoth , Lind & Ponack, L.L.P.
LandOfFree
Device and method for calculation 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 Device and method for calculation on elliptic curve, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method for calculation on elliptic curve will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4069675