☰

random_source 파일의 크기가 중요합니까?

tag-icon • tag-icon sort coreutils random shuf
random_source 파일의 크기가 중요합니까?

일부 GNU coreutils 유틸리티 sort는 shuf파일을 유효한 서비스 시드로 사용합니다. 파일 크기가 중요합니까?

추천하는 방법,https://www.gnu.org/software/coreutils/manual/html_node/Random-sources.html, openssl 기반 방법을 사용하면 시간이 꽤 오래 걸립니다.

다음과 같이 6글자 단어만 사용하면 어떻게 되나요? 이것이 의사 무작위성을 생성하는 유틸리티의 능력에 영향을 줍니까?

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

답변1

고정 문자열을 무작위 소스로 제공하면 동일한 방식으로 "무작위화"됩니다.매번. 이를 증명하기 위해 테스트해 보겠습니다.

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

내 시스템에서는 위 명령을 실행할 때마다 출력이 동일합니다. (구현에 따라 다를 수 있지만 매번 동일해야 한다고 생각합니다.) 이 XKCD에 따르면 무작위성을 하드코딩하고 있습니다.

지코CD

실제로는 무작위가 아닙니다. 매번 동일한 출력을 생성합니다. 고정 문자열 소스의 크기는 중요하지 않습니다. 아직 해결된 상태입니다.

관련 정보가 들어있어요제공한 링크에 대한무작위의무작위 소스의 품질:

/dev/urandom대부분의 실제 목적에는 충분하지만 개인 데이터의 높은 가치나 장기적인 보호가 필요한 애플리케이션에는 /dev/random또는 와 같은 대체 데이터 소스가 필요할 수 있습니다 /dev/arandom.

후자의 두 옵션은 첫 번째 옵션보다 "더 무작위적"입니다. 즉, 소스가 무작위일수록 셔플도 더 무작위로 이루어집니다. 따라서 고정 문자열은 특별히 견고하지 않습니다.

특히 shuf문자열의 길이를 고정하는 것과 관련이 있습니다. 예를 들어 다음은 실패합니다.

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

그러나 출력을 로 제한하면 -n16작동하지만 -n17실패합니다. 몇 가지 다른 단어와 순열을 테스트했는데 소스의 문자 수를 줄이면 최대값도 -n떨어졌습니다.

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

직접적인 관계는 확실하지 않지만 아마도 추가로 정렬된 항목( -n)에는 시드로 더 많은 소스 문자가 필요할 것입니다. 그러나 적어도 shuf이 최소 임계값을 초과하면 각 추가 문자는 무작위성 자체에 영향을 미치지 않습니다. 위의 예에서 50번째 문자를 변경해도 출력은 여전히 ​​동일합니다.

답변2

예, 크기가 중요합니다 . shuf필요한 만큼 randint_genmax()커야 합니다.https://github.com/coreutils/coreutils/blob/master/gl/lib/randint.c사용된 셔플링 알고리즘에 필요한 모든 난수를 파생시킵니다(각 숫자는 특정 범위에서 선택할 수 있음). 이 크기는 두 가지 모두에 따라 다릅니다.

  • 행 수를 입력하고
  • 무작위 소스 파일의 바이트 값.

임의의 소스 파일에서 1바이트를 변경하면 필요한 총 바이트 수가 변경될 수 있습니다. 예를 들어, 0-254 범위의 숫자가 필요한 경우 이 범위에 있으면 1바이트만 읽는 것으로 충분하지만 해당 바이트가 "\xff"(부호 없는 8비트로 255)인 경우 정수) , 최소 1바이트를 읽으려면 더 많은 바이트가 필요합니다.

이는 많은 수의 바이트가 제공되더라도 실패하는 예제를 작성하는 데 사용할 수 있습니다.

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

3바이트 "ab" + 개행 문자이면 충분합니다.

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

시드와 함께 의사 무작위 소스를 제공하기 위해 명령줄 전용 솔루션을 찾지 못했지만 적어도 여기에는 bash만 사용하는 초안 솔루션이 있습니다(아래 알려진 문제 참조).

(1) 보조 스크립트 seed-and-counter.sh:

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

(2) 보조 스크립트 bin-hash-lines.sh:

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

(3) 이를 결합하여 재현 가능한 임의 바이트 시퀀스를 생성합니다.

./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) 무작위 소스로 사용하십시오.

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

알려진 문제: 도우미 스크립트와 xargs명령이 계속 실행되는 것으로 나타납니다.

관련 정보