Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2002-03-13
2009-08-25
Ngo, Choung D (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
07580966
ABSTRACT:
The invention relates to a method for speeding up the time required to perform a Montgomery product calculation by applying the High-Radix Montgomery method on computing hardware. A loop of operations is performed consisting in repeating successive operations, i.e.: a first addition operation involving the addition of a value of one of several first products, designated ai·b and a value of one variable, designated u, according to a first relationship u:=u+ai·b; and a second addition operation involving the addition of a value of one of several second products, designated m·n, and a value of variable u according to a second relationship u:=u+m·n. At least the first and second addition operations are Carry-Save addition operations in order to speed up the time required to perform an addition.
REFERENCES:
patent: 6185596 (2001-02-01), Gressel et al.
patent: 7046800 (2006-05-01), Tenca et al.
patent: 7174015 (2007-02-01), Koc et al.
Koc, CK et al: Multi-Operand Modulo Addition Using Cary Save Adders, Electronics Letters, IEE Stevenage, GB, vol. 26, No. 6, Mar. 15, 1990, pp. 361-363, XP000122754; ISSN: 0013-5194, p. 361, Right Hand col. Line 48,-p. 362, Right Hand col. Line 50.
Koc, CK et al: Carry-Save Adders for Computing the Product AB Modulo N, Electronics Letters, IEE Stevenage, GB, vol. 26, No. 13, Jun. 21, 1990, pp. 899-900, XP000107954, ISSN: 0013-5194, p. 899, Left Hand col. Line 36—p. 900, Lefthand col. Line 4.
Ploog H et al: FPGA Based Architecture Evaluation of Cryptographic Coprocessors for Smartcards; FPGAS for Custom Computing Machines, 1998, Proceedings, IEEE Symposium on Napa Valley, CA, USA Apr. 15-17, 1998, Lost Alamitos, CA, USA, IEEE Comput. Soc. US, Apr. 15, 1998, pp. 292-293, XP010298224 ISBN: 08186 8900-5, p. 292, Lefthand col. Line 13—Right Hand col. Line 10, p. 293, Lefthand col. Line10-Line 23.
Shand, M et al: Fast Implementations of RSA Cryptography, Computer Arithmetic, 1993, USA IEEE Comput. Soc. Jun. 29, 1993, pp. 252-259, XP010128541, ISBN: 0 8186 3862 1, p. 252, Left col., Line 1-p. 254, Right col., Line 25, p. 256, Left col,—Line 29-p. 257,Right col, Line 10; p. 258, Left col.,Line11-p. 259, Left col,LN 10.
Koc C K: Montgomery Reduction With Even Modulus; IEE Proceedings, vol. 141, No. 5 pp. 314-316-XP006001604; ISSN: 1350-2387; p. 314, Left col., Line 1-p. 315, Left col., Line 45, p. 315, Right col. Line 2-p. 316, Left col. Line 15.
Guinier D: Multiplication of Large Integers by the Use of Modular Arithmetic Application to Cryptography, SIG Security, vol. 7, No. 4, 1990, pp. 7-20, XP000925424; ISSN0277-920X; p. 8, Line 12-p. 9, Line 23, p. 10, Line 13-p. 18, Line 24, p. 18, Line 30-p. 19, Line 22.
Schindler W: A Timing Attack Against RSA With the Chinese Remainder Theorem; Cryptographic Hardware & Embedded Systems, Aug. 17-18, 2000 Proceedings, Lecture Notes in Computer Science, Berlin: Springer, DE, vol. 1965, Aug. 17, 2000; pp. 109-124, XP001049131; ISBN: 3-540-41455-X; p. 109, Line 12-p. 112, Line 20; p. 114, Line 24-p. 117, Line 16.
Koc CK et al: Fast Software Exponentiation in GF (2) Proceedings 13th IEEE Symp on Computer Arithmetic; Jul. 6, 1997; pp. 225-231, XP010241213; ISBN: 0-8186-7846-1; p. 225, Right col. Line 14-p. 228, Left col. Line 6.
Cetin Kaya KOC, Koc@ece.orst.edu, “High-Speed RSA Implementation” RSA Laboratories; RSA Data Security, Inc., 100 Marine Parkway, Ste. 500, Redwood City, CA 94065-1031; Version 2.0, Nov. 1994.
Bull SA
King Eric G.
Miles & Stockbridge P.C.
Ngo Choung D
LandOfFree
Method and device for reducing the time required to perform... 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 and device for reducing the time required to perform..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for reducing the time required to perform... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4078479