Abstract:
A method and apparatus for use in encrypting and decrypting digital communications converting an initial block to final block based on freely selectable control information and secret key information. The apparatus or method having a plurality of units or steps operating on plain text or cipher text to provide a final block. The steps or methods including three modulo operations having unique modulus and meeting a specified constraint.

Description:
BACKGROUND OF THE INVENTION 
     The invention is directed to encrypting and decrypting blocks of digital data, more specifically, to a cipher method and device for the block-by-block conversion of a first digital block into a second digital block using at least one freely selectable control block. 
     The rapidly growing use of digital communication systems in commerce has spurred the need for cryptographic systems which are secure against popular &#34;cryptoanalysis&#34; or cracking techniques at least for a sufficient length of time. Prior art systems such as Massey, et al. U.S. Pat. No. 5,214,703 use a block cipher device which is suitable both for the encryption of plain text blocks and for the decryption of ciphertext blocks. However, prior art systems cannot be designed with any input/output size by appropriately scaling the size of system operations and are susceptible to existing cracking techniques. In addition, use of this cryptographic apparatus guarantees that any communications equipment will be interoperable only if all are using this same cryptographic apparatus. 
     Accordingly, it is an object of the present invention to provide a novel scaleable block cipher device. 
     It is another object of the present invention to provide a novel block cipher device which overcomes the disadvantages of the prior art. 
     It is yet another object of the present invention to provide a novel method of converting an initial block to a final block for use in encrypting and decrypting digital communications. 
     It is still another object of the present invention to provide a novel block cipher device having multiple stages which is suitable for encrypting and decrypting digital information. 
     It is a further object of the present invention to provide a novel method for use in encrypting and decrypting information which minimizes the possibility of signal interception. 
     It is yet a further object of the present invention to provide a novel block cipher device which is scaleable and customizable. 
     It is still a further object of the present invention to provide a novel block cipher device which is not vulnerable to standard cryptoanalysis techniques. 
     These and many other objects and advantages of the present invention will be readily apparent to one skilled in the art to which the invention pertains from a perusal of the claims, the appended drawings, and the following detailed description of the preferred embodiments. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic representation of a communication system operating in block cipher feedback mode using a block cipher device according to the present. invention. 
     FIG. 2 is a schematic representation communication system operating in minimum error propagation mode using a block cipher device according to the present invention. 
     FIG. 3 is a schematic representation of a communication system operating in self-synchronizing cipher feedback mode using a block cipher device according to the present invention. 
     FIG. 4 is a block diagram of a block cipher device according to the present invention. 
     FIG. 5 is a schematic representation of the block cipher device shown in FIG. 4. 
    
    
     DESCRIPTION OF PREFERRED EMBODIMENTS 
     With reference now to FIG. 4, a block cipher device 100 is non-recursive and may include an input unit 10, eight units 1-8, an output unit 11, and a key scheduling unit 9. 
     The input unit 10 and output unit 11 assemble and buffer input and output data to and from the block cipher device 100. The structure of the input unit 10 and output unit 11 generally depends on an application (e.g., serial or parallel). The input unit 10 and output unit 11 are not unique to the block cipher device 100. 
     The block cipher device receives three input variables, X, Z 1 , and Z 6  and produces an output variable, Y. X is the primary traffic input to the block cipher device 100 and Y is the primary traffic output. Z 1  and Z 6  may be externally applied variables. Z 6  may be a secret &#34;Key&#34; variable which is input to the block cipher device 100 via a secure channel (e.g., a courier with sealed cover) prior to encryption or decryption. Z 1  (or &#34;customer algorithm modification&#34; variable) and subunits of Z 1  (i.e., Z 2 , Z 3 , Z 4 , and Z 5 ) are operated on in the first, second, third, fourth, and fifth units 1, 2, 3, 4, and 5 of the block cipher device 100. The output Y of the block cipher device 100 is a unique function of the primary traffic X, the Key variable Z 6  and the variable Z 1 . 
     The first, fifth, sixth, and eighth units 1, 5, 6, and 8 may consist primarily of modular arithmetic logic gates. The seventh unit 7 performs a non-invertible operation (for example, a mid transform). Units 2 and 4 perform &#34;nibble swapping.&#34; The third unit 3 provides a custom operation substituting or expanding a block based on Z 3 . The key scheduling unit 9 receives an externally applied input variable, Z 6 , and deterministically generates two pseudo random key blocks, Z 7  and z 8 . The key blocks Z 7  and Z 8  are used as operands in the fifth unit 5 and the eighth unit 8, respectively. 
     To facilitate the description, FIGS. 1, 2, 3, and 5 illustrate 64 bit block implementations. 64 bit blocks are used only as an example. Generally, in 64 bit block implementations, each unit includes at least a 64 bit input/output space. A block cipher device of the present invention having any input or output size can be designed by appropriately scaling the size of block cipher device operations. 
     With reference now to FIG. 5, the first unit 1 performs a modulo 2 addition (Exclusive-Or) on primary traffic input X with variable Z 1  resulting in first unit 1 output W 1 . 
     The second unit 2 performs a nibble swap operation. The second unit 2 segments W 1  into 8 pairs of nibbles; each nibble holding 4 bits. The second unit 2 transposes each segment based on Z 2  (e.g., bits 0-7 of Z 1 ) resulting in second unit 2 output W 2 . For example, when the value of bit &#34;0&#34; in Z 2  is equal to binary &#34;1&#34; then the order of the nibbles pair &#34;0&#34; will be transposed. Likewise, if bit &#34;0&#34; in Z 2  is equal to binary &#34;0&#34; then the order is left unchanged. The order of each nibble pair will be determined by the value of the corresponding bit in Z 2 . The value of bit 0 controls the order of nibble pair 0, the value of bit 1 the order of nibble pair 1 continuing through to bit 7 which controls the order of nibble pair 7. 
     The third unit 3 is a custom unit providing a custom substitution and expansion operation. The custom operation with inputs W 2  and Z 3  and output W 3  may be inserted into the block cipher device 100 in the form of a look-up table. Z 3  may be bits 24 through 31 of Z 1 . Providing a custom unit allows unique system variants to be designed and provided while meeting the requirements of secure cipher design. For example, the customized substitution or expansion operation of a look-up table is only disclosed to intended end users. 
     The fourth unit 4 may be another nibble swap operation where W 3  is segmented into 16 nibbles. Z 4  (for example, bits 24 through 31 of Z 1 ) controls the re-ordering of W 3  in a slightly different manner than explained for the second unit 2. For example, when the value of bit &#34;8&#34; in Z 4  is equal to a binary &#34;0&#34; then the first nibble in the pair will be written to the first position in the high order segment of W 4  and the second nibble will be written to the first position in the low order segment of W 4 . When the value of bit &#34;8&#34; in Z 4  is equal to a binary &#34;1&#34; then the two nibbles will be transposed before being written to W 4 . As with the second unit 2, the re-ordering of each nibble pair will be determined by a corresponding bit in Z 4 . 
     The fifth unit 5 performs a modulo addition operation. W 4  and Z 7  are operands of the fifth unit 5. W 4  is the output of the fourth unit 4 and Z 7  is an output from the key scheduler unit 9. The modulus q of the operation is determined using Z 5  by the following relation: 
     
         q=2.sup.128 -Z.sub.5                                       (equ. 1) 
    
     Z 5  may be bits 33 through 64 of Z 1 . The sixth unit 6 performs a modular cubing operation. In other words, W 5  is raised to the third power modulo p and the result is designated as W 6 . The modulus p is determined by the following relation: 
     
         p=2.sup.125 -X                                             (equ. 2) 
    
     The variable X is chosen such that the greatest common denominator between the order of the operation &#34;3&#34; and (p-1) is equal to 1. This is captures in the following equation: 
     
         GCD(3, p-1)=1                                              (equ. 3) 
    
     The seventh unit 7 performs a non-invertible operation such as an operation known as a mid transform. The input to the operation, W 6 , is 128 bits in length and the output of the operation, W 7 , is 64 bits in length. The mid transform simply maps bits 64 bits of the input to a 64 bit output. For example, the mid transform may map bits 30 through 93 of W 6  to bits 0 through 63 of W 7 . The rest of the bits in W 6  are discarded. 
     The eighth unit 8 performs another modulo addition operation. W 7  and Z 8  are operands of this unit. W 7  is an output from the seventh unit 7 and Z 8  is an output from the Key Scheduler 9. The modulus of the operation is chosen as 2 64 . The output of this stage is the output of the block cipher device and is designated as Y 1 . 
     Although specific values are specified for moduli of the first, fifth, sixth, and eighth units 1, 5, 6, and 8, the objective of the block cipher device will be satisfied by a range of choices. It is required, however, that the constraint of equ. 3 be satisfied and that a unique modulus be used in each stage. The &#34;modulo&#34; units 1, 5, 6, and 8 along with &#34;non-invertible&#34; unit 7 are not segmentable into a set of lower level operations. 
     The key scheduler unit 9 comprises a first function unit 12, a second function unit 13, a third function unit 14, shift register 15 and a mod 2 add logic gate 16. 
     The key scheduler unit 9 processes key variable Z 6  to produce variable Z 7  and Z 8 . Z 7  and Z 8  are used during the block cipher device operation. Z 9  is an output of the third function unit 14 and is stored in the shift register 15. The third function unit 14 may be a deterministic function operating on Z 6 . The contents of the shift register are shifted to the right one bit at a time until its content have been completely recirculated. With each shift, the least significant bit in shift register 15 is mod 2 added to the output of first function unit 12. The result being moved into the most significant bit position of the shift register 15. When the contents of the shift register 15 have been completely processed, the shift register is output as Z 7 . Z 7  is input to the second function unit 13 to produce Z 8 . 
     The first function unit 12 may be a custom look-up table mapping, for example, six one bit inputs to a single one bit output. Each of the inputs to the first function unit 12 is a tap connected to an individual bit position in the shift register 15. The tap locations may be arbitrarily chosen with the following constraint: no tap can be connected to either the least significant or to the most significant bit positions of the shift register 15. The first function unit 12 must meet secure design. For example, a design for the first function unit may be customized and disclosed only to an intended end user. 
     The second function unit 13 performs a bit-wise mod 2 sum without carry of the higher and lower order halves of Z 7  to produce Z 8 . The third function unit 14 performs a bit-wise mod 2 sum without carry of variable Z 6  and a custom bit pattern of equal length to produce variable Z 9 . The custom bit pattern is disclosed only to an intended end user. 
     When required, the value of the original key variable Z 6  may be recovered by first reloading Z 7  into shift register 15. Shift register 15 is then shifted to the left one bit a time until its content have been completely recirculated. With each shift, the most significant bit in the shift register 15 is mod 2 summed to the output of the first function unit 12. The result is moved into the least significant bit position of shift register 15. When the contents of shift register 15 have been completely processed, it is input to third function unit 14. In the third function unit 14, the custom bit pattern is bit-wise mod 2 summed to reproduce Z 6 . 
     The block cipher device may be operated in various modes such as a self-synchronizing cipher feedback mode (SSCFB), a minimum error propagation (or counter) mode (MEP), or a block cipher feedback mode (BCFB). 
     With reference now to FIG. 1 illustrating a BCFB mode, a block of unencrypted data or &#34;Plain Text&#34; (PT) is applied to the input of the encrypter 500 labeled PT,. PTE is then modulo 2 added to a block of &#34;Key Stream&#34; KS. KS represents the output of the block cipher device 100-1. CT represents the resulting block (i.e., cipher text). CT is output at the port labeled CT E  and is then transmitted over a channel 200. In the next iteration, CT is fed back as input to the block cipher device 100-1. The block cipher device processes the fed back block to produce a new block of KS. KS is then combined with the next block of PT and the encryption process continues. At the decrypter 600, received CT is represented by CT D . CT D  is combined with a block of KS to produce as output a block of recovered plain text PT D . The CT D  block is simultaneously applied to the input of the block cipher device 100-2. The block cipher device 100-2 uses the CT D  block as input to produce another block of KS. This KS block is used to process the next block of CT D . This mode is intended for relatively error free communication channels. 
     With reference now to FIG. 2 illustrating a MEP mode, unencrypted data or &#34;Plain Text&#34; PT is applied to the input of the encrypter 500 labeled PT E . PT E  is then modulo 2 added to a block of KS to produce a block of cipher text. CT is output at a port labeled CT E  and is then transmitted over the channel 200. For a next iteration, encrypter counter 300-1 is incremented and the output of the counter 300-1 is input to the block cipher device 100-1. The block cipher device 100-1 processes to produce a new block of KS. The new block of KS is then combined with the next block of PT and the encryption process continues. At the decrypter 600, received CT is represented by CT D . CT D  is combined with a block of KS to produce as output a block of recovered plain text PT D  and decrypter counter 300-2 is incremented. The block cipher device 100-2 uses the output of the counter to produce another block of KS. This KS block is used to process the next block of CT D . This mode is intended for noisy or error prone communication channels. A toggled bit error on the channel will likely result in only a one bit error on PT D . In other words, in this mode the cryptographic system will likely have only one bit of error extension. 
     With reference now to FIG. 3 illustrating a SSCFB mode, unencrypted data or &#34;Plain Text&#34; (PT) is applied one bit at time to the input labeled PT E . Each PT E  bit is modulo 2 added to a bit of KS to produce a bit of cipher text CT. Encryption continues until another iteration is initiated. Another iteration may begin when either the entire block of KS is consumed or when the pattern detector 400-1 is triggered. The pattern detector 400-1 continually monitors CT for a specific bit sequence and when the sequence is detected a new iteration is triggered. Because CT appears statistically random, this mechanism will initiate a new iteration at pseudo-random intervals. When a new iteration is initiated, all remaining KS is purged from the key buffer 401-1 and the most recent bit block of CT, CT E , is input to the block cipher device 100-1. The block cipher device 100-1 uses the most recent block as input to produce another block of KS. The new block of KS is stored in the key buffer 401-1 and is used to continue the encryption process. At the decrypter 600, the received CT is applied one bit at time to input labeled CT D . Each CT D  bit is modulo 2 added with a bit of KS to produce a bit of recovered &#34;Plain Text&#34; as output PT D . The CT bit stream is simultaneously applied to the input buffer 402-2 (CB1) of the block cipher device 100-2. When either the input buffer 402-2 becomes full or the pattern detector 400-1 triggers, the following will occur: 
     1) the key buffer 401-2 is purged; 
     2) the most recent block of CT, CT E , is input to the block cipher device 100-2; 
     3) the block cipher device uses the most recent block of CT to produce a new block of KS; and 
     4) the new block of KS is stored in the key buffer 401-2. 
     The block cipher device 100-2 continues processing and CT D  continues to be shifted into input buffer 402-2 until another iteration is initiated. This mode is intended for communication channels that are subject to synchronization errors. In this mode, a communication system will be able to automatically recover from loss cryptographic and block boundary synchronization. 
     To operate in any of the modes shown in FIGS. 1-3, the encrypter 500 and the decrypter 600 must first be initialized such that their internal states are all identical. Initialization may be obtained using an initialization vector &#34;IV&#34; which is generated on the encrypter side and is used to initialize all internal states of the encrypter. The IV is then transmitted over the channel 200 to the decrypter 600. Using the IV, all internal states of the decrypter 600 are initialized to the same values. 
     While preferred embodiments of the present invention have been described, it is to be understood that the embodiments described are illustrative only and the scope of the invention is to be defined solely by the appended claims when accorded a full range of equivalence, many variations and modifications naturally occurring to those of skill in the art from a perusal hereof.