WO1988001817A1

WO1988001817A1 - Stations for communicating with encrypted messages via randomly selected circularly stored keys

Info

Publication number: WO1988001817A1
Application number: PCT/US1987/002149
Authority: WO
Inventors: George Tomomitsu Shima
Original assignee: Unisys Corp
Current assignee: Unisys Corp
Priority date: 1986-09-02
Filing date: 1987-08-31
Publication date: 1988-03-10
Anticipated expiration: 1989-03-02

Abstract

A communication network of a type in which a first station sends encrypted messages to a second station is constructed such that the first station includes: a module for choosing an encryption key in a radom fashion from a plurality of encryption keys, and a module for encrypting a message via the randomly chosen encryption key and transmitting the encrypted message on the network; and such that the second station includes: a module for receiving and storing the encrypted message from the network, a module for selecting by chance a decryption key from a plurality of decryption keys, a module for performing a decrypt operation on a certain portion of the stored encrypted message via the selected decryption key, a module for comparing the result of the decrypt operation to a control word, a module for repeatedly activating the above recited selecting, performing, and comparing modules until the result of the decrypt operation matches the control word, and a module for performing the decrypt operation on the remainder of the stored encrypted message via the decryption key which causes the match. Modules which choose the encryption key and select the decryption key each include a memory which stores a circular sequence of bits, a submodule which picks a particular bit from all of the bits in the sequence, and a submodule which reads the key from the memory as the circular bit sequence beginning at the particular bit.

Description

STATIONS FOR COMMUNICATING WITH ENCRYPTED MESSAGES VIA RANDOMLY SELECTED CIRCULARLY STORED KEYS

BACKGROUND OF THE INVENTION

This invention relates to methods of communicatin via encrypted messages from one station to another on communication network, and to circuits for implementin such communication methods.

Basically, a communication network of the typ with which this invention is concerned includes at leas one station which accepts messages from an operator, an which encrypts and transmits those messages; and i includes at least another station which receives th encrypted messages, decrypts them, and provides th decrypted message to an operator. Such networks are usefu wherever proprietary information needs to be transmitted. For example, the proprietary information might include recommendation from a broker to a client to purchase o sell certain stock, an electronic transfer of funds, military-related data, etc. Typically, each person at the receiving station who is to receive a message has his own unique key, and the operator at the transmitting station has all such keys. Then, to encrypt a message for a particular person, the transmitting station uses the key which is assigned to that person.

In other words, in order to communicate between stations, certain individuals at both the transmitting station and the receiving station must "know" what the encryption/decryption key is. No one else can have access to the key, for if they do, they can monitor the encrypted message on the network and decrypt it. This, however, presents the problem of how to secretively transport the keys between the stations. Also, it is desirable in the above described communications networks to use relatively long keys to encrypt and decrypt each message. This is because, in general, the degree of security which an encrypted message is given is proportional to the length of the key that, is used to encrypt the message. However, long keys also require a large number of memory cells for their storage. For example, one million keys which are each one million bits .long would require one billion storage cells, and that is impractical to achieve with^* today's technology.

BRIEF DESCRIPTION OF THE DRAWINGS

Various features and advantages of the inventio are described herein in detail in conjunction with th accompanying drawings wherein: FIG. 1 is a detailed logic diagram of a station which receives, encrypts, and transmits messages in accordance with the present invention;

FIG. 2 is a flow chart of a program in a micro- processor in FIG. 1 which controls its operation;

FIG. 3 is a schematic diagram showing how encryption keys are stored in a memory in FIG. 1;

FIG. 4 is a detailed logic diagram of a station which receives and decrypts messages in accordance with the present invention; and

FIG. 5 is a flow chart of a program in a micro¬ processor in FIG. 4 which controls its operation.

DETAILED DESCRIPTION OF THE INVENTION A preferred embodiment of a station which encrypts and transmits messages in accordance with the present invention will now be described in detail in conjunction with FIG. 1. This station includes a random access read/write memory 10, a random access read only memory 11, an exclusive OR gate 12, a modulator 13, a transmitter 14, a pair of counters 15 and 16, a multiplexor 17, a random number generator 18, a microprocessor 19, and a keyboard/CRT 20. All of these components are intercon¬ nected as illustrated via conductors 30a thru 30s. Memory 10 holds the messages which are to be encrypted and transmitted. It is 1 bit wide and N bits long, where N is any integer which is large enough to allow the memory to hold each message individually. Memory 10 has a single data input terminal DI, a single data output terminal DO, a single write control terminal W, and binary address terminals A.

