의사 난수와 실제 난수는 어떻게 다르며 왜 중요한가? 번 롤링되었을 것으로 예상됩니다. 왜 ‘진정한

나는 이것을 전혀 얻지 못했습니다. 주사위를 굴리는 모든 언어로 작은 프로그램을 작성한다고 가정하십시오 (예를 들어 주사위를 사용함). 600,000 롤 후, 각 숫자는 약 10 만 번 롤링되었을 것으로 예상됩니다.

왜 ‘진정한 무작위성’전용 웹 사이트가 있습니까? 분명히, 위의 관찰을 고려할 때, 어떤 숫자를 얻을 확률은 얼마나 많은 숫자를 선택할 수 있는지에 대해 거의 정확히 1입니다.

나는 파이썬으로 시도했다 : 6 천만 롤의 결과는 다음과 같다. 가장 높은 변형은 0.15와 같습니다. 그것이 얻는 것만 큼 무작위 적이 지 않습니까?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0



답변

당신과 나, 그리고 우리 둘 다 신뢰하는 서버로 컴퓨터 포커를하자. 서버는 우리가 플레이하기 직전에 32 비트 시드로 초기화 된 의사 난수 생성기를 사용합니다. 약 40 억 개의 갑판이 있습니다.

나는 내 손에 5 장의 카드를받습니다. 분명히 우리는 Texas Hold ‘Em을하고 있지 않습니다. 카드가 나에게, 하나는 당신에게, 하나는 나에게, 하나는 당신에게, 등등 처리된다고 가정하자. 덱에 첫 번째, 세 번째, 다섯 번째, 일곱 번째 및 아홉 번째 카드가 있습니다.

이전에 의사 난수 생성기를 각 시드마다 한 번씩 40 억 번 실행하고 각각에 대해 생성 된 첫 번째 카드를 데이터베이스에 기록했습니다. 첫 번째 카드가 스페이드의 여왕이라고 가정합니다. 이는 가능한 모든 덱 52 개 중 하나에서 첫 번째 카드로만 표시되므로 가능한 덱을 40 억에서 8 천만 정도 정도로 줄였습니다.

내 두 번째 카드가 세 개의 하트라고 가정합니다. 이제 스페이드 여왕을 첫 번째 숫자로 만드는 8 천만 종자를 사용하여 RNG를 8 천만 번 더 실행합니다. 이 작업에는 몇 초가 걸립니다. 나는 세 번째 카드, 즉 내 손에 두 번째 카드로 세 개의 하트를 생성하는 모든 데크를 기록합니다. 이는 다시 데크의 약 2 %에 불과하므로 이제는 2 백만 데크로 줄었습니다.

제 손에있는 세 번째 카드가 7 개의 클럽이라고 가정합니다. 나는 두 카드를 다루는 200 만 종자 데이터베이스를 가지고있다. 7 개의 클럽을 세 번째 카드로 만드는 데크의 2 %를 찾기 위해 RNG를 2 백만 번 더 실행하면 4 만 데크에 불과합니다.

이것이 어떻게 진행되는지 봅니다. RNG 40000을 네 번 더 실행하여 네 번째 카드를 생산하는 모든 씨앗을 찾고 800 데크까지 데려 간 다음 800 번 더 실행하여 다섯 번째 카드를 생산하는 ~ 20 개의 씨앗을 얻습니다. 20 개의 카드 덱을 생성하면 20 개의 손 중 하나가 있다는 것을 알고 있습니다. 또한, 나는 다음에 무엇을 그릴 지에 대해 아주 잘 알고 있습니다.

이제 왜 진정한 무작위성이 중요합니까? 당신이 설명하는 방식으로, 당신은 분배 가 중요 하다고 생각 하지만, 분배는 프로세스를 무작위로 만드는 것이 아닙니다. 예측 불가능 성은 공정을 무작위로 만드는 것입니다.

최신 정보

(현재 구조적이지 않기 때문에 삭제 된) 의견에 따르면, 이것을 읽은 사람들의 적어도 0.3 %가 내 요지에 대해 혼란스러워합니다. 사람들이 점을 내가 만든, 또는 악화되지 않은에 대해 주장 할 때, 주장 에 대해 나는 점 않았다 내가 그들을하지 않은 가정을 확인한 다음 나는 더 명확하게 조심스럽게 설명 할 필요가 있음을 알고있다.

