Início / unix / Perguntas / 496788
Accepted
flow2k
Asked: 2019-01-26 16:58:57 +0800 CST

O tamanho do arquivo random_source importa?

  • 772

Alguns utilitários GNU coreutils gostam sorte shufusam um arquivo como o que efetivamente serve uma semente. O tamanho do arquivo importa?

A maneira recomendada, https://www.gnu.org/software/coreutils/manual/html_node/Random-sources.html , usa um método baseado em openssl que leva bastante tempo.

E se eu usar apenas uma palavra de 6 letras como abaixo? Isso afeta a capacidade dos referidos utilitários de criar pseudo-aleatoriedade?

shuf -i1-10 --random-source=<(echo durian)

sort coreutils

2 respostas

  1. Best Answer

    Se você fornecer uma string fixa como fonte aleatória, ela será "randomizada" da mesma maneira todas as vezes . Para provar isso, vamos testá-lo.

    $ printf '%s\n' a b c | shuf --random-source=<(echo durian)
b
c
a

    No meu sistema, a saída é a mesma toda vez que executo o comando acima. (Suspeito que possa ser diferente dependendo da implementação, mas ainda deve ser o mesmo todas as vezes.) Você está codificando a aleatoriedade, conforme este XKCD:

    XKCD

    Não é realmente aleatório; está apenas produzindo a mesma saída todas as vezes. O tamanho da fonte de string fixa é irrelevante. Ainda está fixo.

    Há informações relevantes no link que você fornece relacionadas à qualidade aleatória da fonte aleatória:

    /dev/urandomé suficiente para a maioria dos usos práticos, mas os aplicativos que exigem proteção de dados privados de alto valor ou longo prazo podem exigir uma fonte de dados alternativa como /dev/randomou /dev/arandom.

    As duas últimas opções são "mais aleatórias" que a primeira. A implicação é que quanto mais aleatória a fonte, mais aleatório o embaralhamento. Portanto, strings fixas não são particularmente robustas.

    Com shufespecificamente, o comprimento da string fixa é relevante. Por exemplo, o seguinte falha.

    shuf -i1-19 --random-source=<(echo durian)

    No entanto, se você restringir a saída para -n16, ela funcionará, mas -n17falhará. Testei algumas palavras e permutações diferentes e, à medida que reduzo o número de caracteres na fonte, o máximo -ndiminui.

    source length     max -n
7                 16
6                 13
5                 10
4                  8
3                  5
2                  3
1                  1
0                  0

    Não tenho certeza do relacionamento direto, mas presumivelmente itens classificados adicionais (em -n) exigem mais caracteres de origem como sementes. No entanto, shufpelo menos, uma vez que você ultrapasse esse limite mínimo, cada caractere adicional não faz diferença para a aleatoriedade em si. No exemplo acima, se você alterar o 50º caractere, a saída ainda será a mesma.

    • 3

  2. Sim, o tamanho importa para shuf: O tamanho deve ser tão grande quanto necessário para randint_genmax()em https://github.com/coreutils/coreutils/blob/master/gl/lib/randint.c para derivar todos os números aleatórios do algoritmo de embaralhamento usado necessidades (cada número pode ser escolhido de um intervalo específico). Este tamanho depende de ambos

    • o número de linhas de entrada e
    • os valores de byte no arquivo de origem aleatório.

    Se você alterar um byte no arquivo de origem aleatório, ele poderá alterar quantos bytes no total são necessários. Por exemplo, se for necessário um número no intervalo 0-254, basta ler um byte se estiver nesse intervalo, mas se o byte for '\xff' (255 como um inteiro de 8 bits sem sinal) pelo menos um mais byte é necessário também.

    Isso pode ser usado para construir um exemplo que falha mesmo que muitos bytes sejam fornecidos:

    shuf -i1-10 --random-source=<(echo $'\xff\xff\xff\xff\xff\xff\xff\xff')
shuf: ‘/dev/fd/63’: end of file

    Apenas três bytes 'ab' + nova linha podem ser suficientes:

    shuf -i1-10 --random-source=<(echo ab) | md5sum
742a739ea959851f883ec692d6675cdf  -

    Para fornecer uma fonte pseudo aleatória com semente, não encontrei uma solução apenas de linha de comando, mas pelo menos aqui está uma solução de rascunho usando apenas o bash (veja o problema conhecido abaixo):

    (1) Script auxiliar seed-and-counter.sh:

    #!/bin/bash
SEED="$1"
COUNTER=0
while true; do
    echo $SEED $COUNTER
    COUNTER=$((COUNTER+1))
done

    (2) Roteiro auxiliar bin-hash-lines.sh:

    #!/bin/bash
echo "$1" | md5sum | cut -c-32 | xxd -r -p

    (3) Combine-os para produzir uma sequência reproduzível de bytes aleatórios:

    ./seed-and-counter.sh 320 | xargs -d'\n' -n 1 ./bin-hash-lines.sh | hexdump -C | head
00000000  02 56 8b 68 34 78 bd 98  6e 8d 42 d2 cb 7b 8d b4  |.V.h4x..n.B..{..|
00000010  7d d8 23 b9 89 f8 29 5b  6c 51 fb 9f b3 74 1d 03  |}.#...)[lQ...t..|
00000020  bc 1d 62 81 31 0b 5d 82  8c cb 37 4a b8 bc 85 70  |..b.1.]...7J...p|
00000030  88 3d 57 ae ef 77 28 aa  3a cf f7 49 ed 00 37 21  |.=W..w(.:..I..7!|
00000040  45 55 39 94 3f 30 90 49  4f f0 04 d5 1e c5 0c 1e  |EU9.?0.IO.......|
00000050  e4 e8 8e 72 84 58 3c 03  66 e5 bd af fb 87 78 6b  |...r.X<.f.....xk|
00000060  b0 40 e4 cb 6f 78 c0 90  f8 e6 0d 73 89 fe 0a 98  |[email protected]....|
00000070  04 45 39 0c e6 32 ae 26  c5 13 0e ca fb e6 bc f2  |.E9..2.&........|
00000080  49 57 65 da 79 c1 4f 03  f7 97 ec 8c 72 59 cf ac  |IWe.y.O.....rY..|
00000090  64 d6 fe 87 6e 18 5e 81  2c 9b a3 6a b5 10 12 da  |d...n.^.,..j....|

    (4) Use isso como fonte aleatória:

    shuf -i1-1000 --random-source=<(./seed-and-counter.sh 320 | xargs -d'\n' -n 1 ./bin-hash-lines.sh) | tail
430
854
890
580
441
960
944
332
687
703

    Problema conhecido: os scripts auxiliares e o xargscomando parecem continuar em execução.

    • 1

relate perguntas