Enhanced ANSI X9.17 and FIPS 186 pseudorandom number generators with forward security

• US 20030086565A1
• Filed: 10/08/2002
• Published: 05/08/2003
• Est. Priority Date: 11/06/2001
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: DOCOMO Communications Laboratories USA, Inc.
• Inventors: Desai, Anand, Yin, Yiqun, Hevia, Alejandro
• Granted Patent: US 7,227,951 B2
• Time in Patent Office: Days
• US Class Current: 380/45
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator

Abstract

Disclosed herein are apparatuses and methods for generating pseudorandom numbers by making the existing ANSI and FIPS PRNGs forward secure and eliminating the need for re-keying them. A forward secure ANSI PRNG is created which includes an enhanced block cipher that is non-invertible even if the key becomes known and a function of the block cipher used in the existing ANSI PRNG. Additionally, the forward secure ANSI PRNG includes an enhanced next state that allows previous states to remain secret even when the key and the current state become known. A forward secure FIPS PRNG is created which includes a computation of an enhanced next state that is noninvertible.

Claims

1. A forward secure ANSI X9.17 pseudorandom number generator, comprising:

an iteration integer i, wherein i is defined in accordance with a relationship i 0;

a processor;

a key K;

a current state As<sub>i−

1</sub> for each iteration integer i calculated by the processor;

an enhanced keyed block cipher F′

_K, wherein the enhanced block cipher F′

_K does not require re-keying and is non-invertible even if the key K is known;

an enhanced next state As′

_i for each iteration integer i, wherein the enhanced next state As′

_i is calculated by the processor such that previous states remain secret even when the key K and the enhanced next state As′

_i become known; and

an enhanced pseudorandom number generator output Ay′

_i for each iteration integer i, wherein the enhanced pseudorandom number generator output Ay′

_i is a function of at least one auxiliary input t_i.

2. A forward secure ANSI X9.17 pseudorandom number generator, as claimed in claim 1, further comprising an input device, wherein the enhanced next state As′

_i is defined in accordance with a relationship;

As′

_i=F′

_K (As′

<sub>i−

1</sub>) and is calculated by the processor, and wherein the at least one auxiliary input t_i for each iteration integer i is received by the processor via the input device and the enhanced pseudorandom number generator output Ay′

_i is defined in accordance with a relationship Ay′

_i=F′

