Browse Prior Art Database

Random Initialization Circuit For Feedback Shift Register

IP.com Disclosure Number: IPCOM000111667D
Original Publication Date: 1994-Mar-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 139K

Publishing Venue

IBM

Related People

Butter, AS: AUTHOR [+5]

Abstract

Disclosed is a method for generating a "strong" random number seed which is used to initialize a pseudo-random feedback shift register.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Random Initialization Circuit For Feedback Shift Register

      Disclosed is a method for generating a "strong" random number
seed which is used to initialize a pseudo-random feedback shift
register.

      Many computer applications rely on random numbers as input
parameters.  For example, random numbers can be used as DES [1]

Private keys and as the basis for generating RSA [2] Public/Private
key pairs in cryptographic applications.

      Assuring randomness is a difficult task.  This is especially
true for generating a random seed following the hardware
initialization procedure.  One method which is currently employed by
the Key Storage Unit of the ES/3090* and ES/9000* Cryptographic
Coprocessor feature is to use the power-on state as the base seed for
a random number register.  Although this procedure assures a "strong"
random seed following the initial power-on sequence, its strength
following subsequent power-on sequences tends to diminish (i.e., the
random seed tends to be the same after each power-on sequence).  This
disclosure describes a random number initialization procedure for a
pseudo-random feedback shift register which exhibits a high degree of
randomness following power-on/reset sequences.

      A block diagram for the proposed pseudo-random number generator
is shown in Fig. 1.  Data is input to the 64-bit Feedback Shift
Register from either the FSR Next State Logic or the FSR
Initialization Logic.  The selection of which source is determined by
the state of the Reset Control signal.  Whenever this control is
inactive, the Feedback Shift Register is loaded with the FSR Next
State Logic output value.  This logic is responsible for generating
the next Feedback Shift Register value in a pseudo-random sequence
which approximates a digital noise source.  Although the
pseudo-random sequence is periodic, the amount of time required to
detect repetition in a 64-bit output is prohibitive.  For example,
the repetition period for a 64-bit Feedback Shift Register which is
comprised of the concatenation of a 33-bit stage and 31-bit stage is
approximately 11,669 years when a 20 ns System Clock is used.  Thus,
all observable Feedback Shift Register output sequences will appear
to be random.  Additional information regarding pseudo-random bit
sequences using Feedback Shift Registers can be found in [3].

      In order to prevent an outside observer from detecting pseudo-
random sequence repetition following hardware initialization, it is
highly desirable to...