Memory 11, by comparison, holds all of the keys which are utilized to encrypt the messages from memory 10. It is 1 bit wide and M bits long, where M is any number which is large enough to allow the memory to store all the encryption keys at the same time. How this is achieve without making memory 11 excessively large will b described shortly in conjunction with FIG. 3. Memory 1 has a single data output terminal DO, and binary addres terminals A.

Some of the other components also have thei terminals labeled as follows. Multiplexor 17 has inpu terminals Al and A2. Address signals on terminals Al an A2 respectively pass through the multiplexor when th control signal on conductor 301 is high and low. Counte 16 has a reset terminal R and a clock terminal CK; an counter 15 has a load data terminal LD and a clock termina CK. When terminal R receives a low signal, counter 1 resets; when terminal CK receives a clock pulse, counter 15 and 16 increment by one; and when terminal LD receives pulse, counter 15 loads a random number from generator 18.

Turning now to FIG. 2, a program in microprocesso 19 which controls the sequence by which the above circuitr operates to encrypt and transmit a message will b described. Initially, as indicated by reference numera 41, the program waits for a message that is to be encrypte and transmitted. This message is received by microproces sor 19 from keyboard 20, and it must include a contro word.

Preferably, each control word is chosen such tha it has some secondary meaning to the person for whom th message is intended (i.e., a meaning other than an abstrac sequence of one and zero bits). For example, the contro words can be selected from a large set of data that i personal to the individual for whom a message is intended, such as his Social Security number, his license plat number, his home address, etc. Fro microprocessor 19, as indicated by reference numeral 42, the message is loaded into memory 10. To achieve this, microprocessor 19 forces the signal on conductor 301 to a high state, generates a sequence of consecutive addresses on the conductors 30k, and it generates the bits of the message on conductor 30a and write pulses on conductor 30m in synchronization with the addresses.

Subsequently, as indicated by reference numeral 43, microprocessor 19 randomly selects an encryption key from memory 11. To achieve this, microprocessor 19 sends a pulse on conductor 30n to generator 18; and in response, signals representing a random number are generated on the conductors 30p. Microprocessor 19 then sends a pulse on conductor 30o which causes the random number on the conduc¬ tors 30p to be loaded into counter 15. By this means, a beginning address for memory 11 is randomly selected.

Now in order to save memory space, the keys in memory 11 are not stored separate from one another. Instead, all of the keys are stored as a single circular sequence of bits; and each bit of this sequence is a bit of many different keys. This circular sequence is illustrated schematically in FIG. 3.

In that figure, reference numeral 50-1 indicates the cell in memory 11 which has address 0, reference numeral 50-2 indicates the cell in memory 11 which has address 1, ..., and reference numeral 50-M indicates the cell in memory 11 which has address M-l. To select a key, one of these cells is addressed initially in a rando fashion as described above. Thereafter, the cells are addressed by counter 15 by adding one to the previous address in sequential fashion until cell 50-M is addressed. Then the next cell that is addressed by counter 15 is cell 50-1. Then the cells are addressed by adding one to the previous address in a sequential fashion until cell 50-M again reached, at which time the whole sequence repea itself.

For example, if memory 11 contains the bit patte which is shown in FIG. 3 and cell 50-6 is initial addressed, then the encryption key would be 111010... indicated by reference numeral 51 in FIG. 3. As anoth example, if the initial address in counter 15 selects ce 50-(M-3), then the encryption key, as indicated reference numeral 52, would be 11011001..., etc. In oth words, the key which is utilized to encrypt a message the circular sequence of bits which is stored in memory beginning at a cell which is randomly selected.

To activate an actual encryption and transmissi process, microprocessor 19 simply forces signal STARTXMT o conductor 30g to a high state. This is indicated by refe rence umeral 44 in FIG. 2. In response, modulator 1 starts sending CLOCK pulses on conductor 30i. Each CLOC pulse on conductor 30i causes one bit of the message i memory 10 and one bit of the selected key in memory 11 t be exclusively ORed, and the result is modulated b modulator 13 and transmitted by transmitter 14.

