Block substitution based encryption by a modulo 2 addition method and apparatus

• US 5,038,376 A
• Filed: 10/04/1989
• Issued: 08/06/1991
• Est. Priority Date: 10/04/1989
• Status: Expired due to Term

• Current Assignee: Litton Systems Incorporated (Northrop Grumman Corporation)
• Original Assignee: Teledyne Industries Incorporated (Teledyne Technologies Incorporated)
• Inventors: Mittenthal, Lothrop
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): SWANN, TOD R
• Application Number:
  US07/416,953
• Time in Patent Office: 671 Days
• Field of Search: 380/28, 380/36, 380/37, 380/42, 380/49
• US Class Current: 380/37
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation

Abstract

Methods and apparatus for modulo 2 addition based encryption by block substitution techniques which allows use of the substitution scheme with relatively simple hardware. The block substitution, a one to one mapping of n bit binary numbers onto themselves, is based on the fact that certain permutations of the n bit binary numbers define a block substitution by modulo 2 addition of one permuted set of numbers to another, and that a subset of these define equations having an additive relationship when viewed as vectors. This allows the simple changing of the transformation on a frequent basis. Various properties of the transformations and methods of using the same are disclosed.

Claims

1. A method of encryption by substituting for any one of the 2ⁿ unique clear text blocks of n bit binary numbers an associated unique encrypted block of n bit binary numbers comprising the steps of;

(a) finding a first set of 2ⁿ equations, each equation representing the modulo 2 addition of one of the 2ⁿ clear text blocks with a unique one of 2ⁿ n bit numbers to provide the associated unique encrypted n bit block, equations in the first set of 2ⁿ equations being characterized by the sum modulo 2 of any odd number of the equations being another one of the equations in the first set, where the blocks in each position of a given equation are added modulo 2 to the corresponding blocks in the other equations, whereby any clear text block can be converted into an associated encrypted block by the one to one mapping defined by the 2ⁿ equations;

(b) for each clear text block to be encrypted, adding modulo 2 to that block, the unique one of the 2ⁿ bit numbers associated therewith in accordance with the associated equation of the first set of 2ⁿ equations to obtain the encrypted block.

2. The method of claim 1 further comprising the decryption of the encrypted blocks comprising the further steps of;

(c) finding a second set of 2ⁿ equations, each equation representing the modulo 2 addition of one of the 2ⁿ encrypted blocks with a unique of 2ⁿ bit numbers to provide the associated unique clear text n bit block, the second set of 2ⁿ equations containing columns corresponding to those in the first matrix of 2ⁿ equations with the symbol ⊕ and

= thereof interchanged, whereby any encrypted block can be converted into an associated clear text block by the one to one mapping defined by the second set of 2ⁿ equations;

(d) for each encrypted block to be decrypted, adding modulo 2 to that block, the unique one of the 2ⁿ n bit numbers associated therewith in accordance with the associated equation of the second set of 2ⁿ equations to obtain the decrypted or clear text block.

3. The method of claim 1 wherein one of the equations in the first set is the identity equation mapping the zero value onto itself, and wherein the equations can be ordered in the form:

##EQU6##

4. The method of claim 3 further comprising the decryption of the encrypted blocks comprising the further steps of;

(c) finding a second set of 2ⁿ equations, each equation representing the modulo 2 addition of one of the 2ⁿ encrypted blocks with a unique one of 2ⁿ n bit numbers to provide the associated unique clear text n bit block, the second set of 2ⁿ equations containing columns corresponding to those in the first set equations with the symbols ⊕ and

= thereof interchanged, whereby any encrypted block can be converted into an associated clear text block by the one to one mapping defined by the second set of 2ⁿ equations;

(d) for each encrypted block to be decrypted, adding modulo 2 to that block, the unique one of the 2ⁿ n bit numbers associated therewith in accordance with the associated equation of the second set of 2ⁿ equations to obtain the decrypted or clear text block.

5. The method of claim 3 wherein one of the equations in the first set is the identity equation mapping the zero value onto itself, and wherein the equations in the first set can be generated from a set of original equations ordered in the form:

##EQU7## the equations in the first set being generatable from the foregoing set of original equations by shifting with wrap around and by any predetermined integer s, the n bit numbers in either of the first two columns of the set, and by shifting with wrap around and by a second predetermined integer Ps dependent on the first predetermined integer s, the n bit numbers in the third column of the set, the foregoing shifts involving all equations of the set except the identity equation.

6. The method of claim 5 further comprising the decryption of the encrypted blocks comprising the further steps of;

(c) finding a second set of 2ⁿ equations, each equation representing the modulo 2 addition of one of the 2ⁿ encrypted blocks with a unique one of 2ⁿ bit numbers to provide the associated unique clear text n bit block, the second set of 2ⁿ equations containing columns corresponding to those in the first set of 2ⁿ equations with the symbols ⊕ and

= thereof interchanged, whereby any encrypted block can be converted into an associated clear text block by the one to one mapping defined by the second set of 2ⁿ equations;

(d) for each encrypted block to be decrypted, adding modulo 2 to that block, the unique one of the 2ⁿ n bit numbers associated therewith in accordance with the associated equation of the second set of 2ⁿ equations to obtain the decrypted or clear text block.

7. The method of claim 5 wherein the amount of the shifts is varied from time to time as successive n bit blocks are encrypted.

8. The method of claim 5 wherein one of the equations in the first set is the identity equation mapping the zero value onto itself, and wherein the equations in the first set can be generated from a set of equations ordered in the form:

##EQU8## the equations in the first set being generatable from the forgoing set of equations by;

(e) shifting with wrap around and by a first predetermined integer s, the n bit numbers in the first column of the set, and shifting with wrap around and by a second predetermined integer P_s dependent on the first predetermined integer, the n bit numbers in the third column of the set, the foregoing shifts involving all equations in the set except the identity equation, and;

(f) adding modulo two, any n bit number Y to the n bit numbers in the first and the second columns of the set, including the identity equation.

9. The method of claim 8 wherein the amount of the shifts is varied from time to time as successive blocks of n bit blocks are encrypted.

10. The method of claim 8 wherein the n bit number added in step (f) is varied from time to time as successive blocks of n bit blocks are encrypted.

11. The method of claim 8 wherein both the amount of the shifts and the n bit number added in step (f) are varied from time to time as successive blocks of n bit blocks are encrypted.

12. The method of claim 8 further comprising the decryption of the encrypted blocks comprising the further steps of;

(c) finding a second set of 2ⁿ equations, each equation representing the modulo 2 addition of one of the 2ⁿ encrypted blocks with a unique one of 2ⁿ n bit numbers to provide the associated unique clear text n bit block, the second set of 2ⁿ equations containing columns corresponding to those in the first set of 2ⁿ equations with the symbols ⊕ and

= thereof interchanged, whereby any encrypted block can be converted into an associated clear text block by the one to one mapping defined by the second matrix of 2ⁿ equations;

(d) for each encrypted block to be decrypted, adding modulo 2 to that block, the unique one of the 2ⁿ n bit numbers associated therewith in accordance with the associated equation of the second set of 2ⁿ equations to obtain the decrypted or clear text block.