To Part C:

Some Other Fenced Block Cipher Mechanisms

FIGURES 15(a) and 15(b) show various other fenced block cipher mechanisms that may be used as cryptographic mechanism 100. FIGURE 15(a) shows a 4x fenced construct with 1x strength.

FIGURE 15(b) shows a variation on 4x fenced block ciphers.

Balanced Block Mixers in combination with Substitution Mechanisms

In some embodiments of cryptographic mechanism 100, balanced block mixers are combined with substitution mechanisms without the use of other cipher mechanisms. For example, the cryptographic mechanism of FIGURE 16 is a 64-bit block cipher using three fencing layers (of substitution mechanisms) 202, 204, and 206, and balanced block mixers (in two groups 208, 210 of balanced block mixers).

As another example, the cryptographic mechanism 100 shown in FIGURE 17 depicts a 64-bit block cipher using three fencing layers 212, 214, 216 and balanced block mixers with FFT-style mixing (in two groups or layers 218 and 220 of balanced block mixers). Note here that the output of each substitution mechanism eventually propagates over the entire message since the outputs of the balanced block mixers are fed to adjacent balanced block mixers.

In the discussion above, the term "cipher mechanism" has been used to described mechanisms that are used as components of cryptographic mechanisms. However, it should be clear that each cryptographic mechanism described herein can itself be used wherever a cipher mechanism is used in the description. For example, the 64-bit cipher mechanism of FIGURE 12 can be a 64-bit version of the cryptographic mechanism of FIGURE 10.

A Multiple Size Block Cryptographic Mechanism

This invention provides many ways to increase the block size of a cryptographic mechanism. This makes for stronger cryptographic mechanisms, but it can cause inefficiencies in their use. In particular, if the length of a message to be encrypted (or decrypted) is not a multiple of the block size, then part of one block will be empty (and therefore wasted). It is possible for almost an entire block to be empty.

With reference to FIGURE 18, a multiple-size cryptographic mechanism 222 comprises m cryptographic mechanisms 100a-100m, having different block sizes and a decision means 216. For example, cryptographic mechanism 222 has cryptographic mechanisms with block sizes which are different multiples of n. There is an n-bit cryptographic mechanism 100a, a 2n-bit cryptographic mechanism 100b, up to an (mxn)-bit cryptographic mechanism 100m. These cryptographic mechanisms can be made up of any of the cryptographic mechanisms described above or of other cryptographic mechanisms. The decision means 216 of cryptographic mechanism 222 operates as follows to select among the cryptographic mechanisms so as to process the message: When an input signal is to be enciphered, a particular cryptographic mechanism 100a-100m is chosen based on the length of the input signal so as to minimize the wasted block space in the output signal. In one embodiment, the decision means always selects the cryptographic mechanism which can process the input block with the least waste. In another embodiment, in the case where the entire length of the input data block is known in advance, decision means 216 can select an optimal combination of cryptographic mechanisms 100a-100x, and use them in any order (the order in which they are used must be known by a decipherer). When the entire size of the input message is known in advance, and when the optimal combination of cryptographic mechanisms is chosen, the input message can be processed by these mechanisms in any order, in a fixed order, or in an order based on a key. Note that decision means 216 need not be a part of the cryptographic mechanism 222, but can instead be incorporated into the system which employs the multiple-size cryptographic mechanism 222. In that case, cryptographic mechanism 222 would be given blocks of a size (corresponding to the size of one its component cryptographic mechanisms 100a-100m), along with some indication as to the size of the current input block.

For example, if n is 64, and m is 8, then cryptographic mechanism 222 has eight cryptographic mechanisms 100a-100h, one for each of 64-bit, 128-bit, . . ., 512-bit blocks. An input message of 514 bits would use the 512-bit cryptographic mechanism and the 64-bit cryptographic mechanism, with a waste of only 62 bits. (If only the 512-bit cryptographic mechanism was used, the waste would be 510-bits.)

While the invention has been described in connection with what are presently considered to the most practical and preferred embodiments, it is to be understood that the invention is not to be limited to the disclosed embodiment, but on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims.

CLAIMS

What Is Claimed Is:

1. An invertible balanced block mixer cryptographic mechanism for mixing each of some number x input blocks of some block size into each of said number x output blocks of said block size, comprising:

said number x mutually orthogonal latin square mixing or combiner mechanisms of order 2 to the power n, where n is said block size in bits.

2. A balanced block mixer mechanism for the invertible mixing of two input blocks of some block size n in bits into two output blocks of said block size n, comprising:

(a) A first latin square mixing mechanism of order 2 to the power n for combining said two input blocks into the first of said two output blocks; and

(b) A second latin square mixing mechanism of order 2 to the power n, orthogonal to said first latin square mixing mechanism, for combining said two input blocks into the second of said two output blocks.

3. The invertible mixer of claim 2 wherein the latin square mixing used in at least one said latin square mixing mechanism is explicitly described in an array.

4. The invertible mixer of claim 2 wherein the latin square mixing used in at least one said latin square mixing mechanism is implicitly described by a pre-determined computation.

5. The balanced block mixing method for the invertible mixing of two input blocks of some block size n in bits into two output blocks of said block size n, comprising the steps of:

(a) combining the two input blocks by using a first latin square mixing of order 2 to the power n to produce the first of said two output blocks; and

(b) combining the two input blocks by using a second latin square mixing of order 2 to the power n, orthogonal to said first latin square mixing, to produce the second of said two output blocks.

6. The invertible mixing method of claim 5, wherein at least one said latin square mixing is described in an array.

7. The invertible mixing method of claim 5, wherein at least one said latin square mixing is described by a pre-determined computation.

8. A balanced block mixer cryptographic mechanism for mixing each of some number n greater than 2 input blocks of some block size into each of said number n output blocks of said block size, comprising:

(a) said number n mutually orthogonal latin square mixing or combiner mechanisms of order 2 to the power m, where m is said block size in bits.

9. A balanced block mixer mechanism for mixing two input blocks of some block size n in bits into two output blocks of said block size n, comprising:

(a) a first latin square of order 2 to the power n, described in an array, for combining said two input blocks into the first of said two output blocks; and

(b) a second latin square of order 2 to the power n, described in an array, orthogonal to said first latin square, for combining said two input blocks into the second of said two output blocks.

10. The method of using an inverse to an original orthogonal latin squares mixing of order 2 to the power n, where n is the block size in bits, to recover the original input values from each mixed result, comprising the steps of:

(a) producing an inverse orthogonal latin squares mixing of order 2 to the power n, which is the inverse to said original orthogonal latin squares mixing; and

(b) for each said mixed result, presenting said mixed result to said inverse latin squares mixing and collecting said original input values from the result of that mixing.

Last updated: 1997-04-03