Method of generating secret identification numbers

• US 5,757,923 A
• Filed: 04/19/1996
• Issued: 05/26/1998
• Est. Priority Date: 09/22/1995
• Status: Expired due to Term

• Current Assignee: Lear Corporation EEDS and Interiors Incorporated (Lear Corporation)
• Original Assignee: UT Automotive Dearborn, Inc.
• Inventors: Koopman, Philip J. Jr.
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/635,145
• Time in Patent Office: 767 Days
• Field of Search: 380/46, 364/717
• US Class Current: 380/46
• CPC Class Codes: G06F 2207/581 Generating an LFSR sequence, e.g. an m-sequence; sequence may be generated without LFSR, e.g. using Galois Field arithmetic
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H04L 9/001 using chaotic signals
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

The present invention teaches a method of generating a secret identification number from a random digital data stream. The method comprises the step of initially selecting a first and a second group of bytes from the random digital data stream, wherein the first and second groups of bytes have a first and second numerical value. Subsequently, a first maximal length LFSR feedback term is looked up from a list in response to said first numerical value, while a second maximal length LFSR feedback term is looked up from the list in response to said second numerical value. The method additionally comprises the step of generating a cyclic redundancy code feedback term in response to executing a cyclic redundancy code check on a third group of bytes selected from the random digital data stream. Moreover, the method comprises the step of forming the secret identification number from the first and second maximal length LFSR feedback terms, the cyclic redundancy code feedback term, and a fourth group of bytes from the random digital data stream.

Claims

1. A method of generating a secret identification number from a random digital data stream, the method comprising the steps of:

selecting a first group of bytes from the random digital data stream, said first group of bytes having a first numerical value;

looking up a first maximal length LFSR feedback term from a list in response to said first numerical value;

generating a cyclic redundancy code feedback term in response to filtering out predetermined values from a third group of bytes selected from said random digital data stream; and

forming the secret identification number from said first maximal length LFSR feedback term, said cyclic redundancy code feedback term, and a fourth group of bytes from said random digital data stream.

2. The method of generating a secret identification number from a random digital data stream of claim 1, wherein said step of generating a cyclic redundancy code feedback term comprises the steps of:

examining whether said cyclic redundancy code feedback term comprises less than two "0" bits or "1" bits; and

generating a replacement feedback term for said cyclic redundancy code feedback term if said cyclic redundancy code feedback term comprises less than two "0" bits or "1" bits.

3. The method of generating a secret identification number from a random digital data stream of claim 1, further comprising the steps of:

selecting a second group of bytes from the random digital data stream, said second group of bytes having a second numerical value; and

looking up a second maximal length LFSR feedback term from a list in response to said second numerical value such that said secret identification number is formed from said first and second maximal length LFSR feedback terma, said cyclic redundancy code feedback term, and a fourth group of bytes from said random digital data stream.

4. The method of generating a secret identification number from a random digital data stream of claim 3, further comprising the steps of:

repeating the steps of randomly selecting a first and a second group of bytes, looking up a first maximal length LFSR feedback term, looking up a second maximal length LFSR feedback term, generating a cyclic redundancy code feedback term, N times to create N secret identification numbers;

one way encrypting each of said N secret identification numbers;

computing a secure digest for each one way encrypted secret identification number of said N secret identification numbers;

comparing each one way encrypted secret identification number of said N secret identification numbers with each other one way encrypted secret identification number of said N secret identification numbers within said digest; and

discarding each one way encrypted secret identification number of said multiplicity within said digest when two identical compressed one way encrypted secret identification number are discovered.

5. A method for generating a multiplicity of random numbers, the method comprising the steps of:

generating chaotic noise;

sampling said chaotic noise such that a plurality of samples are created;

converting said plurality of samples into a random digital data stream; and

forming the multiplicity of random numbers from said random digital data stream.

6. The method for generating a multiplicity of random numbers of claim 5, wherein said step of forming the multiplicity of random numbers comprises:

