Buffered cyphering.

0001This invention relates generally to buffered cyphering, i.e., to systems and methods for encrypting and decrypting digitally represented data streams using buffering to increase the throughput of data communications.

0002Techniques for encrypting and decrypting digitally represented data are well known in the prior art and are generally used to prevent the unauthorised access of data. These techniques are most commonly used in situations in which data must be communicated from one point to another. Classically, such a situation may be one in which data must be transmitted over a communications link from a transmitting station to a receiving station, which stations are separated by a substantial distance. However, encryption and decryption may also be used when security is a concern in the transfer of data from a central processing unit to a relatively remote unit, such as a disk storage device.

0003The process of taking data to be encrypted, which will hereinafter be referred to as plaintext, and transforming this data into an unrecognisable form, which will hereinafter be referred to as ciphertext, can seriously impact data processing system performance. Simply stated, it takes time to encrypt plaintext into ciphertext and more time to decrypt ciphertext back into plaintext. When data requiring encryption and decryption is communicated frequently, the capability of the encryption and decryption hardware and/or software can be easily saturated.

0004Many systems and techniques for encrypting and decrypting data are taught in the prior art. One example is shown in U.S. Patent 4,642,424. Figure 3 of that patent illustrates an encryptor used in the system described by that patent. Within the encryptor hardware a pair of registers is shown, as well as a pair of logic gates through which data or control signals are conveyed. While such an encryptor (and corresponding decryptor) may be relatively efficient, in terms of minimising delays and maximising throughput, those skilled in the art will understand that the hardware delays inherent in such systems can be substantial, especially as the number of registers and stages within the system, through which the data and other control signals must pass, increases.

0005In stream cipher operations, such as those described in U.S. Patent 4,471,164 and in the text by Karl H. Meyer and Stephen M. Matyas, <u style="single">Cryptography: A New Dimension in Computer Data Security</u>, pp. 53-61, John Wiley &amp; Sons (1982), the unencrypted plaintext is combined through some mathematical operation with a secret sequence of data bits, known as the cryptographic bit stream, to produce ciphertext. When the ciphertext is received, it is similarly, mathematically operated upon with a cryptographic bit stream to reproduce the plaintext. For a specific example, the same secret cryptographic bit stream may be used at both transmitting and receiving ends and the mathematical operation may be that of EXCLUSIVE-ORing the plaintext and the cryptographic bit stream to produce the ciphertext at the transmitter and then, again, EXCLUSIVE-ORing the ciphertext and the cryptographic bit stream at the receiving end to reproduce the plaintext.

0006With such stream cipher systems, the generation of the cryptographic bit stream is typically accomplished by use of a key and a particular algorithm which takes the key and generates the same stream of data bits each time the key is used. Thus, use of the key and the cryptographic bit stream generating algorithm at both the transmitting end and the receiving end yields identical cryptographic bit streams at both ends for use in the encryption and decryption process. Probably the greatest impact to real time, secure transfers of data using such a process is the fact that the generation of the cryptographic bit streams with the algorithms and keys is a time consuming process which has been accomplished in real time in prior art systems while data was held up for encrypting prior to transmission and for decrypting upon reception.

0007The process of generating the stream cryptographic bit stream, with this inherent delay, can be improved by using a simpler or less sophisticated algorithm with the key; however, while this may improve performance, security may be compromised in that the cryptographic bit stream may be more easily duplicated by unauthorised persons seeking access to the data.

0008Another approach for improving this throughput problem involves the use of higher performance processing or computing capability in generating the cryptographic bit stream with the key and the algorithm. That is, with faster computing capability, the real time generation of the cryptographic bit stream from the algorithm and key is accomplished with greater speed and, therefore, less delay. However, this solution poses an obvious impact in costs, since it usually requires a jump from the use of one processor to another processor in a higher performance family of processors. The cost of this hardware difference may be an order of magnitude.

0009It would, therefore, be of great benefit to achieve a substantial improvement in the throughput of enciphering and deciphering data without compromising its security or substantially increasing the hardware costs associated with these enciphering and deciphering operations.

