Nonlinear dynamic substitution devices and methods for block substitutions

CA 02115063 1999-06-14

WO 93/09559

PCT/US92/06497

NONLINEAR DYNAMIC SUBSTITUTION DEVICES AND METHODS FOR BLOCK SUBSTITUTIONS

BACKGROUND QF...THE INVENTION

I - Field of the Invention.

The present Invention relates to the field of encryption devices and methods# and more particularly, to block substitution encryption methods and devices.

2. Prior Art.

In many cases# it is desired to communicate information in digital form from one location to another in a manner which is clear and unambiguous to the receiver# but which is incomprehensible to an interloper therebetween. Accordingly, in many instances, it is common to encrypt the Information to be communicated by some predetermined encryption process# to transmit the encrypted form of the information and to then decrypt the information at the receiving location. Depending upon the degree of security desired, a relatively simple and easily broken encryption may be used, as any level of encryption will make the transmission meaningless to the casual interloper. In other situations, the degree of security desired may dictate the use of an encryption

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0001.tif" />

technique which is more difficult to decipher by cryptanalysis, or of course hopefully in the highest level of security, make the same substantially impossible to decipher. Applications for such encryption techniques include commercial applications such as sensitive communications between manufacturing plants, bank branches, etc., and military applications including but not limited to IFF (identification friend or foe). While in some cases the primary objective of the encryption is to prevent an interloper from deciphering the information being communicated, in other cases a primary object, such as in IFF, is to prevent the interloper from himself originating false information with the same encryption scheme so as to mislead the intended receiver. Both objectives are frequently present in many applications.

Block substitution is a method used to encrypt a clear text message which is in the form of a sequence of binary numbers. In accordance with the method, the sequence is broken into blocks of some predetermined block length n, with the block substitution device substituting a unique new block of binary numbers for each of those in the clear text. Substitute blocks constitute the encrypted message or cipher text, each substitute block representing a nonambiguous oneto-one transformation of a clear text block. In the prior art, such substitution generally takes place by means of look-up tables, switching arrangements, or feedback shift registers. However, without changing codes or substitution schemes frequently, the encryption may be broken by

CA 02115063 1999-06-14

WO 93/03559

PCT/US92/06497 cryptanalysis, though, changing look-up tables is cumbersome, only a limited number of possible switching arrangements is practical, and repeated cycling of a shift register is time consuming. An additional problem arises in finding substitutions which do not have any pattern or biaa in them. At the present time, candidate substitutions are examined by computer simulation for possible systematic patterns and in some cases, additional circuitry is used to compensate therefor.

Various types of encryption equipment and methods are well-known in the prior art. See for instance U.S. Patents No. 3,796,830, 3, 798,359, 4,078, 152, 4,195,200, 4,255,811, 4,316,055 and 4,520,232. In general, these systems as they relate to block substitution are key dependent ciphering and deciphering systems and are not based upon block substitution by modulo 2 addition of one additive permuted set of numbers to another, as in the present invention.

In U.S. Patent 5,030,376, methods and apparatus for modulo 2 addition based encryption by block substitution techniques were disclosed which allow 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, whereby the remainder of the set may be generated

WO 93/03559

PCT/US92/06497 kA

<img file="CA2115063C_D0002.tif" />

from a limited subset of the equations. This allows the simple changing of the transformation on a frequent basis. Various properties of the transformations and methods of using the same were disclosed. The fact that the remainder of the set equations may be generated from a limited subset of the equations, however, may make cryptanalysis less difficult than desired in some applications. Accordingly the present invention comprises a method and apparatus for nonlinearizing the equations, also in an orderly and readily variable manner, so that the remainder of the set equations may no longer be generated from a limited subset of the equations .

.».·

v.'·

CA 02115063 1999-06-14

BRIEF DESCRIPTION OF THE INVENTION

Method and apparatus for nonlinearizing modulo 2 addition based encryption by block substitution techniques which allows use of the substitution scheme with relatively simple hardware and yet makes cryptanalysis more difficult. The basic 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. Then the equations are nonlinearized, also in an orderly and readily variable manner, so that the remainder of the set equations may no longer be generated from a limited subset of the equations. Various properties of the transformations and methods of using the same are disclosed.

* Accordingly, in one aspect, the present invention provides 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 π bit binary numbers comprising the steps of:

(a) finding a first matrix 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 an associated unique intermediate n bit block, all of the equations in the first matrix of 2ⁿ equations being

CA 02115063 1999-06-14

5a characterized by the vector sum modulo 2 of any number of the equations also being one of the equations in the first matrix, the equations including the null equation 0 = 0 φ 0 and the remaining 2ⁿ - 1 equations being orderable as follows:

Equation /

<td> 1</td><td></td><td></td><td> β</td><td> xi</td><td> Xl-p</td>

<td> 2</td><td></td><td> Xl</td><td> Φ</td><td> X2</td><td> X2-p</td>

<td> j</td><td></td><td> Xj-1</td><td> Φ</td><td> X_}</td><td> Xj-p</td>

<td> m</td><td></td><td> Xm-1</td><td> e</td><td> x_m</td><td>^xm-p</td>

<td> where m = 2ⁿ</td><td> - 1</td><td> and p</td><td> is</td><td> an integer</td><td> and wherein the</td>

<td colspan="2"> vector is constituted</td><td colspan="2"> by three</td><td> components</td><td> corresponding to</td>

<td> the three numbers</td><td> x in</td><td> i each</td><td colspan="2"> equation;</td><td></td>

(b) modifying a plurality of the nonzero 2ⁿ - 1

I equations in the first matrix of 2ⁿ equations to provide a second matrix of 2ⁿ equations, the plurality of equations being modified so that the second matrix of equations includes the 2ⁿ clear text text blocks Xj_i in the same order as the 2ⁿ clear text blocks Xj__x of the first matrix of equations, with the unique set of 2ⁿ n bit numbers Xj of the second matrix of equations in different order from that of the unique set of 2ⁿ n bit numbers Xj of the first matrix of equations, the different order being such that the modulo 2 addition of one of the 2ⁿ clear text blocks x-j-i of the

CA 02115063 1999-06-14

5b second matrix of equations with the corresponding unique n bit block in the reordered unique set 2ⁿ π bit numbers xj of the second matrix of equations provides an associated unique n bit block (Xk-_P) , wherein each of the modified equations in the plurality is not the sum modulo 2 of any number of the unmodified equations left over and not included in the modified plurality of equations, the second matrix of 2ⁿequations consisting of the modified plurality and the remaining unmodified equations from the first matrix of 2ⁿequations; and, (c) for each clear text block to be encrypted, 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 matrix of 2ⁿ equations to obtain the encrypted block.

In a further aspect, the present invention provides 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

CA 02115063 1999-06-14

5c 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.

f.

WO 93/03559

PCT/IJS92/06497

<img file="CA2115063C_D0003.tif" />

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 illustrates a many-one transformation of one set of three bit binary numbers to another set of binary , 1 numbers by a modulo 2 addition.

Figure 2 illustrates a one-to-one transformation of one set of three bit binary numbers to another set of binary numbers by a modulo 2 addition.

Figure 3 presents the transformation equations of Figure reordered, excluding the first equation, making the three digit number in the first column the same as the three digit number in the second column of the preceding row. Excluding the first equation, each column now is in the same order but with different starting positions.

Figure 4 corresponds to Figure 3, though with the first and third columns shifted vertically with respect to the second column. These shifts are 6 and 2 positions downward respectively. Except for the first equation, each column remains in the same order but with different starting positions.

Figure 5 corresponds to Figure 4, with the Φ and symbols interchanged for encryption purposes.

Figure 6 is a block diagram of an apparatus for encrypting data.

♦

Figure 7 is a block diagram of apparatus for decrypting data encrypted by the apparatus of Figure 6. .

»

Figure 8 is an example of encryption using Figure 6.

i

Figure 9 is an example of decryption using Figure 7.

WO 93/03559

PCT/US92/06497 transformation equations with the fixed word 001

