Secure Transmission System

This invention relates to cryptography, that is, the use of secret codes to maintain privacy of communications in the presence of an intruder. More particularly, it relates to the management and distribution of the keys to cryptographic codes.

Not very long ago, the use of cryptography was mostly limited to military and diplomatic communications. The privacy of the mails was sufficient for most business purposes. Today, however, most business communication is carried on almost instantaneously by electric means. The mails are considered too slow. Furthermore, with the explosion of computer technology, computers, customers and data bases often located in different parts of the country must interact on a routine basis. As a result, very large amounts of very sensitive data are transmitted back and forth. Since the transmission facilities may be terrestrial microwave radio, satellite or long wires, the opportunities for interception by an interested intruder are great. In addition, the sensitivity of many types of communications to interception by an intruder, or to the introduction of false information, or the erasing of information from a data bank, is often critical. In the instance of electronic funds transfer, for example, such interference by an intruder could be very rewarding for the intruder and disastrous to the system.

In the terminology commonly used in cryptography, encypherment or encryption is a transformation process by which the original text, called plain text or clear text, is replaced by cypher text. The reverse process is known as decryption or decypherment. A cryptographic system usually includes a whole family of transformations, each member of the family being uniquely identified by a particular parameter called a key. Changing the key, therefore, changes the transformation algorithm without changing the system. Thus, in order to decrypt the cypher text and recover the plain text, the recipient must know not only the system but the particular key as well. An intruder is said to have broken the cryptographic code when he has discovered the system and key. Since systems usually involve hardware and are in place over a period of time, they are subject to discovery. The security of the code, therefore, and all the data protected by it, lies in the security of the key.

The advances in digital computing and communications technology which have given rise to the need to protect so much business data, have also spawned many cryptographic systems which rely on intricate algorithms implemented by computer. Recognizing the extent of the need and the cost and availability advantages of standardization, the National Bureau of Standards has adopted a data encryption standard, as described in the Federal Information Processing Standards Publication No. 46, dated Jan. 15, 1977. The Data Encryption Standard (DES) specifies a general algorithm to be implemented in electronic hardware devices and used for cryptographic protection of computer data. Blocks of input data of 64 bits each are transformed under a 56-bit key using 16 rounds of permutations and substitutions to generate 64-bit cypher blocks.

Unfortunately, however, high speed computing technology is also available to sophisticated intruders who have a substantial interest in breaking a cryptographic code. It makes possible, for example, the trial of many different algorithms in a very short time. As a consequence, given knowledge of a system and access to clear text and associated cypher text, a well equipped intruder can, in time, derive the key used. Even with the large family of transformations implemented by the DES, security against sophisticated intruders therefore suggests frequent changing of the key.

The problem that this presents, however, in a communications system where the encrypter and decrypter are not colocated is obvious. All legitimate users must change to the same new key at the same time. Since it may well be desirable to change key at least every day, physical delivery of each new key is far too cumbersome. It is therefore necessary that the material for many keys be available at each location.

In one possible arrangement, many whole keys may be stored in one physical medium, such as a read-only memory. To keep all stations synchronized, the keys are used in the order in which they are stored, and all stations change key upon the same criteria. For example, all might change at 12:01 A.M., each day, or perhaps after each communication session. Such a system would obviously provide a very high degree of security, so long as each key is used only once. With an electronic system, however, an interruption in power, even of momentary duration, can cause the key selection apparatus to lose its place. Any resulting repeated use of a key reduces security, but if the system must return to the first key in order to synchronize all stations, the security is obviously drastically reduced. Such systems, therefore, in general, require back-up power to avoid interruption, an expensive necessity.

In an alternative arrangement, specific key material may be selected at each location from a bank or library of key material in accordance with an electronic signal. This signal, which may be called a key index signal, may specify the key directly or may provide the initial starting point of a predetermined process for choosing the key. The key index signal may even be chosen totally at random, but it must unambiguously define the key. In order to provide all communicating stations with the same key, however, it must be transmitted and therefore is as subject to interception as the encrypted message itself.

The text "Cryptography", A. G. Konheim, John Wiley & Sons, Inc., 1981, in Section 7.4 describes a system for end-to-end encryption using the DES algorithm. Operational keys which perform the message encypherment are encrypted by system keys, so that the key index signal sent to the receiver is an encrypted operational key. With high powered computing capability, a sophisticated intruder that could derive operational key could derive the key for decrypting the key index signal as well, gaining access to future operational keys.