단어 배포와 관련 하여 특히 혼란스러워 보이므로 사용법을 신중하게 호출하고 싶습니다.

당면한 질문은 다음과 같습니다.

  • 의사 난수와 실제 난수는 어떻게 다릅니 까?
  • 차이점이 왜 중요한가요?
  • 차이점은 PRNG의 결과 분포와 관련이 있습니까?

포커를 할 수있는 임의의 카드 덱을 생성하는 완벽한 방법을 고려하여 시작합시다 . 그런 다음 데크 생성을위한 다른 기술이 어떻게 다른지 살펴보고 그 차이를 활용할 수 있는지 살펴 보겠습니다.

마술 상자에 레이블이 붙어 있다고 가정 해 봅시다 TRNG. 입력으로 우리는 정수 n을 1보다 크거나 같게하고, 그 출력으로서 1과 n 사이의 정수 (정수)를 제공합니다. 상자의 출력은 전체적으로 예측할 수 없으며 (1 이외의 숫자가 지정된 경우) 1과 n 사이의 숫자는 다른 것과 같습니다. 즉, 분포균일 하다는 것입니다 . (우리가 수행 할 수있는 다른 고급 무작위 통계 검사가 있습니다. 나는이 주장이 내 주장에 맞지 않기 때문에이 점을 무시하고 있습니다. TRNG는 가정에 의해 완벽하게 통계적으로 무작위입니다.)

우리는 섞이지 않은 카드 덱으로 시작합니다. 상자에 1에서 52 사이의 숫자, 즉 TRNG(52). 숫자가 무엇이든, 우리는 분류 된 덱에서 그 많은 카드를 세어 그 카드를 제거합니다. 뒤섞인 데크에서 첫 번째 카드가됩니다. 그런 다음 TRNG(51)두 번째 카드를 선택 하도록 요청 하고 동일한 작업을 수행합니다.

그것을 보는 또 다른 방법은 52입니다! = 52 x 51 x 50 … x 2 x 1 가능한 데크, 대략 2 226 입니다. 우리는 그중 하나를 무작위로 선택했습니다.

이제 우리는 카드를 다룹니다. 내 카드를 볼 때 어떤 카드를 가지고 있는지 전혀 모릅니다. (내가 가지고있는 카드가 없다는 명백한 사실을 제외하고) 같은 확률로 모든 카드가 될 수 있습니다.

제가 이것을 명확하게 설명하도록하겠습니다. 우리는 각 개별 출력의 균일 한 분포 를 가지고 있습니다 TRNG(n). 각각 1과 n 사이의 숫자를 확률 1 / n으로 선택합니다. 또한이 프로세스의 결과로 52 개 중 하나를 선택했습니다! 1/52의 확률! 그래서 분포 가능한 데크 가능한 갑판의 위에 세트가 있다 또한 균일.

괜찮아.

이제 레이블이 적은 마법 상자가 있다고 가정 해 봅시다 PRNG. 사용하기 전에 부호없는 32 비트 숫자 로 시드 해야합니다 .

ASIDE : 왜 32 입니까? 64 또는 256 또는 10000 비트 숫자로 시드 할 수 없습니까? 확실한. 그러나 (1) 실제로 대부분의 상용 PRNG는 32 비트 숫자로 시드되며, (2) 시드를 만들기 위해 10000 비트의 임의성이 있으면 PRNG를 사용하는 이유는 무엇입니까? 이미 10000 비트의 무작위 소스가 있습니다!

어쨌든 PRNG의 작동 방식으로 돌아갑니다. 시딩 후 사용하는 것과 같은 방식으로 사용할 수 있습니다 TRNG. 즉, 숫자 n을 전달하면 1과 n 사이의 숫자를 포함합니다. 또한, 그 출력의 분포는 다소 균일 합니다. 즉 PRNG, 우리가 1에서 6 사이의 숫자를 요청할 때, 씨앗이 무엇이든 관계없이 대략 6 분의 1의 1, 2, 3, 4, 5 또는 6을 얻습니다.

