Randomized modular reduction method and hardware therefor

Details Randomized modular reduction method and hardware therefor Randomized modular reduction method and hardware therefor

2004-02-18

2010-10-05

LaForgia, Christian (Department: 2439)

Cryptography

Particular algorithmic function encoding

C714S100000, C714S724000

Reexamination Certificate

active

07809133

ABSTRACT:
A cryptographically secure, computer hardware-implemented modular reduction method systematically underestimates and randomizes an approximate quotient used for computation of a remainder. The randomizing error injected into the approximate quotient is limited to a few bits, e.g. less than half a word. The computed remainder is congruent with but a small random multiple of the residue, which can be found by a final set of subtractions by the modulus. In addition to a computational unit and operations sequencer, the computing hardware also includes a random or pseudo-random number generator for producing the random error. The modular reduction method thus resists hardware cryptoanalysis attacks, such as timing and power analysis attacks.

REFERENCES:
patent: 5077793 (1991-12-01), Falk et al.
patent: 5144574 (1992-09-01), Morita
patent: 5185711 (1993-02-01), Hattori
patent: 5210710 (1993-05-01), Omura
patent: 5373560 (1994-12-01), Schlafly
patent: 5479511 (1995-12-01), Naccache
patent: 5513133 (1996-04-01), Cressel et al.
patent: 5724279 (1998-03-01), Benaloh et al.
patent: 5764554 (1998-06-01), Monier
patent: 5793659 (1998-08-01), Chen et al.
patent: 5870478 (1999-02-01), Kawamura
patent: 5954788 (1999-09-01), Suh et al.
patent: 5999627 (1999-12-01), Lee et al.
patent: 6049815 (2000-04-01), Lambert et al.
patent: 6088453 (2000-07-01), Shimbo
patent: 6091819 (2000-07-01), Venkatesan et al.
patent: 6175850 (2001-01-01), Ishii et al.
patent: 6366673 (2002-04-01), Hollmann et al.
patent: 6466668 (2002-10-01), Miyazaki et al.
patent: 7073072 (2006-07-01), Salle
patent: 7164765 (2007-01-01), Nishioka et al.
patent: 2002/0039418 (2002-04-01), Dror et al.
patent: 2002/0055962 (2002-05-01), Schroeppel
patent: 2002/0143836 (2002-10-01), Ebergen et al.
patent: 2002/0161810 (2002-10-01), Mellott et al.
patent: 2003/0044014 (2003-03-01), Liardet et al.
patent: 2003/0079139 (2003-04-01), Drexler et al.
patent: 2003/0206629 (2003-11-01), Eberle et al.
patent: 2003/0208518 (2003-11-01), Gura et al.
patent: 2003/0212729 (2003-11-01), Eberle et al.
patent: 2004/0019622 (2004-01-01), Elbe et al.
patent: 2004/0066934 (2004-04-01), Chen
patent: 2006/0282491 (2006-12-01), Joye
patent: 2008/0109501 (2008-05-01), Douguet
patent: 2010/0023572 (2010-01-01), Dupaquis et al.
patent: WO-2004111831 (2004-12-01), None
patent: WO-2006124160 (2006-11-01), None
patent: WO-2006124160 (2006-11-01), None
Design of an Efficient Public-Key Cryptographic Library for RISC-based Smart Cardsby Jean-Francois Dhem, Doctorate of Applied Sciences Thesis, Universite Catholique de Louvain, May 1998, pp. 11-22.
Implementing the Rivest Sharmi and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processorby Paul Barrett, Security Bulletin, Computer Security Ltd., Aug. 1986.
Efficient Implementation, Handbook of Applied Cryptography, 1997, Menezes, Oorschot, and Vanstone, pp. 591-635.
Architectural Tradeoff in Implementing RSProcessor by Fu-Chi Chang and Chia-Jiu Wang, ACM SIGARCH Computer Architecture News archive, Department of Electrical and Computer Engineering, University of Colorado at Colorado Springs, Colorado, vol. 30, Issue 1, Mar. 2002.
J. Grosschadel,the Chinese Remainder Theorem and Its Application in a High-Speed RSA Crypto Chip, Dec. 11, 2000, IEEE Comput. Soc., U.S., pp. 384-393, XP010529836. ISBN 0-7695-0859-6.
K.C. Posch et al., r Microprocessing and Microprogramming, Elsevier Science Publishers, BV, Amsterdam NL., vol. 29, No. 3, Oct. 1990, pp. 177-184, XP000151455, ISSN: 0165-6074.
A. Bosselaers et al., “Comparison of Three Modular Reduction Functions”, Advances in Cryptology/Crypto '93, LNCS 772, Springer-Verlag, 1994, pp. 175-186.
C.H. Lim et al., “Fast Modular Reduction With Precomputation”, preprint, 1999 (available from CiteSeer Scientific Literature Digital Library, 15 pages.
J.F. Dhem, “Design of an Efficient Public-Key Cryptographic Library for RISC-based Smart Cards”, doctoral dissertation, Université catholique de Louvain, Louvain-la-Neuve, Belgium, May 1998.
“European Application Serial No. 06749987.1, European Search Report mailed May 28, 2008”, 14.
“European Application Serial No. 06749987.1, EP Office Action mailed Oct. 1, 2008”, 3 pages.
Bajard, et al., “Arithmetic Operations in the Polynomial Modular Number System”,Research Report LIRMM, No. 04030, XP002358296, (Sep. 2004), 1-26.
De Dinechin, B. D., “A Ultra Fast Euclidean Division Algorithm for Prime Memory Systems”,ACM, (1991), 56-65.
Dhem, Jean-Francois, “Efficient Modular Reduction Algorithm in IFq[x] and Its Application to ‘Left to Right’ Modular Multiplication in IF2[x]”,Cryptographic Hardware and Embedded Systems - CHES2003, vol. 2779/2003, XP-002358295, Berlin, (2003), 203-213.
“U.S. Appl. No. 11/203,939, Non-Final Office Action mailed Apr. 16, 2009”, 6 pgs.
04800660.5, “European Application serial No. 04800660.5 ,Office Action Mailed on Mar. 3, 2009”, 3 pages.
Dhem, J- F, et al., “Design of an Efficient Public-Key Cryptographic Library for RISC based”,Doctorate of Applied Sciences Thesis, Universite Catholique De Louvain,, (May 1998), pp. 11 to 22.
Donald, E. K, “The Art of Computer Programming vol. 2 Seminumerical Algorithm”,Third Edition, Addison Wesley, USA, ISBN: 0-20189684-2, (1998), chapter 4.3.2.
“U.S. Appl. No. 11/203,939, Response filed Aug. 17. 2009 to Non Final Office Action mailed Apr. 16, 2009”, 6 pgs.
200480033595.5, “Chinese Application No. 200480033595.5, Office Action mailed May 22, 2009”, 6 pgs.
Grobchadl, J., “The Chinese Remainder Theorem and Its Application in a High-Speed RSA Crypto Chip”,IEEE Computer Society Wasgington, DC, USA, (Apr. 29, 2009).
Knuth, Donald E., “Chapter 4.3.2”,The Art of Computer Programming, vol. 2 Seminumerical Algorithm, Third Edition, , Addison Wesley, USA, ISBN: 0-201-89684-2, (1998), 284-294.
“U.S. Appl. No. 11/203,939, Notice of Allowance mailed Nov. 3, 2009”, 6 pgs.
“Chinese Application Serial No. 200480033595.5, Chinese Office Action (with English translation) mailed Oct. 30, 2009”, 5 pgs.
“Chinese Application Serial No. 200480033595.5, Response (with English translation) filed Sep. 18, 2009 to Chinese Office Action maiied May 22, 2009”, 4 pgs.
“European Application Serial No. 04800660.5, European Office Action mailed Sep. 28, 2007”, 2 pgs.
“European Application Serial No. 04800660.5, Response filed Mar. 20, 2008 to European Office Action received Sep. 28, 2007”, 13 pgs.
“European Application Serial No. 04800660.5, Supplementary European Search Report mailed Apr. 18, 2007”, 2 pgs.
“European Application Serial No. 06749987.1, European Office Action mailed Sep. 18, 2009”, 7 pgs.
“European Application Serial No. 06749987.1, Response filed Apr. 8, 2009 to Extended European Search Report mailed Oct. 1, 2008”, 7 pgs.
“International Application Serial No. PCT/US2004/036590, International Search Authority Written Opinion mailed Apr. 19, 2005”, 3 pgs.
“International Application Serial No. PCT/US2004/036590, International Search Report mailed Apr. 19, 2005”, 1 pg.
“International Application Serial No. PCT/US2006/013795, Search Report mailed Oct. 19, 2007”, 4 pgs.
“International Application Serial No. PCT/US2006/13795, Written Opinion of the International Search Authority, mailed Oct. 19, 2007”, 4 pgs.
Morales-Sandoval, M., et al,, “On the hardware design of an eiliptic curve cryptosystem”,Proceedings of the Fifth Mexican International Conference in Computer Science, 2004.ENC2004, (2004), 64-70.
“U.S. Appl. No. 11/203,939, Notice of Allowance mailed Mar. 23, 2010”, 4 pgs.
“Chinese Application Serial No. 200480033595.5, Office Action mailed Apr. 13, 2010”, 3 Pgs.
“European Application Serial No. 04800660.5, Response filed Aug

Affiliated with

Also associated with

Rating

Randomized modular reduction method and hardware therefor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Randomized modular reduction method and hardware therefor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized modular reduction method and hardware therefor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4174545