의사 난수 생성기

의사난수발생기(PRNG)는 결정론적 랜덤비트발생기(DRBG)^[1]라고도 불리며, 그 특성이 난수열 속성에 가까운 일련의 숫자를 생성하기 위한 알고리즘입니다.PRNG가 생성한 시퀀스는 PRNG의 시드(진정한 랜덤 값을 포함할 수 있음)라고 하는 초기 값에 의해 완전히 결정되기 때문에 실제로는 랜덤하지 않다.하드웨어 난수 생성기를 사용하여 진정한 난수에 가까운 시퀀스를 생성할 수 있지만 의사 난수 생성기는 번호 생성 속도와 재현성을 ^[2]위해 실제로 중요합니다.

PRNG는 시뮬레이션(예: 몬테카를로 방법의 경우), 전자 게임(예: 절차 생성의 경우) 및 암호학과 같은 애플리케이션에서 중심적이다.암호화 애플리케이션에서는 이전 출력에서 출력을 예측할 수 없는 것이 요구되며, 보다 단순한 PRNG의 선형성을 계승하지 않는 보다 정교한 알고리즘이 필요합니다.

양호한 통계 특성은 PRNG의 출력에 대한 핵심 요건이다. 일반적으로 PRNG가 의도한 용도에 적합하도록 랜덤에 충분히 가까운 수치를 생성한다는 확신을 갖기 위해서는 신중한 수학적 분석이 필요하다.John von Neumann은 PRNG가 정말로 랜덤한 발생기로 잘못 해석되는 것에 대해 경고하고, "랜덤 자릿수를 생성하는 산술적 방법을 고려하는 사람은, 물론,^[3] 죄의 상태에 있는 것입니다."라고 농담을 했다.

잠재적인 문제

실제로 많은 일반적인 PRNG의 출력은 통계 패턴 검출 테스트에 실패하는 아티팩트를 나타냅니다.여기에는 다음이 포함됩니다.

일부 시드 상태의 경우 예상보다 짧은 기간(이 문맥에서는 이러한 시드 상태를 "weak"라고 부를 수 있음)
대량의 생성된 숫자에 대한 분포의 균일성 결여
연속값의 상관관계
출력 시퀀스의 치수 분포가 불량합니다.
특정 값이 발생하는 간격은 랜덤 시퀀스 분포와 다르게 분포됩니다.

결함이 있는 PRNG에 의해 나타나는 결함은 눈에 띄지 않는 것(그리고 알려지지 않은 것)에서 매우 명백한 것까지 다양합니다.예를 들어 메인프레임 컴퓨터에서 수십 년 동안 사용된 LANDU 난수 알고리즘이 그 예입니다.그것은 심각한 결함이 있었지만, 그것의 부족함은 오랫동안 감지되지 않았다.

많은 분야에서, 무작위 선택이나 몬테카를로 시뮬레이션, 또는 다른 방식으로 PRNG에 의존하는 21세기 이전의 연구 작업은 낮은 ^[4]품질의 PRNG를 사용한 결과로서 이상보다 신뢰성이 훨씬 낮았다.국제통계과학대백과사전(2010)^[5]에서 다음과 같이 경고한 바와 같이 오늘날에도 주의가 요구되기도 한다.

폐기해야 할 널리 사용되는 발전기 목록은 [우량 발전기 목록]보다 훨씬 길다.소프트웨어 벤더를 맹목적으로 신뢰하지 마십시오.마음에 드는 소프트웨어의 디폴트 RNG를 체크하고, 필요에 따라서 교환할 수 있습니다.이 마지막 권고는 지난 40년 동안 계속해서 이루어졌다.아마도 놀랍게도, 그것은 40년 전과 마찬가지로 오늘날에도 관련이 있다.

예시로 널리 사용되는 프로그래밍 언어 Java를 생각해 보십시오.2017년 현재^[update], Java는 낮은 품질의 PRNG를 ^[6]^[7]위해 여전히 Linear Congruential Generator(LCG)에 의존하고 있습니다.

