US4944009A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pseudo-random sequence generator
Assignee: Massachusetts Institute of Technology
•
Filing: 1988-02-25
•
Granted: 1990-07-24
•
Expires: 2008-02-25
Abstract
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.
Inventors
- 👤 Silvio Micali
- 👤 Claus Schnorr
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 21:12
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/06; H04L9/065; H04L9/0656; H04L9/0662; H04L2209/00; H04L2209/12; H04L2209/125; H04L2209/26
Claims Analysis
Total Claims: 70
Claim 1
Independent Claim
63 words
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.
Claim 2
Dependent Claim
63 words
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.
Claim 3
Dependent Claim
61 words
A random sequence generator as claimed in claim 1 wherein each node input sequence is extended by the operation 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, a e , a e-1 , . . . ,a 0 and N are integers, the node input sequence represents x and the node output sequence represents y.
Claim 4
Dependent Claim
52 words
A random sequence generator as claimed in claim 2 wherein there is at least one a d of a e , a e-1 , . . . ,a 3 not equal to zero and the greatest common divisor of d and φ(N) is equal to one where φ(N) is Euler's Totient function.
Claim 5
Dependent Claim
22 words
A random sequence generator as claimed in claim 2 where N is the product of two large random primes p and q.
Claim 6
Dependent Claim
40 words
A random sequence generator as claimed in claim 4 wherein at least one a d of a e , a e-1 , . . . ,a 3 is nonzero, and d is an integer that is relatively prime to (p-1)(q-1).
Claim 7
Dependent Claim
27 words
A random sequence generator as claimed in claim 5 wherein all coefficients of the polynomial of y are equal to zero except the coefficient a 3 .
Claim 8
Dependent Claim
16 words
A random sequence generator as claimed in claim 6 where a 3 is equal to one.
Claim 9
Dependent Claim
58 words
A random sequence generator as claimed in claim 1 wherein each node input sequence is extended by the operation 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.
Claim 10
Dependent Claim
15 words
A random sequence generator as claimed in claim 8 wherein d is equal to 3.
Claim 11
Dependent Claim
21 words
A random sequence generator as claimed in claim 1 wherein each node input sequence is extended by a single modular operation.
Claim 12
Dependent Claim
30 words
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.
Claim 13
Dependent Claim
59 words
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.
Claim 14
Dependent Claim
59 words
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.
Claim 15
Dependent Claim
58 words
A random sequence generator as claimed in claim 12 wherein each node input sequence is extended by the operation 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.
Claim 16
Dependent Claim
15 words
A random sequence generator as claimed in claim 13 wherein d is equal to 3.
Claim 17
Dependent Claim
21 words
A random sequence generator as claimed in claim 12 wherein each node input sequence is extended by a single modular operation.
Claim 18
Dependent Claim
105 words
A random sequence generator as claimed in claim 12 wherein each node input sequence is extended by the operation 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, a e , a e-1 , . . . ,a 0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one a d of a e , a e-1 , . . . ,a 3 not equal to zero and the greatest common divisor of d and φ(N) is equal to one where φ(N) is Euler's Totient function.
Claim 19
Dependent Claim
80 words
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.
Claim 20
Dependent Claim
80 words
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.
Claim 21
Dependent Claim
58 words
A random sequence generator as claimed in claim 17 wherein each node input sequence is extended by the operation 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.
Claim 22
Dependent Claim
15 words
A random sequence generator as claimed in claim 18 wherein d is equal to 3.
Claim 23
Dependent Claim
21 words
A random sequence generator as claimed in claim 17 wherein each node input sequence is extended by a single modular operation.
Claim 24
Dependent Claim
105 words
A random sequence generator as claimed in claim 17 wherein each node input sequence is extended by the operation 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, a e , a e-1 , . . . ,a 0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one a d of a e , a e-1 , . . . ,a 3 not equal to zero and the greatest common divisor of d and φ(N) is equal to one where (N) is Euler's Totient function.
Claim 25
Independent Claim
56 words
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.
Claim 26
Independent Claim
56 words
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.
Claim 27
Dependent Claim
56 words
A method as claimed in claim 22 wherein each node input sequence is extended by the operation 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.
Claim 28
Dependent Claim
13 words
A method as claimed in claim 23 wherein d is equal to 3.
Claim 29
Dependent Claim
19 words
A method as claimed in claim 22 wherein each node input sequence is extended by a single modular operation.
Claim 30
Dependent Claim
105 words
A random sequence generator as claimed in claim 22 wherein each node input sequence is extended by the operation 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, a e , a e-1 , . . . ,a 0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one a d of a e , a e-1 , . . . ,a 3 not equal to zero and the greatest common divisor of d and φ(N) is equal to one where φ(N) is Euler's Totient function.
Claim 31
Independent Claim
60 words
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.
Claim 32
Independent Claim
60 words
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.
Claim 33
Dependent Claim
56 words
A method as claimed in claim 27 wherein each node input sequence is extended by the operation 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.
Claim 34
Dependent Claim
13 words
A method as claimed in claim 28 wherein d is equal to 3.
Claim 35
Dependent Claim
19 words
A method as claimed in claim 27 wherein each node input sequence is extended by a single modular operation.
Claim 36
Dependent Claim
105 words
A random sequence generator as claimed in claim 27 wherein each node input sequence is extended by the operation 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, a e , a e-1 , . . . ,a 0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one a d of a e , a e-1 , . . . ,a 3 not equal to zero and the greatest common divisor of d and φ(N) is equal to one where φ(N) is Euler's Totient function.
Claim 37
Independent Claim
77 words
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.
Claim 38
Independent Claim
77 words
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.
Claim 39
Dependent Claim
56 words
A method as claimed in claim 32 wherein each node input sequence is extended by the operation 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.
Claim 40
Dependent Claim
13 words
A method as claimed in claim 33 wherein d is equal to 3.
Claim 41
Dependent Claim
19 words
A method as claimed in claim 32 wherein each node input sequence is extended by a single modular operation.
Claim 42
Dependent Claim
105 words
A random sequence generator as claimed in claim 32 wherein each node input sequence is extended by the operation 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, a e , a e-1 , . . . ,a 0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one a d of a e , a e-1 , . . . ,a 3 not equal to zero and the greatest common divisor of d and φ(N) is equal to one where φ(N) is Euler's Totient function.
Claim 43
Dependent Claim
70 words
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.
Claim 44
Dependent Claim
70 words
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.
Claim 45
Dependent Claim
57 words
An encryption system as claimed in claim 37 wherein each node input sequence is extended by the operation 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.
Claim 46
Dependent Claim
14 words
An encryption system as claimed in claim 38 wherein d is equal to 3.
Claim 47
Dependent Claim
20 words
An encryption system as claimed in claim 37 wherein each node input sequence is extended by a single modular operation.
Claim 48
Dependent Claim
29 words
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.
Claim 49
Dependent Claim
26 words
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.
Claim 50
Dependent Claim
31 words
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.
Claim 51
Dependent Claim
105 words
A random sequence generator as claimed in claim 37 wherein each node input sequence is extended by the operation 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, a e , a e-1 , . . . ,a 0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one a d of a e , a e-1 , . . . ,a 3 not equal to zero and the greatest common divisor of d and φ(N) is equal to one where φ(N) is Euler's Totient function.
Claim 52
Independent Claim
64 words
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.
Claim 53
Independent Claim
64 words
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.
Claim 54
Dependent Claim
19 words
A method as claimed in claim 45 wherein each node input sequence is extended by a single modular operation.
Claim 55
Dependent Claim
28 words
A method as claimed in claim 45 wherein the random sequence applied to the encryption unit comprises a plurality of node output random sequences of the tree structure.
Claim 56
Dependent Claim
25 words
A method as claimed in claim 47 wherein the random sequence applied to the encryption unit is generated as successive leaves of the tree structure.
Claim 57
Dependent Claim
30 words
A method as claimed in claim 45 wherein the random sequence generator comprises a plurality of processors, each of the plurality of processors performing a portion of the tree structure.
Claim 58
Dependent Claim
105 words
A random sequence generator as claimed in claim 45 wherein each node input sequence is extended by the operation 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, a e , a e-1 , . . . ,a 0 and N are integers, the node input sequence represents x and the node output sequence represents y, and where there is at least one a d of a e , a e-1 , . . . ,a 3 not equal to zero and the greatest common divisor of d and φ(N) is equal to one where φ(N) is Euler's Totient function.
Claim 59
Independent Claim
68 words
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.
Claim 60
Independent Claim
68 words
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.
Claim 61
Dependent Claim
27 words
A method as claimed in claim 51 wherein each input string is about 2/3 or less of the bits of the output string from the previous step.
Claim 62
Dependent Claim
24 words
A method as claimed in claim 51 wherein the other bits utilized toward the random sequence are a part of the generated random sequence.
Claim 63
Dependent Claim
36 words
A method as claimed in claim 51 wherein the iterative steps are performed in a tree operation and the function is also applied to the other bits of the output string utilized toward the random sequence.
Claim 64
Dependent Claim
76 words
A method as claimed in claim 51 wherein each output string of bits is obtained by the function 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, a e , a e-1 , . . . ,a 0 and N are integers, the input string represents x and the output string represents y and where the number of bits in x is significantly less than the number of bits in N.
Claim 65
Dependent Claim
104 words
A random sequence generator as claimed in claim 51 wherein each input string of bits is extended by the function 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, a e , a e-1 , . . . ,a 0 and N are integers, the input string represents x and the output string represents y, and where there is at least one a d of a e , a e-1 , . . . ,a 3 not equal to zero and the greatest common divisor of d and φ(N) is equal to one where φ(N) is Euler's Totient function.
Claim 66
Independent Claim
74 words
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.
Claim 67
Independent Claim
74 words
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.
Claim 68
Dependent Claim
27 words
A method as claimed in claim 57 wherein each input string is about 2/3 or less of the bits of the output string from the previous step.
Claim 69
Dependent Claim
76 words
A method as claimed in claim 57 wherein each output string of bits is obtained by the function 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, a e , a e-1 , . . . ,a 0 and N are integers, the input string represents x and the output string represents y and where the number of bits in x is significantly less than the number of bits in N.
Claim 70
Dependent Claim
104 words
A random sequence generator as claimed in claim 57 wherein each input string of bits is extended by the function 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, a e , a e-1 , . . . ,a 0 and N are integers, the input string represents x and the output string represents y, and where there is at least one a d of a e , a e-1 , . . . ,a 3 not equal to zero and the greatest common divisor of d and φ(N) is equal to one where φ(N) is Euler's Totient function.
References Cited (Backward Citations)
US4405829A
Cited
SU785859A1
Cited
US4208739A
Cited
CA1174364A
Cited
DE3339985A1
Cited
US4799259A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-07-23 | 1994-01-22 | 1994-07-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-07-23 | 1998-01-22 | 1998-07-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-07-23 | 2002-01-22 | 2002-07-24 | $7700.00 | Window Closed / Lapsed |