5377270 : Cryptographic authentication of transmitted messages using pseudorandom numbers

We claim:

• 1. A method of cryptographically authenticating a transmission from a transmitting unit at a receiving module, comprising:
  • providing a secret initial value in said transmitter and providing said secret initial value in said receiver;
  • in said transmitting unit:
  • generating a random number;
  • concatenating said random number with a key word derived from said secret initial value to provide a combined word;
  • cat: cannot open /arc/local/etc/httpd/htdocs/tmplobs/300566
  • transmitting a command word derived at least in part from said encrypted number and indicative of a command;
  • comprising in said receiving module:
  • receiving said command word;
  • recovering said encrypted number from said received command word;
  • performing a decryption operation on said recovered encrypted number to recover said combined word;
  • comparing a second word derived from said secret initial value with the key word portion of said recovered combined word;
  • storing the random number portion of said recovered combined word for future use in subsequent authentication operations;
  • comparing the random number portion of said recovered combined word with a previously stored random number portion; and
  • performing the command indicated by said command word only if said second secret initial value is identical to the initial value portion of said recovered combined word and said random number portion of said recovered combined word is different from said previously stored random number portion.
• 2. A method according to claim 1 wherein said step of comparing the random number portion is performed only if said second secret initial value is identical to said initial value portion of said recovered combined word.
• 3. A method according to claim 1 wherein said step of storing is performed after said step of comparing the random number portion, said random number is stored at the head of a queue in a first-in, first-out memory, the first recovered one of said previously stored random numbers being dropped only if said step of comparing indicates that said random number portion is different.
• 4. A method according to claim 1 wherein said step of storing comprises storing the random number portion of said recovered combined word until at least four subsequent authentication operations have been performed; and
  • said step of comparing the random number portion comprises comparing with four of said previously stored random number portions.
• 5. A method according to claim 1 wherein said secret number is zero.
• 6. A method according to claim 1 wherein said secret number is a non-zero number.
• 7. A method according to claim 1 wherein said command indicated by said command word is a synchronization command, performance of which provides cryptographic synchronization between said receiving module and said transmitting unit.
• 8. A method according to claim 7 comprising:
  • in said transmitting unit, storing one of said numbers for future use in subsequent authentication; and wherein
  • said step of performing said command comprises storing said one of said numbers for future use in subsequent authentication.
• 9. A method according to claim 8 wherein said one of said numbers is said encrypted number.
• 10. A method according to claim 1 wherein said step of performing an encryption operation comprises performing a linear encryption operation.
• 11. A method according to claim 1 wherein said step of performing an encryption operation comprises performing a feedback shift register operation.
• 12. A method according to claim 11 wherein said step of performing an encryption operation comprises performing a linear feedback shift register operation employing the same secret initial value and the same secret feedback mask in said transmitting unit as in said receiving module.
• 13. A method according to claim 12 wherein said linear feedback shift register operation comprises a number of iterations on the order of the degree of said combined word or more.
• 14. A method according to claim 1 comprising:
  • encrypting the concatenation of said encrypted number with a third word to provide an encrypted word; and wherein
  • said step of transmitting comprises transmitting said command word including said encrypted word; and
  • said step of recovering said encrypted number comprises performing a decryption operation on said encrypted word, to also recover said third word.
• 15. A method according to claim 14 wherein said third word provides said indication of a command.
• 16. A method according to claim 14 wherein said third word is derived from a third secret initial value.
• 17. A method according to claim 14 wherein said third word comprises a third secret initial value having command indicating bits exclusive ORed into a command portion thereof; and
  • comprising in said receiving module:
  • comparing the non-command portion of said recovered third word with a corresponding portion of a fourth secret initial value; and
  • exclusive ORing said command portion of said recovered third word with a corresponding portion of said fourth secret initial value to recover said command indicating bits only if said second initial value is identical to the initial value portion of said recovered combined word, and said non-command portion of said recovered third word is identical to said corresponding portion of said fourth secret initial value.
• 18. A method according to claim 14 wherein said steps of encrypting and of performing an encryption operation each comprise performing a linear encryption operation.
• 19. A method according to claim 14 wherein said steps of encrypting and of performing an encryption operation each comprise performing a feedback shift register operation.
• 20. A method according to claim 19 wherein said steps of encrypting and of performing an encryption operation each comprise performing a linear feedback shift register operation.
• 21. A method according to claim 1 wherein said command indicated by said command word is a panic command, and performance of said panic command sets off an alarm.
• 22. A method according to claim 21 wherein said alarm comprises the horn of a vehicle with which said receiving module is associated.
• 23. A method according to claim 21 wherein said alarm comprises the headlights of a vehicle with which said receiving module is associated.
• 24. A method according to claim 1 wherein the random number portion of said combined word is compared with a plurality of previously stored random number portions.
• 25. A method according to claim 1 wherein said key word is said secret initial value.
• 26. A method of cryptographically synchronizing a command transmitting unit with a command performing receiving module for selective response thereto, comprising:
  • providing, in both said transmitting unit and in said receiving module, a word including a key portion derived at least in part from a secret initial value;
  • in said transmitting unit:
  • performing an encryption operation on said word to provide an encrypted word; and
  • transmitting a command word derived at least in part from said encrypted word and indicative of a synchronization command;
  • comprising in said receiving module:
  • receiving said command word;
  • recovering said encrypted word from said received command word;
  • performing a decryption operation on said recovered encrypted word to recover said word;
  • comparing the key portion of said word with the key portion of said recovered word; and
  • providing cryptographic synchronization between said receiving module and said transmitting unit only if the key portion of said word is identical to the key portion of said recovered word.
