Chaos generator for accumulation of stream entropy

• US 7,587,047 B2
• Filed: 06/22/2005
• Issued: 09/08/2009
• Est. Priority Date: 06/22/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Tribble, Guy, Krueger, Scott, Crandall, Richard E., Mitchell, Douglas P.
• Primary Examiner(s): CERVETTI, DAVID GARCIA
• Application Number:
  US11/159,657
• Publication Number:
  US 20060291649A1
• Time in Patent Office: 1,539 Days
• Field of Search: 380/46, 380/263, 713/176
• US Class Current: 380/46
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 9/001 using chaotic signals
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

A chaos generator for accumulating stream entropy is disclosed. The chaos generator includes a random source coupled to an entropy accumulator that is configurable for generating a binary random input sequence. The entropy accumulator is configurable for accumulating entropy of the input sequence and providing a binary random output sequence based on the accumulated entropy. The binary random output sequence is reduced by a modular reduction operation having a modulus that is set equal to a cryptographic prime (e.g., the order of an elliptic curve). The number of iterations performed by the entropy accumulator on the binary random input sequence is selected to provide a binary random output sequence having a desired cryptographic strength. The chaos generator can be part of a signing and verification system that uses fast elliptic encryption for small devices.

Claims

1. A digital hardware device, comprising:

a pseudo-random source, implemented in hardware, configurable for generating a binary pseudo-random input sequence having a first entropy; and

an entropy accumulator, implemented in hardware, coupled to the pseudo-random source and configurable for accumulating the first entropy and providing a binary pseudo-random output sequence based on the accumulated first entropy and a cryptographic prime.

2. The digital hardware device of claim 1, wherein the pseudo-random source is a low-entropy pseudo-random number generator.

3. The digital hardware device of claim 1, wherein the entropy accumulator is a chaos system.

4. The digital hardware device of claim 3, wherein the chaos system is a chaotic map.

5. The digital hardware device of claim 4, wherein the chaotic map is a quartic chaotic map.

6. The digital hardware device of claim 5, wherein the quartic chaotic map is given by r_n+1= ((r_n+w_n)⁴+(r_n+n)⁴) mod p , where w is an m-bit portion of the input sequence, n is the current iteration of the quartic chaotic map, p is the cryptographic prime, and r_n+1 is a q-bit portion of the output sequence.

7. The digital hardware device of claim 1, wherein the entropy accumulator accumulates at least N samples generated by the pseudo-random source, where

8. The digital hardware device of claim 7, wherein the first entropy E is 2.9 bits per sample.

9. The digital hardware device of claim 1, wherein the cryptographic prime is set equal to an order of an elliptic curve.

10. A method of accumulating entropy, comprising:

at a first communication device coupled to a second communication device via an unsecured channel;

receiving a first pseudo-random sequence associated with a first entropy;

accumulating the first entropy;

generating a second binary pseudo-random sequence from the accumulated first entropy and a cryptographic prime; and

using the second binary pseudo-random sequence to generate or verify a digital signature to establish a communication session between the first and second communication devices over the unsecured channel.

11. The method of claim 10, further comprising:

repeating the accumulating step until the second binary sequence is of cryptographic strength.

12. The method of claim 11, further comprising:

periodically updating the second binary pseudo-random sequence based on a new binary pseudo-random sequence.

13. The method of claim 11, wherein the accumulating step is repeated at least N times, where

14. The method of claim 10, wherein the accumulating step includes iterating a chaotic map.

15. The method of claim 14, wherein the chaotic map is a quartic chaotic map given by r_n+1=((r_n+w_n)⁴+(r_n+n)⁴)mod p ,where w is an rn-bit portion of the input sequence, n is the current iteration of the quartic chaotic map, p is the cryptographic prime, and r_n+1 is a q-bit portion of the output sequence.

16. A computer-readable medium storing one or more programs configured to be executed by a computer system, the one or more programs comprising:

instructions to receive a first pseudo-random sequence associated with a first entropy;

instructions to accumulate the first entropy; and

instructions to generate a second binary pseudo-random sequence from the accumulated first entropy and a cryptographic prime, wherein the second binary pseudo-random sequence is associated with a second entropy that is higher than the first entropy.

