Hardware assisted fast pseudorandom number generation

Patent metadata

Field	Value
Publication number	US-10142103-B2
Application number	US-201514961307-A
Country	US
Kind code	B2
Filing date	Dec 7, 2015
Priority date	Dec 7, 2015
Publication date	Nov 27, 2018
Grant date	Nov 27, 2018

Abstract

A system and method for generating pseudorandom numbers by initializing a counter value for a call-counter, sending a bit-wise form of the counter value from the counter to a mixing function, and mixing the counter value to generate the pseudorandom number. The mixing function may be a XOR tree, substitution-permutation, or double-mix Feistel. The pseudorandom number generator can operate by mixing the bits of the call-counter, repeatedly mixing its own output, or a combination thereof. The counter is incremented by a predetermined value. In order to provide backward secrecy, the pseudorandom number is processed by a one-way function or is hashed with a cryptographic hash function, and the result thereof is used as an input value for a subsequent cycle of the mixing function. Also, several mixing functions can be operated in parallel with their output XORed.

First claim

What is claimed is:

1. A method for generating pseudorandom numbers comprising the steps of:
initializing a counter value for a counter (block 402 );
sending a bit-wise form of the counter value from the counter to a mixing function (block 408 );
mixing the bit-wise form of the counter value to generate a pseudorandom number (block 410 );
filling an input register by repeating the counter value in its entirety as many times as possible without exceeding capacity of the input register (block 404 ); and
filling any remaining, unfilled bits of the input register with individual bits of the counter value until the input register is full (block 406 ).

2. The method of claim 1 further comprising the step of incrementing the counter value by a predetermined value (block 424 ).

3. The method of claim 1 further comprising the step of using the pseudorandom number as an input value for a subsequent cycle of the mixing step (block 410 ).

4. The method of claim 1 wherein the mixing step (block 410 ) maps a first segment of the bit-wise form of the counter value input with a first segment of the bit-wise form of the counter value output by concatenating the segments.

5. The method of claim 4 wherein the mixing step (block 410 ) is invertible.

6. The method of claim 4 wherein the mixing step (block 410 ) is non-linear.

7. The method of claim 4 wherein the mixing step (block 410 ) comprises a function selected from the group consisting of an exclusive-OR “XOR” tree mixing function, a substitution-permutation mixing function, and a double-mix Feistel mixing function.

8. The method of claim 1 wherein the mixing step (block 410 ) further comprises steps of mixing the counter value at least twice in parallel mixing functions (block 412 ) and exclusive-XORing (“XORing”) outputs from the parallel mixing functions (block 414 ).

9. The method of claim 1 further comprising the steps of:
processing the pseudorandom number by a one-way function or hashing the pseudorandom number with a cryptographic hash function (block 416 ); and
using a result of the one-way processing of the pseudorandom number or hashing of the pseudorandom number as an input value for a subsequent cycle of the mixing function (block 418 ).

10. The method of claim 1 further comprising the step of using the pseudorandom number to store encrypted data in a memory (block 422 ).

11. A system for generating pseudorandom numbers comprising:
a counter that is initialized with a counter value (block 402 );
a mixing function that mixes a bit-wise form of the counter value to generate a pseudorandom number (block 410 );
an input register arranged to be filled by repeating the counter value in its entirety as many times as possible without exceeding capacity of the input register (block 404 ) and by filling any unfilled bits of the input register with individual bits of the counter value until the input register is full (block 406 ).

12. The system of claim 11 wherein the counter value is incremented by a predetermined value (block 424 ).

13. The system of claim 11 wherein the pseudorandom number serves as an input value for a subsequent cycle of the mixing function (block 420 ).

14. The system of claim 11 further comprising a storage device having a memory that stores encrypted data based on the pseudorandom number (block 422 ), the encrypted data being selected from the group consisting of encryption keys, tweak values, nonces, and initial values.

15. The system of claim 11 wherein the mixing function (block 410 ) maps a first segment of the bit-wise form of the counter value input with a first segment of the bit-wise form of the counter value output by concatenating the segments.

16. The system of claim 11 wherein the mixing function (block 410 ) is invertible.

17. The system of claim 11 wherein the mixing function (block 410 ) is non-linear.

18. The system of claim 11 wherein the mixing function (block 410 ) is selected from the group consisting of a XOR tree mixing function, substitution-permutation mixing function, and double-mix Feistel mixing function.

19. The system of claim 11 wherein the mixing function (block 410 ) is performed by at least two mixing functions operating in parallel (block 412 ) and the outputs from the at least two mixing functions are XORed (block 414 ).

20. The system of claim 11 wherein:
the pseudorandom number is processed by a one-way function or hashed with a cryptographic hash function (block 416 ); and
a result of the one-way processing of the pseudorandom number or hashing of the pseudorandom number is used as an input value for a subsequent cycle of the mixing function (block 418 ).

Assignees

• Boeing Co

Inventors

• Hars Laszlo

Classifications

• G06F7/582 Primary

  Pseudo-random number generators · CPC title

• H04L9/0869 Primary

  involving random numbers or seeds · CPC title

• H04L9/0662

  with particular pseudorandom sequence generator · CPC title

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title

• H04L9/0668

  producing a non-linear pseudorandom sequence · CPC title