3

Tenho uma função que gera números pseudo-aleatórios com rand que tem um seed que é uma hora publicamente conhecida. Alterar a seed não é uma opção.

A aplicação necessita de um grau mais apurado de aleatoriedade, pois essa ordena uma sequência de elementos em uma lista e tal lista não pode, de maneira nenhuma, ser reconstruída. Pois o seed e a lista aleatória são públicos, dessa forma a reconstrução da lista inicial é possível. O resultado de uma lista ordenada pode ou não ser único.

A lista ordenada de forma "aleatória" também é pública. O ambiente da aplicação é Linux. Gostaria de saber como realizar isso com alguma outra função.

5
  • 1
    srand deve ser chamado apenas na inicialização do gerador. Qual sistema operacional? Se for Linux, utilize o /dev/random ou /dev/urandom provido pelo SO. Ou utilize o algoritmo Mersenne-Twister. Commented 2/10/2015 às 2:35
  • 1
    O que você quer dizer com "grau mais apurado de aleatoriedade"? Há algum teste de aleatoriedade que a função rand não está passando? Ou talvez o período da função seja curto demais? Por favor especifique exatamente o que procura. O uso de /dev/urandom ou algum CSPRNG (se aplicável) ou talvez algum processo de mixagem pode ser uma boa ideia, ou não, depende muito de onde você quer chegar...
    – mgibsonbr
    Commented 2/10/2015 às 3:46
  • Tentei ser muito generalista e acabei tornando a pergunta vaga.
    – DaviAragao
    Commented 2/10/2015 às 14:18
  • Melhorou, mas me explica melhor o que quer dizer com "tal lista não pode, de maneira nenhuma, ser reconstruída". Significa que após repetidos sorteios você não quer que volte à mesma lista? Ou entendi errado? Além disso, é importante pra você que o programa seja repetível, i.e. que dado o mesmo seed se chegue ao mesmo sorteio? Se a resposta for "não", então /dev/urandom é uma boa pedida (mas talvez não seja suficiente pros seus requisitos, esclareça o ponto acima por favor e talvez eu consiga responder algo).
    – mgibsonbr
    Commented 2/10/2015 às 14:37
  • Podes usar o Mersenne Twister com inicialização melhorada.
    – pmg
    Commented 2/10/2015 às 15:56

1 Resposta 1

2

Você precisa de uma função de hash.

Se entendi bem, sua lista final é Li e sua semente s, e a lista final Lf é dada por Lf = f(s, Li). Lf e s são públicos, e você não quer que se descubra Li somente a partir de ambas as informações públicas apresentadas. Certo? Nesse caso, tudo o que você precisa fazer é com que a função f não seja invertível (i.e. dado seu resultado - sua imagem - você descubra suas entradas - sua pré-imagem).

Não se sabe se existem ou não funções não-invertíveis (one-way functions), mas até hoje ninguém sabe como inverter eficientemente certas funções de hash. De modo que elas são uma boa candidata para resolver seu problema. Se você tiver acesso a alguma delas, digamos SHA-256, você pode usá-la para gerar uma sequência de números pseudo-aleatórios:

semear(Li, s) {
    sufixo = SHA-256(str(Li) + SHA-256(s))
    indice = 0
}

próximo número aleatório() {
    return SHA-256((indice++) + sufixo);
}

Pseudo-código: str(Li) é uma representação em string (ou bytes) da sua lista, e + no caso representa a concatenação. Também é necessário transformar a saída da função SHA-256 (que virá em bytes ou em string hexadecimal, normalmente) em um número usável.

O fato de eu ter chamado SHA-256 várias vezes dessa forma é pra evitar length extension attacks, pode ser exagero, mas prefiro pecar pelo excesso de cautela... O fato é que cada vez que você pedir um novo número aleatório ele vai calcular o hash de um valor único, imprevisível sem o conhecimento de Li. E a saída de uma boa função de hash costuma ser indistinguível de um valor realmente aleatório.

P.S. Essa solução pode não ser a mais rápida de todas, mas preserva a propriedade desejada. De início eu pensei em simplesmente semear o rand com o valor do hash, mas aí me lembrei que é possível recuperar a semente do mesmo observando-se um número relativamente pequeno de valores gerados... De modo que não serve para o propósito. Outra alternativa que me veio à cabeça agora é usar um CSPRNG semeado da mesma forma que no meu exemplo (uma combinação da lista original e do seu seed), não sei quais existem nem boas implementações dos mesmos em C, mas se você tiver acesso a um o desempenho certamente será melhor que essa minha solução ad-hoc...

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .