Protected communication method and system

• US 5,703,948 A
• Filed: 10/11/1994
• Issued: 12/30/1997
• Est. Priority Date: 02/14/1994
• Status: Expired due to Term

• Current Assignee: Elementrix Technologies Limited
• Original Assignee: Elementrix Technologies Limited
• Inventors: Yanovsky, Eli
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/320,452
• Time in Patent Office: 1,176 Days
• Field of Search: 380/21, 380/46
• US Class Current: 380/262
• CPC Class Codes: H04L 9/12 Transmitting and receiving encryption devices synchronised or initially set up in a particular manner
• CPC Class Codes: H04L 9/16 the keys or algorithms being changed during operation

Abstract

A method and apparatus for transmitting encrypted messages between two units, by initializing the two units with respect to each other, and thereafter transmitting the messages between the two units encrypted by means of dynamic random keys which are changed internally within the two units in synchronism with each other, thereby obviating the need for transferring keys or for a master key.

Claims

1. A method of transmitting encrypted messages between two units, including initializing the two units with respect to each other, and thereafter transmitting the messages between the two units encrypted by means of dynamic random keys which are changed internally within the two units in synchronism with each other;

wherein one unit, serving as the transmitter party for a message, divides the message into a plurality of segments, encrypts each segment by an encrypting key which changes randomly from segment to segment, and transmits the encrypted segments;

wherein the other unit, serving as the receiver party for the respective message, receives the encrypted segments, divides each received message into the same segments as the transmitter, and decrypts each segment by the use of a decrypting key which initially matches the encrypting key and which changes randomly from segment to segment in the same manner as the encrypting key;

wherein the encrypting key is the output of a state machine at the transmitter, which state machine changes its state in a random manner from segment to segment according to at least one random manner from segment to segment according to at least one random characteristic transmitted with the respective segment;

and wherein the decrpting key is the output of a state machine at the receiver, which latter state machine also changes its state in a random manner from segment to segment according to the same random characteristic of the respective segment.

2. The method according to claim 1, wherein:

one unit, serving as the transmitter party for a message, divides the message into a plurality of segments, encrypts each segment by an encrypting key which changes randomly from segment to segment, and transmits the encrypted segments;

and the other unit, serving as the receive party for the respective message, receives the encrypted segments, divides each received message into the same segments as the transmitter, and decrypts each segment by the use of a decrypting key which initially matches the encrypting key and which changes randomly from segment to segment in the same manner as the encrypting key.

3. The method according to claim 2, wherein:

the encrypting key is the output of a state machine at the transmitter, which state machine changes its state in a random manner form segment to segment according to at least one random characteristic transmitted with the respective segment;

and the decrypting key is the output of a state machine at the receiver, which latter state machine also changes its state in a random manner from segment to segment according to the same random characteristic of the respective segment.

4. The method according to claim 1, wherein:

said segments are in the form of digital data in the binary notation;

and the state machines of the two parties change their states according to a function of at least one random bit in the respective segment.

5. The method according to claim 1, wherein the state machines of the two parties change their states according to a function of at least one random bit in the respective transmitted encrypted segment.

6. The method according to claim 1, wherein said at least one random bit is the value of the bit at the location specified by the state of said state machines.

7. The method according to claim 1, wherein the state machines of the two parties change their states according to a function of two random bits in the respective segment.

8. The method according to claim 1, including the further step of utilizing a function of the state of the respective state machine for determining the location of at least one random bit in the respective segment.

9. The method according to claim 1, including the further step of utilizing a function of the state of the respective state machine for determining the length of the respective segment.

10. The method according to claim 1, including the further steps of:

interjecting at least one redundant bit into each segment;

and utilizing said interjected redundant bits for detecting and/or correcting transmission errors.

11. The method according to claim 10, including the further step of utilizing a function of the state of the respective state machine for determining the locations of the interjected redundant bits in the respective segment.

12. The method according to claim 10, wherein a plurality of redundant bits are interjected into each segment.