shuffling said plurality of converted samples to obscure correlations between the multiplicity of random numbers.

7. The method for generating a multiplicity of random numbers of claim 5, wherein said step of forming the multiplicity of random numbers comprises:

compressing said plurality of converted samples such that each random number of the multiplicity has an equal probability of being generated.

8. The method for generating a multiplicity of random numbers of claim 5, wherein said step of forming the multiplicity of random numbers comprises:

one way encrypting said plurality of converted samples to prevent sampling the random digital data stream for extrapolating other generated values based on modeling said generated chaotic noise.

9. The method for generating a multiplicity of random numbers of claim 8, further comprising the step of:

examining said one way encrypted plurality of converted samples for duplicate converted samples; and

discarding said duplicate one way encrypted converted samples.

10. The method for generating a multiplicity of random numbers of claim 8, further comprising the step of:

exclusively ORing an independent perspective marker with said compressed plurality of converted samples to insure the randomness of the multiplicity of random numbers.

11. The method for generating a multiplicity of random numbers of claim 5, wherein said step of generating chaotic noise comprises the step of:

generating turbulent air flow.

12. The method for generating a multiplicity of random numbers of claim 11, wherein said step of generating turbulent air flow comprises the step of:

operating a fan for generating said turbulent air flow.

13. The method for generating a multiplicity of random numbers of claim 12, wherein said step of sampling is performed at a lower frequency than said fan operates.

14. The method for generating a multiplicity of random numbers of claim 5, wherein said further comprising the steps of:

selecting a first group of bytes from said random digital data stream, said first group of bytes having a first numerical value, respectively;

looking up a first maximal length LFSR feedback term from a list in response to said first numerical value;

generating a cyclic redudancy code feedback term in response to filtering out predetermined values from a third group of bytes selected from said random digital data stream; and

forming a secret identification number from said first maximal length LFSR feedback term, said cyclic redudancy code feedback term, and a fourth group of bytes from said random digital data stream.

15. The method for generating a multiplicity of random numbers of claim 14, wherein said step of generating a cyclic redudancy code feedback term comprises the step:

examing whether said cyclic redundancy code feedback term comprises less than two "0" bits or "1" bits; and

generating a replacement feedback term for said cyclic redundancy code feedback term if said cyclic redundancy code feedback term comprises less than two "0" bits or "1" bits.

16. The method for generating a multiplicity of random numbers of claim 14, further comprising the steps of:

selecting a second group of bytes from the random digital data stream, said second group of bytes having a second numerical value; and

looking up a second maximal length LFSR feedback term from a list in response to said second numerical value such that said secret identification number is formed from said first and second maximal length LFSR feedback terma, said cyclic redundancy code feedback term, and a fourth group of bytes from said random digital data stream.

17. The method for generating a multiplicity of random numbers of claim 16, further comprising the steps of:

repeating the steps of randomly selecting a first and a second group of bytes, looking up a first maximal length LFSR feedback term, looking up a second maximal length LFSR feedback term, generating a cyclic redudancy code feedback term, N times to create N secret identification numbers;

one way encrypting each of said N secret identification numbers;

computing a secure digest of each one way encrypted secret identification number of said N secret identification numbers;

comparing each one way encrypted secret identification number of said N secret identification numbers within said digest; and

discarding each one way encrypted secret identification number of said multiplicity within said digest when two identical compressed one way encrypted secret identification number are discovered.

18. A process for generating a multipicity of secure random numbers, the process comprising:

generating chaotic noise from turbulent air flow;

sampling said chaotic noise such that a plurality of samples are created;

converting said plurality of samples into a random digital data stream;

shuffling said plurality of converted samples to obscure correlations between the multiplicity of random numbers;

compressing said shuffled plurality of converted samples such that each random number of the mulitplicity has an equal probability of being generated; and

one way encrypting said compressed plurality of shuffled and converted samples such that the plurality of secure random numbers are created.

