5363448 : Pseudorandom number generation and cryptographic authentication

We claim:

• 1. A method of cryptographic authentication of transmissions from a transmitting unit to a receiving module,
  • comprising, in said transmitting unit:
  • separately generating a plurality of pseudorandom numbers;
  • concatenating said numbers to form a combined word;
  • performing an encryption operation on said combined word; and
  • transmitting a command word including a key portion derived from the result of said encryption operation; and
  • comprising, in said receiving module:
  • receiving said command word;
  • performing a decryption operation on the key portion of said command word to recover said combined word;
  • providing at least one number; and
  • providing an authentication signal only if at least a portion of said at least one number is identical to a corresponding portion of said recovered combined word.
• 2. A method according to claim 1 wherein:
  • said step of providing at least one number comprises separately generating a second plurality of pseudorandom numbers; and
  • said step of providing an authentication signal comprises providing said authentication signal only if at least a portion of each of said second plurality of pseudorandom numbers is identical to a corresponding portion of said recovered combined word.
• 3. A method according to claim 2 wherein said generating steps each comprise generating a pair of numbers.
• 4. A method according to claim 1 wherein said generating step comprises generating a pair of numbers.
• 5. A method according to claim 1 wherein said step of performing an encryption operation comprises performing a linear encryption operation.
• 6. A method according to claim 1 wherein said step of performing an encryption operation comprises performing a feedback shift register operation.
• 7. A method according to claim 6 wherein said step of performing an encryption operation comprises performing a linear feedback shift register operation employing a secret feedback mask and said step of performing a decryption operation comprises performing a reverse linear feedback shift register operation employing the same secret feedback mask as in said encryption operation.
• 8. A method according to claim 7 wherein said linear feedback shift register operation comprises a number of iterations on the order of the degree of said combined word or more.
• 9. A method of cryptographically authenticating a transmission from a transmitting unit to a receiving module, comprising:
  • providing a starting number in said transmitting unit and providing said starting number in said receiving module;
  • in said transmitting unit:
    • providing an iteration control signal which changes in a pseudorandom manner in response to successive transmissions from said transmitting unit;
    • performing a variable number of iterations of an iterative encryption operation on said starting number, said variable number determined by said iteration control signal;
    • transmitting a command word derived at least in part from the result of said encryption operation; and
  • in said receiving module:
    • receiving said command word;
    • recovering the result of said encryption operation from said received command word;
    • providing a second iteration control signal which changes, in the same pseudorandom manner as said first iteration control signal, in response to successive receptions of command words by said receiving module;
    • performing a variable number of iterations of said iterative encryption operation on said starting number, said variable number determined by said second iteration control signal;
    • comparing at least a portion of the result of said encryption operation performed in said receiving module with a corresponding portion of said recovered result; and
    • providing an authentication signal only if said portion of said encryption operation performed in said receiving module is identical to said corresponding portion of said recovered result.
• 10. A method according to claim 9 wherein said step of performing an iterative encryption operation comprises performing a linear iterative encryption operation.
• 11. A method according to claim 9 wherein said step of performing an iterative encryption operation comprises performing a feedback shift register operation.
• 12. A method according to claim 9 wherein said step of performing an iterative encryption operation comprises performing a linear feedback shift register operation employing the same secret feedback mask in said transmitting unit as in said receiving module.
• 13. A method according to claim 9 wherein:
  • the same secret initial value is provided in said transmitting unit and in said receiving module; and
  • said starting number is provided by performing said iterative encryption operation on a word derived at least in part from said secret initial value a number of iterations on the order of the degree of said word, or more.