0010The present invention provides a method for ciphering - encrypting and/or decrypting - data in a data processing system, comprising: generating a cryptographic bit stream, in advance of and thus independently of receipt of data to be ciphered; buffering the cryptographic bit stream upon its generation; and retrieving the cryptographic bit stream, or sufficient thereof, form the buffer and combining it with the data to be ciphered using it, as that data is received.

0011Accordingly, in contrast with the obvious drawbacks of the aforementioned delays inherent in enciphering and deciphering hardware due to the temporary storage of data in, or passage of data through, registers and gates, respectively, this invention advantageously uses buffering, whether for encryption and/or decryption processes by generation of the cryptographic bit streams in advance of their needs by the system and storing these cryptographic bit streams in buffers until they are needed, whereupon the cryptographic bit streams are instantly available for combination with the plaintext (at the transmitter) and ciphertext (at the receiver) for encryption and decryption, respectively.

0012An encryption mechanism, such as a processor programmed in accordance with an appropriate algorithm, has applied thereto an encryption or decryption key and initialising values. The encryption mechanism generates a cryptographic bit stream which is an intermediate stream of generated values. This intermediate stream is then stored in a buffer until plaintext data is presented for encrypted transmission, at which time the series of bits of the cryptographic bit stream are conveyed from the buffer to a mathematical function, for combination with the plaintext, to produce the ciphertext which is transmitted to the receiver.

0013At the receiver a similar process has taken place in advance of reception of the ciphertext. That is, as described for the transmitting end, an encryption mechanism has applied thereto initialising values and a decryption key to generate the intermediate cryptographic bit stream of values which are, likewise, held in a buffer until needed for deciphering received ciphertext. The previously prepared and stored cryptographic bit stream is mathematically combined with the received ciphertext to reproduce the plaintext originally presented to the transmitter for encryption. Appropriate synchronisation of the generation and buffer storage of the cryptographic bit streams at the transmitter and receiver is provided herein.

0014The present invention will be described further by way of example with reference to an example of the prior art and an embodiment of the invention as illustrated in the accompanying drawings, in which:- <ul id="ul0001" list-style="none"><li>Fig. 1 is a block diagram of a typical stream cipher communication system including encryption at the transmitter and decryption at the receiver;</li><li>Fig. 2 is a block diagram of a stream cipher communication system including buffering of the cryptographic bit streams before encryption and decryption;</li><li>Fig. 3 is a flow diagram of the buffer management process;</li><li>Fig. 4 is a flow diagram showing use of the buffered cryptographic bit stream at the transmitter; and</li><li>Fig. 5 is a flow diagram showing use of the buffered cryptographic bit stream at the receiver.</li></ul>

0015Beginning with reference to the block diagram of Fig. 1, a secure, stream cipher communication system is shown, as is taught in the prior art by the aforementioned U.S. Patent 4,471,164 and Meyer et al text.

0016In this drawing figure X represents a message in plaintext consisting of a sequence of data X₀, X₁, . . . that may be individual bits or uniform groups of bits, e.g., bytes. The term "word" may be hereinafter used to refer to one of these bits or groups of bits. The plaintext message X is applied to a function f1 which is represented by block 11 within the transmitter 10. As shown at block 12, the cryptographic bit stream R of generated values R₀, R₁, . . ., which are also individual bits or uniform groups of bits, is generated by an encryption mechanism g as initialised by the series Z of initialising values and with the encryption key K. As in prior art systems, the transformation of the plaintext message X to a ciphertext, encrypted message Y at block 11 takes places by the real time generation, a word at a time, of the cryptographic bit stream R by the encryption mechanism g of block 12.

0017The ciphertext message is conveyed along a communications link 15 to a function f2 depicted as block 21 within a receiver 20. An encryption mechanism g, depicted by block 22, receives a decryption key K and initialising values Z, as in block 12 of the transmitter 10, to produce, in real time, a cryptographic bit stream R of values to be combined with the ciphertext message Y at block 21 to reproduce the plaintext message X output from the receiver 20.

0018Reviewing the throughput problem associated with the system shown in Fig. 1, the cryptographic bit stream R, being generated in real time, require significant amounts of time for their generation, such that the cryptographic bit stream R may, at both the transmitter and receiver, be generated at a slower rate than the plaintext message X is applied to block 11 of the transmitter and as the ciphertext message Y is applied to block 21 of the receiver. Those skilled in the art will understand that in this real time generation of the cryptographic bit stream R, any additional gating circuitry and registers used in the generation of R will tend to add additional delays in its generation.