19. The process for generating a multiplicity of secure random numbers of claim 18, wherein said step of shuffling said digital data set comprises the step of:

positioning each converted sample of said plurality into a data array using a stride to reduce sampling correlations resulting from said sampling of said chaotic noise.

20. The process for generating a multiplicity of secure random numbers of claim 19, wherein said array comprises a width, said stride comprises a size, said width and said size being a prime number.

21. The process for generating a multiplicity of secure random numbers of claim 18, wherein said step of compressing said shuffled plurality of converted samples comprises the step of:

Huffman encoding said shuffled plurality of converted samples;

or

PKZIP compressing said shuffled plurality of converted samples;

or

UNIX compressing said shuffled plurality of converted samples.

22. The process for generating a multiplicity of secure random numbers of claim 18, wherein said step of one way encrypting said compressed plurality of shuffled and converted samples comprises the step of:

MD-2 encrypting said compressed plurality of shuffled and converted samples;

or

MD-4 encrypting said compressed plurality of shuffled and converted samples;

or

MD-5 encrypting said compressed plurality of shuffled and converted samples;

or

SHA encrypting said compressed plurality of shuffled and converted samples;

or

SNEFRU encrypting said compressed plurality of shuffled and converted samples.

23. The process for generating a multiplicity of secure random numbers of claim 18, further comprising the step of:

examining each encrypted sample of said plurality for a duplicate encrypted sample; and

discarding said duplicate encrypted sample to insure the uniqueness of each random number of the plurality.

24. The process for generating a multiplicity of secure random numbers of claim 18, further comprising the step of:

exclusively ORing an independent perspective marker with said compressed plurality of shuffled and converted samples to insure the randomness of the multiplicity of random numbers.

25. The process for generating a multiplicity of secure random numbers of claim 24, wherein said independent perspective marker comprises a time of day stamp.

26. The process for generating a multiplicity of secure random numbers of claim 18, wherein said step of generating chaotic noise from turbulent air flow comprises the step of:

operating a fan for generating said turbulent air flow.

27. The process for generating a multiplicity of secure random numbers of claim 24, wherein said step of sampling is performed at a lower frequency than said fan operates.

28. The process for generating a multiplicity of secure random numbers of claim 18, further comprising the steps of:

randomly selecting a first and a second group of bytes from said random digital data stream, said first and second groups of bytes having a first and a second numerical value, respectively;

looking up a first maximal length LFSR feedback term from a list according to said first numerical value;

looking up a second maximal length LFSR feedback term from said list according to said second numerical value;

generating a cyclic redudancy code feedback term in response to executing a cyclic redudancy code check on a third group of bytes selected from said random digital data stream; and

forming a secret identification number from said first and second maximal length LFSR feedback terms, said cyclic redudancy code feedback term, and a fourth group of bytes from said random digital data stream.

29. The process for generating a multiplicity of secure random numbers of claim 28, wherein said step of generating a cyclic redudancy code feedback term comprises the steps of:

examing whether said cyclic redundancy code feedback term comprises less than two "0" bits or "1" bits; and

generating a replacement feedback term for said cyclic redundancy code feedback term if said cyclic redundancy code feedback term comprises less than two "0" bits or "1" bits.

30. The process for generating a multiplicity of secure random numbers of claim 28, further comprising the steps of:

repeating the steps of randomly selecting a first and a second group of bytes, looking up a first maximal length LFSR feedback term, looking up a second maximal length LFSR feedback term, generating a cyclic redudancy code feedback term, N times to create N secret identification numbers;

one way encrypting each of said N secret identification numbers;

computing a secure digest of each one way encrypted secret identification number of said N secret identification numbers;

comparing each one way encrypted secret identification number of said N secret identification numbers within said digest; and

discarding each one way encrypted secret identification number of said multiplicity within said digest when two identical compressed one way encrypted secret identification number are discovered.