Cryptographically secure pseudo-random bit generator for fast and secure encryption

• US 6,104,811 A
• Filed: 08/15/1997
• Issued: 08/15/2000
• Est. Priority Date: 08/16/1996
• Status: Expired due to Fees

• Current Assignee: Intellectual Ventures Assets 158 LLC (Intellectual Ventures LLC)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Rajagopalan, Sivaramakrishnam, Aiello, William Anthony, Venkatesan, Ramarathnam
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): LATHAM, BRYAN S
• Application Number:
  US08/911,690
• Time in Patent Office: 1,096 Days
• Field of Search: 380/28, 380/44, 380/45, 380/46, 380/47, 708/250, 708/253, 708/245, 708/256
• US Class Current: 380/46
• CPC Class Codes: H04L 2209/122 Hardware reduction or efficient architectures
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator

Abstract

A pseudo-random number generator is used as a pre-processing step to generating a long random bit string. The bit string is then "stretched" by performing certain one-way functions in parallel on the bit strings. In a preferred embodiment, specialized constructions based on expander graphs are also used. Preferably, the strings generated by the one-way functions and expander graphs are exclusive-ored. An embodiment may operate in the following manner. Assume a slow but secure generator G₀.

1. Using G₀, generate random numbers x₁, x₂, . . . , x_n.

2. Using a stretch function, stretch the random numbers into R=r₁, r₂, . . . , r_n where each r_i is a predetermined amount longer than x_i.

3. Use R as a one-time pad for encryption.

This process provides a long, random, cryptographically secure bit string. This bit string is sufficiently fast to support encryption processes suitable for real-time, on-line encryption, such as video stream encryption and TCP/IP layer encryption.

Claims

1. Apparatus for generating an output stream of cryptographically strong pseudo-random bits from an input stream of random bits, the apparatus comprising:

means, responsive to the input stream, for forming a first seed from the input stream;

means, responsive to the input stream, for forming a second seed from the input stream;

means, responsive to the input stream, for selecting a set of bits from the input stream;

random function processor circuitry for generating a random function processor bit stream including means for performing a one-way stretching function, said means for performing the one-way stretching function comprising means for performing a plurality of parallel one-way functions to generate a plurality of larger random numbers and means for concatenating the plurality of larger random numbers to generate the random function processor bit stream;

graph processor circuitry for generating a graph processor bit stream including means for performing an expander graph function using the second seed and the set of bits from the input stream; and

means, responsive to the random function processor bit stream and the graph processor bit stream, for generating the output stream as the bitwise exclusive-OR of the random function processor bit stream and the graph processor bit stream.

2. A method for generating successive output streams of cryptographically strong pseudo-random bits from an input stream of random bits, the method comprising the steps of:

(a) responsive to the input stream, forming a first seed from the input stream for processing by a random function processor;

(b) responsive to the input stream, forming a second seed from the input stream for processing by a graph processor;

(c) responsive to the input stream, selecting a set of bits from the input stream for processing by the graph processor;

(d) in the random number processor, performing a one-way stretching function, said step of performing the one-way stretching function comprising the steps of performing a plurality of parallel one-way functions to generate a plurality of larger random numbers, and concatenating the larger random numbers to generate a random function processor bit stream;

(e) in the graph processor, performing an expander graph function using the second seed and the set of bits from the input stream to generate a graph processor bit stream;

(f) responsive to the random function processor bit stream and the graph processor bit stream, generating the output stream as the bitwise exclusive-OR of the random function processor bit stream and the graph processor bit stream; and

(g) returning to steps (c), (d), (e), and (f) to generate successive output streams.

3. A method for generating an output stream of cryptographically strong pseudo-random bits from an input stream of random bits, the method comprising the steps of:

(a) responsive to the input stream, forming a first seed from the input stream for processing by a random function processor;

(b) responsive to the input stream, forming a second seed from the input stream for processing by a graph processor;

(c) responsive to the input stream, selecting a set of bits from the input stream for processing by the graph processor;

(d) in the random number processor, performing a one-way stretching function, said step of performing the one-way stretching function comprising the steps of performing a plurality of parallel one-way functions to generate a plurality of larger random numbers, and concatenating the larger random numbers to generate a random function processor bit stream;

(e) in the graph processor, performing an expander graph function using the second seed and the set of bits from the input stream to generate a graph processor bit stream; and

(f) responsive to the random function processor bit stream and the graph processor bit stream, generating the output stream as the bitwise exclusive-OR of the random function processor bit stream and the graph processor bit stream.

4. The method of claim 3, wherein the plurality of parallel one-way functions are secure hash functions.

5. The method of claim 3 further comprising the step of performing a bitwise exclusive-OR on the output stream and a text stream to provide secure encryption.

6. A method for generating an output stream of cryptographically strong pseudo-random bits from an input stream of random bits, the method comprising the steps of:

(a) responsive to the input stream of random bits, forming a seed from the input stream for processing by a random function processor; and

(b) in the random function processor, performing a one-way stretching function on the seed as a first input, said step of performing the one-way stretching function comprising the steps of performing a plurality of one-way functions on the seed using different random numbers as second inputs to generate a plurality of larger random numbers and concatenating the larger random numbers to generate the output stream.

7. The method of claim 6 further comprising the step of performing a bitwise exclusive-OR on the output stream and a text stream to provide secure encryption.

8. The method of claim 6 further comprising repetitively performing step (b) in the random function processor to generate successive output streams.