An object of this invention is a more secure transmission system which has no need for backup power.

A second object is a more secure transmission system in which access to both key index and encrypted message does not enable access to future operational keys.

A third object of this invention is a more secure transmission system using the DES algorithm.

Still a fourth object is a more secure transmission system using the DES algorithm in which the key can be continually changed to provide running key.

In a secure transmission system wherein the message signal is encrypted for transmission according to a predetermined algorithm and a stored key, and the key is selected for storage from a key library according to a transmitted key index signal, the key index signal is itself encrypted and the key selected according to the encrypted key index signal. A key index signal may be encrypted for new key selection each transmission session according to the DES algorithm and another key that is changed daily, the daily key itself being selected from a day key library according to a transmitted random number. Finally, a new session may be continually selected from the session key library according to an encrypted pseudorandom bit stream.

FIG. 1 is a block diagram of an embodiment of the invention.

FIG. 2 is a block diagram of an embodiment of the invention using the DES algorithm and allowing continual key change.

FIG. 3 is a plot of various control signals which may be used in connection with the embodiment of FIG. 2.

In the embodiment of the invention depicted in FIG. 1, a secure transmission system includes at least a transmitting station 10 and a receiving station 30. In transmission station 10 a message encryption means 11 has an input 12, an output 13, and a stored key 14. A memory 16 is connected to key 14, and a key index encryption means 17 has its output connected to memory 16 and its input connected to the output of a key index generator 18. Similarly, at receiving station 30 a message decryption means 31 has an input 32, an output 33, and a stored key 34. A memory 36 is connected to key 34, and a key index encryption means 37 has its output connected to memory 36 and its input connected to key index generator 18 via a key index communication channel 21. The output 13 of message encryption means 11 is connected to the input 32 of message decryption means 31 via a message communication channel 20.

At transmitting station 10 encryption means 11 operates to encrypt a message signal on input 12 according to a predetermined algorithm and stored key 14. Stored key 14 is made up of elements selected from memory 16. At receiving station 30 decryption means 31 operates to decrypt the message signal on input 32 according to stored key 34 and a predetermined decryption algorithm. Stored key 34 is selected from memory 36 according to the key index signal from generator 18 after it has been encrypted by key index encryption means 37.

Encryption means 11 and decryption means 31 may use any number of available encryption methods which employ a changeable stored key. The encryption algorithm may be implemented, for example, by a general purpose computer, a microprocessor, a hard wired circuit, or even a mechanical device. Decryption means 31 must, of course, operate under its stored key to implement the complimentary process of encryption means 11 in order to recover the original message signal.

Memories 16 and 36 store a quantity of possible key elements in excess of what is required for any particular key. Memories 16 and 36 may also be implemented by a very wide range of devices that include not only volatile and non-volatile electronic memories, but physical and mechanical devices as well, such as punched cards and even printed circuit boards.

Key index encryption means 17 and 37 may employ an even wider choice of methods since they are not necessarily limited to the use of stored keys. Further, they need not implement complimentary processes since they both serve to provide an encrypted signal with which to select key. The ultimate requirement, of course, is that stored key 34 selected from memory 36 must operate in the decryption means 31 to regenerate the signal originally encrypted in encryption means 11 using stored key 14 which was selected from memory 16. For ease of implementation memories 16 and 36 may of course be identical and, therefore, keys 14 and 34 also identical. Key index generator 18 may be located anywhere as long as it delivers the same key index signal to both key index encryption means 17 and 37.

The strength of the invention as illustrated in FIG. 1 lies in the fact that an intruder does not have access to both clear text and associated cypher text within the key selection chain from which to derive future key information. That is, even if he has key index information from generator 18 and has derived an associated operational key 14, he still has not broken the key selection process.

