Gerador de números aleatórios do Linux

[Rogerio Brito <rbrito@iname.com>]

	Olá a todos os colegas.

	Como uma forma de inaugurar a lista com algumas informações
	motivadas hoje pela discussão em que o Yoshi falava sobre
	algoritmos aleatórios, estive pensando em mandar o seguinte
	texto, contido nos comentários do arquivo
	linux/drivers/char/random.c da versão 2.2.11 dos fontes do
	kernel do Linux (mas eu acredito que este arquivo fonte em
	particular não tenha mudado há muito tempo, pelo que eu tenho
	acompanhado do desenvolvimento do Linux).

	O texto trata brevemente sobre a implementação de uma maneira
	um pouco mais segura de realizar a geração de números
	(pseudo-)aleatórios, sem ser por meio de um gerador de
	congruência linear (acho que é esse o nome), que, acredito,
	seja um padrão de facto para a geração de números aleatórios
	nos diversos sistemas operacionais/bibliotecas de linguagens
	em uso hoje em dia.

	Um pouco de discussão sobre o assunto é que é impossível
	(tanto quanto eu sei) gerar números propriamente
	pseudo-aleatórios em uma máquina determinística como um
	computador. Entretanto, com um pouco de ajuda externa
	(leia-se: usuário e eventos relacionados a periféricos como,
	por exemplo, entrada e saída) acho que isso torna-se mais
	fácil (ou, pelo menos, as seqüências de números geradas
	tornam-se menos previsíveis).

	O texto está abaixo da minha assinatura.

	Caso alguém tenha algum comentário extra ou sugestão de
	leitura, eu agradeceria.


	Abraços e muito obrigado, Roger...

P.S.: Desculpem-me se a minha mensagem não faz muito sentido. Estou
bastante cansado agora e só estou mandando esta mensagem porque eu sei
que esqueceria se eu não a mandasse agora.

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  Rogerio Brito - rbrito@iname.com - http://www.ime.usp.br/~rbrito/
     Nectar homepage: http://www.linux.ime.usp.br/~rbrito/opeth/
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

(...)
/*
 * (now, with legal B.S. out of the way.....) 
 * 
 * This routine gathers environmental noise from device drivers, etc.,
 * and returns good random numbers, suitable for cryptographic use.
 * Besides the obvious cryptographic uses, these numbers are also good
 * for seeding TCP sequence numbers, and other places where it is
 * desirable to have numbers which are not only random, but hard to
 * predict by an attacker.
 *
 * 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 number generators, and for some
 * applications this is not acceptable.  So instead, 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
 * timings, 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 mixed using a CRC-like function.
 * This is not cryptographically strong, but it is adequate assuming
 * the randomness is not chosen maliciously, and it is fast enough that
 * the overhead of doing it on every interrupt is very reasonable.
 * 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 SHA
 * hash of the contents of the "entropy pool".  The SHA hash avoids
 * exposing the internal state of the entropy pool.  It is believed to
 * be computationally infeasible to derive any useful information
 * about the input of SHA from its output.  Even if it is possible to
 * analyze SHA in some clever way, as long as the amount of data
 * returned from the generator is less than the inherent entropy in
 * the pool, the output data is totally unpredictable.  For this
 * reason, the routine decreases its internal estimate of how many
 * bits of "true randomness" are contained in the entropy pool as it
 * outputs random numbers.
 * 
 * If this estimate goes to zero, the routine can still generate
 * random numbers; however, an attacker may (at least in theory) be
 * able to infer the future output of the generator from prior
 * outputs.  This requires successful cryptanalysis of SHA, which is
 * not believed to be feasible, but there is a remote possibility.
 * Nonetheless, these numbers should be useful for the vast majority
 * of purposes.
 * 
 * Exported interfaces ---- output
 * ===============================
 * 
 * There are three exported interfaces; the first is one designed to
 * be used from within the kernel:
 *
 * 	void get_random_bytes(void *buf, int nbytes);
 *
 * This interface will return the requested number of random bytes,
 * and place it in the requested buffer.
 * 
 * The two other interfaces are two character devices /dev/random and
 * /dev/urandom.  /dev/random is suitable for use when very high
 * quality randomness is desired (for example, for key generation or
 * one-time pads), as it will only return a maximum of the number of
 * bits of randomness (as estimated by the random number generator)
 * contained in the entropy pool.
 * 
 * The /dev/urandom device does not have this limit, and will return
 * as many bytes as are requested.  As more and more random bytes are
 * requested without giving time for the entropy pool to recharge,
 * this will result in random numbers that are merely cryptographically
 * strong.  For many applications, however, this is acceptable.
 *

(...)

 */