Efficient Method for Encrypting Superblocks of Data

This invention relates to arrangements for encrypting a buffer of data, the buffer comprising a plurality of blocks.

It is well known in the field of encryption that the longer the basic block of data which is being encrypted the more difficult it is to break the encryption. At the same time it is also much more complex to encrypt a very long block of data and this is one of the reasons why such arrangements as the Data Encryption Standard (DES) encryption scheme operate on only 64 bits at a time. Further, while arrangements such as the DES encryption scheme can be implemented in hardware and integrated circuits are now available which perform such encryption, these encryption schemes do not lend themselves readily and efficiently to the use of a processor under software control for performing the encryption. Accordingly, a problem in the prior art is that there is no efficient arrangement implemented largely in software for encrypting and decrypting data for storage in a storage device under processor control, for possible subsequent transmission.

In accordance with the principles of this invention, a superblock or buffer of data comprising a plurality of blocks, each block containing an integral number of words, is encrypted in the following way. First, each block is encrypted using a block encryption arrangement (such as a DES encryption or a simpler program-controlled encryption) and a first key. The outputs of these encryptors are organized into words and these output words from all of the encryptors are permuted according to a second key to generate the encrypted output. Advantageously, the second encryption key can have N! values which will make it very difficult to attack an encrypted message when N is a number such as 256 representing a buffer of 256 words (bytes) or 2,048 bits.

Decryption of the encrypted data is accomplished by placing the encrypted data into a buffer, performing the inverse permutation of the words, and applying block decryptors to obtain the original data buffer. This is simply the inverse of the encryption process described above; it requires no more effort than the encryption process, when the keys are known.

In one specific implementation of applicant's invention, only two keys are used, the same key being used for all of the block encryptors. Each block encryptor encrypts 8 bytes using the DES algorithm (in Electronic Code Book mode). The permuter then takes the 256 byte output of the 32 block encryptors and permutes the 256 bytes in conformance with a second key. This second key has 256! values and so it is computationally infeasible to break an encoding using key-searching methods.

FIG. 1 is a block diagram of an encryption arrangement in conformance with the principles of this invention;

FIG. 2 is a flow diagram illustrating the principles of the invention; and

FIG. 3 is a block diagram of a block encryptor that is easily implemented in software.

FIG. 1 is a block diagram which illustrates the operation of the invention. In the figure, N is the number of words in the input buffer, and in the output buffer; m is the number of bits in each word; n is the number of bits processed by a single block encryptor; k is the number of block encryptors necessary to process the input buffer. Thus, each block encryptor handles n/m words, and there are nk/m=N words in the buffers.

One buffer of the plain text to be encrypted is originally stored in an input buffer, 10, N words long. A convenient size for the word is an 8 bit byte. For processors using a different length word, 16 or 32 bits might be more convenient. The input buffer, which is stored in data store 5 of processor 2, is N words long and in this specific implementation N is 256. The buffer may be thought of as consisting of an integral number of blocks of convenient length. In this specific implementation, each block is 64 bits or 8 words long so that the buffer stores 32 blocks each 8 words long. Each of these blocks is then encrypted by block encryptors 1 using any convenient encryption algorithm such as the DES algorithm and the output of each block encryption is organized into an integral number of words. The words from all encrypted blocks are then permuted (box 11) using a second key. The permuting process is particularly easy to perform in a program controlled processor 2, comprising a central processing unit 3, a data store 5, and a program store 4 in the following way. The key consists of 256 different addresses, each address representing the permuted location in the output buffer 12 of one of the words of the block encrypted data. The output of the block encryption process is read consecutively and stored into the memory locations of the output buffer 12, also in data store 5, addressed by consecutive addresses of the permuting key, thus placing the fully encrypted output into proper slots of the output buffer. The keys are stored in the data store, and may be derived directly or indirectly from password data.