나는이 점을 몇 번 강조하고 싶다. 왜냐하면 그것은 특정 주석가들을 혼란스럽게 만드는 점이기 때문이다. PRNG의 분포는 적어도 두 가지 방식으로 균일하다. 먼저 특정 종자를 선택한다고 가정하십시오. PRNG(6), PRNG(6), PRNG(6)...백만 번의 시퀀스 는 1에서 6 사이의 숫자 분포를 균등하게 분배 할 것으로 예상됩니다 . 둘째, 백만 개의 다른 시드를 선택하고 각 시드에 대해 PRNG(6) 한 번 호출 하면 다시 1에서 5까지의 균일 한 분포가 예상됩니다. 6. 이러한 작업 중 하나에서 PRNG의 균일 성은 내가 설명하는 공격과 관련이 없습니다 .

이 과정은 상자의 동작이 실제로 완전히 결정적이므로 의사 난수 라고합니다. 시드에 따라 2 개의 32 가지 가능한 동작 중 하나를 선택합니다 . 즉, 일단 시딩되면 균일 한 분포를 PRNG(6), PRNG(6), PRNG(6), ... 갖는 일련 의 숫자를 생성 하지만, 그 순서는 전체적으로 시드에 의해 결정됩니다. PRNG (52), PRNG (51) … 등의 일련의 호출에 대해 2 개의 32 개의 가능한 시퀀스가 ​​있습니다. 씨앗은 본질적으로 우리가 얻는 것을 선택합니다.

데크를 생성하기 위해 서버는 이제 시드를 생성합니다. (우리는 다시 그 시점에 온 것이다 어떻게?.) 그런 다음 그들은 전화 PRNG(52), PRNG(51)이전과 비슷한 갑판을 생성하는 등등합니다.

이 시스템은 내가 설명한 공격에 취약합니다. 먼저 서버를 공격하기 위해 먼저 상자 자체에 0을 시드하고 요청 PRNG(52)하고 적어 둡니다. 그런 다음 1로 다시 시드하고 요청하고 PRNG(52)최대 2 32 -1까지 기록하십시오.

이제 PRNG를 사용하여 데크를 생성하는 포커 서버는 어떻게 든 시드를 생성해야합니다. 그들이 그렇게하는 것은 중요하지 않습니다. 그들은 TRNG(2^32)정말 무작위 씨앗을 얻기 위해 전화 를 걸 수 있습니다. 또는 그들은 현재 시간을 씨앗으로 삼을 수 있습니다. 나는 당신이 몇시인지 알고 있습니다. 내 공격의 요점은 데이터베이스가 있기 때문에 중요하지 않다는 것입니다 . 첫 카드를 볼 때 가능한 씨앗의 98 %를 제거 할 수 있습니다. 두 번째 카드를 볼 때 98 % 더 많은 것을 제거 할 수 있습니다. 결국 몇 가지 가능한 씨앗을 얻을 수있을 때까지 당신의 손에 무엇이 있는지 알 수 있습니다.

다시 한 번, 여기서 백만 번을 호출 PRNG(6)하면 각 숫자의 약 1/6을 얻게 된다는 가정을 강조하고 싶습니다 . 그 분포는 (거의) 균일 하며, 그 분포의 균일성에 관심이 있다면 괜찮습니다. 문제의 요점은 우리가 관심 을 갖는 다른 배포판이 PRNG(6)있습니까? 대답은 ‘ 예’ 입니다. 우리는 예측할 수없는 것도 염려 합니다.

문제를 보는 또 다른 방법 은 PRNG가 2 32 개의 가능한 동작 중에서 선택하기 때문에 백만 PRNG(6)번의 호출을 분배 해도 괜찮을 수 있지만 가능한 모든 데크를 생성 할 수는 없습니다. 2,226 개의 데크 중 2 32 개만 생성 할 수 있습니다 . 작은 분수. 따라서 모든 데크 세트에 대한 분포 는 매우 나쁩니다. 그러나 여기서도 근본적인 공격 은 작은 산출량으로 과거와 미래의 행동 을 성공적으로 예측할 수 있다는 점 입니다. PRNG