• 14. A method according to claim 9 wherein said variable number of iterations is a fraction of the degree of said starting number.
• 15. A method according to claim 9, comprising:
  • providing a second starting number in said transmitting unit and providing said second starting number in said receiving module;
  • in said transmitting unit:
    • providing a third iteration control signal which changes in a pseudorandom fashion in response to successive transmissions from said transmitting unit;
    • performing a changeable number of iterations of an iterative encryption process on said third starting number, said changeable number determined by said third iteration control signal;
    • transmitting said command word derived at least in part from the result of said encryption process; and
  • in said receiving module:
    • recovering the result of said encryption process from said received command word;
    • providing a fourth iteration control signal which changes, in the same pseudorandom fashion as said third iteration control signal, in response to successive receptions of command words by said receiving module;
    • performing a changeable number of iterations of said iterative encryption process on said starting number, said changeable number determined by said fourth iteration control signal;
    • comparing at least a portion of the result of said encryption process performed in said receiving module with a corresponding portion of said recovered result of said encryption process; and
    • providing an authentication signal only if said portion of said encryption process performed in said receiving module is identical to said corresponding portion of said recovered result of said encryption process.
• 16. A method according to claim 15 wherein said variable number is different from said changeable number.
• 17. A method according to claim 15 wherein said pseudorandom manner is different from said pseudorandom fashion.
• 18. A method according to claim 15 wherein said iterative encryption operation is the same as said iterative encryption process.
• 19. A method according to claim 9 wherein, in response to the presence of said first and second equal signals, the command portion of said recovered new altered word is exclusive ORed with the corresponding portion of said second new pseudorandom number and said steps (a) and (b), are performed in response to the result of said exclusive OR operation indicating said command is a synchronization command.
• 20. A method according to claim 9 wherein said iteration control signal changes in response to the value of a bit position of a changing number.
• 21. A method according to claim 9 wherein said iteration control signal changes in response to the value of a plurality of bit positions of a changing number.
• 22. A method according to claim 9 wherein said iteration control signal changes in response to the value of a bit position of said starting number.
• 23. A method of cryptographically authenticating transmissions from any of a plurality of remote command transmitting units to a command performing receiving module, comprising:
  • providing a set of numbers in each of said transmitting units, each set corresponding to one of said transmitting units, each set including at least one secret initial value, each set essentially unique to the corresponding unit;
  • providing in said receiving module, said set of numbers for each of said transmitters to which said receiving module is to respond;
  • transmitting a command word from one of said transmitting units including a key portion derived at least in part from an encryption operation performed on said secret initial value; and
  • authenticating said command word received at said receiving module utilizing the numbers in a corresponding set.
• 24. A method according to claim 23 wherein each of said sets includes an identification number;
  • said transmitting step comprises transmitting said command word including said identification number; and
  • said authenticating step comprises performing a process to authenticate said received command word only in response to said command word containing an identification number which matches an identification number in one of the sets provided in said receiving module.
• 25. A method according to claim 24 wherein, in response to receipt of said command word, said receiving module performs an authentication process using successive ones of said sets which have an identification number that matches the identification number included in said received command word until either authentication occurs or all of said sets have been used.
• 26. A method according to claim 23 wherein, in response to receipt of said command word, said receiving module performs an authentication process on said key portion using successive ones of said sets until either authentication occurs or all of said sets have been used.
• 27. A method according to claim 23 wherein each set includes at least one corresponding secret feedback mask, and said encryption operation comprises a feedback shift register pseudorandom number generation operation utilizing said secret feedback mask.
• 28. A method according to claim 27 wherein said shift register operation is linear.
• 29. A method of synchronized cryptographic authentication of transmissions from a remote command transmitting unit to a command performing receiving module selectively responsive thereto comprising:
  • transmitting a command word including a key portion derived from at least one encrypted number generated in said transmitting unit and indicative of a command;
  • receiving said command word and, in response thereto, comparing a number in said receiving module with a number decrypted from the key portion recovered from said command word, providing an authentication signal based at least in part on identity between said number in said receiving module and said number decrypted from the key portion recovered from said command word, selectively performing the command indicated thereby in response to said authentication signal; and
  • rendering said receiving module unresponsive, following receipt of one command word, to receipt of an additional command word for a period of time on the order of one-half second, or more.
