# US 2002/0054679 A1 · Cascaded stream cipher

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2002/0054679 A1
- Document ID: US20020054679A1
- Status: Published application
- Kind: A1
- Application number: 09/947,032
- Filed: 2001-09-04
- Published: 2002-05-09
- Earliest claimed: 2000-09-07
- Inventors: Ivan Vesely
- Web page: https://patentgrep.com/patent/US20020054679A1

## CPC

- G06F 7/584: {using finite field arithmetic, e.g. using a linear feedback shift register}
- G06F 7/582: {Pseudo-random number generators}
- H04L 9/0662: {with particular pseudorandom sequence generator}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A pseudo-random number generating circuit and method, comprising: a plurality of pseudo-random number generator (PRNG) units combined in a cascade structure of several layers to produce a pseudo-random output stream, the PRNG units of any given layer running more slowly than those PRNG units of more downstream layers of the cascade structure and running more quickly than those PRNG units of more upstream layers of the cascade structure, the PRNG units including a relatively slow but cryptographically very secure PRNG unit feeding the most upstream layer of the cascade structure, and very fast, but possibly cryptographically insecure PRNG unit at the most downstream layer.

## Claims

### Claim 1

A pseudo-random number generating circuit, comprising:
a plurality of pseudo-random number generator (PRNG) units combined in a cascade structure of several layers to produce a pseudo-random output stream, the PRNG units of any given layer running more slowly than those PRNG units of more downstream layers of the cascade structure and running more quickly than those PRNG units of more upstream layers of the cascade structure, the PRNG units including a relatively slow but cryptographically very secure PRNG unit feeding the most upstream layer of the cascade structure.

### Claim 2 (depends on 1)

The circuit of claim 1 further comprising:
a plurality of operational units for combining the PRNG units into said cascade structure, each operational unit corresponding to a different layer of the cascade structure and outputting a pseudo-random stream, the most upstream operational unit connected to receive a pseudo-random stream generated by the very secure PRNG unit and all other operational units connected to receive a pseudo-random stream from the next upstream operational unit, each operational unit having means for using that received pseudo-random stream as a dynamic key to mangle pseudo-random outputs of the PRNG units which are in the same layer as that operational unit.

### Claim 3 (depends on 2)

The circuit of claim 2 wherein said means for using the received pseudo-random stream as a dynamic key includes:
a plurality of permutation units in each operational unit, each permutation unit performing a permutation upon the received dynamic key segment;
a plurality of combiner units, each combining the permuted dynamic key segment from one of the permutation units with the pseudo-random output from one of the PRNG units into a mangled output; and
means for combining the separate mangled outputs from each combiner unit into a single pseudo-random stream output of the operational unit.

### Claim 4 (depends on 3)

The circuit of claim 3 wherein the number of PRNG units in any particular layer is less than the number of different permutations that are performed by that layer, but different permutations are applied to different consecutive segments of the pseudo-random output from any one or more of the PRNG units in that layer.

### Claim 5 (depends on 4)

The circuit of claim 4 wherein the number of PRNG units in at least one of the layers is equal to one.

### Claim 6 (depends on 3)

The circuit of claim 3 wherein the number of permutation units in each particular operational unit equal the number of PRNG units that are in the same layer as that operational unit.

### Claim 7 (depends on 3)

The circuit of claim 3 wherein the assignment to particular combiners of at least some of the permutation units and PRNG units is permuted from time to time.

### Claim 8 (depends on 3)

The circuit of claim 3 wherein at least some of the permutations performed in each layer dynamically change with time.

### Claim 9 (depends on 3)

The circuit of claim 3 wherein the means for combining comprises a buffer concatenating the plurality of mangled outputs of the combiners.

### Claim 10 (depends on 1)

The circuit of claim 1 wherein all PRNG units except the very secure PRNG unit are lagged Fibonacci generators characterized by a modulus, a pair of lags, and an initial value.

### Claim 11 (depends on 10)

The circuit of claim 10 wherein any one or more of the lags, and the initial value of the lagged Fibonacci generators are initialized by a static key input.

### Claim 12 (depends on 1)

The circuit of claim 1 wherein the very secure PRNG unit comprises a quadratic residue generator characterized by a modulus and an initial value.

### Claim 13 (depends on 1)

The circuit of claim 1 wherein the initial value is initialized by a static key input.

### Claim 14 (depends on 1)

The circuit of claim 1 wherein each layer of the cascade structure combines one upstream pseudo-random stream with a plurality n of pseudo-random outputs from n PRNG units of that layer to produce a pseudo-random stream that is n times longer than the received upstream pseudo-random stream.

### Claim 15 (depends on 10)

The circuit of claim 10 wherein n=64.

### Claim 16 (depends on 1)

The circuit of claim 1 further including means for combining a message stream with the pseudo-random output stream from the most downstream layer of the cascade structure of the circuit.

### Claim 17 (depends on 16)

The circuit of claim 16 wherein the means for combining comprises a bit-wise XOR unit.

### Claim 18 (depends on 16)

The circuit of claim 16 wherein the message stream is a plaintext message and the combined output from the XOR unit is an encrypted ciphertext message stream.

### Claim 19 (depends on 16)

The circuit of claim 16 wherein the message stream is a ciphertext message and the combined output from the XOR unit is a decrypted plaintext message stream.

### Claim 20 (depends on 16)

The circuit of claim 16 wherein the means for combining comprises a modulo addition and subtraction unit, and means for selecting one of said units for a plaintext message stream and the other of said units for a ciphertext message stream.

### Claim 21 (depends on 1)

The circuit of claim 1 wherein at least some of the PRNG units and layers of the cascade structure are implemented as one or more microcontrollers running firmware permanently burned in ROM.