After sending the STARTXMT signal, microprocesso 19 waits for signal ENDXMT on conductor 30h to go high This is indicated by reference numeral 45 in FIG. 2 Signal ENDXMT is forced high by counter 16 after it ha reached a certain count which indicates that the entir message in memory 10 has been encrypted and transmitted When that occurs, microprocessor 20 returns to its quies cent state by forcing signal STARTXMT low.

Reference should now be made to FIG. 4, wherein preferred embodiment of a station which receives an decrypts messages in accordance with the invention is illus trated. This station includes a random access read/writ memory 60, a random access read only memory 61, a receiver 62, a demodulator 63, a counter 64, a multiplexor 65, an exclusive OR gate 66, a comparator 67, a random access read/write memory 68, a pair of counters 69 and 70, a micro- processor 71, and a keyboard/CRT 72. All of these compo¬ nents are interconnected via conductors 80a through 80w as illustrated.

Memory 60 stores the encrypted messages which are received for decryption, and it has the same structure as memory 10 of the FIG. 1 station. Memory 61 stores the keys that are utilized to decrypt the messages in memory 60, and it has the same structure and stored bit pattern as memory 11 of the FIG. 1 station.

Other components in FIG. 4 which have various control terminals that are labeled include: counter 64 which has a reset terminal R and clock terminal CK, counter 69 which has a load terminal LD and a clock terminal CK, and counter 70 which has a clock terminal CK. Also, multi¬ plexor 65 has two sets of input terminals Al and A2; and memory 68 has a single data input terminal DI, a single data output terminal DO, a single write terminal W, and binary address terminals A. Signals on those terminals cause the same operations as described for correspondingly labeled terminals in FIG. 1. Consider now FIG. 5 which shows a high level flow chart of a program in microprocessor 71. This program controls the sequence by which the FIG. 4 circuitry operates to receive and decrypt a message. To begin, as indicated by reference numeral 91, microprocessor 71 forces a STARTRCV signal on conductor 80h to a high level. In response, demodulator 63 receives the next message which passes through receiver 62. As that message is received, demodulator 63 sequentially generates the bits of the message on conductor 80x; and in synchronization with those bits it generates write pulses on conductor 80d and clo pulses on conductor 80c

In response to each of the clock pulses conductor 80c, counter 64 counts up by one; and the signa from the output of counter 64 are passed through mult plexor 65 to address memory 60. Thus the bits of encrypted message are sequentially loaded into memory 60 consecutively addressed cells beginning at address 0. Whe the message is completely loaded, counter 64 forces ENDRCV signal on conductor 80i to a high state which cause demodulator 63 to stop sending the pulses on conductors 80 and 80d.

A high state of signal ENDRCV on conductor 80i i also detected by microprocessor 71 as an indication that message has been received. This is indicated by referenc numeral 92 in FIG. 5. In response, as indicated by refe rence numeral 93, microprocessor 71 forces signal STARTRC on conductor 80h to a low state; and this returns demodu lator 63 to its quiescent state and resets counter 64. Next, microprocessor 72 waits for an operator t enter a control word from keyboard 72. This control word as indicated by reference numeral 94, is then loaded b microprocessor 71 into memory 68. Such loading is achieve by sequentially sending the bits of the control word o conductor 80q in synchronization with addresses on conduc tors 80o and write pulses on conductor 80p.

Thereafter, as indicated by reference numeral 95 microprocessor 71 selects by chance a decryption key fro memory 61. To do this, microprocessor 71 sends a -pulse o conductor 80s which causes whatever count is in counter 7 to increment by one; and then, it sends a pulse o conductor 80t which causes the contents of counter 70 to b loaded into counter 69. Next, as indicated by reference numeral 96, micro¬ processor 71 uses the selected key to perform a decryption operation on the control word portion of the message. To do this, microprocessor 71 sequentially addresses the bits of encrypted control word in memory 60 via the conductors 80f; and in synchronization therewith it sequentially addresses the bits of the selected key by sending clock pulses on conductor 80r. Each address on the conductors 80f and corresponding clock pulse on conductor 80r results in one bit of the encrypted control word being exclusively ORed via gate 66 with one bit of the selected key.

