|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valentin Davydov 2:5020/400 12 Dec 2002 17:55:28
To : Artur Mogozov
Subject : Re: Случайные числа
--------------------------------------------------------------------------------
> 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