이것을 세 번 또는 네 번 말씀 드리고자합니다. 여기에는 세 가지 분포가 있습니다. 첫째, 랜덤 32 비트 시드를 생성하는 프로세스의 분포. 그것은 완벽하게 임의적이고 예측할 수 없으며 균일 할 수 있으며 공격은 여전히 ​​유효합니다 . 둘째,에 백만 번의 전화 분배 PRNG(6). 그것은 완벽하게 균일 할 수 있으며 공격은 여전히 ​​작동합니다. 셋째, 의사 난수 처리 과정에서 선택한 데크의 분포에 대해 설명했습니다. 그 분포는 매우 열악합니다. IRL 가능한 데크의 작은 부분 만 선택할 수 있습니다. 공격은 출력에 대한 부분적인 지식을 기반으로 PRNG의 행동 예측 가능성 에 달려 있습니다.

ASIDE :이 공격은 공격자가 PRNG에서 사용하는 정확한 알고리즘이 무엇인지 알고 있거나 추측 할 수 있어야합니다. 그것이 현실적인지 아닌지는 공개 된 질문입니다. 그러나 보안 시스템을 설계 할 때 공격자가 프로그램의 모든 알고리즘을 알고 있더라도 공격으로부터 보호되도록 보안 시스템을 설계해야합니다 . 다시 말해, 보안을 유지하기 위해 보안을 유지해야하는 보안 시스템 부분을 “키”라고합니다. 시스템이 보안에 의존하여 사용하는 알고리즘에 의존하는 경우 키에는 해당 알고리즘이 포함 됩니다. 그것은 매우 약한 입장입니다!

계속합니다.

이제라는 레이블이 붙은 세 번째 마법 상자가 있다고 가정 해 봅시다 CPRNG. 의 암호화 강도 버전입니다 PRNG. 32 비트 시드가 아닌 256 비트 시드가 필요합니다. 그것은 PRNG종자가 2,256 개의 가능한 행동 중 하나에서 선택하는 특성 과 공유됩니다 . 다른 기계와 마찬가지로 CPRNG(n)1과 n 사이의 균일 한 결과 분포 를 생성하기 위한 많은 호출이 1 / n의 시간마다 발생한다는 특성이 있습니다. 우리는 그것에 대해 우리의 공격을 실행할 수 있습니까?

우리의 원래 공격은 씨앗에서까지 32 개의 매핑 을 저장해야 합니다 PRNG(52). 그러나 2256 은 훨씬 더 큰 숫자입니다. CPRNG(52)여러 번 실행 하여 결과를 저장하는 것은 완전히 불가능 합니다.

그러나 씨앗에 대한 사실을 추론 할 수있는 다른 방법 이 있다고 가정 해 봅시다 CPRNG(52). 우리는 지금까지 꽤 멍청했습니다. 가능한 모든 조합을 무차별하게 적용했습니다. 우리는 마법 상자를 들여다보고 그것이 어떻게 작동하는지 알아 내고, 출력을 기반으로 씨앗에 관한 사실을 추론 할 수 있습니까?

제 자세한 설명이 너무 복잡하지만 추론 없음 불가능되도록 CPRNGs 교묘하게 설계되어 어떠한 의 첫 번째 출력의 씨앗에 대한 유용한 사실 CPRNG(52)또는에서 어떤 출력의 일부를 얼마나 큰 상관없이 .

이제 서버가 CPRNG데크를 생성 하는 데 사용한다고 가정 해 봅시다 . 256 비트 시드가 필요합니다. 그 씨앗을 어떻게 선택합니까? 공격자가 예측할 수있는 값을 선택하면 갑자기 공격이 다시 실행됩니다 . 우리는 2 개의 확인할 수있는 경우 256 가능한 씨앗을 만 사십억 그들의 서버에 의해 선택 될 가능성이 후, 우리는 다시 사업에 있습니다 . 우리는이 공격을 다시 시작할 수 있으며, 생성 될 수있는 적은 수의 씨앗에만주의를 기울입니다.

따라서 서버는 256 비트 숫자가 균일하게 분배 되도록해야합니다. 즉, 가능한 모든 시드가 1/2 256의 확률로 선택됩니다 . 기본적으로 서버는에 TRNG(2^256)-1대한 시드를 생성하기 위해 호출해야합니다 CPRNG.

