Determining message residue using a set of polynomials

Details Determining message residue using a set of polynomials Determining message residue using a set of polynomials

2006-10-12

2010-11-02

Chaudry, M. Mujtaba K (Department: 2112)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S758000

Reexamination Certificate

active

07827471

ABSTRACT:
A method is described for use in determining a residue of a message. The method includes loading at least a portion of each of a set of polynomials derived from a first polynomial, g(x), and determining the residue using a set of stages. Individual ones of the stages apply a respective one of the derived set of polynomials to data output by a preceding one of the set of stages.

REFERENCES:
patent: 3980874 (1976-09-01), Vora
patent: 4945537 (1990-07-01), Harada
patent: 4949294 (1990-08-01), Wambergue
patent: 4979174 (1990-12-01), Cheng et al.
patent: 5166978 (1992-11-01), Quisquater
patent: 5363107 (1994-11-01), Gertz et al.
patent: 5384786 (1995-01-01), Dudley et al.
patent: 5642367 (1997-06-01), Kao
patent: 5768296 (1998-06-01), Langer et al.
patent: 5942005 (1999-08-01), Hassner et al.
patent: 6038577 (2000-03-01), Burshtein
patent: 6128766 (2000-10-01), Fahmi et al.
patent: 6223320 (2001-04-01), Dubey et al.
patent: 6484192 (2002-11-01), Matsuo
patent: 6609410 (2003-08-01), Axe et al.
patent: 6721771 (2004-04-01), Chang
patent: 6728052 (2004-04-01), Kondo et al.
patent: 6732317 (2004-05-01), Lo
patent: 6795946 (2004-09-01), Drummond-Murray et al.
patent: 6904558 (2005-06-01), Cavanna et al.
patent: 7058787 (2006-06-01), Brognara et al.
patent: 7171604 (2007-01-01), Sydir et al.
patent: 7190681 (2007-03-01), Wu
patent: 7243289 (2007-07-01), Madhusudhana et al.
patent: 7343541 (2008-03-01), Oren
patent: 7428693 (2008-09-01), Obuchi et al.
patent: 7458006 (2008-11-01), Cavanna et al.
patent: 7461115 (2008-12-01), Eberle, Hans et al.
patent: 7543214 (2009-06-01), Ricci
patent: 2002/0053232 (2002-05-01), Axe et al.
patent: 2002/0144208 (2002-10-01), Gallezot et al.
patent: 2003/0167440 (2003-09-01), Cavanna et al.
patent: 2003/0202657 (2003-10-01), She
patent: 2003/0212729 (2003-11-01), Eberle et al.
patent: 2004/0059984 (2004-03-01), Cavanna et al.
patent: 2004/0083251 (2004-04-01), Geiringer et al.
patent: 2005/0044134 (2005-02-01), Krueger et al.
patent: 2005/0138368 (2005-06-01), Sydir et al.
patent: 2005/0149725 (2005-07-01), Sydir et al.
patent: 2005/0149744 (2005-07-01), Sydir et al.
patent: 2005/0149812 (2005-07-01), Hall et al.
patent: 2005/0154960 (2005-07-01), Sydir et al.
patent: 2006/0059219 (2006-03-01), Koshy et al.
patent: 2006/0282743 (2006-12-01), Kounavis
patent: 2006/0282744 (2006-12-01), Kounavis
patent: 2007/0083585 (2007-04-01), St Denis et al.
patent: 2007/0150795 (2007-06-01), King et al.
patent: 2007/0297601 (2007-12-01), Hasenplaugh et al.
patent: 2008/0092020 (2008-04-01), Hasenplaugh et al.
patent: 2009/0157784 (2009-06-01), Gopal et al.
patent: 2009/0158132 (2009-06-01), Gopal et al.
patent: 2006016857 (2006-02-01), None
patent: 2008/002828 (2008-01-01), None
patent: 2008/002828 (2008-02-01), None
patent: 2008046078 (2008-04-01), None
patent: 2008046078 (2008-04-01), None
patent: 2009/012050 (2009-01-01), None
patent: 2009/012050 (2009-03-01), None
patent: 2009/082598 (2009-07-01), None
patent: 2009/085489 (2009-07-01), None
patent: 2009/085489 (2009-08-01), None
International Preliminary Report on Patentability for PCT Patent Application No. PCT/US2007/081312, mailed on Apr. 7, 2008, 4 pages.
International Search Report/Written Opinion for PCT Patent Application No. PCT/US2007/081312, mailed on Apr. 7, 2008, 9 Pages.
International Search Report/Written Opinion for PCT Patent Application No. PCT/US2008/085284, mailed on May 18, 2009, pp. 11.
Hasenplaugh, W. et al., “Fast Modular Reduction”, Proceedings of the 18th IEEE Symposium on Computer Arithmetic, Jun. 25-27, 2007, pp. 225-229.
Kounavis, M. E., et al., “Novel Table Lookup-Based Algorithms for High-Performance CRC Generation”, IEEE Transactions on Computers, vol. 57, No. 11, Nov. 2008, pp. 1550-1560.
International Search Report & Written Opinion for Application No. PCT/US2007/071829, mailed on Dec. 12, 2007, 10 Pages.
Antoon, B. et al., “Comparison of three modular reduction function”, Comparative Description and Evaluation, Oct. 25, 1993, pp. 13.
Chin, B. L., et al., “Design and Implementation of Long-Digit Karatsuba's Multiplication Alogorithm Using Tensor Product Formulation”, Workshop on Compiler Techniques for High Performance Computing, 2003, 8 Pages.
International Preliminary Report on Patentability for PCT Patent Application No. PCT/US2007/071829, mailed on Jan. 15, 2009, 7 pages.
Nedjah, N. et al., “A Review of Modular Multiplication Methods and Respective Hardware Implementation”, Informatica, vol. 30, No. 1, 2006, pp. 20.
Nedjah, N. et al., “A reconfigurable recursive and efficient hardware for Karatsuba-Ofman's multiplication algorithm”, Retrieved on Apr. 16, 2010 , Available at: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F8665%2F27464%2F01223160.pdf%3Farnumber%3D1223160&authDecision=-203.
International Search Report/Written Opinion for Patent Application No. PCT/US2008/084571, mailed Jun. 18, 2009, 11 pages.
International Search Report/ Written Opinion for PCT Patent Application No. PCT/US2008/068801, mailed on Dec. 31, 2008, 10 pages.
Barrett: Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor; Computer Security LTD Aug. 1986, 13 pages (Crypto '86, LNCS 263, pp. 311-323, 1987; copyright Springer-Verlag Berlin Heidelberg 1987).
Dhem: Design of an Efficient Public-Key Cryptographic Library for RISC-Based Smart Cards; Faculte Des Sciences appliquees Laboratoire de Microelectronique; Louvain-la-Neuve, Belgium, May 1998, 198 pages.
Fischer et al: Duality Between Multiplicatio and Modular Reduction; Infineon Technologies AG, Secure Mobile Solutions, Munich, Germany; Intel Corp., Systems Tech. Labl, Hillsboro, OR; pp. 1-13, 2005.
Koc et al: Analyzing and Comparing Montgomery Multiplication Algorithms; IEEE Micro, 16(3): 26-33, Jun. 1996; Dep't of Electrical & Computer Engineering, OSU, Corvallis, Oregon,; pp. 1-18.
Montgomery: Five, Six, and Seven-Term Karatsuba-Like Formulae; IEEE Transactions on Computers, vol. 54, No. 3, Mar. 2005, 8 pages.
Montgomery: Modular Multiplication Without Trial Division; Mathematics of Computation, vol. 44, No. 170, Apr. 1985, pp. 519-521.
Number Theory and Public Key Cryptography; Introduction to Number Theory, pp. 1-14, 1996.
Phatak et al: Fast Modular Reduction for Large Wordlenghts via One Linear and One Cyclic Convolution, Computer Science & Electrical Engineering Dep't, Univ. of Mayland, Baltimore, MD; 8 pages, 2005.
Sedlak: The RSA Cryptography Processor; Institut fur Theoretische Informatik, Germany, Copyright 1998, Springer-Verlag, pp. 95-105, 14 pages total.
Tenca et al: A Scalable Architecture for Montgomery Multiplication; Electrical & Computer Engineering; OSU, Corvallis, OR,; Cryptographic Hardware and Embedded Systems, CHES 99, C.K. Koc et al, Lecture Notes in computer Science, No. 1717, pages 94-108, New York, NY: Springer-Verlag, 1999.
Weimerskirch et al: Generalizations of the Karatsuba Algorithm for Polynomial Multiplication; communication Security Group, Dep't of Electrical Engineering & Info. Sciences, Bochum, Germany, Mar. 2002; pp. 1-23.
Ramabadran et al.: A Tutorial on CRC Computations; Aug. 1998 IEEE (Dep't of EE&CE, Iowa), pp. 62-74, 14 pages total.
Lin et al: High-Speed CRC Design for 10 Gbps applications; ISCAS 2006, IEEE, (Dep't of Electrical Engineering, Taiwan, ROC), pp. 3177-3180, 4 pages total.
Williams: A Painless Guide to CRC Error Detection Algorithms Version 3; Aug. 19, 2003; Copyright Ross Williams, 1993; 37 pages.
Sprachmann: Automatic Generation of Parallel CRC Circuits; Generation of Parallel Circuits; IEEE Design & Test of Computers May-Jun. 2001; pp. 108-114, 7 pages total.
Koopman et al.: cyclic Redundancy Code (CRC) Polynomial Selection for Embedded Networks; Preprint: The In'tl Conference on Dependable Systems and Networks, DSN-2004 pp. 1-10.
Campobello et al.: Parallel CRC Realization; IEEE Transactions on Computers, vol. 52, No. 10, Oct. 2003; Published by the IEEE Computer Society

Affiliated with

Also associated with

Rating

Determining message residue using a set of polynomials does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Determining message residue using a set of polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining message residue using a set of polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4150052