BLOCK CIPHER CRYPTOGRAPHIC SYSTEM

• US 3,798,359 A
• Filed: 06/30/1971
• Issued: 03/19/1974
• Est. Priority Date: 06/30/1971
• Status: Expired due to Term

• Current Assignee: Horst Feistel
• Original Assignee: Horst Feistel
• Inventors: Feistel, Horst
• Primary Examiner(s): Borchelt, Benjamin A.
• Assistant Examiner(s): Birmiel, H. A.
• Application Number:
  US05/158,360
• Time in Patent Office: 993 Days
• Field of Search: 178/22 340/172.5,348
• US Class Current: 380/37
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation

Abstract

A cryptographic system for encrypting a block of binary data under the control of a key consisting of a set of binary symbols. The cryptographic system is utilized within a data processing environment to ensure complete privacy of data and information that is stored or processed within a computing system. All authorized subscribers who are permitted access to data within the network are assigned a unique key consisting of a combination of binary symbols. The central processing unit within the computing network contains a complete listing of all distributed authorized subscriber keys. All communications transmitted from terminal input are encrypted into a block cipher by use of the cryptographic system operating under the control of the subscriber key which is inputed to the terminal device. At the receiving station or central processing unit, an identical subscriber key which is obtained from internal tables stored within the computing system is used to decipher all received ciphered communications. The cryptographic system develops a product cipher which is a combination of linear and nonlinear transformations of the clear message, the transformation being a function of the binary values that appear in the subscriber key. In addition to the transformation, the key controls various register substitutions and modulo-2 additions of partially ciphered data within the cryptographic system.

Claims

1. A cryptographic system for converting a block of data into a block cipher comprising:

input means for accepting a block of binary data;

means for presenting key consisting of a plurality of binary representations, said key to be used to control manipulations on said input data;

non-linear transformation means connected to said input means for carrying out a plurality of substitution transformations on said input data;

linear transformation means connected to said non-linear transformation means for rearranging the combination of binary representations in said block of data;

said non-linear transformation means operating under the control of said key;

whereby the combined transformation executed on said block of data, develops a product block cipher which is a function of said key.

2. The system as defined in claim 1 wherein said non-linear transformation comprises:

a plurality of substitution devices, each generating a point permutation on a subgroup of data binary representations.

3. The system as defined in claim 2 further comprising:

a plurality of gate means, each associated with a particular substitution device, said gate means being selectively engaged by a plurality of binary representations derived from said key;

a plurality of output means each associated with said gate means for presenting said point permutations generated by each substitution device to said linear transformation means.

4. The system as defined in claim 3 wherein said linear transformation means comprises input means for accepting a block of binary representation output signals from said non-linear transformation means;

a plurality of output means of equal dimension to said plurality of input means;

a plurality of interconnecting wires for rearranging the location of information signals on said input means to a different combination at said output means.

5. The system as defined in claim 4 further comprising a plurality of storage means each associated with a segment of said subscriber key binary representations;

said storage means presenting rearrangements of binary representations to said system for controlling the operations of said non-linear transformation means.

6. The system as defined in claim 5 wherein each of said plurality of storage means comprises:

a cyclic shift register containing a subgroup of the key binary signal representation;

whereby each shift register is shifted one position for each round of encryption performed by said cryptographic system thereby presenting a different combination of key binary representations for each round.

7. The system as defined in claim 1 further comprising:

interrupter means connected to said linear transformation means for performing modulo-2 additions of certain binary representations that are outputted from said linear transformation meanS and certain binary representations from said key;

feedback means connected to said interrupter means for feeding the results of said modulo-2 additions to said input means.

8. The system as defined in claim 7 further comprising a plurality of bit shift register means for rearranging various combinations of binary signal representation in accordance with the values of certain binary representations in said subscriber key.

9. The system as defined in claim 8 further comprising a plurality of storage means each associated with a segment of said subscriber key binary representations;

said storage means presenting rearrangements of binary representations to said system for controlling the operations of said non-linear transformation means.

10. The system as defined in claim 9 wherein each of said plurality of storage means comprises:

a cyclic shift register containing a subgroup of the key binary signal representation;

whereby each shift register is shifted one position for each round of encryption performed by said cryptographic system thereby presenting a different combination of key binary representations for each round.

11. The system as defined in claim 10 wherein said plurality of bit shift registers are arranged in subgroups, each subgroup being associated with an equal number of information input lines;

said bit shift registers being a two-bit shift register section having two storage elements and capable of shifting binary data between storage elements;

whereby said two-bit shift registers are controlled by a plurality of binary representation values derived from various elements within said cycle shift registers.

12. The system as defined in claim 11 further comprising feedback means for introducing the output values of said plurality of modulo-2 additions to said two-bit shift register sections after the completion of each round of encryption.

13. A process for enciphering a message block of binary digits comprising the steps of:

a. loading said message block of binary digits into a first register means;

b. loading a key block of binary digits into a second register means;

c. grouping the message binary digits into a plurality of sets each having n digits;

substituting for each said set of n digits one out of 2n! combinations of n binary digits, as determined by the binary condition of selected binary digits in said second register means;

d. linearly transforming the substituted binary digits, as a group, by rearranging the combination of binary representations;

e. repeating steps c and d for a prespecified number of rounds so that upon termination of the prespecified number of rounds the message block is fully enciphered.