Source: https://patents.google.com/patent/US8689078
Timestamp: 2018-02-18 19:07:27
Document Index: 639726387

Matched Legal Cases: ['Application No. 20105161332', 'Application No. 200610172839', 'Application No. 200610172839', 'Application No. 200610172839', 'Application No. 200610179839', 'Application No. 200610179839', 'Application No. 200880106206', 'Application No. 200880106206']

US8689078B2 - Determining a message residue - Google Patents
Determining a message residue
US8689078B2
US8689078B2 US11777538 US77753807A US8689078B2 US 8689078 B2 US8689078 B2 US 8689078B2 US 11777538 US11777538 US 11777538 US 77753807 A US77753807 A US 77753807A US 8689078 B2 US8689078 B2 US 8689078B2
US11777538
US20090019342A1 (en )
A technique of determining a message residue includes accessing a message and simultaneously determining a set of modular remainders with respect to a polynomial for different respective segments of the message. The technique also includes determining a modular remainder with respect to the polynomial for the message based on the set of modular remainders and a set of constants determined prior to accessing the message. The modular remainder with respect to the polynomial for the message is stored in a memory.
FIG. 1 is a diagram illustrating determination of a message residue.
FIG. 2 is a diagram illustrating operations to determine a message residue.
FIG. 3 is a diagram illustrating table lookups that can be used in determining a message residue.
Determining residue of a message occurs frequently in a variety of applications. This computation often represents significant overhead in processing a message, for example, for transmission or after receipt. The following describes techniques that can speed this computation by permitting simultaneous processing of different portions of a message.
To illustrate, FIG. 1 depicts CRC computation of a message M 100 of length 3N-bits. The bits of the message M represent coefficients of a polynomial M(x). As described above, a CRC is the modular remainder of the message, M(x), with respect to a polynomial P(x) modulus (“poly”):
CRCM(x)=M(x)mod P(x) [1]
where P(x) is another polynomial represented by a bit-string. In practice, P(x) is defined for different applications. For example, iSCSI (Internet Small Computer System Interface), which uses CRC for end-to-end data protection, uses the value of 11EDC6F41H16 as the polynomial P(x). Other applications have selected different polynomial sizes and values. For a typical k-bit CRC residue, P(x) will be a k-bit polynomial (e.g., 32-bits) and M will be a message m(x) shifted k-bits. The k-bit CRC value is typically stored in the vacant, least significant k-bits of M(x).
A CRC value reflects the value and position of each bit in a message M. However, as shown in FIG. 1, the CRC value may be computed in parallel by independently processing segments of the message and later combining the results in a way to preserve proper CRC computation. More precisely, the CRC of M(x) can be broken down into the computation of the CRC for different segments (A, B, C) of the message. For example:
CRCM(x)=(CRC(C)·K2)+(CRC(B)·K1)+(CRC(A)) [2]
where “+” represents polynomial addition (e.g., bitwise XOR) and “·” represents polynomial multiplication (e.g., carry-less multiplication of bit strings mod P(x)). The values of CRC (C), CRC (B), and CRC (A) can be independently and simultaneously computed to speed computation of the overall CRC value. The CRC values for each segment can then be combined into the overall CRC value of message M by polynomial multiplication, e.g., by constants K. For example, in the example shown in FIG. 1 which features uniform segments of size N-bits, K2=x2N mod poly and K1=xN mod poly where x2N and xN correspond to the significance of the segments within the message. Since x2N and xN are constants, and the modulus polynomial poly is constant, the values of K2 and K1 are, therefore, also constants that can be pre-computed before the value of message M is even accessed. That is, the values of constants, K, depends on the segmentation points and known value of poly, rather than the bit values of message M. In other words, a given set of constants determined for a given polynomial can be used for different messages. Sets of constants may be pre-computed and provided for the different polynomials used in practice. The values of the constants can be determined using a CRC operation. For example, in the above example, K2 can be computed as CRC (x2N) for a specified polynomial.
While FIG. 1 depicted three segments, other implementations may use different segmentation schemes using a different number of segments, segments of non-uniform size, and so forth. Additionally, while the values of these constants may be pre-computed, they may also be computed concurrently with the segment CRC values (e.g., during initial processing of a first message or, less efficiently, for each message processed).
The potential advantages of such a scheme can be quantified in different environments and implementations. For example, a processor may feature a dedicated CRC instruction (e.g., a CRC or other message residue processor macro-op). Such an instruction may have a syntax of:
CRC (input-bit-string, message-residue)
where the input-bit-string (e.g., 64, 32, 16, 8, or other specified or hard-wired string length) can represent a portion of a message. Optionally, the instruction or a companion instruction may specify the polynomial or bit-string-width. The instruction can update the CRC message-residue value to reflect the incremental contribution of the new input-bit-string. Using such an instruction, computing the CRC of a message M can be done cumulatively, using a sequence of calls to the CRC instruction that consumes the message in input-bit-string sized chunks with each invocation of the CRC instruction incrementally updating the CRC value. After all data chunks are consumed, the remaining message residue reflects the CRC value of the message as a whole.
Such an instruction could be implemented by the following processor micro-ops which implement a 32-bit CRC operation:
TEMP1[63-0]←BIT_REFLECT64 (SRC[63-0])
TEMP2[31-0]←BIT_REFLECT32 (DEST[31-0])
TEMP3[95-0]←TEMP1[63-0]<<32
TEMP4[95-0]←TEMP2[31-0]<<64
TEMP5[95-0]←TEMP3[95-0]XOR TEMP4[95-0]
TEMP6[31-0]←TEMP5[95-0]MODULO POLY
DEST[31-0]←BIT_REFLECT (TEMP6[31-0])
DEST[63-32]←00000000H
where BIT_REFLECT changes the endian representation of a string if necessary.
In the sample implementation to determine a CRC value described above, each CRC instruction required the output of a previous CRC instruction as input. This serial approach, however, consumes a number of processor cycles that is at least T*L where T is the CRC instruction cycle latency and L is the number of chunks. By contrast, computing the segments in parallel results in a latency of approximately (T*L/NumSegments) plus the latency of the recombination operations which is, by comparison, relatively insignificant. Generally, the later approach will represent a significant decrease in the time used to determine a CRC.
FIG. 2 illustrates a sample implementation that uses a processor provided CRC instruction. In the example depicted, the particular CRC instruction takes three cycles to complete. The timing diagram illustrates that the processor implements a multiple-instruction execution pipeline.
As shown, the CRC instruction operates on a sub-segments (e.g., A[i], B[i], and C[i] where i=1 to 3) of each segment in succession. The residue for each segment is stored in an incrementally updated residue variable. For example, the residue value, X, is updated for each sub-segment chunk (e.g., C[1], C[2], C[3]) of segment C. The residue values may be initialized to values appropriate to a given application (e.g., all 1-s for iSCSI).
Due to the pipeline architecture and latency of the CRC instruction, operations on chunks of a given segment are interleaved with operations on chunks of other segments. For example, as illustrated, the like-positioned chunks of segments A, B, and C (e.g., [A[1], B[1], and C[1]) are sequentially inserted 104 a-104 c into the pipeline. Once the segment residue for a given chunk has been updated, the next chunk for that segment can be processed. For example, after completion of CRC instruction 104 a for chunk C[1], CRC instructions 104 d can process chunk C[2]. The illustrated overlap between CRC instructions represents an overall latency reduction attributable to techniques described above.
As shown, after determining X, Y, and Z, recombination 106 proceeds. Potentially, recombination 106 can overlap the CRC computations. For example, determining X·K2 may be initiated as soon as the value of X is determined instead of waiting for the values of Y and Z. Potentially, the message residue values of X, Y, and Z may be stored in the message itself (e.g., the value of X may be stored in C[3], Y in B[3], and Z in A[3]) changing the message into sparse storage of the message residues.
While FIG. 2 illustrated a particular implementation for a given environment, many variations are possible. For example, computation of the segment CRC values may be determined by different processor elements (e.g., programmable processor cores of a processor integrated on a single die) in addition to or in lieu of pipeline processing. In addition, the number cycles of a CRC instruction may be larger or smaller than the 3-cycle implementation depicted. Potentially, the number of message segments may be based on (e.g., equal to) the number of cycles used by a CRC instruction. For example, a 4-cycle instruction may be paired with an implementation that divides messages into 4-segments and process the 4-segments simultaneously. Further, while a dedicated CRC instruction was depicted, the techniques may also be applied where no explicit dedicated CRC instruction is provided by a processor. Additionally, again, while a CRC computation was illustrated in FIG. 2, techniques described above may be used in other message residue determinations.
Additional variations can further or independently speed computation of a message residue. For example, the approach illustrated above computed (CRC(segment)·K). A straight-forward implementation can simply perform this polynomial multiplication and modular reduction after determining a segment's CRC value. However, since K and poly are constants, this operation can instead be implemented using a set of lookup tables. For example, as shown in FIG. 3, modular polynomial multiplication of a segment's CRC value (denoted Y) 108 by a constant K can be expressed as:
Y·K=Y 3(D 3 ·K)mod poly+Y 2(D 2 ·K)mod poly+Y 1(D 1 ·K)mod poly+Y 0 mod poly [4]
where Yi represent n-bit segments of Y, and Di represent constants of xDi. The values of (Di·K) represent the modular polynomial multiplication of two constants and, therefore, are also constant. Thus, instead of actually computing Yi (Di·K) mod poly, each value of Yi can be used as an n-bit lookup key into a table 110 a, 110 b, 110 c storing pre-computed possible values of Yi (Di·K) mod poly. For example, where Y is a 32-bit number, table 110 a may store pre-computed values of Y3 (D3·K) mod poly for lookup by the 8-bit value of Y3. Such tables can speed these computations considerably without consuming excessive amounts of data storage. Additionally, such lookups may be performed in parallel. The resulting lookup values can be quickly summed using polynomial addition.
The above described CRC message residues. Such residues can be stored Random Access Memory, for example, in a packet stored in memory or for comparison with residues stored in received packets, for example, to determine whether data corruption has likely occurred. The techniques described above are not limited to CRCs, however, but may be used in other schemes, such as other coding/error correction schemes that operate on modular residue, for example, in a finite field of polynomials over GF(2). Additionally, while the above techniques repeatedly performed modular reduction on intermediate values, such modular reduction may be deferred or performed at other junctures.
The techniques described above may be implemented in a variety of logic that includes hardware, software, and/or firmware or a combination thereof. For example, techniques described above may be implemented as instructions of a computer program disposed on a computer readable medium that causes a processor to perform the message residue determination described above.
accessing a message;
splitting said message into a plurality N of different message segments S[y] representing a first polynomial for the message, S[y] represents a message segment and y=1 to N, each message segment S[y] comprising a plurality of n sub-segments Ss[x], wherein x=1 to n;
simultaneously determining a residue of like-ordinal sub-segments Ss[x] of each of the message segments S[y] in different clock cycles of a multi-cycle pipeline;
storing said residue of said like-ordinal sub-segments Ss[x] in an incrementally updated residue value;
determining a set of modular remainders based on said incrementally updated residue value for each of said plurality of different respective segments S[y] of the message;
determining a message modular remainder with respect to the first polynomial for the message based on a contribution of each of the set of modular remainders for different respective segments S[y] of the message and a set of values determined prior to accessing the message, the set of values being based on the first polynomial;
storing the message modular remainder with respect to the first polynomial for the message; and
performing at least one of: (1) including the determined message modular remainder in a packet stored in Random Access Memory; and (2) comparing the determined message modular remainder with a modular remainder value included in a received packet.
wherein the determining a message modular remainder with respect to the first polynomial for the message based on the contribution of each of the set of modular remainders and a set of values determined prior to accessing the message comprises:
determining based on:
( ∑ i = Sto ⁢ ⁢ 1 ⁢ R i · K i ) + R 0
S is a number of segments of the message;
Ri is a residue associated with a segment, i, of the message;
Ki is a value based on xsegmentation-point i mod the first polynomial;
· represents modular polynomial multiplication with respect to the first polynomial; and
+ represents polynomial addition.
wherein determining Ri·Ki comprises performing multiple table lookups for sub-segments of Ri using the sub-segments of Ri as the lookup keys.
4. A computer readable medium comprising instructions for causing a processor to:
access a message;
split said message into a plurality N of different message segments S[y] representing a first polynomial for the message, S[y] represents a message segment and y=1 to N, each message segment S[y] comprising a plurality of n sub-segments Ss[x], wherein x=1 to n;;
simultaneously determine a residue of like-ordinal sub-segments Ss[x] of each of the message segments S[y] in different clock cycles of a multi-cycle pipeline;
store said residue of said like-ordinal sub-segments Ss[x] in an incrementally updated residue value;
determine a set of modular remainders based on said incrementally updated residue value for each of said plurality of different respective segments S[y] of the message;
determine a message modular remainder with respect to the first polynomial for the message based on a contribution of each of the set of modular remainders for different respective segments S[y] of the message and a set of values determined prior to accessing the message, the set of values being based on the first polynomial;
store the message modular remainder with respect to the first polynomial for the message; and
perform at least one of: (1) including the determined message modular remainder in a packet stored in Random Access Memory; and (2) comparing the determined message modular remainder with a modular remainder value included in a received packet.
5. The computer readable medium of claim 4,
wherein the instructions for causing the processor to determine a message modular remainder with respect to the first polynomial for the message based on a contribution of each of the set of modular remainders and a set of values determined prior to accessing the message comprise instructions for causing the processor to:
determine based on:
· represents modular polynomial multiplication respect to the first polynomial; and
6. The computer readable medium of claim 4,
wherein instructions for causing the processor to determine Ri·Ki comprise instructions for causing the processor to perform multiple table lookups for sub-segments of Ri using the sub-segments of Ri as the lookup keys.
US11777538 2007-07-13 2007-07-13 Determining a message residue Active 2029-09-03 US8689078B2 (en)
US11777538 US8689078B2 (en) 2007-07-13 2007-07-13 Determining a message residue
PCT/US2008/068801 WO2009012050A3 (en) 2007-07-13 2008-06-30 Determining a message residue
JP2010516132A JP5384492B2 (en) 2007-07-13 2008-06-30 Determination of the message surplus
EP20080772266 EP2181386A4 (en) 2007-07-13 2008-06-30 Determining a message residue
CN 200880106206 CN101796482A (en) 2007-07-13 2008-06-30 Determining a message residue
US20090019342A1 true US20090019342A1 (en) 2009-01-15
US8689078B2 true US8689078B2 (en) 2014-04-01
ID=40254146
US11777538 Active 2029-09-03 US8689078B2 (en) 2007-07-13 2007-07-13 Determining a message residue
US (1) US8689078B2 (en)
JP (1) JP5384492B2 (en)
CN (1) CN101796482A (en)
EP (1) EP2181386A4 (en)
WO (1) WO2009012050A3 (en)
KR20100008849A (en) * 2008-07-17 2010-01-27 삼성전자주식회사 Apparatus and method for cyclic redundancy check in communication system
US8312363B2 (en) * 2008-12-16 2012-11-13 Intel Corporation Residue generation
US3980874A (en) 1975-05-09 1976-09-14 Burroughs Corporation Binary to modulo M translation
US4949294A (en) 1987-10-30 1990-08-14 Thomson-Csf Computation circuit using residual arithmetic
JPH0385923A (en) 1989-08-30 1991-04-11 Fujitsu Ltd Crc arithmetic system
US5384786A (en) * 1991-04-02 1995-01-24 Cirrus Logic, Inc. Fast and efficient circuit for identifying errors introduced in Reed-Solomon codewords
US5619516A (en) 1992-12-29 1997-04-08 Motorola, Inc. Efficient CRC remainder coefficient generation and checking device and method
US6128766A (en) * 1996-11-12 2000-10-03 Pmc-Sierra Ltd. High speed cyclic redundancy check algorithm
US20020053232A1 (en) 2000-09-29 2002-05-09 Axe John D. High strain rate tester for materials used in sports balls
US20020144208A1 (en) 2001-03-30 2002-10-03 International Business Machines Corporation Systems and methods for enabling computation of CRC' s N-bit at a time
US6484192B1 (en) 1998-01-29 2002-11-19 Toyo Communication Equipment Co., Ltd. Root finding method and root finding circuit of quadratic polynomial over finite field
US6530057B1 (en) 1999-05-27 2003-03-04 3Com Corporation High speed generation and checking of cyclic redundancy check values
US20030167440A1 (en) 2002-02-22 2003-09-04 Cavanna Vicente V. Methods for computing the CRC of a message from the incremental CRCs of composite sub-messages
US20030200500A1 (en) 2002-02-15 2003-10-23 Weissinger Steve H. Obtaining cyclic redundancy code
US20030202657A1 (en) 2002-04-30 2003-10-30 She Alfred C. Method and apparatus of fast modular reduction
US20040083251A1 (en) 2000-06-01 2004-04-29 Geiringer Felix Egmont Parallel modulo arithmetic using bitwise logical operations
US6732317B1 (en) 2000-10-23 2004-05-04 Sun Microsystems, Inc. Apparatus and method for applying multiple CRC generators to CRC calculation
US20040193993A1 (en) 2003-03-28 2004-09-30 Pulakesh Roy Error detection for multi-stream communications
US6912683B2 (en) 2000-02-17 2005-06-28 Analog Devices, Inc. Method, apparatus, and product for use in generating CRC and other remainder based codes
US20050149812A1 (en) 2003-11-19 2005-07-07 Honeywell International Inc. Message error verification using checking with hidden data
US7027597B1 (en) 2001-09-18 2006-04-11 Cisco Technologies, Inc. Pre-computation and dual-pass modular arithmetic operation approach to implement encryption protocols efficiently in electronic integrated circuits
US7058787B2 (en) 2003-05-05 2006-06-06 Stmicroelectronics S.R.L. Method and circuit for generating memory addresses for a memory buffer
US20060282743A1 (en) 2005-05-24 2006-12-14 Michael Kounavis Instructions for performing modulo-2 multiplication and bit reflection
US20060282744A1 (en) 2005-05-25 2006-12-14 Michael Kounavis Technique for performing cyclic redundancy code error detection
US7187770B1 (en) 2002-07-16 2007-03-06 Cisco Technology, Inc. Method and apparatus for accelerating preliminary operations for cryptographic processing
US20070150795A1 (en) 2005-12-23 2007-06-28 King Steven R Performing a cyclic redundancy checksum operation responsive to a user-level instruction
US20070297601A1 (en) 2006-06-27 2007-12-27 Hasenplaugh William C Modular reduction using folding
US20080144811A1 (en) 2006-12-14 2008-06-19 Intel Corporation Method for Simultaneous Modular Exponentiations
WO2009012050A2 (en) 2007-07-13 2009-01-22 Intel Corporation Determining a message residue
US20090157784A1 (en) 2007-12-18 2009-06-18 Vinodh Gopal Determining a message residue
US20090158132A1 (en) 2007-12-18 2009-06-18 Vinodh Gopal Determining a message residue
US20090164546A1 (en) 2007-12-21 2009-06-25 Vinodh Gopal Method and apparatus for efficient programmable cyclic redundancy check (crc)
US20090168999A1 (en) 2007-12-28 2009-07-02 Brent Boswell Method and apparatus for performing cryptographic operations
US20120124445A1 (en) 2008-08-04 2012-05-17 Hargan Ebrahim H Multiple device apparatus, systems, and methods
JP3545623B2 (en) * 1999-01-05 2004-07-21 株式会社エヌ・ティ・ティ・ドコモ Decoding method
US6609410B2 (en) 2000-09-29 2003-08-26 Spalding Sports Worldwide, Inc. High strain rate tester for materials used in sports balls
EP1499024A1 (en) 2002-04-22 2005-01-19 Fujitsu Limited Error-detection encoder and decoder, and divisor
WO2008002828A2 (en) 2006-06-27 2008-01-03 Intel Corporation Modular reduction using folding
WO2009082598A1 (en) 2007-12-18 2009-07-02 Intel Corporation Determining a message residue
WO2009085489A2 (en) 2007-12-21 2009-07-09 Intel Corporation Method and apparatus for efficient programmable cyclic redundancy check (crc)
"Federal Information Processing Standards Publication 197". Announcing the Advanced Encryption Standard (AES), Nov. 26, 2001, pp. 1-51.
"Number Theory and Public Key Cryptography"; Introduction to Number Theory, pp. 1-14.
Barrett, "Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor", Proceedings on Advances in cryptology-CRYPTO '86,Copyright (c) 1998, Springer-Verlag, Berlin 1987, pp. 311-323.
Bosselaers et al., "Comparsion of three modular reduction function", Comparative Description and Evaluation, Katholieke Universiteit Leuven, Department of Electrical Engineering-ESAT Kardinaal Mercierlaan, Oct. 25, 1993, pp. 1-12.
Campobello et al., "Parallel CRC Realization", IEEE Transactions on Computers, vol. 52, No. 10, Oct. 2003, Published by the IEEE Computer Society; pp. 1312-1319.
Chin-Bou 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, pp. 1-8.
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.
Extended European Search Report from related application 08772266.6 dated Oct. 29, 2012.
Fischer et al., "Duality Between Multiplicatio and Modular Reduction", Infineon Technologies AG, Secure Mobile Solutions, Munich, Germany; Intel Corporation, Systems Technology Laboratory, Hillsboro. OR; pp. 1-13.
Hubaux et al., Word-parallel CRC computation on VLIW DSP, Electronics Letters, IEE Stevenage, Jan. 1, 2002.
Inernational Preiminary Report on Patentability for PCT Patent Application No. PCT/US2008/085284, mailed on Jul. 1, 2010, 6 pages.
International Preliminary Report on Patentability received for PCT Application No. PCT/US2008/084571 mailed on Jul. 1, 2010, 6 pages.
International Preliminary Report on Patentability received for PCT Patent Application No. PCT/US2007/071829, mailed on Jan. 15, 2009. 7 Pages.
International Preliminary Report on Patentability received for PCT Patent Application No. PCT/US2008/068801, mailed on Jan. 28, 2010, 6 pages.
International Search Report & Written Opinion received for PCT Patent Application No. PCT/US2007/071829, mailed on Dec. 12, 2007, 10 Pages.
International Search Report and Written Opinion for PCT Patent Application No. PCT/US2008/085284, mailed on May 18, 2009, 11 pages.
International Search Report and Written Opinion received for PCT Patent Application No. PCT/US2008/068801, mailed on Dec. 31, 2008, 10 pages.
International Search Report and Written Opinion received for PCT Patent Application No. PCT/US2008/084571, mailed Jun. 18, 2009, 11 pages.
Ji et al., Fast Parallel CRC Algorithm and Implementation on a Configurable Processor, Proceedings of IEEE International Conference on Communications, Apr. 28, 2002.
Koc et al., "Analyzing and Comparing Montgomery Multiplication Algorithms", IEEE Micro; vol. 16, No. 3, 26-33; Jun. 1996, pp. 1-18.
Koopman et al., "Cyclic Redundancy Code (CRC) Polynomial Selection for Embedded Networks", The International Conference on Dependable Systems and Networks, DSN-2004, pp. 1-10.
Kounavis et al., "A Sysematic Approach to Buiding High Perormance Software-based CRC Generators", Proceedings of the 10th IEEE Symposium on Computers and Communications, ISCC 2005; pp. 855-862.
Lin et al., "High-Speed CRC Design for 10 Gbps applications", ISCAS 2006. IEEE, pp. 3177-3180.
Lin et al.: High-Speed CRC Design for 10 Gbps Applications, ISCAS IEEE 2006, pp. 3177-3180.
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.
Nedjah et al., "A reconfigurable recursive and efficient hardware for Karatsuba-Ofman's multiplication algoritm", Proceedings of 2003 IEEE Conference on Control Applications, vol. 2, Jun. 23-25, 2003, pp. 1076-1081.
Nedjah et al., "A Review of Modular Multiplication Methods and Respective Hardware Implementation", Informatica, vol. 30, No. 1, 2006, pp. 111-129.
Notice of Reasons for Rejection dated Mar. 6, 2012 issued in related Japanese Patent Application No. 20105161332.
Office Action from related China application 200880106206.5 mailed Jan. 28, 2013.
Office Action from related China application 200880106206.5 mailed Jun. 20, 2013.
Office Action Received for Chinese Patent Application No. 200610172839.9, mailed on Feb. 6, 2009. 3 Pages of Chinese Office Action and 5 Pages of English Translation.
Office Action Received for Chinese Patent Application No. 200610172839.9, mailed on Jan. 8, 2010, 3 Pages of Chinese Office Action and 5 Pages of English Translation.
Office Action Received for Chinese Patent Application No. 200610172839.9, mailed on Sep. 18, 2009, 4 Pages of Chinese Office Action and 5 Pages of English Translation.
Office Action Received for Chinese Patent Application No. 200610179839.9, mailed on Apr. 15, 2010, 4 Pages of Chinese Office Action and 5 Pages of English Translation.
Office Action Received for Chinese Patent Application No. 200610179839.9, mailed on Jul. 30, 2010, 5 Pages of English Translation.
Office Action received for Chinese Patent Application No. 200880106206.5, mailed on May 10, 2011, 9 pages of Office Action including 6 pages of English Translation.
Office Action Received for the Chinese Application No. 200880106206.5, mailed on May 17, 2012, 16 pages of Office Action including 10 Pages of English Translation.
Office Action Received for U.S. Appl. No. 11/476,432, mailed on May 26, 2010, 13 Pages.
Office Action Received for U.S. Appl. No. 11/476,432, mailed on Oct. 28, 2009, 24 Pages.
Office Action received for U.S. Appl. No. 11/610,919, mailed on Jul. 8, 2010, 7 pages.
Office Action received for U.S. Appl. No. 11/959,142, mailed on Jun. 30, 2010, 11 pages.
Phatak at al., "Fast Modular Reduction for Large Wordlengths via One Linear and One Cyclic Convolution", Proceedings of the 17th IEEE Symposium on Computer Arithmetic, 2005; pp. 179-186.
Ramabadran et al., "A Tutorial on CRC Computations", Micro, IEEE, IEEE Computer Society, Aug. 1988, pp. 62-75.
Sedlak, "The RSA Cryptography Processor", Lecture Notes in Computer Science, Proceedings of the 6th annual international conference on Theory and application of cryptographic techniques, Springer-Verlag Bedin, Heidelberg, pp. 95-105.
Sedlak. "The RSA Cryptography Processor", Lecture Notes in Computer Science, Proceedings of the 6th annual international conference on Theory and application of cryptographic techniques, 1987, Springer-Verlag Berlin, Heidelberg, pp. 95-105.
Sprachmann, "Automatic Generation of Parallel Circuits", IEEE Design and Test of Computers May-Jun. 2001; pp. 108-114.
Tenca et al., "A Scalable Architecture for Montgomery Multiplication". Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science,. No. 1717, Springer-Verlag London, UK, 1999, pp. 94-108.
Weimerskirch et al., "Generalizations of the Karatsuba Algorithm for Polynomial Multiplication"; communication Security Group, Department of Electrical Engineering & Information Sciences, Bochum, Germany, Mar. 2002; pp. 1-23.
Williams, "A Painless Guide to CRC Error Detection Algorithms", Version 3; Aug. 9. 2003, Copyright 1993; 37 pages.
Williams: A Painless Guide to CRC Error Detection Algorithms; Aug. 19, 1993; 31 pages.
CN101796482A (en) 2010-08-04 application
EP2181386A2 (en) 2010-05-05 application
JP5384492B2 (en) 2014-01-08 grant
WO2009012050A3 (en) 2009-03-12 application
EP2181386A4 (en) 2012-11-28 application
US20090019342A1 (en) 2009-01-15 application
JP2010534007A (en) 2010-10-28 application
WO2009012050A2 (en) 2009-01-22 application
US7155658B2 (en) 2006-12-26 CRC calculation for data with dynamic header
US5936978A (en) 1999-08-10 Shortened fire code error-trapping decoding method and apparatus
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:GUERON, SHAY;GOPAL, VINODH;FEGHALI, WAJDI;AND OTHERS;SIGNING DATES FROM 20070829 TO 20071031;REEL/FRAME:024279/0931