Lean multiplication of multi-precision numbers over GF(2 m )

Details Lean multiplication of multi-precision numbers over GF(2 m ) Lean multiplication of multi-precision numbers over GF(2 m )

2003-08-06

2008-11-04

Moazzami, Nasser (Department: 2136)

Cryptography

Particular algorithmic function encoding

C380S029000, C380S030000, C708S492000

Reexamination Certificate

active

07447310

ABSTRACT:
Multi-precision multiplication methods over GF(2m) include representing a first polynomial and a second polynomial as an array of n words. A recursive algorithm may be used to iteratively decompose the multiplication into a weighted sum of smaller subproducts. When the size of the smaller subproducts is less than or equal to a predetermined size, a nonrecursive algorithm may be used to complete the multiplication. The nonrecursive algorithm may be optimized to efficiently perform the bottom-end multiplication. For example, pairs of redundant subproducts can be identified and excluded from the nonrecursive algorithm. Moreover, subproducts having weights in a special form may be efficiently calculated by a process that involves storing and reusing intermediate calculations.

REFERENCES:
patent: 4037093 (1977-07-01), Gregg et al.
patent: 4435823 (1984-03-01), Davis et al.
patent: 4754421 (1988-06-01), Bosshart
patent: 4811269 (1989-03-01), Hirose et al.
patent: 5220606 (1993-06-01), Greenberg
patent: 5457804 (1995-10-01), Ohtomo
patent: 5642367 (1997-06-01), Kao
patent: 5880985 (1999-03-01), Makineni et al.
patent: 6026420 (2000-02-01), DesJardins et al.
patent: 6199087 (2001-03-01), Blake et al.
patent: 6233597 (2001-05-01), Tanoue et al.
patent: 6343305 (2002-01-01), Koc et al.
patent: 6421807 (2002-07-01), Nakamura et al.
patent: 6466959 (2002-10-01), Blake et al.
patent: 6687725 (2004-02-01), Chen et al.
patent: 6766345 (2004-07-01), Stein et al.
patent: 6993136 (2006-01-01), Solinas
patent: 7003106 (2006-02-01), Ouyang
patent: 7031468 (2006-04-01), Hoffstein et al.
patent: 7069287 (2006-06-01), Paar et al.
patent: 7082452 (2006-07-01), Stein et al.
patent: 7111166 (2006-09-01), Dror et al.
patent: 7133889 (2006-11-01), Parthasarathy et al.
patent: 7343472 (2008-03-01), Porten et al.
patent: 2001/0024502 (2001-09-01), Ohkuma et al.
patent: 2002/0016773 (2002-02-01), Ohkuma et al.
patent: 2002/0039418 (2002-04-01), Dror et al.
patent: 2002/0041681 (2002-04-01), Hoffstein et al.
patent: 2002/0062330 (2002-05-01), Paar et al.
patent: 2003/0068037 (2003-04-01), Bertoni et al.
patent: 2003/0105791 (2003-06-01), Stein et al.
patent: 2003/0110196 (2003-06-01), Stein et al.
patent: 2003/0128841 (2003-07-01), Ouyang
patent: 2003/0133568 (2003-07-01), Stein et al.
patent: 2003/0135530 (2003-07-01), Parthasarathy et al.
patent: 2003/0140078 (2003-07-01), Feuser
patent: 2003/0206628 (2003-11-01), Gura et al.
patent: 2003/0206629 (2003-11-01), Eberle et al.
patent: 2003/0212729 (2003-11-01), Eberle et al.
patent: 2004/0078411 (2004-04-01), Porten et al.
patent: 2004/0107341 (2004-06-01), Hall et al.
patent: 2006/0269054 (2006-11-01), Dror et al.
Erdem, Serdar, An Abstract of The Thesis, Improving the aratsuba-Ofman Multiplication Algorithm for Special Applications, Nov. 8, 2001, Oregon State University.
Cormen et al.,Introduction to Algorithms, MIT, pp. 59-61 (1990).
De Win et al., “A fast software implementation for arithmetic operations in GF(2″),”Advances in Cryptology—ASIACRYPT 96, Proceedings, pp. 65-76 (1996).
Diffie et al., “New Directions in Cryptography,”IEEE Trans. Information Theory, pp. 644-654 (1976).
Erdem et al., “A Less Recursive Variant of Karatsuba-Ofman Algorithm for Multiplying Operands of Size a Power of Two,”16th IEEE Symposium on Computer Arithmetic, 8 pp (2003).
Erdem, “Improving the Karatsuba-Ofman Multiplication Algorithm for Special Applications,” Ph.D. Thesis, Oregon State University (2002).
Geddes et al.,Algorithms for Computer Algebra, Kluwer Academic Publishers, Boston Chapter 4, pp. 111-145 (1992).
Guajardo et al., “Efficient algorithms for elliptic curve cryptosystems,”Advances in Cryptology—CRYPTO 97, Proceedings, pp. 342-356 (1997).
IEEE P1363, “Standard specifications for public-key cryptography,” Draft Version 13 (Nov. 12, 1999).
Johnson et al., “The Elliptic Curve Digital Signature Algorithm (ECDSA),” Technical Report CORR 99-34, Dept. of C&O, University of Waterloo, Canada, 55 pp. (1999).
Karatsuba et al., “Multiplication of Multidigit Numbers on Automata,”Soviet Physics-Doklady, vol. 7, pp. 595-596 (1963).
Knuth,The Art of Computer Programming, vol. 2, Seminumerical Algorithms, Addison-Wesley, Reading, MA, pp. 265-294 (1998).
Koblitz, “Elliptic curve cryptosystems,”Mathematics of Computation, vol. 48, No. 177, pp. 203-209 (Jan. 1987).
Koç,High-Speed RSA Implementation: Version 2.0, RSA Laboratories, 73 pp. (Nov. 1994).
Koç et al., “Montgomery Multiplication in GF(2κ),”Design, Codes and Cryptography, vol. 14, pp. 57-69 (1998).
Lidl et al.,Introduction to Finite Fields and Their Applications, Cambridge University Press, New York, NY, pp. 541-566 (1994).
Menezes,Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, Boston, MA, pp. 83-99 (1993).
Menezes et al.,Handbook of Applied Cryptography, CRC Press, Boca Raton, FL, pp. 591-630 (1997).
Miller, “Uses of Elliptic Curves in Cryptography,”Advances in Cryptology—CRYPTO 85, Proceedings, pp. 417-426 (1985).
Montgomery, “Modular Multiplication Without Trial Division,”Mathematics of Computation, vol. 44, pp. 519-521 (1985).
Mullin et al., “Optimal Normal Bases in GF(pn),”Discrete Applied Mathematics, vol. 22, pp. 149-161 (1988).
National Institute for Standards and Technology, Digital Signature Standards (DSS), FIPS PUB 186-2, 76 pp. (Jan. 2000).
Paar et al., “Fast Arithmetic Architectures for Public-Key Algorithms over Galois Fields GF((2n)m),”Advances in Cryptology—EURO-CRYPT 97, Proceedings, pp. 363-378 (1997).
Rivest et al., “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,”Communications of the ACM, vol. 21, No. 2, pp. 120-126 (Feb. 1978).
Schroeppel et al., “Fast Key Exchange with Elliptic Curve Systems,”Advances in Cryptology—CRYPTO 95, Proceedings, pp. 43-56 (1995).
Silverman, “Fast Multiplication in Finite Field GF (2N),”Cryptographic Hardware and Embedded Systems, pp. 122-134 (1999).
Office action mailed Apr. 12, 2007 in U.S. Appl. No. 10/636,321, filed Aug. 6, 2003 (published as U.S. Patent Application Publication No. 2004/0098440-A1).
Office action mailed Sep. 29, 2006 in U.S. Appl. No. 10/636,321, filed Aug. 6, 2003 (published as U.S. Patent Application Publication No. 2004/0098440-A1).

Affiliated with

Also associated with

Rating

Lean multiplication of multi-precision numbers over GF(2 m ) does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Lean multiplication of multi-precision numbers over GF(2 m ), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lean multiplication of multi-precision numbers over GF(2 m ) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4025184