_K(F′

_K(t_i)⊕

(As′

<sub>i−

1</sub>) and is calculated by the processor.

3. A forward secure ANSI X9.17 pseudorandom number generator, as claimed in claim 1, wherein the enhanced keyed block cipher F′

_K is defined, for all of at least one input x, in accordance with a relationship;

F′

_K(x)=F_K(x)⊕

x.

4. A forward secure ANSI X9.17 pseudorandom number generator, comprising:

a seed generating function _ANSI;

a processor, wherein the processor, using the seed generating function _ANSI, returns a key K and an initial state As₀;

an input device;

an iteration integer i, wherein i is defined in accordance with a relationship;

i 0;

at least one auxiliary input ti for each iteration integer t_i wherein the at least one auxiliary input t_i is received by the processor via the input device;

a current state As′

<sub>i−

1</sub> for each iteration integer i, wherein the current state As′

<sub>i−

1</sub> is calculated by the processor;

a seeded block cipher F_K, wherein F_K is keyed by the key K;

an enhanced keyed block cipher F′

_K, wherein the enhanced seeded block cipher F′

_K is keyed by the key K, does not require re-keying, is non-invertible even if the key K is known, and for all of at least one input x, is defined in accordance with a relationship F′

_K(x)=F_K(x)⊕

x;

an enhanced next state As′

_i for each iteration integer i, wherein As′

_i is calculated by the processor and defined in accordance with a relationship As′

_i=F′

_K(As40 <sub>i−

1</sub>)=F_K(As′

<sub>i−

1</sub>)⊕

As′

<sub>i−

1</sub>; and

an enhanced pseudorandom generator output Ay′

_i for each iteration integer i, wherein Ay′

_i is calculated by the processor and defined in accordance with a relationship Ay′

_i=F′

_K(F′

_K(t_i)⊕

As′

<sub>i−

1</sub>.

5. A computer readable storage medium storing computer readable program code implementing a forward secure ANSI X9.17 pseudorandom number generator, the computer readable program code comprising:

a first computer code implementing an enhanced keyed block cipher F′

_K, wherein the enhanced block cipher F′

_K does not require re-keying and is noninvertible even if the key K is known;

data encoding an iteration integer i, wherein i is defined in accordance with a relationship;

i 0;

a second computer code implementing a current state As<sub>i−

1</sub> for each iteration integer i;

a second computer code implementing an enhanced next state As′

_i for each iteration integer i, wherein the enhanced next state As′

_i is calculated by the processor such that previous states remain secret even when the key K and the enhanced next state As′

_i become known; and

a third computer code implementing an enhanced pseudorandom number generator output Ay′

_i for each iteration integer i, wherein the enhanced pseudorandom number generator output Ay′

_i is a function of at least one auxiliary input t_i.

6. A forward secure FIPS 186 pseudorandom number generator, comprising:

a processor;

a seeded hash function H_K;

an iteration integer i, wherein i is defined in accordance with a relationship;

i 0;

an enhanced next state Fs′

_i for each iteration integer i, wherein the enhanced next state Fs′

_i is non-invertible; and

an enhanced pseudorandom number generator output Fy′

_i for each iteration integer i, wherein the enhanced pseudorandom number generator output Fy′

_i is calculated by the processor and is a function of at least one auxiliary input t_i.

7. A forward secure FIPS 186 pseudorandom number generator, as claimed in claim 6, further comprising:

a pseudorandom number generator block length n wherein n is defined in accordance with a relationship;

n=|Fy′

_i|; and

an input device, wherein the at least one auxiliary input t_i is received by the processor via the input device, Fy′

_i is defined in accordance with a relationship Fy′

_i=H_K((Fs′

<sub>i−

1</sub>+t_i) mod 2ⁿ) and Fs′

_i is defined in accordance with a relationship;

Fs′

_i=(H_K((Fs′

<sub>i−

1</sub>+Fy′

_i+1+t_i) mod 2ⁿ)+Fs′

<sub>i−

1</sub>+Fy′

_i+2) mod 2ⁿ) and is calculated by the processor.

8. A forward secure FIPS 186 pseudorandom number generator, comprising:

a seed generating function _FIPS;

a processor, wherein the processor, using the seed generating function _FIPS, returns at least one key K and an initial state Fs₀;

a keyed hash function H_K;

an iteration integer i, wherein i is defined in accordance with a relationship i 0;

an input device;

at least one auxiliary input t_i for each iteration integer i, wherein the at least one auxiliary input t_i is received by the processor via the input device;

an enhanced current state Fs′

<sub>i−

1</sub> for each iteration integer i;

an enhanced pseudorandom generator output Fy′

_i for each iteration integer i;

a pseudorandom number generator block length n wherein n is defined in accordance with a relationship n=|Fy′

_i|, and wherein Fy′

_i is defined in accordance with the relationship Fy′

_i=H_K((Fs′

<sub>i−

1</sub>+t_i) mod 2ⁿ); and

an enhanced next state Fs′

_i for each iteration integer i, wherein the enhanced next state Fs′

_i is calculated by the processor and defined in accordance with a relationship;

Fs′

_i=(H_K((Fs′

<sub>i−

1</sub>+Fy′

_i+1+t_i) mod 2ⁿ)+Fs′

<sub>i−

1</sub>+Fy′

_i+2) mod 2ⁿ).

9. A computer readable storage medium storing computer readable program code implementing a forward secure FIPS 186 pseudorandom number generator, the computer readable program code comprising:

a first computer code implementing a keyed hash function H_K;

data encoding an iteration integer i, wherein i is defined in accordance with a relationship;

i 0;

a second computer code implementing an enhanced next state Fs′

_i for each iteration integer i, wherein the enhanced current state Fs′

_i is non-invertible; and

a third computer code implementing an enhanced pseudorandom number generator output Fy40 _i for each iteration integer i, wherein the enhanced pseudorandom number generator output Fy′

_i is a function of at least one auxiliary input t_i.

10. A method for producing forward secure pseudorandom numbers by altering an ANSI X9.17 pseudorandom number generator, comprising:

defining an iteration integer i, wherein i is defined in accordance with a relationship i 0;

replacing a keyed block cipher F_K with an enhanced keyed block cipher F′

_K, wherein the enhanced keyed block cipher F′

_K is non-invertible even if the key K is known;

replacing a current state with an enhanced current state As′

<sub>i−

1</sub>; and