13. The method according to claim 10, wherein the state machines of the two parties change their states according to two random bits in the respective segment, and six redundant bits are interjected into the respective segment for detecting and correcting up to two transmission errors in said bits.

14. The method according to claim 1, wherein:

said state machines are normal state machines effective during normal message transmissions to produce said random encrypting key and decrypting key;

each unit includes an emergency state machine;

the states of the emergency state machines in the two units are both changed together in a random manner during the transmissions of messages;

and in the event of detection of a difference in the states of the normal state machines of the two parties, an emergency condition is determined to have occurred, whereupon an emergency message is transmitted by one of the parties causing the current state of the emergency state machines at the transmitter and receiver to be utilized for changing the normal state machines at the transmitter and receiver to the same new normal state.

15. The method according to claim 14, wherein a message counter is incremented at each unit to count the number of normal message transmissions between the two units;

each emergency state machine is changed in the same random manner by its respective messsage counter after counting a predetermined number of normal message transmissions to define a round of messages; and

during each round of messages, random emergency bits are utilized for creating a new state in the emergency state machines of both units.

16. The method according to claim 15, wherein said random emergency bits are taken from one or more predetermined messages in the respective round of messages.

17. The method according to claim 16, wherein said predetermined message is the first message in the respective round of messages.

18. The method according to claim 15, wherein:

the occurrence of an emergency condition within a round restarts the counting of messages for the respective round;

and said random emergency bits are utilized for creating a new state in said emergency state machines only after a predetemined number of normal message transmissions in the respective round without the occurrence of an emergency condition.

19. The method according to claim 18, wherein:

each emergency message transmission includes a header announcing whether the Old state or a New state of the emergency state machine is to be used;

and in case an emergency condition occurs in a prescribed ambiguity region in the proximity of the end of the respective round, the receiver party uses the Old state or the New state, as included in the header of the emergency message transmission.

20. The method according to claim 19, wherein the transmitter and receiver each includes registers for registering any one of four zones, zone 1 identifying a beginning non-ambiguity region, zone 2 identifying a beginning ambiguity region, zone 3 identifying an ending ambiguity region, and zone 4 identifying an ending non-ambiguity region;

the occurrence of an emergency condition in zone 1 causing both parties to use the Old state of the emergency state machine;

the occurrence of an emergency condition in zone 4 causing both parties to use the New state of the emergency state machine;

and the occurrence of an emergency condition in either of zones 2 or 3 causing the receiver of the respective message to use the Old or New state, as announced in the header of the respective message transmission;

but when using the Old state, the New state can be produced; and

when using the New state, the Old state remains stored and the New state is produced at hoc, so that such states will be available in case the respective unit has to return to the Old state or resume the New state in order to maintain synchronism.

21. The method according to claim 20, including the further steps of:

setting a flag in the respective unit when an emergency condition occurs;

resetting the flag after a predetermined number M₂ of normal message transmissions have taken place between the two parties;

but if an emergency condition occurs while the respective party is in ambiguity zone 2 or 3, the respective unit utilizes the combination of the zone number, and the Old or New state of the respective emergency state machine used, to determine whether to return to the Old state, or use the New state and erase the Old state.

22. The method according to claim 21, wherein, upon the occurrence of an emergency condition the respective party:

(a) if in zone 2, and the Old state was used, returns to zone 1 after M₂ normal message transmission;

(b) if in zone 2, and the New state was used, moves to zone 3 after a predetermined number M₁ of normal message transmissions, wherein M₁ is less than M₂ ;

(c) if in zone 3, and the Old state was used, moves to zone 2 after a predetermined number M₁ of normal message transmissions;

(d) and if in zone 3, and the New state was used, moves to zone 4 after M₂ normal message transmissions.

23. Apparatus for transmitting encrypted messages between two nits, one unit including an encrypting system for encrypting messages, and a transmitter for transmitting the encrypted messages, and the other unit including a received for receiving the encrypted messages, and a decrypting system for decrypting the received messages;

