US5651069A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Software-efficient message authentication
Assignee: International Business Machines Corp
•
Filing: 1994-12-08
•
Granted: 1997-07-22
•
Expires: 2014-12-08
Abstract
Abstract Fast message authentication code generation is achieved by preprocessing a secret key into an efficiently-computable representation of a hash function selected from a family of hash functions that share a characteristic property. The secret key is also mapped into a particular cryptographic transform. The hash function and the transform are used to generate the authentication code. In particular, the hash function is applied to the message to generate a hashed message. The cryptographic transform is then applied to the hashed message to generate a tag. The tag and possibly other information (such as the state of a counter) are then combined to create the authentication code.
Inventors
- 👤 Phillip W. Rogaway
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:57
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/32; H04L9/3236; H04L9/3242; H04L2209/00; H04L2209/84
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
103 words
A method, using a key and implementable on a computer, for hashing a message consisting of a sequence of words into a string having a length shorter than the length of the message, comprising the steps of: (a) mapping the key into an association of each word of the string to a set of words of the message; (b) forming each word of the string by combining the words of the message associated therewith: wherein the association is represented as a table specifying, for each word of the string, the words of the message to which said word of the string is associated.
Claim 2
Independent Claim
103 words
A method, using a key and implementable on a computer, for hashing a message consisting of a sequence of words into a string having a length shorter than the length of the message, comprising the steps of: (a) mapping the key into an association of each word of the string to a set of words of the message; (b) forming each word of the string by combining the words of the message associated therewith: wherein the association is represented as a table specifying, for each word of the string, the words of the message to which said word of the string is associated.
Claim 3
Independent Claim
103 words
A method, using a key and implementable on a computer, for hashing a message consisting of a sequence of words into a string having a length shorter than the length of the message, comprising the steps of: (a) mapping the key into an association of each word of the string to a set of words of the message; (b) forming each word of the string by combining the words of the message associated therewith: wherein the association is represented as a table specifying, for each word of the message, the words of the string to which said word of the message is associated.
Claim 4
Independent Claim
103 words
A method, using a key and implementable on a computer, for hashing a message consisting of a sequence of words into a string having a length shorter than the length of the message, comprising the steps of: (a) mapping the key into an association of each word of the string to a set of words of the message; (b) forming each word of the string by combining the words of the message associated therewith: wherein the association is represented as a table specifying, for each word of the message, the words of the string to which said word of the message is associated.
Claim 5
Independent Claim
106 words
A method, using a key and implementable on a computer, for hashing a message consisting of a sequence of words into a string having a length shorter than the length of the message, comprising the steps of: (a) mapping the key into an association of each word of the string to a set of words of the message; (b) forming each word of the string by combining the words of the message associated therewith: wherein the association is represented by a sequence of instructions executable on the computer, this sequence of instructions computing each word of the string by combining the associated words of the message.
Claim 6
Independent Claim
106 words
A method, using a key and implementable on a computer, for hashing a message consisting of a sequence of words into a string having a length shorter than the length of the message, comprising the steps of: (a) mapping the key into an association of each word of the string to a set of words of the message; (b) forming each word of the string by combining the words of the message associated therewith: wherein the association is represented by a sequence of instructions executable on the computer, this sequence of instructions computing each word of the string by combining the associated words of the message.
Claim 7
Dependent Claim
21 words
The method as described in claim 1 wherein each word of the message is associated to two words of the string.
Claim 8
Dependent Claim
21 words
The method as described in claim 1 wherein each word of the message is associated to three works of the string.
Claim 9
Independent Claim
87 words
A method, using a key and implementable on a computer, for hashing a message consisting of a sequence of words into a string having a length shorter than the length of the message, comprising the steps of: (a) mapping the key into an association of each word of the string to a set of words of the message; (b) forming each word of the string by combining the words of the message associated therewith; wherein the words of the message are combined by an exclusive OR operation.
Claim 10
Independent Claim
87 words
A method, using a key and implementable on a computer, for hashing a message consisting of a sequence of words into a string having a length shorter than the length of the message, comprising the steps of: (a) mapping the key into an association of each word of the string to a set of words of the message; (b) forming each word of the string by combining the words of the message associated therewith; wherein the words of the message are combined by an exclusive OR operation.
Claim 11
Independent Claim
107 words
A method, using a key and implementable on a computer, to generate a message authentication tag useful in authenticating a message, comprising the steps of: mapping the key into an efficiently-computable representation of a hash function selected from a family of hash functions, wherein the family of hash functions is characterized by the property that the probability that distinct strings hash to the same value is small; applying the selected hash function to the message to generate a hashed message having length shorter than the length of the message; and applying a cryptographic transformation to the hashed message and the key to generate the message authentication tag.
Claim 12
Independent Claim
107 words
A method, using a key and implementable on a computer, to generate a message authentication tag useful in authenticating a message, comprising the steps of: mapping the key into an efficiently-computable representation of a hash function selected from a family of hash functions, wherein the family of hash functions is characterized by the property that the probability that distinct strings hash to the same value is small; applying the selected hash function to the message to generate a hashed message having length shorter than the length of the message; and applying a cryptographic transformation to the hashed message and the key to generate the message authentication tag.
Claim 13
Dependent Claim
39 words
The method as described in claim 7 wherein the hashed message is computed at least in part by forming a string, each word of the string being the exclusive OR of a subset of words drawn from the message.
Claim 14
Dependent Claim
34 words
The method as described in claim 8 wherein the efficiently-computable representation of the hash function is a table that specifies the subset of words that are exclusive-ORed to form each word of the string.
Claim 15
Dependent Claim
22 words
The method as described in claim 7 wherein the efficiently-computable representation is a sequence of instructions to be executed by a computer.
Claim 16
Dependent Claim
117 words
A computer, comprising: a storage device; program means supported in the storage device for generating a message authentication tag useful in authenticating a message, the program means comprising: means for mapping the key into an efficiently-computable representation of a hash function selected from a family of hash functions, wherein the family of hash functions is characterized by the property that the probability that distinct strings hash to the same value is small; means for applying the selected hash function to the message to generate a hashed message having a length shorter than the length of the message; and means for applying a cryptographic transformation to the hashed message and the key to generate the message authentication tag.
Claim 17
Dependent Claim
117 words
A computer, comprising: a storage device; program means supported in the storage device for generating a message authentication tag useful in authenticating a message, the program means comprising: means for mapping the key into an efficiently-computable representation of a hash function selected from a family of hash functions, wherein the family of hash functions is characterized by the property that the probability that distinct strings hash to the same value is small; means for applying the selected hash function to the message to generate a hashed message having a length shorter than the length of the message; and means for applying a cryptographic transformation to the hashed message and the key to generate the message authentication tag.
Claim 18
Dependent Claim
106 words
A program storage device readable by a processor and tangibly embodying a program of instructions executable by the processor to perform a method, using a secret key, for hashing a message into a string having a length shorter than the length of the message, wherein the method comprises the steps of: (a) mapping the key into an association of each word of the string to a set of words of the message; and (b) forming each word of the string by combining the words of the message associated therewith; wherein each word of the message is associated to a varying number of words of the string.
Claim 19
Dependent Claim
106 words
A program storage device readable by a processor and tangibly embodying a program of instructions executable by the processor to perform a method, using a secret key, for hashing a message into a string having a length shorter than the length of the message, wherein the method comprises the steps of: (a) mapping the key into an association of each word of the string to a set of words of the message; and (b) forming each word of the string by combining the words of the message associated therewith; wherein each word of the message is associated to a varying number of words of the string.
Claim 20
Independent Claim
142 words
A method for authenticating messages transmitted among a set of entities in a distributed computer system, comprising the steps of: establishing a secret key shared by the set of entities; having each of the entities map the secret key into an efficiently-computable representation of a hash function selected from a family of hash functions, wherein the family of hash functions is characterized by the property that the probability that distinct strings hash to the same value is small; having an entity desiring of transmitting a message apply the selected hash function to message to generate a hashed message having a length shorter than the length of the message; and having the entity apply a cryptographic transformation to the hashed message and the key to generate a message authentication tag; and having the entity transmit the message and its associated message authentication tag.
Claim 21
Independent Claim
142 words
A method for authenticating messages transmitted among a set of entities in a distributed computer system, comprising the steps of: establishing a secret key shared by the set of entities; having each of the entities map the secret key into an efficiently-computable representation of a hash function selected from a family of hash functions, wherein the family of hash functions is characterized by the property that the probability that distinct strings hash to the same value is small; having an entity desiring of transmitting a message apply the selected hash function to message to generate a hashed message having a length shorter than the length of the message; and having the entity apply a cryptographic transformation to the hashed message and the key to generate a message authentication tag; and having the entity transmit the message and its associated message authentication tag.
Claim 22
Dependent Claim
38 words
The method as described in claim 13 further including the steps of: having an entity among the set of entities who receives the message and its associated message authentication tag verify the validity of the message authentication tag.
Claim 23
Independent Claim
91 words
A method, using a key and implementable on a computer, for hashing a message consisting of a sequence of fixed-length bytes, into an output, comprising the steps of: mapping the key into a table; assigning a variable an initial value; for each byte of the message, modifying the variable by replacing it by a function of its current value, a value of the byte, a position of the byte within the message, and an entry retrieved from the table; and defining the output to be the final value of the variable.
Claim 24
Independent Claim
91 words
A method, using a key and implementable on a computer, for hashing a message consisting of a sequence of fixed-length bytes, into an output, comprising the steps of: mapping the key into a table; assigning a variable an initial value; for each byte of the message, modifying the variable by replacing it by a function of its current value, a value of the byte, a position of the byte within the message, and an entry retrieved from the table; and defining the output to be the final value of the variable.
Claim 25
Dependent Claim
37 words
The method as described in claim 15 wherein the function is the current value exclusive-ORed with some second function of the value of the byte, the position of the byte and the entry retrieved from the table.
Claim 26
Dependent Claim
70 words
The method as described in claim 16 wherein when the position of the byte is within some range, the second function consists of the entry retrieved from the table at a position indexed by both the value of the byte and the position of the byte, and wherein when the position of the byte is outside the range, the second function consists of the byte itself shifted by some amount.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-07-21 | 2001-01-20 | 2001-07-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-07-21 | 2005-01-20 | 2005-07-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-07-21 | 2009-01-20 | 2009-07-22 | $7700.00 | Window Closed / Lapsed |