números aleatórios mais saborosos se um pouco de pimentaCombinaremos teoria com prática - mostraremos que é possível melhorar a entropia de seqüências aleatórias, após o que examinaremos os códigos-fonte que fazem isso.
Eu realmente queria escrever sobre o fato de que a geração aleatória de números de alta qualidade, ou seja, altamente entrópica, é fundamental para resolver um grande número de problemas, mas isso provavelmente é supérfluo. Espero que todos saibam disso muito bem.
Na busca de números aleatórios de qualidade, as pessoas inventam dispositivos muito espirituosos (veja, por exemplo,
aqui e
aqui ). Em princípio, boas fontes de aleatoriedade são incorporadas à API dos sistemas operacionais, mas isso é um assunto sério, e um verme de dúvida sempre nos come um pouco: o RNG que eu uso é bom o suficiente e é estragado ... digamos, por terceiros?
Um pouco de teoria
Para começar, mostramos que, com a abordagem correta, a qualidade do RNG existente não pode ser degradada. A abordagem correta mais simples é sobrepor qualquer outra sequência através da operação XOR na sequência
principal .
A sequência
principal pode ser, por exemplo, um RNG sistêmico, que já consideramos bom, mas ainda há algumas dúvidas, e tínhamos o desejo de jogar pelo seguro.
Uma sequência
adicional pode ser, por exemplo, um gerador de números pseudo-aleatórios, cuja saída parece boa, mas sabemos que sua entropia real é muito baixa.
A sequência
resultante será o resultado da aplicação da operação XOR aos bits das sequências primária e secundária.
Uma nuance significativa: as seqüências primárias e secundárias devem ser independentes uma da outra. Ou seja, sua entropia deve ser obtida de fontes fundamentalmente diferentes, cuja interdependência não pode ser calculada.
Denote por
x o próximo bit da sequência principal
ey - o bit correspondente da sequência adicional. O bit da sequência resultante é indicado por
r :
r = x⊕y
A primeira tentativa de provar. Vamos tentar analisar a entropia informacional de
x ,
ye er . Denotamos a probabilidade de zero
x como
p x0 e a probabilidade de zero
y como
p y0 . As entropias de informações
xey são calculadas de acordo com a fórmula de Shannon:
H
x = - (p
x0 log
2 p
x0 + (1 - p
x0 ) log
2 (1 - p
x0 ))
H
y = - (p
y0 log
2 p
y0 + (1 - p
y0 ) log
2 (1 - p
y0 ))
Zero na seqüência resultante aparece quando há dois zeros ou duas unidades na entrada. Probabilidade de zero r:
p
r0 = p
x0 p
y0 + (1 - p
x0 ) (1 - p
y0 )
H
r = - (p
r0 log
2 p
r0 + (1 - p
r0 ) log
2 (1 - p
r0 ))
Para provar a invariabilidade da sequência principal, é necessário provar que
Hr - Hx ≥ 0 para quaisquer valores de
p x0 ep y0 . Não pude provar analiticamente, mas o cálculo visualizado mostra que o aumento da entropia forma uma superfície lisa, que não vai ser menos que isso:
Por exemplo, se adicionarmos um sinal adicional altamente inclinado com
p y0 = 0,1 ao sinal principal inclinado c
p x0 = 0,3 (entropia 0,881), obteremos o resultado
p r0 = 0,66 com entropia 0,925.
Portanto, a entropia não pode ser estragada, mas isso ainda não é preciso. Portanto, é necessária uma segunda tentativa. No entanto, através da entropia também se pode provar. Esquema (todas as etapas são bastante simples, você pode fazer isso sozinho):
- Provamos que a entropia tem um máximo no ponto p 0 = 1/2.
- Provamos que para qualquer p x0 ep y0, o valor de p r0 não pode ser maior que 1/2 do que p x0 .
A segunda tentativa de provar. Através da capacidade de adivinhar. Suponha que um invasor a priori tenha algumas informações sobre as seqüências primária e secundária. A posse de informações é expressa na capacidade com alguma probabilidade de adivinhar antecipadamente os valores de
x ,
y e, como resultado,
r . As probabilidades de adivinhar
x e
y são denotadas por
g x e
y , respectivamente (da palavra adivinhar). O bit da sequência resultante é calculado quando ambos os valores são calculados corretamente ou quando ambos estão incorretos; portanto, a probabilidade de estimativa é a seguinte:
g
r = g
x g
y + (1 - g
x ) (1 - g
y ) = 2 g
x g
y - g
x - g
y + 1
Quando temos o adivinhador perfeito, temos
g = 1. Se não sabemos nada,
g é ... não, não zero, mas 1/2. Essa é exatamente a probabilidade de adivinhar que se tomarmos uma decisão jogando uma moeda. Um caso muito interessante é quando
g <1/2. Por um lado, esse adivinho em algum lugar dentro de si tem dados sobre o valor previsto, mas por alguma razão inverte sua saída e, portanto, a
moeda se torna
pior . Lembre-se da frase "pior que uma moeda", que será útil para nós abaixo. Do ponto de vista da teoria matemática da comunicação (e, como resultado, a teoria quantitativa da informação que nos é familiar), essa situação é absurda, pois não será uma teoria da informação, mas uma teoria da desinformação, mas na vida temos essa situação com muito mais frequência do que gostaríamos. .
Considere os casos limitantes:
- g x = 1 , ou seja, a sequência x é completamente previsível:
g r = g x g y + (1 - g x ) (1 - g y ) = 1 g y + (1−1) (1 - g y ) = g y
Ou seja, a probabilidade de adivinhar o resultado é igual à probabilidade de adivinhar a sequência adicional. - g y = 1 : Semelhante ao anterior. A probabilidade de adivinhar o resultado é igual à probabilidade de adivinhar a sequência principal.
- g x = 1/2 , ou seja, a sequência x é completamente imprevisível:
g r = 2 g x g y - g x - g y + 1 = 2/2 g y - 1/2 - g y +1 = g y - g y + 1/2 = 1/2
Ou seja, a adição de qualquer sequência adicional não prejudica a imprevisibilidade completa da principal. - g y = 1/2 : Semelhante ao anterior. Adicionar uma sequência extra completamente imprevisível torna o resultado completamente imprevisível.
Para provar que adicionar uma sequência adicional à principal não ajudará o invasor, precisamos descobrir sob quais condições
g r pode ser maior que
g x , ou seja,
2 g
x g
y - g
x - g
y + 1> g
xMova g
x do lado direito para a esquerda e g
y e 1 para a direita:
2 g
x g
y - g
x - g
x > g
y - 1
2 g
x g
y - 2 g
x > g
y - 1
Retiramos no lado esquerdo 2g
x entre parênteses:
2 g
x (g
y - 1)> g
y - 1
Como temos g
y menor que um (o caso limitante quando g
y = 1, já consideramos), transformamos g
y -1 em 1 - g
y , sem esquecer de mudar "mais" para "menos":
2 g
x (1 - g
y ) <1 - g
yReduza “1 - g
y ” e obtenha a condição sob a qual a adição de uma sequência adicional melhorará a situação para o atacante adivinhar:
2 g
x <1
g
x <1/2
Ou seja,
g r pode ser maior que
g x apenas quando se pensa que a sequência principal é
pior que uma moeda . Então, quando nosso preditor estiver envolvido em sabotagem consciente.
Algumas considerações adicionais sobre entropia.- Entropia é um conceito extremamente mitológico. Informações - inclusive. Isso é muito perturbador. Freqüentemente, a entropia informacional é representada como um tipo de matéria sutil que está objetivamente presente nos dados ou não. De fato, a entropia informacional não é algo presente no próprio sinal, mas uma avaliação quantitativa da percepção a priori do destinatário da mensagem em relação à própria mensagem. Ou seja, não é apenas sobre o sinal, mas também sobre o destinatário. Se o destinatário não souber nada sobre o sinal com antecedência, a entropia informacional da unidade binária transmitida é exatamente de 1 bit, independentemente de como o sinal foi recebido e o que é.
- Temos um teorema de adição de entropia segundo o qual a entropia total de fontes independentes é igual à soma das entropias dessas fontes. Se combinássemos a sequência principal com a adicional através da concatenação, teríamos preservado as entropias das fontes, mas teríamos um resultado ruim, porque em nossa tarefa precisamos avaliar não a entropia total, mas a específica, em termos de um bit separado. A concatenação de fontes nos fornece a entropia específica do resultado igual à média aritmética da entropia das fontes, e a seqüência adicional fraca de entropia piora naturalmente o resultado. A aplicação da operação XOR leva ao fato de que perdemos parte da entropia, mas é garantido que a entropia resultante não seja pior que a entropia máxima dos termos.
- Os criptografadores têm um dogma: o uso de geradores de números pseudo-aleatórios é uma arrogância imperdoável. Porque esses geradores têm uma pequena entropia específica. Mas acabamos de descobrir que, se tudo for feito corretamente, a entropia se tornará um barril de mel que não pode ser estragado por nenhuma quantidade de alcatrão.
- Se tivermos apenas 10 bytes de entropia real, distribuídos por um kilobyte de dados, de um ponto de vista formal, teremos apenas 1% da entropia específica, o que é muito ruim. Mas se esses 10 bytes são manchados qualitativamente e, além da força bruta, não há como calcular esses 10 bytes, tudo não parece tão ruim. 10 bytes é 2 80 , e se nossa força bruta por segundo pesquisar em um trilhão de opções, precisaremos de uma média de 19 mil anos para aprender a adivinhar o próximo caractere.
Como mencionado acima, a entropia informacional é um valor relativo. Onde, para um assunto, a entropia específica é 1, para outro pode ser 0. Além disso, um com 1 pode não ter como saber o verdadeiro estado das coisas. O sistema RNG produz um fluxo indistinguível para nós de verdadeiramente aleatório, mas só podemos esperar que seja realmente aleatório
para todos . E acredite. Se a paranóia sugere que a qualidade do RNG principal pode subitamente ser insatisfatória, faz sentido proteger com a ajuda de outro.
Implementando um RNG de soma em Python
from random import Random, SystemRandom from random import BPF as _BPF, RECIP_BPF as _RECIP_BPF from functools import reduce as _reduce from operator import xor as _xor class CompoundRandom(SystemRandom): def __new__(cls, *sources): """Positional arguments must be descendants of Random""" if not all(isinstance(src, Random) for src in sources): raise TypeError("all the sources must be descendants of Random") return super().__new__(cls) def __init__(self, *sources): """Positional arguments must be descendants of Random""" self.sources = sources super().__init__() def getrandbits(self, k): """getrandbits(k) -> x. Generates an int with k random bits."""
Exemplo de uso:
>>> import random_xe
O SystemRandom, que é considerado correto, é considerado o fluxo principal e o fluxo secundário - o PRNG Random padrão. O ponto nisso, é claro, não é muito. O PRNG padrão definitivamente não é o tipo de suplemento para o qual valeu a pena começar. Em vez disso, você pode casar dois RNGs sistêmicos juntos:
>>> myrandom2 = random_xe.CompoundRandom(SystemRandom(), SystemRandom())
O sentido é que a verdade é ainda menor (embora por algum motivo Bruce Schneier recomende essa técnica em Criptografia Aplicada por algum motivo), porque os cálculos acima são válidos apenas para fontes independentes. Se o sistema RNG estiver comprometido, o resultado também será comprometido. Em princípio, o vôo da fantasia na busca por uma fonte de entropia adicional não é limitado por nada (em nosso mundo, a desordem é muito mais comum que a ordem), mas como uma solução simples, ofereço o HashRandom PRSP, também implementado na biblioteca random_xe.
PRSPs baseados em streaming de hash circular
No caso mais simples, você pode pegar uma quantidade relativamente pequena de dados iniciais (por exemplo, pedir ao usuário para tocar o teclado), calcular o hash e adicionar ciclicamente o hash à entrada do algoritmo de hash e pegar os seguintes hashes. Esquematicamente, isso pode ser representado da seguinte maneira:
A força criptográfica desse processo é baseada em duas suposições:
- A tarefa de restaurar os dados originais do valor do hash é insuportavelmente complicada.
- Usando o valor do hash, é impossível restaurar o estado interno do algoritmo de hash.
Após consultar um paranóico interno, ele reconheceu a segunda suposição como desnecessária e, portanto, na implementação final do PRNG, o esquema é um pouco complicado:
Agora, se um invasor conseguir obter um valor de "Hash 1r", ele não poderá calcular o valor de "Hash 2r" após ele, pois ele não possui um valor de "Hash 2h" que não pode reconhecer sem calcular a função de hash "contra a lã". Assim, a força criptográfica desse esquema corresponde à força criptográfica do algoritmo de hash usado.
Exemplo de uso:
>>>
Por padrão, o algoritmo SHA-256 é usado. Se você quiser algo mais, pode transferir o tipo desejado de algoritmo de hash para o construtor com o segundo parâmetro. Por exemplo, vamos criar um RNG composto, resumindo o seguinte em uma pilha:
1. RNG sistêmico (isso é sagrado).
2. Entrada do usuário processada pelo algoritmo SHA3-512.
3. O tempo gasto nessa entrada processado pelo SHA-256.
>>> from getpass import getpass >>> from time import perf_counter >>> from hashlib import sha3_512
Conclusões:- Se não tivermos certeza do nosso gerador de números aleatórios, podemos resolver esse problema de maneira fácil e incrivelmente barata.
- Resolvendo esse problema, não podemos fazer pior. Só que melhor E é matematicamente comprovado.
- Não devemos esquecer de tentar garantir que as fontes de entropia usadas sejam independentes.
As fontes da biblioteca estão no
GitHub .