next up previous contents
Next: Recommended random number sources Up: Generation of random numbers Previous: Introduction

Fundamental information theory

The probability of an adversary succeeding at guessing your random numbers must be made acceptably low, depending on the particular application. The size of the space the adversary must search is related to the amount of key ``information'' present in the information theoretic sense [11].

This depends on the number of different secret values possible and the probability of each value as follows:

equation174

where i varies from 1 to the number of possible secret values and tex2html_wrap1251 is the probability of the value numbered tex2html_wrap1252 . (Since tex2html_wrap1251 is less than one, the log will be negative so each term in the sum will be non-negative.) n is the number of bits of information.

If there are tex2html_wrap1254 different values of equal probability, then n bits of information are present and an adversary would, on the average, have to try half of the values, or tex2html_wrap1255 , before guessing the secret quantity. If the probability of different values is unequal, then there is less information present and fewer guesses will, on average, be required by an adversary. In particular, any values that the adversary can know are impossible, or are of low probability, can be initially ignored by an adversary, who will search through the more probable values first.

For example, consider a cryptographic system that uses 56 bit keys. If these 56 bit keys are derived by using a fixed pseudo-random number generator that is seeded with an 8 bit seed, then an adversary needs to search through only 256 keys (by running the pseudo-random number generator with every possible seed), not the tex2html_wrap1256 keys that may at first appear to be the case. Only 8 bits of ``information'' are in these 56 bit keys.



Asgaut Eng
Wed Apr 10 14:07:30 MET DST 1996