said encrypting system in the transmitter, and decrypting system in the receiver utilizing dynamic random keys which are changed internally within the two units in synchronism with each other;

said one unit, serving as the transmitter, comprising means for dividing each message into a plurality of segments, means for encrypting each segment by an encrypting key which changes randomly from segment to segment, and means for transmitting the encrypted segments;

said other unit, serving as the receiver, comprising means for receiving the encrypted messages, means for dividing the messages into the same segments as in the transmitter, and means for decrypting each segment by the use of a decrypting key which initially matches the encrypting key and which changes randomly from segment to segment in the same manner as the encrypting key;

said encrypting key being the output of a state machine at the transmitter, which state machine changes its state in a random manner from segment to segment according to at least one random characteristic transmitted with the respective segment;

said decrypting key being the output of a state machine at the receiver, which latter state machine also changes its state in a random manner from segment to segment according to the same at least one random characteristic of the respective segment.

24. The apparatus according to claim 23;

wherein said one unit, serving as the transmitter, comprises means for dividing each message into a plurality of segments, means for encrypting each segment by an encrypting key which changes randomly from segment to segment, and means for transmitting the encrypted segments;

and wherein said other unit, serving as the receiver, comprises means for receiving the encrypted messages, means for dividing the messages into the same segments as in the transmitter, and means for decrypting each segment by the use of a decrypting key which initially matches the encrypting key and which changes randomly from segment to segment in the same manner as the encrypting key.

25. The apparatus according to claim 24, wherein:

the encrypting key is the output of a state machine at the transmitter, which state machine changes its state in a random manner from segment to segment according to at least one random characteristic transmitted with the respective segment;

and the decrypting key is the output of a state machine at the receiver, which latter state machine also changes its state in a random manner from segment to segment according to the same at least one random characteristic of the respective segment.

26. The apparatus according to claim 23, wherein:

said segments are in the form of digital data in the binary notation;

and the state machines at the transmitter and receiver change their states according to a function of at least one random bit in the respective segment.

27. The apparatus according to claim 26, wherein the state machines at the transmitter and receiver change their states according to a function of at least one random bit in the respective transmitted encrypted segment.

28. The apparatus according to claim 26, wherein said at least one random bit is the value of the bit at the location specified by the state of said state machines.

29. The apparatus according to claim 26, wherein the state machines at the transmitter and receiver change their states according to a function of two random bits in the respective segment.

30. The apparatus according to claim 23, including means utilizing a function of the state of the respective state machine for determining the location of at least one random bit in the respective segment.

31. The apparatus according to claim 23, including means utilizing a function of the state of the respective state machine when transmitting one segment for determining the length of the respective segment.

32. The apparatus according to claim 25, further including:

interjecting means for interjecting at least one redundant bit into each segment;

and means utilizing said interjected redundant bit for detecting and/or correcting transmission errors.

33. The apparatus according to claim 32, further including means utilizing a function of the state of the respective state machine for determining the locations of the interjected redundant bits in the respective segment.

34. The apparatus according to claim 32, wherein said interjecting means interjects a plurality of redundant bits into each segment.

35. The apparatus according to claim 32, wherein the state machines at the transmitter and at the receiver change their states according to two random bits in the respective segment, and six redundant bits are interjected into the respective segment for detecting and correcting up to two transmission errors in said bits.

36. The apparatus according to claim 23, wherein:

said state machines at the transmitter and receiver are normal state machines effective during normal message transmissions to produce said random encrypting key and decrypting key;

and wherein said transmitter and receiver each includes;

an emergency state machine whose states are both changed together in a random manner during the transmissions of messages;

means for detecting a difference in the states of the normal state machines at the transmitter and receiver, and for determining an emergency condition to have occurred in the event of such detection;

and means effective, upon the determination of such emergency condition, for actuating the transmitter to transmit an emergency message causing the current state of the emergency state machines at the transmitter and receiver to be utilized for changing the normal state machines at the transmitter and receiver to the same new normal state.

