Data processing systems with format-preserving encryption and decryption engines

• US 7,864,952 B2
• Filed: 12/06/2006
• Issued: 01/04/2011
• Est. Priority Date: 06/28/2006
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Voltage Security Incorporated (HP Inc.)
• Inventors: Martin, Luther W., Pauker, Matthew J., Spies, Terence
• Primary Examiner(s): Patel; Ashok B
• Assistant Examiner(s): POTRATZ, DANIEL B
• Application Number:
  US11/635,756
• Publication Number:
  US 20100074441A1
• Time in Patent Office: 1,490 Days
• Field of Search: 380/28, 380/37, 380/29, 380/42, 713/193
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI

Abstract

A data processing system is provided that includes format-preserving encryption and decryption engines. A string that contains characters has a specified format. The format defines a legal set of character values for each character position in the string. During encryption operations with the encryption engine, a string is processed to remove extraneous characters and to encode the string using an index. The processed string is encrypted using a format-preserving block cipher. The output of the block cipher is post-processed to produce an encrypted string having the same specified format as the original unencrypted string. During decryption operations, the decryption engine uses the format-preserving block cipher in reverse to transform the encrypted string into a decrypted string having the same format.

Claims

1. A method for encrypting a data string using an encryption engine in a data processing system, comprising:

obtaining a data string containing characters, wherein the data string has a format specifying a legal set of character values for each of its characters;

processing the data string to remove any extraneous characters from the data string that are present, wherein the processed data string contains a left-half string of characters that has a left-half format specifying a legal set of character values for each of its characters and contains a right-half string of characters that has a right-half format specifying a legal set of character values of each of its characters;

encoding the processed data string using at least one index of sequential index values each of which corresponds to a respective one of the character values in the legal set of character values for the characters of the data string, wherein the encoded data string includes an encoded version of the left-half string of characters and an encoded version of the right-half string of characters;

encrypting the encoded data string using a format-preserving block cipher, wherein the format-preserving block cipher receives the encoded data string as input and produces a corresponding encrypted encoded data string as output, wherein encrypting the encoded data string using the format-preserving block cipher comprises using a subkey generation algorithm and a format-preserving combining operation to process the encoded data string, wherein the subkey generation algorithm receives a key as an input, wherein the subkey generation algorithm is used in generating at least first and second subkeys, wherein the format-preserving combining operation preserves the left-half format of the left-half string of characters when combining the encoded version of the left-half string of characters with the first subkey, and wherein the format-preserving combining operation preserves the right-half format of the right-half string of characters when combining the encoded version of the right-half string of characters with the second subkey; and

using the index, decoding the encrypted encoded data string to produce a decoded encrypted data string with characters in the legal set of characters.

2. The method defined in claim 1 wherein processing the data string to remove extraneous characters comprises removing a checksum from the data string.

3. The method defined in claim 1 further comprising processing the decoded encrypted data string to restore the removed extraneous characters.

4. The method defined in claim 1 wherein processing the data string to remove extraneous characters comprises removing a checksum from the data string, the method further comprising processing the decoded encrypted data string to add a newly-computed checksum.

5. The method defined in claim 1 wherein processing the data string to remove extraneous characters comprises removing a checksum from the data string, the method further comprising processing the decoded encrypted data string to add a dummy checksum value, wherein the dummy checksum value does not form a valid checksum for the decoded encrypted data string.

6. The method defined in claim 1, wherein the format-preserving combining operation comprises addition.

7. The method defined in claim 1, wherein the format-preserving combining operation comprises addition mod x, where x is an integer.

8. The method defined in claim 1, wherein the format-preserving combining operation comprises addition mod x, where x is an integer, the method further comprising:

processing the decoded encrypted data string to restore the removed extraneous characters, so that the processed decoded encrypted data string has the same format as the data string.