17. The computer readable storage medium of claim 16, further comprising:

instructions to repeat the accumulating step until the second binary sequence is of cryptographic strength.

18. The computer readable storage medium of claim 17, further comprising:

instructions to periodically update the second binary pseudo-random sequence based on a new binary pseudo-random sequence.

19. The computer readable storage medium of claim 17, wherein the instructions to repeat the accumulating step include instructions to repeat the accumulating step at least N times, where

20. The computer readable storage medium of claim 16, wherein the instructions to accumulate the first entropy include instructions to iterate a chaotic map.

21. The computer readable storage medium of claim 20, wherein the chaotic map is a quartic chaotic map given by r_n+1=((r_n+wn)⁴+(r_n+n)⁴) mod p ,where w is an rn-bit portion of the input sequence, n is the current iteration of the quartic chaotic map, p is the cryptographic prime, and r_n+1is a q-bit portion of the output sequence.

22. A digital signature generation system, comprising:

a processor;

a computer readable medium coupled to the processor and having stored thereon instructions, which, when executed by the processor, causes the processor to perform the operations of;

receiving a first pseudo-random number;

accumulating entropy associated with the first pseudo-random number;

generating a second pseudo-random number from the accumulated entropy, wherein the second pseudo-random number is from a finite field of numbers;

generating field elements defining a first point on an elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the second pseudo-random number and an initial public point on the elliptic curve;

generating a product from a field element, a private key, and a third pseudo-random number from the finite field of numbers, wherein the third pseudo-random number is received from a challenger seeking verification of a digital signature;

generating a signature component by summing the product and the second pseudo- random number;

reducing the signature component using one or more modular reduction operations, wherein the modular reduction operations are based on a modulus equal to an order of the elliptic curve; and

sending the signature component and the field elements to the challenger as a signature for verification by the challenger.

23. A digital signature verification system, comprising:

a processor;

a computer readable medium coupled to the processor and having stored thereon instructions, which, when executed by the processor, causes the processor to perform the operations of;

generating a first pseudo-random number;

accumulating entropy associated with the first pseudo-random number;

generating a second pseudo-random number based on the accumulated entropy, wherein the second pseudo-random number is from a finite field of numbers;

sending the second pseudo-random number to a signing device;

receiving a digital signature packet from the signing device including a first point on an elliptic curve defined over the finite field of numbers and a signature component, wherein the signature is a function of the second pseudo-random number and a third pseudo-random number generated by the signing device;

generating a second point on the elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the signature component and an initial public point on the elliptic curve;

generating a product from the second point and the second pseudo-random number;

reducing the product using one or more modular operations, wherein the modular operations are based on a modulus equal to an order of the elliptic curve;

generating a third point on the elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the reduced product and a public point on the elliptic curve representing a public key of the signing device; and

evaluating an elliptic identity using the first, second and third points, wherein the result of the evaluation is indicative of either a positive or negative verification of the digital signature.

24. A communication device, comprising:

memory;

one or more processors; and

one or more programs stored in the memory and configured for execution by the one or more processors, the one or more programs including;

instructions to receive a first pseudo-random sequence associated with a first entropy;

instructions to accumulate the first entropy;

instructions to generate a second binary pseudo-random sequence from the accumulated first entropy and a cryptographic prime; and

instructions to use the second binary pseudo-random sequence to generate or verify a digital signature to establish a communication session between the first and second communication devices.

25. The communication device of claim 24, further comprising:

instructions to repeat the accumulating step until the second binary sequence is of cryptographic strength.

26. The communication device of claim 25, further comprising:

instructions to periodically update the second binary pseudo-random sequence based on a new binary pseudo-random sequence.

27. The communication device of claim 25, wherein the instructions to repeat the accumulating step include instructions to repeat the accumulating step at least N times, where

28. The communication device of claim 24, wherein the instructions to accumulate the first entropy include instructions to iterate a chaotic map.

29. The communication device of claim 28, wherein the chaotic map is a quartic chaotic map given by r_n+1=((r_n+w_n)⁴+(r_n+n)⁴) mod p ,where w is an rn-bit portion of the input sequence, n is the current iteration of the quartic chaotic map, p is the cryptographic prime, and r_n+1 is a q-bit portion of the output sequence.