Re: Случайные числа

From

Valentin Davydov ()

To

Artur Mogozov

Date

2002-12-12T16:55:28Z

Area

RU.ALGORITHMS

From: Valentin Davydov <val@sqdp.trc-net.co.jp>

>   From: Artur Mogozov <Artur.Mogozov@p6.f7.n5002.z2.fidonet.org>
>   Date: Wed, 11 Dec 2002 16:46:46 +0300
>
>Всем известно, что в системах программирования генераторы случайных чисел не
>совершенны (генерится на основе системного времени). Есть ли алгоритм генерации
>*очень* случайного числа, а не псевдо-случайного?

man 4 random

   Theory of operation

     Computers are very predictable devices.  Hence it is extremely hard to
     produce truly random numbers on a computer -- as opposed to pseudo-random
     numbers, which can easily generated by using a algorithm.  Unfortunately,
     it is very easy for attackers to guess the sequence of pseudo-random num-
     ber generators, and for some applications this is not acceptable.  So in-
     stead, we must try to gather "environmental noise" from the computer's
     environment, which must be hard for outside attackers to observe, and use
     that to generate random numbers.  In a Unix environment, this is best
     done from inside the kernel.

     Sources of randomness from the environment include inter-keyboard tim-
     ings, inter-interrupt timings from some interrupts, and other events
     which are both (a) non-deterministic and (b) hard for an outside observer
     to measure.  Randomness from these sources are added to an "entropy
     pool", which is periodically mixed using the MD5 compression function in
     CBC mode.  As random bytes are mixed into the entropy pool, the routines
     keep an estimate of how many bits of randomness have been stored into the
     random number generator's internal state.

     When random bytes are desired, they are obtained by taking the MD5 hash
     of a counter plus the contents of the "entropy pool".  The reason for the
     MD5 hash is so that we can avoid exposing the internal state of random
     number generator.  Although the MD5 hash does protect the pool, each ran-
     dom byte which is generated from the pool reveals some information which
     was derived from the internal state, and thus increases the amount of in-
     formation an outside attacker has available to try to make some guesses
     about the random number generator's internal state.  For this reason, the
     routine decreases its internal estimate of how many bits of "true random-
     ness" are contained in the entropy pool as it outputs random numbers.

     If this estimate goes to zero, the routine can still generate random num-
     bers; however it may now be possible for an attacker to analyze the out-
     put of the random number generator, and the MD5 algorithm, and thus have
     some success in guessing the output of the routine.  Phil Karn (who de-
     vised this mechanism of using MD5 plus a counter to extract random num-
     bers from an entropy pool) calls this "practical randomness", since in
     the worse case this is equivalent to hashing MD5 with a counter and an
     undisclosed secret.  If MD5 is a strong cryptographic hash, this should
     be fairly resistant to attack.

Вал. Дав.
--- ifmail v.2.15dev5
 * Origin: St. Petersburg State University (2:5020/400)