Enhanced ANSI X9.17 pseudorandom number generators with forward security

• US 7,227,951 B2
• Filed: 10/08/2002
• Issued: 06/05/2007
• Est. Priority Date: 11/06/2001
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Desai, Anand, Yin, Yiqun, Hevia, Alejandro
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): Szymanski; Thomas M.
• Application Number:
  US10/267,463
• Publication Number:
  US 20030086565A1
• Time in Patent Office: 1,701 Days
• Field of Search: 708/254, 708/255, 380/259, 380/268, 380/262
• US Class Current: 380/46
• 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 a processor which executes instructions for implementing a state machine having:

an iteration integer i, which takes on integer values that satisfy i>

0;

a key K;

a current state As<sub>i−

1</sub> for each iteration integer i;

an enhanced keyed block cipher F′

_K, wherein the enhanced block cipher F′

_K is a function obtained by combining a block cipher F_K with its input value;

an enhanced next state As′

_i for each iteration integer I, given by As′

_i=F′

_K(As<sub>i−

1</sub>); 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, given by Ay′

_i=F′

_K(F′

_K(t_i) ⊕

As<sub>i−

1</sub>).

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

_K is given by;

F′

_K(x)=F_K(x)⊕

x, for an input value x.

3. A forward secure ANSI X9.17 pseudorandom number generator, comprising a processor which executes instructions for implementing a state machine comprising:

a seed generating function ANSI;

a function operating on the seed generating function ANSI, and which returns a key K and an initial state As₀;

an iteration integer i, which takes on integer values that satisfy i>

0;

an auxiliary input t_i for each iteration integer t_i;

a current state As′

<sub>i−

1</sub> for each iteration integer i;

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, given by F′

_K(x)F_K(x)⊕

x, where x is an input value;

an enhanced next state As′

_i for each iteration integer i, wherein As′

_i is given by As′

_i=F′

_K(As<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 is given by Ay′

_i=F′

_K (F_K(t_i)⊕

As<sub>i−

1</sub>).

4. 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 instructions for implementing a state machine having:

an enhanced keyed block cipher F′

_K, wherein the enhanced block cipher F′

_K is a function obtained by combining a block cipher F_K wit its input value;

data encoding an iteration integer i, which takes on integer values that satisfy i>

0;

a current state As<sub>i−

1</sub> for each iteration integer i;

an enhanced next state As′

_i for each iteration integer i, given by As′

_i=F′

_K(As<sub>i−

1</sub>); 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 an auxiliary input t_i, given by Ay′

_i=F′

_K(F_K(t_i)⊕

As<sub>i−

1</sub>.

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

defining an iteration integer i which takes on values satisfying 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 a function obtained by combining a block cipher F′

_K with its input value; and

using a current state As<sub>i−

1</sub>, calculating an enhanced next state As′

_i, given by As′

_i=F′

_K(As<sub>i−

1</sub>); and

defining an enhanced pseudorandom generator output Ay′

_i and an auxiliary input t_i for each iteration integer i, given by Ay′

_i=F′

_K(F_K(t_i)⊕

As<sub>i−

1</sub>).

6. A method for producing pseudorandom numbers as in claim 5, further comprising:

defining F′

_K as F′

_K(x)=F_K(x)⊕

x for an input value x.

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

defining an iteration integer, which takes integer values that satisfy i>

1;

enabling an auxiliary input t_i for each iteration integer i;

defining an enhanced keyed block cipher F′

_K seeded with a key K, for an input x, which satisfy 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 function obtained by combining F_K with its input value;

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 As′

_i=F′

_K (F_K(t_i)⊕

As<sub>i−

1</sub>).