Except for the first {· i

ι i

!

. 7

Figure 10 presents a set of corresponding to those of Figure added to columns 1 and 2 thereof, equation, columns 1 and 2 are in the same order but with different starting positions.

Figure 11 is a block diagram for an apparatus for encrypting data in accordance with a set of transformation equations such as those of Figure 10.

Figure 12 is a block diagram for an apparatus for decrypting data encrypted with the apparatus of Figure 11.

Figure 13 is an example of encryption using Figure 11.

Figure 14 is an example of encryption using Figure 12.

Figure 15 illustrates a rearrangement equations in

Figure 2 into the general form x_n-l ® Xn “ ²n*

Figure 16 is a block diagram of a system for encryption and decryption in accordance with the present invention.

Figure 17 illustrates a set of equations useful for encryption and decryption derived by adding the offset 0101 to the first and second columns of the set of equations presented on page A12 of Appendix 2.

I'·'

CA 02115063 2000-07-10

DETAILED DESCRIPTION OF THE INVENTION

Since the present invention comprises methods and apparatus for nonlinearizing the modulo 2 addition based encryption by block substitution described in detail in U.S. Patent 5,038,376, that disclosure is repeated herein to provide a basis for the improvement of the present invention. Thus as described in U.S. Patent 5,038,376, in the description to follow, the methods and apparatus of the U.S. Patent 5,038,376 will first be described with respect to blocks of n bit binary numbers where the value of n is 3.

Then the methods and apparatus will be expanded to n bit blocks generally, and certain characteristics of blocks up to n = 8 will be presented. By presenting the following example for n = 3, it is believed that the concepts of the original invention may be better understood than would be the case if a larger block having many more combinations were used.

Block substitution is the term usually applied to a oneto-one mapping of the n-bit binary numbers onto themselves. This mapping can be written as a pairing of the 2ⁿ n-bit numbers :

Xl Zi

X2 Z2

Xk Zk

WO 93/03559

PCT/US92/06497 i

211

Γ' Γ» .*» Λ Λ h f ' ·ν G 'J \J il where each column is the set of the same 2ⁿ distinct n-bit

M numbers but written in different orders. Thus, this mapping can be thought of as a permutation of the n-bit numbers written as:

Î {

s i

ι

Xl X2 -.Xk *1 Z2 --Zk or (Χχ Xi Xj) for some set of indices. This usual notation for permutations simply means that Xi -► Xi, Xi

-► Xj, etc.

Going back to the column.notations, one could define a set of simple equations from the original set and its image:

Yl © Xl = Zi Y₂ ® *2 Z2

Y_k ® Xk = Zk £?·;/ where Φ means modulo 2 addition (i.e., addition of corresponding digits without any carry). In general, the set {Yl, Y2, ...} will not all be distinct, but in certain

WO 93/03559

PCT7US92/06497

<img file="CA2115063C_D0004.tif" />

circumstances they will be. In accordance with the original invention, when they are distinct, block substitutions can be generated by modulo 2 addition rather than by conventional* means. The main tasks are to determine the circumstances, if any, in which this scheme works, how the substitutions can be quickly changed, and the lack of bias.

It is not obvious that block substitutions can ever be generated by modulo 2 addition. For example, consider the attempt to substitute one arrangement of 3-bit binary numbers for another by modulo 2 addition shown in Figure 1. In column 3 on the right, Oil and 100 each appear twice, while 001 and 110 never appear. The numbers in column 1 on the left, acting on the numbers in column 2 in the center, constitute a transformation of the set of 3-bit binary words of column 1 into themselves . This is a many-one transformation and is useless for block substitutions because of the ambiguity that results when trying to recover the original block for the transformed blocks Oil and 100.

Trying another arrangement as shown in Figure 2 gives a different result. Any pair of columns now constitutes a oneto-one transformation. In particular, the transformation is one-to-one from the 3-bit binary numbers of column 3 (the clear text) onto themselves, the encrypted text of column 1. Each column consists of all the 3-bit numbers exactly once.

Obviously, one could use the transformations of Figure 2 to transform any three digit binary block into an encrypted binary block, and of course use the same equations to deencrypt the encrypted message by finding the encrypted word

WO 93/03559

PCT/US92/06497 co in column 1 and then selecting the corresponding clear text word in the same row, column 3 of Figure 2. This is most convenient if Φ and - are interchanged as shown in Figure’* 5. An equivalent transformation to transform the encrypted word back to the clear text word results if the words of column one are added to those of column two to obtain those in column three.

Referring again to Figure 2, an interesting property of the transformation shown therein, and for that matter, for all transformations of the type of interest herein, may be seen. In particular, of the eight blocks of three binary numbers, the lower four blocks 000, 001, 010 and Oil map into two blocks of the lower four, namely 000 and 001, and two blocks of the upper four, namely 110 and 111. Similarly of course, the four larger blocks of the eight map two into blocks in the lower four, and two into blocks of the upper four. Similarly, the even blocks 000, 010, 100 and 110 map into two even blocks, 000 and 010, and into two odd blocks, 001 and Oil. The odd four blocks map half into odd blocks and half into even blocks. Obviously for decryption, the same is true. Thus, knowledge of some characteristic of the encrypted block such as its being large, small, even, odd, etc., does not convey any similar knowledge of a characteristic of the unencrypted block. As a result of this, the encryption is said to be unbiased. For that matter it should be noted that, even considering the middle digit of each block, the four blocks of Figure 2 having a zero as the middle digit map two blocks into blocks also having a zero as

WO 93/03559

PCT/US92/06497 •Ç .k .V :.&lt;V a middle digit, and two blocks having one as the middle digit. Similarly of course, the four blocks having a one as the middle digit map two into blocks having a one as a middle digit, and two into blocks having a zero as the middle digit. This property applies to all block sizes and extends to dividing equally all set of blocks which may be characterized algebraically as maximal subgroups. This unbiased character of the encryption is a highly beneficial characteristic of the encryption scheme disclosed herein, particularly in conjunction with the frequent changing of the encryption from time to time.

In particular, in any practical encryption device of course, one would like to be able to frequently change the encryption scheme so that patterns will not persist for a sufficient length of time to allow cryptanalysis of the pattern. For this purpose, certain properties of the equations of Figure 2 may be recognized by rearranging the rows of Figure 2 as shown in Figure 3. Rearrangement of the rows in any manner of course does not effect the transformation in any way, as each of the equations maintains its own integrity separate and apart from its position in the table. In essence, the second row of Figure 3 is the 4th row in Figure 2 and the third row of Figure 3 is the fifth row in Figure 2, with each successive row being arranged so that the left column in each successive row contains the same 3 bit number as the second column of the preceding row. When so arranged, neglecting the first or identity row, it will be noted that each of the three columns contains the same

WO 93/03559

PCT/US92/06497

21X5063 sequence of the 3 bit binary numbers, with wrap-around. In particular, the first column has the same sequence as the second column, but displaced downward therefrom one position (or upward six positions), and the third column has the same sequence as the second column, though displaced downward three positions (or upward four positions) from the sequence of column two.

Neglecting the first row or identity row of Figure 3 again, if the 3 bit binary numbers in column 1 are shifted downward a total of six positions with wrap-around with respect to the second column, it will be noted that a one to one transformation still results, as shown in Figure 4.

Except for the identity row, the transformation is entirely different from that of Figure 3. By way of example, 111 column 3 maps into Oil column 1 in Figure 3, and maps into 100 column 1 in Figure 4. In addition however, it is important to note that the sequence of the 3 digit numbers in columns 1 and 3 of Figure 4 (separating out the identify row) is still the same as that in column 2 of Figures 3 and 4, though each is shifted with wrap-around in comparison to column 2. Thus, the transformation of Figure 3 has been changed to the new transformation of Figure 4 by merely shifting the numbers in the first column of Figure 3 with respect to those in the second column, and with the numbers in the third column also being shifted with respect to those in the second column, but by a different amount to preserve the integrity of the modulo 2 addition equations. Again, for

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0005.tif" />

decryption, symbols © and == of Figure 4 can be interchanged as in Figure 5.

More generally for any block size, the sets of equations can be written as:

ENCRIETIDH

Θ

Xl-s

X2-s •

Xk-s «

Xm-s

2

<td> ss</td><td> θ</td><td> Φ</td><td> θ</td>

<td></td><td> xi</td><td> Φ</td><td> Xl-Ps</td>

<td></td><td> Χ2 •</td><td> Φ</td><td> X2-Ps *</td>

<td> -</td><td> xi •</td><td> Φ</td><td> • Xk-Ps •</td>

<td> as</td><td> Xm</td><td> Φ</td><td> • Xm-Ps</td>

Θ = 00. . .00

PBCRYETIQN

2

<td> Θ</td><td> Φ</td><td> Θ</td><td> =5</td><td> 6</td>

<td> Xl-s</td><td> Φ</td><td> xi</td><td> «</td><td> Xl-Ps</td>

<td> X2-s</td><td> Φ</td><td> X2</td><td> «</td><td> X2-Ps</td>

Xk-s

Xm-s

Xk

Xk-Ps

Xm-Ps

2ⁿ-l. Θ = 00...00, the n bit word

For block size n, m consisting of all zeroes

WO 93/03559

PCT/US92/06497

If column 1 is shifted by S positions with respect to column 2, then column 3 is shifted by a different amount Pg to preserve the integrity of the modulo 2 addition equations. For a given shift S, Ps is determined by the shift programmer .

Now referring to figure 6, a block diagram of a system for carrying out encryption in accordance with the encryption and decryption techniques discussed so far may be seen.

The clear test word is sent to its address in Memory I. This corresponds to selecting a word Xk-Ps from column 3 other than θ . The concept is to add it to its counterpart in column 2. If Xk-Ps is other than Θ and is to be added to Xkz this is equivalent to adding the word with order data K - P_sin column 3 to the word with order K - P_s + P_s = K, also in column 3. Thus the order data of the clear test word K - P_sis sent to the adder to be added to P_s. The new order number is sent to its address in Memory II. The content of that address is added modulo 2 to the clear test word to obtain the encrypted word

Xk-s iⁿ column 1. If the clear text word is θ, its cipher test image is the same.

Adding of the order data is accomplished by two adders, carry (C) and least significant bit (LSB). The carry adder adds the numbers conventionally with carry, e.g. Q01 + 011 = 100. However, if the addition requires more than n digits, that is, a 1 is carried to the n+1 position, that extra 1 is instead added to the first position, e.g., 100 + 110 = 1010 «&gt; Oil. This is accomplished by the LBS adder. This is

WO 93/03559

PCT/US92/06497 simply addition modulo m where m = 2ⁿ - 1. In this example, n = 3, m = Ί and the addition expressed in decimal terms is 4 + 6 = 10 s 3 mod 7 where 100 =&gt; 4, 110 =&gt; 6 and Oil =&gt; 3.

The block diagram for decryption is shown at Figure 7. The cipher text word is sent to its address in Memory I.

This corresponds to selecting a word Xk-s from column 1 other than Θ. The concept is to add it to its counterpart, Xr in column 2. This is equivalent to adding Xk-s in column 1 to the word with order data K - s + s “ K, also in column 1.

Thus the order data of the cipher text word, K-s is sent to the adder to be added to s. The new order number is sent to its address in Memory II. The contents of that address is added modulo 2 to the cipher text word to obtain the deencrypted word Xk-Ps in column 3. If the cipher text word is Θ' it is de-encrypted as Θ.

The addition of order data, K - S + S and K - P_s + P_s is understood to be modulo m or with wraparound. That is, if the order data is greater than m, the last position, m is subtracted from the order data. If the cipher text word is Θ, it is de-encrypted as the same word.

The shift program determines the order in which the shifts, S, in column 1 are used, with the corresponding P₃shift S in column 3. Any desired order can be used. The shift S corresponds to a power of the basic permutation described on Page 8, which determines the substitution by addition.

Thus, by way of example, in Figure 8, if the clear data value is 010, then that address in Memory I provides order

WO 93/03559

<td> PCT/US92/06497</td><td> &amp; R</td>

<td> 9i1 ~_t n p 9</td><td> J</td>

<td> 1 .i. 'J y 9</td><td> I</td>

data 001, which is binary notation that 010 is in position 1 j in the sequence in Memory I (column 3 of the set of j

- ;

equations). The first shift position in the program is S = ;

6, for which Pg = 2. To the position of 010, K - Pg = 1 is jadded Pg == 2. In binary notation, 001 + 010 - Oil.

Corresponding to the address Oil in Memory II is the number 100. (This is equivalent to saying that 100 is in position 3 in column 3). 110 “ 100 Φ 010 is the cipher text word.

This represents the first of the additive equations in Figure

5.

For decryption, the cipher text word is 110. In Figure 9, that address in Memory I provides order data 100, or position 4 in the sequence in Memory I. The first shift position in the program is S = 6. To the position of 110, K - 6 = 4, is added 6, or 110 in binary notation. 4 + 6 = 10.

Subtracting by in = 7, 10 - 7 = 3, or position 3 with wrap around. In binary notation, 100 + 110 = 011 modulo 7.

Corresponding to the address 011 in Memory II is the number 100. 110 Φ 100 = 010. This represents the first of the additive equations in Figure 4.

J

If one adds Modulo 2 a fixed number to the first and

- second columns of Figure 4. A still further one-to-one transformation results .

tf/.

WO 93/03559

PCT/US92/0G497

2ί

ENCRYPTION (I © Y) = (Xi-S Φ Y) = (X₂-s © Y)= (Xk-s © Y) = (X_ro_s Φ Y) = (I Φ Y) Φ (Xl Φ Y) Φ (X2 Φ Y) Φ (Xk Φ Y) Φ (X_m Φ Y) ©

I

Xl-p s

X2-PS

Xk-P s

Xm-Ps

DECRYPTION

2 2

<td> (I ©</td><td> Y)</td><td colspan="2"> Φ</td><td> (I</td><td> ©</td><td> Y) =</td><td> I</td>

<td> (Xl-s</td><td> ©</td><td> Y)</td><td> Φ</td><td> (Xl</td><td> Φ</td><td> Y) =</td><td> Xi-Ps</td>

<td> &lt;X2-s</td><td> Φ</td><td> Y)</td><td> Φ</td><td> (X2</td><td> Φ</td><td> Y) =</td><td> X2-Ps</td>

<td> (Xk-s</td><td> Φ</td><td> Y)</td><td> Φ</td><td> (Xk</td><td> ©</td><td> Y) =</td><td> Xk-Ps</td>

<td> (Xm-s</td><td> ©</td><td> Y)</td><td> ©</td><td> (Xm</td><td> ©</td><td> Y) =</td><td> Xm-Ps</td>

Now referring to Figures 11 and 12, for any block size a block diagram for carrying out encryption and decryption using a fixed word other than θ, the zero word, may be seen. The procedure is essentially the same as before with the additional step of adding the fixed word Modulo 2 as the last step in the encryption process and the first step in the decryption process.

WO 93/03559

PCT/US92/06497

An example is shown in Figure 13 and 14. In this case,

000 no longer remains fixed, but is transformed into 001.

r*

Now 110 is transformed to itself and thus becomes fixed in this case.

The fixed word adder can add in succession any or all of the n bit words in whatever order is selected by the user.

Now referring to Figure 8, as an example, a block diagram of a system for carrying out encryption in accordance with the encryption and decryption techniques discussed so far may be seen. As shown in the figure, any value of the clear data 20, except 000, is provided as an address to memory 22. Stored at the various memory addresses is the order data for the clear data value, that is, the position, expressed as a binary number, of that clear data value in the ordered sequence of the right column of Figure 4 (and Figures 5 and 10). This position is provided as an output of the memory 22 to an adder shown as the combination of adders 24 and 26. The adders are coupled to add the output of the memory to a value of shift Ps as controlled by shift programmer 28. This addition is not a modulo 2 addition but rather is the normal binary add, with the one exception that the carry from the most significant bit is coupled to the carry in of the least significant bit. Thus, the adder will provide the result 001 as the sum 1 larger than 111, not 1000 or simply 000. Thus, it may be seen that the output of the adders is a new three bit binary number shifted in the order data sequence by an amount Ps· This new position is then used as the address for memory 30, which provides as its

<img file="CA2115063C_D0006.tif" />

PCT/US92/06497

WO 93/03559 output the three bit binary number corresponding to the value in column 2 of Figure 4, or the corresponding clear data value in Figure 3. Thus, by way of example, if the clear data value is 010, that value as an address to memory I provides the location of that value of 001 in the sequence.

If the shift program selects S = 6, then Pg = 2 and column 3 is shifted downward two positions from column 2 or by an amount 010. The three bit binary number which would then be adjacent to the clear data value of 010 is 100 as in Figure

5. This added modulo 2 to the clear data 010 provides an encrypted value of 110, corresponding to the value shown in Figure 5. However, if the clear text data value is 000, that value as an address to Memory I provides the location of the value of 000 in the sequence. It is not shifted but provided unchanged as the order data in memory 30. Thus 000 added to itself, remains fixed.

The downward.shift P_s of the sequence of column 3 of Figure 5 in comparison to the basic order data of column 2 of Figure 5 of course corresponds to a complimentary upward shift. Thus, for an n bit block, a downward shift of Ps is equivalent to an upward shift of m-P_s. Note also that for a three bit block, all values of possible shift provide the desired one-to-one mapping except for a shift of the first column with respect to the second column of zero, and of 7 and multiples thereof, as such shifts would provide a second column in the matrix having each row the same as the corresponding row of the first column, and any number added to itself modulo 2 will be zero. Thus, for a shift of seven v

WO 93/03559

PCT/US92/06497 ί 396;?

or multiples thereof, all clear data values map to 000, useless for encryption purposes. In general however, it will be shown later that for n bit blocks larger than three bits, all shifts other than zero and integer multiples of m give the desired result and thus are usable in accordance with the original invention.

The block diagram for decryption in accordance with Figure 7 is shown in Figure 9. From a hardware standpoint, this diagram is exactly the same as that of Figure 8 for encryption, the decryption differing only in the shift S applicable for a given shift Pg for encryption. As in the example on page 14, for a shift Ps of 2 for encryption, a shift 6 provides the proper decryption, etc., as shown in the tables of Figures 8 and 9. Obviously, the encryption hardware and the decryption hardware must be using the associated shifts for the clear data to be properly recovered on decryption, though the applicable shift may be varied frequently at both ends to make cryptanalysis very difficult, if not virtually impossible.

If one adds modulo 2 a fixed number to any pair of columns of Figure 5, a still further one-to-one transformation results. By way of example, in Figure 10 the fixed number 001 has been added modulo 2 to the first and second columns of Figure 5. Now 010 as a clear text word maps into an encrypted word 111, whereas in the example of Figure 8, 010 mapped into 110.

An example of a block diagram for the encryption using a fixed word adder may be seen in Figure 13. This figure is

PCT/US92/06497

WO 93/03559 . . „ ,·, ,

W ·ν&gt;

I·!* &gt;··· «·* identical to Figure 8 with the exception that the fixed word adder 32 has been included to add the fixed word (001 in the example) to the output of memory 30 corresponding to the value in the same row of the second column as 010 of the first column. Thus, the fixed word adder merely adds the fixed word (001 in the example) to the column 2 value, after which the clear text word is added modulo 2 thereto to obtain the encrypted data. Again for the example, using clear data of 010 as the address to memory 22, the output of the memory will be 001. Using the same shift as in the example of Figure 8,. 010, P_s -= 2 is added to the 001, to provide an address to memory 30 of Oil. This results in an output from memory 30 of 100, to which fixed word adder adds modulo 2, the fixed word 001, yielding 101. This added modulo 2 to the clear text word 010 gives the encrypted word 111 as shown in Figure 10.

A block diagram for decryption, corresponding to the block diagram for encryption of Figure 13, is shown in Figure 14. As may be seen, Figure 14 is identical to Figure 13 (though the shifts for decryption are again different from the shifts for encryption), with the exception of the fixed word adder also adding modulo 2 the fixed word to the encrypted data before the same is applied to memory 22. This modulo 2 addition is in essence the second modulo 2 addition of the fixed word, as a first modulo 2 addition of the fixed word was done in Figure 11 to get the encrypted word. Thus, since a second modulo 2 addition of the same word in effect cancels the first modulo 2 addition so that after the

--,-3

WO 93/03559 PCT/US92/06497

1 1 Ç G fi encrypted data in Figure 12 has the fixed word added modulo 2 thereto, the result of that modulo 2 addition may be used with the equations of Figure 10 for decryption purposes.

Thus, by way of example, using the encrypted word 111 of the example of Figure 13, 111 Φ 001 =110 as the address to memory 22 of Figure 14. This gives a memory output of 100, to which the value of S = 6 or 110 is added. 100 + 110 =

1010 -&gt; Oil with wrap-around. This in turn gives an address of Oil to memory 30 or an output thereof of 100, to which is added modulo 2 110, the address to memory 22, to recover the clear text data 010. Further of course, while the fixed word adder of Figures 13 and 14 used a fixed word 001, any other 3-bit fixed word may be used, or for that matter, the fixed word may be varied from time to time with or separate and apart from variations in the shift, a fixed word of 000 essentially reducing the operation of the system to that of Figures 8 and 9.

Obviously, the methods described in relation to Figures 6, 7, 11 and 12 may readily be carried out with a microprocessor based system under program control. Alternatively, the memory could readily be preprogrammed in read only memory used essentially as look-up tables, and the adders and modulo 2 adders could readily be conventional adder circuitry so that at least the major elements of an encryption and decryption system cou.d be realized in either high speed discrete components or through a custom integrated chip. The shift program also could take various forms depending upon how often a shift is desired, the extent to

CA 021 15063 2000-07- 10 which the shift order is itself varied, etc., microprocessor based, integrated circuits or other realizations being readily applicable, including shift register implementations as desired.

In Appendix 1 which follows, the transformations hereinbefore described are further analyzed and various properties and characteristics thereof are set forth. In Appendix 2, certain aspects of the method of block substitution of U.S. Patent 5,038,376 are reviewed, and the concepts of nonlinearity and nonlinear mappings of clear text to encrypted text (and vice versa) are presented.

Nonlinearity in this sense means that the mappings of clear text to encrypted text (and from encrypted text to clear text) are nonlinear under the operation of bit-wise addition modulo 2. In that regard, it was pointed out that Figure 1 illustrates a many-one transformation of one set of three bit binary numbers to another set of binary numbers by a modulo 2 addition. This specific example maps the eight possible values of the three bit numbers in the first column by modulo 2 addition to six three bit numbers in column 3 representing six of the eight possible combinations, with two (100 and Oil), each being repeated twice. Because two three bit numbers (010 and 101) map to the same three bit number (100), and two other three bit numbers (100 and 110) map to the same three bit number (010), the reverse mapping will have ambiguities, making the mapping illustrated in Figure 1 unsuitable for encryption and decryption purposes.

WO 93/03559

PCT/US92/06497

On the other hand, Figures 2 through 5 provide sets of equations for encryption of any of the eight possible three

- M bit clear text words (column 1) to a corresponding nonambiguous encrypted text word (column 3). These equations remain valid by the interchanging of columns 1 and 3, and thus with this interchange, form the equations for the corresponding decryption in the same way that the equations before the interchange form the equations for encryption. However, the set of equations shown in each of Figures 2 through 5 are linear in the sense that the addition of any two equations within a given set of equations (eight equations for three bit numbers such as in Figures 2 through 5) is also one of the equations of the set. For instance, in Figure 2, while the addition of the first or null equation to any other equation yields that other equation and is thus trivial, the addition of the second and third equations provides the fourth equation, the addition of the third and fourth equation provides the second equation, the addition of the fourth and fifth equation provides the eighth equation, etc. Even when one adds modulo 2 one equation to itself, one obtains one of the eight equations, namely the null equation, as may occur when one adds more than two equations modulo 2 such as, by way of example, equations two, three and four, as the addition of equations two and three yields equation four, and equation four added to itself yields the null equation.

In that regard, adding two equations modulo 2 may be considered equivalent to adding any greater number of equations, as either or both of the equations added may be

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0007.tif" />

considered to be the sum of two or more other equations. Further, there is no combination of equations the sum of which is not another equation in the given set. What is most significant from a cryptanalysis standpoint is that given the right three of the seven equations other than the null equation, the remaining four equations may be determined by the appropriate sums of the combinations of the three known equations. For instance, while the combinations of sums of equations two, three and four of Figure 2 cannot be used to generate the rest of the equations, equations two, three or four, and five, six, seven or eight can be so used. Taking for example, equations two, four and eight, the sum of equations two and four provides equation three, the sum of equations two and eight provides equation seven, the sum of equations two, four and eight provides equation six, and the sum of equations four and eight provides equation five. Also the foregoing rule, of course, applies to encryption of words of other bit lengths, the generating equations for the sixteen equations for encryption of a four bit word being determined by adding modulo 2 various combinations of four independent equations .

With respect to the set of equations in Figure 10, adding any two equations does not provide a third equation of the set, though adding 001 to each of the left hand columns of the Figure 10 again provides the null equation and the rest of the set of equations of Figure 5, which set is generatable by any three independent equations of the set.

It is this ability to generate the remainder of the equations

WO 93/03559

PCT/US92/06497 from a basic set of independent equations which the present invention is intended to avoid, the present invention doing so in an orderly and logical manner so that not only may the base set of linear equations be varied from time to time or dynamically in the various ways disclosed in the original application, but the resulting base set may also be nonlinearized from time to time or dynamically to a varying extent and in varying combinations, making cryptanalysis much more difficult than before.

Referring again to Figure 2, if one rearranges the order of the equations, there is, of course, no change in the mapping of the numbers in column 1 to the numbers in column 3. Accordingly, the equations in Figure 2 may be rearranged as shown in Figure 15. In particular, it will be noted that, neglecting the null equation, the first number appearing in column 2 (001) occurs in the next line of column 1, the second number in column 2 (111) occurs in the third line of column 1, etc., the wraparound resulting in the last number in column 2 (101) falling on the first line of column 1 (again neglecting the null equation). The resulting organization of the equations is in the form illustrated on page 7 of Appendix 2, where in Figure 15, xi is 001 and xm is 101. Any set of equations for words (numbers) of any bit length having a null equation and 2ⁿ - 1 non-zero equations may be so arranged without any changing of the mapping defined thereby, as such an arrangement is a mere changing of the order of appearance of the equations and not a changing of any of the equations themselves.

WO 93/03559

PCT/US92/06497 ;&lt;··

It is shown in Section 3.2 of Appendix 2 that certain groups of such equations may be altered by rearrangement of the words appearing in columns 1 and 2 to provide correspondingly new modulo 2 addition equations, which when substituted for the original group of equations within the original set of equations still maintains a one to one mapping and thus is suitable for use in encryption and decryption. In that regard, the one to one mapping is preserved because the order of the multibit words appearing in columns 1 and 2 of the selected group of equations is changed, but not the words themselves, so that the group of words mapped and the group of words to which they are mapped by the selected equations has not been changed, though within those two groups, which word in column 1 maps to which word in ’column 3 has been changed. The net effect of these changed equations is that the same no longer are linear extensions of the unchanged equations, that is, the same can no longer be generated by the addition of two or more of the unchanged equations. This, therefore, breaks up the linearity of the original set, the possible extent of which will be subsequently discussed, making the cryptanalysis more difficult as desired.

It is shown in Section 3.2 of Appendix 2 that under certain conditions, groups of equations within a given set may be altered and used to replace the corresponding original group of equations within the original set so as to maintain a one to one mapping for the complete set, and at the same time break up the linear characteristic of the set of r

r?

WO 93/03559

PCT/US92/06497 equations as hereinbefore described. These conditions are more specifically illustrated in equation form in Section 3.3 of Appendix 2, wherein the two possible modifications are illustrated in equation form. The basic concept is to take sums of consecutive triples of .rows in the original set of equations, with the analysis in Section 3.2 of Appendix 2 showing that, as stated in Section 3.3, the nonlinearization by taking such consecutive triples of rows works if, and only if, a set of only three or four consecutive rows of the original set are used. If three consecutive rows are used, four rows are actually modified, namely the three consecutive rows of the original set, together with a fourth row corresponding to the vector sum modulo 2 of the three consecutive rows. The modification can be obtained by adding vectorially to each of the four rows, the following equation:

Ul © X2) Φ Ul ® X2&gt; ** Θ

If four consecutive rows of the original set of linear equations are used, six rows of the original set of equations are modified, namely the four consecutive rows, together with the row representing the vector sum of the first three of the four consecutive rows, and the row corresponding to the vector sum of the last three of the four consecutive rows of the original set (e.g. the row corresponding to the sum of rows 1, 2 and 3, and the row corresponding to the sum of rows 2, 3 and 4, as shown on page 10 of Appendix 2). The modification in this case may be obtained by adding vectorially to the corresponding six rows the following:

WO 93/03559

PCT/US92/06497

