Block cipher mode of operation for secure, length-preserving encryption

Claim 2

A computer-implemented method, using first and second keys, to encrypt a plaintext string x to a ciphertext string F, comprising the steps of: using the string x and the first key a 0 to compute a message authentication code t; using the string x, the second key a 1 , and the message authentication code t to produce an enciphered string y' that depends substantively on the message authentication code; and taking the ciphertext y to comprise the message authentication code t together with a predetermined piece of the enciphered string y'.

Claim 3

The computer-implemented method as described in claim 1 wherein said predetermined piece is shorter than y' yet the plaintext string is still uniquely recoverable given the ciphertext.

Claim 4

The computer-implemented method as described in claim 1 wherein the message authentication code is computed by cipher block chaining a block cipher.

Claim 5

The computer-implemented method as described in claim 2 wherein the block cipher is DES.

Claim 6

The computer-implemented method as described in claim 2 wherein the predetermined piece of the enciphered string includes all but a last block of the enciphered string.

Claim 7

The computer-implemented method as described in claim 2 wherein the message authentication code has a length equal to a block length.

Claim 10

The method as described in claim 7 wherein the predetermined portion of the enciphered string includes all but a last block of the enciphered string.

Claim 11

The method as described in claim 7 wherein the first initialization vector is the null vector.

Claim 12

The method as described in claim 7 wherein the plaintext string has a length that is a multiple of a length of a block.

Claim 13

The method as described in claim 7 wherein the plaintext string has a length that is not equal to a multiple of a length of a block.

Claim 14

The method as described in claim 7 wherein step (c) concatenates the CBC message authentication code and the predetermined portion of the enciphered string to form the ciphertext string.

Claim 15

The method as described in claim 7 wherein the ciphertext string has a length equal to the plaintext string.

Claim 16

The method as described in claim 7 wherein the first and second keys are derived from an underlying secret key.

Claim 19

The method as described in claim 15 wherein the block cipher is DES.

Claim 20

The method as described in claim 15 wherein the predetermined function in step (c) is an exclusive OR.

Claim 21

A computer apparatus, comprising: a storage device; program means supported in the storage device for encrypting a plaintext string x to a ciphertext string y, the program means comprising: means for using the string x and a first key a 0 to compute a message authentication code t; means for using the string x, a second key a l , and the message authentication code t to produce an enciphered string y'; and means for taking the ciphertext y to comprise the message authentication code t together with a predetermined piece of the enciphered string y', where said predetermined piece is shorter than y'.

Claim 22

A computer apparatus, comprising: a storage device; program means supported in the storage device for encrypting a plaintext string x to a ciphertext string y, the program means comprising: means for using the string x and a first key a 0 to compute a message authentication code t; means for using the string x, a second key a l , and the message authentication code t to produce an enciphered string y'; and means for taking the ciphertext y to comprise the message authentication code t together with a predetermined piece of the enciphered string y', where said predetermined piece is shorter than y'.

Claim 23

A computer, comprising: a storage device; program means supported in the storage device for decrypting a ciphertext string into a plaintext string, the ciphertext string comprising a CBC message authentication code and an enciphered string, the program means comprising: means for decrypting the enciphered string by cipher block chaining the enciphered string using a secret key and the CBC message authentication code as an initialization vector to generate a deciphered string; means for cipher block chaining the deciphered string using a second secret key and a null initialization vector to generate a string having a last block; means for calculating a predetermined function of the last block and an inverse of a block cipher evaluated using the second secret key; and means for combining the deciphered string and the predetermined function to generate the plaintext string.

Claim 24

A computer, comprising: a storage device; program means supported in the storage device for decrypting a ciphertext string into a plaintext string, the ciphertext string comprising a CBC message authentication code and an enciphered string, the program means comprising: means for decrypting the enciphered string by cipher block chaining the enciphered string using a secret key and the CBC message authentication code as an initialization vector to generate a deciphered string; means for cipher block chaining the deciphered string using a second secret key and a null initialization vector to generate a string having a last block; means for calculating a predetermined function of the last block and an inverse of a block cipher evaluated using the second secret key; and means for combining the deciphered string and the predetermined function to generate the plaintext string.

Claim 25

A program storage device readable by a processor and tangibly embodying a program of instructions executable by the processor to perform encryption and decryption methods, using first and second keys and a block cipher, wherein the encryption method comprises the steps of: (a) cipher block chaining (CBC) a plaintext string using the first key and an initialization vector (IV) to generate a CBC message authentication code; (b) cipher block chaining the plaintext string using the second key and the CBC message authentication code as the initialization vector to generate an enciphered string; and (c) combining the CBC message authentication code and a portion of the enciphered string to form a ciphertext string; and wherein the decryption method comprises the steps of: (a) cipher block chaining the enciphered string using the second key and the CBC message authentication code as the initialization vector to generate a deciphered string; (b) cipher block chaining the deciphered string using the first key and a null initialization vector to generate a string having a last block; (c) calculating a predetermined function of the last block and an inverse of the block cipher under the first key at the CBC message authentication code; and (d) combining the deciphered string and the predetermined function to generate the plaintext string.

Claim 26

A program storage device readable by a processor and tangibly embodying a program of instructions executable by the processor to perform encryption and decryption methods, using first and second keys and a block cipher, wherein the encryption method comprises the steps of: (a) cipher block chaining (CBC) a plaintext string using the first key and an initialization vector (IV) to generate a CBC message authentication code; (b) cipher block chaining the plaintext string using the second key and the CBC message authentication code as the initialization vector to generate an enciphered string; and (c) combining the CBC message authentication code and a portion of the enciphered string to form a ciphertext string; and wherein the decryption method comprises the steps of: (a) cipher block chaining the enciphered string using the second key and the CBC message authentication code as the initialization vector to generate a deciphered string; (b) cipher block chaining the deciphered string using the first key and a null initialization vector to generate a string having a last block; (c) calculating a predetermined function of the last block and an inverse of the block cipher under the first key at the CBC message authentication code; and (d) combining the deciphered string and the predetermined function to generate the plaintext string.