A particularly advantageous embodiment of the invention for encrypting a digital signal is illustrated in the block diagram of FIG. 2. In this embodiment an encryption transmitting station 110 is connected via a full rate digital message channel 120 and a substrate control channel 121 to a decryption receiving station 130. In transmitting station 110 message encryption means 111 may be constructed to implement the Data Encryption Standard and will, henceforth, be termed DES 111. Parallel input leads 140 to DES 111 are connected to a serial-to-parallel converter 141, which is in turn connected to the output of a pseudorandom number generator 144. The eight parallel outputs 146 of DES 111 are connected to a parallel-to-serial converter 147, which in turn is connected to one input of an EXCLUSIVE-OR gate 148. The other input 112 to gate 148 receives the plain text input signal, and the output 113 carries the cypher text output and delivers it to connecting channel 120. A second DES 117 has its parallel outputs 151 connected to a buffer 119, the parallel outputs of which are connected to memory 116. Outputs 152 of memory 116 are connected to the key input of DES 111. The parallel inputs 154 of DES 117 are connected via a serial-to-parallel converter 156 to the output of a pseudorandom number generator 170. A control circuit 166 has a first input 167 connected to the output of a random number generator 168 and second and third inputs 169 and 171 connected into the respective feedback loops of PRNGs 170 and 144. Outputs 173 and 174 are also connected into the feedback loops of PRNGs 170 and 144, respectively. Outputs 176 and 177 are connected to respective control inputs of DES 111 and outputs 179 and 180 to respective control inputs of DES 117. Control output 182 is connected to the clock input of DES 111 and output 183 to the clock input of DES 117; output 184 is connected to the subrate channel 121. The tenth output, 186, of control 166 is connected to a no repeat circuit 158. The parallel outputs of a no repeat circuit 158 address memory 162, the outputs of which are connected to the key inputs of DES 117.

The decrypter-receiver 130 is almost identical to encrypter-transmitter 110; its corresponding parts are identified by corresponding numbers of the 200 series.

The embodiment of FIG. 2 operates to encrypt a pseudorandom number of a very long sequence to form an encrypted bit-stream, which then is modulo-2 added in exclusive ORgate 148 with the message signal to form the cypher text that is transmitted over channel 120. In receiver 130 the same pseudorandom number from generator 244 is encrypted in the same manner by DES 211 to form the same encrypted bit-stream into exclusive ORgate 248, which is then modulo-2 added to the cypher text from channel 120 to reproduce the plain text out. Since both encrypter 110 and decrypter 130 operate to form the identical encrypted bit-stream, the following explanation of the operation of encrypter 110 will also apply to decrypter 130.

To initiate the encryption process in the embodiment of FIG. 2 a key must first be entered into DES 117. Since this may be conveniently accomplished, for example, once a day, it will be termed a "day key". Control 166 connects its input 167 to output 186, thereby feeding random bits from random number generator 168 to no-repeat circuit 158. Circuit 158 accumulates the bits in a memory to form address bytes for memory 162. Each new byte is compared with all previous bytes. Unique bytes are accumulated, and repeat bytes are rejected until eight different bytes are accumulated. Subsequent new unique bytes replace the oldest accumulated bytes, which are outputted to address memory 162. Control 166 connects the proper logic to outputs 179 and 180 to enter as the day key the contents of the memory 162 addressed by the random bytes.

The next step in the initiation process is to initialize the pseudorandom number generator 170. As is well known, a pseudorandom number generator may be merely a long shift register with feedback. Control 166 opens the connection between input 169 and output 173 to open the feedback loop of PRNG 170 and feeds random bits from RNG 168 to output 173 to fill the register in PRNG 170. Once the register is filled with random bits, input 169 is again connected to output 173 and PRNG 170 begins producing its pseudorandom bit-stream.

DES 117 is now set to produce key for DES 111. Control 166 applies the proper logic to leads 179 and 180 to cause DES 117 to enter data, i.e., the output of PRNG 170, until eight bytes of 8-bits each have been entered. The logic on leads 179 and 180 is then altered to cause DES 117 to encrypt the entered data with the DES algorithm and the stored key 164. After encryption, control 160 applies the logic to leads 179 and 180 to output the encrypted data to buffer 119 where it accumulates to form address bytes for memory 116. Upon command of control 166 via outputs 176 and 177 DES 111 enters the key bytes stored at the addressed locations of memory 116 to form key 114. Since this may be accomplished every transmission session, it may conveniently be termed a session key. Alternatively, as will later be shown, new keys may be entered into DES 111 for every 64 bit block of input data; in this usage, the key 114 may be termed running key.

It should be noted that when running key is not needed, PRNG 170 is not necessary either. Random bits from RNG 168 may be connected to serial-to-parallel converter 156 to form data bytes for encryption by DES 117.

Control 166 may now initialize PRNG 144 via ports 171 and 174 with random bits from RNG 168 in a manner similar to that described with respect to PRNG 170. Its pseudorandom bit stream will be encrypted by DES 111 in the electronic code book mode to form a continuous key stream for nodulo two addition with the plain message text.

