Technique for producing a parameter, such as a checksum,...

Details Technique for producing a parameter, such as a checksum,... Technique for producing a parameter, such as a checksum,...

1999-06-09

2002-11-19

Hayes, Gail (Department: 2131)

Cryptography

Particular algorithmic function encoding

Reexamination Certificate

active

06483918

ABSTRACT:

BACKGROUND OF THE DISCLOSURE
1. Field of the Invention
The invention relates to a technique for implementing a primitive for computing, e.g., a checksum. Advantageously, this technique is relatively simple and uses rather elementary register operations, thus saving significant processing time over that conventionally required to compute, e.g., a message authentication code (MAC), or implement a stream cipher.
2. Description of the Prior Art
Many different cryptographic techniques currently in use today employ mathematical functions that include modular arithmetic, typically calculating a residue of a number with respect to a relatively large prime number (M), such as, for example, 2
31
−1 or larger. An illustrative such function, f(x), would be of the form ƒ(x)=ax+bmod(M) in a Galois field (GF) over 2
n
, where n=2m+1, and n and m are predefined integers in a field Z(mod M). While the functions themselves greatly vary from one technique to the other, they commonly require computation of a mod(M) operation of one form or another and usually on a highly repetitive basis.
Not only will such modular operations be used for encrypting each and every block of plaintext in a message to yield a corresponding ciphertext block and decrypting the latter to recover the associated plaintext block, but also in computing intermediate portions of the technique, such as a message authentication code (MAC) or a stream cipher.
Performing a single mod(M) operation can require as many as 10-15 processing cycles, if not more (based on the value of a modulus, M). Since a cryptographic technique requires a large number of such operations, a significant amount of processing time, associated with employing that technique, can be consumed in simply calculating mod(M) operations.
Cryptographic techniques are increasingly finding use to protect information in a wide and expanding variety of highly diverse applications, as well as in a expanding array of devices, from highly sophisticated general purpose devices, such as, e.g., personal computers and workstations, to relatively simple dedicated devices, such as, e.g., “smart cards”, remote controls and electronic appliances.
For example, in view of the ease and low cost of communicating by electronic mail, the Internet (among other network modalities) is experiencing explosive and exponential growth as a preferred communication medium. However, the Internet, being a publicly accessible network, is not secure and, in fact, has been and increasingly continues to be a target of a wide variety of attacks from various individuals and organizations intent on eavesdropping, intercepting and/or otherwise compromising or even corrupting Internet message traffic or illicitly penetrating Internet sites. This security threat, in view of an increasing reliance placed on use of the Internet as a preferred medium of communication, exacerbates the efforts in the art to develop increasingly strong cryptographic techniques that provide enhanced levels of security to electronic communication, such as mail messages, data and computer files, from third-party eavesdropping, interception and possible tampering. As a consequence, cryptographic processing is being incorporated into an increasing array of personal computer software, particularly web browsers and other operating system components, and electronic mail programs and other application programs, in order to provide secure Internet connectivity.
A totally different cryptographic application involves so-called “smart cards”. Here, a dedicated credit-card sized device which employs a rather unsophisticated and inexpensive microprocessor, i.e., a “smart card”, stores bank and/or other financial balances for a corresponding individual. The microprocessor, using a program stored internally to the card, can validate a transaction and appropriately change each such balance based on the transaction. Specifically, that individual can invoke an electronic transaction with another party, such as a vendor or a bank, by simply inserting the card into an appropriate data terminal and entering transaction data into a keyboard associated with the terminal in order to debit and/or credit all or a portion of a balance stored on the card. Transacting in this fashion provides an instantaneous monetary transfer while eliminating any need for and costs associated with processing paper currency or paper-based monetary instruments, such as checks. The stored program utilizes extremely strong cryptographic techniques to protect the information stored on the card, particularly the balances, from illicit third party access and tampering.
However, as noted above, cryptography incurs processing overhead. While in sophisticated devices having significant processing capacity, such as PCs and workstations, the overhead reduces overall system throughput, in other devices, with rather limited processing capacity, such as smart cards, remote controls and other “low-end” devices, the overhead may be intolerable to the point of precluding the use of sufficiently strong cryptographic techniques in such devices.
Hence, given the rapid and apparently ever-increasing desire in the art to incorporate cryptographic techniques into a wide variety of devices, particularly those having limited processing power, a need currently exists in the art to reduce the processing time required to implement cryptographic techniques.
In particular, processing overhead associated with certain cryptographic techniques, particularly in computing a checksum, might be sharply reduced if a mod(M) operation could be replaced by an equivalent though less processor-intensive operation(s). If this result could be achieved, then the overall throughput of highly sophisticated devices, such as personal computers and workstations that employ various cryptographic techniques, could be advantageously increased. Furthermore, if such overhead could be reduced, then strong cryptographic techniques could be incorporated into a multitude of computer-related devices which heretofore had insufficient processing power to adequately support such techniques.
SUMMARY OF THE INVENTION
Advantageously, our present invention satisfies this need by implementing a primitive for computing a checksum but advantageously without any need for a mod(M) operation.
In accordance with our broad inventive teachings, this primitive replaces the mod(M) operation with a series of simple elementary register operations. These operations include mod 2
n
multiplications, order manipulations (e.g., byte or word swaps), and additions—all of which are extremely simple to implement and require very few processing cycles to execute. Use of our inventive technique can significantly reduce the processing time over that conventionally required to compute various cryptographic parameters, such as, e.g., a message authentication code (MAC), or to implement a stream cipher.
Specifically, an elemental, illustrative and non-invertible version of our technique relies on computing the primitive through the following sequence of equations:
x
S
←wordswap(
x
)
y←Ax+Bx
S
mod(2
n
)
y
S
←wordswap(
y
)
z←Cy
S
+yD
mod(2
n
)
&thgr;←z+y
S
E
mod(2
n
)
where:
coefficients A, B, C, D and E are each an odd random integer less than or equal to 2
n
; and
&thgr; is an n-bit string.
For use in generating a MAC or other cryptographic parameter, the coefficients are “secret”; however, when used to generate a checksum, these coefficients are publicly known.
Advantageously, our inventive technique has, as its feature, both invertible and non-invertible variants.


REFERENCES:
patent: 5724428 (1998-03-01), Rivest
Dorthy Denning Cryptography and Data Security, Addison-Wesley Publishing, pp. 59-64, 71-72, 90-93, 135-138, 147, 1982.*
Bruce Schneier, Applied Cryptography, John Wiley, pp. 445-447, Oct. 1995.*
Bosselaers, et. al. Comparison of three modular reduction functions, CRYPTO '93, pp. 175-186, 1982.*
Tucker,The Computer Science and Engineering Handbook,CRC Press, 1992, pp. 398-40

Affiliated with

Also associated with

Rating

Technique for producing a parameter, such as a checksum,... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Technique for producing a parameter, such as a checksum,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for producing a parameter, such as a checksum,... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2951861