Block encryption algorithm with data-dependent rotations

• US 5,835,600 A
• Filed: 04/21/1997
• Issued: 11/10/1998
• Est. Priority Date: 11/01/1995
• Status: Expired due to Term

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: RSA Data Security, Inc. (Symphony Technology Group LLC)
• Inventors: Rivest, Ronald L.
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): Laufer, Pinchus M.
• Application Number:
  US08/845,210
• Time in Patent Office: 568 Days
• Field of Search: 711/216, 364/717.01, 364/717.03, 364/717.04, 364/717.05, 364/717.06, 364/717.07, 380/46, 380/42, 380/43, 380/44, 380/37, 380/57, 380/28
• US Class Current: 380/44
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• 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 simple encryption and decryption device has been developed. The underlying algorithm is a fast block cipher that may be implemented efficiently in hardware or software. The algorithm makes heavy use of data-dependent rotations. The amount of each rotation depends on the data being encrypted and intermediate encryption results. The variables for the algorithm include word size, rounds, and the length of a secret key.

Claims

1. A method of forming a key table, the method comprising the steps of:

(a) storing in one of a first table and a second table a sequence of elements corresponding to a secret key;

(b) initializing the other of the first table and the second table to comprise a pseudorandom sequence of elements;

(c) updating at least one element of the first table, using information in the second table, to produce an updated first table;

(d) updating at least one element of the second table, using information in the updated first table, to produce an updated second table; and

(e) repeating the updating steps (c) and (d) for at least one additional element of each of the updated first table and the updated second table, such that a final version of one of the updated first table and the updated second table corresponds to the key table.

2. The method of claim 1 wherein the storing step (a) includes storing in the first table a sequence of elements corresponding to a secret key, and the initializing step (b) includes initializing the second table to comprise a pseudorandom sequence of elements.

3. The method of claim 2 further including the steps of:

initializing a memory register A and a memory register B;

initializing an accumulator i and an accumulators j, wherein S designates an element of the second table and L designates an element of the first table; and

rotating an element S by a predetermined amount and storing the result in memory register A before performing the updating steps (c) and (d).

4. The method of claim 3 wherein the updating step (c) further includes rotating an element L by an amount determined at least in part by the contents of memory register A, and storing the result in memory register B.

5. The method of claim 3 wherein the updating step (d) further includes computing the sum of an element S and an amount determined at least in part by the contents of memory register B, rotating the sum by a predetermined amount, and storing the result in memory register A.

6. The method of claim 3 wherein the repeating step (e) includes incrementing the accumulators i and j and repeating the updating steps (c) and (d) for different elements S and L of the updated tables.

7. The method of claim 1 wherein the repeating step (e) further includes repeating the updating steps (c) and (d) such that the updating steps (c) and (d) are each performed a constant times the maximum of the number of elements in the first and second tables.

8. The method of claim 1 wherein the secret key corresponds to an initial value of a pseudorandom number generator, and the method further includes the step of outputting a sequence of elements from the final version of at least one of the updated first table and the updated second table as a pseudorandom number.

9. The method of claim 8 wherein the length of the pseudorandom number is greater than the length of the initial value.

10. The method of claim 1 wherein the secret key corresponds to an input of a compression function for a hash routine, and the method further includes the step of outputting a sequence of elements from the final version of at least one of the updated first table and the updated second table as an output of the compression function.

11. An apparatus for forming a key table, comprising:

a memory for storing in one of a first table and a second table a sequence of elements corresponding to a secret key, and for storing in the other of the first table and the second table a pseudorandom sequence of elements; and

a processor associated with the memory and operative;

(i) to update at least one element of the first table, using information in the second table, to produce an updated first table;

(ii) to update at least one element of the second table, using information in the updated first table, to produce an updated second table; and

(iii) to repeat the updating operations for at least one additional element of each of the updated first table and the updated second table, such that a final version of one of the updated first table and the updated second table corresponds to the key table.

12. The apparatus of claim 11 wherein the first table includes the sequence of elements corresponding to a secret key, and the second table includes the pseudorandom sequence of elements.

13. A computer-readable medium containing one or more programs which when executed by a computer and applied to first and second tables of information, with one of the first table and the second table storing a sequence of elements corresponding to a secret key, and the other of the first table and the second table storing a pseudorandom sequence of elements, implement the following steps:

updating at least one element of the first table, using information in the second table, to produce an updated first table;

updating at least one element of the second table, using information in the updated first table, to produce an updated second table;

repeating the updating steps for at least one additional element of each of the updated first table and the updated second table, such that a final version of one of the updated first table and the updated second table corresponds to a key table.