It will be obvious that in order to provide the identical encrypted bit stream at the outputs of parallel-to-serial converters 147 and 247, identical corresponding encryption algorithms, day keys, session keys and pseudorandom bit streams must be used. The contents of the corresponding key library memories at both encryption and decryption stations must be identical. Furthermore, the random numbers which are used to address the corresponding day key library memories and to initialize the respective corresponding pseudorandom number generators must be identical. Control 166, therefore, corresponds with control 266 via subrate channel 121. A code word identifying the initialization process may be sent, then the random numbers themselves from RNG 168. Since the random numbers are only used for initializing the system and generating day key, the rate at which they are transmitted is not important. Therefore, a very low bit rate channel may be used for channel 121. Alternatively, it will be obvious to those skilled in the art, the same information may be transmitted over channel 120 at any bit rate. The national telephone network may be used, therefore, with or without common channel inter-office signalling (CCIS).

To implement the embodiment of the invention shown in FIG. 2, memories 116 and 162, which form the session key and day key libraries respectively, may be any medium capable of storing seven-bit key bytes in a large number of addresses. If the number of addresses is 256, there is no need for buffer 119, as eight-bit data bytes from DES 117 can directly address memory 116. It is particularly useful in thwarting intruders; however, if the number of addresses is much larger than the number of possible key bytes. For example, the key libraries may advantageously be preprogrammed Read Only Memories PROMs) having 2048 bytes of memory. Since the DES uses seven-bit bytes, the maximum number of different key bytes is 2.sup.7 or 128, and statistically there is an average of 16 different addresses for each particular key byte. An intruder who may have recovered the key for a particular block of data cannot determine which address in the memory each key byte came from. The 2048-byte memories will, of course, have 11 inputs to address all bytes. Thus, no-repeat circuit 158 will require 11 outputs, and buffer 119 is needed to accumulate the 8-bit bytes out of DES 117 into the requisite 11-bit bytes. Inclusion of buffer 119, however, provides a substantial advantage of allowing the session key to be changed every 64-bit block of input data.

To implement the Data Encryption Standard (DES), integrated circuits and instructions are available commercially from several suppliers. Fairchild Instruments Data Encryption Set 9414 includes four integrated circuit chips each comprising a pair of data registers, four 8-bit shift registers, control logic, and two 64-word 4-bit read-only memories. When the chips are connected and powered according to instructions provided by Fairchild, a 56-bit key stored in eight bytes of seven bits each is used to encypher a 64-bit data word that is stored in eight bytes. Separate data inputs and outputs allow input and output at the same time, and 16 steps of encryption are performed on each 8-byte word. Every 64-bit block of data, therefore, can be encrypted in 24 externally supplied clock pulses at a rate of up to 5 MHz.

The DES operation is controlled in the 9914 set by binary logic applied to three leads labelled C.sub.0, C.sub.1, C.sub.2, respectively. Since both transmitter and receiver operate to encrypt the pseudorandom number in the embodiment of FIG. 2, however, classic decryption is not needed, and the C.sub.2 lead may be permanently wired high, i.e., to +5 volts, or logic 1. All of the required DES functions may, therefore, be controlled by logic on just two leads, C.sub.0 and C.sub.1, which correspond to the control inputs shown on the various DESs of FIG. 2.

If the externally supplied clock rate is judiciously varied, even though the DES employs a batch process on a block of 64 bits of input data, continuous encryption of an input bit stream can be accomplished. Furthermore, the embodiment of FIG. 2 can be used to provide continuous key change; that is, running key.

Control 166 provides the logic and clock to DESs 117 and 111 and connects random number generator 168 to select day key and to initiate the PRNGs. It can be implemented in hardware, software, or firmware. Table 1 shows the necessary connections, logic and clock rates to cause an embodiment of FIG. 2 to operate at a throughput of 256 kilobits per second with running key. This data is sufficient to allow one of ordinary skill in data control circuits to design a satisfactory control circuit.

In this particular arrangement RNG 168 may output at 1 kb/s. Therefore, the registers in PRNGs 170 and 144 will be loaded at the 1 kb/s rate. No repeat circuit 158 will accumulate bits at 1 kb/s to form 8 unique eleven-bit bytes. The random bits from RNG 168 are also transmitted to receiver control circuit 266. As previously mentioned, any medium may be used for this transmission. If a separate channel 121 is used, the very low bit rate allows time division multiplexing with many other signals, adding to the difficulty of intrusion.

