Method and apparatus for statistical diffusion in iterated block substitution

• US 5,838,795 A
• Filed: 07/07/1997
• Issued: 11/17/1998
• Est. Priority Date: 01/11/1996
• Status: Expired due to Term

• Current Assignee: Teledyne Technologies Incorporated
• Original Assignee: Teledyne Industries Incorporated (Teledyne Technologies Incorporated)
• Inventors: Mittenthal, Lothrop
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): Laufer, Pinchus M.
• Application Number:
  US08/888,454
• Time in Patent Office: 498 Days
• Field of Search: 380/28, 380/29, 380/37, 380/42, 380/59
• US Class Current: 380/28
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms

Abstract

A method and apparatus for inter-round mixing in iterated block substitution systems is disclosed. The method involves optimizing inter-round mixing so that each sub-block of data affects each other in the same way. This is accomplished by applying a quick trickle permutation or a quasi quick trickle permutation to blocks of data allocated to n individual substitution boxes.

Claims

1. A method of encryption to be performed by a computer, comprising:

(a) receiving successive blocks of data, each block of data being sub-divided into n sub-blocks of data, where n is an integer, the sub-block being assigned to n individual substitution boxes;

(b) selecting one of a quick trickle or a quasi quick trickle permutation as a base permutation;

(c) determining if a set of preselected exponents is to be applied to the base permutation;

(d) generating the set of preselected exponents from one of a quick trickle or a quasi quick trickle permutation;

(e)(1) applying the set of preselected exponents to the base permutation if step (c) determines that a preselected set of exponents is to be applied, to obtain a sequence of permutations, otherwise (e)(2) applying an integer k as an exponent to the base permutation for the kth round of encryption to obtain a resulting permutation;

(f) for each round in a predetermined number of rounds, if (e)(1) is applied, applying a corresponding one of the permutations to the partially encrypted sub-blocks, assigning each partially encrypted sub-block as an input to the substitution box whose number is indicated by the the corresponding one of the sequence of permutations, and if (e)(2) is applied, applying the resulting permutation to the partially encrypted sub-blocks, assigning each partially encrypted sub-block as an input to the substitution box whose number is indicated by the resulting kth permutation; and

(g) repeating (e) and (f) for the predetermined number of rounds; and

(h) displaying the encrypted data provided in step (g).

2. The method of claim 1, wherein in (a), n is even.

3. The method of claim 2, wherein in (b), the quick trickle permutation is one in which a totality of spacings from a location of an element i to a location of an element i+1 are all different and constitute a sequencing.

4. The method of claim 3, wherein (b) comprises selecting the quick trickle permutation and generating the quick trickle permutation by:

providing a sequencing {0,a₁,a₂, . . . ,a_n-1 } which is a sequence of all of the elements of a group of n elements arranged in such an order that the sequence of partial sums b₀ =0, b₁ =a₁, b₂ =a₁ +a₂, b₃ =a₁ +a₂ +a₃, . . . , b_n-1, are all different, which when applied as exponents to a permutation g provides a sequence of permutations g⁰, g^a.sbsp.1, g^a.sbsp.2, . . . , g^a.sbsp.n-1, and where g⁰, g⁰ ∘

g^a.sbsp.1 =g^b.sbsp.1, g⁰ ∘

g^a.sbsp.1 ∘

g^a.sbsp.2 =g^b.sbsp.2, . . . , such that the sequence of exponents {0,b₁ b₂, . . . ,b_n-1 } is a directed terrace; and

wherein in step (d) the step of applying the set of preselected exponents comprises the step of applying successive integers of the directed terrace as the set of preselected exponents of the permutation.

5. The method of claim 4, wherein the number of rounds is multiple of n.

6. The method of claim 1, wherein (b) comprises selecting the quasi quick trickle permutation and generating the quasi quick trickle permutation by:

providing a quasi-sequencing which is a sequence of elements {a_i } of a group of n elements {0,a₁,a₂, . . . ,a_n-1 }, where the following occurs;

the group element a_i such that a_i =a_i^-1 occurs once and for each other group element;

either (i) a_i occurs twice and a_i^-1 does not occur, or, (ii) a_i and a_i^-1 each occurs once, or (iii) a_i^-1 occurs twice and a_i does not occur;

where the group elements are arranged in such an order that the sequence of partial sums b₀ =0, b₁ =a₁ +a₂, b₃ =a₁ +a₂ +a₃, . . . , b_n-1, are all different, which when applied as exponents to a permutation g provides a sequence of permutations g⁰, g^a.sbsp.1, g^a.sbsp.2, . . . , g^a.sbsp.n-1, and where g⁰, g⁰ ∘

g^a.sbsp.1 =g^b.sbsp.1, g⁰ ∘

g^a.sbsp.1 ∘

g^a.sbsp.2 =g^b.sbsp.2, . . . , such that the sequence of exponents {0,b₁,b₂, . . . ,b_n-1 } is a terrace; and

wherein in (d) the step of applying the set of preselected exponents comprises the step of applying successive integers of the directed terrace as the set of preselected exponents of the permutation.

7. The method of claim 1, wherein in (b), the quasi quick trickle permutation is one in which a totality of spacings from a location of an element i to a location of an element i+1 are either different or occur no more than twice and constitute a quasi sequencing.

8. The method of claim 1, wherein in (a), n is odd.

9. The method of claim 1, wherein in (g), the number of rounds is multiple of n.