### Claim 22 (depends on 1)

The circuit of claim 1 wherein at least some of the PRNG units and layers of the cascade structure are implemented as one or more digital processors programmed to emulate said PRNG units and layers of cascade structure.

### Claim 23 (depends on 1)

The circuit of claim 1 wherein the PRNG units and layers of the cascade structure forming said circuit are implemented by a general purpose programmable computer running a software program emulating said PRNG units and layers of the cascade structure.

### Claim 24

A pseudo-random number generating circuit, comprising:
a plurality of pseudo-random number generator (PRNG) units combined in a cascade structure of several layers to produce a pseudo-random output stream, the PRNG units of any given layer running more slowly than those PRNG units of more downstream layers of the cascade structure and running more quickly than those PRNG units of more upstream layers of the cascade structure, the PRNG units including a quadratic residue generator unit feeding the most upstream layer of the cascade structure and a plurality of lagged Fibonacci generator units corresponding to each of the layers of the cascade structure, each PRNG unit being initialized by a static key input that sets at least an initial value for each of the PRNG units; and
a plurality of operational units for combining the PRNG units into said cascade structure, each operational unit corresponding to a different layer of the cascade structure and outputting a pseudo-random stream, the most upstream operational unit connected to receive a pseudo-random stream generated by the quadratic residue generator unit and all other operational units connected to receive a pseudo-random stream from the next upstream operational unit, each operational unit having means for using that received pseudo-random stream as a dynamic key to mangle pseudo-random outputs of the lagged Fibonacci generator units which are in the same layer as that operational unit.

### Claim 25 (depends on 24)

The circuit of claim 24 wherein each of the lagged Fibonacci generator units is characterized by a modulus m, a pair of lags p and q, and a set of initial values x[1] . . . x[p], such that x[n]=(x[n-p]+x[n-q]) mod m, with p>q>0, and at least the initial values are set by the static key input, and p and q may be different for each lagged Fibonacci generator unit in the cascade structure.

### Claim 26 (depends on 24)

The circuit of claim 24 wherein said means for using the received pseudo-random stream as a dynamic key includes:
a plurality of permutation units in each operational unit equal in number to the lagged Fibonacci generator units which are in the same layer as the operational unit, each permutation unit performing a permutation upon the received dynamic key segment;
a plurality of combiner units, each combining the permuted dynamic key segment from one of the permutation units with the pseudo-random output from one of the lagged Fibonacci generator units into a mangled output; and
means for combining the separate mangled outputs from each combiner unit into a single pseudo-random stream output of the operational unit.

### Claim 27 (depends on 26)

The circuit of claim 26 wherein each permutation unit executes a permutation that is initialized by the static key input.

### Claim 28 (depends on 26)

The circuit of claim 26 wherein the combining means comprises a buffer connected to receive the separate mangled outputs, the combining means outputting a concatenated string of the mangled outputs.

### Claim 29

A pseudo-random number generating method implemented as a software or firmware program in digital processing hardware, the digital processing hardware executing the following programmed steps:
performing, in any order, a first, relatively rapid, pseudo-random number generating procedure a plurality of times for each time a second, relatively slow but cryptographically very secure, pseudo-random number generating procedure is also performed, each performance of either generating procedure producing a segment of a stream of pseudo-random numbers as a result thereof; and
successively performing a pseudo-random stream mangling operation a plurality of times upon the plurality of segments of streams of pseudo-random numbers generated by the preceding step to produce an overall pseudo-random output stream,
the plurality of performances of the generating procedures and mangling operation being ordered in a cascade sequence of several operational layers in which each layer's execution of the mangling operation uses a plurality n segments of a stream of pseudo-random numbers resulting from successive execution of said first generating procedure as an operand input and another segment of a stream of pseudo-random stream numbers as a dynamic key input and produces a third segment of a stream of pseudo-random numbers as an output, the relative sequential order of producing the operand input and the dynamic key input for any given mangling operation being irrelevant to the performance of that mangling operation, the dynamic key input for a most upstream operational layer of the ordered cascade sequence being a segment of a stream of pseudo-random numbers resulting from execution of said second generating procedure, the dynamic key input for all downstream operational layers of the ordered cascade sequence being the output segment of a stream of pseudo-random numbers from the mangling operation of the next upstream operational layer.

### Claim 30 (depends on 29)

The method of claim 29 wherein the mangling operation is accomplished by combining a plurality of permutations of said dynamic key with a plurality of segments of streams of pseudo-random numbers.

### Claim 31 (depends on 30)

The method of claim 30 wherein the assignment of a particular combining operation to at least some of the permutations and segments of a stream of pseudo-random numbers dynamically changes from time to time.

### Claim 32 (depends on 29)

The method of claim 29 wherein the permutations dynamically change from time to time.

### Claim 33 (depends on 29)

The method of claim 29 wherein the first, relatively rapid, pseudo-random number generating procedure comprises a lagged Fibonacci operation characterized by a pair of lags p>q>0 and a set of p initial values x[1] . . . x[p], set by a static key input, such that each successive generated word x[n]=(x[n-p]+x[n-q]) mod m.

### Claim 34 (depends on 29)

The method of claim 29 wherein the second, relatively slow but very secure, pseudo-random number generating procedure comprises a quadratic residue operation.

### Claim 35 (depends on 29)

The method of claim 29 wherein n=64 and each successive operational layer's output from the mangling operation is n times longer than that from the next upstream layer of the cascade structure.

### Claim 36 (depends on 29)

The method of claim 29 wherein the digital processing hardware comprises one or more microcontrollers running firmware permanently burned in ROM.

### Claim 37 (depends on 29)

The method of claim 29 wherein the digital processing hardware comprises one or more general purpose programmable computers running a software program executing the programmed steps.