0019Reference is now made to Fig. 2 wherein one form of modified stream cipher system of this invention is shown, which includes pregeneration of the cryptographic bit streams and storage thereof in buffers until needed by the mathematical combining functions for encryption and decryption.

0020In Fig. 2, as in Fig. 1, the plaintext message X is applied to a mathematical function f1, as shown by block 41, to which is applied a cryptographic bit stream R for combination therewith to produce the ciphertext message Y that is conveyed to a similar block 51 in the receiver 50. The encryption mechanism g, shown as block 41 in the receiver 40, and the decryption mechanism g, shown as block 52 in the receiver 50, function identically to the encryption and decryption mechanisms shown as blocks 12 and 22, respectively, in Fig. 1. The striking difference between the systems shown in Fig. 1 and Fig. 2 is in the use of buffers 43 and 53 and in pregenerating the cryptographic bit streams R in both the transmitter and receiver and in storing these cryptographic bit streams in the buffers 43 and 53 so that the crypto­graphic bit streams are available for immediate use by blocks 41 and 51 upon receipt of plaintext and ciphertext, respectively.

0021The process for pregenerating and managing the cryptographic bit streams in buffers 43 and 53 is described with reference to Fig. 3, while the processes for using the buffered cryptographic bit streams are described in Fig. 4 for the transmitter 40 and in Fig. 5 for the receiver 50.

0022Note that two separate, but identical instances of the process described in Fig. 3 exist. One performing buffer management for the transmitter described in Fig. 4 and one performing buffer management for the receiver described in Fig. 5. Referring now to Fig. 3, at the beginning of the buffer management process the buffer 43, in the case where the buffer management is for the transmitter, and the buffer 53, in the case where the buffer management is for the receiver, are initialised at 301 by clearing the buffers of all previous entries. At 302K, the secret encryption key, and ZO, the initialisation value, are obtained. K will be used by the encryption mechanisms 12 and 22 to generate the cryptographic bit stream R, as set forth below.

0023At 303 the variable Z is initialised with the value ZO. At 304 the key K and the current value of Z is used to generate a word, Ri, of the cryptographic bit stream R. At 305 a test is made to determine if the buffer 43, in the case of buffer management for the transmitter, or the buffer 53, in the buffer management for the receiver, are in use. Use of the buffer at this point would indicate that its contents were being used for combination with a plaintext value at block 41 or with a ciphertext value at block 51. If the buffer is in use, the process sleeps at 309 until such time that the process is awakened by the process described in Fig. 4, in the case of buffer management for the transmitter, or by the process described in Fig. 5, in the case of buffer management for the receiver. When awakened the process loops back to the test at 305. When the buffer is found to be not in use, processing continues at 306 where a flag is set to indicate that the buffer is now in use by this buffer management process.

0024At 307 the buffer is examined to determine if it is full, and if so at 308 the flag set at 306 is reset and any other process, the transmitter in the case of buffer management for the transmitter and the receiver in the case of buffer management for the receiver, is awakened if it was sleeping. Processing then proceeds to 309 where the buffer management process sleeps. In the case that the test at 307 indicates that the buffer is not full, processing continues at 310 where the value of the cryptographic bit stream R, generated at 304, is inserted into the buffer. The flag set at 306 is reset at 311. At 312 any other process, the transmitter in the case of buffer management for the transmitter and the receiver in the case of buffer management for the receiver, is awakened if it was sleeping. At 313 a new value of Z is computed, using some function h applied to the current value of Z and Ri.

0025The following programming design language listing is another form of the description of the above process of pregenerating and managing the cryptographic bit streams in buffers 43 and 53. This listing parallels the operation described above for Fig. 3.<img file="EP0366288A2_D0001.tif" />

