Pseudo-random sequence generator
First Claim
Patent Images
1. A random sequence generator for generating a random sequence from a seed random sequence of substantially shorter length, the generator performing a tree operation by extending, at each node of a tree structure, a node input random sequence into a longer node output random sequence, a plurality of node output random sequences of the tree structure together comprising a final random output sequence.
1 Assignment
0 Petitions
Accused Products
Abstract
A seed random sequence is extended in successive nodes of a tree structure of a random sequence generator. At each node, an input sequence is expanded to an output sequence substantially greater than the length of the input sequence. Plural processors operate in parallel in generating the final output sequence, and subsequences may be directly accessed as a starting location of the output sequence. The random sequence generator is accessed by an index in an encryption system. In a sequential generator, less than all of the bits from the generator unit are reapplied to the generator unit in an iterative process.
87 Citations
60 Claims
-
1. A random sequence generator for generating a random sequence from a seed random sequence of substantially shorter length, the generator performing a tree operation by extending, at each node of a tree structure, a node input random sequence into a longer node output random sequence, a plurality of node output random sequences of the tree structure together comprising a final random output sequence.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
3. A random sequence generator as claimed in claim 2 wherein there is at least one ad of ae,
ae-1, . . . ,a3 not equal to zero and the greatest common divisor of d and φ - (N) is equal to one where φ
(N) is Euler'"'"'s Totient function.
- (N) is equal to one where φ
-
4. A random sequence generator as claimed in claim 2 where N is the product of two large random primes p and q.
-
5. A random sequence generator as claimed in claim 4 wherein at least one ad of ae, ae-1, . . . ,a3 is nonzero, and d is an integer that is relatively prime to (p-1)(q-1).
-
6. A random sequence generator as claimed in claim 5 wherein all coefficients of the polynomial of y are equal to zero except the coefficient a3.
-
7. A random sequence generator as claimed in claim 6 where a3 is equal to one.
- 8. A random sequence generator as claimed in claim 1 wherein each node input sequence is extended by the operation
- space="preserve" listing-type="equation">y=ax.sup.d (mod N)
where N is the product of two large random primes p and q, d is an integer that is relatively prime to (p-1)(q-1), the node input sequence represents x and the node output sequence represents y.
-
9. A random sequence generator as claimed in claim 8 wherein d is equal to 3.
-
10. A random sequence generator as claimed in claim 1 wherein each node input sequence is extended by a single modular operation.
-
11. A random sequence generator as claimed in claim 1 wherein less than all of the bits of node output sequences are reapplied as node input sequences of the tree structure.
-
12. A random sequence generator for generating a random sequence from a seed random sequence of substantially shorter length, the generator performing a tree operation by extending, at each node of a tree structure, a node input random sequence into a longer node output random sequence, a final random output sequence being generated as successive leaves of the tree structure.
- View Dependent Claims (13, 14, 15, 16)
-
14. A random sequence generator as claimed in claim 13 wherein d is equal to 3.
-
15. A random sequence generator as claimed in claim 12 wherein each node input sequence is extended by a single modular operation.
- 16. A random sequence generator as claimed in claim 12 wherein each node input sequence is extended by the operation
- space="preserve" listing-type="equation">y=a.sub.e x.sup.e +a.sub.e-1 x.sup.e-1 + . . . +a.sub.1 x+a.sub.0 (mod N)
where e, ae, ae-1, . . . ,a0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one ad of ae, ae-1, . . . ,a3 not equal to zero and the greatest common divisor of d and φ
(N) is equal to one where φ
(N) is Euler'"'"'s Totient function.
-
17. A random sequence generator for generating a random sequence from a seed random sequence of substantially shorter length, the generator comprising a plurality of processors, each processor extending a node input random sequence into a longer node output random sequence, each of the plurality of processors performing a portion of a tree structure by extending a node input sequence and then separately extending different portions of a node output sequence in successive operations at successive nodes of the tree structure.
- View Dependent Claims (18, 19, 20, 21)
-
19. A random sequence generator as claimed in claim 18 wherein d is equal to 3.
-
20. A random sequence generator as claimed in claim 17 wherein each node input sequence is extended by a single modular operation.
- 21. A random sequence generator as claimed in claim 17 wherein each node input sequence is extended by the operation
- space="preserve" listing-type="equation">y=a.sub.e x.sup.e +a.sub.e-1 x.sup.e-1 + . . . +a.sub.1 x+a.sub.0 (mod N)
where e, ae, ae-1, . . . ,a0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one ad of ae, ae-1, . . . ,a3 not equal to zero and the greatest common divisor of d and φ
(N) is equal to one where (N) is Euler'"'"'s Totient function.
-
22. A method of generating a random sequence from a seed random sequence of substantially shorter length, comprising performing a tree operation by extending, at each node of the tree structure, a node input random sequence into a longer node output random sequence, a final random output sequence being generated from successive leaves of the tree structure.
- View Dependent Claims (23, 24, 25, 26)
-
24. A method as claimed in claim 23 wherein d is equal to 3.
-
25. A method as claimed in claim 22 wherein each node input sequence is extended by a single modular operation.
- 26. A random sequence generator as claimed in claim 22 wherein each node input sequence is extended by the operation
- space="preserve" listing-type="equation">y=a.sub.e x.sup.e +a.sub.e-1 x.sup.e-1 + . . . +a.sub.1 x+a.sub.0 (mod N)
where e, ae, ae-1, . . . ,a0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one ad of ae, ae-1, . . . ,a3 not equal to zero and the greatest common divisor of d and φ
(N) is equal to one where φ
(N) is Euler'"'"'s Totient function.
-
27. A method of generating a random sequence from a seed random sequence of substantially shorter length comprising performing a tree operation by extending, at each node of a tree structure, a node input random sequence into a longer node output random sequence, a plurality of node output random sequences of the tree structure together comprising a final random output sequence.
- View Dependent Claims (28, 29, 30, 31)
-
29. A method as claimed in claim 28 wherein d is equal to 3.
-
30. A method as claimed in claim 27 wherein each node input sequence is extended by a single modular operation.
- 31. A random sequence generator as claimed in claim 27 wherein each node input sequence is extended by the operation
- space="preserve" listing-type="equation">y=a.sub.e x.sup.e +a.sub.e-1 x.sup.e-1 + . . . +a.sub.1 x+a.sub.0 (mod N)
where e, ae, ae-1, . . . ,a0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one ad of ae, ae-1, . . . ,a3 not equal to zero and the greatest common divisor of d and φ
(N) is equal to one where φ
(N) is Euler'"'"'s Totient function.
-
32. A method of generating a random sequence from a seed random sequence of substantially shorter length comprising in each of a plurality of processors, extending a node input random sequence into a longer node output random sequence, each of the plurality of processors performing a portion of a tree structure by extending a node input sequence and then separately extending different portions of a node output sequence in successive operations at successive nodes of the tree structure.
- View Dependent Claims (33, 34, 35, 36)
-
34. A method as claimed in claim 33 wherein d is equal to 3.
-
35. A method as claimed in claim 32 wherein each node input sequence is extended by a single modular operation.
- 36. A random sequence generator as claimed in claim 32 wherein each node input sequence is extended by the operation
- space="preserve" listing-type="equation">y=a.sub.e x.sup.e +a.sub.e-1 x.sup.e-1 + . . . +a.sub.1 x+a.sub.0 (mod N)
where e, ae, ae-1, . . . ,a0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one ad of ae, ae-1, . . . ,a3 not equal to zero and the greatest common divisor of d and φ
(N) is equal to one where φ
(N) is Euler'"'"'s Totient function.
-
37. An encryption system comprising an encryption unit for performing a transform between encrypted and nonencrypted messages, based on an extended random sequence, and a random sequence generator for generating the random sequence from a seed random sequence and an index input, the random sequence generator performing a tree operation by extending, at each node of a tree structure, a node input random sequence into a longer node output random sequence.
- View Dependent Claims (38, 39, 40, 41, 42, 43, 44)
-
39. An encryption system as claimed in claim 38 wherein d is equal to 3.
-
40. An encryption system as claimed in claim 37 wherein each node input sequence is extended by a single modular operation.
-
41. An encryption system as claimed in claim 37 wherein the random sequence applied to the encryption unit comprises a plurality of node output random sequences of the tree structure.
-
42. An encryption system as claimed in claim 41 wherein the random sequence applied to the encryption unit is generated as successive leaves of the tree structure.
-
43. An encryption system as claimed in claim 37 wherein the random sequence generator comprises a plurality of processors, each of the plurality of processors performing a portion of the tree structure.
- 44. A random sequence generator as claimed in claim 37 wherein each node input sequence is extended by the operation
- space="preserve" listing-type="equation">y=a.sub.e x.sup.e +a.sub.e-1 x.sup.e-1 + . . . +a.sub.1 x+a.sub.0 (mod N)
where e, ae, ae-1, . . . ,a0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one ad of ae, ae-1, . . . ,a3 not equal to zero and the greatest common divisor of d and φ
(N) is equal to one where φ
(N) is Euler'"'"'s Totient function.
- 45. A method of message encryption comprising generating a random sequence from a seed random sequence and an index input, the random sequence being generated in a tree operation by extending, at each node of a tree structure, a node input random sequence into a longer node output random sequence and, based on the extended random sequence, performing a transform between encrypted and nonencrypted messages.
-
51. A method of generating a random sequence from a random seed comprising, in each of iterative steps, applying a function to an input string of random bits to obtain an output string of bits, significantly less than all of an output string of bits being used in an input string of bits in each successive step, and utilizing other bits of the output string toward the random sequence.
- View Dependent Claims (52, 53, 54, 55, 56)
- 56. A random sequence generator as claimed in claim 51 wherein each input string of bits is extended by the function
- space="preserve" listing-type="equation">y=a.sub.e x.sup.e +a.sub.e-1 x.sup.e-1 + . . . +a.sub.1 x+a.sub.0 (mod N)
where e, ae, ae-1, . . . ,a0 and N are integers, the input string represents x and the output string represents y, and where there is at least one ad of ae, ae-1, . . . ,a3 not equal to zero and the greatest common divisor of d and φ
(N) is equal to one where φ
(N) is Euler'"'"'s Totient function.
-
57. A method of generating a random sequence from a random seed comprising, in each of iterative steps, applying a function to an input string of random bits to obtain an output string of bits, significantly less than all of an output string of bits being used as an input string of bits in each successive step, at least some of the bits of each output string being a part of the generated random sequence.
- View Dependent Claims (58, 59, 60)
- 60. A random sequence generator as claimed in claim 57 wherein each input string of bits is extended by the function
- space="preserve" listing-type="equation">y=a.sub.e x.sup.e +a.sub.e-1 x.sup.e-1 + . . . +a.sub.1 x+a.sub.0 (mod N)
where e, ae, ae-1, . . . ,a0 and N are integers, the input string represents x and the output string represents y, and where there is at least one ad of ae, ae-1, . . . ,a3 not equal to zero and the greatest common divisor of d and φ
(N) is equal to one where φ
(N) is Euler'"'"'s Totient function.
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeMassachusetts Institute of Technology
-
Original AssigneeMassachusetts Institute of Technology
-
InventorsMicali, Silvio, Schnorr, Claus
-
Primary Examiner(s)Buczinski, Stephen C.
-
Assistant Examiner(s)Gregory, Bernarr Earl
-
Application NumberUS07/160,354Time in Patent Office880 DaysField of Search364/717, 364/200, 364/900, 364/224.21, 331/78, 380/46, 380/50, 380/49, 380/28-30US Class Current380/46CPC Class CodesH04L 2209/125 Parallelization or pipelini...H04L 2209/26 Testing cryptographic entit...H04L 9/0662 with particular pseudorando...