Alternatively, of course, these random bits may be transmitted over the main channel 120 at 1 kb/s or any faster rate.

If day key is loaded into DES 117 at the rate of 60 bytes per second, enough time is allotted to allow the no-repeat circuit to operate. Memory 162 is, of course, addressed at the same rate. Since this set up occurs only once a day, the fraction of a second that it takes is not material.

The timing for loading session key into DES 111 is a little more complicated because it involves encrypting I.sub.s, the output from PRNG 170 in DES 117. With PRNG 170 outputting at 512 kb/s series-parallel converter 156 can output and DES 117 load data at 64 kb/s. Since DES 117 can load and unload data at the same time, a continuing 64 k-bytes/s can be maintained if encrypting is performed between load/unload steps. A 2048 kHz clock rate performs all 16 encryption steps in 31.25 microseconds. This is one half the time allotted to each load/unload step and enough to avoid interference.

In the example of Table 1 PRNG 144 outputs R.sub.N, a pseudorandom bit stream, at 256 kb/s, the system throughput rate. S/P 141 outputs 8-bit bytes for DES 111 to load and unload data at a 32 kb/s rate. Encryption is performed between load-unload steps at 1024 kHz. Key is loaded from memory 116 also between R.sub.N data load steps. Since key is used only for encryption, it need be in place only after the eighth data byte is loaded and until the next first byte is loaded. Key therefore may be loaded between any other data bytes. It is more convenient, however, if the timing of the load step is symmetrical with that of the encrypt step. The key is therefore loaded between the fourth and fifth data byte. Buffer 119 receives encrypted key index bytes of eight bits at 64 kb/s. It discards five bits of every other received byte to accumulate eight 11-bit bytes. These eight bytes are unloaded to memory 116 and key is loaded into DES 111 at 1024 kb/s per second.

The timing waveforms of FIG. 3 further illustrate the manner in which these processes interleave. Activity is assumed to occur on the negative going edge of each clock pulse and each waveform is labeled according to the output of 166 to which it is applied. It can be seen that waveform 176 is low and 177 is high for each regularly occurring 32 kHz clock pulse on output 182. Since this is the data load/unload mode of DES 111, it provides a steady throughput of 32 kb/s. Clock 182 shifts to 1024 kHz after each four 32 kHz clock pulses and within the period when waveform 177 is low. Sixteen clock pulses at 1024 kHz are needed for encryption when waveform 176 is also low and eight for loading key when 176 is also high.

Except for loading day key, which occurs only, for example, once each day, output 179 of control 166 remains low and hence is not graphed. The clock applied to output 183 shifts from 64 kHz to 2048 kHz after every eight 64 kHz pulses in a similar manner, in order to encrypt the session key stream. The phase relationship between clock 183 and 182 is not important if buffer 119 has a capacity of at least nine bytes. The relationship shown in FIG. 3, however, in which the eight load-key pulses of waveform 182 and the 16 encrypt pulses of waveform 183 both occur between the same 64 kHz pulses, allows eight bytes to suffice.

I have shown, therefore, in FIG. 2 a secure transmission system that can be easily built by one skilled in the art from available materials. The only transmitted signal subject to intruder interception besides the cypher text is a random number needed to select the day key and initialize the PRNGs. Armed with this information and even an identical terminal, but absent the specific key library memories, there is no known way in which an intruder can recover the contents of the memories in any reasonable time period and therefore break the code. Memories may thus be produced in secret and be changed only very infrequently with no fear of loss of security. For even longer memory longevity the session key may be encrypted by several cascaded DESs each with its individual day key chosen from its individual key library memory. Succeeding DESs may re-encrypt the encrypted session key index, or alternatively, each DES may encrypt the key index of the following DES in a manner similar to that of the embodiment of FIG. 2.

It will be obvious to those skilled in the art of secure transmission that other arrangements than those illustrated can be produced without departing from the scope and spirit of the invention. It is not necessary, for example, to utilize the DES algorithm; other encryption means can be used in which the key is selected from a key library according to a key index signal that is encrypted for key selection after transmission. The DES itself can also be implemented in other structures. Advanced Micro Devices Inc. of Sunnyvale, Calif., for example, markets a microprocessor controlled DES which one skilled in the art can use to practice the invention with rather simple software.