• 30. The method according to claim 29 wherein said rendering step comprises providing a waiting period between the conclusion of any operation responsive to receipt of one of said command words and the enabling of said receiving module to be responsive to a subsequently received command word.
• 31. A method of selectively cryptographically authenticating transmissions, indicative of commands initiated by operating switches, from each of a plurality of transmitting units to a receiving module, comprising:
  • providing a set of numbers in each one of said transmitting units, each set corresponding to one of said transmitting units and identified by an identification number, each set including at least a pair of secret initial values;
  • providing in said receiving module the one of said sets corresponding to each of said transmitting units to which said receiving module is to respond;
  • in response to operation of said switches indicating a command other than a lock-related command in one of said transmitting units:
  • providing a command bit;
  • generating a random number;
  • concatenating said random number with a first one of said secret initial values so as to provide a combined word;
  • performing a first encryption operation on said combined word to provide a first number;
  • performing a second encryption operation on a second one of said secret initial values to provide a second number;
  • exclusive ORing a plurality of command bits indicative of said command with the corresponding bits of said second number to provide an altered word;
  • performing a third encryption operation on the concatenation of said first number with said altered word to provide an encrypted key word;
  • storing said first and second numbers as first and second pseudorandom numbers for future use in subsequent authentication;
  • transmitting a command word including said encrypted key word, said command bit, and said identification number;
  • in response to operation of said switches indicating a lock-related command in one of said transmitting units:
  • performing a fourth encryption operation on said first number to provide a new first pseudorandom number;
  • performing a fifth encryption operation on said second number to provide a new second pseudorandom number;
  • exclusive ORing a plurality of command bits indicative of said lock-related command with the corresponding bits of said new second pseudorandom number to provide a new altered word;
  • performing a sixth encryption operation on the concatenation of said new first pseudorandom number and said new altered word to provide a new encrypted key word;
  • storing said new first and second pseudorandom numbers for future use in subsequent authentication in place of said first and second pseudorandom numbers;
  • transmitting a command word including said new encrypted key word and said identification number;
  • in said receiver, selectively, in response to receipt of said command word including said command bit:
  • determining if said receiver has secret initial values related to the received identification number, and if not, terminating all response to said received word, but if so:
  • performing a first decryption operation on said key word portion of said received command word so as to recover said first number and said altered word;
  • performing, on said recovered first number, a second decryption operation so as to recover said combined word, comparing said first secret initial value to a corresponding portion of said recovered combined word and providing a first equal signal only in the event of identity therebetween;
  • performing a seventh encryption operation on said second secret initial value to provide said second number, comparing the non-command portion of said recovered altered word with the corresponding portion of said second number and providing a second equal signal only in response to identity therebetween;
  • then, in response to the absence of either of said first and second equal signals, terminating all further response to said command word;
  • or otherwise, in response to the presence of said first and second equal signals, comparing the random number portion of said recovered combined word to a random number portion derived from a command word previously received from said transmitter and, in response to identity therebetween, terminating all further response to said command word, but otherwise, (a) storing said random number portion for future use in subsequent synchronization operations and (b) storing said second number and said recovered first number, as first and second pseudorandom numbers for future use in subsequent authentication operations;
  • in said receiver, selectively, in response to receipt of said command word not including said command bit:
  • determining if said receiver has secret initial values related to the received identification number, and if not, terminating all response to said received word, but if so:
  • performing a third decryption operation on the key word portion of said received command word, so as to recover said new first pseudorandom number and said new altered word;
  • performing an eighth encryption operation on said first pseudorandom number to provide a first new pseudorandom number, and comparing said first new pseudorandom number to said recovered new first pseudorandom number and providing a third equal signal in response to identity therebetween;
  • performing a ninth encryption operation on said second pseudorandom number to provide a second new pseudorandom number and comparing the non-command portion of said recovered new altered word to a corresponding portion of said second new pseudorandom number and providing a fourth equal signal only in response to identity therebetween;
  • then, in the absence of either of said third or fourth equal signals, terminating all further response to receipt of said command word, but in the presence of both of said third and fourth equal signals, exclusive ORing the command portion of said recovered new altered word with the corresponding portion of said second new pseudorandom number, performing the command indicated by the result thereof, and storing said first new pseudorandom number and said second new pseudorandom number for future use in subsequent authentication operations.
