# US 2020/0401375 A1 · Random Number Generator

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

- Number: US 2020/0401375 A1
- Document ID: US20200401375A1
- Status: Published application
- Kind: A1
- Application number: 16/613,516
- Filed: 2017-11-07
- Published: 2020-12-24
- Earliest claimed: 2017-11-07
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Jan Wassenberg; Obryk Robert; Jyrki Alakuijala; Emmanuel Mogenet
- Web page: https://patentgrep.com/patent/US20200401375A1

## CPC

- G06F 7/582: {Pseudo-random number generators}
- H04L 9/0625: {with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI}
- H04L 9/0631: {Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms}
- H04L 9/0869: {involving random numbers or seeds}
- 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 method for generating random numbers includes initializing a pseudo-random number generator (PRNG) having a state of 2048 bits comprising inner bits and outer bits, the inner bits comprising the first 128 bits of the 2048 bits and the outer bits comprising the remaining bits of the 2048 bits. The method also includes retrieving AES round keys from a key source, and for a threshold number of times, executing a round function using the AES round keys by XOR'ing odd-numbered branches of a Feistel network having 16 branches of 128 bits with a function of corresponding even-numbered neighbor branches of the Feistel network, and shuffling each branch of 128 bits into a prescribed order. The method also includes executing an XOR of the inner bits of the permuted state with the inner bits of a previous state.

## Claims

### Claim 1

A method for generating random numbers, the method comprising:
initializing, by data processing hardware, a pseudo-random number generator (PRNG) having a state of 2048 bits comprising inner bits and outer bits, the inner bits comprising the first 128 bits of the 2048 bits and the outer bits comprising the remaining bits of the 2048 bits;
permuting, by the data processing hardware, the state of the PRNG by:
retrieving Advanced Encryption Standard (AES) round keys from a key source; and
for a threshold number of times:
executing a round function using the AES round keys, the round function comprising XOR'ing odd-numbered branches of a Feistel network having 16 branches of 128 bits with a function of corresponding even-numbered neighbor branches of the Feistel network; and
shuffling each branch of 128 bits into a prescribed order; and
executing, by the data processing hardware, an XOR of the inner bits of the permuted state with the inner bits of a previous state.

### Claim 2 (depends on 1)

The method of claim 1, wherein initializing the PRNG comprises:
setting the state of the PRNG to zero; and
setting the outer bits to arbitrary seed values.

### Claim 3 (depends on 1)

The method of claim 1, wherein initializing the PRNG comprises setting the state of the PRNG to a previous state.

### Claim 4 (depends on 1)

The method of claim 1, wherein the threshold number of times comprises at least 17 times.

### Claim 5 (depends on 1)

The method claim 1, wherein the round function comprises at least two rounds of AES.

### Claim 6 (depends on 1)

The method of claim 1, wherein each of the at least two rounds of AES uses a corresponding AES round key that is different than the AES round keys of the other rounds of AES.

### Claim 7 (depends on 1)

The method of claim 1, wherein XOR'ing the odd-numbered branches of the Feistel network with the function of corresponding even-numbered neighbor branches of the Feistel network results in random bits, the outer bits comprising the resulting random bits.

### Claim 8 (depends on 1)

The method of claim 1, wherein shuffling each branch of 128 bits into the prescribed order achieves full sub-branch diffusion after executing the round function and shuffling each branch eight times.

### Claim 9 (depends on 1)

The method of claim 1, wherein the prescribed order comprises {7, 2, 13, 4, 11, 8, 3, 6, 15, 0, 9, 10, 1, 14, 5, 12}.

### Claim 10 (depends on 1)

The method of claim 1, further comprising preventing access to the inner bits and allowing access to the outer bits.

### Claim 11

A system comprising:
data processing hardware; and
memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:
initializing a pseudo-random number generator (PRNG) having a state of 2048 bits comprising inner bits and outer bits, the inner bits comprising the first 128 bits of the 2048 bits and the outer bits comprising the remaining bits of the 2048 bits;
permuting the state of the PRNG by:
retrieving Advanced Encryption Standard (AES) round keys from a key source; and
for a threshold number of times:
executing a round function using the AES round keys, the round function comprising XOR'ing odd-numbered branches of a Feistel network having 16 branches of 128 bits with a function of corresponding even-numbered neighbor branches of the Feistel network; and
shuffling each branch of 128 bits into a prescribed order; and
executing an XOR of the inner bits of the permuted state with the inner bits of a previous state.

### Claim 12 (depends on 11)

The system of claim 11, wherein initializing the PRNG comprises:
setting the state of the PRNG to zero; and
setting the outer bits to arbitrary seed values.

### Claim 13 (depends on 11)

The system of claim 11, wherein initializing the PRNG comprises setting the state of the PRNG to a previous state.

### Claim 14 (depends on 11)

The system of claim 11, wherein the threshold number of times comprises at least 17 times.

### Claim 15 (depends on 11)

The system of claim 11, wherein the round function comprises at least two rounds of AES.

### Claim 16 (depends on 11)

The system of claim 11, wherein each of the at least two rounds of AES uses a corresponding AES round key that is different than the AES round keys of the other rounds of AES.

### Claim 17 (depends on 11)

The system of claim 11, wherein XOR'ing the odd-numbered branches of the Feistel network with the function of corresponding even-numbered neighbor branches of the Feistel network results in random bits, the outer bits comprising the resulting random bits.

### Claim 18 (depends on 11)

The system of claim 11, wherein shuffling each branch of 128 bits into the prescribed order achieves full sub-branch diffusion after executing the round function and shuffling each branch eight times.

### Claim 19 (depends on 11)

The system of claim 11, wherein the prescribed order comprises {7, 2, 13, 4, 11, 8, 3, 6, 15, 0, 9, 10, 1, 14, 5, 12}.

### Claim 20 (depends on 11)

The system of claim 11, wherein the operations further comprise preventing access to the inner bits and allowing access to the outer bits.