주요 문제를 피하고 여전히 빠르게 작동하는 것으로 잘 알려진 PRNG 중 하나는 1998년에 출판된 Mersenne Twister입니다.계산 및 통계 성능 측면에서 다른 고품질 PRNG는 이 날짜 이전과 이후에 개발되었으며, 의사 난수 발생기 목록에서 확인할 수 있다.

선형 반복을 기반으로 하는 생성자

20세기 후반에는 PRNG에 사용되는 알고리즘의 표준 클래스가 선형 합동 생성기로 구성되었다.LCG의 품질은 불충분하다고 알려져 있었지만 더 나은 방법은 없었습니다.외를 누릅니다.(2007)는 그 결과를 다음과 같이 기술했다. "[LCGs 및 관련]로 인해 결과가 의심스러운 모든 과학 논문이 도서관 선반에서 사라지면 각 선반에 ^[8]주먹만한 틈이 생길 것이다."

의사 난수 발생기 구축의 주요 진보는 2-요소 필드에서의 선형 반복에 기초한 기술의 도입이었다. 이러한 발생기는 선형 피드백 시프트 레지스터와 관련이 있다.

특히 1997년 메르센 트위스터의 ^[9]발명은 초기 발전기의 많은 문제를 피했다.Mersenne Twister는 2-1회^{19 937} 반복 주기(θ4.3×10⁶⁰⁰¹)를 가지며, 도입 당시 통계적으로 합리적인 다른 발전기보다 더 빠르게 작동하고 있었다.

2003년 조지 마르사글리아는 다시 선형 재발을 기반으로 Xorsshift 발전기 ^[10]패밀리를 도입했습니다.이러한 발전기는 매우 빠르고 비선형 작동과 결합되어 강력한 통계 테스트를 ^[11]^[12]^[13]통과합니다.

2006년에는 WELL 발전기 패밀리가 ^[14]개발되었습니다.WELL 생성기는 어떤 면에서 Mersenne Twister의 품질을 향상시킵니다. Mersenne Twister는 상태 공간이 너무 크고 많은 수의 0이 있는 상태 공간으로부터의 복구 속도가 매우 느립니다.

암호화 PRNG

암호화 애플리케이션에 적합한 PRNG는 암호화 보안 PRNG(CSPRNG)라고 불립니다.CSPRNG의 요건은 시드를 모르는 상대방이 제너레이터의 출력 시퀀스와 랜덤시퀀스를 구별하는 데 있어서 무시할 수 있는 이점밖에 없다는 것이다.즉, PRNG는 특정 통계 테스트만 통과해야 하지만 CSPRNG는 시드 크기의 다항 시간으로 제한된 모든 통계 테스트를 통과해야 합니다.이 성질에 대한 증거는 계산 복잡도 이론의 현재 기술 상태를 벗어나지만, 정수 ^[15]인수분해와 같은 어려운 문제로 CSPRNG를 줄임으로써 강력한 증거를 제공할 수 있다.일반적으로 알고리즘을 CSPRNG로 인증하기 전에 수년간의 검토가 필요할 수 있습니다.

CSPRNG의 클래스에는 다음과 같은 것이 있습니다.

스트림 암호
카운터 또는 출력 피드백 모드에서 실행되는^[16] 블록 암호
Microsoft의 Cryptographic Application Programming Interface 함수 CryptGenRandom, Yarrow 알고리즘(Mac OS X 및 FreeB에 통합됨)과 같이 암호학적으로 안전하도록 특별히 설계된 PRNGSD) 및 Fortuna
검출 가능한 비랜덤성을 제거하기 위해 여러 PRNG 원시 알고리즘을 결합하는 조합 PRNG
수학적 경도 가정에 기초한 특수 설계: 강력한 보안 증명을 제공하는 Micali-Schnorr 발생기,^[17] Naor-Reingold 의사 난수 및 Blum Blum Shub 알고리즘이 포함된다(이러한 알고리즘은 기존 구조에 비해 다소 느리고 많은 애플리케이션에 실용적이지 않음).
범용 PRNG: (암호학적으로) 안전한 PRNG는 단방향 ^[18]함수에 관계없이 범용적으로 구축될 수 있는 것으로 나타났지만, 이 범용 구조는 실제로 매우 느리기 때문에 주로 이론적인 관심이 있습니다.