9. The method defined in claim 1 further comprising processing the decoded encrypted data string to restore the removed extraneous characters, so that the processed decoded encrypted data string has the same format as the data string, wherein encrypting the encoded data string using the format-preserving block cipher comprises processing the encoded data string using a cryptographic hash function as the subkey generation algorithm.

10. The method defined in claim 1 further comprising processing the decoded encrypted data string to restore the removed extraneous characters, so that the processed decoded encrypted data string has the same format as the data string, wherein encrypting the encoded data string using the format-preserving block cipher comprises processing the encoded data string using a cryptographic message authentication code function as the subkey generation algorithm.

11. The method defined in claim 1 further comprising processing the decoded encrypted data string to restore the removed extraneous characters, so that the processed decoded encrypted data string has the same format as the data string, wherein processing the data string to remove extraneous characters comprises removing a checksum from the data string and wherein processing the decoded encrypted data string to restore the removed extraneous characters comprises computing a new valid checksum for the decoded encrypted data string.

12. A method for processing a data string using a computer-implemented system, comprising:

obtaining a data string containing characters;

with an encryption engine, encoding the data string using at least one index of sequential index values to produce an encoded string; and

with the encryption engine, encrypting the encoded string using a format-preserving block cipher to produce an encrypted string, wherein the format-preserving block cipher receives the encoded string as input and produces the encrypted string as output, wherein the encoded string includes an encoded version of a left half of the data string containing characters in a left-half format and an encoded version of a right half of the data string containing characters in a right-half format, and wherein encrypting the encoded string comprises using a format-preserving combining operation that preserves the left-half format of the left half of the data string when combining the encoded version of the left half of the data string with a first subkey and that preserves the right-half format of the right half of the data string when combining the encoded version of the right half of the data string with a second subkey, wherein encrypting the encoded string using the format-preserving block cipher comprises encrypting the encoded string using a block cipher having a structure based on a Luby-Rackoff construction and wherein using the format-preserving combining operation comprises using addition mod x, where x is an integer, the method further comprising decrypting the encrypted string using the format-preserving block cipher, wherein decrypting the encrypted string using the format-preserving block cipher comprises decrypting the encrypted string using the block cipher having the structure based on the Luby-Rackoff construction and wherein decrypting the encrypted string using the block cipher comprises decrypting the encrypted string using the subkey generation algorithm and using addition mod x, where x is an integer.

13. The method defined in claim 12 further comprising:

after decrypting the encrypted string, using the index to convert decrypted string indices into legal characters corresponding to the sequential index values.

14. The method defined in claim 12 wherein the data string has a format specifying a legal set of character values for each of its characters, the method further comprising:

processing the data string to remove any extraneous characters from the data string that are present before encrypting the data string; and

using the index, converting indices in the encrypted string into respective characters in a legal set of characters associated with the index.

15. A method for encrypting a data string using an encryption engine in a data processing system, comprising:

obtaining a data string containing characters, wherein the data string has a format specifying a legal set of character values for each of its characters, at least two of the legal sets of character values being different from each other;

processing the data string to remove any extraneous characters from the data string that are present;

encoding the processed data string using at least two different index mappings, wherein each index mapping defines a mapping between the legal set of character values for a given character position in the data string and a corresponding index of sequential index values;

encrypting the encoded data string using a format-preserving block cipher, wherein the format-preserving block cipher receives the encoded data string as input and produces a corresponding encrypted encoded data string as output; and

using the at least two different index mappings, decoding the encrypted encoded data string to produce a decoded encrypted data string with characters in the legal sets of characters, wherein the encoded data string includes an encoded version of a left half of the data string containing characters in a left-half format and an encoded version of a right half of the data string containing characters in a right-half format, and wherein encrypting the encoded data string comprises using a format-preserving combining operation that preserves the left-half format of the left half of the data string when combining the encoded version of the left half of the data string with a first subkey and that preserves the right-half format of the right half of the data string when combining the encoded version of the right half of the data string with a second subkey.