서버를 해킹하고 피어링하여 어떤 시드가 선택되었는지 확인할 수 있습니까? 이 경우 공격자는 CPRNG의 완전한 과거와 미래를 알고 있습니다. 서버 작성자는이 공격을 막아야합니다! (물론이 공격을 성공적으로 수행 할 수 있다면 돈을 은행 계좌로 직접 이체 할 수도 있습니다. 그래서 그다지 흥미롭지 않을 수도 있습니다. 요점은 씨앗은 추측하기 어려운 비밀이어야합니다. 실제로 임의의 256 비트 숫자는 추측하기가 어렵습니다.)

심층 방어에 대한 이전 시점으로 돌아 가면 256 비트 시드 가이 보안 시스템 의 핵심 입니다. CPRNG의 개념은 키가 안전한 한 시스템이 안전하다는 것입니다 . 알고리즘에 대한 다른 모든 사실을 알고 있더라도 키를 비밀로 유지할 수있는 한 상대방의 카드는 예측할 수 없습니다.

시드는 비밀이 유지되고 균일하게 분산되어 있어야합니다. 그렇지 않은 경우 공격을 수행 할 수 있기 때문입니다. 우리는 산출물의 분포 CPRNG(n)가 균일 하다고 가정합니다 . 가능한 모든 데크 세트에 대한 분포는 어떻습니까?

2있다 : 당신은 말할 수 256 CPRNG에 의해 가능한 시퀀스 출력, 만 2가 226 가능한 데크. 따라서 데크보다 시퀀스가 ​​더 많으므로 괜찮습니다. 가능한 모든 IRC 데크는 이제이 시스템에서 (높은 확률로) 가능합니다. 그리고 그것은 좋은 주장입니다 …

2 226 은 52! 의 근사값 입니다. 나누십시오. (2) 256 / 52! 한 가지 때문에 52가 될 수 있습니다. 3으로 나눌 수 있지만 2의 거듭 제곱은 없습니다! 이것은 정수가 아니기 때문에 모든 데크가 가능한 상황 이지만 일부 데크는 다른 데크보다 가능성이 높습니다 .

확실하지 않으면 숫자가 작은 상황을 고려하십시오. 세 개의 카드 A, B 및 C가 있다고 가정합니다. 8 비트 시드가있는 PRNG를 사용하여 256 개의 가능한 시드가 있다고 가정하십시오. PRNG(3)시드 에 따라 256 개의 가능한 출력이 있습니다 . 256을 3으로 균등하게 나눌 수 없기 때문에 1/3을 A로, 1/3을 B로, 1/3을 C로하는 방법은 없습니다.

마찬가지로 52는 2 256 으로 균등하게 분할되지 않으므로 선택한 첫 번째 카드로 일부 카드에 대한 편향과 다른 카드와의 편향이 있어야합니다.

32 비트 시드가있는 원래 시스템에는 엄청난 편향이 있었고 가능한 대부분의 데크는 생산되지 않았습니다. 이 시스템에서는 모든 데크를 생산할 수 있지만 데크 분배에는 여전히 결함이 있습니다. 일부 데크는 다른 데크 보다 약간 더 높습니다.

이제 문제는 : 이 결함에 기반한 공격이 있습니까? 대답은 실제로는 아닐 것입니다 . CPRNG는 시드가 실제로 무작위 인 경우 와와 의 차이를 계산하는 것이 계산적으로 불가능 하도록 설계되었습니다 .CPRNGTRNG

자, 요약하자.

의사 난수와 실제 난수는 어떻게 다릅니 까?

그것들은 그들이 보여주는 예측 수준이 다릅니다.

  • 진정한 난수는 예측할 수 없습니다.
  • 시드를 결정하거나 추측 할 수 있으면 모든 의사 난수를 예측할 수 있습니다.

차이점이 왜 중요한가요?

시스템의 보안이 예측할 수없는 응용 프로그램이 있기 때문에 .

  • TRNG를 사용하여 각 카드를 선택하면 시스템을 사용할 수 없습니다.
  • CPRNG를 사용하여 각 카드를 선택하는 경우 시드를 예측할 수없고 알 수없는 경우 시스템이 안전합니다.
  • 시드 공간이 작은 일반 PRNG를 사용하면 시드를 예측할 수 없는지 또는 알 수 없는지에 관계없이 시스템이 안전하지 않습니다. 작은 종자 공간은 내가 설명한 종류의 무차별 대입 공격에 취약합니다.

