Block encryption algorithm with data-dependent rotations

• US 5,724,428 A
• Filed: 11/01/1995
• Issued: 03/03/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/548,318
• Time in Patent Office: 853 Days
• Field of Search: 380/37, 380/42, 380/43, 380/44, 380/46, 380/57, 380/28, 380/9, 380/50, 364/717
• US Class Current: 380/37
• 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 communicating information comprising:

(a) communicating a secret key from the source to the receiver in a manner intended to maintain the secrecy of the key;

(b) selecting plaintext data at the source to be communicated over the unsecured channel to the receiver;

(c) encrypting the plaintext data using the key and a block cipher that includes at least two data-dependent rotations to generate encrypted data, wherein the amount of a second of the two data-dependent rotations depends on an encryption result derived from a first of the two data-dependent rotations, wherein the block cipher includes steps of

(c.1) segmenting the plaintext data into first and second words,

(c.2) rotating the first word by a value derived from the second word, and rotating the second word by a value derived from the first word, and

(c.3) repeating step c.2 by a number of rounds;

(d) transmitting the encrypted data over the unsecured channel to the receiver;

(e) decrypting at the receiver the encrypted data using the key and an inverse of the block cipher to generate the plaintext data.

2. A method of communicating information as in claim 1 wherein each word has a predetermined uniform bit length, and the bit length is a selectable variable.

3. A method of communicating information as in claim 2 wherein the bit length of each word is 64 bits.

4. A method of communicating information as in claim 2 wherein the bit length of each word is 32-bits.

5. A method of communicating information as in claim 1 wherein the number of rounds performed in step c.3 is a selectable variable.

6. A method of communicating information as in claim 1 wherein the number of rounds performed in step c.3 is at least four.

7. A method of encrypting information comprising the steps of:

(a) selecting a secret key having a predetermined number of bytes, and

(b) encrypting the information using the key and a block cipher that includes data-dependent rotations to generate encrypted data, and wherein the amount of rotation in at least one of the rotations depends on an intermediate result, wherein the block cipher includes steps;

(b.1) segmenting the information, and storing a first part of the information in a first memory register and a second part of the information in a second memory register,

(b.2) rotating a first value stored in the first memory register by a value derived from the contents of the second register, and rotating a second value stored in the second register by a value derived from the contents of the first register,

(b.3) repeating step b.2 by a number of rounds.

8. A method of encrypting information as in claim 7 wherein the first and second parts of information each have a predetermined uniform bit length, and the bit length is a selectable variable.

9. A method of encrypting information as in claim 8 wherein the bit length of each first and second parts of information is 64 bits.

10. A method of encrypting information as in claim 8 wherein the bit length of each of the first and second parts of information is 32-bits.

11. A method of encrypting information as in claim 7 wherein the number of rounds performed in step c.3 is a selectable variable.

12. A method of encrypting information as in claim 7 wherein the number of rounds performed in step c.3 is at least four.

13. A method of encrypting information comprising:

a. inputting a first block of plaintext information into a first memory register that temporarily stores a first value and a second block of plaintext information into a second memory register that temporarily stores a second value;

b. deriving a key table from a secret key where said key table has a sequence of elements;

c. executing a first invertible operation on the first block of plaintext information stored in the first memory register with a first element of the key table and storing a result of the first invertible operation in the first memory register as the first value, and executing a second invertible operation on the second block of plaintext information stored in the second memory register with a second element of the key table and storing a result of the second invertible operation in the second memory register as the second value;

d. executing a third invertible operation on the first value with the second value from step (c); and

storing a result of the third invertible operation in the first memory register as the first value;

e. rotating the bits of the first value from step (d) in the first memory register by a number corresponding to at least a portion of the second value from step (c), and storing a result of the rotation in the first memory register as the first value;

f. executing a fourth invertible operation on the second value from step (c) with the first value from step (e), and storing a result of the fourth invertible operation in the second memory register as the second value;

g. rotating the bits of the second value from step (f) in the second memory register by a number corresponding to at least a portion of the first value from step (e) and storing a result of the rotation in the second memory register as the second value;

h. repeating steps d to g for a predetermined number of rounds, and

i. outputting the values in the first and second memory registers as encrypted information.

14. A method as in claim 13 further comprising step:

j. executing a fifth invertible operation on the first value from step (e) stored in the first memory register with a next in the sequence element of the key table and storing a result of the fifth invertible operation in the first memory register as the first value after step e, and executing a sixth invertible operation on the second value from step (g) stored in the second memory register with a next in the sequence element of the key table and storing a result of the sixth invertible operation in the second memory register as the second value after step g.

15. A method as in claim 14 wherein the fifth and sixth invertible operations are two'"'"'s complement addition operations.

16. A method of encrypting information as in claim 13 wherein the first invertible operation in step c is a two'"'"'s complement addition operation, the third invertible operation in step d is a bitwise exclusive OR operation, and the fourth invertible operation in step f is another bitwise exclusive OR operation.