Array device for data scrambling4177355Abstract This specification describes an array logic chip that can be used to encipher and decipher binary data. The array logic chip contains a matrix of input and output lines with the input lines divided into groups that are each addressed by a different decoder. The digits of a block of data to be encoded are arranged in sets according to the position of the digits in the block and a different set of digits is fed into each of the decoders of the array logic chip. Substitution of new digits for the original digits in each set is accomplished in the matrix by configuration of connections between a group of input lines and output lines of the arrays and in the decoders by changing the configuration of the decoders so as to vary the input lines of the matrix selected by the input signals to the decoders. Transposition or changing of position of the digits in the block of data is accomplished in the selection of the output lines to which any given group of input lines is connected. Multiple substitutions and transpositions are accomplished by readdressing the decoders with the coded data signals on the output lines of the matrix and dynamic encoding is accomplished by continuously reconfiguring the decoders and changing the couplings between input and output lines of the matrix. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
TABLE 1
______________________________________
Code # Code Description (.alpha., .beta.)
______________________________________
1 A,B
2 A,--B
3 --A,B
4 --A,--B
5 (A=B),A
6 (A=B),--A
7 (A=B),B
8 (A=B), --B
9 (A.noteq.B),A
10 (A.noteq.B), --A
11 (A.noteq.B),B
12 (A.noteq.B), --B
code #13-24 reversal of codes 1-12
______________________________________
The vertical personality (bits to be stored in the cells) for .alpha. and .beta. are:
TABLE 2
______________________________________
Personality Table
A --A B --B A=B A.noteq.B
______________________________________
1 0 1 0 0 1
1 0 0 1 1 0
0 1 1 0 1 0
0 1 0 1 0 1
______________________________________
For instance, assume the two input variables A and B are applied to the terminals of the first decoder 15a and the stages 28 and 30 of this decoder are store 0s. Then the decoder 18a is programmed to place AB input combination 00 on the first line, 01 on the second, 10 on the third and 11 on the fourth. Therefore code #6 in Table 1 can be implemented by placing two ones in the stages 20 of the shift registers associated with points 18a and 18b and at 18c and 18d as shown in Table 2. Clearly then any 2 by 2 code in Table 1 can be implemented in this array using one decoder for input lines and two output lines of the array by simply changing the personality of the array 10 in accordance with Table 2. Furthermore it should be apparent that any even number of digits n can be encoded using the 2 to 2 mapping described above as a kernel. The n input bits are divided into n/2, 2=bit groups, each group of 2 bits is placed in a different decoder 15 and goes through mutually independent 2 to 2 mappings as above. The resulting n bits are then arbitrarily permuted to yield the encoded word. The function of the G array or grouping array 42 is to group the n input bits into (the n/2) 2-bit groups mentioned above. Each row and column of the G array 42 contains one and only one digit in the data block. Each digit is placed on only one input line 44 and appears on only one output line 42. Each decoder 15a of the F array or Function Array 10 receives a single one of these groups of 2-bits and performs the 2 to 2 mapping according to the personality of the array along the input lines coupled to the decoder 12. Each decoder 15 is connected to four input lines in the F array 10 which are in turn connected by data in the shift register 22 to two and only two of the output lines 14. An output line associated with any decoder cannot be used to receive signals for any other decoder. For instance, if output line k is the result of the j.sup.th decoder, the personality of the array 10 along the k.sup.th output line would be all 0's except at those four intersections 18 of the k.sup.th line with the four input lines 12 coupled to the j.sup.th decoder. At those four intersections would be the appropriate 4-bit 2 to 2 mapping personality. Let us now consider the size of the array hardware and the number of codes, or the distinct mappings, the basic array offers. The latter, as mentioned earlier, is an indication of the code unbreakability. Again we are only considering the even word length. The Grouping array 42 contains n.sup.2 bits, and the Function array 10 contains 2.times.n.sup.2 bits. The total number of bits in the array is, then N.sub.B =3n.sup.2 (3) There are ##EQU1## ways of group n bits into n/2 groups of 2 bits each. There are 24/2=12 different order-independent 2--2 mapping functions per group. The final output ordering can be achieved in n! ways. Therefore, the total number N.sub.c of the codes delivered by the array device becomes ##EQU2## This number is very small when compared to the maximum N.sub.c of Eq. (1b). However, it is an enormous number by itself. Table 3 shows the log.sub.2 N.sub.c for some values of n. (If n=16, N.sub.c .apprxeq.10.sup.33.)
TABLE 3
______________________________________
log.sub.2 N.sub.c for some values of n
______________________________________
n log.sub.2 N.sub.c
2 4.584962501
4 14.33985
6 26.73859369
8 40.93826604
10 56.50693473
12 73.18068547
14 90.78123725
16 109.1799809
18 128.2797191
20 148.0043928
22 168.2928534
24 189.0948648
26 210.3684192
28 232.0778665
30 254.1925722
32 276.6859273
34 299.5346037
36 322.7179823
38 346.2177065
40 370.0173297
42 394.102031
44 418.4583863
46 443.0741789
48 467.9382441
______________________________________
To select a code in this array device, one should load an appropriate personality into the array. However, one need not handle 3n.sup.2 bits to specify the code. One can specify a key which represents the personality, which is much shorter than the personality length. The key to personality transformation should be simple to implement (either by software or hardware). The proposed key for an n to n mapping has the following format. Key=Frontal permutation, 2--2 functions, End permutation (a) The frontal permutation is used just for grouping the inputs. Since there are n! permutations, there are 2.sup.n/2 distinct permutations per distinct grouping. In this sense, the frontal permutation key is redundant and also many key specifications will give the same code. The Frontal permutation is given as n segments of log.sub.2 n bit strings, each representing the input number appearing in the decoders, top to bottom in order. Thus, for example, the frontal permutation of B, C, A, D means that: (i) the first decoder 15a gets inputs B and C in order, and (ii) the second decoder 18b gets inputs A and D in order, or more precisely, the personality of G array has all zeros except 2, 3, 1 and 4.sup.th columns of 1, 2, 3 and 4.sup.th row, respectively. As far as the inputs to F array is concerned, the frontal permutation specifies where the actual inputs are coming from. So we might say that this is a FROM list of permutation. B C A D FROM-Inputs to G A B C D TO-Inputs to F (b) The 2--2 functions portion of the key is in n/2 segments of 4 bit strings, each specifying the 2--2 function number corresponding to the 2 bit group of inputs. There are 12 distinct functions independent of permutation as given in Table 1. Since the end permutation will finally dominate, we take the functions in order (.alpha.,.beta.) as given by codes #1-12 of Table 1. (c) The End permutation list is a TO-permutation list of functions to final outputs. This portion consists of n segments of log.sub.2 n bit strings, each designating the output column of the corresponding function. Let us take an example key, given as (2, 3, 1, 4; 6, 7; 1, 2, 3, 4) for n=4. The personality for G array is already shown in FIG. 1. The two outputs from the first decoder group are realized in the 1.sup.st and the 2.sup.nd columns in order. The two output bits from the second decoder portion go to 3.sup.rd and 4.sup.th output columns. FIG. 1 again shows the F array personality for the above key. The number of bits in a key for an n to n coding is ##EQU3## The following is a list of N.sub.k for a few values of n.
__________________________________________________________________________
n 4 8 12 16 20 24 28 32 36 40 44 48
n.sub.k
24
64
120
160
240
288
326
384
504
560
616
672
__________________________________________________________________________
If we had an ideal key system (information loss-less) the key length should be log.sub.2 N.sub.c given in Eq. (4). This number for large n becomes ##EQU4## Now, one might say the proposed key has the efficiency of: ##EQU5## Again, as n becomes large the efficiency approaches 1. ##EQU6## This means that the key chosen is not only simple to implement but also fairly good in terms of efficiency. Now we consider the inverse mapping process. If a key is used in scrambling the data we call it the encipher key. Similarly a decipher key is necessary to unscramble the message. The problem is then how to translate an encipher key into a decipher key which establishes the inverse mapping. Recalling the construction of a key, for each 2-bit group we have, (1) two numbers; where they are from (front permutation) (2) one number; what mapping function (function) and (3) two numbers; where the transformed 2 bits are going. (End permutation) Therefore, the reverse process should take the two bits given by the end permutation (this becomes the FROM permutation for front), inverse the function (see Table 4), and put the resulting bits to where they came from (this becomes the TO permutation for end). Due to the set order in the functions, the final TO permutation for deciphering may be in reverse order of the enciphering from portion of the two bits. The encipher to decipher key translation process can be summarized as follows: (1) Copy the end permutation for the front permutation (2) Convert each function to its inverse function, (by Table 4). (3) Copy the front permutation for end permutation and pairwise reverse the order if necessary (see Table 4). For example if the encipher key for 10 to 10 coding were K.sub.E =3,7,5,10,9,8,2,6,4,1;3,9,7,12,6;5,8,7,1,3,2,9,6,10,4.
TABLE 4
______________________________________
Inverse Functions & End Order
End
Inverse Order
Function #
(.alpha., .beta.)=f(A,B)
function #
f.sup.-1 (.alpha., .beta.)
Change
______________________________________
1 A,B 1 A,B no
2 A, --B 2 A,B no
3 --A,B 3 A,B no
4 --A,B 4 A,B no
5 (A=B),A 7 B,A yes
6 (A=B), --A 12 B,A yes
7 (A=B),B 7 A,B no
8 (A=B), --B 12 A,B no
9 (A.noteq.B),A
11 B,A yes
10 (A.noteq.B), --A
8 B,A yes
11 (A.noteq.B),B
11 A,B no
12 (A.noteq.B), --B
8 A,B no
______________________________________
Using Table 4, K.sub.D =5,8,7,1,3,2,9,6,10,4;3,11,7,8,12;3,7,10,5,9,812,6,4,1. where the underline shows the order reversal of the pairs. The translation can take place from the decipher key to the encipher key using the same rules. This gives a choice of retaining either the encipher key or the decipher key with the code, which is an additional flexibility. We have discussed so far a static coding scheme where the code is fixed for some duration, until the key is manually changed. When the key is automatically changing in some predetermined sequence, we call it the dynamic coding. A simple method of achieving this is through circulating the personalities of the array by having the shift registers 22 in some shifting mode rather than statically storing data. Obviously, dynamic coding is much more difficult to break than the static one. The circulation of the data in the shift registers is done either in G array or F array or both. Once the starting key is set in, the personality of the arrays can shift circularly to left or to right at any predetermined word intervals. The circulation can be done at different intervals in F and G array. The only restriction is that the encoder's G array and decoder's F array must shift at the same intervals and the F (encoder) and G (decoder) must shift at the same intervals. These intervals can be fixed or specified by an additional key. One shift of G array cells corresponds to changing the Front-permutation key of the encoder by modifying each from-designation i to i+1 mod n. (Notice the inputs are numbered 0 through n-1.) Of course, if the shift direction is reversed, the modification is i to i-1 mod n. For the decoder, then, the end permutation must shift the same way. Therefore, the decoder should shift in the F array, to compensate the change. We give all possible examples of employing the above circulation-dynamic coding in the following Table 5. Arrows indicate the direction of circulation. S.sub.1 and S.sub.2 designate clocks. The clocks generate the shift-pulses for the arrays at some set word intervals. The most general form would be some arbitrary function on the word counts for Bidirectional shift registers.
TABLE 5
______________________________________
Many Modes of Circulation
Encoder Decoder
Case G F G F
______________________________________
a no no no no.rarw.static
b .fwdarw.S.sub.1
no no .fwdarw.S.sub.1
c .rarw.S.sub.1
no no .rarw.S.sub.1
d no .fwdarw.S.sub.1
.fwdarw.S.sub.1
no
e no .rarw.S.sub.1
.rarw.S.sub.1
no
f .fwdarw.S.sub.1
.fwdarw.S.sub.2
.fwdarw.S.sub.2
.fwdarw.S.sub.1
g .fwdarw.S.sub.1
.rarw.S.sub.2
.rarw.S.sub.2
.fwdarw.S.sub.1
h .rarw.S.sub.1
.fwdarw.S.sub.2
.fwdarw.S.sub.2
.rarw.S.sub.1
i .rarw.S.sub.1
.rarw.S.sub.2
.rarw.S.sub.2
.rarw.S.sub.1
______________________________________
Now, let us examine a trivial, yet a powerful way of making n to m (m>n) codes. Let m=n+k (k>0). The scheme is to simply extend the number of output columns of F array to m. An arbitrary k columns out of m are then personalized with a random 1's and 0's. The remaining n columns carry the same information as before. The number of array bits now becomes: N.sub.BE =3n.sup.2 +2nk (9) The number of distinct codes becomes (see Eq. (4)) ##EQU7## The k-columns contain extraneous or "garbage" information. The k-garbage columns have (15.sup.n/2 +1) distinct output functions each. The reason is, if any decoder portion of a column contains all 1's, the output becomes 0 regardless of inputs. There are, 2.sup.4 -1=15 ways of personalizing each decoder portion for all non-zero output functions. There are n/2 decoders. Hence, the result is, 15.sup.n/2 plus one for the null function on inputs. The encoder then has m=n+k columns in F array and the decoder should have m input columns in G array. Since the personality of the garbage columns does not have to be retained, the only change to the key would be that of specifying the permutations. Each designation in the end permutation of the encoder key and the front permutation of the decoder key would require log.sub.2 m bits instead of log.sub.2 n bits, i.e. ##EQU8## which is a modest increase, if any, compared to Eq. (5). The key efficiency is now somewhat meaningless, since the garbage function is not retained. Therefore, the key efficiency, calculated by Eq. (7) may well exceed 1 as k grows. The number of codes literally sky rockets by each addition of bits (k) as seen from Eq. (10). The numbers in Table 3 correspond to the case when n=m or k=0. One final comment on the Extended-codes as given above is that all the arguments for the circulation directly apply. Therefore, the extended codes can be made dynamic using the same shift register arrangements in the arrays. The only change is the size of the encoder's F array and the decoder's G array. A major advantage of the array scheme presented here is the fact that the whole coder hardware can be packaged in one LSI chip. The arrays and the support circuitry can be packaged in one of two chips. Such a chip in current technology could be built for about 30 input, output bit words, with the chip delay of 10 nano seconds or less, depending on technology. The implication is that the scrambling can be done in the interface of the memory and the CPU if desired. Also in time sharing, terminal oriented environment, the terminals can be equipped with the device. In APL, work spaces can be automatically scrambled with every save command. The scheme can be implemented in the regular array logic if desired. However, there will be some decrease in the number of code words with the regular arrays. The key can be abbreviated for the user if desired. The user may be assigned with a semi permanent permutation key corresponding to his user ID by the CPU, and he provides, for example, just the function key portion. Then he only has to deal with 2n key bits. The number of the codes is very high. However, if additional enciphering complexity is desired, one can cascade 2 codes (since one coder is only one chip) to obtain further scrambling. Of course, this can be done in more than 2 stages. These considerations are possible because of small hardware and delay in coding. Up until now we have been discussing the arrays as if the data stored in the stages 28 and 30 of each of the registers associated with decoders is 0. However, as pointed out previously, the data stored in each of these stages does affect which line is selected by any given combination of the two inputs to the decoders 15 therefore changing the data in the stages which has the same effect as changing the data along any given output line of the array and thereby enables the substitution of new digits for the original digits. Therefore it should be obvious to those skilled in the art that changes and improvements can be made to the present invention without departing from the spirit and scope of the invention.
|
Same subclass Same class Consider this |
||||||||||