As each exclusive OR signal is produced by gate 66, microprocessor 71 addresses via the conductors 80o the corresponding bit of the control word in memory 68; and these signals from gate 66 and memory 68 are compared via comparator 67. Microprocessor 71 monitors the result of each compare operation on conductor 80m. This is indicated in FIG. 5 by reference numeral 97.

If a miscompare occurs, a new key is selected. This is achieved by sending a pulse on conductor 80s and followed by a pulse on conductor 801. Counters 69 and 70 are constructed such that they increment by one for each pulse that is received on their CK terminal until they address the last cell 50-M, and then the next pulse on their CK terminal causes their count to recycle back to zero.

By proceeding in the above fashion, eventually a key will be selected for which no miscompare occurs on any bit of the entire control word. When that happens, then the selected key is utilized to decrypt the remainder of the message. This is indicated in FIG. 5 by reference numerals 98 and 99.

A primary feature of the above described invention is that it enables messages to be transmitted with an added security over the prior art. This is because with the present invention, the keys are selected at random with human intervention; and no one knows what key is bei utilized to encrypt a particular message. Also, no ke have to be secretly carried from a transmitting station t a receiving station; and different keys are utilized t encrypt different messages for the same individual.

Yet another feature of the present invention i that it enables the large number of encryption an decryption keys to be stored in a small number of memor cells. For example, if memory 11 of FIG. 1 and memory 6 of FIG. 4 are each one bit wide and one million bits long then, with present technology, they can each be implemente via a single semiconductor chip. Memories 11 and 60 wil each then store one million keys which are each one millio bits long. By comparison, to store those same key separate from one another would require one million chips which is totally impracticable.

A method of communicating via encrypted message in accordance with the invention, as well as circuitry fo carrying out that method, have now been described i detail. In addition, however, many changes and modifica tions can be made to these details without departing fro the nature and spirit of the invention.

For example, counters 15 of FIG. 1 and 69 of FIG 4 have been described as counting up by one in order t address consecutive bits of the keys. However, thos counters 15 and 69 could alternatively count down by one t address consecutive bits of the keys. In that case, whe they reach a count of zero, they would recycle on the nex CK pulse to address cell M as previously defined.

Also, as described above and as shown in FIGs . and 4, the control word portion of each message is fixed a the beginning of the message. However, as an alternative, the control word can be located at the end of the messag or at any other location within the message. Accordingly, since many such changes and modifica¬ tions can be made to what has been described above, it is to be understood that the invention is not limited to those details but is defined by the appended claims.

Claims

WHAT IS CLAIMED IS:

1. A communication network of a type in which a fir station sends encrypted messages to a second statio wherein said first station is comprised of: a means f choosing an encryption key in a random fashion from plurality of encryption keys, and a means for encrypting message via said randomly chosen encryption key a transmitting the encrypted message on said network; a wherein said second station is comprised of: a means fo receiving and storing said encrypted message from sai network, a means for selecting by chance a decryption ke from a plurality of decryption keys, a means for performin a decrypt operation on a certain portion of said store encrypted message via said selected decryption key, a mean for comparing the result of said decrypt operation to control word, a means for repeatedly activating the abov recited selecting, performing, and comparing means unti the result of said decrypt operation matches said contro word, and a means for performing said decrypt operation^' o the remainder of said stored encrypted message via th decryption key which causes said match.

2. A network according to claim 1 wherein said means for choosing said encryption key and said means for selecting said decryption key each include a memory which stores a circular sequence of bits, a means which picks a particular bit from all of the bits in said sequence, and a means which reads the key from said memory as said circular bit sequence beginning at said particular bit.

3. A network according to claim 2 wherein said means which reads the key from said memory includes a means for repetitively incrementing the address of said particular bit to form memory addresses for respective succeeding bits of said sequence.

4. A network according to claim 2 wherein said means

^* which reads the key from said memory includes a means for repetitively decrementing the address of said particular bit to form memory addresses for respective succeeding bits of said sequence.

