Hardware arrangement for enciphering bit blocks while renewing a key at each iteration5442705Abstract A plaintext is enciphered using a plurality of stages in tandem via a plurality of iterations. Each of the stages is arranged to perform a complex key-dependent computation. The stage includes a memory for storing a key. A cipher function circuit transposes, using the key, one block applied to the stage from a preceding stage. An exclusive-or circuit implements an exclusive-or operation of the output of the cipher function and the other block applied to the stage from the preceding stage. A unique arrangement is provided for transposing the output of the cipher function circuit and then applying the output thereof to the memory. Therefore, the key is replaced with the output of the unique arrangement. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
TABLE 1
______________________________________
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
______________________________________
The permutation PC-1 discards the parity bits and transpose the remaining 56 bits as shown in the above Table 1. The result of the permutation PC-1 is then split into two halves C and D of 28 bits each. The blocks C and D are then successively circularly shifted left to derive each key K.sub.n (suffix n denotes n-th iteration and n=1, 2, . . . , 16 in this case). The key schedule of left shifts is shown in Table 2.
TABLE 2
__________________________________________________________________________
Iteration i
1 2 3 4 5 6 7 8 9 10
11
12
13
14
15
16
__________________________________________________________________________
Number of Shifts
1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
__________________________________________________________________________
Bit data Cn and Dn (n=1, 2, . . . , 16) obtained through the left circular shifts, are then decreased in number from 56 bits to 48 bits via permutation PC-2 shown in Table 3.
TABLE 3
______________________________________
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
______________________________________
The operation of the key scheduling section 10 is well known in the art and hence further descriptions will be omitted for the sake of brevity. The 16 keys K.sub.1 -K.sub.16 thus obtained are respectively applied to the stages S1-S16 and stored in corresponding memories M1-M16. As shown in FIG. 1, the stage S1 includes, in addition to the memory M1, a cipher function circuit F1, expanding permutation circuit E1 and an exclusive-or gate EX1 and EX-A1. The other stages S2-S16 each is configured in exactly the same manner as the stage S1 and thus, each of the counterparts is given the same notation plus an iteration number. After the stages S1-16 have respectively stored the keys K.sub.1 -K.sub.16, an initial 64-bit block of a plaintext is applied to the arrangement of FIG. 1 and then first subjected to an initial permutation IP (Table 4) at a circuit 12.
TABLE 4
______________________________________
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
______________________________________
After the initial block input of 64-bit is transposed under the initial permutation IP, the 64-bit block is divided into two halves L and R of 32-bit each and then undergo 16 iterations of a cipher function f and exclusive-or operations. Let T.sub.n (64 bits) denote the result of the n-th iteration, and let L.sub.n and R.sub.n (each 32 bits) denote the left and right haves of T.sub.n, respectively. Then, L.sub.n =R.sub.n-1 R.sub.n =L.sub.n-1 +f(R.sub.n-1, K.sub.n) where+depicts the exclusive-or operation. FIG. 2 is a sketch of the hardware arrangement implementing the cipher function f(R.sub.n-1, K.sub.n). R.sub.n-1 is first expanded to a 48-bit block, at a bit expanding circuit 14, using a bit selection table (Table 5).
TABLE 5
______________________________________
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
______________________________________
Subsequently, the exclusive-or of E(R.sub.n-1) (viz., the output of the expanding permutation circuit 14) and K.sub.n is implemented at the exclusive-or gate 16 and the result broken into eight 6-bit blocks B.sub.1, . . . , B.sub.8 which are respectively applied to eight selection (substitution) function circuits (S-boxes) S.sub.1, . . . , S.sub.8. These eight S-boxes circuits S.sub.1 -S.sub.8 output respectively 4-bit blocks which are concatenated together, and the resulting 32-bit block is transposed by a permutation circuit 18 using Table 6. The operations of S-boxes S.sub.1 -S.sub.8 are well known and disclosed in detail in the paper referred to in the opening paragraphs and hence will be omitted for the purpose of simplifying the disclosure.
TABLE 6
______________________________________
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
______________________________________
In the following, merely for the convenience of description, the operations of the n-th stage Sn (n=1, 2, . . . , 16) are discussed. The 32-bit block outputted from the cipher function circuit Fn is applied to the EXn to which the bit block L.sub.n is also applied. The EXn carries out an exclusive-or operation of the 32-bit block from Fn and the block L.sub.n, and the result of the operation is applied to the next stage S(n+1) as a block R.sub.i+1. As mentioned above, the first embodiment is to renew the key K.sub.n (n=1, 2, . . . , 16) after each transposition of data block at the corresponding stage Sn. To this end, the memory Mn, the expanding permutation circuit En and the exclusive-or circuit EX-An are provided in the stage Sn. The 32-bit block from the function circuit Fn is expanded to a 48-bit block using the above mentioned Table 5. Following this, the EX-An performs an exclusive-or operation of the 48-bit key K.sub.n and the 48-bit block outputted from En. Let the key K.sub.n currently stored in the memory Mn denote K.sub.old and let a new key denote K.sub.new, we have K.sub.new =K.sub.old +E(O)n wherein E(O)n depicts the output of the exclusive-or circuit EX-An. Thus, the key K.sub.n (i=1, 2, . . . , 16) stored in the corresponding memory Mn can be renewed or replaced after each transposition of data block at the corresponding stage Sn is finished. The data block outputted from the last stage S16 is subjected to the inverse of the initial permutation using Table 7. Thus, a ciphertext can be obtained from the arrangement of FIG. 1.
TABLE 7
______________________________________
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
______________________________________
As mentioned above, the key in each of the stages S1-S16 is subject to change after each iteration. Accordingly, the ciphertext obtained from the first embodiment is computationally much more infeasible to be broken as compared with the prior art. A second embodiment of the present invention will be discussed with reference to FIG. 3. The second embodiment is applied to DEC as in the first embodiment merely by way of example. FIG. 3 shows only one stage (viz., n-th stage (n=1, 2, . . . , or 16)) in that each of the other fifteen stages is arranged or configured in exactly the same manner as the n-th stage. The n-th stage Sn includes a memory Mn', two exclusive-or circuits EXn' and EX-Bn, a cipher function circuit Fn', an expanding permutation circuit En', and a memory 30(n), all of which are coupled as shown. The cipher function Fn' and the exclusive-or circuit EXn' are essentially the same as the counterparts Fn and Exn of FIG. 1. Further, the memory Mn' corresponds to Mn of FIG. 1, and the expanding permutation circuit En' operates in a manner identical to the counterpart En of FIG. 1. In the second embodiment, the key K.sub.n initially outputted from the key scheduling section 10 (FIG. 1) is retained in the memory Mn' and is not subjected to any renewal as in the first embodiment. The second embodiment is advantageous especially in the case where the ciphertext is subject to bit errors during encipherment and/or during data transmission. In more specific terms, the key K.sub.n initially applied is held in the memory Mn' and hence, even if a bit error occurs at a given stage and/or during data transmission, the bit disturbance caused by the bit error can be restored in a very short time. The memory 30(n) includes two memory stages MS1 and MS2 in this particular embodiment. The upper memory stage MS1 stores the bit block E(O)-1 applied thereto from the expanding permutation circuit En' at a given iteration. When the bit block E(O)-1 is stored in the memory stage MS1, the bit block which has been stored therein is transferred to the lower memory stage MS2. The bit transposition operation is controlled by the output (viz., key) of the exclusive-or circuit EX-Bn which is supplied with the key K.sub.n and the previous output E(O)-2 of the expanding permutation circuit En'. At the next iterated operation, the new bit block is stored in the memory stage MS1 as a new bit block E(O)-1. Thus, the old bit block E(O)-1 is transferred to the memory stage MS2 as a new bit block E(O)-2. The old bit block E(O)-2 is abandoned. Following this, the same operation is repeated. The operations of the circuits Fn' and EXn' have been discussed in connection with the first embodiment and as such, further descriptions thereof will be omitted. In FIG. 3, the memory 30(n) includes two memory stages MS1 and MS2 in this particular case. However, the memory stages can be increased wherein the output of the circuit En' stored in the last stage is applied to the exclusive-or circuit EX-Bn. A third embodiment of the present invention will be discussed with reference to FIG. 4. The third embodiment includes a memory 30(n)' having three memory stages MS1, MS2 and MS3. Other than this, the third embodiment is the same as the second embodiment. As shown in FIG. 4, the exclusive-or circuit EX-Bn is supplied with the three inputs from the memory Mn' and the memory stages MS2 and MS3. According to the third embodiment, a key applied to the cipher function circuit Fn' can be changed in a manner which renders more computationally infeasible to break the cipher as compared with the second embodiment. It will be understood that the above disclosure is representative of several possible embodiments of the present invention and that the concept on which the invention is based is not specifically limited thereto.
|
Same subclass Same class Consider this |
||||||||||