차이는 PRNG의 출력 분포와 관련이 있습니까?

개별 호출 에 대한 분배의 균일 성 또는 부족 RNG(n)은 내가 설명한 공격과 관련이 없습니다.

우리가 살펴본 바와 같이, a PRNGCPRNG가능한 모든 데크의 개별 데크를 선택할 확률이 낮게 분포되어있다. 은 PRNG상당히 나쁘다, 그러나 둘 다 문제가있다.

질문 하나 더 :

TRNG가 CPRNG보다 훨씬 낫고 PRNG보다 훨씬 낫다면 왜 CPRNG 나 PRNG를 사용합니까?

두 가지 이유가 있습니다.

첫째 : 비용. TRNG는 비싸다 . 진정한 난수 생성은 어렵습니다. CPRNG 는 시드에 대해 TRNG를 번만 호출하면 임의로 많은 호출에 대해 좋은 결과를 제공 합니다. 단점은 물론 그 씨앗을 비밀로 유지해야한다는 것입니다 .

둘째 : 때때로 우리 예측 성을 원하며 우리가 관심을 갖는 것은 좋은 분포입니다. 테스트 스위트의 프로그램 입력으로 “임의의”데이터를 생성하고 버그가 표시되면 테스트 스위트를 다시 실행하면 버그가 다시 생성된다는 것이 좋을 것입니다!

나는 그것이 훨씬 더 명확 해지기를 바랍니다.

마지막으로, 이것을 즐겼다면 무작위와 순열에 관한 추가 내용을 읽을 수 있습니다.


답변

에릭 리퍼 트 ​​(Eric Lippert)가 말했듯이 그것은 단지 배포가 아닙니다. 임의성을 측정하는 다른 방법이 있습니다.

초기 난수 생성기 중 하나는 최하위 비트의 시퀀스를 갖습니다. 0과 1이 교대로 나타납니다. 따라서 LSB는 100 % 예측 가능했습니다. 그러나 그 이상을 걱정해야합니다. 각 비트는 예측할 수 없어야합니다.

