진정한 난수 생성기 [닫기]

https://stackoverflow.com/questions/37702

09-06-2019
|

문제

이것이 "실제" 질문이 아니어서 죄송합니다. 하지만 언젠가 여기에서 의사 난수가 아닌 진정한 난수를 생성하기 위해 무작위로 난수를 무작위화하는 방법에 대한 게시물을 본 기억이 납니다.검색해봐도 안보이네요.

그 기사에 대해 아는 사람 있나요?

해결책

그 일이 있었을 거라 믿어요 thedailywtf.com - 즉.하고 싶은 일이 아닙니다.

Randomize()를 몇 번 호출하더라도 의사 난수에서 진정한 난수를 얻는 것은 불가능합니다.

너 ~할 수 있다 특수 항목에서 "진정한" 난수를 얻습니다. 하드웨어.마우스 움직임 등으로부터 엔트로피를 수집할 수도 있습니다.

다른 팁

나는 이 질문에 대한 많은 답변에 동의하지 않습니다.

컴퓨터에서 무작위로 데이터를 수집하는 것이 가능합니다.SSL, SSH 및 VPN은 안전하지 않으면 안전하지 않습니다.

소프트웨어 난수 생성기가 작동하는 방식은 다음과 같습니다. 수영장 클럭 드리프트, 인터럽트 타이밍 등과 같은 다양한 장소에서 수집된 무작위 데이터입니다.

이러한 계획의 비결은 엔트로피 (무작위성에 대한 고급 이름).엔트로피를 올바르게 추정하는 한 소스가 편향인지 여부는 중요하지 않습니다.

이를 설명하기 위해 내가 편지를 치는 기회는 이자형 이 댓글은 의 것보다 훨씬 높습니다. 지 따라서 키 인터럽트를 엔트로피의 소스로 사용한다면 편향이 될 것입니다. 하지만 해당 입력에는 여전히 임의성이 있습니다.이 단락에서 다음에 어떤 문자 순서가 나올지 정확히 예측할 수는 없습니다.이 불확실성에서 엔트로피를 추출하여 임의 바이트의 일부로 사용할 수 있습니다.

다음과 같은 좋은 품질의 실제 난수 생성기 톱풀 매우 정교한 엔트로피 추정 기능이 내장되어 있으며 "무작위성 풀"에 있다고 확실하게 말할 수 있는 만큼만 바이트를 방출합니다.

게시물 끝에서 "더 많은 무작위성"을 위해 여러 개의 난수 생성기를 사용하려는 이유에 대한 질문에 답변하겠습니다.

무작위성이 무엇을 의미하는지에 대한 철학적 논쟁이 있습니다.여기서는 "추출된 샘플에 대한 균일한(0,1) iid 분포와 모든 측면에서 구별할 수 없음"을 의미합니다. 나는 무작위가 무엇인지에 대한 철학적 질문을 완전히 무시하고 있습니다.

Knuth 2권에는 귀하가 제안한 대로 난수 생성기를 생성하려고 시도한 다음 그것이 실패한 이유와 진정한 무작위 프로세스가 무엇인지 분석하는 분석이 있습니다.2권에서는 RNG를 자세히 살펴봅니다.

다른 사람들은 임의의 물리적 프로세스를 사용하여 난수를 생성할 것을 권장합니다.그러나 Espo/vt 상호 작용에서 볼 수 있듯이 이러한 프로세스에는 부분적으로 결정론적 동작을 갖는 외부 요인으로 인해 미묘한 주기 요소와 기타 비 무작위 요소가 있을 수 있습니다.일반적으로 임의성을 가정하지 않고 항상 테스트하는 것이 가장 좋으며 일반적으로 이러한 아티팩트를 알고 있는 경우 이를 수정할 수 있습니다.

결정론적으로 완전히 무작위로 나타나는 "무한" 비트 스트림을 생성하는 것이 가능합니다.불행하게도 이러한 접근 방식은 요청된 비트 수에 따라 메모리에서 증가하므로(반복 주기를 피하기 위해 그래야 함) 범위가 제한됩니다.

실제로는 알려진 속성을 가진 의사 난수 생성기를 사용하는 것이 거의 항상 더 좋습니다.찾아야 할 핵심 숫자는 위상 공간 차원(균등하게 분포되어 있다고 믿을 수 있는 샘플 간의 대략적인 오프셋)과 비트 폭(서로에 대해 균일하게 무작위인 각 샘플의 비트 수)입니다. ) 및 주기 크기(분포가 반복되기 전에 취할 수 있는 샘플 수)입니다.