<td> to</td><td> rows</td><td> 1</td><td> and q</td><td> (xi</td><td> Φ</td><td> X2&gt;</td><td> Φ</td><td> (XI</td><td> Φ</td><td> X2) = Θ</td>

<td> to</td><td> rows</td><td> 2</td><td> and 3</td><td> (xi</td><td> Φ</td><td> X3)</td><td> Φ</td><td> (XI</td><td> Φ</td><td> X3) = Θ</td>

<td> to</td><td> rows</td><td> 4</td><td> and q+1</td><td> (X2</td><td> Φ</td><td> X3)</td><td> Φ</td><td> (x2</td><td> ©</td><td> X3) = Θ</td>

The form of the equations above and the original equations shown on page 10 of page A2 of Appendix 2 suggests that nonlinearization works if one takes the first, second, third and one other row of the original set of linear equations, or alternatively, if one takes the first, second, third, fourth and two other rows of the original set of linear equations. Since the method works because the equations in the original set as selected for modification are linear within themselves, equations once nonlinearized by the methods of the present invention may not be again used as part of the nonlinearization process. This would tend to suggest that only four or six equations could be nonlinearized by this process, which of course would be an insignificant number of the total equations for larger word sizes {for instance, a four bit word requires 16 equations, an eight bit word 256 equations, etc.). However, again referring to Figure 15, it is to be noted that which word or i

number in column 2 is to be selected from the non-null rows i i

as xi is arbitrary. By way of example, if one selected Oil as xi rather than 001, the third non-zero line would become j the first, the fourth non-zero line the second, the fifth I non-zero line the third, the sixth non-zero line the fourth, · ί the seventh non-zero line the fifth, the first non-zero line the sixth, etc., essentially shifting the lower five equations up and wrapping the upper two non-zero equations

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0008.tif" />

around, with the result that the equations themselves are not changed, nor is the ordering of the equations, but rather ft* only the starting point in that sequence is changed. Such an arrangement of equations was shown in Figure 3, wherein χχ = 100 and xm (= ^χ7) ⁼ 011» Thus the equations presented on page 10 of Appendix 2 are general in the sense that if three consecutive rows and the row corresponding to the sum of the three consecutive rows are to be modified (nonlinearized) any three consecutive rows may be so selected, limited only by the fact that none of the three selected nor the row corresponding to the sum of the three can have previously been nonlinearized as a result of an earlier selection. Similarly, if four consecutive rows plus the two sum rows hereinbefore described are selected, any four consecutive rows may be so used, again provided that none of the four selected nor of the two sum rows may have previously been nonlinearized by this process. To generalize the equations for nonlinearization, one need only consider χχ as being the value in the second column of the first of the three or four successive rows selected, and renumbering values’ in each column accordingly.

It will be noted that the nonlinearization process is carried out on the equations other than the null equations. Since there are 2ⁿ - 1 such equations, wherein n is the bit length of the word used, there is necessarily an odd number of equations available for nonlinearization regardless of the value of n, whereas the nonlinearization process nonlinearizes an even number (4 or 6) equations at a time

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0009.tif" />

(obviously in a high speed system, apparatus may be provided to simultaneously nonlinearize different non-overlapping groups of a given set of linear equations, as the nonlinearization processes for non-overlapping groups are totally mutually independent, regardless of which process is used). Thus, it is clear that not all equations in any given linear set may be nonlinearized. Consequently, there is a question as to how many of the equations may be nonlinearized, and whether there is a logical manner of selecting equations for nonlinearization. These considerations are discussed in Sections 3.4 through 3.6 of Appendix 2. In general, while not all equations may be nonlinearized, normally a vast majority of the equations may be nonlinearized for word sizes of four or more bits, leaving the remaining nonlinearized equations of little significance, and perhaps if anything, possibly misleading from a cryptanalysis viewpoint. Further of course, it should be noted that varying from time to time or dynamically varying the number and identification of the rows to be nonlinearized and which nonlinearization technique is used further compounds the cryptanalysis problem, though such time varying or dynamically varying nonlinearization is not that difficult from a hardware standpoint (or software standpoint, if done under software control) as the starting set of linear equations (which themselves may be varied from time to time or dynamically, as herein before described) may be generated from a simple and readily variable generating function, which set of equations may be nonlinearized in both manner and

<img file="CA2115063C_D0010.tif" />

WO 93/03559

PCT/US92/06497 extent utilizing logical processes, which manner and extent may each themselves be varied from time to time or

<img file="CA2115063C_D0011.tif" />

dynamically.

As an example of the foregoing, attention is directed to the table on page Al (Appendix A of Appendix 2 hereof) which provides the sixteen equations for the linear mapping of a four bit number or word to another four bit number or word utilizing a specific generating function. Note that these sixteen equations are organized in the manner indicated for the original equations on page 10 of Appendix 2. As noted on page Al, it is easily verified that the sum of any two of the sixteen equations on page Al is another of the sixteen equations in accordance with the concept of linearity as used herein. This table on page Al is nonlinearized as described on page A8 and is presented in its nonlinearized form on page A9 of Appendix 2. In particular, the nonlinearization is in accordance with the first method, namely, utilizing three consecutive rows of the original set of equations (neglecting the null equation), plus the row representing the sum of the first three rows. In that regard, the sum modulo 2 of the first three non-zero numbers in column 1 (1001, 0001 and

0010) is equal to 1010, the value in the eleventh row of the non-zero equations. Thus rows one, two, three and eleven are nonlinearized by adding modulo 2 x^ Φ X2 to each of columns 1 &amp;.· &amp;

and 2 thereof. To be more specific, χχ equals 0001 and X£ equals 0010, so that © *2 ~ θ⁰¹¹· Adding modulo 2 0011 to the first equation gives 1010 © 0010 = 1000 (1000 is the original value in column 3 for the first equation) as shown

WO 93/03559

PCT/US92/06497 •V, in the table on page A9 . The same addition for the equations on lines 2, 3 and 11 carries out the transformation for these four lines. Similarly, if one adds lines 5, 6 and 7 of the non-zero equations, one obtains the equation of line 15 of the non-zero equations, the last non-zero equation shown on page Al. These four lines may be nonlinearized in the same manner as lines one, two, three and eleven, noting however that the applicable equation is effectively now:

(X5 © X6) Φ (^χ5 © *6) = Θ

With respect to further nonlinearization of the set of sixteen equations on page A9 of Appendix 2, there are two other series of three consecutive equations in the table, specifically, lines 8, 9 and 10 and 12, 13 and 14 which might be considered. The modulo 2 sum of lines 8, 9 and 10 however, provide line 3 of the non-zero equations, a line already used, and the modulo 2 sum of lines 12, 13 and 14 provide line 7, another line already used. Accordingly, while two additional groups of three consecutive lines or three consecutive equations exist, the same cannot be used for further nonlinearization because the sum of either of the three is a line or equation which has already been nonlinearized.

As another example, note the table set out at the top of page A4 of Appendix 2 hereof. This set of linear equations uses the same generating function but as applied to a new base (see the bottom of page A3 of Appendix 2), which when nonlinearized using the same set of equations as in the previous example (equations 1, 2, 3, 5, 6, 7, 11 and 15)

WO 93/03559

PCT/US92/06497 •x· provides the nonlinear set of equations set forth on page All of Appendix 2.

Finally, as a third example, note the example described near the bottom of page All, with the nonlinearized equations shown on page A12. This example is an example of another nonlinearization of the table of 15 equations (together with the null equation) presented on page Al of Appendix 2, nonlinearized using a different basis, specifically four successive (non-zero) equations 1, 2, 3 and 4 together with the sum of 1, 2 and 3, namely equation 11, and the sum of equations 2, 3 and 4, namely equation 12, together with the three successive equations 13, 14 and 15 and the sum thereof, equation 8. The equations for nonlinearizing four consecutive equations plus the two modulo 2 sum equations of course have been given before herein and are set out on page 10 of Appendix 2. In particular, three different equations are used, one for rows 1 and q, one for rows 2 and 3, and one for rows 4 and q + 1» By way of example, taking row 1, zero is added to column 3 and χχ φ X2 is added modulo 2 to each of columns 1 and 2 (the modulo 2 sum of anything to itself equalling zero) . Since xj φ X2 ^w 0011, adding this to equation 1 yields the equation 1010 ® 0010 = 1000, the first non-zero equation in the nonlinearized set of equations on page A12 of Appendix 2. For row 2 of the linear set of nonzero equations, φ X3 is added to each of columns 1 and 2, namely 0001 Φ 0100 = 0101. Adding this to columns 1 and 2 of row 2 of the linear set of equations of page Al yields the fifth non-zero equation in the set of equations on page A12.

WO 93/03559

PCT/LJS92/06497

<img file="CA2115063C_D0012.tif" />

Finally, as an example of the use of the third equation for rows 4 and q + 1, *2 ® ^x3 “ 0010 ® 0100 = 0110. Adding &gt; M this, for example, to columns 1 and 2 of row 4 of the linear non-zero equations yields row 2 of the non-zero equations in the nonlinearized set of equations on page A12. Of course all six of the applicable rows must be modified in accordance with the nonlinearization process. Thus, in this latter example, 10 of the equations are nonlinearized instead of the 8 in the prior example, and of course the resulting mapping from column 1 to column 3 is generally quite different for the two sets of equations.

Finally, the nonlinearized equations may be further modified by adding modulo 2 an offset to each of the first two columns. This, of course, is equivalent to adding the offset modulo 2 to itself which of course is 0 and therefore does not affect the numbers in the third column. By way of specific example, Figure 17 presents the set of equations of the third example described above and shown on page A12 of Appendix 2 as modified by the addition of the offset 0101 to the first and second columns.

Figure 16 shows a block diagram of typical apparatus for encryption and decryption in accordance with the present invention. As may be seen in Figure 16, it is convenient to ultimately use a look-up table in the form of a read/write memory wherein the clear text data block or the encrypted text data block (both n bits long) is presented in parallel as the address to the memory with the data stored at the corresponding address corresponding to the encryption or

WO 93/03559

PCT/US92/06497 î,·&lt;·/; \ £·?£;·. '· '·

<img file="CA2115063C_D0013.tif" />

decryption of the respective data block, respectively. For , f ' that purpose, it may be convenient to use a memory of twice !

t ·*· I the address space of that required for either encryption or ( . 1 .

decryption {e.g. n + 1 address bits) so that the memory * address range is one bit wider than the data block to be operated on. In this manner, one bit of the memory address may be used to designate whether the operation is to be an encryption or a decryption operation. By way a specific example, the most significant bit of the memory address might be 0 to indicate a decryption process or a 1 to indicate an encryption process, with the decryption data stored in the lower half of the address range of the memory and the encryption data stored in the upper address range of the memory. Thus both encrytion and decryption may be done as desired by the look-up table by control of the single bit, and encryption or decryption of a block of n bits may be achieved in a single memory cycle.

Assuming that the mappings for encryption and decryption »

are to be changed periodically and/or dynamically, some method of altering the contents of the look-up table must be provided. While this could be done by specialized hardware, &gt;· it is convenient to do the same by an appropriate processor ;

under program control, as the alteration of the encryption and decryption schemes normally will occur far less k frequently than the encryption and decryption process itself y must be carried out. Accordingly, the same normally need not &lt;

be accomplished with the same speed as encryption and decryption itself. Accordingly, the nonlinear dynamic

WO 93/03559

PCT/US92/06497 /'

I substitution generator shown in Figure 16 may operate under program control based on various inputs thereto. In particular, the equation for encryption may readily be generated under program control given certain basic information defining the same, such as by way of example the block substitution bit size (n), the base set of n linearly independent numbers, the generating function, the beginning equation of the linear set on which to begin nonlinearizing, and the number of iterations of the nonlinearizing function to perform.

Once the offset has been applied to the nonlinearized equations, each number or block in column 3 is stored in the portion of the look-up table assigned to encryption at an address equal to the block in column 1 for the respective row. Thus, when a number or block in column 1 is applied as the address, the number read out of the memory is the number in column 3 for that row representing the respective encrypted block. For the decryption portion of the table, the process is reversed, in that the blocks in column 3 are used as memory addresses (more appropriately address portions, the full address including the address bit designating decryption) with the data stored at those addresses being the respective blocks in column 1. Thus, during decryption the memory is entered at the address defined by the encrypted block, with the data stored at the respective address being provided as the output corresponding to the associated clear text block. For convenience,

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0014.tif" />

detailed methods for encrytion and decryption are set out in Appendix 3.

Obviously the encryption and decryption processes could be carried out entirely under program control, as both processes simply involve logical manipulations given certain (variable) starting information. However, the speed with which encryption and decryption could be carried out would be very grossly reduced, as the processor would wind up regenerating the same encryption and decryption equations over and over again. In comparison, the use of the look-up table allows a one time determination of the full set of encryption and decryption equations, which information for any data block to be encrypted or de-encrypted is continuously available in a single memory cycle until such time as the equations are to be changed.

While a preferred embodiment for the encryption and decryption of the present invention has been disclosed and described herein, it will be obvious to one skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention .

WO 93/03559

PCT/US92/06497

211506

APPENDIX 1

UNBIASED BLOCK SUBSTITUTIONS

ABSTRACT

A block substitution is a one-to*one mapping of the n-bit binary numbers onto themselves. Such a substitution or transformation can be represented by a permutation. It is shown 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. Such permutations are termed replicative, A subset of these have an additional feature which is that the equations which they define have an additive relationship when viewed as vectors. Such permutations are termed additive. An unbiased block substitution is defined. It is shown that substitutions defined by an additive permutation are unbiased and that any unbiased block substitution can be represented by a replicative permutation. Additive permutations are shown to form groups which retain the same properties. The conditions for existence of these additive permutations are established, some properties of the groups determined, and the number of such groups enumerated and compared with all possible permutations of the n-bit numbers.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0015.tif" />

INTRODUCTION

A block substitution is the term usually applied to a one-to-one

- H* mapping of the n-bit binary numbers onto themselves. This mapping can De written as a pairing of the 2ⁿ n-bit numbers:

^X1 ^x2 ²1 ^z2 ²k where each column is the set of the same 2ⁿ distinct n-bit numbers but written in different orders. Thus, this mapping can be thought of as a permutation of the n-bit numbers written as:

*1 X₂ ... X_k or (x^ x^ xj ...) for some set of indices simply means that x^-.......» χ^, x^ ............ xj ,

This usual notation for permutations etc.

Going back to the column notation, one could define a set of simple equations from the original set and its image:

Vi Θ *1 = *1 y₂ © x₂ = z₂

Λ Θ x_k · z_k cm fejcrTT-ri cucct

WO 93/03559

PCT/US92/06497 where © means modulo 2 addition (i.e., addition of corresponding digits witnout carrying). In general, the set jy^, ... f wi 11 not all be distinct but in certain circumstances they will be. When they are distinct, block substi I* tutions can be generated by modulo 2 addition rather than by conventional means. The main tasks are to determine the circumstances, if any, in which this scheme works, how the substitutions can be quickly changed, and the lack of bias.

It is not obvious that block substitutions can ever be generated by modulo 2 addition. For example, consider the attempt to substitute one arrangement of 3-bit binary numbers for another by modulo 2 addition. This is shown in Figure 1. In column 3, on the right, Oil and 100 each appear twice, while 001 and 110 never appear. The numbers in column 1, on the left, acting on the numbers in column 2, in the center, constitute a transformation of the set of 3-bit binary words into themselves. This is a many-one transformation and is useless for block substitutions.

<td> 000</td><td> Θ</td><td> 000 =</td><td> 000</td>

<td> 001</td><td> Θ</td><td> 011 =</td><td> 010</td>

<td> 010</td><td> Θ</td><td> 110 =</td><td> 100</td>

<td> Oil</td><td> Θ</td><td> 100 =</td><td> 111</td>

<td> 100</td><td> Θ</td><td> 111 =</td><td> Oil</td>

<td> 101</td><td> Θ</td><td> 001 =</td><td> 100</td>

<td> 110</td><td> Θ</td><td> 101 =</td><td> Oil</td>

<td> 111</td><td> Θ</td><td> 010 =</td><td> 101</td>

Figure 1. Modulo 2 Addition, Many-One Transformation

SUBSTITUTE SHEET

WO 93/03559

PCÏ7LS92/06497

Trying another'arrangement shown in Figure 2 gives a different result. In this case, the transformation is one-to-one from the 3-bit binary numbers onto themselves. Each column consists of all the 3-bit numbers exactly once.

τη / υ

Ft ί\

<td> 000</td><td> Θ</td><td> 000 =</td><td> 000</td>

<td> 001</td><td> ©</td><td> Ul =</td><td> no</td>

<td> Q1Û</td><td> ©</td><td> on -</td><td> 001</td>

<td> on</td><td> ©</td><td> 100 =</td><td> in</td>

<td> 100</td><td> ©</td><td> no =</td><td> 010</td>

<td> 101</td><td> ©</td><td> 001 =</td><td> 100</td>

<td> 110</td><td> Θ</td><td> 101 =</td><td> on</td>

<td> 111</td><td> ©</td><td> 010 =</td><td> 101</td>

Figure 2. Modulo 2 Addition, One-to-One Transformation

Definition: 2ⁿ = m+1 equations:

A replicative array of n-bit binary numbers is a set of

Λ © ^xi ^{= 2}i ^ym+l © ^xm+l ^{= r}m+l where the sets Jy*j, jx_k[, and jz_k| each consist of the 2ⁿ distinct n-bit binary numbers.

The set |y_k f defines the mapping x_k—*z_k values, exactly one member of the set y.

= Zj is a *ixed point and there is no other, of the distinc* -bit numbers, it is a permutation ^xj

Since the y_k take on all •0) the identity. Thus, Since each column consists of each of the other two columns.

The first question is how to construct such a replicative array.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0016.tif" />

Proposition 1: A replicative array of n-bit binary numbers can be constructed from sums of any set of n+1 rows each of whose columns contain the identity and n generators of G_n, the group of n-bit binary numbers.

i?

Proof: Without loss of generality we can assume that the first n+1' rows have this property. Either one row is I = I © I or the identity occurs in three different rows. Assume z^ = x^ = y^ = 1. Then each set

I ^z2.....^zn+l I · ί ^x2 * ····· ^xn+l )· ^2’ .....*n+l i ^{is com}P°^{sed of} distinct generators of G_n. To construct tne remaining rows of the array, take modulo 2 sums of pairs of rows 2 through n+1, sums of triples of these rows, etc, and, finally, n+1

5T ²i- Tb® number of additional rows constructed i = 2 in this manner is:

<img file="CA2115063C_D0017.tif" />

So the array is completely specified by this process. Since each of the z^, x^, and y^ for i &gt; n+1 are different linear combinations of the generators, they will all be distinct, and the sets of 2ⁿ elements of )z_i [, |x^ | and &gt;y^ { will each be a permutation of the n-digit binary numbers.

Now assume that z^ ^s x^ - y₃ = I. No pair of rows from tne first tnree could be added together because this would cause a duplication of x_2&gt;or y^ in one of the columns. We avoid this problem by adding together odd num-

<td> bers of rows from the initial</td><td> n+1 rows.</td><td> Thus we have:</td>

<td> (n+1)! n+1 = - (n+l)!l !</td><td> (?)</td><td> single rows</td>

<td> 1 n-t-1) !</td><td></td><td> triple sums of rows</td>

<td> 3! (n-2)!</td><td> I 3 )</td><td></td>

<td> (n+1)!</td><td> -. /n+H</td><td> quintuple sums, etc</td>

<td> 5!(n-4)!</td><td> \ 5 /</td><td></td>

fti tQerrvvi its

WO 93/03559

PCT/US92/06497 i 1 η c

Keeping in mind the general identity for binomial coefficients: ^J ·- ·^; u U

<img file="CA2115063C_D0018.tif" />

we can sum the number of rows generated this way, for n odd:

<img file="CA2115063C_D0019.tif" />

For n even, the final term in the sum on the left is:

I n+1 \ / n \ \ n+1/ \ n/ so that it again adds to 2ⁿ rows.

As in the first case, the column elements are 2ⁿ distinct linear combinations of the generators and the identity. (Q.E.D.)

Proposition 1 gives a method of generating replicative arrays but does not imply that all can be generated this way. It is convenient to introduce another definition. The individual rows of the replicative array can be thought of as vectors which can be added to each other by adding the corresponding scalar components modulo 2.

Definition: A replicative array, which has the property that the vector sum modulo 2 of any odd number of rows is again another row in the original array, will be called an additive array.

Clearly, replicative arrays generated as in proposition 1 are additive arrays, but there are others as well which do not have this additive property.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497 .-J &gt;&lt; Λ p ’Λ * ⁰ ώ il ΰ·ν υ ύ

Proposition 2: Any additive array of n-bit numbers with fixed row

I © I = I has a maximal set of n linearly independent rows.

Proof: Let k be the maximal number of independent rows and assume k &lt; n. The additive array has exactly 2ⁿ rows including the identity. By

L· proposition 1 these k rows generate an array of 2 rows. Thus, the remaining 2ⁿ - 2^ rows must be duplicates, and the array cannot be additive.

If k - n+q where q is a positive integer, then a maximal set of independent rows will generate 2^ rows. In each column, each of the 2ⁿ distinct n-bit numbers will appear 2^q times. This 2ⁿ additive array is embedded in the array with 2°^ rows. One can extract it by making a proper selection of rows from the larger array. Choose the first row for the additive array, for example, © y^ = Zp x^ will appear 2^q-l more times in column 1, similarly for y^ in column 2 and z^ in column 3. Since the same combination of x^ and yy will not occur again, 3 (2^q-l) rows must be eliminated from further consideration for the additive arrays From the second choice, Zp ^oneeliminate 2^q-l rows containing Zj U column 3, but since x? ^or /2 ^{may have}appeared in a row already eliminated, we can only say that in the second step, the number of rows eliminated is &gt;_ 2^q-l. For each succeeding step 2^q-l rows are eliminated. The process is complete after 2ⁿ steps. 2ⁿ rows have been selected and the number of rows eliminated is:

