Cryptography – Particular algorithmic function encoding
Patent
1998-01-26
2000-07-11
Swann, Tod R.
Cryptography
Particular algorithmic function encoding
713100, 708654, H04L 928, G06F 752, G06F 1500
Patent
active
060884533
ABSTRACT:
A scheme for performing high speed Montgomery division within the Montgomery space. Montgomery division Y=B.multidot.A.sup.-1 .multidot.2.sup.n mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0.ltoreq.A.ltoreq.N, a positive integer B, and an integer n which is satisfying n.gtoreq.L where L is a bit length of N in binary expression, is performed by obtaining a Montgomery inverse X=A.sup.-1 .multidot.2.sup.2n mod N from inputs A and N, and obtaining the Montgomery division Y=B.multidot.X.multidot.2.sup.-n mod N from the Montgomery inverse X and inputs B and N. Montgomery inverse X=A.sup.-1 .multidot.2.sup.2n mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0.ltoreq.A<N, and an integer n which satisfies n.gtoreq.L where L is a bit length of N in binary expression, is determined by obtaining an intermediate result C=A.sup.-1 .multidot.2.sup.k mod N and a parameter k satisfying L.ltoreq.k.ltoreq.2L from inputs A and N, and obtaining the Montgomery inverse X=C.multidot.2.sup.2n-k mod N from the intermediate result C and the parameter k and input N.
REFERENCES:
patent: 5227978 (1993-07-01), Kato
patent: 5321752 (1994-06-01), Iwamura et al.
patent: 5499299 (1996-03-01), Takenaka et al.
patent: 5666419 (1997-09-01), Yamamoto et al.
patent: 5724279 (1998-03-01), Benaloh et al.
patent: 5805703 (1998-09-01), Crandall
Peter L. Montgomery, "Modular Multiplication Without Trial Division", Mathematics of Computation, vol. 44, No. 170, Apr., 1985, pp. 519-521.
Burton S. Kaliski Jr., "The Montgomery Inverse And Its Applications", IEEE Transactions on Computers, vol. 44, No. 8, Aug. 1995, pp. 1064-1065.
Tetsutaro Kobayashi, et al., "Modular Inverse Algorithm Optimized By Initial Operations", Technical Report of IEICE, ISEC97-48, Nov., 1997, pp. 13-23.
Darrow Justin T.
Kabushiki Kaisha Toshiba
Swann Tod R.
LandOfFree
Scheme for computing Montgomery division and Montgomery inverse does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheme for computing Montgomery division and Montgomery inverse , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheme for computing Montgomery division and Montgomery inverse will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-549993