37. The apparatus according to claim 36, further including:

a message counter at the transmitter and receiver;

means for incrementing the message counter to count the number of normal message transmissions between the two parties;

means for causing each emergency state machine to be changed in the same random manner by said messsage counter after counting a predetermined number of normal message transmissions to define a round of messages; and

utilizing means effective after each round of messages for utilizing random emergency bits for creating a new state in said emergency state machines both at the transmitter and at the receiver.

38. The apparatus according to claim 37, wherein said utilizing means takes said random emergency bits from one or more predetermined messages in the respective round of messages.

39. The apparatus according to claim 38, wherein said predetermined message is the first message in the respective round of messages.

40. The apparatus according to claim 37, wherein each of said message counters is effective, upon the occurrence of an emergency condition within a round, to restart the counting of messages for the respective round;

and said utilizing means utilizes said random emergency bits for creating a new state in said emergency state machines only after a predetemined number of normal message transmissions in the respective round have occurred without the occurrence of an emergency condition.

41. The apparatus according to claim 40, wherein:

the transmitter includes means for producing in each emergency message transmission a header announcing whether the Old state or a New state of the emergency state machine is to be used;

and the receiver includes means, effective when an emergency condition occuring in a prescribed ambiguity region in the proximity of the end of the respective round, to use the Old state or the New state, as included in the header of the emergency message transmission.

42. The apparatus according to claim 41,

wherein the transmitter and receiver each includes registers for registering any one of four zones, zone 1 identifying a beginning non-ambiguity region, zone 2 identifying a beginning ambiguity region, zone 3 identifying an ending ambiguity region, and zone 4 identifying an ending non-ambiguity region;

and wherein the receiver includes means, effective;

upon the occurrence of an emergency condition in zone 1, to cause the receiver to use the Old state of the emergency state machine;

upon the occurrence of an emergency condition in zone 4, to cause the receiver to use the New state of the emergency state machine;

and upon the occurrence of an emergency condition in either of zones 2 or 3, to cause the receiver to use the Old or New state, as announced in the header of the emergency message transmission;

but when using the Old state, the New state can be produced; and

when using the New state, the Old state remains stored and the New state is produced at hoc, so that such states will be available in case the respective unit has to return to the Old state or resume the New state in order to maintain synchronism.

43. The apparatus according to claim 42, further including:

a flag in the transmitter and receiver;

means for setting said flag when an emergency condition occurs, and for resetting the flag after a predetermined number M₂ of normal message transmissions have taken place between the parties;

and means effective, upon the occurrence of an emergency condition while a respective party is in ambiguous zone 2 or 3, for utilizing the combination of the zone number, and the Old or New state of the respective emergency state machine used, to determine whether to return to the Old state, or to use the New state and erase the Old state.

44. The apparatus according to claim 43, wherein said latter means is effective upon the occurrence of an emergency condition in the respective party:

(a) if in zone 2, and the Old state was used, to return to zone 1 after M₂ normal message transmission;

(b) if in zone 2, and the New state was used, to move to zone 3 after a predetermined number M₁ of normal message transmissions, wherein M₁ is less than M₂ ;

(c) if in zone 3, and the Old state was used, to move to zone 2 after a predetermined number M₁ of normal message transmissions;

(d) and if in zone 3, and the new state was used, to move to zone 4 after M₂ normal message transmissions.

45. The apparatus according to claim 23, wherein each unit includes both a transmitter and a receiver and is capable of serving as a transmitter for transmitting and encrypting a message, and also as a receiver for receiving and decrypting a message.

46. The apparatus according to claim 45, wherein each unit also includes a state machine and a memory for each party with which it may communicate.

47. The apparatus according to claim 23, wherein each unit includes both a transmitter and receiver, a normal state machine and a memory for each party with which it may communicate, and an emergency state machine and a memory for each party with which it may communicate.