Multiplication of modular numbers

Details Multiplication of modular numbers Multiplication of modular numbers

2005-08-02

2005-08-02

Moise, Emmanuel L. (Department: 2131)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S174000, C708S491000

Reexamination Certificate

active

06925563

ABSTRACT:
A circuit for the implementation of modular multiplication of numbers comprises an alternative formation of the algorithm first proposed by R. C. Montgomery. The modified Montgomery algorithm is implemented in one of a plurality of circuits comprising full adders, half adders, registers and gates.

REFERENCES:
patent: 4686645 (1987-08-01), McCanny et al.
patent: 5060183 (1991-10-01), Sakashita et al.
patent: 5073870 (1991-12-01), Morita
patent: 5101431 (1992-03-01), Even
patent: 5321752 (1994-06-01), Iwamura et al.
patent: 5764772 (1998-06-01), Kaufman et al.
patent: 5815573 (1998-09-01), Johnson et al.
patent: 5914892 (1999-06-01), Wang et al.
patent: 6061706 (2000-05-01), Gai et al.
patent: 6397241 (2002-05-01), Glaser et al.
patent: WO 99/27677 (1999-06-01), None
Pending U.S. Appl. No. 09/668,026 entitled “Key Escrow Systems”, by William T. Jennings, 113 total pages, Sep. 21, 2000.
Choi, Sung-Wook, and Woo, Chong-Ho, “Bit-Level 1-Dimensional Systolic Modular Multiplication”, Journal of the Korean Institute of Telematics and Electronics, Sep. 1996, Korea Inst. Telematics & Electron, South Korea, vol. 33B, No. 9, pp. 62-69, XP000619886.
Blum, Thomas, et al, “Montgomery Modular Exponentiation on Reconfigurable Hardware”, Proceedings 14th IEEE Symposium on Computer Artihmetic, Adelaide, AU, Apr. 14-16, 1999, Los Alamitos, CA, pp. 70-77, XP-000876409.
Komerup, Peter, “A Systolic, Linear-Array Multiplier for a Class of Right-Shift Algorithms”, IEEE Transactions on Computers, IEEE, Inc., New York, vol. 43, No. 8, Aug. 1, 1994, pp. 892-898.
Chen, Po-Song, et al, “A Systolic RSA Public Key Cryptosystem”, IEEE International Symposium on Circuits and Systems (ISCAS), US, New York, 1996, pp. 408-411, XP000619797.
Ciminiera, Luigi, “Pipelined Arrays for Modular Multiplication”, IEEE, Monterey, CA, May 31-Jun. 3, 1998, pp. 397-400, XP000873523.
PCT Written Opinion Dated Sep. 5, 2001 for PCT/US00/26073 filed Sep. 22, 2000.
PCT International Search Report dated Aug. 29, 2001 for PCT/US01/26073 filed Sep. 22, 2000.
Jennings, William T., Dunham, James G., “Key Escrowing Systems and Limited One Way Functions”, Conference Proceedings, vol. I, 19th National Information Systems Security Conference, Baltimore, MD, Oct. 22-25, 1996, 11 pages.
Higgins, John C., “Evaluating the Strength of Ciphers”, National Institute of Standards and Technology/National Computer Security Center, 18th National Information Systems Security Conference, Baltimore, MD, Oct. 10-13, 1995, pp. 395-403.
Alves-Foss, Jim, “The Use of Belief Logics in the Presence of Causal Consistency Attacks”, Conference Proceedings, 20th National Information Systems Security Conference, Baltimore, MD, Oct. 1997, 12 pages.
Burrows, Michael, et al, “A Logic of Authentication”, Association for Computing Machinery, Transactions on Computer Systems, Feb. 1990, vol. 8, No. 1, pp. 18-36.
Rivest, R. L., et al, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, Feb. 1978, vol. 21, No. 2, pp. 120-126.
Cover Page and LOC publication information page (2 pgs) for: Welsh, Dominic, “Codes and Cryptography”, Oxford University Press, Oxford, UK, 1988, LOC No. Z103.W46, containing 257 pages.
Rabin, Michael O., “Digitalized Signatures and Public-Key Functions As Intractable as Factorization”, MIT Laboratory for Computer Science, TR-212, Jan. 1979, pp. 1-16.
Montgomery, Peter L., “Modular Multiplication Without Trial Division”, Mathematics of Computation, American Mathematical Society, Providence, RI, Apr. 1985, vol. 44, No. 170, pp. 519-521.
Cover Page and LOC publication information page (2 pgs) for: Soderstrand, Michael A., et al, “Residue Number System Arithmetic: Modern Applications in Digital Signal Processing”, IEEE Press, 1986, LOC No. QA247.35.R45.
Di Claudio, Elio D., Piazza, Francesco, “Fast Combinatorial RNS Processors for DSP Applications”, IEEE Transactions on Computers, May 1995, vol. 44, No. 5, pp. 624-633.
Alia, Giuseppe, Martinelli, Enrico, “A VLSI Modulo m Multiplier”, IEEE Transactions on Computers, Jul. 1991, vol. 40, No. 7, pp. 873-878.
Paliouras, V., et al., “Systematic Derivation of the Processing Element of a Systolic Array Based on Residue Number System”, 1992 IEEE International Symposium on Circuits and Systems, May 10-13, 1992, San Diego, CA, vol. 2 of 6, pp. 815-818.
Parhami, Behrooz,, Hsun-Feng Lai, “Alternate Memory Compression Schemes for Modular Multiplication”, IEEE Transactions on Signal Processing, Mar. 1993, vol. 41, No. 3, pp. 1378-1385.
Walter, Colin D., “Systolic Modular Multiplication”, IEEE Transactions on Computers, Mar. 1993, vol. 42, No. 3, pp. 376-378.
Blase, Matt, et al., “The Risks of Key Recovery, Key Escrow, and Trusted Third Party Encryption”, Presentation at the 1998 RSA Data Security Conference, Jan. 1998, San Francisco, CA, 21 pages.
Abelson, Hal, et al, “The Risks of Key Recovery, Key Escrow, and Trusted Third Party Encryption”, May 27, 1997 (report on-line, accessed Jan. 18, 1998), 29 pages.
Merkle, R.C.,Secure Communications Over Insecure Channels, Communications of the ACM, Apr. 1978, vol. 21, No. 4, pp. 294-299.
Barlow, J.P., “A Plain Text on Crypto Policy”, Communications of the ACM, vol. 36, No. 11, Nov. 1993, pp. 21-26.
Holleyman, Robert W. “On the Export of Software with Encryption Capabilities”, testimony presented at Key Escrow Meeting, National Institute of Standards and Technology, Gaithersburg, MD, Sep. 6, 1995, pp. 1-7.
Cover Page and LOC publication information page (2 pgs) for: Schwartau, Winn, “Information Warfare: Chaos on the Electronic Superhighway”, Thunder's Mouth Press, New York, 1994, LOC No. QA76.9.A25S354, containing 432 pgs.
Staniford-Chen, Heberlein, L. Todd, “Holding Intruders Accountable on the Internet”, Proceedings of the 1995 IEEE Symposium on Security and Privacy, May 8-10, 1995, Oakland, CA, pp. 39-49.
Walker, S.T., et al, “Commercial Key Escrow: Something for Everyone Now and for the Future”, Trusted Information Systems, Inc., Report #541, Jan. 3, 1995, 10 pages.
Ameke, David, “Clipper Chip Technology”, AT&T Media Relations/Marketing Communications, May 1993, 21 pages.
Madsen, Wayne, “Information Warfare: Indications and Warnings”, Conference Proceedings, 19th National Information Systems Security Conference, Baltimore, MD, Oct. 22-25, 1996, pp. 726-736.
Denning, Dorothy E., “Descriptions of Key Escrow Systems”, unpublished, http:/www.cosc.georgetown.edu/˜denning/crypto /Appendix html, Feb. 26, 1997, 38 pages.
Cover Page and LOC publication information page (2 pgs) for: Aho, Alfred, “Currents in the Theory of Computing”, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1973, LOC No. QA267.5.S4A33, containing 245 pages.
Orup, Holger, “Simplifying Quotient Determination in High-Radix Modular Multiplication”, Proceedings of the 12th Symposium on Computer Arithmetic, Jul. 19-21, 1995, Bath, England, sponsored by the IEEE Computer Society Technical Committee on VLSI, pp. 193-199.
PCT Invitation to Pay Additional Fees, dated Mar. 20, 2001 for PCT/US00/26073 filed Sep. 22, 2000, 4 pages.

Affiliated with

Also associated with

Rating

Multiplication of modular numbers does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiplication of modular numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplication of modular numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3500768