&gt; 3(2^q-l) + (2ⁿ-l) (2^-1) = (2ⁿ+2) (2^-1&gt;

Thus, the total number of rows selected and eliminated is:

2ⁿ + (2ⁿ+2) (2^q-l) = 2^n+q + 2(2^q-l) &gt; 2^n+q.

So there are not sufficient rows to complete this process. This contradiction implies k ** n. (Q.E.D.)

The above may seem to be rather academic, but it shows how to generate additive arrays and the resulting substitutions, and also shows that this process gets them all. But these additive arrays have another very useful property described in the next proposition.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0020.tif" />

Proposition 3: An additive array with fixed identity row is a group.

Proof: Rows in the array can be thought of as vectors and added by respective components:

*i Θ ^{= z}i ^xj O 3 ^{= z}j \ Θ Λ ⁼ where x^ 0 x^ = x^, etc. This is the group operation. Each row in the array is the sum of some subset of the n generators. The sum of two rows is also the sum of some subset of the generators and, thus, is in the array which consists of all possible such sums. The group identity is the row 1 = 10 1. (Q.E.D.)

Each pair of columns defines a permutation as follows: take a number in one column, e.g., y^ in column 2, and find the same number in column 1. It will have a partner, say ⁱⁿ column 2. Again, locating y^ in column 1, there will be a partner y^ in column 2. This defines a permutation y^—►y₉—„y₃—► ... from column 2 to column 1. Six such permutations, three of which are distinct, are defined by the additive array.

Definition: A permutation defined by an additive array will be called an additive permutation.

Initially, consider the case where the fixed point is I, and let ^ym+l ^{= = z}m+l ⁼ I· The ^{order rows} The additive array is arbitrary.

For the second row, one could select yj = xi and for the third row, y^ = Xj,

<td> Redesignating the indices,</td><td> one</td><td> obtains:</td><td></td>

<td> I</td><td> Θ</td><td> I »</td><td> I</td>

<td></td><td> Θ</td><td>^X1 ⁼</td><td>^Z1</td>

<td> *1</td><td> Θ</td><td>^x2 ⁼</td><td>^z2</td>

<td>^x2</td><td> Θ</td><td>^x3 ’</td><td>^z3</td>

©f ΙΡΡΤΓΗ ITC QLICCT

WO 93/03559

PCT/US92/06497

IS

The order of the numbers in columns 1 and 2 now represents the permutation defined by those two columns which leads to:

- M

Definition: An additive array whose rows are arranged in the order defined by the permutation between columns 1 and 2 will be said to be normalized.

Proposition 4: An additive array with fixed identity can be written in the form:

i0i = i ^xm © ^X1 = ^xl-p ^X1 Θ «2 = *₂-p ^xm-l © *111 ^xm-p where p is an integer.

Proof: In normalized form the array can be written:

I 0 I = I ^xm © ^xl ^{= Z}1 ^X1 © *2 = z₂^xm-l © «π. = ^zm

<img file="CA2115063C_D0021.tif" />

».- ·.· ft! IRSTIT, «ΤΓ AWFFT

WO 93/03559

PCT/US92/06497

Since the array is a group, it can be regenerated by taking sums of successive pairs of rows to uotain:

0 fi fi (J -J &lt;?

ι © i ^ίχι Θ x_m) © (*! © i*1 © © ^ίχ2 θ ^x3&gt;

'Vi © ^xm⁾ © ^lxm © ^xl&gt; = '^zm © ^ZP

The rows in the new array must be the same (but rearranged) as those in the original. From the diagonal structure on the left, the order of the rows must be the same although the starting point in the sequence of rows has been shifted by some unspecified number of positions. Column 2 in the new array is:

h ^z3 ^Z1 which is the same as column 3 in the original array. So column 3 in the original array is the same as column 2 in the original array but shifted by some unspecified number of positions p. (Q.E.D.)

As will be seen later, the shift p can take on only certain values. So far, no means has been found to determine p in advance or from a knowledge of p, :

to determine the array, except for special cases. However, there are some rules for eliminating possible values of p and for pairing permissible values. The shift p determines whole classes of arrays and substitutions. So far, all possible values of p have been found for block ε·ζβ π £8. h

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

Proposition 5: If g is a maximal length additive permutation of n-bit binary numbers with fixed identity, then for any power s of the permutation g, g^s is also additive.

Proof: g is defined by columns 1 and 2 cf the following additive array, omitting the.identity:

^xm © ^X1 ^{= x}l-p *1 © ^x2 = ^x2-p ^xm-l θ ^xm ^xm-p

Tne array which defines g^s is;

^xl-s O ^x! ^s «1 ^x2-s Θ ^x2 ^{s w}2

X_ _e Θ X_m^{= W}m m-s m m

As in the proof of proposition 4, from the group structure of the array for g, g can be regenerated by taking the sums of the m pairs of rows whicn are s spaces apart:

^(xm © ^xs^} © ^(X1 © ^xs+l^{) = W}1 © ^ws+l (*1 © Xs+1) Θ (X2 Θ ^xs+2^{) = w}s © ^ws+2 ^(xm-l © ^xs+m-P © f^xm © ^xs₊m^{} 3 w}m ©

From the diagonal structure on the left, it is clear that columns 1 and 2 are in the same order as before but with a different starting point, i.e., tne array

SUBSTITUTE SHEET

WO 93/03559 PCT/IJS92/00497 Γ »

p.î'j ⁵¹ 2115963 '^ÿ has been rotated. Noting that x_s__s = x_m, from the array for g^s, ^xm © *_s^{= w}s j

Thus, column 1 (or column 2) of the rotated array for g consists of the set j w₁, ..., w_m [ which is a displaced or rotated form of | ^xp · · · » ^xm } 'Q.E.D.)

I

This shows that the general form of a row in the additive array for j..

g^s is: f \-_S © \ ’ \-p_s where p_s is the shift corresponding to the power s. p_s is related to the basic shift p and is different for each value of s. It is important to know these shifts and their sequences when changing from one substitution to another in the same permutation group. More will be said about this later.

In proposition 5, the property of being additive is necessary.

Examples can be shown of replicative permutations g which are not additive and for which g^s is not replicative.

Proposition 5 is also true even if g is not a maximal length permutation. The presence of cycles slightly complicates the proof. However, there is little practical interest in starting with substitutions corresponding to non-maximal permutations because powers will not generate the full group.

The permutations which have fixed points other than the identity also form groups. However, the additive arrays which generate them are not groups.

The next step is to show that these groups of permutations and the corresponding substitutions have the highly desirable property of yielding all possible input/output pairs.

Since each additive permutation is generated by an array in which pairs · of columns keep exactly one element fixed, each permutation will keep one of the Γ

2ⁿ binary words fixed. Thus, these permutations not only belong to the symmetric group of all permutations on 2ⁿ elements, but they also belong to the subgroup P_m of permutations on m* 2ⁿ-l elements. All powers of a given per* J mutation will form a group. The order of the permutation is the least common multiple of its cycles, and the order of the group is the number of distinct permutations in it. A permutation is said to be regular if all its cycles are i the same length.

WO 93/03559

PCT/US92/06497

211 ) U i’·

t.

An important property for a group of permutations is transitivity. A transitive group has at least one permutation which transforms any element or word into any other.

Proposition 6: If G is a subgroup of P_m which is generated by powers, of an additive permutation g, where g is of order m = 2ⁿ-l» then G is transitive on the 2ⁿ-l non-fixed words.

proof: Omitting the single cycle permutation (j) corresponding to the fixed word, Xj, G is a subgroup of permutations on the 2ⁿ-l n-bit words that are held fixed. Since the m powers of g jg, g², g³, .... g^m = I ( generate G, its orderj G j = m. Let G| be the subgroup of G which holds fixed one of the 2ⁿ-l n-bit words. Since this is a group of additive permutations, Gj = j I ( the identity permutation only. So G^ has order | G| j = 1 and the index of G^ in G

I —£- I = m. So G is transitive. (Q.E.D.) ^G1 I

ADDITIVE ARRAYS WITH OTHER FIXED POINTS

One can generate additive arrays with a fixed element other than the identity by simply adding a fixed binary number to each number in column 1 and column 2. For example, let H be the array (and group) as written in proposition 4, and generate a new array H' as follows:

<td colspan="4"> H</td><td rowspan="2"> w (x_m Θ &gt; (X! © w)</td><td rowspan="2"> H © w = I © (Xj © w) = © (x₂ © w) = •</td><td rowspan="2">^xl-p ^x2-p</td>

<td> , I ^xm ^X1</td><td> Θ Θ Θ «</td><td> I = ^X1 ⁼*2 - 1</td><td> I ^xl-p *2-P</td>

<td>^xm-l</td><td> 4 è'</td><td> » » X_m⁼m</td><td> ^Sn-p</td><td>^(xm-l ©</td><td> w) © (X_m © w)</td><td>^xm-p</td>

<td> be</td><td colspan="2"> Clearly, H in H since</td><td>¹ has the w'</td><td> 2ⁿ rows and the sum of s will cancel out. If</td><td colspan="2"> any pair or even number of rows any odd number of rows in H' are</td>

r.;· » ^v· · ? ' summed, it will result in a row in H* because it is equivalent to the sum of rows in H plus the row w © w = I. Thus, Hu H* has 2°^4-1 elements, is

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

9 ί ί A Ρ &lt; 1 ί «&gt; V 0 c closed under addition of rows, and contains the identity I © 1 = 1. Thus,

HUH' is a group, H is a maximal subgroup, and H‘ = H is the relative complement of H.

We can shift column 1 in H¹ to obtain the array corresponding to a power of the permutation defined by the original array. A typical row is:

^{xk_j © ^w) ©^(xk © ^{w) = x}k - Pj

This is the image of the corresponding row in the jth power of H. So the permutation defined by H' is additive and so are its powers.

Now, suppose that we have an additive array with 2ⁿ rows for which I is not fixed. Further, assume that the array contains sums of all odd combinations of n+1 linearly independent rows. As in the proof of proposition 1, this generates exactly 2ⁿ rows. Thus, no sums of even sets or rows can be in the array. Since I occurs once in column 3, there is one row of the form w © w - I. Adding it to each of the single rows, including itself, generates an additive array of 2ⁿ rows with fixed identity.

Thus, there is a one-to-one correspondence between additive arrays with fixed identity and additive arrays with another fixed number.

Thus, all the additive arrays of interest for use as block substitutions have either fixed identity or can be derived from such arrays as described above. In what follows, additive arrays will have fixed identity unless otherwise specified. Typically, the row I © I = I will be omitted.

irs-tth itc surer

WO 93/03559

PCT/US92/0M97

GENERATION OF ADDITIVE ARRAYS

It is helpful to know something about the distribution of independent rows or generators in the array.

Proposition 7: In a maximal additive array with fixed I, on the n-bit binary numbers, any n consecutive rows are generators.

Proof: Consider the first n rows:

^xm O ^X1 ^{= x}l-p x_ ί Θ x« = x« ~ n-1 n n-p

If these are not independent then

<td>^xn ⁼</td><td> Σ i«Q</td><td>^xi</td><td colspan="2"> «n-1 * Σ *i.i ieQ</td><td> x_{n n} = n-p</td><td> Σ *i._p ieQ</td>

<td colspan="2"> where £) is a subset</td><td> of</td><td> u.</td><td> ,..., n-1 } with s £ n-1</td><td> elements,</td><td> The next row in</td>

<td> tne array will</td><td> be:</td><td>^xn</td><td> Θ</td><td>^xn+l - ^xn+l-p· ^Since</td><td colspan="2"> the array is an additive</td>

<td> group, it must</td><td colspan="2"> be true</td><td> that</td><td>^xn+l ⁼ Σ ^xi+i ^and</td><td>^xn+l-p</td><td> ΣΖ ^xi+l-p*</td>

<td></td><td></td><td></td><td></td><td> ieQ</td><td></td><td> ieQ</td>

In that case applying this to each successive row, one could generate the entire array witn s &lt; n generators. (Q.E.D.)

This is enough for our purposes, but it can also be shown that any n equally spaced rows are generators.

ftl IPSTITIITP AWPfrr

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0022.tif" />

<img file="CA2115063C_D0023.tif" />

c··

t.

fe'·:

ts

THE SHIFT p

In what follows, it is assumed, unless otherwise stated, that^the additive arrays are maximal, normalized, and with fixed identity. For brevity, the row I © I - I will be omitted. The general form for the kth row of the basic array is:

^xk-l © ^xk = ^xk-p

For the array corresponding to the power s of the basic permutation, the kth row is:

^xk-s © ^xk = ^Xk-Ps

As usual, n is the block size and in = 2ⁿ-l. 8y definition, Pj = p. It is important to know something about the values of p_s in order to use the block substitutions which they generate. It is obvious that p_s „ p if s * t.

Proposition 8: p &gt;_ n

Proof: The (p+11st row of the basic array is:

^XP Θ ^xp₊l ^{= X}P+1-P ^{= X}1

If p+1 £ n, this implies that the first n rows are dependent which contradicts proposition 7. (Q.E.D.)

Note: Since s is a power of a permutation g of order m, if s = m+k g¹** = g^m = g^k = I o g^k.

So the exponents can be expressed modulo m.

»

I i

SUBSTITUTE SHEET

<img file="CA2115063C_D0024.tif" />

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0025.tif" />

Proposition 9:

If p is an allowable value for the shift, so is

2^π-ρ

Proof: In the normalized array, the first column is displaced down one place with respect to column 2. The third column is displaced down p places (the shift) with respect to column 2 and p-1 places from column 1. If we interchange columns 1 and 2 and turn the resulting array upside down (i.e., reverse the order of the rows) then in the new array, the third column is shifted down m-(p-l) = 2ⁿ-p places with respect to column 2. Since only the order has been changed, the new array is equivalent to the original in the sense that it will generate permutations from the same group. (Q.E.D.)

Note: Sincef n, p £ 2ⁿ-n.

Proposition 10: If the power s = 2^r for some integer r &gt;. 0, p_s = sp.

Proof: If r = 1, s = 2 and = ^xk-p2* ^{One can wr}^^te: *k-2 © ^xk ^{= x}k-2 © *k-l © ^xk-l © ^xk·

Considering k-1 ano k-p as indices, ^xk-2 © ^xk ^{= x}k-l-p © ^xk-p ^{= x}k-p-p ^{= x}k-2p·

So p£ = 2p and the statement is true for r = 1.

Assume that for some s = 2^r, p_s = 2^rp. 2^r+^ * 2^r + 2^r.

Then, ^xk-2^r+1 © *k ’ ^xk-2^r-2^r © ^xk * ^xk-2^r-2^r © ^xk-2^r © ^xk-2^r © ^xk = ^xk-2^r-2^rp © ^xk-2^rp ^{= x}k-2^rp-2^rp * ^xk-2^r+1p‘ (Q.E.D.)

There are other constraints on p, the shift in the third column. If g is the permutation defined by columns 2 —► 1 of the additive array, then the permutation defined by columns 1 — 3 is g^p_1 and by columns 3 —* 2, is g^m‘^p. These permutations are obviously commutative and g o gP'¹ □ g^m'^p g° = l, the identity permutation.

The sum of tne exponents 1 + (p-1) + (m-p) s 0 mod m. Clearly, &lt; p &lt; m. More generally, for a power gs, the corresponding permutations are:

9^s . g^ps-^s . g^m-Ps = !

Then s + (P_s-s) + (m-p_s) s Ü mod m and p_s # s, m.

i

Vf.

V?

;

I

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

7 Q 4 Λ A. A &lt;·} ώ i i ü V ϋ ύ

Proposition 11: If an additive array generates the power s of the basic permutation in two pairs of columns, it generates this in all three columns and 3s 0 mod m.

Proof: If two of the three permutations are of the same power, the '* array can be arranged so that typical rows are:

i

I

I i

« ί

;

^xk-s © ^xk = ^xk₊s ^xk © ^xk₊s ^{= x}k+2s

3y the group property, adding these together will give another row in the same array:

^xk₊s © ^xk+2s ^{= (x}k © ^xk+s’ © ^!xk © ^xk-s^!^{= x}k₊s © ^xk-s which implies that ^xk+2s = x_k__s and that 3s ® 0 mod m. This will occur only if 3 I m, in which case, p_$ = -s a 2s mod m, and p_s-s = 2s-s = s, m-p_s = s.

(Q.E.D.)

Corollary: If an additive array generates the same permutation witn eacn pair of columns, the permutation is of order 3.

Proof: If h = g^s is generated as in proposition 11, then n^ = g3s = i.

(Q.E.D.)

If p = 2s, or m-s, the same permutation will be generated, so

- s 2 if 3 Ym, P_s * I s, 2s, , m-s, mJ.

^{1 2} i

* i

BURSTrruTe bheft

WO 93/03559

PCI7US92/06497

211

-î i c.

There are a number of miscellaneous facts to help select or eliminate candidates for the shift, but so far insufficient rules have been found to fully determine the shift pattern. Some of the facts are:

1. If p_s = t, then p_t = s by symmetry

2. If p = 2^X, then ^xk-l ^{= x}k ® ^xk-p ^{= x}k ® ^Xk-2^{x = X}k-2^xp ^{= x}k-2^^x?t which is possible only if 2 =1 modulo m.

3. If p = 2^X+1, then ^xk ^{= x}k-l © ^Xk-1-2^X ’ ^xk-l-2^tp ^{= x}k-l-2^t(2^t+l) which is possible only if 2^^z + 2^Z + 1 s 0 modulo m.

m

4. If p| m then^-“ # 2^X -1 since otherwise, 2^xp = m+p and ^xk © ^Xk-2^{X s X}k-2^xp ^{a x}k-m-p ^{58 x}k-p ^{= x}k © ^xk-l ^{and x =} °' k .. »·..· I-' ·

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

ENUMERATION OF MAXIMAL ADDITIVE PERMUTATIONS

The additive arrays, by convention, have been constructed according to the permutation defined by columns 1 and 2. If the permutation is of maximal length (i.e., a permutation of m = 2ⁿ-l elements with no subcycles) the array’ will be maximal also in the sense that it has no distinct self-contained blocks Conversely, the maximal array will generate a maximal permutation. However, powers of a maximal permutation may have cycles. This will be the case unless the maximal length permutation is of prime order. Thus, no general conclusions can be drawn about the permutations generated by other pairs of columns.

If all six of the permutations generated by the additive array have the same cycles, the array will nave corresponding cycles in the form of disjoint subarrays of the same length in which each column has the same elements. If the basic permutation generated by columns 1 and 2 has a cyclical structure not shared by the other permutations, then there will be disjoint subarrays or blocks in the array in which the elements in column 3 will be distinct from those in columns 1 and 2.

It is also obvious that any maximal length additive permutation can be used to generate a maximal array. Thus, initially considering arrays and permutations with fixed identity, there is a one-to-one correspondence between maximal length permutations and columns 1 and 2 of maximal arrays and, hence, with the array as an entity.

Proposition 12: For n-bit binary numbers, the number of maximal length additive arrays with fixed identity for a given value of the shift p, is

M(n) = ]~| (2ⁿ-2^k) where m = 2ⁿ-l.

k = 1

Proof: Let Q(n) be the number of distinct sets of generators of the n-bit binary numbers. Each set of generators will generate a maximal array. However, the order in which the generators are used makes a difference. This is because the column 3 lead term x_m = f (x^ ... x_n) depends on the relative

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0026.tif" />

orders of the generators. There are n! such orders. Once an array is generated, the starting row of the array or starting point of the permutation is irrelevant. For example, if the first row is: ^xm © ^xi ^{= x}l-p be circulated to the bottom and instead start with: © x₂ = Xj-p so the process is redundant by a factor of m = 2ⁿ-l.

Therefore:

n!

M(n) ~ —— Q(n)

Assume Q(n,k) = — k!

Π (2ⁿ-2^) is the number of independent k-tuples which j=0 can be selected from n-bit words. Clearly, it is true for k = 1 or k = 2. π-tuples can be constructed by adjoining a single n-bit word to an (n-l)-tuple. There are m such words which could be adjoined. However, m = 2ⁿ-l must be diminished by eliminating the n-1 -/^0-¼ words which duplicate those in the (n-l)-tuple, (n-l)-tuple, words in the by the / ⁿ’^\ words which are \ ²7 etc, and finally by the 1 = (n-l)-tuple. Thus, m must be

<td colspan="3"> sums of pairs of words in the</td>

<td> n-1</td><td> \ word which is</td><td> the sum of all</td>

<td> n-!'</td><td> ' n-1</td><td></td>

<td colspan="2"> diminished by 57</td><td> /n-1 \ _{= 2}n-l</td>

<td></td><td> j = 1</td><td> \^j /</td>

The number of words to be adjoined to the (n-l)-tuples = 2^η-1-Ι2^η'*-1)

- 2ⁿ-2ⁿ’^. However, eacn n-tuple could be generated by n different (n-l)~tuples, so that, ₂n ₂n-1 ₂n ₂n—1

Q(n) = Q(n,n) =-Q(n,n-1) =η n n-1 n-1

Thus, M(n) η (2ⁿ-2^k) « [j ^m k=0 k=l (q.E.D.) n-2 , n-1

- Π (2ⁿ-2^k) n-1 )1 k = 0 (2ⁿ-2^k1 n ok\ _ _1_ η (2ⁿ-2^k) nl k=0

SUBSTITUTE SHEET

WO 93/03559 PCT/US92/06497

M(n) can be rewritten in a form easier to compute:

n-1 n-1

M(n) = f] (2ⁿ-2^k) = 2^s f] (2^j-l) k-1 j=l n(n-l) where s -- . There is a simple recursive relationship:

M(n+1) = 2ⁿ (2ⁿ-l) M(n)

Unless m is prime, the permutation group will contain some permutations which are not maximal and, thus, will have some proper cycles. These will be powers g^s of a maximal permutation g where s is a divisor of m. These can be enumerated by counting the number of values of s which are divisors of m-1.

In a group of additive permutations of n-bit numbers with fixed I, there are L(n) maximal permutations and S(n) non-maximal permutations.

L(n) + S(n) « m-1 = 2ⁿ-2

While there are 2ⁿ! permutations on the set of n-bit numbers, there are only 2^η*! which give distinct substitutions because the starting point in tne permutation does not make any difference. In the maximal additive array, we can cycle the order of the rows, other than the fixed row, and not change the substitution. These additive arrays generate permutations which are a subset of all possible permutations having a single fixed point. If F{n) is the total number of permutations holding any one of the 2ⁿ words fixed, then

2ⁿ i

F(n) = 2ⁿ(2ⁿ-2)! = —-.

m

For convenience, a number of other terms can be defined. They are as follows:

Np(n) - the number of distinct values of pp the basic shift in column 3 of a maximal additive array of n-bit numbers.

ft! irstiti iTC swFPT

WO 93/03559

PCT/US92/06497

2115982

M(n) - the number of maximal additive permutations for a given p and a given fixed point. It is derived in proposition 12.

Tin) - the total number of additive permutations for a given p and a given fixed point. If m = 2ⁿ-l is prime, then T(n) = Min).

In general :

m-1

Tin) =- Min).

Lin)

H(n) - the total number of additive permutations on n-bit numbers:

H(n) = 2” N_pin) Tin).

G(n) - the number of groups of additive permutations on n-bit numbers:

Gin) =

Hin) 2Np(ⁿ⁾M(n m-1

Lin)

Table 1 is a tabulation of these parameters for bit size n £ 8. Ratio gives a measure of the relative rarity of additive permutations.

H(n)

Fin)

UNBIASED BLOCK SUBSTITUTIONS

In designing a block substitution device, a basic goal is to have an unbiased transformation of the n-bit binary numbers onto themselves. This does not seem to be well defined but, basically, one desires that the cipher text contain no information on the nature of the clear text. For example, no subset should be mapped onto itself, and numbers with some characteristic (such as, even, lower half, zero in a binary position) should be equally likely to be images of a number with the same property or the reverse property. To require

SUBSTITUTE SHEET i

<img file="CA2115063C_D0027.tif" />

WO 93/03559

PCT/US92/Û6497

Table 1. Comparison of Permutations of Various Bit Sizes

Λ f* ί' *: I ?-&gt; ·&lt;

<td> n</td><td> 3</td><td> 4</td><td> 5</td><td> 6</td><td> 7</td><td> 8</td>

<td> 2ⁿ</td><td> 8</td><td> 16</td><td> 32</td><td> 64</td><td> 128</td><td> 256</td>

<td> m</td><td> 7</td><td> 15</td><td> 31</td><td> 63</td><td> 127</td><td> 255</td>

<td> N_pin)</td><td> 2</td><td> 2</td><td> 6</td><td> 6</td><td> 18</td><td> 16</td>

<td> M(n)</td><td> 24</td><td> 1,344</td><td> 322,560</td><td> 3.20 x 10⁸</td><td> 1.29 χ 10¹²</td><td> 8.42 x 10ⁱ⁶</td>

<td> L(n)</td><td> 6</td><td> 8</td><td> 30</td><td> 36</td><td> 126</td><td> 128</td>

<td> Sin)</td><td> 0</td><td> 6</td><td> 0</td><td> 26</td><td> 0</td><td> 126</td>

<td> T(n)</td><td> 24</td><td> 2,352</td><td> 322,560</td><td> 5.51 x 10⁸</td><td> 1.29 x 10¹²</td><td> 16.78 χ 10¹⁶</td>

<td> H( n)</td><td> 384</td><td> 75,264</td><td> 61,931,520</td><td> 2.12 χ 10¹¹</td><td> 2.97 χ 10¹⁵</td><td> 6.87 x 10²⁰</td>

<td> G(n)</td><td> 64</td><td> 5,376</td><td> 2,064,384</td><td> 3.41 χ 10⁹</td><td> 2.36 χ 10¹³</td><td> 2.71 x 10^1S</td>

<td> F(n)</td><td> 5760</td><td> 1.39 x 10¹²</td><td> 8.49 χ 10³³</td><td> 2.01 χ 10⁸⁷</td><td> 3.04 χ 10²¹³</td><td> 3.36 χ 10⁵³⁴</td>

<td> H(n)</td><td> .0667</td><td> 5.40 x IO⁸</td><td> 7.30 x 10~²⁷</td><td> 1.05 χ ΙΟ’⁷⁵</td><td> 9.79 χ IO¹⁹⁹</td><td> 2.04 x IQ*⁴⁸⁴</td>

<td> F(n)</td><td></td><td></td><td></td><td></td><td></td><td></td>

WO 93/03559

PCT/US92/06497 that all outputs be equally likely for a random input is insufficient and requires only that the transformation be one-to-one. The following definition is proposed.

Definition: A transformation or substitution of the n-bit binary numbers onto themselves is said to be unbiased if:

a. There is no invariant subset other than a single fixed point.

b. Every maximal subgroup of the n-bit numbers is mapped in two equal parts into itself and into its relative complement.

Before proceding further, it is necessary to collect some facts on these maximal subgroups. Any set of binary numbers that has zeros in the same binary position is such a subgroup; however, there are others as well. Any subgroup of order 2 is embedded in a subgroup of order 2 and has a relative lz complement in the larger subgroup with 2 elements.

Proposition 13: Let G_n be the group of n-bit binary numbers with modulo 2 addition as the group operation. Let H be a subgroup of order Σ⁰*¹ and H its complement in G_n. Then for x, y ε H, x © y e H, and if x e H, and y e ÏÏ, χ © y = z e H.

Proof: H cannot be a subgroup since it does not contain the identity I = (O---O). By definition, if x, y e H, x © y e H.

Let z - x © y where x € H and y € H. If z e H , then y = z© x e H by the group property. This is a contradiction since ΗΠΗ = /.

So zeH. The number of elements in H and in H is p = 2^0-1. Each element or binary number in H can be written as the sum of p pairs of numbers belonging to

H. This gives p^ pairs from H to H.

The numbers in H which are sums of mixed pairs can be expressed in two ways considering order: p2 pairs in which the p numbers from H are matched with the p numbers from H. Another p2 p_a-j_{r 1S} generated by matching the p words from H with p words from H. This gives a total of 2p^ ways of expressing the mixed sums in H.

WO 93/03559

PCT/US92/06497

2115352

Overall, in G there are 2p words which can be expressed as (2p)^ = 4p2 pairs. The remaining p pairs are those where the sum of numbers from H is ? 2 taken. So far, 2p pairs correspond to H and p pairs to H. Since the two sets 2