0026The use of the cryptographic bit stream R stored in buffer 43 of the transmitter 40 is now described with reference to Fig. 4. At 74 a test is made to determine if there is additional information to be transmitted. If so, processing continues at 75. At 75 a plaintext value X to be encrypted and transferred along the communications link 45 is obtained. At 76 a test is made to determine if the buffer 43 is busy. If so, the operation sleeps at 101 until such time as it is awakened because buffer 43 may no longer be busy. When buffer 43 is not busy, a flag is set at 77 to indicate that the buffer is now busy with the transmit encryption process. At 78 a test is made to determine if the buffer 43 is empty. If buffer 43 is empty, the buffer is then marked not busy at 79 which allows the process described in Fig. 3 to obtain control of the buffer to add additional words of the cryptographic bit stream thereto; furthermore, at 79 the process described for Fig. 3 is awakened in case it is sleeping. From 79 the operation then sleeps at 101 until awakened because buffer 43 may no longer be empty.

0027Assuming at 78 that the buffer 43 is not empty, at 80 the next word of the cryptographic bit stream R is removed from the buffer. At 81 the flag set at 77 is reset so that the buffer is now marked not busy. At 103 the process described for Fig. 3 is awakened if it was sleeping because the buffer was either busy or full. At 82 the mathematical operation f1 at block 41 is applied to one word, X, of the plaintext and the word, R, removed at 80 to obtain a word of the ciphertext Y. At 83 the word of the ciphertext Y is sent along the communications link 45 to the receiver 50, whereupon operation of this process returns to the start thereof.

0028The following programming design language listing is another form of the description of the above process for using the buffered cryptographic bit streams in the transmiter 40. This listing parallels the operation described above for Fig. 4.<img file="EP0366288A2_D0002.tif" />

0029Fig. 5 shows the complimentary process at the receiver 50. In Fig. 5, at 105 a test is performed to determine if there is additional input to be processed. If so, processing continues at 85. At 85 a ciphertext value Y which was received along the communications link 45 is obtained for decryption. At 86 a test is made to determine if the buffer 53 is busy. If so, the operation sleeps at 106 until such time as it is awakened because buffer 53 may no longer be busy. When buffer 53 is not busy, a flag is set at 87 to indicate that the buffer is now busy with the receive encryption process. At 88 a test is made to determine if buffer 53 is empty. If buffer 53 is empty, the buffer is then marked not busy at 89 which allows the process described in Fig. 3 to obtain control of the buffer to add additional words of the cryptographic bit stream thereto; furthermore, at 89 the process described for Fig. 3 is awakened in case it is sleeping. From 89 the operation then sleeps at 106 until awakened by the process described for Fig. 3 because the buffer is no longer empty.

0030Assuming at 88 that the buffer 53 is not empty, at 90 the next word of the cryptographic bit stream, R, is removed from the buffer. At 91 the flag set at 87 is reset so that the buffer is now marked not busy. At 108 the process described for Fig. 3 is awakened if it was sleeping because the buffer was either busy or full. At 92 the mathematical operation f2 at block 51 is applied to one word, Y, of the ciphertext and the word, Ri, removed at 90 to obtain a word of the plaintext X.

0031The following programming design language listing is another form of the description of the above process for using the buffered cryptographic bit streams in the receiver 50. This listing parallels the operation described above for Fig. 5.<img file="EP0366288A2_D0003.tif" /><img file="EP0366288A2_D0004.tif" />

0032The particular mathematical functions f1 and f2 may be the EXCLUSIVE-OR function. In this case the cryptographic bit stream R in both the transmitter 40 and the receiver 50 are identical security is maintained by maintaining secrecy of the identical key K at both the transmitter 40 and the receiver 50.

0033It will, therefore, be understood that in contrast with the performance impacts suffered by the inherent delays encountered in passing the cryptographic bit stream R and signals used in the generation thereof through gates and registers during its real time generation, the disclosed arrangement provides a substantial increase in throughput by the provision of buffers to store these cryptographic bit streams until they are actually used so that the generation thereof, which presents the greatest performance impact when accomplished in real time, is, in these embodiments, accomplished well in advance of its actual use. The use of the buffer, whether at the transmitting end of a link or at the receiving end thereof, is carefully segregated. Although its use appears interleaved, the protocol is one of the slow process having undivided use of the buffer at all times possible. Note also the shift of emphasis in this respect between transmitting, where the data can be delayed and loading of the buffer is suspended on the buffer becoming full, and the receiving end, where the data incoming is not so easily delayed and the reception is suspended only on the buffer becoming empty.