Pseudorandom number generation and cryptographic authentication
First 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.
11 Assignments
0 Petitions
Accused Products
Abstract
An automobile door lock 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.
373 Citations
46 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
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. - View Dependent Claims (24, 25, 26, 27, 28)
-
-
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. - View Dependent Claims (30)
-
-
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. - View Dependent Claims (32, 33, 34, 35, 36)
-
-
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. - View Dependent Claims (38, 39, 40, 41, 42, 43, 44)
-
-
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. - View Dependent Claims (46)
-
Specification