• 32. A method according to claim 31 wherein said encryption operations comprise linear feedback shift register operations.
• 33. A method according to claim 31 wherein said first, second and third encryption operations employ the same algorithm.
• 34. A method according to claim 31 wherein said first and fourth encryption operations employ the same algorithm.
• 35. A method according to claim 31 wherein said second and fifth encryption operations employ the same algorithm.
• 36. A method according to claim 31 wherein said third and sixth encryption operations employ the same algorithm.
• 37. A cryptographically authenticated remote control system in which a command transmitting unit selectively causes a physical effect in a command receiving module rendered responsive thereto;
  • said transmitting unit comprising:
    • a source of signals for providing first and second seed signals indicative of respective secret pseudorandom number generator initial values and first, second and third mask signals indicative of respective secret feedback masks, each mask defining a respective feedback polynomial for linear feedback shift register pseudorandom number generation, said initial values and said polynomials being essentially unique to said transmitting unit;
    • command switches operable to indicate a physical effect which is to be caused by said receiving module; and
    • first signal processing means responsive to selected operation of said switches indicative of a synchronization command for providing a random signal indicative of a variable random number, for performing a first linear feedback shift register pseudorandom number generation operation, on a combined number consisting of the initial value defined by said first seed signal concatenated with the random number defined by said random signal, a given number of iterations on the order of the degree of said first polynomial, or more, using the mask defined by said first mask signal, said first polynomial having a degree on the order of the degree of said combined word, for performing a second linear feedback shift register pseudorandom number generation operation, on a second word consisting of the initial value defined by said second seed signal, a fixed number of iterations on the order of the degree of said second polynomial, or more, using the mask defined by said second mask signal, said second polynomial having a degree on the order of the degree of said second initial value, for exclusive ORing a plurality of command bits indicative of said synchronization command with a corresponding plurality of bits of the result of said second generation operation to form an altered word, for storing, for future use in authenticating subsequent transmissions to said receiving module, first and second pseudorandom numbers respectively indicative of the results of said first and second generation operations, for performing a third linear feedback shift register pseudorandom number generation operation, on a word consisting of said first pseudorandom number concatenated with said altered word, a predetermined number of iterations on the order of the degree of said third polynomial, or more, using the mask defined by said third mask signal, said third polynomial having a degree on the order of the summation of the degrees of said first pseudorandom number and said altered word, and for transmitting, to said receiving module, a command word signal having the result of said third generation operation as a key portion and including a command bit indicative of said synchronization operation;
    • said first signal processing means responsive to selected operation of said switches indicative of a lock-related command for performing a fourth linear feedback shift register pseudorandom number generation operation, on said first pseudorandom number, a first determined number of iterations, using the mask defined by said first mask signal, to provide a new first pseudorandom number, for performing a fifth linear feedback shift register pseudorandom number generation operation, on said second pseudorandom number, a second determined number of iterations, using the mask defined by said second mask signal, to provide a new second pseudorandom number, for exclusive ORing a plurality of command bits indicative of said lock-related command with a corresponding plurality of bits of said new second pseudorandom number to form a new altered word, for performing a sixth linear feedback shift register pseudorandom number generation operation, on a word consisting of said new first pseudorandom number concatenated with said new altered word, said predetermined number of iterations, using the mask defined by said third mask signal, for storing said new first and second pseudorandom numbers for future use in authenticating subsequent transmissions to said receiving module, and for transmitting, to said receiving module, a command word signal having the result of said third generation operation as a key portion;
  • said receiving module comprising:
    • a signal source for providing third and fourth seed signals respectively indicative of said initial values and fourth, fifth and sixth mask signals respectively indicative of said masks; and
    • second signal processing means for receiving said command word signal and responsive to said command word including said command bit, for performing a first reverse linear feedback shift register pseudorandom number generation operation, on said key portion of said command word signal, said predetermined number of iterations, using the mask defined by said sixth mask signal, for performing a second reverse linear feedback shift register pseudorandom number generation operation, on a portion of the result of said first reverse generation operation corresponding to said combined word, said given number of iterations, using the mask defined by said fourth mask signal, for comparing said initial value defined by said third seed signal with an equivalent portion of the result of said second reverse generation operation and providing a first equal signal only if they are identical, for performing a seventh linear feedback shift register pseudorandom number generation operation on a word consisting of the initial value defined by said fourth seed signal, said fixed number of iterations, using the mask defined by said fifth mask signal, for comparing a portion of the result of said seventh generation operation, corresponding to the unaltered portion of said altered word, with a corresponding portion of the result of said first reverse generation operation and providing a second equal signal only if they are identical, in response to said first and second equal signals, for storing, for subsequent use, the random number portion of the result of said second reverse operation and for comparing said random number portion with a similar random number portion, previously stored for subsequent use in response to prior performances of said second reverse operation, and for selectively storing third and fourth pseudorandom numbers respectively indicative of the result of said second reverse operation and said seventh generation operation, for future use in subsequent authentication of transmissions from said transmitting unit, only if said compared random portions are not equal;
    • said second signal processing means responsive to said command word signal not including said command bit for performing a third reverse linear feedback shift register pseudorandom number generation operation, on said key portion of said command word signal, said predetermined number of iterations, using the mask defined by said sixth mask signal, to recover said new first pseudorandom number and said new modified word, for performing an eighth linear feedback shift register pseudorandom number generation operation, on said third pseudorandom number, said first determined number of iterations, using the mask defined by said fourth mask signal, to provide a third new pseudorandom number with said third new pseudorandom number and generating a third equal signal only if they are identical, for performing a ninth linear feedback shift register pseudorandom number generation operation, on said fourth pseudorandom number, said second determined number of iterations, using the mask defined by said fifth mask signal, to provide a fourth new pseudorandom number, for comparing the non-command portion of said recovered new altered word with a corresponding portion of said fourth new pseudorandom number and providing a fourth equal signal only if they are identical, and, in response to said first and second equal signals, for storing for future use in subsequent authentication of transmissions from said transmitting unit, said new third and fourth pseudorandom numbers indicative of the results of said eighth and ninth generation operations, for exclusive ORing the command portion of said recovered new altered word with the corresponding portion of said fourth new pseudorandom number to recover said plurality of command bits and for performing said lock-related command.