여기에 문제를 생각하는 좋은 방법이 있습니다. 64 비트의 임의성을 생성한다고 가정 해 봅시다. 각 결과에 대해 처음 32 비트 (A)와 마지막 32 비트 (B)를 가져 와서 배열 x [A, B]에 색인을 만듭니다. 이제 테스트를 백만 번 수행하고 각 결과에 대해 해당 수에서 배열을 증가시킵니다 (예 : X [A, B] ++;

이제 2D 다이어그램을 그리십시오. 숫자가 클수록 해당 위치의 픽셀이 더 밝아집니다.

실제로 무작위이면 색상이 균일 한 회색이어야합니다. 그러나 패턴을 얻을 수 있습니다. 예를 들어 Windows NT 시스템의 TCP 시퀀스 번호에서 “랜덤 성”에 대한이 다이어그램을 보자.

윈도우 NT

또는 Windows 98의 이것조차도 :

윈도우 98

Cisco 라우터 (IOS) 구현의 임의성은 다음과 같습니다.
시스코 ISO

이 도표는 Michał Zalewski의 논문에서 제공 한 것 입니다. 이 특별한 경우, 시스템의 TCP 시퀀스 번호를 예측할 수 있다면 다른 시스템에 연결할 때 해당 시스템을 가장하여 연결의 도용, 통신 차단 등을 허용 할 수 있습니다. 시간의 다음 숫자를 100 % 예측할 수 없습니다. 제어하에 새로운 연결을 만들 수 있다면 성공 가능성을 높일 수 있습니다. 그리고 몇 초 안에 컴퓨터가 10 만 개의 연결을 생성 할 수있을 때, 성공적인 공격의 가능성은 천문학적이거나 가능하거나 가능성이 있습니다.


답변

컴퓨터에 의해 생성 된 의사 난수는 컴퓨터 사용자가 겪는 대부분의 유스 케이스에 허용되지만 완전히 예측할 수없는 난수 가 필요한 시나리오가 있습니다.

암호화와 같은 보안에 민감한 애플리케이션에서 PRNG (pseudorandom number generator)는 실제로는 모양이 무작위이지만 침입자가 실제로 예측할 수있는 값을 생성 할 수 있습니다. PRNG가 사용되고 공격자가 PRNG 상태에 대한 정보를 가지고있는 경우 암호화 시스템을 해독하려는 누군가가 암호화 키를 추측 할 수 있습니다. 따라서, 이러한 응용을 위해서는 진정으로 추측 할 수없는 값을 생성하는 난수 생성기가 필요합니다. 참고 일부 PRNG는이 안전한 암호화하도록 설계 및 보안에 민감한 애플리케이션에 사용할 수 있습니다.

RNG 공격에 대한 자세한 내용은 이 Wikipedia 기사를 참조하십시오 .


답변

나는 파이썬으로 시도했다 : 6 천만 롤의 결과는 다음과 같다. 가장 높은 변형은 0.15와 같습니다. 그것이 얻는 것만 큼 무작위 적이 지 않습니까?

실제로, 그것은 “좋다”는 나쁘다 … 기존의 모든 대답 은 작은 초기 값 시퀀스가 ​​주어지면 예측 가능성에 중점을 둡니다 . 다른 문제를 제기하고 싶습니다.

    당신의 분포는 임의 롤보다 훨씬 작은 표준 편차를 가지고해야

진정한 무작위성은 아주 오지 않는 것을 당신이 품질의 표시로 사용하고 있는지 “거의 정확히 1이 선택할 수있는 방법을 지금까지 많은 숫자를 통해”평균 부근에 있습니다.

여러 주사위 롤의 확률 분포에 대한이 스택 교환 질문 을 보면 N 주사위 롤의 표준 편차에 대한 공식이 표시됩니다 (진정한 무작위 결과 가정).

 sqrt(N * 35.0 / 12.0).

이 공식을 사용하여 다음에 대한 표준 편차 :

  • 1 백만 롤은 1708입니다
  • 6 천만 롤은 13229입니다

결과를 보면 :

  • 백만 롤 : stddev (1000066, 999666, 1001523, 999452, 999294, 999999)는 804
  • 6 천만 롤 : stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398)는 3827입니다.

유한 샘플의 표준 편차가 공식과 정확히 일치 할 것으로 기대할 수는 없지만 상당히 가깝습니다. 그러나 1 백만 롤에서 당신은 적절한 stddev의 절반보다 적었고, 6 천만 명이 3 분의 1에 못 미쳤습니다.

Pseudo-RNG는 시드로 시작하여 특정 기간 동안 원래 번호를 다시 방문하지 않는 일련의 고유 번호를 통해 이동하는 경향이 있습니다. 예를 들어, 이전 C 라이브러리 rand()함수 의 구현은 일반적으로주기가 2 ^ 32이며 시드를 반복하기 전에 0에서 2 ^ 32-1 사이의 모든 숫자를 정확히 한 번 방문합니다. 따라서 2 ^ 32 주사위 롤을 시뮬레이트하면 사전 모듈러스 (%) 결과에는 0에서 2 ^ 32까지의 각 숫자, 각 1-6 결과에 대한 개수는 715827883 또는 715827882 (2 ^ 32는 6의 배수가 아님)이며 표준 편차는 0보다 약간 높습니다. 위의 공식에서 2 ^ 32 롤에 대한 올바른 표준 편차는 111924입니다. 어쨌든 의사 랜덤 롤의 수가 증가함에 따라 0 표준 편차로 수렴합니다. 롤 수가 기간의 상당 부분 인 경우이 문제가 중요 할 것으로 예상 될 수 있지만 일부 유사 RNG는 다른 유사성보다 더 나쁜 문제 또는 적은 수의 샘플로 문제가 발생할 수 있습니다.

따라서 암호화 취약점에 신경 쓰지 않아도 일부 응용 프로그램에서는 지나치게 인위적으로 결과가없는 배포가 필요할 수도 있습니다. 일부 유형의 시뮬레이션은 개별적으로 임의의 결과가 많은 샘플에서 자연적으로 발생 하는 고르지 않은 결과 의 결과를 해결하기 위해 노력하고 있지만 일부 pRNG의 결과에서는 과소 평가됩니다. 많은 인구가 어떤 사건에 반응하는 방식을 시뮬레이션하려는 경우이 문제로 인해 결과 가 크게 변경되어 결과가 크게 부정확 해질 수 있습니다.


