Key controlled block-cipher cryptographic system employing a multidirectional shift matrix4195200Abstract A cryptographic system for enciphering a block of binary data under the control of a unique key consisting of a set of binary symbols. A clear message represented in binary data format is transformed into a cipher message (and vise versa) by operating on blocks of clear information utilizing the operations of directional shifting of a derivative form of said clear data in a multidimensional matrix shifting and storage device. Further, cryptographic power is introduced to the system by performing a non-affine substitution operation during a shift operation on segments of information stored in said matrix. The shifting function, as well as the substitution function, is a function of said unique key. The system is further mathematically invertible, that is, the same hardware may be utilized for both encipherment and decipherment by merely reversing the sequence of operations. Claims What is claimed is: Description CROSS REFERENCE TO RELATED APPLICATIONS
TABLE I
______________________________________
CELL-CLASS ELEMENTS
______________________________________
Left Edge L C.sub.0, C.sub.3, E.sub.3.
Top Edge T C.sub.2, C.sub.3, E.sub.2.
Bottom Edge B C.sub.0, C.sub.1, E.sub.0.
Right Edge R C.sub.1, C.sub.2, E.sub.1.
Entire Array A All Cells
-L and -B = A I.sub.1, I.sub.2, ..., I.sub.6, E.sub.1, E.sub.2,
C.sub.2.
______________________________________
In the above table the first four lines are believed to be self-explanatory. The fifth line denoting the entire array A is similarly self-explanatory. The sixth line defines the group of cells A as the entire array (A) less the cells of the bottom and left edges. For purposes of the present embodiment a clock pulse series CL-L, CL-B, and CL-A are specified to activate subsets of desired elements of the array for the various operations. In certain instances it is desired to isolate the operation of the left edge L and the bottom edge B and accordingly circuitry is provided for doing this. For edge operations R and T, it is sufficient to activate the entire array and accordingly corresponding clock pulses CL-R and CL-T are not required. Before proceeding with a specific detailed operation of the system with respect to the flowcharts of FIGS. 4 and 5 and the specific hardware of FIGS. 2 and 7, there will now follow a general description of the cryptographic algorithm insofar as the operation of the bidirectional shift register or array is concerned. As stated previously, the array is first completely loaded with a complete block of data to be transformed (either encrypted or decrypted) and the unique user key is loaded into the key register provided therefor. At this point the transformation process begins. First a predetermined key bit is examined and depending upon whether the key is a 1 or a 0, either a column or a row shift will occur. It should be clearly understood that the row or column shift which occurs is not merely a single row or column shift but a complete rotation of the contents of the array in either of the two specified directions. Thus, if there are eight rows and columns as in the present embodiment where the array comprises an eight by eight matrix there must be eight individual shifting or rolling operations for a cycle or a round to be completed. It is also obvious that something must happen to the data between shifts or at the completion of a round the register would be identical to its appearance at the start. In the present embodiment, two transformation functions occur during the shifting or rolling operation. The first is a substitution transformation and the second is an exclusive-or with the contents of the row or column position into which the substituted data byte is combined. Thus, as many shifts occur utilizing this transformation characteristic as is necessary to complete a round. At this point, reference should be made to the example of FIGS. 6A and 6B which illustrate diagrammatically what happens to the contents of the array during an encipherment and a decipherment round, respectively. This figure represents a row shifting operation, it being clearly understood that a column shift would operate in exactly the same way except that the rolling or shifting would be orthogonal to the row shifting disclosed. Referring now to FIG. 6A it will be noted in the box marked step 1, that the four rows, each contain a letter. This letter represents the original binary data format. It should be noted of course, that only four rows are shown in the present example, although in the embodiment there are eight rows disclosed in the shifting array. The first operation that occurs between step 1 and step 2 is the extraction of the data represented as A and the passing of this data through the substitution step. This procedure forms S(A). This latter expression indicates that a new data byte has been obtained from the substitution step, which is a function A. This new data byte is in turn exclusive-or'd with a binary value D previously stored in the lower row of the array. This new total byte which is stored during step 2 is represented as D .sym. S(A). In step 3 the array is rolled up by one row and the data represented as B passed through the substitution box and in step 4 exclusive-or'd with the quantity A which was in the bottom row as a result of step 3, to produce the new bottom row content A .sym. S(B). This process continues until step 8 which is the last operation in the round. At this point the bottom row becomes C .sym. S(D .sym. S(A)). Thus the content of the bottom row is actually a double substitution function. FIG. 6B illustrates the reversibility of this process. Thus, in step 1 of the decipher round the substitution function is taken of the upper row which operation produces the term S(D .sym. S(A)) which is the second term of the quantity C .sym. S(D .sym. S(A)) currently resident in the bottom row. These two quantities are exclusive-or'd together with the result that the two substitution functions cancel out leaving the value C which is written into the bottom row in step 2. The array is now rolled down since this is a decipher function and the new content of the array as shown in step 3 has the value C in the upper row which again is passed through the substitution step and exclusive-or'd with the bottom row of the array to produce the resultant value B as shown in step 4. This operation continues through step 8 and it will be noted that the final content of the array at the termination of the decipherment round is identical to that at the start of the encipherment round. It will be clearly understood that this example constitutes only one round of encryption which is performed on a given block of data and that there are in reality many such key-controlled rounds performed, each one of course, being dependent upon the particular key bit interrogated. In the present embodiment there are 64 such rounds. However, the precise number would depend upon the degree of cryptographic security required. The above example illustrates how, with a given round, the decipherment produces the original data from an encipherment starting point. However, it will of course be obvious that an identical key bit must of necessity be present in the key register at the time of decipherment, as for encipherment. This is illustrated, by way of example, in the following Table 2 wherein each of the four numbers represent a byte of key, it being presumed in this case that there are four bytes which would produce four transformation rounds. In actuality of course, and in the specific example there are many more than four such rounds. However, to proceed with the example set forth in Table 2 the rolling or advancing of the key register with successive rounds of encryption proceeds as illustrated. This table is organized like FIGS. 6A and 6B and broken into two sections, one for encipherment and the other for decipherment. It should be clearly understood that the key rolling concept illustrated in Table 2 occurs on a round basis rather than an operation basis as with the previously described example illustrated in FIG. 6. Thus once a key byte (2 bits E and D) are at the access position of the key register they remain there until a round is completed, that is, a complete rolling operation of the array. The hardware for accomplishing the shifting of the key register will be described subsequently. The right-hand or grid portion of the table indicates the actual key bytes which would be in the key register at any given time position. Each of the numbers as stated previously represents a key byte but in this particular embodiment comprises two bits. Although only four bytes are shown in the example, the disclosed embodiment would normally require sixty-four such bytes or one hundred twenty-eight total bits, since there are sixty-four array rounds utilized. Referring to the figure, the upper row represents the initial state after loading of the key register with the user supplied unique binary key. During an encipherment operation, the first thing that occurs is that the key register is rolled left (RKL). With the key register in this first permuted position, the first array permutation occurs. Subsequent to this the register is again rolled followed by further permutation etc. until the terminal configuration of the key register occurs (bottom row) which, it will be noted, is the same configuration that the register started with.
TABLE 2
______________________________________
KEY REGISTER SEQUENCING (EXAMPLE)
______________________________________
ENCIPHER
##STR1##
DECIPHER
##STR2##
______________________________________
Upon each successive round it will be noted that the key register is rolled or shifted to the left with the end bit being moved around to the right most or interrogation position. On the decipherment transformation the system must use the initial loading of the key register without rolling for the first decipherment permutation. This is indicated clearly in the right-hand portion of the table. In the hardware this is accomplished by setting the first-bit-group flag in a deciphering transformation which prevents the initial rolling of the key register such as occurs during an initial encipherment round. As with encipherment, with each round, the key register is shifted but in the opposite direction with the result that the key is applied in the reverse order which, as will be apparent, is necessary for a proper decipherment of an encrypted message. It may thus be seen that by operating the key register in the manner described with respect to Table 2, a proper ordering or accessing of the key register occurs automatically for encipherment and decipherment to maintain the proper order of presentation of the key material. Further, although only four bit groups are shown in the Table, the operation would be identical regardless of the number of bit groups utilized insofar as the shifting of the key register between rounds is concerned. Having thus generally described the operation of the system with respect to the rolling of the bidirectional shifting matrix or array 10 and the rolling or shifting of the key register 26, it is believed that the basic transformation concept utilized in the present system is apparent. Further, the reversibility of the algorithm and hardware has been clearly demonstrated in the above example and description. The remainder of the description will be directed to the description of the flowcharts which indicate the specific function performed by the hardware and finally a description of the system hardware itself, especially as set forth in FIGS. 2 and 7. What must be accomplished by the hardware is when a block of data is received which must be transformed, it must first be determined whether or not it is to be enciphered or deciphered. Next the data must be appropriately loaded into the bidirectional shifting matrix or array 10 and then the transformation operations must proceed under control of the user supplied key. The number of transformation rounds are predetermined and the array must be appropriately shifted together with the performance of the substitution and exclusive-or operations in the proper sequences together with the rolling of the key register as appropriate. In addition, the number of rounds performed must be continuously monitored so that the proper number are performed and finally the transformed block of data must be gated out of the matrix. As is apparent from the above description, the primary functional units of the present system are the bidirectional shifting array 10, the substitution device 20 together with the addressing circuitry therefor which performs the substitution, the exclusive-or block 21 and the shiftable key register 26. The control system 28 basically controls the shifting access (i.e., multiplexer control) and shifting direction of the array, the shifting direction of the key register 26 and the gating of data around the various data paths making up the system. The control system 28 will be more specifically described with reference to FIG. 2 (2A and 2B) subsequently, however, it essentially comprises a read only memory 40 with series of microprogram sequences stored therein and various decoders, branch condition tests, setable control latches, etc., which are operable in conjunction with the output of said microprogram sequences to effect the required control operations of the system. The functions of the microprogram sequences will be apparent from the following description of FIGS. 4 and 5, however, in addition a list of microprogram sequences is included subsequently in the specification. Referring now to FIG. 4, which is a high level, overall flowchart for the operation of the system, a start signal which could be an operator controlled button, switch etc. initializes the system, which causes a flag in the system to be set indicating that the first block of data is ready to be transformed, i.e., is a new message. Additionally, a first bit group flag (FBGF) is set in case a decipher operation is being performed, since, as indicated previously, with a decipher the rolling of the key register must be inhibited during the first decipherment round. Finally, a cipher/decipher flag must be set to indicate whether the operation to be performed is encipherment or decipherment. This would normally be done by the system testing an operator controllable switch. The system then proceeds to block 2 entitled "Load Key Register", which causes the unique user key to be gated into the shiftable key register 26. The system then proceeds to block 3 of the flowchart, wherein a test is made as to whether this is the first block, or the beginning of a message, to be transformed by the system. If the answer is "yes", the system proceeds to block 4 entitled "Load Array", wherein the new block of data is transferred from the input memory buffer 12 into the array 10. Block 4 proceeds to block 5 which causes the previously reset first block flag to be set to a one so that the system will know that the next round is not a first block operation, so that the system can proceed to block 6 via the test made at block 3. If the test in block 3 had resulted in "no", the system would have proceeded to block 6, which in addition to loading the array 10 with a new block of data to be transformed, would concurrently cause the current contents of the array to be gated to the output memory buffer. The contents of the array would have been transformed by the preceding array operation. The output of blocks 5 and 6 proceed to block 7 entitled "Array Operations". The details of the array operations are covered in FIG. 5 to be described subsequently and basically cover the actual cryptographic transformation which occurs within the system. At the end of an array operation the system proceeds to block 8 wherein a determination is made as to whether the block just transformed was the last block of the message or not. If not, the system returns back to block 3; if so, it proceeds to block 9 and causes this last transformed block of message data to be gated out into the output memory buffer 14 and terminates the cryptographic transformation operation. FIG. 5 which comprises FIGS. 5A and 5B, comprises a medium level flowchart of the operations which occur in the present system for performing a cryptographic transformation on an individual block of data which is gated into the bidirectional shifting array 10. The operations performed in the flowchart of FIG. 5 are those alluded to as "Array Operation" in block 7, FIG. 4. It will be understood that the start point of the flowchart on FIG. 5A and the terminate point of the flowchart on FIG. 5B represent the entrance and exit portions, respectively, of block 7, FIG. 4. Before proceeding with the explanation of FIG. 5, several terms should be redefined for clarity. A "round" is a complete rolling or shifting of the shifting array to reconstitute all of the rows or columns thereof as was described previously with respect to the examples of FIGS. 6A and 6B. The actual number of rounds is discretionary with the system designer although generally the more rounds the greater the cryptographic power of the system. In the present embodiment sixty-four such rounds are utilized which requires that the round counter be set to 64 upon initialization of the system and, each time a round is completed, the counter is decremented until it finally reaches zero, signifying the completion of the "array operation". Also, as described previously with respect to FIG. 6, a number of "operations" must be performed each time a row or column is transformed and the array is shifted. In the example of FIG. 6A these operations are shown as taking two steps for purposes of description, however in the present embodiment, each such reconstitution or transformation of a given row or column of the array and the requisite shifting is performed in a single "operation". Accordingly, since the array of the present embodiment contains 8 rows and 8 columns, the complete round involves 8 operations which necessitates an "operation counter" being utilized to control this function which is set to eight initially at the beginning of a round and decremented as each operation occurs. To proceed now with the description of an array operation as shown in FIG. 5, block 1, entitled "Preset Round Counter to 64", as previously explained causes the round counter shown in FIG. 2B to be reset to sixty-four. The system then proceeds to block 2, where a determination is made, by testing the status of the C-D flag, whether the system is in a cipher or decipher mode. If the mode switch is set to decipher, the system branches to block 3, wherein the first bit group flag is tested. If it is set to a "0" the system branches to block 5 which causes the first rolling of the key register to be deleted as will be remembered in the previous description of Table 2. Block 5 also causes the first bit group flag to be set to a "1" so that the next round will cause the system to proceed to block 4 rather than block 5 wherein the key register is rolled to the right. If the test in block 2 had caused the system to branch to block 6 this would have indicated a cipher operation and block 6 would have caused the key register to be rolled to the left again, as explained with reference to Table 2. The system, regardless of any of the above three branches, now proceeds to block 7, since this path is entered only at the beginning of a round, the operation counter is initially preset to numeral 8. The system then proceeds to block 8 wherein the initial substitution function is selected as a function of the "E" field of the key register. It will be understood that the remainder of the substitution function is selected as a function of the actual bit configuration of the row or column of the array which is gated to the substitution block. The function of block 8 is to cause this byte to be gated to one of two possible substitution matrices. At this point the system proceeds to block 9 wherein the setting of the "D" field of the key register is interrogated to determine whether it is a row or column operation, if a row operation, in the present embodiment, "D" would have been set to a "0" and vice versa. Assuming a row operation, the system proceeds to block 10. What actually occurs at this point between blocks 9 and 10 is the automatic gating of the data byte in the top (T) or right (R) edge of the array into the substitution device 20, through the multiplexer 22. Concurrently, the data byte in the bottom (B) or the left (L) edge is gated into the exclusive-or 21 through multiplexer 24. The other input to the exclusive-or 21 is the output W from the substitution device 20. In turn the output Z from the exclusive-or 21 is caused by block 10 to be over written into the bottom row, (B). The system then proceeds to block 11 wherein the C-D flag is again interrogated and, depending on the operating mode of the array, is caused to roll up in block 12 or down in block 13. Returning briefly to block 9, if the column operation were to be performed the system would have branched to block 14 with the same result as the branch to block 10. In other words, the proper output Z from the exclusive-or 21, this time based on a column operation, would be gated into the left column (L) or edge of the array 10. In block 15, the C-D flag is tested, if a decipher operation, the system branches to block 16 which causes the array to be rolled to the left. If the cipher mode is being performed the system branches to block 17 which causes the array to be rolled to the right. The output of blocks 12, 13, 16 and 17 (only one of which can be entered during any one cycle) all proceed to block 18 which causes the operation counter to be decremented. The setting of the operation counter is tested in block 19 and if it is not set to "0" (from eight) the system branches back to block 9 and the interim loop is repeated until the operation counter goes to "0" at which point the system proceeds to block 20. This means that a complete row or column shifting operation is completed and that the round counter may be decremented in block 20. Block 21 causes the round counter itself to be interrogated and if it is not set to "0" (from 64) the system returns to block 2 and a new round is begun with an appropriate shifting of the key register. The system thus repeats itself until the round counter is finally set to zero indicating that all rounds of encryption have been completed and thus the current block has been cryptographically transformed. At this point the system proceeds to block 22 wherein the first bit group flag is reset to zero (to allow proper operation of the system in the decipher mode). The output of block 22 returns the system control to block 8 of FIG. 4. Having thus described the flowchart of FIGS. 4 and 5 the overall operation of the system and the functions which are performed thereby will be clearly understood. The specific hardware means by which these functions are performed, especially in the bidirectional shifting array 10, will be clearly understood from the following description of the preferred embodiment of said array which is shown in FIGS. 7A through 7B (FIG. 7). The description of FIG. 7 together with the array operations and controls of Table 3 and the cell-multiplexer input assignments of Table 4 will clearly indicate how the bidirectional shifting matrix operates. Referring to FIG. 7 each of the actual storage cells utilizes the same cell nomenclature or designation as that used in the previous description of FIG. 3. Thus, the four corner cells are C.sub.0 through C.sub.3, the edge cells area E.sub.0 through E.sub.3 and the interior row of cells are I.sub.1 through I.sub.6. FIG. 7 shows complete line details including multiplexers for all eight cells of the left edge L of the array an exemplary number only, of the other four edges and one of the interior row cells I.sub.16. It is believed that this diagram together with Table 4 will very clearly indicate all of the required multiplexer input connections for every cell in the array. Further, reference to Table 3 will indicate which of the possible inputs to a given cell must be selected for each of the eight possible array operations. As mentioned previously, each of these cells of FIG. 7 has its own input multiplexer (MPX). Certain of these cells require larger multiplexers, i.e., all of the cells of the left column and bottom row have eight possible inputs, although all eight are not necessarily used. This is to allow the selection of a desired input for a particular cell from among a relatively large number of possiblities which are determined by the particular array operation being performed.
TABLE 3
__________________________________________________________________________
ARRAY OPERATIONS AND CONTROLS
MPX ADDRESS
ARRAY CELL-CLASS SUB-ARRAY CLOCKS
ARRAY OPERATIONS MNEMONIC
C B A C.sub.0
C.sub.1
C.sub.2
C.sub.3
E.sub.0
E.sub.1
E.sub.2
E.sub.3
I.sub.1-6
L B A
__________________________________________________________________________
ROLL ARRAY LEFT RAL 0 0 0 R R R R R R R R R x x x
ROLL ARRAY DOWN RAD 0 0 1 T T T T T T T T T x x x
ROLL ARRAY UP RAU 0 1 0 B B B B B B B B B x x x
ROLL ARRAY RIGHT RAR 0 1 1 L L L L L L L L L x x x
LOAD ARRAY LDA 1 1 1 Q L L Q L L L Q L x x x
OVERWRITE BOTTOM ROW
OBR 1 0 1 Z Z d d Z d d d d x
OVERWRITE LEFT COLUMN
OLC 1 1 0 Z d d Z d d d Z d x
__________________________________________________________________________
DEFINITIONS
R: RIGHTADJACENT CELL OUTPUT
T: TOPADJACENT CELL OUTPUT
B: BOTTOMADJACENT CELL OUTPUT
L: LEFTADJACENT CELL OUTPUT
Q: DATA SOURCE (FROM INPUT MESSAGE BUFFER)
Z: OUTPUT OF EXCLUSIVEOR FUNCTION BLOCK (XOR)
d: DON'T CARE (IRRELEVANT)
x: GIVEN SUBARRAY CLOCK IS REQUIRED
Thus referring to table 4, the first line references cell C.sub.0. As indicated in the table the possible inputs to this cell via its associated multiplexer, are E.sub.01, E.sub.31, C.sub.3, C.sub.1, Z.sub.7, Z.sub.0, or Q.sub.0. The top row of Table 4 shows the column headings related to the mnemonics which specify the particular operations to be performed. These mnemonics are defined in Table 3. The second row of Table 4 labeled CBA illustrates for the present embodiment the required setting of the cell MPX address control lines which are appropriately labeled and shown in the upper portion of FIG. 7A. It is these lines which actually select the particular multiplexer input for a given cell which is to be subsequently fed into and stored in the cell upon the occurrence of the appropriate sub-array clock pulses appearing on the lines designated CL-L, CL-B, and CL-A. As will be apparent from Table 4, certain of the cells only have four possible inputs, such as all of the cells of rows I.sub.1 through I.sub.6, cells of E.sub.2, E.sub.1, and C.sub.2. Thus, referring to FIG. 7D, the multiplexer for cell I.sub.16 has the four possible inputs E.sub.11, I.sub.26, E.sub.06, I.sub.15. All possible inputs to the multiplexers of each and every cell in the array is specifically designated in Table 4 as well as the multiplex address configuration which will select the particular designated input. It will be noted in Table 4, also, that a number of the interior and edge cells as stated previously only have four possible inputs. Referring to the FIG. (7) it will be noted that all of these cells only have the B and A multiplex address control lines going thereto as the third address control line C is not necessary for the selection. Referring again to Table 3, all of the information in Table 4 is essentially present in a much coarser form plus required timing information for the sub-array clock designated on FIG. 7 as CL-L, CL-B, and CL-A. These latter sub-array clocks control the gating data from the output of the multiplexer into the actual storage cell when the appropriate clock line is energized. As explained previously, the designation L refers to the left column or edge of the array, the designation B refers to the bottom row or edge of the array and the designation A refers to all of the rest of the array except L and B. The left-hand most column of the table (3) specifies the particular one of the eight operations which must be performed by this system at various times. The second column, entitled "mnemonic", is self-explanatory. The third column, designated "MPX address", specifies the binary configurations of the three multiplex address control lines CBA. The column designated "array cell-class" specifies the source for the signal to be gated into the cells of a particular cell class. Finally, the right most column entitled sub-array clocks specifies which clock pulses must be given or be present at the same time during the shift cycle for the various operations specified in the array operations column. A list of definitions is included at the bottom of the table for convenience of reference. It will be noted that the formation in the three interior columns of Table 3 may be expanded to provide the specific wiring diagram data of Table 4. Referring again to the right-hand column entitled sub-array clocks, it will be noted that for the first four operations namely the rolling operations as well as the load and unload operations, all three sub-array clocks must be present and are so designated. Conversely for the over-right bottom row, and over-right left column operations only the B and L clocks respectively are required. Having thus described the operation and wiring details of the bidirectional shifting register shown in detail in FIG. 7, especially when taken in conjunction with Tables 3 and 4, the source of the basic control signals are provided by the control mechanism as shown in FIG. 2 (2A and 2B). As stated previously, the heart of the control mechanism is the control store or read only memory 40 which has present therein a plurality of microprogram sequences having specific binary configurations which are interpreted by the decoder 42, the address portion of the input multiplexer 44 and the selecting circuitry of the control latches 46 for producing the control signals, addresses, etc., required by the system as will be well understood by those versed in the art. All of the outputs from the blocks 42, 44 and 46 are clearly labeled, the particular situations under which the various lines are actuated will be apparent from the subsequent microprogram sequence chart which is tied directly into the flowcharts of FIGS. 4 and 5. These sequence charts indicate which operations occur and the sequence of occurrence. As is well known with such read only memory and micro sequence control systems each instruction implies the address of the next instruction in the sequence (i.e., next memory location) and, if a branch is required, specifies the branch to address which would be loaded into the memory address register 48 if a branch were to be taken or conversely the address register would merely be incremented if no branch were involved. The primary difference between the outputs from the decoder 42 and 46 are merely the type of signal that is produced. Thus the output of the decoder 42 produces a relatively short pulse which exists only during a particular instruction whereas the outputs from the control latches 46 once set, remain set until cleared. Referring specifically to FIG. 2B in the upper portion thereof, the key register 26 is shown. The lines, at the left of this register marked C.sub.k perform the functions of loading the key register, and initiate the shifting of the register either to the right or to the left, depending upon whether a decipherment or an encipherment is occurring. The two output lines designated D and E are the two fields which control the row or column shift selection, and the substitution function selection respectively. Referring to the bottom of FIG. 2B the upper three outputs from the control latches 46 are connected to AND circuits to establish a clock mask for the sub-array clocks CL-L, CL-B, and CL-A. These clock pulses, as stated previously, determine which cells are to be energized during certain operations. The next two outputs from the control latches 46 establish a clock mask to provide clock pulses to the input and output message buffers. The three bottom lines from the control latches 46 designated CBA are the array multiplexer address control lines which select the proper inputs to the individual array cells. The system clock 50 is a conventional clock which controls the sequencing of the read only memory 40. The memory buffer register 52 performs the conventional function of receiving data words gated out of the control store from whence appropriate fields may be selectively gated in the input multiplexer 44, the memory address register 48, the decoder 42, or the control latches 46. Methods of selecting and setting binary bit patterns to effect the control functions desired in these units are well known in the art and would be obvious of those skilled in designing read only memory control systems. The three blocks at the top of FIG. 2A designated "first block flag", "first group flag", and "cipher/decipher flag", are the latches mentioned previously which are used in certain operational sequences to control the operation of the system as will be well understood. Similarly the three blocks entitled, load counter, round counter, and operation counter perform the following functions. The load counter controls the loading and unloading of the array. It requires eight sequences to do this and thus produces eight control pulses. The round counter, as stated previously, is set initially to 64 and is consecutively decremented as each round is completed. This counter basically keeps track of the number of rounds performed and, when the count reaches zero, indicates that transformation of a block of data has been completed. The operation counter is initially set to eight and decremented with each operation which as is required to complete a full transformation round within the array, whether row or column. The following microprogram sequece chart specifies in considerable detail and specific hardware operations required to operate the disclosed embodiment, i.e., it clearly indicates the sequences, operations, branching tests, etc., which are required. It will be noted that the individual sequences are directly coordinated with the flowcharts of FIGS. 4 and 5 by the appropriate numerical designations of each sequence. In the flowcharts the first or left-most digit group of the instruction number refers to FIGS. 4 or 5, the second digit group relates to the specific block of FIGS. 4 or 5 and the last bit group refers to the step in the particular sequence making up that block. Thus, for example, the microprogram steps 5-13-2 would refer to FIG. 5, block 13 and the second microprogram step required to perform the function "roll array down". It is believed that the meaning and function of these microprogram sequence charts is completely self-explanatory, however, several examples will be described subsequently.
______________________________________
MICROPROGRAM SEQUENCE CHART
OVERALL SYSTEM CONTROL OPERATIONS
In-
struc-
tion
No. Function Performed
______________________________________
4-1-1 SET DECODER TO 1, (SET FBF TO 0)
4-1-2 SET DECODER TO 12, (SET FBGF TO 0)
4-1-3 SET DECODER TO 4, (STRB CDF)
4-2 SET DECODER TO 2, (LD KEY REG)
4-3 SET INPUT MULTIPLEXER (IMPX TO 2)
IF IMPX = 0, GO TO 4-4
IF IMPX = 1, GO TO 4-6
4-4-1 SET DECODER TO 13, (clears control latches)
4-4-2 SET DECODER TO 14, (This action causes
appropriate bits on MBR output bus to be
latched into the Control Latches such that
CP-B, CP-L, CP-A, C, B, A, IMB are equal to
1, and OMB equals 0.)
4-4-3 SET IMPX TO 5.
4-4-4 TRIGGER LOAD COUNTER, (The load counter will
transmit 8 pulses to the OR gate 43 to effect
the loading of the array. When 8 pulses
have been emitted, the Load Counter will emit a
"borrow" (BW) signal and enter its quiescent
state).
WHEN IMPX OUTPUT LINE = 1, GO TO 4-5
(i.e., when BW received from Load Counter)
4-5 SET FIRST-BLOCK FLAG = 1.
4-6-1 SET DECODER TO 13.
4-6-2 SET CONTROL LATCHES OUTPUTS CP-L, CP-B,
CP-A, IMB AND OMB = 1
4-6-3 SET IMPX TO 5, AND TRIGGER LOAD COUNTER.
(Load Counter will emit 8 pulses to OR gate,
then emit BW pulse to IMPX and go to quiescent
state).
WHEN IMPX OUTPUT LINE = 1, GO TO 4-7
4-7 GO TO 5-1.
4-8 SET IMPX TO 3.
IF IMPX = 0, GO TO 4-3
IF IMPX = 1, GO TO 4-9
4-9-1 SET DECODER TO 13.
4-9-2 SET DECODER TO 14. (Appropriate bit on MBR-Bus
is strobed into OMB latch, OMB=1).
4-9-3 SET IMPX TO 5, (TRIGGERS LDCTR)
WHEN IMPX OUTPUT LINE = 1, TERMINATE SYSTEM
OPERATION.
ARRAY OPERATIONS
5-1 SET DECODER TO 7, (SET RNDCTR)
5-2 SET IMPX TO 0.
IF IMPX = 0, GO TO 5-6
IF IMPX = 1, GO TO 5-3
5-3 SET IMPX TO 1
IF IMPX = 0, GO TO 5-5
IF IMPX = 1, GO TO 5-4
5-4-1 SET DECODER TO 3. (This generates a momentary
output pulse on line #3 on Decoder ("Roll
Key Reg"). This pulse initiates a 2 bit shift
sequence in the key register; direction is
controlled by the CDF).
5-4-2 GO TO 5-7
5-5-1 SET A-BUS TO 11 (ELEVEN).
(FBGF TO 1)
5-5-2 GO TO 5-7
5-6-1 SET DECODER TO 3. (see note under 5-4-1)
5-6-2 GO TO 5-7.
5-7 SET DECODER TO 9.
(Line #9 out of Decoder, "SET OPCTR",
presets the number 8 into the Operation
Counter).
5-8 SELECT SUBSTITUTION FUNCTION
(This function is performed via hardwired
connection from "E" bit of key register to
Substitution Device 20. Explicit control
action from the Microprogrammed Control
System is not required).
5-9 SET IMPX TO 4.
IF IMPX = 0, GO TO 5-10
IF IMPX = 1, GO TO 5-14
5-10-1
SET DECODER TO 13. (This clears the
Control Latches.)
5-10-2
SET DECODER TO 14. (This action causes
appropriate bits on the MBR Bus to be latched
into CONTROL LATCHES such that CP-B, C, and A
equal 1, and all others equal 0).
5-10-3
SET DECODER TO 10 (TEN).
(Pulses "CELL CLK" output which gates XOR 21
into B (bottom row)).
5-11 SET IMPX TO 0.
IF IMPX = 0, GO TO 5-12
IF IMPX = 1, GO TO 5-13
5-12-1
SET DECODER TO 13. (clears control latches)
5-12-2
SET DECODER TO 14. (Appropriate bits on BUS
are latched into Control Latches such that:
CP-L, CP-B, CP-A, B = 1; C, A = 0 which will
result when the "cell clock" pulse occurs --
in the "Roll Array Up" operation).
5-12-3
SET DECODER TO 10, ("cell clock")
5-13 (SAME AS STEP 5-12, except cell MPX address
controls, CBA = 001).
5-14 (SAME AS STEP 5-10, except: CBA = 110, and CP-L
(instead of CP-B) equals 1).
5-15 SET IMPX TO 0.
IF IMPX = 0, GO TO 5-17
IF IMPX = 1, GO TO 5-16
5-16 (SAME AS STEP 5-12, except CBA = 000).
5-17 (SAME AS STEP 5-12, except CBA = 011).
5-18 SET DECODER TO 8, (decrements OPCTR)
5-19 SET IMPX TO 7,
IF IMPX = 0, GO TO 5-9
IF IMPX = 1, GO TO 5-20
5-20 SET DECODER TO 6. (decrements round counter)
5-21 SET IMPX TO 6.
IF IMPX = 0, GO TO 5-2
IF IMPX = 1, GO TO 5-22
5-22-1
SET DECODER TO 12. (resets FBGF)
5-22-2
GO TO 4-8.
______________________________________
It will be noted in the above Microprogram Sequence Charts that there is extensive explanatory material with various microprogram steps which explain the function of the particular microprogram step insofar as what it does in the hardware system. It will be noted that in a number of the microprogram steps such as 5-13, it is stated that it is the same 5-12, with the exception noted, rather than completely repeating instructions 5-12. The microprogram sequence charts specify the particular lines in the input multiplexer (IMPX), the decoder and the control latches which are activated by the various microprogram instructions. As will be obvious to those skilled in the art, a particular field of the instruction stored in the read only memory, and thus the memory buffer register 52, will be transferred to the appropriate control mechanism to select a particular desired line or emit a required signal. It will also be noted that certain blocks of the flowcharts of FIGS. 4 and 5 do not have a specific microprogram instruction as they are implicit in the system design, i.e., hardwired functions which remain connected at all times and which are activated when data is gated out of the array. Thus, with step 5-8 the "substitution" function, a particular half of the substitution block, (switch or decoder) is selected by the "E" field from the key register which will automatically direct the 8 bits from the array into the substitution block which again is hardwired and will produce a specific 8 bit output for a given 8 bit input. Control branches are handled as follows. By way of example, refer to instruction number 5-9. In the flowchart of FIG. 5 a test is made to determine whether a row or column operation is being performed. Thus, instruction 5-9 specifies that the IMPX is set to 4. This means that the input multiplexer looks at its input line 4 which is connected to the "D" field of the key register, and if this line is set to a 0 the controls within the memory address register cause the address stored therein to be simply incremented which means the system will next access instruction 5-10. If on the other hand the input to line 4 had been a 1 the control logic associated with the memory address register (MAR) would parallel load into the MAR the "branch to 5-14" address present in that field of the memory buffer register output bus that feeds into the MAR. It will be noted from the above description, that the statement, "set unit to" means that a particular line, either input or output of the specified unit is selected by the instruction. It is believed that the above Microprogram Sequence Chart together with the included annotations, clearly sets forth the operation of the present crypytographic system and that any operation as specified in the flowcharts of FIGS. 4 and 5, may be readily followed insofar as the hardware ramifications are concerned by appropriate reference to the Microprogram Sequence Charts and the hardware drawings of FIGS. 1 and 2. CONCLUSIONS The previous description of the microprogram sequence chart completes the description of the disclosed preferred embodiment of the present cryptographic system. While the above embodiment constitutes a preferred form of the invention, it is to be understood, however, that many changes in form and detail could be made by those skilled in the art which would result in a somewhat different looking architecture. For example, a square matrix, i.e., 8 by 8 has been disclosed as this is a conventional byte size in many classes of computer systems and is accordingly a convenient data block to utilize in such a block cipher cryptographic system. This of course results in the encryption of a sixty-four bit block in any one cycle of operation of the system. However, a different matrix size or even a non-square matrix could also be utilized without altering the concepts of the present invention. Similarly sixty-four rounds have been disclosed, however, a greater number or a smaller number could be utilized by appropriately changing the setting of the round counters and making certain that the same number of rounds are utilized both for encryption and decryption. Closely connected with the number of rounds is the size of the unique user supplied key. For the present embodiment it has been assumed that a one hundred twenty-eight bit key is available (64.times.2) however, the size of the key could also be varied without too much difficulty. While a single key bit, i.e. "E" has been utilized to give a twofold increase in the substitution complexity it will be readily understood that more than one key bit could be utilized as well as the eight data bits in a row or a column to add an even greater degree of complexity and cryptographic security to the system. Further, the specific details of the disclosed two dimensional shifting array are considered to be representative of an optimal design, however, it should be readily understood that other forms of the array would also be realizable in a more conventional form such as a series of 8 bit shift registers capable of having data gated in serially at either end, or in parallel and appropriately interconnecting the registers. As a still further variant of the shifting array, it would be possible to utilize a three dimensional array and utilize three or more shifting coordinates. In this instance at least a 2 bit "D" field would be required. These and other modifications could readily be made by skilled systems designers without departing from the spirit and scope of the present invention. It is also possible that the concept of the invention could be realized in software in a somewhat more cumbersome form.
|
Same subclass Same class Consider this |
||||||||||