FIG. 2 is a flow chart of the method corresponding to the block diagram of FIG. 1. Block 20 indicates that the input buffer is first filled with plain text data (action box 20). Each block of the plain text data is then encrypted into intermediate data using the first key (action box 22). The words of intermediate data are then permuted using a second key (action box 24) and the permuted results are stored into an output buffer (action box 26).

A tradeoff can be made in the system between the length of the block and the length of the buffer. Clearly, the longer the buffer the more impervious the permuting process to brute force decryption. This permits the use of relatively less sophisticated block encryption arrangements while still retaining a high level of assurance that the encrypted message cannot be decoded without knowledge of the key.

In order to make unauthorized decryption more complex, any incomplete plain text buffer should be completed with random data. This avoids the situation wherein, for example, the last part of a buffer comprises blocks of all zeroes or of all spaces which results in a plurality of blocks identical in their unencrypted, therefore, also in their block encrypted form.

Many block encryption methods, such as the DES, were designed to be inefficient to implement in software. This invention permits the use of a simpler, more efficient block encryptor to be used, while retaining high overall resistance to unauthorized decryption. An alternate embodiment of this invention, which is easily and efficiently implementable in software, consists of 64 block encryptors (each 4 bytes wide) operating on a 256 byte buffer, followed by a permutation of the 256 bytes. Each 32-bit block encryptor consists of 4 DES-like rounds implemented with look-up tables, which are derived from the key (see FIG. 3). This embodiment, implemented in software on a common microprocessor, is so efficient that encrypting a disk sector requires less time than writing the encrypted sector to disk.

FIG. 3 is a block diagram of an encryptor that is easily implemented in software. Four bytes (32 bits) of information are originally stored in input buffer 301 and are encrypted for storage in output buffer 303. The encryption process uses 4 table look-up operations (blocks 310, 312, 314, and 316) and 12 circuits for performing the exclusive-or (XOR) sum of two one byte inputs (circuits 320, 322, 324, 326, 328, 330, 332, 334, 336, 338, 340, 342). At the first level, block 310 accesses one of 256 3-byte entries in a look-up table that is derived from the block encoding key. Block 310 is addressed by the first byte from the input buffer and its output is combined by XOR with the contents of the second, third, and fourth bytes of the input buffer in XOR circuits 320, 322, and 324, respectively. The first byte is also one input to XOR circuit 326 in the second stage of encoding. The output of XOR circuit 320 is used to address the look-up table in block 312 and the output of block 312 is combined with the first byte in XOR circuit 326 and the outputs of circuits 322 and 324 in XOR circuits 328 and 330, respectively. The output of XOR circuit 328 is used to address the look-up table in block 314 and the output of block 314 is combined with the outputs of XOR circuit 326, XOR circuit 320 and XOR circuit 330 in XOR circuits 332, 334 and 336. Finally, the output of XOR circuit 336 is used to address the look-up table in block 316 and the output of block 316 is combined with the outputs of XOR circuits 332, 334, and 328, in XOR circuits 338, 340, 342, respectively. The outputs of XOR circuits 338, 340, 342, and 336 are the inputs of output buffer 303. While the operation of the encryptor of FIG. 3 has been described as a circuit, it can be readily seen that a program controlled processor, such as processor 2, can perform the look-up operations of blocks 310, 312, 314 and 316 and the XOR combination of circuits 320, . . . , 342.

In an alternative embodiment, a single key can be used for both the block encryption and the permutation. The permutation key can be used to supply in replicated form, or in some other simply derived form such as three successive bytes, the output of the look-up operation blocks 310, 312, 314, and 316. This design choice leads to a less perfectly random block encryption, but avoids the necessity of deriving two keys. In other alternative embodiments, several tables of keys are used to encrypt blocks, and the different tables are used for successive blocks or successive messages. This improves encryption at the cost of deriving a longer encryption table.

It is to be understood that the above descriptions are only of two embodiments of the invention. Numerous other arrangements may be devised by one skilled in the art without departing from the spirit and scope of the invention. The invention is thus limited only as defined in the accompanying claims.