구체적인 예를 들자면, 수학자가 포커 머신 프로그래머에게 6 천만 번의 시뮬레이션 된 롤 후-10,013,229 개 이상의 식스가 6 개가있는 경우 스크린 주위에 수백 개의 작은 “조명”을 깜박 거리는 데 사용한다고 수학자는 평균에서 1 stddev 떨어진 곳에는 약간의 지불금이 있어야합니다. 68–95–99.7 규칙 (Wikipedia)에 따르면, 이는 시간의 약 16 % (표준 편차 내에 ~ 68 %가 넘어 가고 절반 밖에 안 됨)입니다. 난수 생성기를 사용하면 평균보다 약 3.5 표준 편차가 있습니다. 0.025 % 미만의 확률 –이 혜택을받는 고객은 거의 없습니다. 방금 언급 한 페이지의 더 높은 편차 표, 특히 다음을 참조하십시오.

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |


답변

방금 주사위 롤을 생성하기 위해이 난수 생성기를 썼습니다

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

당신은 이것을 이렇게 사용합니다

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

등. 주사위 게임을 실행 한 프로그램에이 생성기를 사용하겠습니까? 분포는 “정확한 무작위”생성기에서 기대하는 것과 정확히 일치합니다!

의사 난수 생성기는 본질적으로 동일한 작업을 수행합니다. 정확한 분포로 예측 가능한 숫자를 생성합니다. 위의 단순한 난수 생성기가 나쁘다는 이유로 같은 이유로 나쁩니다. 정확한 분포뿐만 아니라 예측할 수없는 상황에 적합하지 않습니다.


답변

컴퓨터가 수행 할 수있는 난수 생성은 대부분의 요구에 적합하며, 실제로 난수를 필요로하는 시간에는 오지 않을 것입니다.

진정한 난수 생성에는 그 목적이 있습니다. 컴퓨터 보안, 도박, 대규모 통계 샘플링 등

난수 응용에 관심이 있으시면 Wikipedia 기사를 확인 하십시오 .


답변

대부분의 프로그래밍 언어에서 일반적인 기능으로 생성 된 난수는 순수한 난수가 아닙니다. 그들은 의사 난수입니다. 그것들은 순전히 난수가 아니기 때문에 이전에 생성 된 숫자에 대한 충분한 정보로 추측 할 수 있습니다. 따라서 이것은 암호화 보안재앙 이 될 것 입니다.

예를 들어, 다음에 사용되는 다음 난수 생성기 함수 glibc는 순수한 난수를 생성하지 않습니다. 이것에 의해 생성 된 의사 난수를 추측 할 수 있습니다. 보안 문제에 대한 실수입니다. 이 비참한 역사가 있습니다. 암호화에는 사용하지 않아야합니다.

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

이 유형의 유사 난수 생성기는 통계적으로 훨씬 중요하더라도 보안에 민감한 장소에서 절대 사용해서는 안됩니다.

의사 난수 키에 대한 유명한 공격 중 하나는 802.11b WEP에 대한 공격입니다 . WEP에는 24 비트 IV (카운터)와 연결되어 128 비트 키를 만드는 104 비트 장기 키가 있으며, 이는 의사 난수 키를 생성 하기 위해 RC4 알고리즘 에 적용됩니다 .

( RC4( IV + Key ) ) XOR (message)

열쇠는 서로 밀접한 관련이있었습니다. 여기서는 각 단계에서 IV 만 1 씩 증가했으며 다른 모든 단계는 동일하게 유지되었습니다. 이것은 순전히 무작위가 아니기 때문에 재앙이었고 쉽게 무너졌습니다. 키는 약 40000 프레임을 분석하여 복구 할 수 있는데, 이는 몇 분의 문제입니다. WEP가 순전히 임의의 24 비트 IV를 사용한 경우 약 2 ^ 24 (약 1680 만) 프레임까지 안전 할 수 있습니다.

따라서 가능한 경우 보안에 민감한 문제에서 순수한 난수 생성기를 사용해야합니다.