NSA가 NIST 인증 의사난수 생성기 Dual_에 비대칭 백도어를 삽입한 것으로 나타났습니다.EC_DRBG^[19]

대부분의 PRNG 알고리즘은 몇 가지 테스트 중 하나에 의해 균등하게 분포된 시퀀스를 생성합니다.고품질 PRNG의 출력과 정말로 랜덤한 시퀀스를 구별할 수 있는 방법이 있는지 여부는 암호학의 이론과 실천의 중심이며 열린 질문입니다.이 설정에서는 이미 알려진 PRNG 알고리즘(초기화 상태에서는 사용되지 않음) 또는 진정한 랜덤알고리즘이 사용되었음을 식별자는 인식하고 있으며,^[20] 이 둘을 구별할 필요가 있습니다.PRNG를 사용하는 대부분의 암호화 알고리즘 및 프로토콜의 보안은 적절한 PRNG의 사용과 정말로 랜덤한 시퀀스의 사용을 구별하는 것이 불가능하다는 가정에 기초한다.이 의존성의 가장 간단한 예는 스트림 암호입니다.스트림 암호는 메시지의 플레인텍스트를 PRNG의 출력으로 배타적 또는 입력함으로써(대부분) 동작하며 암호문은 암호문을 생성합니다.암호적으로 적절한 PRNG의 설계는 추가 기준을 충족해야 하기 때문에 매우 어렵습니다.기간의 크기는 PRNG의 암호화 적합성에 중요한 요소이지만 유일한 요소는 아닙니다.

BSI 평가 기준

독일 연방 정보 보안 사무소(독일어:BSI, der Informationstechnik의 Bundsamt für Sicherheit)는 결정론적 난수 ^[21]발생기의 품질에 대한 네 가지 기준을 확립했다.요약은 다음과 같습니다.

K1 – 생성된 난수 시퀀스가 서로 다를 가능성이 높습니다.
K2 – 일련의 숫자는 지정된 통계 테스트에 따라 "진짜 무작위" 숫자와 구별할 수 없다.시험이 그monobit 시험(1과 0의 시퀀스에 같은 숫자), 포커 시험(그 카이 제곱 검정의 특별한 인스턴스), 시험(중요한 주파수의 다양한 기간), BSI[21]과 NIST,[22]에서longruns 시험(길이 점검이 살아 있을 모든 운행 34번이나 경우에 20000비트의 순서)—both고 aut를 운영하고 있다.ocorrel이온 테스트본질적으로 이러한 요건은 비트시퀀스가 얼마나 잘 되어 있는지를 테스트하는 것입니다.즉, 0과 1의 빈도는 같으며, n개의 0의 시퀀스 뒤에 다음 비트가 1/2의 확률로 1(또는 0)이 됩니다.선택한 서브시퀀스는 시퀀스 내의 다음 요소에 대한 정보를 포함하지 않습니다.
K3 – 공격자가 (실제적인 모든 목적을 위해) 시퀀스의 이전 또는 미래 값 또는 제너레이터의 내부 상태를 계산하거나 추측하는 것은 불가능해야 합니다.
K4 – 공격자가 발생기 내부 상태, 시퀀스 내의 이전 수치 또는 이전 내부 발생기 상태를 계산하거나 추정하는 것은 실질적으로 불가능해야 합니다.

암호화 애플리케이션의 경우 K3 또는 K4 표준을 충족하는 제너레이터만 허용됩니다.

수학적 정의

지정:

