To Part A:

DESCRIPTION OF THE PRESENTLY PREFERRED EXEMPLARY EMBODIMENTS

Various embodiments of enhanced cryptographic mechanisms will now be described. These embodiments employ selected combinations of cipher mechanisms, balanced block mixers, and arrays of substitution mechanisms to produce cryptographic mechanisms. When a cipher mechanism is employed, the appropriate addition of balanced block mixers and substitution mechanisms enhances the strength of the cipher mechanism.

The operation of these cryptographic mechanisms is sometimes explained herein in the context of systems within which the mechanisms might be used, for example, a communications system such as that of FIGURE 3(a), or a computer system such as that of FIGURE 3(b), however, the use of the cryptographic mechanism of the present invention is in no way intended to be limited to those systems.

Increasing the Block Size of Block Ciphers using Balanced Block Mixers

One form of enhanced cryptographic mechanism employs balanced block mixers (described below in detail) in combination with other block cipher mechanisms to increase the input block size of the other cipher mechanisms. For example, with reference to FIGURES 1, 4(a) and 4(b), the encryption mechanism 102 of cryptographic mechanism 100 has balanced block mixers 140 and 142, and block cipher mechanisms 144a and 144b, each block cipher mechanism implementing an n-bit block cipher. The decryption mechanism 104 of the cryptographic mechanism 100 has balanced block mixers 146 and 148 and block cipher mechanisms 150a and 150b, each block cipher mechanism implementing the n-bit cipher. The cipher mechanisms can be DES or IDEA mechanisms or any other n-bit block cipher mechanisms. The block cipher mechanisms 150a and 150b need not be the same mechanism, for example, one can be DES and the other can be IDEA. An input message block P2n of size 2n-bits to be encrypted is split into two n-bit data blocks An and Bn (herein the subscript is the size of the block in bits). Data blocks An and Bn are mixed by balanced block mixer 140 to produce two output n-bit data blocks Xn and Yn. Data blocks Xn and Yn are then input to cipher mechanisms 144a and 144b, respectively, and encrypted (using the appropriate keys), to produce encrypted n-bit data blocks Xn' and Yn'. Data blocks Xn' and Yn' are mixed using balanced block mixer 142, producing n-bit data blocks En and Dn. The output of the encryption mechanism 102 (and thus of the cryptographic mechanism 100) is the 2n-bit output message block C2n formed by joining the two n-bit blocks En and Dn. Balanced block mixers 140 and 142 can perform the same or different balanced block mixing transform. In a communication system 120 such as depicted in FIGURE 3(a), the output message C2n is sent over the open channel 124 to another communication device 122 in the communication system. In a computer system 130 such as depicted in FIGURE 3(c), the output message is saved in a file or is transmitted to another computer 132 in the system or is further processed.

Decryption of the output message C2n (for instance, in another communication device 122 in the communication system 120) is achieved using decryption mechanism 104 of cryptographic mechanism 100 as follows, with reference to FIGURE 4(b). In the mechanism of FIGURE 4(b) (with reference also to FIGURE 4(a)), balanced block mixer 146 is the inverse of balanced block mixer 142, and balanced block mixer 148 is the inverse of balanced block mixer 140. Further, cipher mechanisms 150a and 150b are the inverse mechanisms of cipher mechanisms 144a and 144b, respectively.

The ciphertext message C2n is split into two n-bit data blocks En and Dn, which are mixed by balanced block mixer 146 to produce two n-bit mixed data blocks Xn' and Yn'. The two mixed data blocks are then decrypted using cipher mechanisms 150a and 150b to produce decrypted data blocks Xn and Yn. These decrypted data blocks are input to balanced block mixer 148 which mixes them to produce n-bit data blocks An and Bn which are then joined to produce the 2n-bit decrypted plaintext message P2n.