replacing a next state As_i with an enhanced next state As′

_i, wherein As′

_i is defined for each iteration integer i, as a function of the enhanced current state As′

<sub>i−

1</sub>, and allows previous states to remain secret even if the key K and the enhanced next state As′

_i become known.

11. A method for producing pseudorandom numbers, as claimed in claim 10, further comprising defining the enhanced keyed block cipher F′

_K as a function of a block cipher F_K.

12. A method for producing pseudorandom numbers, as claimed in claim 11, further comprising:

defining F′

_K as a function of at least one input x in accordance with a relationship F′

_K(x)=F_K(x)⊕

x for all of the at least one inputs x.

13. A method for producing pseudorandom numbers, as claimed in claim 10, further comprising defining the enhanced next state As′

_i in accordance with a relationship;

As′

_i=F′

_K(As′

<sub>i−

1</sub>).

14. A method for producing pseudorandom numbers, as claimed in claim 11, further comprising:

defining an iteration integer, wherein the iteration integer is defined in accordance with a relationship i 1;

enabling at least one auxiliary input t_i for each iteration integer i; and

defining an enhanced pseudorandom generator output Ay′

_i for each iteration integer i, and wherein Ay′

_i is defined in accordance with a relationship Ay′

_i=F′

_K (F′

_K(t_i)⊕

As′

<sub>i−

1</sub>.

15. A method for producing pseudorandom numbers by altering an ANSI X9.17 pseudorandom number generator, comprising:

defining an iteration integer, wherein the iteration integer is defined in accordance with a relationship i 1;

enabling at least one auxiliary input ti for each iteration integer i;

defining an enhanced keyed block cipher F′

_K seeded with a key K, for all of at least one input x in accordance with a relationship F′

_K(x)=F_K(x)⊕

x;

replacing a keyed block cipher F_K with the enhanced keyed block cipher F′

_K, wherein the enhanced keyed block cipher F′

_K is a non-invertible function even if the key K is known;

replacing a current state As<sub>i−

1</sub> with an enhanced current state As′

<sub>i−

1</sub>;

replacing a next state As_i with an enhanced next state As′

_i, wherein As′

_i is defined as a function of the keyed block cipher F_K and the current state As′

<sub>i−

1</sub> for each iteration integer i in accordance with a relationship As′

_i=F′

_K(As′

<sub>i−

1</sub>)=F_K(As′

<sub>i−

1</sub>)⊕

As′

<sub>i−

1</sub>; and

defining an enhanced pseudorandom generator output Ay_i′

for each iteration integer i, wherein Ay′

_i is defined in accordance with a relationship Ay′

_i=F′

_K(F′

_K (t_i)⊕

As′

<sub>i−

1</sub>.

16. A method for producing pseudorandom numbers, comprising altering a FIPS 186 pseudorandom number generator, wherein altering a FIPS 186 pseudorandom number generator comprises replacing a next state Fs_i with an enhanced next state Fs′

_i, wherein the computation of the enhanced next state Fs′

_i is non-invertible.

17. A method for producing pseudorandom numbers, as claimed in claim 16, wherein replacing a next state Fs_i with an enhanced next state Fs′

_i further comprises defining the enhanced next state Fs′

_i as a function of a keyed hash function H_K and an enhanced current state Fs′

<sub>i−

1</sub>.

18. A method for producing forward secure pseudorandom numbers, as claimed in claim 17, further comprising defining:

an iteration integer i, wherein i is defined in accordance with a relationship i 0;

an auxiliary input t_i for each iteration integer i;

an enhanced pseudorandom number generator output Fy′

_i for each iteration integer i;

a pseudorandom number generator block length n wherein n=|Fy′

_i;

an enhanced current state Fs′

<sub>i−

1</sub>;

wherein defining the enhanced next state Fs further comprises defining the enhanced next state Fs′

_i for each iteration integer i, wherein Fs′

_i is defined in accordance with a relationship Fs′

_i=(H_K((Fs′

<sub>i−

1</sub>+Fy′

_i+1+t_i) mod 2ⁿ)+Fs′

<sub>i−

1</sub>+Fy′

_i+2) mod 2ⁿ); and

wherein defining the enhanced pseudorandom generator output Fy′

_i further comprises defining Fy′

_i in accordance with a relationship Fy′

_i=H_K((Fs′

<sub>i−

1</sub>+t_i) mod 2ⁿ).