$(\displaystyle$ P $)$ – ( $\left(\mathbb {R} ,{\mathfrak {B}}\right)$ $\left(\mathbb {R} ,{\mathfrak {B}}\right)$ $)$ 의 확률 분포 $(\displaystyle \left(\mathbb {$ R}, ${\$ mathfrak ${B$ $}}\right))$ ( ${\mathfrak {B}}$ 서 $B(\$ displaystyle\ $mathfrak$ {B $})$ 는 실제 라인에 설정된 표준 보렐입니다)
${\mathfrak {F}}$ {{ $displaystyle {F}}$ ${\mathfrak {F}}$ – Borel ${\mathfrak {F}}\subseteq {\mathfrak {B}}$ ${\mathfrak {F}}\subseteq {\mathfrak {B}}$ B { $displaystyle$ { $mathfrak { F}}$ \ $subseteq$ { $mathfrak$ { $B}$ ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ ${\mathfrak {F}}\subseteq {\mathfrak {B}}$ ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ = ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ { ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ ( - ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ 、 ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ : $t$ ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ { $displaystyle$ { \ $mathfrak$ { $F}$ } } } \ \ \ \ \ \ \ \ \ \ \ \ f f \ \ \ \ $=$ { F \ \ f f f f f ${F}}$ 이 ${\mathfrak {F}}$ (가) 지정되지 않았습니다. 컨텍스트에 따라 B ${\mathfrak {B}}$ {\ $displaystyle$ {\ $mathfrak$ {B $}}$ ${\mathfrak {B}}$ $\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ - $\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ $\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ : $t$ R $}$ { $displaystyle \ left$ ( - \ $infty , t$ \ $right }$ : $t$ \ $in$ \ $mathbbb$ { R $\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ } 。
$r$ R \ $displaystyle$ A \ $subseteq$ \ $mathbb$ { R $}$ - 비어 있지 않은 세트(보렐 세트일 필요는 없습니다).대부분의 $경우$ A $(\displaystyle$ A $)$ 는 $A$ P $(\displaystyle$ P $P$ 의 지원과 내부 $P$ 의 집합입니다. $P$ 를 들어P(\ $displaystyle$ $\left(0,1\right]$ P $)$ 가 $P$ $\left(0,1\right]$ $\left(0,1\right]$ $A$ $\left(0,1\right]$ 0 $\left(0,1\right]$ 1)의 $\left(0,1\right]$ 균일한 분포인 경우 A $(\displaystyle$ \ $left($ $0,1$ $\right$ 는 ( $,$ 1 $)일$ 수 $있습니다$ .{\ $displaystyle A}$ 는 $A$ 지정되지 않았으며, 컨텍스트에따라 P {\ $displaystyle$ P $}$ 의 $P$ $P$ 에 포함된 내부가 포함된 세트라고 $가정$ 합니다.

$f:\mathbb {N} _{1}\rightarrow \mathbb {R}$ f : $f:\mathbb {N} _{1}\rightarrow \mathbb {R}$ $f:\mathbb {N} _{1}\rightarrow \mathbb {R}$ $f:\mathbb {N} _{1}\rightarrow \mathbb {R}$ $f:\mathbb {N} _{1}\rightarrow \mathbb {R}$ {\ $displaystyle$ f $:\mathbb {N} _{1}\rightarrow \mathbb {R}$ ( $\mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$ 서 $\mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$ 1 $=$ { $\mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$ , $\mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$ , $\mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$ $...}$ { $displaystyle \mathbb {N} _{1$ } $=\left\{1$ , 2, 3, $3\$ rights $})$ 를 $\mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$ 양의 정수 집합이라고 합니다. $athfrak {F}}$ 은 ${\mathfrak {F}}$ (는) 다음과 같은 경우에만 A $(\displaystyle$ A $)$ 값을 $A$ 취합니다.

$\displaystyle f\left(\mathbb {N} _{1}\right)\subseteq A}$
$\displaystyle \forall E\in \mathfrak {F}\quad \varepsilon > 0\quad \exists N\in \mathbb {N} _{1}\quad \frac \forall n\geq N, \fright \frac \frac {#\left\i\f}:\d$

$\#S$ $(\displaystyle \#S)$ 는 $\#S$ 유한 $집합$ S(\ $displaystyle$ S $)$ 내의 요소의 수를 나타냅니다). $S$

${displaystyle$ f $}$ 가 $f$ $\left(0,1\right)$ ( $,$ )의 $\left(0,1\right)$ 균일한 $P$ 에 대한 의사난수발생기이고F ${$ $displaystyle$ $\left(0,1\$ right)가 $F$ F{ $displaystyle$ P $P$ 의 $F^{*}\circ f$ CDF이면 ${displaystyle$ F $}$ 는 F{ $cir$ }임을 알 수 있습니다.P{\ $displaystyle$ P $P$ 의 eudo-display number generator. $F^{*}:\left(0,1\right)\rightarrow \mathbb {R}$ 서 F $F^{*}:\left(0,1\right)\rightarrow \mathbb {R}$ : $F^{*}:\left(0,1\right)\rightarrow \mathbb {R}$ ( $F^{*}:\left(0,1\right)\rightarrow \mathbb {R}$ , $F^{*}:\left(0,1\right)\rightarrow \mathbb {R}$ ) $F^{*}:\left(0,1\right)\rightarrow \mathbb {R}$ { \ $left$ ( 0 , $1$ \ right ) \ $rightarrow$ \ $mathbb { R }$ 는 $F^{*}:\left(0,1\right)\rightarrow \mathbb {R}$ P { $displaystyle$ P $}$ 의 백분위수입니다. $}$ $=\inf$ \left $\{t\in \mathbb$ { $R} :x\leq F(t)\$ right $F^{*}(x):=\inf \left\{t\in \mathbb {R} :x\leq F(t)\right\}$ 직관적으로 표준균등분포의 시뮬레이션에서 임의의 분포를 시뮬레이션할 수 있다.

1946년 John von Neumann이 제안한 초기 컴퓨터 기반 PRNG는 중간 제곱법으로 알려져 있습니다.알고리즘은 다음과 같습니다.임의의 숫자를 제곱하여 결과 숫자의 가운데 숫자를 "난수"로 제거한 후 그 숫자를 다음 반복의 시드로 사용합니다.예를 들어 숫자 "111"을 제곱하면 "1234321"이 됩니다. "01234321"은 4자리 숫자의 제곱인 8자리 숫자입니다.이것에 의해, 「2343」이 「랜덤」번호로서 지정됩니다.이 절차를 반복하면 "4896"이 다음 결과로 표시됩니다.Von Neumann은 10자리 숫자를 사용했지만 그 과정은 같았다.

"중간 정사각형" 방법의 문제는 결국 모든 시퀀스가 반복되고 일부는 "0000"과 같이 매우 빠르게 반복된다는 것입니다.폰 노이만은 이것을 알고 있었지만, 그는 그 접근법이 그의 목적에 충분하다는 것을 알았고 수학적 "고정"이 오류를 제거하는 것이 아니라 단순히 감추는 것에 대해 걱정했다.

Von Neumann은 하드웨어 난수 발생기가 부적절하다고 판단했다. 왜냐하면 생성된 출력을 기록하지 않으면 나중에 오류를 테스트할 수 없었기 때문이다.만약 그들이 출력을 기록한다면, 그들은 제한된 컴퓨터 메모리를 소진할 것이고, 따라서 컴퓨터의 숫자를 읽고 쓸 수 있게 될 것이다.만약 그 숫자들이 카드에 쓰여졌다면, 쓰고 읽는 데 훨씬 더 오래 걸릴 것이다.그가 사용하던 ENIAC 컴퓨터에서는 "중간 정사각형" 방식이 펀치된 카드에서 숫자를 읽는 속도보다 수백 배 빠른 속도로 숫자를 생성했다.

중간 제곱법은 그 이후로 더 정교한 발전기로 대체되었다.

최근의 혁신은 가운데 정사각형을 와일 수열과 결합하는 것이다.이 방법은 장기간에 걸쳐 고품질 출력을 생성합니다(중간-제곱 방법 참조).

균일하지 않은 확률 분포에서 선택된 숫자는 균일한 분포 PRNG 및 두 분포와 관련된 함수를 사용하여 생성할 수 있다.

우선 대상 $f(b)$ f $f(b)$ b $)$ 의 누적 분포 $F(b)$ F $F(b)$ $)$ { $displaystyle$ F $($ $b$ 가 $F(b)$ 필요합니다.

F(b)=\int _{-\infty }^{b}f(b')db'

$0=F(-\infty )\leq F(b)\leq F(\infty )=1$ $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ ( $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ - $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ ) $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ F ( $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ ) $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ F ( $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ ) ) ) F ( $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ ) ) $=$ $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ { $displaystyle$ 0 $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ = F ( - \ $infty$ )\ $leq F$ ( b )\ $leq$ F ( \ $infty$ $1$ } 입니다. "통과할 확률 밀도로서 균등 분포의 난수 c 를 사용하면 다음과 같이 됩니다.

F(b)=c

하도록

b=F^{-1)(c)

는 $f(b)$ f ( $f(b)$ $)\displaystyle$ f $(b$ 에서 랜덤으로 선택된 수치입니다.이것은 역변환 샘플링을 기반으로 합니다.

예를 들어 범위 (0, 1)를 $입력$ x {\ $displaystyle$ x}로 $x$ 하는 이상적인 균일한 PRNG를 갖는 누적 가우스 분포 $erf$ - 1 $\operatorname {erf} ^{-1}(x)$ µ ( $x )$ 의 $\operatorname {erf} ^{-1}(x)$ 역수는 가우스 분포를 사용하여 일련의 (양수만 해당) 값을 생성합니다.

실제 숫자 표현을 사용할 때는 분포의 무한 "꼬리"를 유한 값으로 잘라내야 합니다.
$\operatorname {erf} ^{-1}(x)$ - $\operatorname {erf} ^{-1}(x)$ ( $x$ ){ displaystyle $\operatorname {erf }^{-1}(x$ )}의 반복적인 재계산은 보다 빠른 생성을 위해 ziggurat 알고리즘 등의 방법으로 줄여야 합니다.

Rayleigh 및 Poisson과 같은 다른 불균일 분포 생성에도 유사한 고려 사항이 적용됩니다.

「」를 참조해 주세요.

레퍼런스

^ Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (July 2012). "Recommendation for Key Management" (PDF). NIST Special Publication 800-57. NIST. Retrieved 19 August 2013.
^ "Pseudorandom number generators". Khan Academy. Retrieved 2016-01-11.
^ Von Neumann, John (1951). "Various techniques used in connection with random digits" (PDF). National Bureau of Standards Applied Mathematics Series. 12: 36–38.
^ 외를 누릅니다.(2007), 7장
^ L'Ecuyer, Pierre (2010). "Uniform random number generators". In Lovric, Miodrag (ed.). International Encyclopedia of Statistical Science. Springer. p. 1629. ISBN 3-642-04897-8.
^ 랜덤(Java Platform SE 8), Java Platform Standard Edition 8 문서.
^ OpenJDK의 Random.java.
^ 외를 누릅니다.(2007) §7.1
^ Matsumoto, Makoto; Nishimura, Takuji (1998). "Mersenne twister: a 623-dimensionally equi-distributed uniform pseudo-random number generator" (PDF). ACM Transactions on Modeling and Computer Simulation. ACM. 8 (1): 3–30. doi:10.1145/272991.272995.
^ Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software. 8 (14).
^ S.Vigna. "xorshift*/xorshift+ generators and the PRNG shootout".
^ Vigna S. (2016), "Marsaglia의 xorsshift 제너레이터의 실험적 탐색", ACM Transactions on Mathemical Software, 42; doi:10.1145/2845077.
^ Vigna S. (2017), "Marsaglia의 xorshift 제너레이터의 추가 스크램블링", 계산 및 응용 수학 저널, 315; doi :10.1016/j.cam.2016.11.006.
^ Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto (2006). "Improved long-period generators based on linear recurrences modulo 2" (PDF). ACM Transactions on Mathematical Software. 32 (1): 1–16. doi:10.1145/1132973.1132974.
^ Song Y. Yan. Cryptanalytic Attacks on RSA. Springer, 2007. p. 73. ISBN 978-0-387-48741-0.
^ Niels Ferguson, Bruce Schneier, Tadayoshi Kohno (2010). "Cryptography Engineering: Design Principles and Practical Applications, Chapter 9.4: The Generator" (PDF).{{cite web}}: CS1 maint: 여러 이름: 작성자 목록(링크)
^ Klaus Pommerening (2016). "IV.4 Perfect Random Generators". Cryptology. uni-mainz.de. Retrieved 2017-11-12. The MICALI-SCHNORR generator {{cite web}}:외부 링크 quote=(도움말)
^ Pass, Rafael. "Lecture 11: The Goldreich-Levin Theorem" (PDF). COM S 687 Introduction to Cryptography. Retrieved 20 July 2016.
^ Matthew Green. "The Many Flaws of Dual_EC_DRBG".
^ Katz, Jonathan; Yehuda, Lindell (2014). Introduction to modern cryptography. CRC press. p. 70.
^ ^a ^b Schindler, Werner (2 December 1999). "Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators" (PDF). Anwendungshinweise und Interpretationen (AIS). Bundesamt für Sicherheit in der Informationstechnik. pp. 5–11. Retrieved 19 August 2013.
^ "Security requirements for cryptographic modules". FIPS. NIST. 1994-01-11. p. 4.11.1 Power-Up Tests. Archived from the original on May 27, 2013. Retrieved 19 August 2013.

참고 문헌

Barker E., Kelsey J., 결정론적 랜덤 비트 생성기를 사용한 랜덤 번호 생성에 대한 권고, NIST SP800-90A, 2012년 1월
Brent R.P., "교대와 xors를 사용하는 일부 장기 난수 발생기", ANZIAM Journal, 2007; 48:C188–C202
젠틀 J.E.(2003), 난수 생성 및 몬테카를로 방법, 스프링거.
Hörmann W., Leydold J., Derflinger G. (2004, 2011), 스프링거-벨라그, 자동 불균일 랜덤 변동 생성.
크누스 D.E.The Art of Computer Programming, 제2권: 세미네머ical Algorithms, 제3판.애디슨 웨슬리, 1997년ISBN 0-201-89684-2.제3장 [비랜덤성 통계 테스트의 광범위한 적용 범위]
Princeton Univ Press, Pseudorandomness and Cryptographic Applications, Luby M., 1996.ISBN 9780691025469
von Neumann J., A.S. "랜덤 디짓과 관련하여 사용되는 다양한 기술"가구주, G.E. Forsythe 및 H. H. Germond, ed., 몬테카를로 방법, 국립표준적용수학시리즈, 12(워싱턴DC: 미국정부인쇄국, 1951): 36-38.
Peterson, Ivars (1997). The Jungles of Randomness : a mathematical safari. New York: John Wiley & Sons. ISBN 0-471-16449-6.
W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), 수치 레시피(Cambridge University Press)를 누릅니다.
2003년 12월 제19회 컴퓨터 보안 애플리케이션 회의에서 Viega J., "소프트웨어에서의 실용적인 난수 생성"

외부 링크

Test U01: 무료 최첨단(GPL) C++ 난수 테스트 스위트.
DieHarder: 무료(GPL) C 난수 테스트 스위트.
Eric Uner(2004)의 "랜덤 번호 생성" (임베디드 시스템 내)
Zvi Gatterman, Benny Pinkas 및 Tzachy Reinman(2006)의 "Linux 난수 생성기의 분석"
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan 및 Salil Vadhan의 "더 나은 의사랜덤 생성기" (Microsoft Research, 2012)
Stephan Lavavej가 YouTube에서 유해하다고 간주한 rand() (Microsoft, 2013)
Wsphynx는 단순한 온라인 난수 생성기입니다.난수는 Javascript pseudorandom number generators(PRNG) 알고리즘에 의해 생성됩니다.

[1] Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (July 2012). "Recommendation for Key Management" (PDF). NIST Special Publication 800-57. NIST. Retrieved 19 August 2013.

[2] "Pseudorandom number generators". Khan Academy. Retrieved 2016-01-11.

[3] Von Neumann, John (1951). "Various techniques used in connection with random digits" (PDF). National Bureau of Standards Applied Mathematics Series. 12: 36–38.

[4] 외를 누릅니다.(2007), 7장

[5] L'Ecuyer, Pierre (2010). "Uniform random number generators". In Lovric, Miodrag (ed.). International Encyclopedia of Statistical Science. Springer. p. 1629. ISBN 3-642-04897-8.

[6] 랜덤(Java Platform SE 8), Java Platform Standard Edition 8 문서.

[7] OpenJDK의 Random.java.

[8] 외를 누릅니다.(2007) §7.1

[9] Matsumoto, Makoto; Nishimura, Takuji (1998). "Mersenne twister: a 623-dimensionally equi-distributed uniform pseudo-random number generator" (PDF). ACM Transactions on Modeling and Computer Simulation. ACM. 8 (1): 3–30. doi:10.1145/272991.272995.

[10] Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software. 8 (14).

[11] S.Vigna. "xorshift*/xorshift+ generators and the PRNG shootout".

[12] Vigna S. (2016), "Marsaglia의 xorsshift 제너레이터의 실험적 탐색", ACM Transactions on Mathemical Software, 42; doi:10.1145/2845077.

[13] Vigna S. (2017), "Marsaglia의 xorshift 제너레이터의 추가 스크램블링", 계산 및 응용 수학 저널, 315; doi :10.1016/j.cam.2016.11.006.

[14] Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto (2006). "Improved long-period generators based on linear recurrences modulo 2" (PDF). ACM Transactions on Mathematical Software. 32 (1): 1–16. doi:10.1145/1132973.1132974.

[15] Song Y. Yan. Cryptanalytic Attacks on RSA. Springer, 2007. p. 73. ISBN 978-0-387-48741-0.

[16] Niels Ferguson, Bruce Schneier, Tadayoshi Kohno (2010). "Cryptography Engineering: Design Principles and Practical Applications, Chapter 9.4: The Generator" (PDF).{{cite web}}: CS1 maint: 여러 이름: 작성자 목록(링크)

[17] Klaus Pommerening (2016). "IV.4 Perfect Random Generators". Cryptology. uni-mainz.de. Retrieved 2017-11-12. The MICALI-SCHNORR generator {{cite web}}:외부 링크 quote=(도움말)

[GoldreichLevinNotes-18] Pass, Rafael. "Lecture 11: The Goldreich-Levin Theorem" (PDF). COM S 687 Introduction to Cryptography. Retrieved 20 July 2016.

[19] Matthew Green. "The Many Flaws of Dual_EC_DRBG".

[20] Katz, Jonathan; Yehuda, Lindell (2014). Introduction to modern cryptography. CRC press. p. 70.

[bsi_ais20-21] Schindler, Werner (2 December 1999). "Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators" (PDF). Anwendungshinweise und Interpretationen (AIS). Bundesamt für Sicherheit in der Informationstechnik. pp. 5–11. Retrieved 19 August 2013.

[22] "Security requirements for cryptographic modules". FIPS. NIST. 1994-01-11. p. 4.11.1 Power-Up Tests. Archived from the original on May 27, 2013. Retrieved 19 August 2013.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

Search

의사 난수 생성기

네임스페이스

더

목차

잠재적인 문제

선형 반복을 기반으로 하는 생성자

암호화 PRNG

BSI 평가 기준

수학적 정의

「」를 참조해 주세요.

레퍼런스

참고 문헌

외부 링크

Search

의사 난수 생성기

잠재적인 문제

선형 반복을 기반으로 하는 생성자

암호화 PRNG

BSI 평가 기준

수학적 정의

「 」를 참조해 주세요.

레퍼런스

참고 문헌

외부 링크

「」를 참조해 주세요.