Cryptography – Particular algorithmic function encoding
Reexamination Certificate
2007-05-15
2007-05-15
Moise, Emmanuel L. (Department: 2137)
Cryptography
Particular algorithmic function encoding
C380S030000, C708S491000
Reexamination Certificate
active
10068294
ABSTRACT:
A data encryption method performed with ring arithmetic operations wherein a modulus C is be chosen of the form 2w−L, wherein C is a w-bit number and L is a low Hamming weight odd integer less than 2(w−1)/2. And in some of those embodiments, the residue mod C is calculated via several steps. P is split into 2 w-bit words H1and L1. S1is calculated as equal to L1+(H12x1)+(H12x2)+ . . . +(H12xk)+H1. S1is split into two w-bit words H2and L2. S2is computed as being equal to L2+(H22x1)+(H22x2)+ . . . +(H22xk)+H2. S3is computed as being equal to S2+(2x1+ . . . +2xk+1). And the residue is determined by comparing S3to 2w. If S3<2w, then the residue equals S2. If S3≧2w, then the residue equals S3−2w.
REFERENCES:
patent: 4799149 (1989-01-01), Wolf
patent: 5542061 (1996-07-01), Omata
patent: 5699537 (1997-12-01), Sharangpani et al.
patent: 5724279 (1998-03-01), Benaloh et al.
patent: 5764554 (1998-06-01), Monier
patent: 5983299 (1999-11-01), Qureshi
patent: 5987574 (1999-11-01), Paluch
patent: 6088453 (2000-07-01), Shimbo
patent: 6134244 (2000-10-01), Van Renesse et al.
patent: 6141705 (2000-10-01), Anand et al.
patent: 6151393 (2000-11-01), Jeong
patent: 6157955 (2000-12-01), Narad et al.
patent: 6266771 (2001-07-01), Bellare et al.
patent: 6337909 (2002-01-01), Vanstone et al.
patent: 6341299 (2002-01-01), Romain
Silverman, Robert D. et al., “Recent Results on Signature Forgery,” Apr. 11, 1999, RSA Labortories Bulletin, pp. 1-5.
Menezes, A.J. et al., “Handbook of Applied Cryptography” Boca Raton, CRC press, 1997, pp. 611-612.
Menezes, A.J., et al “Efficient Implementation” from theHandbook of Applied Cryptography, (Boca Raton, CRS Press, 1997), pp. 591-607.
Dimitrov, V. and Cooklev, T., “Two Algorithms for Modular Exponentiation Using Nonstandard Arithmetics” IEICE Trans. Fundamentals, vol. E78-A, No. 1, Jan. 1995.
Koc, C.K. and Hung, C.Y., “Carry-Save Adders for Computing the Product AB Modulo N” Electronics Letters, vol. 26, No. 13, (Jun. 21, 1990), pp. 899-900.
Freking, W. L. and Parhi, K.K., “Montgomery Modular Multiplication and Exponentiation in the Residue Number System” Proc. 33rd Asilomar Conf. Signals Systems and Computer, Oct. 1999, pp. 1312-1316.
Tenca, A.F. and Koc, C.K., “A Scalable Architecture for Montgomery Multiplication” in: Koc, C.K. and Paar, C., Cryptographic Hardware and Embedded Systems, CHES 99, Lecture Notes in Computer Science, No. 1717. 1998, New York, NY: Springer-Verlog, 1999.
Koc, C.K. and Acar, T., “Montgomery Multiplication in GF (2k)” 3rd Annual Workshop on Selected Areas in Cryptography, (Aug. 15-16, 1996), pp. 95-106.
Bajard, J.C., et al “An RNS Montgomery Modular Multiplication Algorithm” IEEE Transactions on Computer, vol. 47, No. 7, (Jul. 1998), pp. 766-776.
Eldridge, S.E., “A Faster Modular Multiplication Algorithm” International Journal of Computer Math, vol. 40, (1991), pp. 63-68.
Bossalaers, A.., et al “Comparison of Three Modular Reduction Functions” In Douglas R. Stinson, editor, Advances in Cryptology—CRYPTO '93, vol. 773 of Lecture Notes in Computer Science, (Aug. 22-26, 1993), pp. 166-174.
Montgomery, P.L., “Modular Multiplication Without Trial Division” Mathematics of Computation, vol. 44, No. 170 (Apr. 1985), pp. 519-521.
Koc, C.K., et al “Analyzing and Comparing Montgomery Multiplication Algorithms” IEEE Micro, vol. 16, Issue 3, (Jun. 1996), pp. 26-33.
Kornerup, P., “High-Radix Modular Multiplication for Cryptosystems” Department of Mathematics and Computer Science, (1993), pp. 277-283.
Sunar, B. and Kox, C.K., “An Efficient Optimal Normal Basis Type II Multiplier” Brief Contributions, IEEE Transactions on Computers, vol. 50, No. 1, (Jan. 2001), pp. 83-87.
Koc, C.K., “Comments on‘ Residue Arithmetic VLSI Array Architecture for Manipulator Pseudo-Inverse Jacobian Computation’” Communications, IEEE Transactions on Robotics and Automation, vol. 7, No. 5, (Oct. 1991), pp. 715-716.
Savas, E. and Koc, C.K., “The Montgomery Modular Inverse-Revisited” IEEE Transactions on Computers, vol. 49, No. 7, (Jul. 2000), pp. 763-766.
Walter, C.D., “Montgomery's Multiplication Technique: How to Make it Smaller and Faster” in Cryptographic Hardware and Embedded Systems—CHAS 1999, C. Paar (Eds.). K. Ko, Ed. 1999, Springer, Berlin Germany, pp. 61-72.
Oh, H. and Moon, J., “Modular Multiplication Method” IEE Proc.-Comput. Digit.Tech., vol. 145, No. 4, (Jul. 1998), pp. 317-318.
Blum, T., “Modular Exponentiation on Reconfigurable Hardware” Master's thesis, ECE Department, Worcester Polytechnic Institute, Submitted to Faculty Apr. 8, 1999, Published May 1999. Retrieved from the Internet <URL: http://www.wpi.edu/pubs/ETD/Available/etd-090399-090413/unrestricted/blum.pdf>.
Marwedel, P., et al. “Built in Chaining: Introducing Complex Components into Architectural Synthesis.” Apr. 1996. Proceedings of the ASP-DAC, 1997. [online]. Retrieved from the Internet <URL: http://eldorado.uni-dortmund.de:8080/FB4/ls12/forshung/1997/aspdac/aspacPDF>.
Tiountchik, A., and Trichina, E., “RSA Acceleration with Field Programmable Gate Arrays” Lecture Notes in Computer Science, vol. 1587, pp. 164-176. Retrieved from the Internet: <URL:http://citeseer.nj.nec.com/274658.html>.
Menezes, A.J., et al “Handbook of Applied Cryptography” Boca Raton, CRC Press, 1997.
Blakely George Robert
Datta Rajat
Mitchell Oscar
Stein Kyle
Fortkort John A.
Fortkort & Houston P.C.
Moise Emmanuel L.
nCiper Corporation Limited
Pyzocha Michael
LandOfFree
Ring arithmetic method, system, and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Ring arithmetic method, system, and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ring arithmetic method, system, and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3781090