Product block cipher system for data security

• US 3,962,539 A
• Filed: 02/24/1975
• Issued: 06/08/1976
• Est. Priority Date: 02/24/1975
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Meyer, Carl H. W., Ehrsam, William Friedrich, Powers, Robert Lowell, Tuchman, Walter Leonard, Smith, John Lynn
• Primary Examiner(s): Birmiel, Howard A.
• Application Number:
  US05/552,684
• Time in Patent Office: 470 Days
• Field of Search: 340/172.5, 178/22
• US Class Current: 380/29
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• 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 device for ciphering a block of data bits under control of a cipher key. The cipher device performs a ciphering process for the block of data by carrying out an operation in which the block of data bits is first expanded by duplicating predetermined ones of the data bits. The data bits of the expanded block are combined by modulo-2 addition with an equal number of cipher key bits, selected in accordance with an arbitrary but fixed permutation, to produce a plurality of multi-bit segments forming the arguments for a plurality of different nonlinear substitution function boxes. The substitution boxes perform a plurality of nonlinear transformation functions to produce a substitution set of bits which are equal in number to the number of data bits in the first half of the message block. The substitution set of bits is then subjected to a linear transformation in accordance with an arbitrary but fixed permutation. The combined nonlinear transformation and linear transformation results in a product block cipher of the block of data.

Claims

1. A device for performing a product block cipher operation on a block of data bits under control of a set of cipher key bits comprising:

first store means storing said block of data bits,

first linear transformation means permuting said set of cipher key bits,

means connected to said first store means duplicating predetermined ones of the data bits of said block of data bits to produce ann expanded block of data bits equal in number to the number of said permuted cipher key bits,

means connected to said expansion means and said first linear transformation means carrying out a substitution transformation function in accordance with said expanded block of data bits and said permuted cipher key bits to produce a substitution set of bits equal in number to the number of bits in said block of data, and

second linear transformation means connected to said substitution transformation means permuting said substitution set of bits whereby the combined transformation results in a product block cipher of said block of data bits.

2. A cipher device as defined in claim 1 wherein said expansion means duplicates half of the data bits of said block of data bits.

3. A cipher device as defined in claim 1 wherein said substitution transformation means comprises:

means combining the data bits of said expanded block of data bits and said permuted cipher key bits to produce a combined set of bits, and

nonlinear transformation means connected to said combining means carrying out a nonlinear substitution transformation function of said combined set of bits to produce said substitution set of bits.

4. A device for performing a product block cipher operation on a block of data bits under control of a set of cipher key bits comprising:

first store means storing said block of data bits,

first linear transformation means permuting said set of cipher key bits,

said permuted cipher key bits being grouped into a plurality of permuted cipher key bit segments,

means connected to said first store means duplicating predetermined ones of the data bits of said block of data bits to produce an expanded block of data bits equal in number to the number of said permuted cipher key bits,

said expanded block of data bits being grouped into a plurality of data bit segments equal in number to said plurality of permuted cipher key bit segments,

a plurality of substitution transformation means responsive to said plurality of data bit segments and said plurality of permuted cipher key bit segments carrying out different substitution transformation functions to produce a substitution set of bits equal in number to the number of bits in said block of data bits, and

second linear transformation means connected to said plurality of substitution transformation means permuting said substitution set of bits whereby the combined transformation results in a product block cipher of said block of data bits.

5. A cipher device as defined in claim 4 wherein said plurality of substitution transformation means comprises:

a plurality of adders combining said plurality of data bit segments and said plurality of permuted cipher key bit segments to produce a plurality of combined bit segments, and

a plurality of nonlinear transformation means connected to said plurality of adders carrying out a plurality of different nonlinear substitution transformation functions of said plurality of combined bit segments to produce said substitution set of bits.

6. A cipher device as defined in claim 5 wherein said plurality of data bit segments consist of different groups of data bits the outer ones of each group comprising the duplicated predetermined ones of the data bits of said block of data bits.

7. A cipher device as defined in claim 6 wherein said plurality of permuted cipher key segments consist of different groups of permuted cipher key bits and said plurality of adders comprises:

subgroups of adders combining said groups of data bits and said groups of permuted cipher key bits to produce subgroups of combined bits, and

said plurality of nonlinear transformation means comprising subgroups of nonlinear transformation means connected to said subgroups of adders for carrying out a plurality of different nonlinear substitution transformation functions of said subgroups of combined bits to produce subgroups of said substitution set of bits, the outer ones of the combined bits of each subgroup of combined bits being effective to select one nonlinear transformation means in each of said subgroup of nonlinear transformation means.

8. A device for performing a product block cipher operation on a block of 32 data bits under control of a set of 48 cipher key bits comprising:

first store means storing said block of 32 data bits,

first linear transformation means permuting said set of 48 cipher key bits,

means connected to said first store means duplicating 16 predetermined ones of the data bits of said block of 32 data bits to produce an expanded block containing 48 data bits,

means connected to said expansion means and said first linear transformation means carrying out a many to one substitution transformation function in accordance with said expanded block of 48 data bits and said 48 permuted cipher key bits to produce a substitution set of 32 bits, and

second linear transformation means connected to said substitution transformation means permuting said substitution set of 32 bits, whereby the combined transformation results in a product block cipher of said block of 32 data bits.

9. A process for product block ciphering a block of data represented by a combination of binary digits under control of a cipher key represented by a combination of binary digits comprising the steps of:

a. storing said block of data bits in a first store means,

b. linearly transforming said cipher key by rearranging a portion of said cipher key combination of binary digits,

c. duplicating predetermined ones of the data bits of said block of data bits to provide an expanded block of data bits consisting of said duplicated data bits and said block of data bits,

said expanded block of data bits being equal in number to the number of said transformed cipher key bits,

d. carrying out a substitution transformation function in accordance with said expanded block of data bits and said transformed cipher key bits to produce a substitution set of bits represented by a combination of binary digits equal in number to the number of bits in said block of data, and

e. linearly transforming said substitution set of bits by rearranging said substitution combination of binary digits,

whereby the combined transformation results in a product block cipher of said block of data bits.

10. A process for product block ciphering a block of data bits under control of a set of cipher key bits comprising the steps of:

a. storing said block of data bits in a first store means,

b. linearly transforming said set of cipher key bits into a plurality of transformed cipher key bit segments,

c. duplicating predetermined ones of the data bits of said block of data bits to provide an expanded block of data bits consisting of said duplicated data bits and said block of data bits grouped into a plurality of data bit segments equal in number to said plurality of transformed cipher key bit segments,

d. carrying out a plurality of different substitution transformation functions in accordance with said plurality of data bit segments and said plurality of transformed cipher key segments to produce a substitution set of bits equal in number to the number of bits in said block of data bits, and

e. linearly transforming said substitution set of bits,

whereby the combined transformation results in a product block cipher of said block of data bits.