• 27. A method according to claim 26 wherein said word comprises a random number concatenated with said key portion, said decryption operation recovers said random number, and said step of providing cryptographic synchronization is performed only if said recovered random number is different from a previous random number recovered from a received command word.
• 28. A method according to claim 26 wherein said word comprises said key portion and a third secret initial value having bits indicative of a synchronization command exclusive ORed into a command portion thereof; and
  • said step of providing cryptographic synchronization comprises exclusive ORing a fourth secret initial value into the command portion of said recovered word to recover said synchronization command bits and providing cryptographic synchronization in response to said recovered synchronization command bits.
• 29. A method according to claim 26 wherein said key portion is said secret initial value.
• 30. A method according to claim 26 wherein said step of providing cryptographic synchronization comprises storing said recovered encrypted word for future use in subsequent authentication.
• 31. A method of transferring a cryptographically authenticated command from a transmitting unit to a receiving module, comprising:
  • providing, in both said transmitting unit and in said receiving module, a code word, derived from a secret initial value, including a key portion and a command portion;
  • comprising, in said transmitting unit:
    • providing a plurality of bits indicative of a command to be transmitted;
    • exclusive ORing said plurality of bits into corresponding bits of said command portion to provide an altered word;
    • performing an encryption operation on a word including said altered word to provide an encrypted word; and
    • cat: cannot open /arc/local/etc/httpd/htdocs/tmplobs/3005671
  • comprising in said receiving module:
    • receiving said command word;
    • recovering said encrypted word from said received command word;
    • performing a decryption operation on said recovered encrypted word to recover said altered word; and
    • exclusive ORing the command portion of said code word with the command portion of said recovered altered word to recover said plurality of bits.
• 32. A method according to claim 31 comprising:
  • exclusive ORing the command portion of said code word with the command portion of said recovered altered word only if said key portion of said code word is identical to said key portion of said recovered altered word.
• 33. A cryptographically authenticated control system in which a command message from a transmitting unit causes a physical effect in a receiving module;
  • said transmitting unit comprising:
    • a source of signals for providing a seed signal indicative of a secret initial value, said initial value being essentially unique to said transmitting unit;
    • command switches that indicate a physical effect to be caused by said receiving module; and
    • first signal processing means responsive to selected operation of said switches indicative of a command for providing a random signal indicative of a variable random number, for providing a combined number including a key word derived from said secret initial value concatenated with the random number defined by said random signal, for encrypting said combined number, and for transmitting, to said receiving module, a command word signal having a key portion derived from the encrypted combined number and including an indication of said command;
  • said receiving module comprising:
    • a signal source for providing a seed signal indicative of said secret initial value; and
    • second signal processing means for receiving said command word signal, for recovering said encrypted combined number from said key portion of said received command word signal, for decrypting said recovered encrypted combined number so as to recover said combined number, for providing a key word derived from said secret initial value, for comparing said key word with an equivalent portion of said recovered combined number, for storing, in response to said initial value being identical to said equivalent portion, the random number portion of said recovered combined word for subsequent use, and for comparing said random number portion, for which said equivalent portion is equal to said key word, with a similar random number portion, previously stored for subsequent use in response to a prior key word comparison, and for selectively performing the command indicated by said command word only if said compared random number portions are not equal.
• 34. A system according to claim 33 wherein:
  • said command switches indicate a synchronization command;
  • said first signal processing means comprises means responsive to said switches indicating said synchronization command for storing one of said numbers for future use in subsequent generation of encrypted messages; and
  • said second signal processing means comprises means for performing said synchronization command by storing said one of said numbers recovered from said command word for future use in authenticating subsequently received messages.
• 35. A system according to claim 34 wherein said first and second signal processing means each comprise means for storing said encrypted combined number for future use in authenticating subsequently received messages.
• 36. A system according to claim 33 wherein said key word is said secret initial value.
• 37. A system according to claim 33 wherein said second signal processing means compares said random number portion with a plurality of previously stored similar random number portions.
• 38. A method of causing an alarm at a receiving module in response to a command from a transmitting unit, comprising:
  • providing, in both said transmitting unit and in said receiving module, a word including a key portion derived at least in part from a secret initial value;
  • in said transmitting unit:
    • performing an encryption operation on said word to provide an encrypted word; and
    • transmitting a command word derived at least in part from said encrypted word and indicative of an alarm command;
  • comprising in said receiving module:
    • receiving said command word;
    • recovering said encrypted word from said received command word;
    • performing a decryption operation on said recovered encrypted word so as to recover said word;
    • comparing the key portion of said word with the key portion of said recovered word; and
    • setting off an alarm near said receiving module if the key portion of said word is identical to the key portion of said recovered word.
• 39. A method according to claim 38 wherein said alarm comprises the horn of a vehicle with which said receiving module is associated.
• 40. A method according to claim 38 wherein said alarm comprises the headlights of a vehicle with which said receiving module is associated.