Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2006-06-27
2006-06-27
Mai, Tan V. (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C380S028000
Reexamination Certificate
active
07069287
ABSTRACT:
A method for implementing an elliptic curve or discrete logarithm cryptosystem on inexpensive microprocessors is disclosed which provides for advantageous finite field computational performance on microprocessors having limited computational capabilities. The method can be employed with a variety of commercial and industrial imbedded microprocessor applications such as consumer smart cards, smart cards, wireless devices, personal digital assistants, and microprocessor controlled equipment. In one embodiment, a Galois Field (GF) implementation based on the finite field GF((28−17)17) is disclosed for an Intel 8051 microcontroller, a popular commercial smart card microprocessor. The method is particularly suited for low end 8-bit and 16-bit processors either with or without a coprocessor. The method provides for fast and efficient finite field multiplication on any microprocessor or coprocessor device having intrinsic computational characteristics such that a modular reduction has a greater computational cost than double precision, long number additions or accumulations. The disclosed method offers unique computational efficiencies in requiring only infrequent subfield modular reduction and in employing an adaptation of Itoh and Tsujii's inversion algorithm for the group operation. In one embodiment, a core operation for a signature generation, an elliptic curve scalar multiplication with a fixed point, is performed in a group of order approximately 2134in less than 2 seconds. In contrast to conventional methods, the method does not utilize or require curves defined over a subfield such as Koblitz curves.
REFERENCES:
patent: 5999959 (1999-12-01), Weng et al.
patent: 6049815 (2000-04-01), Lambert et al.
patent: 6230179 (2001-05-01), Dworkin et al.
patent: 6252959 (2001-06-01), Paar et al.
patent: 6377969 (2002-04-01), Orlando et al.
patent: 6611597 (2003-08-01), Futa et al.
patent: 2002/0041681 (2002-04-01), Hoffstein et al.
patent: 2002/0055962 (2002-05-01), Schroeppel
Preda Mihailescu, “Optical Galois Field Bases which are not Normal”, presentation (Recent Results Session), FSE '97 (Fast Software Encryption), Jan. 20-22, 1997, Haifa, Israel.
D.V. Bailey et al., “Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms”, Advances in Cryptology-CRYPTO '98, ed. H.Krawczyh, Lecture Notes in Computer Science 1462, Springer-Verlag (Heidelburg 1998), p 472-485.
Anonymous, “The Elliptic Curve Cryptosystem for Smart Cards”, Certicom White Paper, Certicom Corp., San Mateo, CA (May 1998).
T. Kobayashi et al., “Fast Elliptic Curve Algorithm Combining Frobenius Map and Table Reference to Adapt to Higher Characteristic”, Advances in Cryptology-EUROCRYPT '99, ed. J. Stern, Lecture Notes in Computer Science 1592, Springer-Verlag (Berlin 1999), p176-189.
J.W. Chung et al., “Fast Implementation of Elliptic Curve Defined over GF(p**m) on Calm RISC with MAC2424 Coprocessor”, Cyrptographic Hardware and Embedded Systems-CHES 2000, ed. C.K. Koc et al., Lecture Notes in Computer Science 1965, Springer-Verlag (Berlin 2000), p57-70.
J. Guajardo et al., “Efficient Implementation of Elliptic Curve Cryptosystmes on the TI MSP430x33x Family of Microcontrollers”, PKC 2001, ed. K. Kim, Lecture Notes in Computer Science 1992, Springer-Verlag (Berlin 2001), p 365-382.
D.V. Bailey et al., “Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Crytopgraphy”, J. Cryptology, 14(3): 153-176 (2001).
Bailey Daniel V
Paar Christof
Woodbury Adam D
Greehan, Esq. R. Dennis
Mai Tan V.
Worcester Polytechnic Institute
LandOfFree
Method for efficient computation of odd characteristic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for efficient computation of odd characteristic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for efficient computation of odd characteristic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3674287