US5870470A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for encrypting long blocks using a short-block encryption procedure
Assignee: International Business Machines Corp
•
Filing: 1996-02-20
•
Granted: 1999-02-09
•
Expires: 2016-02-20
Abstract
Abstract A system for encrypting a plaintext block using a block encryption algorithm having a block size smaller than that of the plaintext block. The plaintext block is transformed into a masked plaintext block using an invertible transformation optionally dependent on additional data and defined such that each bit of the masked plaintext block depends on every bit of the original plaintext block. A subportion of the masked plaintext block is encrypted using the encryption algorithm to generate an encrypted portion of the masked plaintext block. A ciphertext block is generated from the thus encrypted portion of the masked plaintext block and the remaining portion of the masked plaintext block. The ciphertext block is transmitted to a data recipient, who reverses the procedure to recover the original plaintext block. Since the entire masked plaintext block is necessary to reconstruct the original plaintext block and since the encrypted portion cannot be derived from the remaining portion, the remaining portion of the masked plaintext block may be transmitted to the recipient in unencrypted form. To thwart certain cryptanalytic attacks, either the plaintext block or the optional additional data is uniquely modified for each encryption of a plaintext block, using an incrementing counter, time stamp, random number or other mechanism. In an exemplary embodiment, an elliptic curve algorithm having a block size on the order of 160 bits is used to encrypt a 512-bit block containing a symmetric encryption key.
Inventors
- 👤 Donald Byron Johnson
- 👤 Stephen Michael Matyas, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 07:39
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/06; H04L9/0618; G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/725; H04L2209/00; H04L2209/04; H04L2209/046
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
89 words
Apparatus for encrypting a plaintext block using a block encryption procedure, the apparatus comprising: means for generating a masked plaintext block as a function of the plaintext block and additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from the masked plaintext block and additional data, the masked plaintext block having the same length as the original plaintext block; and means for encrypting at least a subportion of the masked plaintext block using the block encryption procedure to generate a ciphertext block.
Claim 2
Dependent Claim
89 words
Apparatus for encrypting a plaintext block using a block encryption procedure, the apparatus comprising: means for generating a masked plaintext block as a function of the plaintext block and additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from the masked plaintext block and additional data, the masked plaintext block having the same length as the original plaintext block; and means for encrypting at least a subportion of the masked plaintext block using the block encryption procedure to generate a ciphertext block.
Claim 3
Dependent Claim
29 words
The apparatus of claim 1, further comprising: means for uniquely modifying the additional data prior to generation of the masked plaintext block for each encryption of a plaintext block.
Claim 4
Dependent Claim
109 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for encrypting a plaintext block using a block encryption procedure, the method steps comprising: generating a masked plaintext block as a function of the plaintext block and optional additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from the masked plaintext block and optional additional data, the masked plaintext block having the same length as the original plaintext block; and encrypting at least a subportion of the masked plaintext block using the block encryption procedure to generate a ciphertext block.
Claim 5
Dependent Claim
109 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for encrypting a plaintext block using a block encryption procedure, the method steps comprising: generating a masked plaintext block as a function of the plaintext block and optional additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from the masked plaintext block and optional additional data, the masked plaintext block having the same length as the original plaintext block; and encrypting at least a subportion of the masked plaintext block using the block encryption procedure to generate a ciphertext block.
Claim 6
Dependent Claim
32 words
The program storage device of claim 3, the method steps further comprising: uniquely modifying the additional data prior to generation of the masked plaintext block for each encryption of a plaintext block.
Claim 7
Independent Claim
114 words
A method of encrypting a plaintext data block using a block encryption procedure having a block size smaller than that of the plaintext block, the method comprising the steps of: transforming the plaintext block into a masked plaintext block using a predetermined invertible transformation defined such that each bit of the masked plaintext block depends on every bit of the original plaintext block and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; and generating a ciphertext block by encrypting a first portion of the masked plaintext block using the block encryption procedure while leaving a second portion of the masked plaintext block unencrypted.
Claim 8
Independent Claim
114 words
A method of encrypting a plaintext data block using a block encryption procedure having a block size smaller than that of the plaintext block, the method comprising the steps of: transforming the plaintext block into a masked plaintext block using a predetermined invertible transformation defined such that each bit of the masked plaintext block depends on every bit of the original plaintext block and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; and generating a ciphertext block by encrypting a first portion of the masked plaintext block using the block encryption procedure while leaving a second portion of the masked plaintext block unencrypted.
Claim 9
Dependent Claim
17 words
The method of claim 5, comprising the further step of transmitting said ciphertext block to a recipient.
Claim 10
Dependent Claim
25 words
A method of transmitting a plaintext block as in claim 5, comprising the further step of recovering the original plaintext block from said ciphertext block.
Claim 11
Dependent Claim
55 words
The method of claim 7 wherein said recovering step comprises the steps of: regenerating said masked plaintext block from said ciphertext block, said regenerating step including the step of decrypting said first portion of said masked plaintext block; and regenerating the original plaintext block from the regenerated masked plaintext block by inverting said predetermined transformation.
Claim 12
Dependent Claim
25 words
The method of claim 5 wherein said block encryption procedure comprises an asymmetric encryption procedure having a public encryption key and a private decryption key.
Claim 13
Dependent Claim
16 words
The method of claim 5 in which said block encryption procedure comprises an elliptic curve procedure.
Claim 14
Dependent Claim
102 words
The method of claim 5 wherein said plaintext block comprises first and second parts, said transforming step comprising the steps of: masking said first part with said second part to generate an intermediate-stage first part; masking said second part with said intermediate-stage first part to generate a masked second part; and masking said intermediate-stage first part with said masked second part to generate a masked first part, one of said masked parts being used to generate a first part of said masked plaintext block, the other of said masked parts being used to generate a second part of said masked plaintext block.
Claim 15
Dependent Claim
46 words
The method of claim 11 wherein at least one of said masking steps comprises the steps of: concatenating one of said parts with additional data outside of said plaintext block to generate an extended part; and masking the other of said parts with said extended part.
Claim 16
Dependent Claim
33 words
The method of claim 11 wherein said masked first part forms said first part of said masked plaintext block and said masked second part forms said second part of said masked plaintext block.
Claim 17
Dependent Claim
144 words
The method of claim 5 wherein said plaintext block comprises first and second parts, said transforming step comprising the steps of: generating a first mask value from said second part using a first transformation; combining said first mask value with said first part to generate an intermediate-stage first part; generating a second mask value from said intermediate-stage first part using a second transformation; combining said second mask value with said second part to generate a masked second part; generating a third mask value from said masked second part using a third transformation; and combining said third mask value with said intermediate-stage first part to generate a masked first part, one of said masked parts being used to generate a first part of said masked plaintext block, the other of said masked parts being used to generate a second part of said masked plaintext block.
Claim 18
Dependent Claim
14 words
The method of claim 11 wherein said mask values are generated using one-way functions.
Claim 19
Dependent Claim
18 words
The method of claim 11 wherein said combining steps are performed by combining n-bit blocks using modulo addition.
Claim 20
Dependent Claim
16 words
The method of claim 16 wherein said combining steps are performed using bitwise modulo 2 addition.
Claim 21
Dependent Claim
60 words
The method of claim 5 wherein said masked plaintext block is generated as a function of said plaintext block and optional additional data, said method comprising the further step of uniquely modifying at least one of said plaintext block and optional additional data for each encryption of a plaintext block, said transforming step being performed on said modified plaintext block.
Claim 22
Independent Claim
143 words
A method of encrypting a plaintext block using a block encryption procedure, said method comprising the steps of: generating a masked plaintext block as a function of said plaintext block and optional additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from said masked plaintext block and optional additional data, each bit of the masked plaintext block depends on every bit of the original plaintext block, and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; encrypting at least a subportion of said masked plaintext block using said block encryption procedure to generate a ciphertext block; and uniquely modifying at least one of said plaintext block and said optional additional data prior to generation of said masked plaintext block for each encryption of a plaintext block.
Claim 23
Independent Claim
143 words
A method of encrypting a plaintext block using a block encryption procedure, said method comprising the steps of: generating a masked plaintext block as a function of said plaintext block and optional additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from said masked plaintext block and optional additional data, each bit of the masked plaintext block depends on every bit of the original plaintext block, and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; encrypting at least a subportion of said masked plaintext block using said block encryption procedure to generate a ciphertext block; and uniquely modifying at least one of said plaintext block and said optional additional data prior to generation of said masked plaintext block for each encryption of a plaintext block.
Claim 24
Dependent Claim
27 words
The method of claim 19 wherein said plaintext block is uniquely modified prior to generation of said masked plaintext block for each encryption of a plaintext block.
Claim 25
Dependent Claim
27 words
The method of claim 19 wherein said additional data is uniquely modified prior to generation of said masked plaintext block for each encryption of a plaintext block.
Claim 26
Dependent Claim
32 words
The method of claim 19 wherein said at least one of said plaintext block and said optional additional data contains a count that is incremented for each encryption of a plaintext block.
Claim 27
Dependent Claim
33 words
The method of claim 19 wherein said at least one of said plaintext block and said optional additional data contains a time stamp that is different for each encryption of a plaintext block.
Claim 28
Dependent Claim
33 words
The method of claim 19 wherein said at least one of said plaintext block and said optional additional data contains a value that is randomly generated for each encryption of a plaintext block.
Claim 29
Dependent Claim
33 words
The method of claim 19 in which the ciphertext block is generated by encrypting a first portion of the masked plaintext block while leaving a second portion of the masked plaintext block unencrypted.
Claim 30
Dependent Claim
112 words
Apparatus for encrypting a plaintext data block using a block encryption procedure having a block size smaller than that of the plaintext block, comprising: means for transforming the plaintext block into a masked plaintext block using a predetermined invertible transformation defined such that each bit of the masked plaintext block depends on every bit of the original plaintext block and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; and means for generating a ciphertext block by encrypting a first portion of the masked plaintext block using the block encryption procedure while leaving a second portion of the masked plaintext block unencrypted.
Claim 31
Dependent Claim
112 words
Apparatus for encrypting a plaintext data block using a block encryption procedure having a block size smaller than that of the plaintext block, comprising: means for transforming the plaintext block into a masked plaintext block using a predetermined invertible transformation defined such that each bit of the masked plaintext block depends on every bit of the original plaintext block and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; and means for generating a ciphertext block by encrypting a first portion of the masked plaintext block using the block encryption procedure while leaving a second portion of the masked plaintext block unencrypted.
Claim 32
Dependent Claim
102 words
Apparatus as in claim 26 wherein said plaintext block comprises first and second parts, said transforming means comprising: means for masking said first part with said second part to generate an intermediate-stage first part; means for masking said second part with said intermediate-stage first part to generate a masked second part; and means for masking said intermediate-stage first part with said masked second part to generate a masked first part, said masked first part being used to generate a first part of said masked plaintext block, said masked second part being used to generate a second part of said masked plaintext block.
Claim 33
Dependent Claim
151 words
Apparatus as in claim 26 wherein said plaintext block comprises first and second parts, said transforming means comprising: means for generating a first mask value from said second part using a first transformation; means for combining said first mask value with said first part to generate an intermediate-stage first part; means for generating a second mask value from said intermediate-stage first part using a second transformation; means for combining said second mask value with said second part to generate a masked second part; means for generating a third mask value from said masked second part using a third transformation; and means for combining said third mask value with said intermediate-stage first part to generate a masked first part, said final masked first part being used to generate a first part of said masked plaintext block, said masked second part being used to generate a second part of said masked plaintext block.
Claim 34
Dependent Claim
145 words
Apparatus for encrypting a plaintext block using a block encryption procedure, said apparatus comprising: means for generating a masked plaintext block as a function of said plaintext block and optional additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from said masked plaintext block and optional additional data, each bit of the masked plaintext block depends on every bit of the original plaintext block, and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; means for encrypting at least a subportion of said masked plaintext block using said block encryption procedure to generate a ciphertext block; and means for uniquely modifying at least one of said plaintext block and said optional additional data prior to generation of said masked plaintext block for each encryption of a plaintext block.
Claim 35
Dependent Claim
145 words
Apparatus for encrypting a plaintext block using a block encryption procedure, said apparatus comprising: means for generating a masked plaintext block as a function of said plaintext block and optional additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from said masked plaintext block and optional additional data, each bit of the masked plaintext block depends on every bit of the original plaintext block, and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; means for encrypting at least a subportion of said masked plaintext block using said block encryption procedure to generate a ciphertext block; and means for uniquely modifying at least one of said plaintext block and said optional additional data prior to generation of said masked plaintext block for each encryption of a plaintext block.
Claim 36
Dependent Claim
33 words
The apparatus of claim 29 in which the ciphertext block is generated by encrypting a first portion of the masked plaintext block while leaving a second portion of the masked plaintext block unencrypted.
Claim 37
Dependent Claim
162 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for encrypting a plaintext block using a block encryption procedure, said method steps comprising: generating a masked plaintext block as a function of said plaintext block and optional additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from said masked plaintext block and optional additional data, each bit of the masked plaintext block depends on every bit of the original plaintext block, and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; and encrypting at least a subportion of said masked plaintext block using said block encryption procedure to generate a ciphertext block; and uniquely modifying at least one of said plaintext block and said optional additional data prior to generation of said masked plaintext block for each encryption of a plaintext block.
Claim 38
Dependent Claim
162 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for encrypting a plaintext block using a block encryption procedure, said method steps comprising: generating a masked plaintext block as a function of said plaintext block and optional additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from said masked plaintext block and optional additional data, each bit of the masked plaintext block depends on every bit of the original plaintext block, and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; and encrypting at least a subportion of said masked plaintext block using said block encryption procedure to generate a ciphertext block; and uniquely modifying at least one of said plaintext block and said optional additional data prior to generation of said masked plaintext block for each encryption of a plaintext block.
Claim 39
Dependent Claim
35 words
The program storage device of claim 31 in which the ciphertext block is generated by encrypting a first portion of the masked plaintext block while leaving a second portion of the masked plaintext block unencrypted.
Claim 40
Dependent Claim
132 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for encrypting a plaintext data block using a block encryption procedure having a block size smaller than that of the plaintext block, the method steps comprising: transforming the plaintext block into a masked plaintext block using a predetermined invertible transformation defined such that each bit of the masked plaintext block depends on every bit of the original plaintext block and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; and generating a ciphertext block by encrypting a first portion of the masked plaintext block using the block encryption procedure while leaving a second portion of the masked plaintext block unencrypted.
Claim 41
Dependent Claim
132 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for encrypting a plaintext data block using a block encryption procedure having a block size smaller than that of the plaintext block, the method steps comprising: transforming the plaintext block into a masked plaintext block using a predetermined invertible transformation defined such that each bit of the masked plaintext block depends on every bit of the original plaintext block and no bit of the original plaintext block can be determined without having every bit of the masked plaintext block; and generating a ciphertext block by encrypting a first portion of the masked plaintext block using the block encryption procedure while leaving a second portion of the masked plaintext block unencrypted.
Claim 42
Independent Claim
89 words
A method of encrypting a plaintext block using a block encryption procedure, the method comprising the steps of: generating a masked plaintext block as a function of the plaintext block and additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from the masked plaintext block and additional data, the masked plaintext block having the same length as the original plaintext block; and encrypting at least a subportion of the masked plaintext block using the block encryption procedure to generate a ciphertext block.
Claim 43
Independent Claim
89 words
A method of encrypting a plaintext block using a block encryption procedure, the method comprising the steps of: generating a masked plaintext block as a function of the plaintext block and additional data using a predetermined invertible transformation defined such that the original plaintext block is recoverable from the masked plaintext block and additional data, the masked plaintext block having the same length as the original plaintext block; and encrypting at least a subportion of the masked plaintext block using the block encryption procedure to generate a ciphertext block.
Claim 44
Dependent Claim
102 words
The method of claim 34 wherein the plaintext block comprises first and second parts, the generating step comprising the steps of: masking the first part with the second part to generate an intermediate-stage first part; masking the second part with the intermediate-stage first part to generate a masked second part; and masking the intermediate-stage first part with the masked second part to generate a masked first part, one of the masked parts being used to generate a first part of the masked plaintext block, the other of the masked parts being used to generate a second part of the masked plaintext block.
Claim 45
Dependent Claim
46 words
The method of claim 35 wherein at least one of the masking steps comprises the steps of: concatenating one of the parts with additional data outside of the plaintext block to generate an extended part; and masking the other of the parts with the extended part.
Claim 46
Dependent Claim
30 words
The method of claim 34, comprising the further step of: uniquely modifying the additional data prior to generation of the masked plaintext block for each encryption of a plaintext block.
References Cited (Backward Citations)
US3956615A
Cited
US5146500A
Cited
US5272755A
Cited
US5351297A
Cited
US5159632A
Cited
US5271061A
Cited
US5351299A
Cited
US5442707A
Cited
WO1994015423A1
Cited
US5412729A
Cited
US5511123A
Cited
US5696823A
Cited
US5684876A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-08 | 2002-08-10 | 2003-02-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-08 | 2006-08-10 | 2007-02-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-08 | 2010-08-10 | 2011-02-09 | $7700.00 | Window Closed / Lapsed |