• 38. A system according to claim 37 wherein the initial value indicated by said first seed signal is different from the initial value defined by said second seed signal.
• 39. A system according to claim 37 wherein said polynomials are all different from each other.
• 40. A system according to claim 37 wherein said fixed number is equal to said given number.
• 41. A system according to claim 37 wherein said first determined number is different from said second determined number.
• 42. A system according to claim 37 wherein said feedback polynomials are maximal length feedback polynomials.
• 43. A system according to claim 37 wherein said first and second determined numbers each vary as a function of a respective pseudorandom event, responsive to each transmission in said transmitting unit and responsive to each reception in said receiving module.
• 44. A system according to claim 43 wherein said first and second determined numbers are a fraction of said given number and said fixed number, respectively.
• 45. A method of cryptographically authenticating a transmission from a transmitting unit to a receiving module, comprising:
  • providing a starting number in said transmitting unit and providing said starting number in said receiving module;
  • in said transmitting unit:
    • providing an iteration control signal which changes in a random manner in response to successive transmissions from said transmitting unit;
    • performing a variable number of iterations of an iterative encryption operation on said starting number, said variable number determined by said iteration control signal;
    • transmitting a command word derived at least in part from the result of said encryption operation; and
  • in said receiving module:
    • receiving said command word;
    • recovering the result of said encryption operation from said received command word;
    • providing a second iteration control signal which changes, in the same random manner as said first iteration control signal, in response to successive receptions of command words by said receiving module;
    • performing a variable number of iterations of said iterative encryption operation on said starting number, said variable number determined by said second iteration control signal;
    • comparing at least a portion of the result of said encryption operation performed in said receiving module with a corresponding portion of said recovered result; and
    • providing an authentication signal only if said portion of said encryption operation performed in said receiving module is identical to said corresponding portion of said recovered result.
• 46. A method according to claim 45 wherein said iteration control signal changes in response to the value of a plurality of bit positions of a random number.