그러나 특정 생성기의 난수는 결정론적으로 알려진 시퀀스이므로 누군가 생성기를 검색하고 정렬 시퀀스를 찾는 경우 절차가 노출될 수 있습니다.따라서 두 개의 생성기를 유지 관리하면 분포가 특정 난수 생성기에서 나온 것으로 즉시 인식되는 것을 방지할 수 있습니다.처음부터 i를 샘플링한 다음 이를 1에서 n으로 균일하게 매핑합니다. 여기서 n은 기껏해야 위상 차원입니다.그런 다음 두 번째에서는 i번 샘플링하고 i번째 결과를 반환합니다.이렇게 하면 최악의 경우 주기 크기가 (원래 주기 크기/n)로 줄어들지만, 해당 주기의 경우 여전히 균일한 난수를 생성하고 n에서 정렬 검색을 기하급수적으로 만드는 방식으로 그렇게 합니다.또한 독립 위상 길이도 줄어듭니다.감소된 주기와 독립 위상 길이가 애플리케이션에 어떤 의미인지 이해하지 못한다면 이 방법을 사용하지 마십시오.

진정한 난수에 대한 알고리즘은 다음과 같이 존재할 수 없습니다. 정의 난수는 다음과 같습니다.

예측할 수 없는 결과를 낳고, 이상적인 경우, 모든 결과가 동등하게 가능성이;이러한 결과 선택;통계 부족 상관.

더 좋거나 나쁜 PRNG(의사 난수 생성기)가 있습니다.완전히 예측 가능한 숫자의 시퀀스로, 정보를 모르면 예측하기 어렵습니다. 씨앗.

이제 시드를 추론하기가 극도로 어려운 PRNG는 다음과 같습니다. 암호학적으로 안전함.그것이 당신이 원하는 것이라면 Google에서 찾아보고 싶을 수도 있습니다.

또 다른 방법(이것이 정말로 무작위인지 아닌지는 철학적인 질문입니다)은 무작위 데이터 소스를 사용하는 것입니다.예를 들어 소음이나 방사성 붕괴 측정과 같은 예측할 수 없는 물리적 양이 있습니다.

이러한 것들은 독립적으로 측정될 수 있고 편견이 있기 때문에 여전히 공격을 받기 쉽습니다.그래서 정말 까다롭습니다.이는 일반적으로 상당히 비싼 맞춤형 하드웨어를 사용하여 수행됩니다.얼마나 좋은지 전혀 모르겠어 /dev/random 그러나 나는 이것이 암호화에 충분하지 않다고 확신합니다(대부분의 암호화 프로그램은 자체 RNG와 함께 제공되며 Linux도 시작 시 하드웨어 RNG를 찾습니다).

위키피디아에 따르면 /dev/random, 는 Unix 계열 운영 체제에서 진정한 난수 생성기 역할을 하는 특수 파일입니다.

/dev/random 드라이버는 운영 체제 환경 내에서 발생하는 키보드 간 타이밍 및 인터럽트 간 타이밍을 포함하되 이에 국한되지 않는 다양한 비결정적 소스로부터 환경 소음을 수집합니다.노이즈 데이터는 샘플링되어 CRC와 같은 혼합 기능과 결합되어 지속적으로 업데이트되는 "엔트로피 풀"로 만들어집니다.이 풀 내용의 MD5 해시를 사용하여 무작위 비트 문자열을 얻습니다.단방향 해시 기능은 풀 데이터에서 실제 무작위 비트를 추출하고 풀 상태를 적으로부터 숨깁니다.

/dev/random 루틴은 풀의 실제 무작위성에 대한 추정치를 유지하고 무작위 문자열 사용이 요청될 때마다 이를 감소시킵니다.추정치가 0으로 떨어지면 루틴은 잠기고 비결정적 이벤트가 발생하여 풀을 새로 고칠 때까지 기다립니다.

/dev/random 커널 모듈은 엔트로피 풀이 재충전될 때까지 기다리지 않고 요청한 만큼의 바이트를 반환하는 또 다른 인터페이스인 /dev/urandom도 제공합니다.결과적으로 /dev/urandom은 매우 높은 품질의 무작위성이 필요할 때만 사용되는 /dev/random에 비해 생성 속도가 상당히 빠릅니다.

존 폰 노이만(John von Neumann)은 "알고리즘 수단을 통해 난수를 생성하려는 사람은 누구나 물론 죄 가운데 살고 있는 것"이라는 취지로 말한 적이 있습니다.

수학자나 물리학자의 관점에서는 /dev/random도 무작위가 아닙니다.방사성 동위원소 붕괴 측정도 무작위가 아닙니다.(부패율은.측정값은 그렇지 않습니다.가이거 계수기는 각 이벤트가 감지된 후 약간의 재설정 시간이 있으며, 이 시간 동안에는 새로운 이벤트를 감지할 수 없습니다.이는 미묘한 편견으로 이어집니다.이를 실질적으로 완화할 수 있는 방법이 있지만 완전히 제거할 수는 없습니다.)

