7.2.3. DSS Pseudo-random Number Generation

Appendix 3 of the NIST Digital Signature Standard [DSS] provides a method of producing a sequence of pseudo-random 160 bit quantities for use as private keys or the like. This has been modified by Change Notice 1 [DSS_CN1] to produce the following algorithm for generating general-purpose pseudo-random numbers:

t = 0x 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0

XKEY  = initial seed
    0

For j = 0 to ...

    XVAL = ( XKEY  + optional user input ) (Mod 2^512)
                 j

    X  = G( t, XVAL )
     j

    XKEY   = ( 1 + XKEY  + X  ) (Mod 2^512)
        j+1            j    j

The quantities X thus produced are the pseudo-random sequence of 160-bit values. Two functions can be used for "G" above. Each produces a 160-bit value and takes two arguments, a 160-bit value and a 512 bit value.

The first is based on SHA-1 and works by setting the 5 linking variables, denoted H with subscripts in the SHA-1 specification, to the first argument divided into fifths. Then steps (a) through (e) of section 7 of the NIST SHA-1 specification are run over the second argument as if it were a 512-bit data block. The values of the linking variable after those steps are then concatenated to produce the output of G [SHA*].

As an alternative method, NIST also defined an alternate G function based on multiple applications of the DES encryption function [DSS].