H and H have the same number of elements, the remaining p pairs belong to H (i.e., x, y e H =^- x Q y € H). (Q.E.D.)

A substitution of the n-bit binary numbers G_n onto themselves can also be thought of as a transformation T, such that, TG_n = G_n if this is expressed by an additive array:

= Zi

Then the first column defines the transformation Tx_fc = z_fc. If T is linear,

T(*j © x_R) = Τχ^ © Tx_R.

Proposition 14: A maximal additive array with fixed identity defines a linear transformation.

Proof: A general row is © x_k = *_k__p«

Let T be the transformation mapping column 2 on column 3, Tx^ = ^xk._p·

Let \ © *j ⁵⁸ *r

T(x_k © = T_Xi = x^p. î

Tx_k 0 TXj = x_k_p ©Xj.p. ?

Since the array is an additive group by proposition 3, ^xk-p Θ Xj.p = (x_k © Xj) © (x_k.i © Xj-i) = Xi © ^xi-l ^{= x}i-p , and

T(x_k © Xj) = Tx_k© TXj.

This property is not generally true for one-to-one transformations on G_n. &lt;

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/G6497

<img file="CA2115063C_D0028.tif" />

Proposition 15: A transformation of the n-bit binary numbers onto themselves can be linear only if I - (00*··0) is a fixed point.

Proof: Without loss of generality, the n-bit binary numbers can be . arranged in order such that the successor to eacn is its image under tne trans· formation:

1* ‘k+1

Since T is linear, T(x_fc © _Xj) = Tx_fc © Txj = x_k+1 © x_j+1.

^xk © Xj = x, for some i in the set 1,.....m. If Xj - (, then

T(x_fc © Xj) = T(x_k © 1)= Tx_k = Tx_fc © Txj, which implies that (Q.E.D.) ^Txj ' ^xj + l = I

Proposition 16: A linear transformation of the n-bit binary numbers onto themselves can be represented as an additive array.

Proof: Without loss of generality, the n-bit numbers can be arranged in an order so that each is mapped onto its successor:

^xk ^xk+l

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

Λ /&gt;

î î ,’^Ί ; ’ h

-L -i. ‘J

By proposition 15, if T is linear, î = (0···0) is a fixed point. Initially, it is assumed that there are no cycles. Tx^ = x_k+p Since T is a linear transfor. mation, T(x_R 0 x) = Tx_k 0 Tx^. If χ_η. = © x^ , then

X_i+1 = Tx, = T(x_k © Xj) = Tx_k © TXj = x_k+1 © x_{j + 1}.

Let 2_k = ^xk 0 x_k i for each of the m = 2^n-i binary numbers other than

I = (0···0). There are m = 2ⁿ^ such equations. Either z_k takes on all values of the n-bit numbers except I, or there are duplicates. Suppose z_k = Zj for some k - j. Then x_R © x_k+1 = _Xj © x_j+1 and x, . _Xr Q _x. , ^_+i @ _x. _{+ i}

- a contradiction.

If there are cycles or invariant sets, each cycle can be written as above as a self-contained set and the same reasoning applied to each cycle. (Q.E.D.)

So far we have seen that all linear transformations on G_n are additive with fixed identity. Next we consider affine transformations which are nonlinear (at least to a mathematician). An affine transformation has the property tnat T(x 0 y) = Tx 0 Ty 0 C where C is some constant.

Proposition 17: A maximal additive array with a fixed point other than the identity defines an affine transformation.

Proof: It has already been shown tnat an additive array with some fixed number A can be obtained from an array with fixed I by adding the row A 0 A = I to each row in that array.

In the array with fixed I, Tx^ - \.ρ· The array with fixed A,

T'(\ 0 A) = x_k_p. Then, redesignating xfj = x_k © A, T'Xj = Tx_k = T(Xj © A).

Τ' (x © y) = T(x © y © A) = T(x © A ©y © A © A)

T‘ (x © y) = T(x © A) © T(y + A) + TA

T'(X © y) = T’X © T'y © C where C = TA. (Q.E.D.)

If Τ' is an arbitrary affine transformation, it can be written in terms of a linear transformation T as T'x = Tx 0 C. By proposition 16, T can be ι

ί &lt;

τ }

i »

I,,-.·

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497 represented as an additive array.

Defining A = T“^C, a corresponding additive array can be generated to represent T’ by adding the row A © A = I to each row in the array for T.

Proposition 18: If H is a subgroup of G_n&gt; the group of n-bit binary numbers, and T is a linear transformation or T'x - Tx Q TA with A e H, is an affine transformation on G_n, then TH and T'H are subgroups of G_nProof: Let G = TH. By propositions 15 and 16, T can be represented by an additive array with fixed identity. I e H, TI = I so IeG. Let x, yeH. Since H is an additive group x © y = z e H. Tx, Ty and Tz e G. By linearity Tz = T(x © y) = Tx © Ty c G, so G is closed under modulo 2 addition. For any x € G, x © x = I e G, so x is its own inverse and G is a group. In the affine case, TAeG and T’A = TA © TA = I, so HG. T'x ©T'y = Γ(χ © y © A) e G since x © y © A e H. (Q.E.D.)

Proposition 19: A maximal length linear or affine transformation is unbiased.

Proof: First of all, being of maximal length, the transformation has no cycles, other than its fixed point, and thus has no proper invariant set.

Let T be linear and consider a maximal subgroup H of G_n. Define two sets:

M « |x e H I Tx e H I N = { x e H I Tx € ïï Î

I &lt; Μ, ΙΉΝ = /and H = MUN.

I,f x, y « M, T(x © y) = Tx © Ty e H since T is linear and H is a group. Thus, x © y e M also. Since each x is a self-inverse, M is a subgroup, and N is its complement relative to H.

If x ε M and y e N, then z = x © y e H and, hence, is either in M or N. If z e M, then y = z © x ε M by its group property. Thus, z ε N.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

ί..·-,.

If x, y e N, Tx, Ty ε H, complement of a maximal subgroup H. By proposition 13, Tx θ Ty e H. By linearity T(x © y) e H. Since x, y e H, x © y e H. Since T{x © y) e H, so x, y e N =» x © y e M.

Since T has no proper invariant subset, TH * H and N * /, the empty set Select x c N and consider the group Q generated by x and M, Q c H. Q contains the complex x © M which includes all pairs of the form x © y where y e M.

Obviously, Me Q. Choose any z e N, where z * x. This is possible since J M j divides) H J = 2ⁿ^. So) n| &gt;_ 2. z = x © w for some w. Since z, x e H, a group, w e H also. Since x, z e N, w e M. Thus, any element of N or M is an element of Q. Therefore, Q = H and M is a maximal subgrou

2ⁿ“* and, thus, the order of the maximal subgroup Mis M N I = I H -I Μ I = —| H

D of H. H is of order

I I “ H .

I I = 2ⁿ2 ₌

Note: TM is a group andj TmJ - | M | .

Let T* be an affine transformation defined by T'x = Tx © TA, and C « TA. Again define two sets:

M* = 1 x e H Ν' = I x e H

T’x € Hj T’x € H I

Assume C ε H. If xcM‘, T’x = Tx © C e H. Thus Tx € H and Μ* £ M, If x e M, TxeH. T'x = Tx © C e H, so x e M', and M' = M. Since M’uN' = H and M'An* -X Ν' = N. From here, the proof proceeds as in the first part.

Now assume C*H. If x e M', T'x - Tx © CeH. Thus, Tx e H and M'£N. If xeN, Txe H. T'x = Tx © CcH, M' = N and, consequently, Ν' = M. In this case, M' is not a subgroup but, by the first part of the proof,

Μ* I « I N I ^a“ I Η I . Since H is maximal, the relative complement H is the total complement, so that C e H or C e H.

(Q.E.D.)

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497 ι

ί ί - JL i-ί ό”·?/ v c*

If T is linear, the proof holds for any subgroup. If H is of order it is isomorphic to the group of n-1 bit binary numbers. G_p^ has a ig of H, The sai ^Gn Γ This leads to a nested sequence of subgroups relative complement in G_n consisting of H, The same process can be applied to ^Gn ^{3 G}n-1 =&gt; '·· ^G1 ~ ^GÛ ⁼ I ¹ I in which each G^ is mapped by T half onto G^^j and half onto G^.p

Note: This sequence of suogroups is not unique, as we can begin with several candidates for ., etc.

n-l

We have seen that any additive array produces unbiased substitutions or transformations. Next, we consider the necessary properties for a transformation or substitution to be unbiased in the sense defined here.

Proposition 20: G_n has m = 2 -1 maximal subgroups.

Proof: G_n is generated by any n independent n-bit numbers. Let

