Browse Prior Art Database

MULTI-CLOCK RANDOM NUMBER GENERATOR

IP.com Disclosure Number: IPCOM000009522D
Original Publication Date: 1999-Sep-01
Included in the Prior Art Database: 2002-Aug-29
Document File: 3 page(s) / 163K

Publishing Venue

Motorola

Related People

Jeff McTaggart: AUTHOR [+2]

Abstract

For many products that involve secure commu- nications, there is the need for a highly non-deter- ministic random number generator. Most hardware random number generators (RNGs) can be catego- rized as either analog or digital devices. Most of the analog designs require a noise source, essentially a piece of circuitry that is designed to have poor per- formance. However, when designed well, the data output from them is truly non-deterministic. Most of the digital designs incorporate circuits that do not create actual random data, but pseudo random data, meaning that future output is deterministic based on previous output. This deterministic aspect of some digital random number generators is undesirable in many high security systems.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 40% of the total text.

Page 1 of 3

Technical MOTOROLA @ Developments

MULTI-CLOCK RANDOM NUMBER GENERATOR

by Jeff McTaggart and Brook Burson

BACKGROUND

  For many products that involve secure commu- nications, there is the need for a highly non-deter- ministic random number generator. Most hardware random number generators (RNGs) can be catego- rized as either analog or digital devices. Most of the analog designs require a noise source, essentially a piece of circuitry that is designed to have poor per- formance. However, when designed well, the data output from them is truly non-deterministic. Most of the digital designs incorporate circuits that do not create actual random data, but pseudo random data, meaning that future output is deterministic based on previous output. This deterministic aspect of some digital random number generators is undesirable in many high security systems.

  With regards to implementation cost and com- plexity, digital designs usually win out over analog designs. Analog RNGs are much more complex, more costly to lay out, and tougher to get working well when a high level of non-deterministic behav- ior is needed. However, digital RNGs are typically easy to implement in a reliable fashion in a relative- ly small amount of space. Other than their deter- ministic behavior, digital RNGs have most of the advantages.

  Various methods have been implemented to reduce the deterministic behavior of digital RNGs, while still retaining the inherent advantages. This

article looks at a method of implementing a non- deterministic digital RNG, while maintaining the advantages that digital RNGs have over their analog counterparts.

INVENTION

  The Multi-Clock Random Number Generator (MCRNG) is a digital random number generator that provides a source of numbers that is non-deter- ministic, does not add noise to adjacent circuitry, can not be compromised from an outside threat, and can be implemented at low cost in a small amount of space. Our implementation of the MCRNG was designed with most of the circuitry inside a Field Programmable Gate Array (FPGA), but could be implemented in an ASIC or other programmable device.

  The basic core of the MCRNG invention is the use of multiple linear feedback shift registers (LFSR) which are different sized, maximal length, and running on unassociated clocks. The least sig-. niticant bits of output from the multiple LFSRs are XORed together and sampled with another unasso- ciated clock, which is running at a speed at least 10 times slower than the slowest LFSR clock. The MCRNG bit stream is ensured to be non-repeatable on successive power ups via the use of initialization registers which outside software or hardware can use to initialize some of the bits within the MCRNG LFSRs to a different starting point at each power up.

0 Moram,a,lnc. 1999 172 September 1999

[This page contains 15 pictures or other non-text objects]

Page 2 of 3

Developments Technical 0 M MO7OROLA

8 Bit Registers

El m z =+

LSB #1

        5 N Stage LFSR
0 + Random X M...