5. A network according to claim 1 wherein said first and second stations each include a means for storing a circular sequence of bits; a means for picking a particular bit from all of the bits in said sequence in a random fashion in said first station and by chance in said second station; and a means for using said circular bit sequence beginning at said particular bit as the respective key in each station. 6. A network according to claim 1 wherein sai control word is of a type which has a secondary meanin independent of its use with said comparing means.

7. For use in a communication network, a statio which is comprised of: a means for receiving and storing an encrypte message from said network; a means for selecting by chance a decryption ke from a plurality of decrypted keys; a means for performing a decrypt operation on certain portion of said stored encrypted message via sai selected decryption key; a means for storing a control word; and a means for repeatedly activating the abov recited selecting means and performing means until th result of said decrypt operation matches said control word.

8. A station according to claim 7 wherein said means for selecting includes a memory which stores a circular sequence of bits; a means for picking a particular bit fro all of the bits in said sequence by guess; and a means for reading said decryption key from said memory as said circular bit sequence beginning at said particular bit.

9. For use in a communication network, a statio which is comprised of: a means which stores a circular sequence of bits; a means for picking any bit from all of the bits in said sequence in a random fashion; and a means for performing an encryption operation o a message by utilizing said bit sequence beginning at sai picked bit as an encryption key in said encryptio operation.

10. A station according to claim 9 wherein said means for storing is a one bit wide and M word long memory havin the bits of said circular sequence stored at consecutivel addressed storage cells within the memory.

11. A method of communicating via encrypted message from a first station to a second station on a communicatio network, including the steps of: choosing an encryption key in said first statio in a random fashion from a plurality of encryption keys; encrypting a message, which includes a contro word, in said first station via said randomly chose encryption key and transmitting the encrypted message o said network; receiving and storing said encrypted message fro said network in said second station; selecting by chance a decryption key in sai second station from a plurality of decryption keys; performing a decrypt operation, in said secon station, on the encrypted control word in said store message via said selected decryption key; comparing, in said second station, the result o said decrypt operation to said control word; repeating the above recited selecting, performing, and comparing steps until the result of said decryp operation matches said control word; and performing said decrypt operation, in said secon station, on the remainder of said stored encrypted messag via the decryption key which causes said match.

12. A method according to claim 1 wherein said encryption and decryption keys are chosen by the steps of providing a memory in each station with a plurality of bits stored therein, and reading all of the bits from a respective one of said memories in a circular sequence beginning with a bit which is randomly selected for said encryption key and selected by chance for said decryption key.

13. A method according to claim 2 wherein to address consecutive bits of said circular sequence in said memories, a predetermined number is added to the address of the immediately preceding bit.

14. A method according to claim 2 wherein to address consecutive bits of said circular sequence in said memories, a predetermined number is subtracted from the address of the immediately preceding bit.

15. A method according to claim 1 wherein said keys are chosen by the substeps of: storing in said first and second stations a circular sequence of bits; picking a particular bit from all of the bits in said sequence in a random fashion for said encryption key and by chance for said decryption key; and using said circular bit sequence beginning at said particular bit as said keys. 16. A method according to claim 1 wherein the contro word portion of said encrypted message is at predetermined location therein.

17. A method according to claim 1 wherein said contro word is of a type which has a secondary meaning to a intended receiver of the message independent of its use i said comparing step.

18. For use in communicating from a first station to second station, a method of operating said second statio including the steps of: receiving and storing an encrypted message fro said first station in said second station; selecting a key by chance in said second statio from a plurality of decryption keys; performing a decrypt operation, in said secon station, on a certain portion of said stored encrypte message via said selected decryption key; comparing, in said second station, the result o said decrypt operation to a control word; repeating the above recited selecting, performing and comparing steps until the result of said decryp operation matches said control word; and generating a signal that indicates whic decryption key causes said match. _{9 #} A method according to claim 8 wherein said decryption key is chosen by the substeps of: providing a memory which stores a circular sequence of bits; picking a particular bit from all of the bits in said sequence by guess; and utilizing as said decryption key, said bit sequence beginning at said particular bit.

20. For use in communicating via encrypted messages from a first station to a second station, a method of operating said first station including the steps of: providing a memory in said first station which stores a circular sequence of bits; picking a bit from all of the bits in said sequence in a random fashion; and utilizing said bit sequence beginning at the picked bit as an encryption key for a message to said second station.