Key controlled block-cipher cryptographic system employing a multidirectional shift matrix

• US 4,195,200 A
• Filed: 06/30/1976
• Issued: 03/25/1980
• Est. Priority Date: 06/30/1976
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Feistel, Horst
• Primary Examiner(s): Birmiel, Howard A.
• Application Number:
  US05/701,060
• Time in Patent Office: 1,364 Days
• Field of Search: 178/22, 235/92 SH, 340/172.5, 364/900
• US Class Current: 380/37
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• 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 enciphering a block of binary data under the control of a unique key consisting of a set of binary symbols. A clear message represented in binary data format is transformed into a cipher message (and vise versa) by operating on blocks of clear information utilizing the operations of directional shifting of a derivative form of said clear data in a multidimensional matrix shifting and storage device. Further, cryptographic power is introduced to the system by performing a non-affine substitution operation during a shift operation on segments of information stored in said matrix. The shifting function, as well as the substitution function, is a function of said unique key. The system is further mathematically invertible, that is, the same hardware may be utilized for both encipherment and decipherment by merely reversing the sequence of operations.

Claims

1. A Block-Cipher Cryptographic System for enciphering/deciphering a block of binary data under the control of a unique binary key, said system including a multidirectional shift matrix capable of shifting in at least two directions along a predetermined coordinate of said matrix said system further including means for loading said matrix with a block of data to be cryptographically transformed, means for loading said binary key, means for causing said matrix to shift to a predetermined distance along a coordinate of said array which is a function of said key, end around connection means for said array for transferring data shifted out of one edge thereof back into the opposite edge, and means for continuing said shifting operations for a predetermined number of rounds until the cryptographic transformation process is completed.

2. A cryptographic system as set forth in claim 1 including means for performing a plurality of shifting operations which continue until each segment in the matrix has passed through said shifting operation and including means for further cryptographically transforming a segment of data during its transition from one edge of the array back into the opposite edge.

3. A cryptographic system as set forth in claim 2 including means for continuing said shifting operations along the coordinate specified by a given key field until all of the segments of data in said array have been transformed by said system, said transformation constituting a single encryption round.

4. A cryptographic system as set forth in claim 3, wherein said means for further cryptographically transforming comprises means for performing a non-affine transformation on each segment of data shifted out of one edge of said array and means for returning said transformed segment back into the opposite edge of said array.

5. A cryptographic system as set forth in claim 4 wherein said non-affine transformation means comprises means for substituting a new segment of data for the segment gated out of said array as a function of the data content of said segment and a predetermined field of said key and means for using the same key material for each shifting operation within a given round and for using different key material for different rounds.

6. A cryptographic system as set forth in claim 5 including exclusive-or means for performing an exclusive-or transformation on the output of said non-affine transformation means and another segment of data currently in said array and means for gating the output of said exclusive-or means back into said other edge of said array.

7. A cryptographic system as set forth in claim 6 wherein said array is a two dimensional rectangular array having as many storage locations as there are bits in a data block said array having the dimensions m (rows) and n (columns) and means for performing m×

n rounds of encryption on said data block stored in said array as a function of said key.

8. A cryptographic system as set forth in claim 7 wherein said array is square (m×

m) and wherein said means for shifting and transforming a segment of data performs m such shifting and transformation operations along the coordinate selected as a function of said key to complete a single round of encryption.

9. A key controlled block-cipher cryptographic system for selectively enciphering or deciphering a block of binary data presented thereto under the control of a unique user-supplied binary key, said system including a bidirectional shifting matrix capable of shifting in either direction along both axes of said matrix, said system further including,

means for loading said matrix with a block of data to be cryptographically transformed and for unloading said matrix subsequent to said transformation,

means for loading said unique binary key,

means for accessing a predetermined segment of said key and causing said matrix to shift along a coordinate of said array which is a function of said key,

end around connection means for said array for transferring data shifted out of one edge thereof back into the opposite edge,

means for performing a non-affine transformation on each segment of data shifted out of one edge of said array, and

means for returning said transformed segment of data back into the opposite edge of said array,

means for continuning said shifting and transformation operations on the contents of said array as a function of a given portion of said key until all of the rows or columns of said array being currently shifted have been transformed by the shifting operation, said complete transformation comprising a single round of encryption,

means for continuing said cryptographic transformation process for a predetermined number of rounds wherein each round is under control of different consecutive segments of said key, and

means for causing said system to access different key segments on successive rounds.

10. A cryptographic system as set forth in claim 9 including means for reversing the order of key presentation and the direction of shifting between encipherment and decipherment operations whereby said system performs a mathematically invertible transformation on the block of data presented thereto.

11. A cryptographic system as set forth in claim 10, including means for performing an exclusive-or operation on a data segment gated out of one edge of said array which has been transformed by said non-affine transformation means and the data segment currently stored in the opposite edge of said array, and means for transferring the result of said exclusive-or operation back into the opposite edge of said array.

12. A cryptographic system as set forth in claim 11, wherein said non-affine transformation means comprises a substitution matrix for substituting a new n bit segment of data for the n bit segment of data appearing as an input to said means, means for performing substitution selection as a function of the data content of the old segment and at least one bit of said key, and means for using the same bit of said key for all substitution transformations occurring within a single encryption round and for utilizing a different key bit on successive rounds.

14. A method as set forth in claim 12, including the step of performing a non-affine substitution transformation on each segment of data shifted out of one edge of said matrix prior to said exclusive-or operation, performing said non-affine substitution operation as a function of a predetermined segment of said key wherein the same key segment is used during a given cryptographic round and wherein different segments are used on consecutive rounds.

15. A method as set forth in claim 14 including the steps of presenting the segments of said key in a first order and shifting the matrix in a first direction during an encryption operation and presenting the segments of said key in the opposite order and shifting the matrix in the opposite direction during a decryption operation whereby the method is mathematically invertible.

13. A method for cryptographically transforming a block of binary data under control of a unique user-supplied key consisting of a set of binary symbols, said method including the steps of:

bidirectionally shifting rows and columns (data segments) of blocks of data loaded into a bidirectional shifting matrix, said shifting direction being selected as a function of a predetermined bit of said binary key,

transferring data shifted out of one edge of said bidirectional matrix back into the opposite edge thereof during shifting operations,

performing an exclusive-or operation utilizing as one input thereto a data segment which is a function of the segment of data shifted out of one edge of said matrix and the contents of a predetermined portion of said matrix as the other input thereto, and

transferring the result of said exclusive-or operation back into the opposite edge of said matrix,

continuing said shifting and exclusive-or operations under control of a given key segment until all of the contents of the matrix have been transformed, said transformation comprising a single encryption round,

continuing said rounds of encryption under control of different successive key segments until a predetermined number of rounds have been performed, and gating the so transformed block of data out of the system as a cryptographically transformed block.