Data processing systems with format-preserving encryption and decryption engines

• US 20100074441A1
• Filed: 12/06/2006
• Published: 03/25/2010
• 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
• Granted Patent: US 7,864,952 B2
• Time in Patent Office: Days
• US Class Current: 380/45
• 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;

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;

encrypting the encoded data string using a format-preserving block cipher; 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 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.

7. The method defined in claim 1 wherein encrypting the encoded data string using the format-preserving block cipher comprises:

using a subkey generation algorithm in generating subkeys from the encoded data string, wherein the subkey generation algorithm uses as inputs a key and portions of the encoded data string; and

using a format-preserving combining operation to combine subkeys generated by the subkey generation algorithm with portions of the encoded data string.

8. The method defined in claim 1 wherein encrypting the encoded data string using the format-preserving block cipher comprises:

using a subkey generation algorithm in generating subkeys from the encoded string, wherein the subkey generation algorithm uses as inputs a key and portions of the encoded data string; and

using a format-preserving combining operation to combine subkeys generated by the subkey generation algorithm with portions of the encoded data string, wherein the format-preserving combining operation is a function selected from the group consisting of addition and multiplication.

9. The method defined in claim 1 wherein encrypting the encoded data string using the format-preserving block cipher comprises:

separating the encoded data string into first and second halves; and

repeatedly using a subkey generation algorithm and a format-preserving combining operation to perform operations on the first and second halves, wherein the subkey generation algorithm uses a key as an input and wherein the format-preserving combining operation comprises addition mod x, where x is an integer.

10. The method defined in claim 1 wherein encrypting the encoded data string using the format-preserving block cipher comprises:

separating the encoded data string into first and second halves; and

repeatedly using a subkey generation algorithm and a format-preserving combining operation to perform operations on the first and second halves, wherein the subkey generation algorithm uses a key as an input and 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.

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 encrypting the encoded data string using the format-preserving block cipher comprises processing the encoded data string using a cryptographic hash function as a subkey generation algorithm.

12. 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 a subkey generation algorithm.

13. The method defined in claim 1 wherein encrypting the encoded data string using the format-preserving block cipher comprises encrypting the encoded data string using a block cipher having a structure based on a Luby-Rackoff construction.

14. The method defined in claim 1 wherein encrypting the encoded data 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 encrypting the encoded data string using the block cipher comprises encrypting the encoded data string using a subkey generation algorithm based on a cryptographic hash function and a format-preserving combining algorithm.

15. 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.

16. 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; and

with the encryption engine, encrypting the encoded string using a format-preserving block cipher to produce an encrypted string.

17. The method defined in claim 16 further comprising with a decryption engine, decrypting the encrypted string using the format-preserving block cipher.

18. The method defined in claim 16 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 encrypting the encoded string using the block cipher comprises encrypting the encoded string using a subkey generation algorithm and using addition mod x or multiplication mod x, where x is an integer.

19. The method defined in claim 16 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 encrypting the encoded string using the block cipher comprises encrypting the encoded string using a subkey generation algorithm and using addition mod x or multiplication 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 or multiplication mod x, where x is an integer.

20. The method defined in claim 16 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 encrypting the encoded string using the block cipher comprises encrypting the encoded string using a subkey generation algorithm and addition mod x or multiplication mod x, where x is an integer, the method further comprising:

decrypting the encrypted string using the format-preserving block cipher, wherein decrypting 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 or multiplication mod x, where x is an integer; and

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

21. The method defined in claim 16 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.

22. 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; 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.