Existe uma grande diferença entre segurança perfeita (ou confidencialidade perfeita) e segurança semântica. A primeira é mais de interesse teórico e, nesse contexto, não se pode "gerar" aleatoriedade - ou você tem números verdadeiramente aleatórios ou você não tem (e se você tem, você só pode usá-los uma única vez e em seguida tem que descartá-los). A segunda, de interesse prático, diz respeito apenas ao que se pode razoavelmente esperar de um processo computacional que opera em tempo polinomial. O conceito de entropia nesse caso é o mesmo, mas o uso da entropia é bem diferente - e nesse caso sim, pode-se conseguir bastante segurança a partir de uma quantidade pequena de entropia.
(Nota: substitua "segurança" por "imprevisibilidade", caso seu foco seja outro que não a criptografia - por exemplo, garantir a aleatoriedade durante uma simulação científica)
Na teoria
Uma boa maneira de ilustrar do que se trata a entropia é através de um exemplo. Considere a seguinte sequência de bits:
01001101010011010100110101001101010011010100110101001101010011010100110101001101
Eu usei 80 caracteres para descrevê-la, mas eu poderia "compactá-la" por exemplo da seguinte forma:
01001101 repetido 10 vezes
O que me toma somente 26 caracteres. Eu poderia continuar buscando formas mais sucintas de descrever essa sequência, até chegar num ponto em que não é possível comprimir mais, pois ela estaria na forma mais compacta possível e que ainda descreve unicamente essa mesma sequência (i.e. sem ambiguidade, uma forma que não pode igualmente descrever uma sequência diferente). Se essa forma usar, digamos, 10 caracteres, então eu posso dizer que ela possui 10 caracteres de entropia.
(você pode converter essa medida pra bits, se quiser: log23710 = 52 bits de entropia, assumindo que um "caractere" é uma letra, número ou espaço)
O que isso significa? Por que essa é a entropia dessa sequência? É simples: se alguém quiser chegar nessa mesma sequência partindo do nada, tudo o que precisa fazer é gerar todos os arranjos possíveis de 10 caracteres e um deles descreverá a sua sequência.
Intuitivamente, pode-se perceber por que a entropia está ligada ao conceito de "imprevisibilidade". Imagina que eu te mostrasse só um pedaço dessa sequência:
010011010100110101001101...
Observando bem, dá pra ver que aparece um padrão, e muito embora não há garantia alguma que a sequência continue seguindo esse padrão (o próximo bit poderia ser um 1) ainda é um bom "chute", é preferível testar essa hipótese primeiro em vez de tentar por força bruta todas as sequências possíveis de 80 bits.
Na prática
Um gerador de números pseudo-aleatórios costuma partir de uma semente aleatória e então ir "produzindo" novos números através de um processo bem definido, na esperança desses números se mostrarem imprevisíveis. Mas eles são realmente imprevisíveis? Teoricamente, se você sabe que sua semente é um inteiro de 32 bits, e que a sequência é gerada encriptando os números naturais em ordem usando essa semente como chave (ex.: cifras de fluxo), então ao observar o primeiro número gerado já é possível prever o próximo (e de forma semelhante, todos os outros):
- Crie uma lista com todas as 232 sementes possíveis;
- Encripte o número 0 usando cada uma dessas sementes como chave;
- Compare com o número observado, descobrindo assim qual é a semente certa;
- Encripte o número 1 usando a semente correta; você acaba de prever com 100% de certeza o próximo número da sequência.
Ou seja, do ponto de vista da segurança perfeita, depois que você gerou o primeiro número você já "gastou" toda a entropia da semente, e portanto não deve usá-la de novo (total ou parcialmente) para gerar novos números - do contrário eles não serão realmente imprevisíveis. Ou seja, a entropia da sequência inteira só é tão grande quanto a entropia da semente, talvez menor, mas nunca maior, e você não pode aumentá-la combinando-a com ruído branco ou qualquer outra fonte de aleatoriedade (é preciso substituí-la por esse ruído branco, a original não serve mais pra nada).
E quanto à segurança semântica? Bem, na prática testar 232 possibilidades é bastante custoso, sobretudo porque cada teste envolve um grande número de operações. Por isso, ainda que um adversário observe um número gerado por uma semente de 32 bits, ainda se considera que o próximo número terá uma entropia de aproximadamente 32 bits. Somente após observar uma sequência bem grande (ver ataque de aniversário) é que se considera uma redução na entropia do processo, assumindo que menos e menos operações são necessárias para se prever o restante da sequência.
Ciclos de repetição
Eu mencionei que ao usar uma chave de 32 bits a entropia da sequência seria no máximo 32, mas que poderia ser menos. Isso está relacionado à qualidade do PRNG em si. Se uma semente de 32 bits é usada para gerar números também de 32 bits, então pelo Princípio da Casa dos Pombos a maior sequência possível a ser gerada sem repetição tem tamanho 232. No entanto, se o procedimento de geração não for perfeito, os números podem começar a se repetir muito antes de se atingir um ciclo desse tamanho. O exemplo da função rand()
do PHP no Windows mostra uma repetição prematura dos números gerados (ou ao menos uma repetição prematura de parte dos mesmos), revelando um padrão. Na pior das hipóteses, pode-se até particionar o espaço de soluções, chegando-se a uma previsibilidade perfeita após um número muito pequeno de observações.
Seja o PRNG bom ou ruim, o fato é que ele eventualmente começará a repetir, a menos que mais entropia seja acrescentada ao sistema. Para a segurança semântica, em geral a quantidade de entropia necessária não precisa ser muito grande, já que a "perda" é pequena após cada nova observação. Para a segurança perfeita, como já mencionei, a perda é sempre total, e o acréscimo de ruído branco seria a fonte exclusiva de segurança do sistema. Mas para efeitos práticos, pode-se considerar que à medida que nova entropia é acrescentada - levando em consideração a entropia perdida - o total continuaria crescendo, tendendo ao infinito.
Resumindo
É necessário sim uma fonte externa de aleatoriedade ("barulho") para se obter - não "gerar" - verdadeira aleatoriedade, mesmo porque essa fonte é exclusivamente responsável por qualquer aleatoriedade à exceção da própria semente (e do ponto de vista teórico, restrito ao primeiríssimo uso dessa semente). E não é possível obter "entropia absoluta" de forma alguma, pois a partir do momento em que se para de acrescentar entropia no sistema, esta já começa a diminuir conforme o uso (lentamente, do ponto de vista semântico, ou muito rapidamente, do ponto de vista teórico), e eventualmente chegará a zero.
P.S. Eu estou assumindo que qualquer PRNG, criptograficamente seguro ou não, é periódico. Eu posso estar errado nesse sentido, no entanto isso não muda o fato que, pra uma semente de 32 bits, no máximo 232 sequências distintas podem ser geradas. E embora o acréscimo de ruído não mude essa natureza periódica, um bom algoritmo de mistura pode alongar enormemente esse período, enquanto uma mistura ruim talvez "resete" a sequência mas mantenha seu período inalterado.
P.P.S. Eu interpretei "entropia absoluta" como uma entropia eterna, inesgotável, que foi o que eu entendi baseado no seu comentário. Se o conceito for outro, por favor esclareça. De todo modo, mesmo sem entrar no mérito do "cálculo" (pessoalmente, eu chamaria de "estimação") da entropia, ainda posso afirmar conforme o raciocínio anterior que a entropia sempre se "gasta", e eventualmente chegará a zero a menos que nova entropia seja continuamente acrescentada no sistema.
[1 0]
vc acha que a entropia é zero? são totalmente diferentes não são? usando a equação vai ter umaentropia = 1.4430e-12
isso é equivalente a0.000000000001443
, complexo chegar no0
absoluto.x
sem chegar no0
absoluto...