진정한 무작위성을 찾지 마세요.좋은 의사 난수 생성기는 실제로 당신이 찾고 있는 것입니다.

결정론적인 우주를 믿는다면 진정한 무작위성은 존재하지 않습니다.:-) 예를 들어, 누군가 방사성 붕괴가 다음과 같다고 제안했습니다. 진심으로 무작위적이지만 IMHO는 과학자들이 아직 패턴을 해결하지 못했다고 해서 해결해야 할 패턴이 없다는 의미는 아닙니다.일반적으로 "무작위" 숫자를 원할 때 필요한 것은 다른 누구도 추측할 수 없는 암호화용 숫자입니다.

무작위로 얻을 수 있는 가장 가까운 방법은 어떤 적도 측정할 수 없는 자연스러운 것을 측정하는 것입니다.일반적으로 측정에서 가장 중요한 비트를 버리고 숫자가 균등하게 퍼질 가능성이 더 높습니다.하드 코어 난수 사용자는 방사능 이벤트를 측정하는 특수 하드웨어를 얻지만 키 누르기 간격 및 마우스 움직임과 같은 것에서 컴퓨터를 사용하는 사람으로부터 그리고 컴퓨터에 직접 사용자가 없는 경우 CPU 온도 센서에서 임의성을 얻을 수 있습니다. 그리고 네트워크 트래픽에서.웹 캠이나 사운드 카드에 연결된 마이크 등을 사용할 수도 있지만, 그런 사람이 있는지는 모르겠습니다.

지금까지 말한 내용 중 일부를 요약하면 안전한 임의성 소스에 대한 실제 정의는 암호화 보안에 대한 정의와 유사합니다.똑똑한 사람들이 그것을 살펴보고 그것이 완전히 예측할 수 없는 것이 아니라는 것을 보여줄 수 없다면 그것은 무작위로 보입니다.

있다 아니요 해독할 수 없는 암호화 암호가 없는 것처럼 예측할 수 없는 난수를 생성하는 시스템입니다.중요한 작업에 사용되는 신뢰할 수 있는 솔루션은 지금까지 패배하기 어려운 솔루션일 뿐입니다.누군가가 당신에게 다르게 말한다면, 그들은 당신에게 무언가를 파는 것입니다.

영리함은 암호화에서 거의 보상되지 않습니다.검증된 진정한 솔루션을 사용하세요.

컴퓨터에는 일반적으로 쉽게 사용할 수 있는 무작위 노이즈의 물리적 소스가 많이 있습니다.

마이크(시끄러운 곳에서 사용하시길 바랍니다)
웹캠의 압축 비디오(라바 램프나 거리 등 가변적인 대상을 가리킴)
키보드 및 마우스 타이밍
네트워크 패킷 내용 및 타이밍(전 세계가 기여)

그리고 때때로

클록 드리프트 기반 하드웨어
가이거 계수기 및 기타 희귀 사건 감지기
A/D 변환기에 부착된 각종 센서

어려운 점은 이러한 소스의 엔트로피를 추정하는 것인데, 이는 높은 데이터 속도와 매우 가변적임에도 불구하고 대부분의 경우 낮습니다.그러나 엔트로피는 Yarrow 또는 Fortuna와 같은 공급 시스템에 대해 보수적인 가정을 사용하여 추정하거나 적어도 낭비되지 않을 수 있습니다.

'진정한' 난수를 얻는 것은 불가능합니다. 컴퓨터는 '진정한' 난수를 생성할 수 없고 오직 의사 난수만 생성할 수 있는 논리적 구조입니다.그러나 더 좋고 더 나쁜 의사 무작위 알고리즘이 있습니다.

'진정한' 난수를 얻으려면 물리적인 난수 소스가 필요합니다. 일부 도박 기계에는 실제로 이러한 소스가 내장되어 있습니다. 종종 방사성 소스, 방사성 붕괴(내가 아는 한 진심으로 무작위)는 숫자를 생성하는 데 사용됩니다.

난수를 생성하는 가장 좋은 방법 중 하나는 시계 드리프트.이것은 주로 두 개의 발진기와 함께 작동합니다.

이것이 어떻게 작동하는지에 대한 비유는 랩 시작 부분에 잠시 선이 있고 타이어 중 하나에 잠시 선이 있는 단순한 타원형 서킷의 경주용 자동차를 상상하는 것입니다.자동차가 랩을 완료하면 도로 위의 흰색 선과 타이어 위의 흰색 선 위치의 차이를 기반으로 숫자가 생성됩니다.

생성하기가 매우 쉽고 예측이 불가능합니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow