US5345507A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Secure message authentication for binary additive stream cipher systems
Assignee: International Business Machines Corp
•
Filing: 1993-09-08
•
Granted: 1994-09-06
•
Expires: 2013-09-08
Abstract
Abstract A method of verifying the authenticity of a message transmitted from a sender to a receiver in a communication system is partitioned into three stages. In the first stage, a key is secretly exchanged between the sender and receiver. This key is a binary irreducible polynomial p(x) of degree n. In addition, the sender and receiver share an encryption key composed of a stream of secret random, or pseudo-random bits. In the second stage, the sender appends a leading non-zero string of bits, which, in the simplest case, may be a single "1" bit, and n tail bits "0" to M to generate an augmented message, this augmented message considered as a polynomial having coefficients corresponding to the message bits. If the length of the message is known and cryptographically verified, then there is no need for a leading "1". The sender then computes a polynomial residue resulting from the division of the augmented message polynomial generated by the key polynomial p(x) exchanged by the sender and receiver. The sender encrypts the computed residue. Preferably, the encryption is done by performing a bitwise Exclusive OR operation between the bits of the residue and the stream of secret bits shared by the sender and receiver. The sender then transmits the message M and the encrypted residue. The third stage is performed by the receiver by decrypting the transmitted encrypted residue at the time of reception. The receiver then appends the decrypted residue to the end of the received message M to obtain a combined bit stream M'. The receiver computes the residue of the division between the binary polynomial represented by the bit stream M' and the key polynomial p(x) exchanged by the sender and receiver. The receiver accepts a received message M as authentic only if the residue computed is zero.
Inventors
- 👤 Amir Herzberg
- 👤 Hugo M. Krawczyk
- 👤 Shay Kutten
- 👤 Yishay Mansour
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 08:47
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/32; H04L9/06; H04L9/0618; H04L9/0631; H04L9/065; H04L9/0656; H04L9/0662; H04L9/30; H04L9/3006; H04L9/3026; H04L9/3236; H04L9/3242; H04L2209/00; H04L2209/12; H04L2209/125; H04L2209/20
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
241 words
In a communication system, a method of verifying the authenticity of a message transmitted from a sender to a receiver comprising the steps of: (a) secretly exchanging between the sender and receiver an encryption key and an irreducible polynomial p(x) of degree n; (b) for each message M to be transmitted by the sender, appending a leading non-zero string and n tail bits to the message M to generate an augmented message M' that corresponds to a polynomial having coefficients corresponding to bits of the message M; (c) computing a polynomial residue r resulting from the division of the polynomial corresponding to the augmented message M' generated in step (b) by the polynomial p(x) exchanged in step (a); (d) encrypting the residue computed in step (c) using the encryption key exchanged in step (a); (e) transmitting the message M and the encrypted residue generated in step (d); (f) decrypting by the receiver the transmitted encrypted residue at the time of reception using the encryption key exchanged in step (a); (g) concatenating the decrypted residue in step (f) with a received message m and appending a non-zero leading string to generate an augmented received message m'; (h) computing a residue r of a division between a polynomial represented by the augmented message m' and the polynomial p(x) exchanged in step (a); and (i) accepting the received message m as authentic only if the residue computed in step (h) is a predetermined value.
Claim 2
Dependent Claim
241 words
In a communication system, a method of verifying the authenticity of a message transmitted from a sender to a receiver comprising the steps of: (a) secretly exchanging between the sender and receiver an encryption key and an irreducible polynomial p(x) of degree n; (b) for each message M to be transmitted by the sender, appending a leading non-zero string and n tail bits to the message M to generate an augmented message M' that corresponds to a polynomial having coefficients corresponding to bits of the message M; (c) computing a polynomial residue r resulting from the division of the polynomial corresponding to the augmented message M' generated in step (b) by the polynomial p(x) exchanged in step (a); (d) encrypting the residue computed in step (c) using the encryption key exchanged in step (a); (e) transmitting the message M and the encrypted residue generated in step (d); (f) decrypting by the receiver the transmitted encrypted residue at the time of reception using the encryption key exchanged in step (a); (g) concatenating the decrypted residue in step (f) with a received message m and appending a non-zero leading string to generate an augmented received message m'; (h) computing a residue r of a division between a polynomial represented by the augmented message m' and the polynomial p(x) exchanged in step (a); and (i) accepting the received message m as authentic only if the residue computed in step (h) is a predetermined value.
Claim 3
Dependent Claim
22 words
The method recited in claim 1 wherein the step (b) is performed by appending a leading bit "1" as the non-zero string.
Claim 4
Dependent Claim
29 words
The method recited in claim 1 wherein the step (b) is performed by appending n "0s" as the tail bits and the predetermined value in step (i) is zero.
Claim 5
Dependent Claim
34 words
The method recited in claim 1 wherein the step (b) is performed by appending an arbitrary string S as the n tail bits and the predetermined value in step (i) is the string S.
Claim 6
Dependent Claim
41 words
The method recited in claim 1 wherein bits of the message M and polynomial coefficients are considered as elements over a non-binary finite field F, and the polynomial residue operation of steps (c) and (h) are performed over the field F.
Claim 7
Dependent Claim
37 words
The method recited in claim 1 wherein the steps (d) and (f) are performed by a bitwise Exclusive OR operation between bits of the residue and a stream of secret bits shared by the sender and receiver.
Claim 8
Dependent Claim
14 words
The method recited in claim 6 wherein said stream of secret bits are random.
Claim 9
Dependent Claim
14 words
The method recited in claim 6 wherein said stream of secret bits are pseudorandom.
Claim 10
Dependent Claim
47 words
The method recited in claim 1 further comprising the steps of encrypting by the sender the message M prior to the step (e) and decrypting by the receiver the message m prior to appending the decrypted residue to the end of the received message in step (f).
Claim 11
Dependent Claim
232 words
A communication system wherein an encryption key and an irreducible polynomial p(x) of degree n are secretly exchanged between the sender and receiver, said communication system comprising: a first buffer containing a message M to be transmitted by the sender and in which a leading non-zero string and n tail bits are appended to the message M to generate an augmented message M' that corresponds to a polynomial having coefficients corresponding to bits of the message M; a first divider for computing a polynomial residue r resulting from the division of the polynomial corresponding to the augmented message M' by the polynomial p(x); a first cryptographic device for encrypting the residue r using the encryption key; a transmitter for transmitting the message M and the encrypted residue from the first cryptographic device; a receiver for receiving a transmitted message m and encrypted residue; a second cryptographic device for decrypting transmitted encrypted residue using the encryption key; a second buffer in which the decrypted residue is concatenated with the received message m and a non-zero leading string is appended to generate an augmented received message m'; a second divider for computing a residue r of a division between a polynomial represented by the augmented message m' and the polynomial p(x); and a processor accepting the received message m as authentic only if the residue computed by the second divider is a predetermined value.
Claim 12
Dependent Claim
232 words
A communication system wherein an encryption key and an irreducible polynomial p(x) of degree n are secretly exchanged between the sender and receiver, said communication system comprising: a first buffer containing a message M to be transmitted by the sender and in which a leading non-zero string and n tail bits are appended to the message M to generate an augmented message M' that corresponds to a polynomial having coefficients corresponding to bits of the message M; a first divider for computing a polynomial residue r resulting from the division of the polynomial corresponding to the augmented message M' by the polynomial p(x); a first cryptographic device for encrypting the residue r using the encryption key; a transmitter for transmitting the message M and the encrypted residue from the first cryptographic device; a receiver for receiving a transmitted message m and encrypted residue; a second cryptographic device for decrypting transmitted encrypted residue using the encryption key; a second buffer in which the decrypted residue is concatenated with the received message m and a non-zero leading string is appended to generate an augmented received message m'; a second divider for computing a residue r of a division between a polynomial represented by the augmented message m' and the polynomial p(x); and a processor accepting the received message m as authentic only if the residue computed by the second divider is a predetermined value.
Claim 13
Dependent Claim
18 words
The communication system recited in claim 10 wherein a leading bit "1" is appended as the non-zero string.
Claim 14
Dependent Claim
32 words
The communication system recited in claim 10 wherein n "0s" are appended as the tail bits and the processor accepts the received message m as authentic when the predetermined value is zero.
Claim 15
Dependent Claim
37 words
The communication system recited in claim 10 wherein an arbitrary string S is appended as the n tail bits and the processor accepts the received message m as authentic when the predetermined value is the string S.
Claim 16
Dependent Claim
167 words
The communication system recited in claim 10 wherein said first and second dividers each comprise: an accumulator register having n stages, said accumulator being initialized to contain all zeros except for a first stage which is initialized to "1", data bits being shifted through the accumulator register with L+n clock pulses, where L is a number of data bits; a plurality of Exclusive OR gates, each of the Exclusive OR gates being disposed between adjacent stages of the accumulator register; a control register having n stages and loadable with said polynomial key p(x); and a plurality of AND gates, each AND gate connected to be enabled by an output of a last stage of the accumulator register and receiving an input from a corresponding one of the stages of said control register, an output of each AND gate being supplied to a corresponding one of said Exclusive OR gates, whereby the final contents of the accumulator register, after the L+n shifts, is a value of a check-sum.
References Cited (Backward Citations)
US4797921A
Cited
US4685132A
Cited
US4771463A
Cited
US4860353A
Cited
US5054066A
Cited
US5220606A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-09-05 | 1998-03-07 | 1998-09-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-09-05 | 2002-03-07 | 2002-09-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-09-05 | 2006-03-07 | 2006-09-06 | $7700.00 | Window Closed / Lapsed |