Cryptographic authentication of transmitted messages using pseudorandom numbers

Abstract

An automobile door receiver module (30) and a plurality of keychain fob transmitter units (16) contain identification numbers, secret initial values, and secret feedback masks so as to authenticate encrypted messages from any of the assigned fobs, indicative of commands registered by closing switches on the fob. Each fob is synchronized with the receiving module by means of a truly random number concatenated with a secret initial value and encrypted, through a linear feedback shift register or other operations. A second secret initial value is encrypted and command bits are exclusive ORed into the low order bit positions; the two encrypted numbers are concatenated and encrypted to form a key word which is transmitted with the fob ID. Synchronization includes decrypting to recover the truly random number and the secret initial value concatenated therewith; the truly random number is compared with previously received random numbers in order to avoid copying of recently transmitted synchronization commands. Successive lock-related commands utilize the number encrypted from the truly random number and the second secret initial value as starting values, employing a pseudorandom number of encryption iterations. A half-second delay between responses mitigates gaining access through numerical trials. An authenticated panic alarm command operates the headlights and horn of the vehicle but does not alter the synchronization.

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;   performing an encryption operation on said combined word to provide an encrypted number; and   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.]. .Iadd.word .Iaddend.is identical to the .[.initial value.]. .Iadd.key word .Iaddend.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.]. .Iadd.word .Iaddend.is identical to said .[.initial value.]. .Iadd.key word .Iaddend.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.]. .Iadd.initial value .Iaddend.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.]. .Iadd.word .Iaddend.is identical to the .[.initial value.]. .Iadd.key word .Iaddend.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 step 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 .Iadd.in said transmitter .Iaddend.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.]. .Iadd.second .Iaddend.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.]. .Iadd.third .Iaddend.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   transmitting a command word derived at least in part from said encrypted word;   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. .Iadd. 
     
     
       41.  A method according to claim 26 wherein said word is said secret initial value. .Iaddend..Iadd.42. 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 first signal source for providing a word signal indicative of a word, said word signal including a key portion derived at least in part from a secret initial value signal;   an encrypter for performing an encryption operation on said word signal to provide an encrypted signal indicative of an encrypted word;   transmission means for transmitting a command signal derived at least in part from said encrypted signal and indicative of a synchronization command;     said receiving module comprising: a second signal source for providing a word signal indicative of said word;   reception means for receiving said command signal;   a signal processor for recovering said encrypted signal from said command signal;   a decrypter for recovering said word signal from said encrypted signal;   means for comparing the key portion of said word signal with the key portion of said recovered word signal; and   synchronization means for providing cryptographic synchronization between said receiving module and said transmitting unit only if the key portion of said word signal is identical to the key portion of said recovered word     
     
     
        signal. .Iaddend..Iadd.43.  A system according to claim 42 wherein said word signal in said transmitter comprises a random number signal concatenated with said key portion, said decrypter operative to recover said random number signal, and said synchronization means operative to provide cryptographic synchronization only if said recovered random number signal is different from a previous random number signal recovered from a received command signal. .Iaddend..Iadd.44. A system according to claim 42 wherein said word signal comprises said key portion and a second secret initial value signal indicative of a binary number having synchronization command bits exclusive ORed into a command portion thereof; and said synchronization means comprises a second signal processor for exclusive ORing a third secret initial value signal into the command portion of said recovered word signal to recover said synchronization command bits and provide cryptographic synchronization in response to said recovered synchronization command bits. .Iaddend..Iadd.45. A system according to claim 42 wherein said key portion is said secret initial value signal. .Iaddend..Iadd.46. A system according to claim 42 wherein said word signal is said secret initial value signal. .Iaddend..Iadd.47. A system according to claim 42 wherein said synchronization means comprises means for storing said recovered encrypted signal for future use in   
     
     
        subsequent authentication. .Iaddend..Iadd.48.  A command system in which a command message sent from a transmitting unit causes a physical effect in a receiving module, said transmitting unit comprising: a first signal source for providing a code word signal derived from a secret initial value signal, said code word signal including a key portion and a command portion;   means for providing a plurality of bits indicative of a command to be transmitted;   a signal processor for exclusive ORing said plurality of bits into corresponding bits of said command portion to provide an altered word signal;   an encrypter for performing an encryption operation on a word signal including said altered word signal to provide an encrypted signal; and   transmission means for transmitting a command signal derived at least in part from said encrypted signal;     comprising in said receiving module; a second signal source for providing a code word signal;   reception means for receiving said command signal;   a signal processor for recovering said encrypted signal from said command signal;   a decrypter for recovering said altered word signal from said encrypted signal; and   a second signal processor for exclusive ORing the command portion of said code word signal with the command portion of said recovered altered word signal to recover said plurality of bits. .Iaddend..Iadd.49. A system according to claim 48, said second signal processor comprising:     means for exclusive ORing the command portion of said code word signal with the command portion of said recovered altered word signal only if said key portion of said code word signal is identical to said key portion of said recovered altered word signal. .Iaddend..Iadd.50. A system for causing an alarm at a receiving module in response to a command from a transmitting unit,   said transmitting unit comprising: a first signal source for providing a word signal indicative of a word, said word signal including a key portion derived at least in part from a secret initial value signal;   an encrypter for performing an encryption operation on said word signal to provide an encrypted signal indicative of an encrypted word;   transmission means for transmitting a command signal derived at least in part from said encrypted signal and indicative of an alarm command;     said receiving module comprising: a second signal source for providing a word signal indicative of said words reception means for receiving said command signal;   a signal processor for recovering said encrypted signal from said command signal;   a decrypter for recovering said word signal from said encrypted signal;   means for comparing the key portion of said word signal with the key portion of said recovered word signal; and   alarm means for setting off an alarm near said receiving module if the key portion of said word signal is identical to the key portion of said     
     
     
        recovered word signal. .Iaddend..Iadd.51.  A system according to claim 50 wherein said alarm comprises the horn of a vehicle with which said receiving module is associated. .Iaddend..Iadd.52. A system according to claim 50 wherein said alarm comprises the headlights of a vehicle with which said receiving module is associated. .Iaddend..Iadd.53. 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 first signal source for providing a word signal indicative of a word, said word signal including a key portion derived at least in part from a secret initial value signal;   transmission means for transmitting a command signal derived at least in part from said word signal and indicative of a synchronization command;     said receiving module comprising: a second signal source for providing a word signal indicative of said word;   reception means for receiving said command signal;   a signal processor for recovering said word signal from said command signal;   means for comparing the key portion of said word signal with the key portion of said recovered word signal; and     synchronization means for providing cryptographic synchronization between said receiving module and said transmitting unit only if the key portion of said word signal is identical to the key portion of said recovered word signal. .Iaddend..Iadd.54. A system according to claim 53 wherein said word signal in said transmitter comprises a random number signal concatenated with said key portion, said signal processor operative to recover said random number signal, and said synchronization means operative to provide cryptographic synchronization only if said recovered random number signal is different from a previous random number signal recovered from a received command signal. .Iaddend..Iadd.55. A system according to claim 53 wherein said word signal comprises said key portion and a second secret initial value signal indicative of a binary number having synchronization command bits exclusive ORed into a command portion thereof; and   said synchronization means comprises a second signal processor for exclusive ORing a third secret initial value signal into the command portion of said recovered word signal to recover said synchronization command bits and provide cryptographic synchronization in response to said recovered synchronization command bits. .Iaddend..Iadd.56. A system according to claim 53 wherein said key portion is said secret initial value signal. .Iaddend..Iadd.57. A system according to claim 53 wherein said word signal is said secret initial value signal. .Iaddend..Iadd.58. A system according to claim 53 wherein said synchronization means comprises means for storing said recovered word signal for future use in subsequent authentication. .Iaddend..Iadd.59. A method of cryptographically synchrononizing 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; transmitting a command word derived at least in part from said word and indicative of a synchronization command;     comprising in said receiving module: receiving said command word;   recovering said word from said received command 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. .Iaddend..Iadd.60. A method according to claim 59 wherein said word in said transmitter comprises a random number concatenated with said key portion, said step of recovering comprises recovering 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. .Iaddend..Iadd.61. A method according to claim 59 wherein said word comprises said key portion and a second 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 third 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. .Iaddend..Iadd.62. A method according to claim 59 wherein said key portion is said secret initial value. .Iaddend..Iadd.63. A method according to claim 59 wherein said word is said secret initial value. .Iaddend..Iadd.64. A method according to claim 59 wherein said step of providing cryptographic synchronization comprises storing said recovered word for future use in subsequent authentication. .Iaddend.