J Xp Xj, ·*·· , x_n I be such a set. Any subset of n-1 of the generators will generate a maximal subset. I ⁿ \^s n maximal subgroups will be generated this \n-l/ way. Let this collection of maximal suogroups be designated Hp Hp ···* , H_nwhere H- is generated by { Xp ··· , x^p x_i+p ·· , *_n [ , that is, by all except x.. Then x^ € for each i &lt; n, and x^ e Hj for i * j.

Next, one can define an operation + between maximal subgroups as:

^Hk ^{s H}i ^{+ H}j ^{æ {H}i ^{Π H}p ^{u (H}i^{n H}?

n-1

Η. Π H;

I J since it is a union of disjoint sets and = 2^Π\ Let ^xc - *_a © where x_a, x_fa &lt; H_fc. There are three possibili ties:

H, = 2 n-2

1' ^Xa» ^xb ^{e H}i &gt; ^ien x_c € Π Hj since π Hj is a group.

SUBSTITUTE SHEET

<img file="CA2115063C_D0029.tif" />

WO 93/03559 PCT/US92/06497

I , ·'

2. x_a, x_K c Η, ΠΗ_η then x„ € Η, Π H- by proposition 13.

a D 1 J C « J

3. x. e Η, Π H- and x_h e H_s ΓΊ H , then x_ e Η, Π H by a i j d i j c ί j proposition 13.

In each case χθ e H_k, obviously I e H_k, so H_k is also a maximal subgroup.

To each maximal subgroup generated in this fashion, we can associate ^xk ^{= x}i © ^xj ’ That ^{is&gt; x}k ^{the suni} °f 9^{ener3rors tïie set} j x_? x₂, ·*· , x_n } which belong to Clearly, the maximal subgroups generated this way total m and are in one-to-one correspondence to the n-bit numbers.

Assume there is some maximal subgroup Ηθ which was not generated this way. Let the q numbers { x_a, χθ, ··· { € Ηθ be the maximal such subset of the generators { Xj, x₂, ... , x„ } . x_Q = x_a 0 x_b 0 ··· - x_Q = x_k for some previously generated. Since the generators produce unique sums, then j x_a, x_b, ·· J c Η^. There are p remaining generators J x^, Xg ί * ^Hoⁿ where p + q = n. Then (Ηθη h^) U (Ηθη H^) is a maximal subgroup. This is not possible unless H = h. . (Q.E.D.) u x

There is an interesting relationship between the maximal subgroups and the numbers. G_n is trivially a maximal subgroup of itself. G_n + Η_Ί· ₌ + G_n = H^ and + = G_n. The collection of maximal subgroups £= | G_n, ··· ,

H_n, Hj + H₂, ·· ( form a group under the operation ”+ with G_n acting as tne identity. G is isomorphic to G_n under the mapping x^—* defined above.

The above proof is a little complicated, but it illustrates something of the structure of the subgroups. The same result can be obtained by more elementary means.

Each set of n-1 independent elements generates a maximal subgroup of order 2^0-1. The number of distinct sets of independent (n-l)-tuples, from proposition 12, is Q (n, n-1). However, different (n-l)-tuples may generate the same subgroup. The subgroup of order n-1 is isomorphic to the group of n-1 oit numbers. This latter group has Q(n-l) independent (n-1 )-tuples. Thus, the l···

F

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0030.tif" />

<img file="CA2115063C_D0031.tif" />

group of n-1 bit numbers can be generated by Q(n-l) sets of generators, and each maximal subgroup is generated Q(n-l) times using all possible independent (n-l)-tuples. So the number of distinct maximal subgroups of G_R is:

Qin, n-1)

R(n) = Q(n-l) n-2 η (2ⁿ - 2^J) (n-1)! j = 0 (n-1)!

n-2

<img file="CA2115063C_D0032.tif" />

₍₂n-l

2^j)

<img file="CA2115063C_D0033.tif" />

2ⁿ - 2^J2^n_1 - 2^

2ⁿ - 1 = m

Corollary: Each number other than the identity will occur in . maximal subgroups and in ...·Η,·.ΐΑ. complements.

Proof: Since there are m maximal subgroups each number will appear m times, either in a maximal subgroup or its complement. The identity I will appear m times in the maximal subgroups but never in a complement. There are remaining places for the non-identity numbers to appear in maximal subgroups.and ”1 places in the complements. Thus, by symmetry, each 2 non-identity number will appear in maximal subgroups and in

2 complements. (Q.E.D.)

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

Ρ ί ί £ Λ i Α.

Proposition 21: If Ηρ Ηρ are any three dependent maximal subgroups, then G_n ~ + Hj + H_k.

— m+1

Proof: Each and each have-numbers. Also each Π Hp — _ _ m+1

Η. Π H₄, and rb A H&lt; have-numbers. The set of distinct numbers in H, u H.

^{1 J 1} _J _ 4 3(m+l) ¹ J is the set (H&lt; fiHj u (H&lt; HHJ U (H. û H.) and consists of-numbers. The . ' J * J ¹ J 4 m+1 — — missing - numbers are those contained in Η. n H_v. = H, + H. = (H^n H.) i J x ί j » j

UtH^OHj). So G_n = H_i U Hj U and G_n = H_i + Hj + H_k. (Q.E.D)

Corollary: The set of any three dependent numbers { x·, Xp x_k [ , none of which is I, contain at least one number from each of the m maximal subgroups.

Proof: In the proof of proposition 20, for a set of generators of G_n, { Xp x₂, ” , ^xn } , a set of maximal subgroups was generated. The generators can be written in terms of these subgroups:

j ^χι I = H₁n h₂ n..... n H_n

I ^x2 P ^Hiⁿ⁷2 ⁿ..... ^{n H}n i ^xn I - ^η1^Πη2 ^A.....° %

I ^Hk|=KI = 2ⁿ~\, I ^Hj^nHkl ⁼ l^ïïj^nïïJ ⁼ l^Hj^nïïkl⁼|^îïj^r,Hkl· 2ⁿ*².

By induction these n-fold intersections have 2° = 1 elements and are singleton sets. As an example, take Xp x₂, and x_k = 0 x₂. K_k = Hj + H₂ is a dependent set in the sense of proposition 20, x_k is the number associated with H_k, and by proposition 21, G_n = H| + H₂ + H_k. By proposition 13, of course, k |l, 2, ··· , n | . Any maximal subgroup is of the form H^· where i ranges over some subset of j 1, 2, , n | . If i * 1, 2, then

I ^xp *2’ ^xk I ^e Σ ^Hi· Otherwise, there are three possible cases:

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/Û6497

<td></td><td> ? 11 4» 1. x u</td><td></td><td> Jf</td><td> 74</td>

<td> 1,</td><td> i *</td><td> 1,</td><td> = 2</td><td>^X1 ^ε Σ H_i</td>

<td> 2,</td><td> i =</td><td> 1,</td><td> * 2</td><td> X₂ e Σ H_i</td>

<td> 3,</td><td> i -</td><td> 1,</td><td> = 2</td><td> X_k e Σ H_i (Q.E.D.)</td>

<td colspan="4"> This is different from the of vectors spans the space.</td><td> situation with vector spaces where an independent set</td>

Proposition 22: A one-to-one transformation of G_n onto itself is unbiased, if and only if, it can be represented by a replicative array.

Proof : As shown in the introduction, any transformation TG_n—*G_n, where Tx^ - Z-, can be written in the form y. Q ^xi ^{s 2}i· This can be represented by the addition modulo 2 of two column matrices to obtain a third:

<img file="CA2115063C_D0034.tif" />

The y^ matrix represents the transformation T. Each matrix will have 2ⁿentries. For the x^ and z^ matrices, each of the 2ⁿ n-bit binary numbers will appear exactly once since T is 1 to 1 onto it. Assume that T is unbiased and that the y^ matrix may have some of the n-bit numbers repeated so that the 2ⁿ numbers are not all distinct.

There are m = 2ⁿ-l maximal subgroups Hp h₂, ··· , H_m. Since T is unbiased, it will map each such that

<td></td><td></td><td></td><td></td><td> 1</td><td></td>

<td> τ^η H_i</td><td> s</td><td> TH_i Π</td><td> a</td><td> 2</td><td></td>

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

From proposition 13, we can arrange the matrices in blocks that correspond to the maximal subgroup and its complement

H,

H.

H.

H.

H.

^Hi ? Ή -Λ Π Ρ *’ &amp; X x,) V υ «χ

H.

Since T is unbiased, each of the four blocks must consist of 2ⁿ“^ numbers. The n-bit numbers may be designated y_Q = I, y*. y?, ···· , y_p in the y matrix, and each will appear with some multiplicity p. &gt; Q. Let a.-j = 1 if y - e H-j and a^j = 0 if y^ e . Clearly a^_Q = l for all i since the identity I belongs to each subgroup. For each and the following equations hold:

m+1 ' ’i i ^: έ _i d - ^aij )Pj m+1

These two sets of equations are consistent since

V:·.

Pn + Σ Pj = Σ Pj = m + 1 j = l ^J j = o ^J

AtlRRTITVITR RWFcrr

WO 93/03559

PCT/US92/06497

The m equations corresponding to the m maximal subgroups can be written in matrix form:

η ,5 4 ii I. ie. ·? ÏT*)-iB

12 lm

Pi m+1 m+1 ^Q22

2m

P2 m+1 'ml ^dm2 mm

<img file="CA2115063C_D0035.tif" />

Using the determinant of the m x m matrix on the left, we can use Cramer's rule to solve for the pp For example,

<td> m+1</td><td></td><td></td><td></td><td></td>

<td> 2</td><td> Po</td><td>^a12</td><td>^a13 ··*'</td><td>^alm</td>

<td> m+1</td><td></td><td></td><td></td><td></td>

<td> 2 •</td><td> Po</td><td> ^2</td><td>^a23 ....</td><td>^a2m</td>

<td> • m+1</td><td></td><td></td><td> *</td><td> •</td>

<td> 2</td><td> -Po</td><td>^am2</td><td>^am3 · · ‘ ·</td><td>^amm</td>

<td>^all</td><td></td><td>^a12</td><td>^a13 ····</td><td>^alm</td>

<td>^a21</td><td></td><td>^a22 •</td><td>^a23 · * ' ’ •</td><td>^a2m</td>

<td> t ^aml</td><td></td><td>^am2</td><td>^am3 · · ·</td><td> * c mm</td>

SUBSTITUTE SHEET wo 93/03559

PCT/US92/06497

2115853

From the corollary to proposition 20, each row of the determinant in the denomi,, m-1 . m+1 nator will have— entries which are 1 and-which are 0. Adding columns 2

2 .

through m to column 1 will not change the value of the determinant, so that:

m+1

-p, ‘13 lm m+1

-p, ‘22

2m m+1 “^po ^am2 ^am3 ···· ^amm

Pi = m-1 — a₁₂ a₁₃ .... a_lm m-1 — a₂₂ a₂₃ .... a_2m m-1 ^am2 ^am3 ’ ’ * ’ ^amm

Factoring out the constant first column in each determinant and noting that the same result holds for the ith column, yields:

m+1

T”»

p.· --— for 1 &lt; 1 &lt; m.

¹ ra-1

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497 one fixed word, contrary to the definition m+1 o then P. =—- which is not an integer.

¹ m-1

P_o &lt; 1 since p_Q.&gt; 1 implies more than of an unbiased substitution. If p_Q =

V Ή ην À .à,W-£

The only remaining posibility is p_Q - 1, in which case:

πηΊ 2 ^-1

--- - f_or m-1

Thus if the transformation is unbiased, all the = 1 which, by definition, is a replicative array.

NOTE: One does not need to appeal to the definition of an unbiased substitution to restrict the value of p . If p_Q &gt; 2, than o &lt; &lt; 1 which is also impossible.

Assume now that the transformation is replicative. Consider any arbitrary maximal subgroup H. Each column matrix will have 2ⁿ~* entries in H and 2ⁿ'^ entries in H. The matrices can be written in blocks, as follows, using proposition 13:

<img file="CA2115063C_D0036.tif" />

<img file="CA2115063C_D0037.tif" />

<img file="CA2115063C_D0038.tif" />

where b entries from H and 2ⁿ’^ -b entries from H in the x matrix are added to the 2^n-1 entries from H in the y matrix. This yields a total of 2b entries from H and 2ⁿ - 2b entries from H in the z matrix. Since the transformation is replicative, the z column matrix has | H | » 2^n-1 entries from K. Thus 2b = 2-¹ and b » 2ⁿ'^z = 2^n_1 -b. So | ΤΗ Π H | = | fFTΓΊ ΤΓ | = 2ⁿ“² and T is unbiased.

Q.E.D.

I.· 1 · }

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

Proposition 14 is really included in proposition 22, but the proof of the former reveals more about the structure of the transformations and the additional property resulting from linearity.

*

Thus, any unbiased substitution of the n-bit binary numbers will fall into one of three categories:

1. It is replicative but not additive. Its powers are in general not replicative. It is a non-linear transformation which is also not affine.

2. It is additive with fixed point other than the identity. Its powers are also additive. This group of transformations are all affine.

3. It is additive with the identity fixed. Its powers are also additive. This group of transformations are all linear. They have the further property that they split all subgroups and not just the maximal ones.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

NON-LINEAR DYNAMIC SUBSTITUTION DEVICES AS MECHANISMS FOR

BLOCK SUBSTITUTIONS

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0039.tif" />

$

TABLE OF CONTENTS

I

I t

j &gt;

î ί

I i

i

Section Title

1. INTRODUCTION.......................................

2. BACKGROUND WORK WITH LINEAR AND AFFINE

ORTHOMORPHISMS..................................

3. NONLINEAR ORTHOMORPHISMS AND DYNAMIC

SUBSTITUTION DEVICES (DSD).......................

3-1 General Considerations....................

3-2 Conversion of Linear Orthomorphisms.......

3-3 Nonlinearization Summary..................

3-4 Application of Nonlinearization Techniques ...

3-5 Selection of Equations for Nonlinearization ...

3- 6 Nonlinearization Techniques Summary.......

4. MEASURES OF CRYPTOGRAPHIC FREEDOM FROM BIAS .

4- 1 Avalanching and Bit Independence...........

4-2 Other Criteria for Lack of Bias.................

4-3 Applications to Orthomorphisms..............

REFERENCES......................................................

APPENDIX.........................................................

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0040.tif" />

1. INTRODUCTION

The term Dynamic Substitution Device (DSD) was coined at Teledyne Electronics to designate a block substitution device, or S-box, in which the mappings or substitutions of clear text blocks of binary numbers to encrypted blocks of binary numbers, or vice versa, are accomplished by means of so-called orthomorphisms.

Any block substitution can be described in terms of look-up tables, permutations, or Boolean functions. A look-up table is simply a tabulation of corresponding clear text and cipher text pairs. A permutation is an orderly way of describing a look-up table and has the advantage of showing any cycles or subsets of numbers mapped onto themselves. Permutations also have some algebraic properties which can be considered in the design of S-boxes. Boolean functions (commonly used) are functions of n-bit binary numbers or blocks whose dependent variables are individual bits of another n-bit number. Thus, n Boolean functions are needed to describe a block substitution for n-bit numbers.

Orthomorphisms are another method of describing block substitutions, albeit a special class of them because most block substitutions are not orthomorphisms. As shown in ref. 2, there are many orthomorphisms existing. When they are described by look-up tables or Boolean functions, their special properties tend to be obscured.

Letting G_n be the group of n-bit binary numbers under coordinatewise addition modulo 2 (denoted by the symbol ©), an orthomorphism of G_n is a 1 to 1 mapping R:G_n-*G_n such that (x Θ7?(χ))_χε£_π = G_n. This is equivalent to pairing each n-bit binary number with another in such a way that in the collection of 2ⁿ pairs, each number appears exactly once in each of the two sets of numbers and in such a way that the sums modulo 2 of the pairs is again G_n. (It is not obvious that this can ever be done.) 'This constitutes a bijective mapping with a single fixed point since some number must be added modulo 2 to the all-zero additive identity.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

2. BACKGROUND WORK WITH LINEAR AND AFFINE ORTHOMORPHISMS

Linear (automorphic) and affine orthomorphisms are described in some detail in refs. 3 and 4. A linear orthomorphism can be represented by a set of 2⁷¹ equations, for block size n, where each is an n-bit binary number:

Θ Φ Θ = Θ

Xm θ *1 *1 Θ X₂ = X2-p ^è-1 θ Xk “ ^xk-p θ Xfn - Xm-p where m = 2ⁿ - 1 and p is an integer determined by the generating function but independent of the initial conditions or key variable {xj, x₂, *·» x_nJ- This set of equations can be thought of as a set of 2ⁿ vectors on a three-dimensional space. These vectors can be added componentwise modulo 2.

In the linear case, the set of vectors forms an additive group, but this is both a strength and a weakness. Knowing any set of n linearly independent vectors (equations) one could construct the remaining equations from the group property. As in every block substitution, the mapping can be represented by a permutation. In this case, there are three permutations depending on which pair of columns is chosen. As a convention, we typically consider the mapping to be from column 1, x*.! to column 3, x^._p. The compensating quality described in refs. 3 and 4 is that if column I is shifted with respect to column 2, column 3 is also shifted by a corresponding amount and represents a new linear orthomorphism.

The permutation representing the new orthomorphism is a power of the permutation representing the original orthomorphism. In ref. 4, it is shown that these permutations form a cyclic permutation group of order 2ⁿ - 1 which is transitive, i.e., each number other than the fixed number is mapped on every other number by the family of orthomorphisms.

The affine orthomorphisms can be converted to or derived from linear orthomorphisms by adding vectorially to each of the 2ⁿ original equations an equation of the form S © S = Θ where S is a fixed number.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

211

Λ P ^r\ ' f ft *5, «&gt; ν -e·¹

In practice, a linear DSD has been used with a continual change of shift position, or equivalently, a different member of the permutation group. Employed in this way, the S-box is nonlinear.

There is another aspect to linearity us. nonlinearity, namely, the level at which it is described. Orthomorphic block substitutions have been derived by linear recursive generating functions applied to a maximal set of linearly independent n-bit numbers. The mappings of numbers from one column to another in the set of equations is also linear under the operation of modulo 2 addition bitwise; however, if the same mapping is now considered under the operation modulo m, where m = 2ⁿ -1, the mappings, in general, are nonlinear. Here, linearity is defined by the property of a mapping F, such that F(ax + by) = aFx + bFy for all vectors x,y, and scalars α, ά.

In ref. 1, S-boxes or mappings are defined in terms of Boolean functions, i.e., a set of n functions which map an n-bit number (clear text) to one bit of an n-bit (cipher text) number. Because orthomorphisms are block substitutions, although of a special type, they can also be represented this way. In ref. 1, it is proven that a sufficient condition for the mapping or block substitution to be nonlinear at the integer level (presumably under modulo m addition) is that all n Boolean functions (at the bit level) be nonlinear. This is not claimed to be a necessary condition. In the appendix, an example is given of a linear orthomorphism (under modulo 2 addition) with linear Boolean functions which is nonlinear at the integer level modulo nt.

3. NONLINEAR ORTHOMORPHISMS &amp; DYNAMIC SUBSTITUTION DEVICES

3.1 General-Considerations

In view of the comments in the last section on different definitions of j nonlinearity, this section is concerned specifically with block substitutions using nonlinear orthomorphisms in the sense that they are nonlinear mappings from G_nonto G_n under the operation of bitwise addition modulo 2. The motivation to look at :

nonlinear orthomorphisms is twofold: r '

a. There are many more nonlinear than linear orthomorphisms. jb. Nonlinear orthomorphisms should be more resistant to cryptanalysis ;

than the linear or affine versions because of the lack of group symmetries.

SUBSTITUTE SHEET

WO 93/03559

PCÏ7US92/06497

<img file="CA2115063C_D0041.tif" />

There is a trade-off, however, in that the nonlinear orthomorphisms do not generate an automorphism group and the corresponding dynamic substitution devices no longer can change substitutions by shifting.

J &lt;3 t) .

<img file="CA2115063C_D0042.tif" />

I OUTPUT Y OUTPUT

Figure 1.

The first problem is to find a way of routinely generating nonlinear orthomorphisms. In one approach, it is tempting to try a variation of the process used in ref. 4, prop. 1, relaxing the requirement that successive sets of n numbers in each column be linearly independent, while constructing a set of equations to

<td rowspan="2"> represent an orthomorphism, array of equations as follows: *1</td><td colspan="3"> Select n linearly independent numbers, and start the</td>

<td> © ©</td><td> X, X₂</td><td>^z2</td>

<td>^xn-l</td><td> ©</td><td>^xn ~</td><td>^zn</td>

<td>^xn</td><td> ©</td><td></td><td></td>

<td colspan="3"> The choice of the linearly independent set (x_lt ·</td><td> ··, x_n) specifies n - 1 equations of the</td>

budding orthomorphism. Choosing a candidate for x_n+1( such that (*2* · and

U2» ^&amp;Γθ linearly independent, yields a linear or affine orthomorphism if successive steps can continue to x_m. If the restriction on linear independence is removed, the only restriction is that neither x_n+1 nor z_n+1 duplicate a predecessor.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

2115582

The problem experienced with this procedure is that one almost always runs out of choices before reaching x_m where m = 2ⁿ - 1, Without loss of generality, one can assume that the fixed point is given by the equation Θ θ Θ = Θ. To avoid Tengthy cut and try procedures, some additional guidance is needed.

Another approach is to convert a linear orthomorphism to a nonlinear one by taking the set of equations defining the linear orthomorphism and permuting the numbers in two columns in such a manner that the third column of sums is unchanged. In the next section, this approach will be explored.

3.2 Conversion of Linear Orthomorphisms to Nonlinear

Any linear orthomorphism can be expressed as an additive group of equations which can be treated as vectors and added componentwise modulo 2 to obtain another equation (vector) in the same array or group of equations representing the orthomorphic block substitution. Omitting the identity equation, Θ θ Θ = Θ, the orthomorphism can be written:

^xm θ *1 ⁼ *1 -p ^X1 θ ^x2 = ^x2-p

Xj. 1 Θ Xj = Xj.p ^χζπ·1 θ ^{= x}rtt*p

If numbers in columns 1 and 2 could be rearranged within themselves so that the sums in column 3 are preserved, a nonlinear orthomorphism would result. Since the orthomorphism is based on the relationship between three columns, it is * intuitively tempting to seek some relationship among triples of rows. Because of the group structure, the vector sum of the first three equations will be another equation which already occurs at position ç, where q is given by:

SUBSTITUTE SHEET

WO 93/03559 PCT/US92/06497 L.

<img file="CA2115063C_D0043.tif" />

<td> xi © X2</td><td> ©</td><td>^x3</td><td> =</td><td>^xg</td>

<td>^x2-p</td><td> ©</td><td>^x3</td><td> =</td><td>^XQ</td>

<td>^x3-(p+l)</td><td> ©</td><td> *3</td><td> =</td><td> Xq</td>

<td colspan="4"> This last equation is from the array representing a shift of p</td><td> + 1 in column 1 or the</td>

<td> (p + l)st power of the basic permutation. Thus: ^3-&lt;ρ+1) ®</td><td> *3</td><td>_lrr</td><td colspan="2">^X3-P(p+1)</td>

and q — 3 - P(p+i) modulo m where P(p₊i) is the shift in column 3 corresponding to a shift of p + 1 in column 1. (See ref. 4.)

Without, loss of generality, we take the first j rows in the linear orthomorphic array and take successive triple sums of adjacent rows. The first of these will be:

(x_m©X!©x₂) © (*1©*2®^X3) = (xi-p ©X2-p ©*3-p) which is the row in the qth position in the array of equations and can be written:

%q*l © Xq ~ ^xQ-p

The remaining rows generated in this way are:

Xq © Xç+l - ^xç+l-p ® ^¢+/-3 - ^xq+j-3-p for a total of j - 2 adjacent rows in the original array separated by q - j rows from the set of j equations. The second group of J- 2 rows lend themselves to a natural transformation by cancelling the common numbers in columns 1 and 2, yielding:

® X3 ⁼ Χ_ρ.ρ

Xj θ X^ = ^ç+1-p

Xj-3 © Xj = ^xQ+&gt;.3-p

In these y - 2 modified rows, column 1 duplicates all but Xj.₂ and xj.j in column 1 of the first set and all but xj and X2 from column 2. If this process is to succeed, a mechanism must be found to replace the duplicates in the first set with j - 2 original numbers in columns 1 and 2 of the second set. The first question, however, is whether or not this is possible.

SUBSTITUTE SHEET

PCT/US92/06497

<img file="CA2115063C_D0044.tif" />

J

WO 93/03559 kit

Let S be the set of numbers in column 1 of the first j equations and T be the corresponding set of numbers in column 2. These sets must be replaced, respectively, by the sets S’ and Τ' consisting of the original numbers in columns Γ and 2 of the second set of/ - 2 equations plus those two numbers left over in each of S and T.

S = (x_m) Xp ··’, X/.i) —» S = fcj-2, ^7-P ^ç-l» ^+7.4)

T = {xp ^x2 , ' , *7} ·—&gt; Τ' = {Xp X₂* Xqi ^ç+7.3)

The conditions on transforming from one set to another are interrelated. If ε S and x^ &gt; X£ ε S , then, x^₊1 ε T and x^₊1 &gt; 1 ₊j ε 7¹. x^ Φ ~ +1 -p = ^xk®\ Λ+1&gt; so thatx’^₊₁ =x^ Θχ^₊ι Θχ'^.

Let x_m —» x'_m ε S', then, from T, Xj —&gt; x_m Φ *2 Θ x'_m = Xj ε Τ'. There is only

I t f one possible choice of x_m z S' so that X; ε Τ', i.e., x_m = Xç-i = x_m θχι ® x₂ , in which case, Xj -4 xj = x₂.

Similarly, at the other end, xj.i e S and xy_i —&gt; xy.j. ε S'. xj e T and xj -+ X7.1 θ xj θ xj-i = xj ε Τ'. Again, there is only one possible choice for xf^ = xj.₂ so • I that xjz Τ', namely, xj = xy.₂ θ xy.i Θ xj = ^xq+j-3 ε 7”. Thus, the first and last modified rows of the first set of j equations are uniquely specified:

x^®xi=xp_p becomes x_ç.i©x₂=xp_p and:

^xj-l®^xj = ^xj-p becomes X;.₂ θ x_q+j.3 = Xy.p.

Next, consider the second original equation:

*1 ®X₂=X₂._p » » * » xi -+ xi ε S’. xi *x«.i orx;.₂ since these have been used. x₂ -» x₂^ε Τ' where Χ₂=ΧιΦχ₂ΦΧι

If Xl ^{— x}q* Xg+P ^xq+j‘4&gt; case, x₂ = ^xi ® ^x2 ®^xj-i · e S.

In that ifj = 3 ifj = 4 if J &gt; 4

I , then, x₂ T. So, the only possibility is xj = xy.i , J&gt;3:

I I

Xl=*2 and X₂=X! X₂©Xi=X2-p.

I (

Xr=x₃ and x₂ = x_ç x₃©x_&lt;7=x₂._p.

χ₂έ T .

If J = 4, there is one more equation of the first set of four to be modified: the third. Because j = 4, S’ = (x₂»X3»*ç.p*ç) and Τ' = (χρχ₂,χ_ρ(Χρ+ι). The only unused pair is x_q ε S' and xi ε T. Fortunately, x_q Θ xi = £3.^,, and the transformation is complete.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

3.3 Nonlinearizaîion Summary

Nonlinearization by taking sums of consecutive triples of rows works, if and only if, a set of three or four consecutive rows is used. If three consecutive rows are selected, the result is:

<img file="CA2115063C_D0045.tif" />

<td> 1.</td><td>^xm</td><td colspan="2"> Original © Xj</td><td>^{= x}l-p</td><td>^xq-l</td><td colspan="2"> Modified Φ x₂</td><td> = *l-p</td>

<td> 2.</td><td>^X1</td><td> Φ</td><td>^x2</td><td> = ^X2-_P</td><td>^x2</td><td> Φ</td><td> *1</td><td> = ^x2-p</td>

<td> 3.</td><td>^x2</td><td> Φ</td><td>^x3</td><td> = ^x3-p</td><td> *1</td><td> Φ</td><td>^xq</td><td> ~ ^x3-p</td>

<td> 9</td><td></td><td> Φ</td><td> Xq</td><td> ~ ^XQ-P</td><td></td><td> Φ</td><td>^x3</td><td> = Xq.p</td>

The modification can be obtained by adding vectorially to each of the four rows: (xj Φ x₂) © (*i ® *2^ = ®

If four consecutive rows are selected, the result is:

Original Modified

<td> 1.</td><td>^xm</td><td> Θ</td><td> *1</td><td> - ^χ1φ</td><td>^xq-l</td><td> ©</td><td>^x2</td><td> = ^xl-p</td>

<td> 2.</td><td>^X1</td><td> Φ</td><td> *2</td><td>^{= χ}2φ</td><td> X3</td><td> ©</td><td> Xq</td><td>^{= x}2-p</td>

<td> 3.</td><td>^x2</td><td> Φ</td><td> *3</td><td> = ^χ3φ</td><td> Xq</td><td> ©</td><td>^X1</td><td> = ^x3-p</td>

<td> 4.</td><td>^x3</td><td> Φ</td><td> x₄</td><td> ^^χ4φ</td><td>^x2</td><td> ©</td><td>^xq+l</td><td> = X₄.p</td>

<td> 9</td><td> Xq-l</td><td> Φ</td><td> Xq</td><td> -^xq-p</td><td>^xm</td><td> ©</td><td>^x3</td><td> = ^xq-p</td>

<td colspan="2"> 9+1 x,</td><td> Φ</td><td>^xq+l</td><td>^{= x}ç+l-p</td><td> *1</td><td> ©</td><td>^x4</td><td>^{= X}Q+1</td>

The modification can be obtained by adding vectorially:

to rows land q (Xi Φχ₂) Φ (xj Φχ₂) = Θ to rows 2 and 3 (χχ © x₃) Φ (xj Φ x₃) = Θ to rows 4 and q + 1 (x₂ Φ x₃) Φ (x₂ Φ x₃) = Θ

3.4 Application plIMnearizalion Techniques

It is often tempting to try to speak of levels of nonlinearity as if such levels were measurable quantities. Somehow, piecewise linear functions seem less nonlinear than transcendental functions. In cryptography, one refers to the Hamming distance of nonlinear Boolean functions from linear ones. While linearity is well defined, and nonlinear functions are simply everything left over when the linear, and perhaps affine functions are deleted, in what follows we will succumb to the tendency to ascribe measurability to levels of nonlinearity.

In the last section, two means were described to nonlinearize four or six rows at a time of an arbitrary linear orthomorphism. Because those methods could be applied, starting with any row in the orthomorphic array, each could yield 2ⁿ - 1 different, nonlinear orthomorphisms from one linear orthomorphism; however, they &lt;51 ιηςτιτι ι-re esuccrr

WO 93/03559

PCT/US92/06497

211506

L·' would not be very nonlinear in the sense that for large zi, a big chunk of the original array of equations would be left intact. So it is natural to use one orboth of these processes repeatedly. The limitation, short of running out of rows, is having chunks of rows overlap. The fraction of original rows, modified, might be considered a measure of nonlinearity, so the next question is how to select efficiently clumps of non-overlapping rows.

3.5. Selection oi Rows or Equations for Nonlinearizaîion

There are many ways to choose sets of triples or quadruples of consecutive equations for this nonlinearization process. The only essential criterion is that no rows derived as triple sums from some triple or quadruple sets overlap with another triple or quadruple set. In addition to this, it seems obvious that as many rows as possible from the linear orthomorphism be modified and with a reasonably uniform distribution so as to avoid any piecewise linear portions in the new orthomorphism. First, consider the case in which ni = 2ⁿ - 1 is a composite number. Let d be a factor of zn. From the linear orthomorphisms, select rows number 1, 2, 3 and 4 along with the corresponding sum row's q and q + 1. We can then select successive sextuples of rows to be modified as in the preceding section. The row numbers of these successive sextuples will be:

<td> 1</td><td> 2</td><td> 3</td><td> 4</td><td> 9</td><td> 9 + 1</td>

<td> 1 +d</td><td> 2 + d</td><td> 3 + d</td><td> 4 + d</td><td> q + d</td><td> q + 1 + d</td>

+ ad (\ + ad where a takes on successive values 0, 1, 2, — . This process can terminate in two ways. First of all, one of the equations in a quadruple set may be duplicated in another set, i.e., overlapping quadruplets and the same may happen between the sets of equations which are the triple sums. This will occur when for some integer a:

+ ad_t 2 + ad_r 3 + ad or 4 + ad ξ 1, 2, 3 or 4 modulo m ρ + ad or ç + 1 + ad s q or q + 1 modulo zn.

This is equivalent to:

ad s 0, ±1, ±2 or ±3 modulo zn.

SUBSTITUTE SHEET

PCT/US92/06497

<img file="CA2115063C_D0046.tif" />

WO 93/03559

The minimum separation between successive initial rows, Le., 1 and 1 + d, must be at at least 4 for quadruples. Since m = 2ⁿ - 1 is odd, and d divides m, d is also odd and, thus, d &gt; 5. this also means that ad έ ±1, ±2, ±3 modulo m.

The second means of potential overlap is when:

1, 2, 3, or 4 h q + ad or q + 1 + ad modulo m 1 + cd, 2 + ad, 3 + ad, or 4 + ad = q or q + 1 modulo m.

This is equivalent to:

ad s ±ρ, ±(q - 1), ±(&lt;? - 2), ±(q - 3), or ±(ç - 4) modulo m.

To avoid this, d must be relatively prime to &lt;?, q - 4; however, one of these numbers must be a multiple of 5 so that we require d £ 7. If triples rather than quadruples of rows are selected, then the conditions ad έ ±q or ±(q - 4) are eliminated. In that case, d &gt; 5 satisfies the conditions above. (Note: All integers here are positive, so the condition ad έ - q modulo m , etc, means ad é bm - q. Since d divides m, if it is relatively prime to q, it must also be relatively prime to bm - q for any integer ά.)

3.5 Nonlinearization Technioues Summary

If m = 2ⁿ - 1 is not a prime, seek a factor d of m, relatively prime to ç, ç - 1, ···', q - 4 to space successive quadruples of equations (relatively prime to q - 1, ç - 2, q - 3 to space successive triples of equations) for the nonlinearization process.

When such a number d can be found, it leads a uniformly spaced, dense set of equations in the linear array for nonlinearization. Some examples are given in the appendix.

3.6 Other Selections ol Rows

When the above method does not appear to be rewarding, another obvious possibility is to take successive quadruples of rows, defined by a triple and its sum, in which the first row of a subsequent quadruple follows immediately after the last row (triple sum) of the previous quadruple. For example:

&lt;7+1 &lt;7 + 2 bq + 1 bq + 2 bq + 3 (ά+ l)q

SUBSTITUTE SHEET

PCT/US92/06497

WO 93/03559

2115962

This process terminates when any one of three conditions occurs:

1. bq s 0, ±1, ±2 modulo m

2. (5 - l)ç == -1, -2, -3 modulo m

3. (ό + 1) s 1, 2, 3 modulo m

If q is a prime, or at least not a divisor of ni ±1, m ±2, or m ±3, this process can yield a large number of nonoverlapping quadruples for nonlinearization. This process can also be done with sextuples of rows, but the conditions for termination are more complex.

In general, these two methods, under proper conditions, can select nonoverlapping sets of equations from the linear orthomorphism for nonlinearization. Only a relatively small number of equations, evenly distributed, are left unmodified.

There are many other ways to go about this process, e.g., fitting sets of quadruples and sextuples of rows together without overlapping. This becomes a topological problem. The important point is that it is possible in this way to generate nonlinear orthomorphisms which are not piecewise linear.

4. MEASURES OF CRYPTOGRAPHIC BIAS

The author is unaware of any generally accepted measurable standard for freedom from bias in block substitutions of binary numbers. Two widely used criteria are avalanching (good or strict) and bit independence. In what follows, two other possible criteria are suggested: (1) balance, which is related to properties of the n-bit binary numbers as an algebraic group, and (2) transitivity, which is a property of certain permutation groups that in not commonly applied to block substitutions. Of the four, it appears to be possible to meet, at most, three criteria simultaneously.

4,1 Avalanching and Bit Independence

The strict avalanche criterion (SAC) is defined as the property that changing the zth bit in the input block causes a change in theyth bit in the output block one half of the time for all 1 &lt; i, j &lt;n, where n is the block size. The bit independence criterion (BIC) is defined as the property that changing the ith bit in the input block of the averages changes half the bits in the output block. (See ref. I.) These properties can also be described in terms of the algebraic properties of the binary numbers of arbitrary block size.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0047.tif" />

<img file="CA2115063C_D0048.tif" />

G_n is the additive group of all n-bit binary numbers, where the symbol Θ means modulo 2 addition bitwise.

There are n maximal subgroups H which may be termed basic which are defined by the property that each block in //, has 0 in the ith position. Numbering from left to right, H_n consists of all even numbers, and H j, consists of all lower half numbers. In general:

Hi = lx ε G_n I x = -- -- 0 -- -- ) i n

Clearly, //, is characterized by the property that:

XiHi = 0 where x, = 0-010-0 1 ( n

1//,1 = I IG„ I = 2'”¹ .

There are a total of 2ⁿ - 1 maximal subgroups (MSG) which can be generated from these basic MSG’s by the operation:

Hk = Hi + Hj s (Hi n Hf (ff η Hj)

This is somewhat analogous to the Boolean rings described in ref. 2, section 9.4; however, the multiplicative semi-groups property defined by the intersection of sets does not apply here because the intersections of MSG's are not MSG's. The addition operation is actually the complement of that defined above, which would, in effect, define the sum of two MSG's to be the complement of another.

Changing the ith bit in some number x to obtain a new number y is equivalent to choosing y such x ® y = 0 0 · · 0 1 0 - 0, For a given i there are 2^n-1 such pairs.

L

SAC is equivalent to requiring that for 1 £ i,j &lt;n Tx Φ Ty has 0 as the jth bit one half of the time (no change) and 1 as theyth n-bit one half of the time (change). More formally, define:

Λ = (Γχ ΘΓν I x®y = 0 - 0 1 0 - 0) where 1 is at the ith bit position.

Note: This implies that x ε H, and y c H_i or vice versa. IP, I &lt; 2^n-1 since there are 2ⁿ*^x such pairs but the sums may not be distinct. Thus, SAC is equivalent to;

Pi c\Hj\ = \PiC\Hj\ = I I Pi I for 1 &lt; i_tj &lt; n n² conditions.

Pi consists of 2”’¹ n-bit numbers which may range from all the same to all different. Each bit results from adding a (unordered) pair (0,1), (0,0), (1,1). If the number of such pairs is, respectively, a, 6, c, then a + b + c = 2'¹ ‘ \ the number of paiTS defining P_t·. The number of zeroes in the pairs is a + 2b = 2*'¹ and the number of one’s is a + 2c = 2ⁿ’¹; therefore, a is even and the number of l’s and 0‘s appearing

SUBSTITUTE SHEET

<img file="CA2115063C_D0049.tif" />

WO 93/03559

PCT/US92/06497 'Φ / f* pi za Z*

-&lt;

in each bit position of the 2⁷¹'¹ numbers in P_t is even. For example, if n = 4, P₍ will contain eight 4-bit numbers, perhaps not distinct but each bit position will contain 0, 2, 4, 6 or 8 one's. If they are not evenly divided (avalanching), the closest approximation will be 2:6.

Considering P₍ a set of 2^{n l} numbers, including multiple occurrences, a IP; r^Hfï ₉ measure of approximate avalanching is -- averaged over all i,j pairs.

The bit independence criterion is related to avalanching. Consider the set P, including the multiplicity of each member. To meet BIC, the number of zeroes and ones should be approximately equal in each block. For n odd, of course, this can never occur in an individual block. There are 2ⁿ'¹ n-bit numbers (including duplicates) in P_t with a total of n2^/1’¹ binary bits. Let NPi be the number of zeroes in the setPj, including duplicates or multiple appearances

NPi n2ⁿ'^y is a measure of BIC for a given bit position. Overall, BIC specifies that:

iNPi i = l 1 n²2^{nl =} 2

For a given P₍, let the numbers be enumerated as follows, where Zy is the Jth position of the xth number and I = 2*\ ²u ^zi2 ..... ^Zln

Zji Z\2 Z_ln

Then, avalanching specifies that the zeroes and ones in each column will be approximately evenly divided, and BIC specifies the equivalent condition on the row's.

Both SAC and BIC are usually referred to as bit level properties because they refer to relations between individual bits in the same and different n-bit numbers for a given S-box or mapping. Thus, if applied to orthomorphic mappings, these properties depend on the key variable or the particular set of n linearly independent numbers acted on by the generating functions.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0050.tif" />

4-2. Other Criteria for_Lack_Qf Bias

The previous section briefly described the maximal subgroups (MSÎî's) of the group G_n of n-bit binary numbers where the group operation (©) is bitwise addition modulo 2. There are m = 2ⁿ ~ 1 such MSG’s H ···-, H_m which themselves form a group under the operation of Boolean addition:

+ (Hi n Hj) u, (Hi n Hj)

The n MSG’s which are characterized by all having zero in a given bit position, e.g., the even numbers, are easy to visualize conceptually. They are implicitly used in the definition of avalanching; however, the other m - n MSG’s are of equal significance algebraically, and any n linearly independent MSG’s can be used to generate the entire set. In ref. 3, the following was introduced:

Definition: A bijective mapping on G_n is said to be balanced if it maps each maximal subgroup, i.e., each subgroup of order 2ⁿ - I, half into itself and half into its complement.

If T is the bijective mapping, this means ITHi r\Hil = I THi r\ H_t I = 2^n-21 £ i &lt; 2ⁿ - 1. It was also shown in ref. 3 that T is an orthomorphism if and only if it is balanced. Thus, balance is a unique and universal property of orthomorphic block substitutions at the integer level, independent of linearity or key variable. A practical consequence is that in design of an orthomorphic S-box, no special effort need be made to incorporate or verify this property.

Transitivity is not an obvious quality to attribute to S-boxes since it is a property of certain permutation groups. If we are considering permutations on m = 2ⁿ - 1 numbers (or letters) of which block substitutions are an example, then the definition from ref. 6, pg. 82, is pertinent:

Definition: A group of permutations is said to be transitive if it contains at least one permutation which transforms any one of the m letters (numbers) into any other letter (number).

However, by prop. 6 of ref. 3, linear orthomorphisms form a transitive group on the 2ⁿ » 1 nonfixed numbers. In fact, this is also true for affine orthomorphisms. This property, which implies a thorough mixing at the integer level is, of course, a property not of a single block substitution but of a group of them.

The collection of all possible block substitutions or bijective mappings on G_n. viewed as permutations, constitute a transitive group, namely P_m, the symmetric group on m elements and of order /??*. Other transitive subgroups can be generated by taking all powers of a maximal permutation, that is, one with no proper subcycles.

SUBSTITUTE SHEET

WO 93/03559

PCT/ES92/06497

2115863

In the case of linear or automorphic orthomorphisms, this is particularly easy because of the property of being able to shift columns in the array of equations defining the automorphisms. Maximal nonlinear orthomorphisms could be usedto generate a transitive subgroup but, in general, the other members would not be orthomorphisms.

4-3. Applications to Orthomorphisms

If T is a linear (automorphic) or affine orthomorphism, it is clear that strict avalanching is not possible. In this case, Tx Φ Ty = T(x ®y) + S where S is a fixed number (S = 00·-0 if T is linear). Thus, consists of a single number and

IPj c\Hj\ = 0 or I and nHjI = 1 or 0. However, the n numbers P_t may have an equal distribution of zeros and ones so that bit independence is possible.

On the other hand, the nonlinear orthomorphisms constructed from linear ones have shown good avalanching and BIC. An example is given in the appendix of a nonlinear orthomorphism with strict avalanching and a BIC ratio of exactly |.

All orthomorphisms and only orthomorphisms have balance as defined in ref.

3. Linear and affine orthomorphisms are represented by transitive groups of permutations. Thus, over the family of block substitutions, each clear text block is mapped to each possible cipher text block except for the fixed point which may be varied. This can be summarized as follows:

<td> a.</td><td> SAC and BIC:</td><td> Bit level properties depending on the key variable</td>

<td> b.</td><td> Balance:</td><td> A universal integer level property of all orthomorphisms</td>

<td> c.</td><td> Transitivity:</td><td> A universal integer level property for groups of</td>

linear or affine orthomorphisms

SUBSTITUTE SHEET

<img file="CA2115063C_D0051.tif" />

WO 93/03559

PCT/LS92/06497

Orthomorphisms Other and also:

<td> Property</td><td> Nonlinear</td><td> Linear/Affme</td><td> Substitutions</td>

<td> Avalanching</td><td> Yes</td><td> No</td><td> Yes</td>

<td> Bit independence</td><td> Yes</td><td> Yes</td><td> Yes</td>

<td> Balance</td><td> Yes</td><td> Yes</td><td> No</td>

<td> Transitivity</td><td> No</td><td> Yes</td><td> Possibly*</td>

Ϊ t

j

I

I &lt;

Ϊ

V »

V'

T * This is a group properly and depends on selecting a block substitution which is maximal, i.e., no cycles, and then taking all powers of it.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497 ||

2115963

6. REFERENCES

1. The Structured Design of Cryptographically Good S-Boxes, Adams and Tavares, J, Cryptology (1990) 3:27-41

2. Fundamentals of Mathematics,'¹ Vol 1, Behnke, Bachman, et. al., MIT Press

1986.

6. Introduction to the Theory of Finite Groups, W. Ledermann, Oliver and Boyd, 1964.

7. Shift Register Sequences, S.W. Golomb, Aegean Park Press, 1982.

SUBSTITUTE SHEET

WO 93/03559

PCT/VS92/06497

<img file="CA2115063C_D0052.tif" />

APPENDIX

A. LINEAR ORTHOMORPHISMS VIEWED FROM VARIOUS PERSPECTIVES

As pointed out in section 2, a linear orthomorphism can be viewed and represented in several ways. For example, consider n = 4, with generating function ^xk - ^xk-4 f°^r which p - 12, and with base set or linearly independent set:

Xi = 0001, x₂ = θ^0Ιθ· *3 = 0100, x₄ = 1000.

This defines the table:

Column 1 Column 2 Column 3

<td> oooo</td><td> ©</td><td> oooo</td><td> =</td><td> oooo</td>

<td> 1001</td><td> ©</td><td> 0001</td><td></td><td> 1000</td>

<td> 0001</td><td> ©</td><td> 0010</td><td></td><td> 0011</td>

<td> 0010</td><td> ©</td><td> 0100</td><td> =</td><td> 0110</td>

<td> 0100</td><td> ©</td><td> 1000</td><td></td><td> 1100</td>

<td> 1000</td><td> ©</td><td> 0011</td><td> =</td><td> 1011</td>

<td> 0011</td><td> ©</td><td> 0110</td><td> s</td><td> 0101</td>

<td> 0110</td><td> ©</td><td> 1100</td><td> =</td><td> 1010</td>

<td> 1100</td><td> ©</td><td> 1011</td><td> =</td><td> 0111</td>

<td> 1011</td><td> ©</td><td> 0101</td><td></td><td> 1110</td>

<td> 0101</td><td> ©</td><td> 1010</td><td> =</td><td> 1111</td>

<td> 1010</td><td> ©</td><td> 0111</td><td> —</td><td> noi</td>

<td> 0111</td><td> ©</td><td> 1110</td><td> =</td><td> 1001</td>

<td> 1110</td><td> ©</td><td> mi</td><td> =</td><td> 0001</td>

<td> 1111</td><td> ©</td><td> 1101</td><td> =</td><td> 0010</td>

<td> 1101</td><td> ©</td><td> 1001</td><td> =</td><td> 0100</td>

It is easily verified that the mapping from column 1 to column 3 (or any other pair of columns) is linear under addition modulo 2. That same mapping could be

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0053.tif" />

100 represented by a table in which y (column 3) is a function f[x) of* (column 1). In decimal notation this becomes:

o

11 12

-4 0

6

12 15 10 9 11

7

1 2

It is easy to see that this is nonlinear under addition modulo 16 or by representing it in graphical form. The mapping can also be represented as a permutation:

(0)(1,3,5. 15. 2,6. 10. 13, 4. 12,7, 9,8, 11, 14)

It can also be written in terms of Boolean functions by rewriting column 1 in the natural order of the numbers and correspondingly rearranging column 3. The Boolean functions describe bits in column 3 as functions of blocks in column 1.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0054.tif" />

1.01

Ο η *&gt; ζ ί ίι ·£ iJ ·„? F

Column,...! 6j ά₂ ά₃ b₄0 0 0 0 0 0 0 1 0 0 10 0 0 11 0 10 0 0 10 1 0 110 0 111

0 0 10 0 1 10 10 10 11 110 0 110 1 1110 1111

Column 3

Λ &lt;2 h Λ 0 0 0 0 0 0 11 0 110 0 10 1

110 0 1111 10 10 10 0 1 10 11 î ο ο ο 110 1 1110

111 0 10 0 0 0 0 1 0 0 10

From this, the Boolean functions can be written:

/*! = 6 j © à₂/2 = M /3 = ® 63 © 0₄ f₄ = 6] © b₄

The generating function x_A, = x,_M © x/.,₃ operates universally on any set of 4 linearly independent 4-bit numbers; however, the Boolean functions depend on the specific mapping. For example, consider the same generating function but applied to the base:

xi = 0011,x₂ = 0110,x₃ = 1100,x₄ = 1000

SUBSTITUTE SHEET

<img file="CA2115063C_D0055.tif" />

WO 93/03559

PCT/US92/06497

102

<img file="CA2115063C_D0056.tif" />

This defines a new table:

<td colspan="2"> Column I</td><td colspan="2"> Column 2</td><td> Column</td>

<td> 0000</td><td> ©</td><td> 0000</td><td> =</td><td> 0000</td>

<td> 1011</td><td> ©</td><td> 0011</td><td> =</td><td> 1000</td>

<td> 0011</td><td> ©</td><td> 0110</td><td> =</td><td> 0101</td>

<td> 0110</td><td> ©</td><td> 1100</td><td></td><td> 1010</td>

<td> 1100</td><td> ©</td><td> 1000</td><td> =</td><td> 0100</td>

<td> 1000</td><td> ©</td><td> 0101</td><td> =</td><td> 1101</td>

<td> 0101</td><td> ©</td><td> 1010</td><td></td><td> nn</td>

<td> 1010</td><td> ©</td><td> 0100</td><td> =</td><td> 1110</td>

<td> 0100</td><td> ©</td><td> 1101</td><td> —</td><td> 1001</td>

<td> 1101</td><td> ©</td><td> 1111</td><td></td><td> 0010</td>

<td> 1111</td><td> ©</td><td> mo</td><td> =</td><td> 0001</td>

<td> 1110</td><td> ©</td><td> 1001</td><td></td><td> 0111</td>

<td> 1001</td><td> ©</td><td> 0010</td><td></td><td> 1011</td>

<td> 0010</td><td> ©</td><td> 0001</td><td></td><td> 0011</td>

<td> 0001</td><td> ©</td><td> 0111</td><td></td><td> 0110</td>

<td> 0111</td><td> ©</td><td> ion</td><td> —</td><td> 1100</td>

As in the first example, to obtain the Boolean functions, it is convenient to rearrange columns 1 and 3:

Column 1 6l 02 i&gt;3 Ô4 0 0 0 0 0 0 0 1 0 0 10 0 0 11 0 10 0 0 10 1 0 110 0 111 10 0 0 10 0 1 10 10 10 11 110 0 110 1 1110 1111

Column 3

Λ f-2 f3 fa 0 0 0 0 0 110 0 0 11 0 10 1

0 1 1111 10 10 110 0 110 1 10 11 1110 10 0 0

10 0 0 0 10 0 111 0 0 0 1

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

From this, the Boolean functions can be written:

fl -b^b-y f₂-b₁^b₄f₃ = b₃®b₄f₄ = b^b,eb₃

Except for f\, these differ from the previous example.

B. SELECTION OF EQUATIONS OR ROWS IN AN AUTOMORPHIC (LINEAR) ORTHOMORPHISM FOR NONLINEAR1ZAT1ON

Section 3.5 suggested various ways to choose nonoverlapping quadruples or sextuples of equations for nonlinearization. The idea is to nonlinearize a large fraction of the m - 2ⁿ - 1 equations in the array which defines the orthomorphic mapping. Since 2* - 1 is odd, it will never be possible by the methods of section 3.2 to modify all the equations because the process is applied to sets with four or six members. There is no optimal process for all block sizes or even for different generating functions with the same block size. Following are some examples for block sizes n = 4, 5, 6, 7, and 8.

For n = 4, there is just one pair of conjugate generating functions with p - 4, 9 = 8 and p = 12, q = 11, respectively. The corresponding maximal density of rows is given by:

3 4

7 and

2 3

6 7

12 15 for a modification of 10 of the 15 rows.

For.n = 5, the optimum again is a hybrid mix. For example, for x* = X/..5 Θ ^ΧΛ-2*Ρ = 18, ç = 23, and m - 31. Twenty-four rows out of 31 can be modified, selecting:

<td> 1</td><td> 2</td><td> 0</td><td> 4</td><td> 23</td><td> 24</td>

<td> i</td><td> δ</td><td> 9</td><td> 10</td><td> 29</td><td> 30</td>

<td> 14</td><td> 15</td><td> 16</td><td></td><td> 5</td><td></td>

<td> 20</td><td> 21</td><td> 22</td><td></td><td> 11</td><td></td>

<td> 25</td><td> 26</td><td> 27</td><td></td><td> 6</td><td></td>

For p = 19, 9 = 11 corresponding to x/. =x&gt;-5 ^{one can} do ^a better with 28 rows out of 31 for modification by selecting:

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<td> 1</td><td> 2</td><td> 3</td><td> 4</td><td> 11 12</td>

<td> 7</td><td> 8</td><td> 9</td><td> 10</td><td> 17 1Î</td>

<td> 13</td><td> 14</td><td> 15</td><td> 16</td><td> 23 24</td>

<td> 19</td><td> 20</td><td> 21</td><td> 22</td><td> 29 30</td>

<td> 26</td><td> 27</td><td> 28</td><td></td><td> 5</td>

<td> For π = 6 and</td><td></td><td> the shift p =</td><td colspan="2"> 6 and q = 40. Since m = 63 of which</td>

<td> 7 is a factor, d = 7 is £</td><td> l candidate fo:</td><td colspan="3"> r a spacing as described in section 3.5. Also, for</td>

<td colspan="2"> q = 40, 7 is not a divisor of q, q -</td><td> 1, — , q - 4.</td><td> This</td><td> yields 54 out of 63 rows for</td>

<td colspan="2"> modification as follows:</td><td></td><td></td><td></td>

<td> 1</td><td> 2</td><td> 3</td><td> 4</td><td> 40 41</td>

<td> I + al</td><td> 2 + a7</td><td> 3 + al</td><td> 4 + a</td><td> 7 40 + al 41 + al</td>

<td> 57</td><td> 58</td><td> 59</td><td> GO</td><td> 33 34</td>

<td colspan="3"> Once again, the selection of sets of equations or</td><td> rows fo</td><td> •r modification depends on the</td>

<td colspan="3"> generating function. This particular selection \\</td><td> •ill not</td><td> work for most other values of</td>

<td> q corresponding to n =</td><td> 6.</td><td></td><td></td><td></td>

<td> For n = 7, m =</td><td colspan="3"> 127 is a Mersenne prime, so</td><td> the previous shortcut is not</td>

<td colspan="5"> available; however, for certain generating functions, one can do quite well. Consider</td>

<td> n = 7,^ = h.₇®x,.₅</td><td> ®X_k.₄ ®Xk-3</td><td> Θ A'k-2 ®</td><td colspan="2"> .j for which p = 19 and q = 9. Take</td>

<td> rows as follows:</td><td></td><td></td><td></td><td></td>

<td> 1</td><td> 2</td><td> 3</td><td></td><td> 9</td>

<td> then,</td><td></td><td></td><td></td><td></td>

<td> 5</td><td> 6</td><td> ί</td><td> s</td><td> 13 14</td>

<td> 10</td><td> 11</td><td> 12</td><td></td><td> 18</td>

<td> 15</td><td> 16</td><td> 17</td><td></td><td> 23</td>

<td colspan="5"> Following the same pattern of a sextuple followed by two quadruples, through:</td>

<td> 103</td><td> 104</td><td> 105</td><td> 106</td><td> 111 112</td>

<td> 108</td><td> 109</td><td> no</td><td></td><td> 116</td>

<td> 113</td><td> 114</td><td> 115</td><td></td><td> 121</td>

<td colspan="2"> and then completing with rows:</td><td></td><td></td><td></td>

<td> 118</td><td> 119</td><td> 120</td><td></td><td> 126</td>

<td> 123</td><td> 124</td><td> 125</td><td></td><td> 4</td>

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497 r·i··· (

t

105

124 out of 127 equations can thus be modified, omitting only 117, 122, and 127, Other variations on this will work just as well omitting only three equations.

Also for n = 7, xjj = χ^.η θ x^.g Θ Χ£„₄ θ xjj.₂, p - 107 and q = 10, an analogous f

V !

ί system works taking two sextuples and one quadruple followed by adjustments among the last rows. Again, 124 out of 127 equations can be selected for modification; however, this density or efficiency does not appear to hold for all generating functions.

For n - 8, consider the generating function x^ = x*.g Θ xj^.g Φ x*.₅ Φ x_k.$ for which p = 16, q = 54, and m = 2ⁿ - 1 = 255. We will select quadruples of rows consisting of successive triples, starting with the first row other than the identity, plus the row which is the triple sum of the first three. Referring to section 3.5, choose the row spacing d = 5. 5 is a factor of m and relatively prime to q - 1 = 53, q - 2 = 52, and q - 3 = 51. This will lead to selection of the following rows:

2 3

7 8 + 5α 2 + 5ά 3 +5α + 5α

251 252 253 49 where 0 £ α S 50. This selects 51 X 4 = 204 rows or equations for nonlinearization from the total of 255 in the orthomorphic array. Left out are row 5 and all multiples of 5.

This spacing, however, will not work efficiently if we choose sextuples of rows because q - 4 = 50, a multiple of 5. In fact, when a= 10, 4 + 10a= 54, so that the process will terminate with just 6 X 10 = 60 rows. However, there are several ways in which the remaining 195 rows can be divided into quadruples or sextuples, more or less piecemeal.

The spacing d = 17 is also a divisor of m = 255, but it is also a divisor of q - 3 = 51 and, hence, is not an efficient spacing.

Again, for n = 8 but with the generating function x* = x^.g Φ xj^.₄ © x^.g © x^.₂for which p = 25, q - 60, and m = 255, d = 17 is a factor of m but now it is not a divisor of q = 60, q - 1 = 59, ····, q - 4 = 56. Sextuples of rows can be selected as follows:

Γ

I

K i

Ï ί

£· ί

ί.'

V··

f.

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<td> o-</td><td></td><td> 106</td><td></td><td></td><td></td>

<td> 1</td><td> 2</td><td> 3</td><td> 4</td><td> 60</td><td> 61 . **</td>

<td> IS</td><td> 19</td><td> 20</td><td> 21</td><td> 77</td><td> 78</td>

<td></td><td> 1 + 17a</td><td> 2+ 17a</td><td> 3 +17a</td><td> 4 + 17a</td><td> 60 + 17a</td><td> 61 + 17a</td>

<td colspan="3"> This process terminates when a-</td><td colspan="3"> 14, for a total of 15 X 6 = 90 rows. For a=</td><td> 15, 1 + 17a</td>

<td> = 256 s</td><td> 1 modulo zn.</td><td colspan="3"> and, so, the process repeats; however,</td><td colspan="2"> one can start again as</td>

<td> follows:</td><td></td><td></td><td></td><td></td><td></td><td></td>

<td></td><td> 5</td><td> 6</td><td> 7</td><td> 8</td><td> 64</td><td> 65</td>

<td></td><td> 22</td><td> 23</td><td> 24</td><td> 25</td><td> 81</td><td> 82</td>

<td></td><td> 5+ 17o</td><td> 6 +17a</td><td> 8 + 17a</td><td> 9 + 17a</td><td> 64+ 17a</td><td> 65 + 17a</td>

This process again terminates when a= 14 for 15 X 6 = 90 additional rows. Again, at a= 15 the process repeats. This gives a total of 180 rows. None of the remaining 75 rows contain triples with corresponding sums.

However, as in p = 16, q = 54, quadruples can be selected with a spacing of d = 5 again because 5 is relatively prime to q - 1 = 59, q - 2 = 58, and q - 3 = 57.

This is easy to apply for suitable combinations of m and q_t that is, for cooperative generating functions; however, it is not obvious how many equations representing the linear orthomorphism must be modified to get a ’'good'* nonlinear mapping.

C. THE DEPENDENCE OF AVALANCHING AND BIT INDEPENDENCE ON SYSTEM PARAMETERS

In section 4-1 it was pointed out that avalanching and bit independence depend on the actual numbers in the block substitution and not just the algebraic structure. Ti illustrate this, we take an n = 4 bit family of block substitutions defined by a linear orthomorphism with generating function = x*.₄ © x^.₃ for which the shift p = 12 and q = 11.

As the first example, we generate a nonlinear orthomorphism using rows:

2 3 11

6 7 15

SUBSTITUTE SHEET

WO 93/03559

PCI7US92/06497

<img file="CA2115063C_D0057.tif" />

107 and with base or linearly independent set = 0001, xo = 0010, x₃ = 0100, x₄ = 1000.

This is a nonlinearized version of the first linear orthomorphic mapping in section A of this appendix. As modified, it becomes:

!T η P n

J b j

<td> 0000</td><td> ©</td><td> 0000</td><td> =</td><td> 0000</td>

<td> 1010</td><td> ©</td><td> 0010</td><td> =</td><td> 1000</td>

<td> 0010</td><td> ©</td><td> 0001</td><td> - .</td><td> 0011</td>

<td> 0001</td><td> ©</td><td> 0111</td><td> =</td><td> 0110</td>

<td> 0111</td><td> ©</td><td> 1110</td><td> =</td><td> 1001</td>

<td> 1110</td><td> ©</td><td> 1111</td><td> =</td><td> 0001</td>

<td> 1111</td><td> ©</td><td> 1101</td><td> =</td><td> 0010</td>

<td> 1101</td><td> ©</td><td> 0110</td><td> =</td><td> 1011</td>

<td> 0110</td><td> ©</td><td> 0011</td><td></td><td> 0101</td>

<td> 0011</td><td> ©</td><td> 1001</td><td> =</td><td> 1010</td>

<td> 1001</td><td> ©</td><td> 0100</td><td> =</td><td> 1101</td>

<td> 0100</td><td> ©</td><td> 1000</td><td></td><td> 1100</td>

<td> 1000</td><td> ©</td><td> 1100</td><td></td><td> 0100</td>

<td> 1100</td><td> ©</td><td> ion</td><td> =</td><td> 0111</td>

<td> 1011</td><td> ©</td><td> 0101</td><td></td><td> 1110</td>

<td> 0101</td><td> ©</td><td> 1010</td><td> =</td><td> 1111</td>

To measure avalanching and bit independence as described in section 4-1, we first enumerate the set Pj = |Γχ © Ty lx ©y = 1000), that is, pairs x, y which differ only in the first bit position. For n = 4, the sixteen 4-bit number pairs form eight pairs, not necessarily distinct. So, including multiplicity of appearance, I Pi 1 = IP2I = IP₃1 = 1P₄ I = 8, Also recall that !l_t is the maximal subgroup of n-bit numbers with 0 in the ith bit position. Here, for zi = 4, H₄ is the subgroup of even numbers, and

Hy is the subgroup of lower half numbers, etc. For Pj, the tabulation is on the following worksheet. Each IPj n ΗΛ = 4 which means that 4 out of 8, or one half of = the bits in each member of Pj is 0 in the Jth bit position, i.e., in the columnar ί tabulation, each column is comprised of half 0 s and half I s. The number of 0's in y each member of Pj is tabulated, i.e., horizontal tabulation. The total number of 0's,

JVPj = 16 out of 32 bits, so that half are 0's.

When the same tabulation is made for Pj P₃ P₄ it turns out that IPin/fyl =4 | for all 16 pairs, NP_X - 16 for each p_x so that the avalanching is strict and ;

Σ^Ρ, 64 1 f „2₂,M ⁼ 128 ⁼ 2 i

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

108

WORKSHEET

COMPUTATION OF AVALANCHING AND BIT INDEPENDENCE

ClearBits Cipher Bits P\ = {Tx® Ty}

<td> 1</td><td> 2</td><td> 3 4</td><td colspan="3"> 1</td><td> 2</td><td> 3</td><td> 4</td><td> 1</td><td> 2 3</td><td colspan="2"> 4</td><td> No. of 0 Bits</td>

<td> 0</td><td> 0</td><td> 0</td><td> 0</td><td> Tx</td><td> 0</td><td> 0</td><td> 0</td><td> 0</td><td> 0</td><td> 3</td><td> 0</td><td> 0</td><td> 3</td>

<td> 1</td><td> 0</td><td> 0</td><td> 0</td><td> Ty</td><td> 0</td><td> 1</td><td> 0</td><td> 0</td><td></td><td></td><td></td><td></td><td></td>

<td> 0</td><td> 0</td><td> 0</td><td> 1</td><td></td><td> 0</td><td> 1</td><td> 1</td><td> 0</td><td> 1</td><td> 0</td><td> 1</td><td> 1</td><td> 1</td>

<td> 1</td><td> 0</td><td> 0</td><td> 1</td><td></td><td> 1</td><td> 1</td><td> 0</td><td> 1</td><td></td><td></td><td></td><td></td><td></td>

<td> 0</td><td> 0</td><td> 1</td><td> 0</td><td></td><td> 0</td><td> 0</td><td> 1</td><td> 1</td><td> 1</td><td> 0</td><td> 1</td><td> 1</td><td> 1</td>

<td> 1</td><td> 0</td><td> 1</td><td> 0</td><td></td><td> I</td><td> 0</td><td> 0</td><td> 0</td><td></td><td></td><td></td><td></td><td></td>

<td> 0</td><td> 0</td><td> 1</td><td> 1</td><td></td><td> I</td><td> 0</td><td> 1</td><td> 0</td><td> 0</td><td> 1</td><td> 0</td><td> 0</td><td> 3</td>

<td> 1</td><td> 0</td><td> 1</td><td> 1</td><td></td><td> 1</td><td> 1</td><td> 1</td><td> 0</td><td></td><td></td><td></td><td></td><td></td>

<td> 0</td><td> 1</td><td> 0</td><td> 0</td><td></td><td> 1</td><td> 1</td><td> 0</td><td> 0</td><td> I</td><td> 0</td><td> 1</td><td> 1</td><td> 1</td>

<td> 1</td><td> 1</td><td> 0</td><td> 0</td><td></td><td> 0</td><td> 1</td><td> 1</td><td> 1</td><td></td><td></td><td></td><td></td><td></td>

<td> 0</td><td> 1</td><td> 0</td><td> 1</td><td></td><td> 1</td><td> I</td><td> 1</td><td> 1</td><td> 0</td><td> 1</td><td> 0</td><td> 0</td><td> 3</td>

<td> 1</td><td> 1</td><td> 0</td><td> 1</td><td></td><td> 1</td><td> 0</td><td> I</td><td> 1</td><td></td><td></td><td></td><td></td><td></td>

<td> 0</td><td> 1</td><td> 1</td><td> 0</td><td></td><td> 0</td><td> 1</td><td> 0</td><td> 3</td><td> 0</td><td> 1</td><td> 0</td><td> 0</td><td> 3</td>

<td> 1</td><td> 1</td><td> 1</td><td> 0</td><td></td><td> 0</td><td> 0</td><td> 0</td><td> 1</td><td></td><td></td><td></td><td></td><td></td>

<td> 0</td><td> 1</td><td> 1</td><td> 1</td><td></td><td> 1</td><td> 0</td><td> 0</td><td> 1</td><td> 1</td><td> 0</td><td> 1</td><td> 1</td><td> 1</td>

<td> 1</td><td> 1</td><td> 1</td><td> 1</td><td></td><td> 0</td><td> 0</td><td> 1</td><td> 0</td><td></td><td></td><td></td><td></td><td></td>

IPi n/Zjl =4 IP_X ntf₂l =4 IP_X n/f₃1 =4 IPjnJ^I =4

NPi = 16

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

109 9 1 Ί A P ^f‘ &amp; 11 j J o &lt;i

For comparison, we can now use the second example in section A, nonlinearized with the same set of equations, and differing only in that a^new base set is used:

= 0011,x₂ = 0110,x₃ - 1100,x₄ = 1000 This second nonlinear orthomorphism can be written as follows:

<td> 0000</td><td> ©</td><td> 0000</td><td> 0000</td>

<td> 1110</td><td> ©</td><td> 0110</td><td> 1000</td>

<td> 0110</td><td> ©</td><td> 0011</td><td> 0101</td>

<td> 0011</td><td> ©</td><td> 1001</td><td> 1010</td>

<td> 1001</td><td> ©</td><td> 0010</td><td> 1011</td>

<td> 0010</td><td> ©</td><td> 0001</td><td> 0011</td>

<td> 0001</td><td> ©</td><td> 0111</td><td> 0110</td>

<td> 0111</td><td> ©</td><td> 1010</td><td> 1101</td>

<td> 1010</td><td> ©</td><td> 0101</td><td> mi</td>

<td> 0101</td><td> ©</td><td> 1011</td><td> 1110</td>

<td> 1011</td><td> ©</td><td> 1100</td><td> 0111</td>

<td> 1100</td><td> ©</td><td> 1000</td><td> 0100</td>

<td> 1000</td><td> ©</td><td> 0100</td><td> 1100</td>

<td> 0100</td><td> ©</td><td> 1101</td><td> 1001</td>

<td> 1101</td><td> ©</td><td> 1111</td><td> 0010</td>

<td> 1111</td><td> ©</td><td> 1110</td><td> 0001</td>

<td colspan="3"> Making the same computation as on the sample</td><td> worksheet, the results are as</td>

<td> follows:</td><td> \Ρ_ϊηΗ₁</td><td> 1 = 1?! n//₂l = ο, 1</td><td> P] r,tf₃l = 8</td>

<td colspan="4"> and IP,· r\H:\ = 4 for the remaining 13. A'Pj = 12, and .\'P₂ = Λ’Ρ₃ = .\^rP₄ = 16. Thus:</td>

<td> The avalanching is no</td><td colspan="3"> Σ--' - - 047 128 “ 128 ^u‘⁴' longer strict but since almost half the time there is a bit</td>

<td colspan="3"> change, it might be called good. For the third example, we again</td><td> return to the same linear</td>

<td> orthomorphism with p</td><td> = 12 and q</td><td colspan="2"> = 11, but this time nonlinearize it with a partially</td>

<td colspan="2"> different collection of rows, that is,</td><td colspan="2"> a sextuple and a quadruple:</td>

<td> 1</td><td> 2</td><td> 3 4</td><td> 11 12</td>

<td> 13</td><td> 14</td><td> 15</td><td> 8</td>

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

Λ _f? .4»' p a_sS» &amp; a

110

However, the same base or linearly independent set is used as in the first example, that is, Xi = 0001, x₂ = 0010, x₃ = 0100, x₄ = 1000. The third nonlinear orthomorphism ;

i can be written as follows: ί

<td> 0000</td><td> ©</td><td> 0000</td><td> =</td><td> 0000</td>

<td> 1010</td><td> θ</td><td> 0010</td><td></td><td> 1000</td>

<td> 0010</td><td> ©</td><td> 1110</td><td> =</td><td> 1100</td>

<td> 1110</td><td> ©</td><td> 1001</td><td> =</td><td> 0111</td>

<td> 1001</td><td> Θ</td><td> 0100</td><td> =</td><td> 1101</td>

<td> 0100</td><td> ©</td><td> 0111</td><td> =</td><td> 0011</td>

<td> 0111</td><td> ©</td><td> 0001</td><td> -</td><td> 0110</td>

<td> 0001</td><td> ©</td><td> 1000</td><td> =</td><td> 1001</td>

<td> 1000</td><td> ©</td><td> 0011</td><td> =</td><td> 1011</td>

<td> 0011</td><td> ©</td><td> 0110</td><td></td><td> 0101</td>

<td> 0110</td><td> . ©</td><td> 1100</td><td> =</td><td> 1010</td>

<td> 1100</td><td> ©</td><td> 1101</td><td> =</td><td> 0001</td>

<td> 1101</td><td> ©</td><td> 1111</td><td> =</td><td> 0010</td>

<td> 1111</td><td> ©</td><td> 1011</td><td> =</td><td> 0100</td>

<td> 1011</td><td> ©</td><td> 0101</td><td> -</td><td> 1110</td>

<td> 0101</td><td> ©</td><td> 1010</td><td> =</td><td> mi</td>

The results now are:

IP₂ⁿ 1 ⁼ θ I Py n Hy I = 4 for the other 15 sets

NP₂ = 12 and APj = NP₀ = NP₄ =16

Thus:

œ.

128 ⁼ 128 = 0.47 and the avalanching, while not strict, is closer to it by some visceral measure than in the second example.

<img file="CA2115063C_D0058.tif" />

à

SUBSTITUTE SHEET

WO 93/03559

PCT/US92/06497

<img file="CA2115063C_D0059.tif" />

I

f.

r

111

METHODS OF ’’ON-LINEAR DYNAMIC SUBSTITUTION

Using the Generating Function and Base Set, generate the set of Linear Orthomorphism Equations:

Equation #

Xm © Xl — Xl-p Xl © X2 X2-p

Xj-1 © Xj

Xj_p ro Xjn-1 © ^xm — Xm—p

Where m - 2ⁿ - 1

2. Determine q such that Xq = xi φ X2 φ X3

3. Based on q and the factors of m determine:

a) Which of the following two sets of Equations to be nonlinearized for each iteration of a = 0, 1, 2, . . I:

Set 1 - B+ad, B+l+ad, B+2+ad and B+q-l+ad

Set 2 = B+ad, B+l+ad, B+2+ad, B+3+ad, B+q-l+ad, B+q+ad

Where B is the Beginning Equation and may be any number between 1 and m, inclusive, and d is defined below.

b) The spacing, d, between successive sets of nonlinearized equations (e.g., equations B+3d,

WO 93/03559

PCT/US92/06497

112

B+l+3d, B+2+3d and B+q-l+3d will be nonlinearized in one iteration and then, in the next iteration, equations B+4d, B+l+4d, B+2+4d and B+q~l+4d will be nonlinearized, .

Note: In some instances, both Set 1 and Set 2 will be used alternately or in some other pattern.

4. Starting with a = 0 and stopping when either a = I (the input number of iterations) or when the. process attempts to work on rows already nonlinearized, iteratively perform the nonlinearizing algorithm defined below:

If Set 1 is being nonlinearized, add vectorially to each of the Set 1 equations, (^xB+ad θ ^xB+l+ad) θ (^xB+ad Φ ^xB+l+ad) ~ θ·

If Set 2 is being nonlinearized, add vectorially to equations B+ad and B+g-l+ad, (^xB+ad Φ ^xB+l+adl θ (^xB+ad θ ^xB+l+ad) “ θ» add vectorially to equations B+l+ad and B+2+ad, (ΧΒ+ad Φ ^xB+2+ad&gt; Φ (^xB+ad Φ ^xB+2+ad) = Θ; and add vectorially to equations B+3+ad and B+Q+ad, (^xB+l+ad Φ ^xB+2+ad&gt; Φ &lt;^xB+l+ad Φ ^xB+2+ad&gt; ” Θ.

i ί' *·.

I

Note: In all cases, if any equation number or index to x is greater than m, the value of m minus that number will be used instead of that number (e.g.,

WO 93/03559

PCT/US92/06497

113

<img file="CA2115063C_D0060.tif" />

if B+l+ad is greater than m, m - (B + l+ad) will be used instead).

j i

i r

5. Generate the naturally ordered Encryption Look-up Table ' and De-encryption Look-up Table which reflect the Orthomorphic Encryption Permutation and the Orthomorphic De-encryption Permutation resulting from the Nonlinear Orthomorphism Equations generated in step 4. The Nonlinear Dynamic Substitution Device is comprised of these look-up tables plus mechanisms for changing the transformation fixed point.

As an alternative to the Look-up Table, two sets of modified equations can be used:

<td> For encryption,</td><td> , the</td><td> clear text</td><td> is</td><td> column 1,</td><td> which</td>

<td> encrypted into</td><td> the</td><td> cipher text</td><td> in</td><td> column 3:</td><td></td>

<td> 1</td><td></td><td> 2</td><td></td><td></td><td> 3</td>

<td> Ym</td><td> Φ</td><td> Yl</td><td></td><td> =</td><td> Zi</td>

<td> Yl</td><td> Φ</td><td> Y2</td><td></td><td> -</td><td> z₂</td>

<td> •</td><td> «</td><td> •</td><td></td><td> •</td><td></td>

<td> •</td><td> «</td><td> •</td><td></td><td> •</td><td></td>

<td> yj-i</td><td> Φ</td><td> yj</td><td></td><td> =s</td><td>^zj</td>

<td> •</td><td></td><td></td><td></td><td> •</td><td> •</td>

<td> Ym-1</td><td> Φ</td><td> Ym</td><td></td><td> —</td><td> Zm</td>

WO 93/03559

PCT/US92/O6497

G ·{ * ·*·' '·’

L i Γ./ύ

114

Columns 1 and 2 are in the same order but shifted by one position. The numbers in column 3 are in a different . *· order.

For decryption, the cipher text in column 3 is de encrypted into the clear text in column 1

Vl

V₂

Φ ^wm w₂ © wi © Wj_i

Vjn “ ^wm Φ ^wm-l

The order of the rows of equations have now been arranged leaving the individual equations unchanged, so that columns 2 and 3 are in the same order, but shifted by one position, the numbers in column 1 are now in a different order from those in columns 2 and 3.

i