If An and Bn are each 64-bit data blocks, and the cipher mechanisms 144a, 144b, 150a and 150b are DES mechanisms, then the cryptographic mechanism in FIGURES 4(a) and 4(b) encrypts and decrypts 128-bit messages using DES. For example, the decryption mechanism 104 takes a 128-bit ciphertext (produced by an encryption mechanism 102), splits it in two 64-bit parts, En and Dn) and mixes it with balanced block mixer 146 to produce two 64-bit data blocks as inputs to two DES decryption mechanisms 150a and 150b (with the same or different keys, k1 and k2). The two 64-bit output data blocks from DES mechanisms 150a and 150b are each input to balanced block mixer 148 giving two 64-bit data blocks which are joined to produce the 128-bit message block P2n.

If the cipher mechanisms 144a and 144b are DES mechanisms, then functionally, the encryption of the message by cryptographic mechanism 100 of FIGURE 4(a) can be written as:

     P2n -> An, Bn
     MIXER140(An, Bn) -> (Xn, Yn)
     DES ENCIPHER144a(Xn, k1) -> Xn'
     DES ENCIPHER144b(Yn, k2) -> Yn'
     MIXER142(Xn', Yn') -> (En, Dn)
     Cn, Dn -> C2n

Similarly, the decryption of the ciphertext message C2n can be written as:

     C2n -> En, Dn
     MIXER146(En, Dn) -> (Xn', Yn')
     DES DECIPHER150a(Xn', k1) -> Xn
     DES DECIPHER150b(Yn', k2) -> Yn
     MIXER148(Xn, Yn) -> (An, Bn)
     An, Bn -> P2n

This construct ciphers a double-size DES block at nearly single DES rates. By increasing the block size of the cipher, its strength is potentially increased.

FIGURES 5(a) and 5(b) show another embodiment of a cryptographic mechanism 100 consisting of a combination of balanced block mixers and block cipher mechanisms to effectively double the input message block size of the block cipher mechanisms. The encryption mechanism 102 (FIGURE 5(a)) uses balanced block mixer 152, and the decryption mechanism 104 (FIGURE 5(b)) uses the inverse balanced block mixer 154. Cipher mechanisms 156a, 156b, 156c, and 156d (encryption mechanism of FIGURE 5(a)) are inverses of cipher mechanisms 158c, 158d, 158a, and 158b, respectively (decryption mechanism of FIGURE 5(b)). An n-bit plaintext input signal P is split into two n-bit data blocks, A and B. Each of these data blocks A and B is encrypted using cipher mechanisms 156a and 156b with the same or different keys, k1, and k2, producing two n-bit encrypted data blocks A' and B'. The two n-bit outputs A' and B' are mixed using balanced block mixer 152 to produce two n-bit data blocks X and Y. Data blocks X and Y are encrypted with cipher mechanisms (156c and 156d) using keys k3 and k4 (which can be the same or different from each other and from keys k1 and k2). The cipher mechanisms 156c and 156d produce n-bit data blocks X' and Y' which are joined to produce a 2n-bit output message signal C (ciphertext).

In the above, the sub-blocks A and B can be created by simply splitting the input block in the middle or by some other form of reversible (invertible) splitting. Similarly, sub-blocks X' and Y' may be joined by simple concatenation or by some other form of reversible accumulation.

Decryption of the ciphertext signal C by the cryptographic mechanism 104 is as follows (with reference to FIGURE 5(b)).

A cryptographic mechanism 100 decrypts a 2n-bit ciphertext signal C as follows. The signal C is split into two n-bit data blocks (corresponding to data blocks X' and Y'). These data blocks are deciphered by cipher mechanisms 158a and 158b, to produce two n-bit data blocks X and Y. Data blocks X and Y are mixed by balanced block mixer 154 (the inverse of balanced block mixer 152 of FIGURE 5(a)) to give two n-bit data blocks A' and B' which are then input to the two cipher mechanisms 158c, 158d to produce two n-bit data blocks A and B which are joined to form the 2n-bit plaintext signal P.

An alternate embodiment of an encryption mechanism 102 for a cryptographic mechanism 100 which ciphers at half the rate of the cipher mechanism it uses is shown in FIGURE 6, which uses, in combination, balanced block mixer 160, four exclusive-OR (XOR) mechanisms 164a-164d, and four cipher mechanisms 166a-d with cryptographic keys k1-k4. As in the other cryptographic mechanisms described herein that use more than one cryptographic key, the keys can be the same or different and the balanced block mixers can be the same or different.

In this cryptographic mechanism, a 2n-bit input message signal I is split into two n-bit data blocks A and B. Data block B is encrypted by cipher mechanism 166a, producing n-bit data block B' which is then combined with data block A using XOR mechanism 164a to produce n-bit data block A'. Data block A' is encrypted with cipher mechanism 166b to produce n-bit data block A" which is combined in XOR mechanism 164b with B (from the original input message) to produce n-bit data block B". Data blocks A' and B" are mixed by balanced block mixer 160, producing two n-bit data blocks C and D. Data block D is encrypted with cipher mechanism 166c, producing n-bit data block D' which is combined with data block C by XOR mechanism 164c to produce n-bit data block C'. Data block C' is encrypted by cipher mechanism 166d to produce n-bit data block C" which is combined with data block D by XOR mechanism 164d to produce n-bit data block D". Functionally, the encryption by the mechanism of FIGURE 6 can be written as follows:

     I -> A, B
     CIPHER(B, k1) -> B'
     XOR(A, B') -> A'
     CIPHER(A', k2) -> A"
     XOR(B, A") -> B"
     MIXER160(A', B") -> (C, D)
     CIPHER(D, k3) -> D'
     XOR(C, D') -> C'
     CIPHER(C', k4) -> C"
     XOR(D, C") -> D"
     C', D" -> O

The decryption mechanism 104 corresponding to encryption mechanism 102 described above is functionally written as follows, given a ciphertext message O:

     O -> C', D"
     CIPHER(C', K4) -> C"
     XOR(C", D") -> D
     CIPHER(D, k3) -> D'
     XOR(C', D') -> C
     INVERSE-MIX(C, D) -> (A', B")
     CIPHER(A', k2) -> A"
     XOR(B", A") -> B
     CIPHER(B, k1) -> B'
     XOR(A', B') -> A
     A, B -> I

Note that the individual ciphers need only encipher, while the structure of FIGURE 6 ensures that overall deciphering is possible.

The cryptographic mechanism 100 shown in FIGURE 7 ciphers (encrypts and decrypts) quadruple-size cipher mechanism message blocks at nearly single cipher mechanism rates, whereas that shown in FIGURE 8 ciphers quadruple-size cipher mechanism message blocks at nearly half single cipher mechanism rates. Thus, if the cipher mechanisms 168a-d and 170a-h in FIGURES 7 and 8 are DES cipher mechanisms, then the cryptographic mechanism 100 shown in FIGURE 7 ciphers quadruple-size DES blocks (i.e., 256-bit data blocks) at nearly single DES rates, and that shown in FIGURE 8 ciphers quadruple-size DES blocks at nearly half single DES rates. In FIGURE 7, I is a 4n-bit input message signal and the reference letters A, B, C, D, A', B', C', D', W, X, Y, Z, W', X', Y', Z', W", X", Y", Z", P, Q, R, and S represent n-bit data sub-blocks. The output signal O (ciphertext) of the mechanism is a 4n-bit signal.

Note that in order to propagate any input changes throughout the mechanism of FIGURE 7, four balanced block mixers 172a-172d are used, with one output data block of balanced block mixer 172a being an input to balanced block mixer 172d and one output data block of balanced block mixer 172b being an input to balanced block mixer 172c. Similar construction is used for balanced block mixers 172e-172h in FIGURE 7 and balanced block mixers 172i-172l in FIGURE 8.

To Part C: