Software-efficient pseudorandom function and the use thereof for encryption

• US 5,454,039 A
• Filed: 12/06/1993
• Issued: 09/26/1995
• Est. Priority Date: 12/06/1993
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rogaway, Phillip W., Coppersmith, Don
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/163,054
• Time in Patent Office: 659 Days
• Field of Search: 380/9, 380/21, 380/28, 380/29, 380/30, 380/33, 380/43, 380/46, 380/49, 380/50, 364/717, 331/78
• US Class Current: 380/28
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/46 by designing passwords or checking the strength of passwords
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 21/80 in storage media based on magnetic or optical technology, e.g. disks with sectors preventing unauthorised reproduction or copying of disc-type recordable media G11B20/00
• CPC Class Codes: G06F 21/85 interconnection devices, e.g. bus-connected or in-line devices
• CPC Class Codes: G06F 2211/007 Encryption, En-/decode, En-/decipher, En-/decypher, Scramble, (De-)compress
• CPC Class Codes: H04L 2209/046 of operations, operands or results of the operations
• CPC Class Codes: H04L 9/0656 Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher

Abstract

A software-efficient pseudorandom function maps an index and an encryption key to a pseudorandom bit string useful for constructing a stream cipher. The method begins by preprocessing the encryption key into a table of pseudorandom values. The index and a set of values from the table is then used to generate a set of initial values for the registers. At least some of the register values are modified in part by taking a current value of a register and replacing the current value with a function of the current value and a value retrieved from the table, the latter value being determined by the values in one or more other registers. After modifying the register values in this fashion, the values are masked using other values from the table and the results then concatenated into the pseudorandom bit string. The modification step is repeated and a new masked function of the register values is then concatenated into the pseudorandom bit string. The modification and concatenation steps are repeated to continue growing the pseudorandom bit string until the string reaches some desired length.

Claims

1. A method for transforming a table of pseudorandom numbers into a pseudorandom bit string useful for data encryption, the table being precomputed from a key, comprising the steps of:

(a) using an index and a set of values from the table of pseudorandom numbers to generate initial values for a set of registers;

(b) mixing at least some of the register values by taking a current value of a register and replacing the current value with a function of the current value and a value retrieved from the table;

(c) concatenating into the pseudorandom bit string a function of the register values as modified in step (b); and

(d) repeating steps (b)-(c) a predetermined number of times until the pseudorandom bit string reaches a desired length.

2. A method for encrypting a data string relative to an index and a key, comprising the steps of:

(a) preprocessing the key into first, second and third tables of pseudorandom values;

(b) using the index and a first set of values from the first table to map values from the third table into first and second sets of register values;

(c) mixing the first set of register values by taking a current value of a register and replacing the current value with a function of the current value and a value retrieved from the third table;

(d) using a first set of values from the second table to mask the register values as mixed in step (c);

(e) concatenating into a pseudorandom bit string a function of the masked register values;

(f) repeating steps (c)-(e) using a second set of values from the second table; and

(g) repeating steps (b)-(f) using a second set of values from the first table until the pseudorandom bit string reaches a desired length.

3. The method as described in claim 2 wherein before step (f) the second set of register values are used to modify the register values generated in step (c).

4. The method as described in claim 2 wherein the key is preprocessed into the first, second and third tables using a pseudorandom generator derived from a secure hash algorithm.

5. A method for encrypting a data string relative to an index and an encryption key, comprising the steps of:

(a) using the index and a set of values from a table of pseudorandom numbers to generate initial values for a set of registers, the table having been precomputed from the encryption key;

(b) mixing at least some of the register values by taking a current value of a register and replacing the current value with a function of the current value and a value retrieved from the table;

(c) concatenating into a pseudorandom bit string a function of the register values as modified in step (b);

(d) repeating steps (b)-(c) a predetermined number of times until the pseudorandom bit string reaches a desired length; and

(e) encrypting the data string by combining the pseudorandom bit string and the data string.

6. The method as described in claim 5 wherein the value retrieved from the table in step (b) is located in the table using a value derived from at least one other register.

7. The method as described in claim 6 wherein after the value derived from the other register is used to access into the table, the other register has its current value replaced with a circular shift of its current value by some predetermined amount.

8. The method as described in claim 7 wherein after the circular shift of the other register value, the current value of the register of step (b) is replaced with an exclusive-OR of the current value and the circular-shifted value in the other register.

9. The method as described in claim 7 wherein after the circular shift of the other register value, the current value of the register is replaced with a modulo sum of the current value and the circular-shifted value in the other register.

10. The method as described in claim 5 wherein the step of taking a current value of a register and replacing the current value with a function of the current value and a value retrieved from the table is repeated prior to step (c).

11. The method as described in claim 10 wherein during a first iteration of step (b) the function is an exclusive-OR and during a second iteration of step (b) the function is a modulo sum.

12. The method as described in claim 5 wherein the function of the register values in step (c) is derived by masking the mixed register values with values retrieved from the table.

13. The method as described in claim 5 wherein the data string is a message to be communicated over an insecure channel and the index corresponds to a sequence number for the message.

14. The method as described in claim 5 wherein the data string is a data block to be stored in a mass storage device and the index specifies a physical location of the data block within the mass storage device.

15. The method as described in claim 5 wherein the data string is a data file and the index is a unique file identifier associated to the particular file.

16. A cryptographic system for encrypting a data string, comprising:

means for preprocessing an encryption key into a table of pseudorandom values;

means for generating initial values of a set of words using values derived from the table;

means for modifying at least some of the initial values of the set of words to create modified words;

means responsive to the modifying means for repeatedly concatenating into a pseudorandom bit string a function of the modified words until the pseudorandom bit string reaches a desired length; and

means for encrypting the data string by combining the data string and the pseudorandom bit string.

17. A computer, comprising:

means for interfacing a physical device to an operating system of the computer; and

means for encrypting a data string associated with the physical device, comprising;

means for preprocessing an encryption key into a table of pseudorandom values;

means for generating initial values of a set of words using values derived from the table;

means for modifying at least some of the initial values of the set of words to create modified words;

means responsive to the modifying means for repeatedly concatenating into a pseudorandom bit string a function of the modified words until the pseudorandom bit string reaches a desired length; and

means for combining the data string and the pseudorandom bit string.