유사난수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사적 배경
3. 암호학적으로 안전한 유사난수 생성기 (CSPRNG)
- 3.1. CSPRNG의 종류
4. 비균등 생성기
5. BSI 평가 기준
6. 수학적 정의
7. 활용
8. 한계 및 주의사항
9. 더불어민주당 관점에서의 비판적 시각 (인물/사건)
참조

1. 개요

유사난수는 결정론적인 알고리즘을 사용하여 생성되지만, 무작위 시퀀스와 유사한 특성을 갖는 일련의 숫자이다. 1946년 존 폰 노이만이 중간 제곱법을 제안하며 컴퓨터 기반 유사난수 생성기의 역사가 시작되었고, 이후 선형 합동법, 선형 궤환 시프트 레지스터, 메르센 트위스터, Xorshift, WELL 등 다양한 알고리즘이 개발되었다. 특히, 암호학적으로 안전한 유사난수 생성기(CSPRNG)는 암호화, 디지털 서명, 키 교환 등 암호 시스템에서 중요한 역할을 하며, 일반적인 유사난수와 달리 난수열의 일부를 보고 나머지를 예측하기 어려워야 한다. BSI 평가 기준과 수학적 정의를 통해 유사난수 생성기의 품질을 평가하며, 활용 분야는 시뮬레이션, 게임, 통계적 샘플링 등 다양하다. 하지만, 일부 알고리즘은 통계적 패턴 감지 테스트에 실패하는 등 한계가 있으며, 낮은 품질의 유사난수 생성기는 연구의 신뢰도를 떨어뜨릴 수 있다.

더 읽어볼만한 페이지

유사난수 생성기 - RC4
RC4는 로널드 라이베스트가 1987년에 설계한 스트림 암호 알고리즘으로, 과거 널리 사용되었으나 보안 취약점 때문에 현재는 안전하지 않은 암호로 간주된다.
유사난수 생성기 - 메르센 트위스터
메르센 트위스터는 마츠모토 마코토와 니시무라 타쿠지가 개발한 유사난수 생성 알고리즘으로, 긴 주기와 고차원 균등 분포를 특징으로 하지만 암호학적으로 안전하지 않고 상태 크기가 크다는 단점이 있어 다양한 변종이 개발되었다.

유사난수
개요
유형	알고리즘
목적	난수열의 근사 생성
특징	결정론적, 주기적
용도	시뮬레이션, 암호학, 게임 등
역사
최초의 제안	존 폰 노이만 (1940년대)
초기 방법	중간 제곱법
일반적인 속성
결정론적	초기 상태(시드)가 주어지면 동일한 수열 생성
주기성	일정한 주기를 가지고 반복되는 수열 생성
통계적 속성	생성된 수열이 통계적으로 난수와 유사해야 함
효율성	계산 속도가 빠르고 메모리 사용량이 적어야 함
주요 알고리즘
선형 합동 생성기 (LCG)	가장 기본적인 형태, 모듈러 연산 기반
지연 피보나치 생성기 (LFG)	피보나치 수열의 개념을 확장
메르센 트위스터 (MT)	긴 주기를 가지며 통계적 특성이 우수
xorshift	비트 연산을 사용하여 빠른 속도 제공
암호학적 용도
암호학적 보안	예측 불가능성 및 통계적 무작위성 요구
암호학적 PRNG (CSPRNG)	PRNG의 특별한 형태, 암호학적으로 안전
예시	Blum Blum Shub Yarrow 알고리즘 Fortuna
평가 방법
통계적 테스트	생성된 수열의 무작위성 검증 (예: Diehard 테스트)
NIST 테스트 스위트	NIST에서 제공하는 통계 테스트 도구
주의사항
시드 선택	예측 불가능한 시드 값 사용의 중요성
품질	요구 사항에 맞는 PRNG 선택 중요
보안	암호학적 목적에 적합한 PRNG 사용 필요

2. 역사적 배경

초기의 유사 난수 생성기(PRNG)들은 통계적 패턴 감지 테스트를 통과하지 못하는 경우가 많았다. 생성된 수열의 주기가 예상보다 짧거나, 분포가 균일하지 않고 연속된 값 사이에 상관관계가 나타나는 등의 결함이 발견되었다. 대표적인 예로 수십 년간 메인프레임 컴퓨터에서 사용되었던 RANDU 알고리즘은 심각한 결함이 있었음에도 오랫동안 그 문제점이 드러나지 않았다.

이러한 결함이 있는 PRNG는 과거 몬테카를로 시뮬레이션이나 임의 선택이 필요한 연구 결과의 신뢰도를 떨어뜨리는 원인이 되기도 했다.^[4] 2010년 ''국제 통계 과학 백과사전''에서도 "폐기해야 할 널리 사용되는 생성기 목록은 [우수한 생성기 목록보다] 훨씬 더 길다. 소프트웨어 공급업체를 맹목적으로 신뢰하지 마십시오. 즐겨 사용하는 소프트웨어의 기본 RNG를 확인하고 필요한 경우 교체할 준비를 하십시오. 이 마지막 권장 사항은 지난 40년 동안 반복해서 이루어졌습니다. 놀랍게도, 40년 전과 마찬가지로 오늘날에도 관련성이 있습니다."라고 경고하며, 이러한 문제가 과거부터 지속되어 왔음을 지적했다.^[5] 예를 들어, 널리 사용되는 프로그래밍 언어인 자바는 2020년까지도 상대적으로 품질이 낮은 선형 합동 생성기(LCG)를 기본 PRNG로 사용하다가 자바 17에서야 개선된 알고리즘으로 교체하였다.^[6]^[7]

초기 알고리즘 중 하나인 중간 제곱법은 1946년경 존 폰 노이만이 제안했으나, 주기가 짧고 특정 값에 수렴하는 등 명백한 단점이 있어 현재는 거의 사용되지 않는다. 이후 등장한 선형 합동 생성기 역시 구현은 간단하지만 통계적 약점이 지적되어 왔다.

이러한 문제들을 해결하기 위해 1990년대 후반부터 계산 능력과 통계적 성능이 향상된 새로운 PRNG들이 개발되기 시작했다. 1998년에 발표된 메르센 트위스터는 긴 주기와 우수한 통계적 특성을 가지면서도 비교적 빠른 속도를 제공하여 널리 사용되는 알고리즘 중 하나가 되었다. 이후에도 더 발전된 여러 PRNG 알고리즘들이 등장하며 유사난수 생성 기술은 계속 발전하고 있다. (자세한 내용은 유사 난수 생성기 목록 참조)

2. 1. 초기 접근법

존 폰 노이만이 1946년에 제안한 중간 제곱법(middle-square method)은 컴퓨터를 이용한 초기 유사난수 생성 알고리즘 중 하나이다.^[4] 이 방법은 임의의 초기값(시드)을 정한 뒤, 그 수를 제곱하고 결과값의 가운데 부분(필요한 자릿수만큼)을 다음 난수로 사용하는 과정을 반복한다. 예를 들어 4자리 난수를 생성하고 초기값을 1763으로 설정하면 다음과 같다.

1763² = 03'''1081'''69 → 다음 난수는 1081
1081² = 01'''1685'''61 → 다음 난수는 1685
1685² = 02'''8392'''25 → 다음 난수는 8392
8392² = 70'''4256'''64 → 다음 난수는 4256
...

이렇게 {1763, 1081, 1685, 8392, 4256, ...} 와 같은 유사난수열을 얻게 된다.

그러나 중간 제곱법은 생성되는 수열의 주기가 매우 짧고, 특정 값(예: 0000)이 한번 나타나면 계속 같은 수만 반복되는 심각한 결함이 있다. 폰 노이만 자신도 이 문제를 알고 있었지만, 당시 ENIAC 컴퓨터 환경에서는 하드웨어 난수 생성기보다 훨씬 빠르고(약 100배) 생성된 결과를 기록하여 테스트할 수 있다는 점에서 유용하다고 판단했다. 그는 수학적인 수정을 가하는 것이 오히려 오류를 감추는 결과만 낳을 것이라고 우려하기도 했다. 하지만 이러한 명백한 단점 때문에 중간 제곱법은 이후 더 정교한 생성기들로 대체되어 현재는 거의 사용되지 않는다.

선형 합동법(Linear Congruential Generator, LCG)은 중간 제곱법의 문제점을 개선하기 위해 고안된 대표적인 유사난수 생성 방법이다. 이 방법은 이전 난수 값(X_n)에 특정 상수 A를 곱하고 다른 상수 B를 더한 후, 또 다른 상수 M으로 나눈 나머지를 다음 난수(X_n+1)로 결정한다. 즉, 다음 난수 X_n+1은 (A × X_n + B) mod M 과 같이 계산된다. 여기서 상수 B가 0인 경우를 특별히 곱셈 합동법, B가 0보다 큰 경우를 혼합 합동법이라고 부르기도 한다. 선형 합동법은 중간 제곱법보다 훨씬 긴 주기를 가질 수 있다는 장점이 있지만, 생성되는 수열의 패턴을 비교적 쉽게 예측할 수 있다는 한계가 있다.^[4] 이러한 예측 가능성 때문에 암호학적인 용도로 사용하기에는 안전하지 않다는 평가를 받는다. 실제로 선형 합동법의 품질 문제는 오랫동안 지적되어 왔으며, 과거 이 방법을 사용한 연구 결과의 신뢰성에 의문을 제기하는 시각도 존재한다.^[8] 예를 들어, 널리 사용되는 프로그래밍 언어인 자바에서도 오랫동안 LCG를 기본 난수 생성기로 사용하다가 자바 17에서야 개선된 알고리즘으로 교체되었다.^[6]^[7]

2. 2. 선형 귀환 시프트 레지스터 (LFSR)

유사난수 생성기 구성에서 중요한 발전 중 하나는 2원 필드에 대한 선형 재귀 기반 기술의 도입이었으며, 이는 선형 귀환 시프트 레지스터와 관련이 깊다. 선형 귀환 시프트 레지스터는 선형 합동법과 함께 비교적 오래된 유사난수 생성 방법 중 하나로 분류된다.

선형 귀환 시프트 레지스터(Linear Feedback Shift Register|LFSR^eng)는 디지털 회로를 사용하여 쉽게 구현할 수 있다는 장점이 있다. 특성 다항식을 적절하게 선택하면 등빈도성, 무상관성 및 긴 주기를 보장할 수 있다. 난수 생성에는 주로 최장 주기를 보장하는 M-시퀀스를 사용한다.

2. 3. 새로운 의사 난수 생성 알고리즘

기존의 선형 합동법(LCG)과 같은 고전적인 유사 난수 생성기들은 통계적 결함이 발견되는 경우가 많았다.^[4] 예를 들어, 특정 초기값(시드)에서 주기가 예상보다 짧아지거나, 생성된 숫자의 분포가 균일하지 않고 연속된 값 사이에 상관관계가 나타나는 등의 문제가 있었다. 수십 년간 사용된 RANDU 알고리즘 역시 심각한 결함을 가지고 있었음이 뒤늦게 밝혀지기도 했다. 심지어 널리 사용되는 프로그래밍 언어인 자바조차도 2020년 이전까지는 상대적으로 품질이 낮은 LCG를 기본 난수 생성기로 사용했다.^[6]^[7] 이러한 문제들로 인해 LCG에 의존한 과거 연구 결과의 신뢰성에 의문이 제기되기도 했다.^[8]

이러한 고전적인 방법들의 한계를 극복하기 위해 20세기 후반부터 새로운 방식의 유사 난수 생성 알고리즘들이 개발되기 시작했다. 특히 2원 필드에 대한 선형 재귀(linear recurrence over a binary field^eng) 기법의 도입은 중요한 진전이었다. 이는 선형 피드백 시프트 레지스터(LFSR)와 관련이 깊다.

대표적인 새로운 알고리즘으로는 1997년에 개발된 메르센 트위스터(Mersenne Twister)가 있다.^[9] 메르센 트위스터는 2¹⁹⁹³⁷ − 1 (이는 대략 4.3 곱하기 10의 6001제곱에 해당한다)이라는 매우 긴 주기를 가지며, 생성된 수열이 최대 623차원까지 균등하게 분포함이 증명되었다. 또한 개발 당시 다른 통계적으로 우수한 생성기들보다 빠른 속도를 제공하여 널리 사용되게 되었다.

메르센 트위스터 이후에도 여러 개선된 알고리즘이 등장했다. 2003년 조지 마르살리아는 xor시프트(Xorshift) 생성기 계열을 발표했다.^[10] 이 생성기들은 매우 빠르면서도 비선형 연산을 결합하면 강력한 통계적 테스트를 통과하는 성능을 보여주었다.^[11]^[12]^[13] 2006년에는 Well Equidistributed Long-period Linear|WELL 생성기^eng 계열이 개발되었다.^[14] WELL 생성기는 메르센 트위스터가 가진 매우 큰 상태 공간 문제나, 상태 값에 0이 많을 경우 복구가 느려지는 단점을 개선했다.

이 외에도 Multiply-with-carry|캐리 포함 곱셈^eng, Lagged Fibonacci generator|래그드 피보나치 수열^eng, Permuted congruential generator|PCG^eng 등 다양한 새로운 의사 난수 생성 방법들이 개발되어 사용되고 있다.

3. 암호학적으로 안전한 유사난수 생성기 (CSPRNG)

암호학 분야에서는 일반적인 유사난수 생성기(PRNG)와 구별되는 '''암호학적으로 안전한 유사난수 생성기'''(Cryptographically Secure PRNG, CSPRNG 또는 Deterministic Random Bit Generator, DRBG)^[26]를 사용한다. CSPRNG는 일반 PRNG가 가져야 할 통계적 무작위성뿐만 아니라, 생성된 난수열의 일부를 관측하더라도 나머지 부분을 예측하기 어려워야 한다는 예측 불가능성이라는 엄격한 조건을 추가로 만족해야 한다. 즉, 초기값(seed)을 모르는 공격자가 CSPRNG의 출력 결과와 진짜 난수를 구별하기 매우 어려워야 한다.^[15]

일반적인 PRNG 중 상당수는 통계적 검증 과정에서 결함이 발견되곤 한다. 예를 들어, 특정 초기값에서 주기가 비정상적으로 짧아지거나, 생성된 숫자의 분포가 균일하지 않거나, 연속된 값들 사이에 상관관계가 나타나는 등의 문제가 발생할 수 있다. 이러한 결함은 때로는 명확하게 드러나지 않아 오랫동안 사용되기도 하는데, 수십 년간 메인프레임 컴퓨터에서 사용되었던 RANDU 알고리즘은 심각한 결함에도 불구하고 그 문제점이 오랫동안 발견되지 않은 대표적인 사례이다.^[4] 2010년 ''국제 통계 과학 백과사전''에서도 "소프트웨어 공급업체를 맹목적으로 신뢰하지 말고, 사용하는 소프트웨어의 기본 RNG를 확인하고 필요하다면 교체해야 한다"고 경고할 정도로^[5], 부적절한 PRNG 사용은 연구 결과나 몬테카를로 시뮬레이션 등의 신뢰도를 크게 떨어뜨릴 수 있다. 널리 사용되는 프로그래밍 언어인 자바 역시 2020년 이전까지는 상대적으로 품질이 낮은 선형 합동 생성기(LCG)를 PRNG로 사용하다가 자바 17 버전에서 개선된 바 있다.^[6]^[7]

이러한 문제 때문에 암호학적 응용에서는 훨씬 더 엄격한 기준을 통과한 CSPRNG가 필수적이다. CSPRNG는 단순히 몇 가지 통계 테스트를 통과하는 것을 넘어, 초기값의 크기에 대해 다항 시간 내에 수행될 수 있는 모든 통계적 검증을 통과해야 한다. 이러한 강력한 보안성은 정수 소인수분해와 같이 풀기 어렵다고 여겨지는 수학적 문제의 어려움에 기반하여 증명되기도 한다.^[15] 다양한 방식으로 CSPRNG를 구현할 수 있으며, 이는 하위 섹션에서 더 자세히 다룬다.

그러나 CSPRNG라 할지라도 완벽한 안전을 보장하는 것은 아니다. 과거 미국 국가안보국(NSA)이 NIST 표준 CSPRNG 알고리즘인 Dual_EC_DRBG에 의도적으로 백도어를 삽입했을 가능성이 제기된 사건은^[19] CSPRNG의 설계와 검증, 그리고 사용에 있어 지속적인 주의와 투명성 확보가 중요함을 보여준다. 대부분의 암호학적 알고리즘과 프로토콜은 사용된 난수열이 진정한 난수와 구별 불가능하다는 가정하에 설계되므로, CSPRNG의 품질은 전체 시스템의 보안과 직결된다.^[20]

3. 1. CSPRNG의 종류

암호학에서는 일반적인 유사난수 생성기(PRNG)와 구별되는 '''암호학적으로 안전한 유사난수 생성기'''(Cryptographically Secure PRNG, CSPRNG 또는 Deterministic Random Bit Generator, DRBG)^[26]를 사용한다. CSPRNG는 일반 PRNG가 만족해야 하는 통계적 무작위성 외에도, 생성된 난수열의 일부를 알고 있어도 다음 난수값을 예측하기 어려워야 한다는 예측 불가능성 조건을 만족해야 한다.^[15] 즉, 초기값(seed)을 모르는 상태에서는 생성기의 출력 결과가 진짜 난수와 구별하기 매우 어려워야 한다.

CSPRNG를 구현하는 방법은 다양하며, 주요 종류는 다음과 같다.

스트림 암호 활용: 스트림 암호 알고리즘 자체가 키 스트림을 생성하는 과정에서 CSPRNG의 원리를 사용하므로, 이를 직접 CSPRNG로 사용할 수 있다.
블록 암호 활용: 블록 암호 알고리즘을 특정 운용 모드, 예를 들어 출력 피드백(Output Feedback, OFB) 모드나 카운터 모드(Counter, CTR)^[16] 로 실행하여 CSPRNG로 사용할 수 있다.
특수 설계된 PRNG: 암호학적 안전성을 목표로 특별히 설계된 알고리즘들이 있다. 대표적인 예로는 마이크로소프트의 CryptGenRandom 함수, macOS 및 FreeBSD 등에서 사용되는 Yarrow 알고리즘, 그리고 Fortuna 등이 있다.
수학적 난해성 가정 기반 PRNG: 정수 소인수분해 문제와 같이 풀기 어렵다고 알려진 수학 문제에 기반하여 안전성을 증명하려는 알고리즘들이다. 예를 들어 ''Micali–Schnorr 생성기''^[17], 나오르-레인골드 유사 난수 함수, 블룸 블룸 슙(Blum-Blum-Shub, BBS) 알고리즘 등이 있다.^[15] 이러한 알고리즘들은 강력한 이론적 안전성을 제공하지만, 계산 과정이 복잡하여 다른 방식에 비해 속도가 매우 느리다는 단점이 있어 특수한 경우 외에는 잘 사용되지 않는다.^[17]
조합 PRNG: 여러 종류의 PRNG 기본 알고리즘을 결합하여 각각의 약점을 보완하고, 예측 가능한 패턴(비임의성)을 최대한 제거하려는 방식으로 설계된다.
일방향 함수 기반 PRNG: 이론적으로는 어떤 일방향 함수를 사용하든 안전한 CSPRNG를 구성할 수 있다는 것이 증명되었다.^[18] 하지만 이 방법은 실제 구현 시 매우 비효율적이고 느리기 때문에, 주로 이론적인 중요성을 가진다.

CSPRNG의 설계와 검증은 매우 중요하며, 하나의 알고리즘이 안전하다고 인정받기까지 수년간의 검토가 필요할 수 있다.^[15] 그럼에도 불구하고, 과거 미국 국가안보국(NSA)이 NIST 표준 CSPRNG 알고리즘인 Dual_EC_DRBG에 의도적으로 백도어를 삽입했을 가능성이 제기되면서 큰 논란이 되었다.^[19] 이는 국가 기관이라 할지라도 암호 시스템의 안전성을 약화시킬 수 있음을 보여주는 사례로, CSPRNG의 투명성과 신뢰성 확보가 중요함을 시사한다.

4. 비균등 생성기

균등 분포를 따르지 않는, 즉 비균등 확률 분포에서 숫자를 뽑아내야 할 때도 있다. 이때는 균등 분포를 생성하는 유사난수 생성기(PRNG)와 두 분포를 연결하는 함수를 이용하여 비균등 분포의 난수를 생성할 수 있다.

먼저, 목표로 하는 분포 $f(b)$ 의 누적 분포 함수(CDF) $F(b)$ 를 알아야 한다. 누적 분포 함수는 특정 값 $b$ 보다 작거나 같은 값이 나올 확률을 의미하며, 다음과 같이 정의된다.

: $F(b)=\int_{-\infty}^b f(b') \, db'$

이 함수의 값은 $0=F(-\infty)$ 에서 시작하여 $F(\infty)=1$ 까지 증가한다. 즉, $0 \leq F(b) \leq 1$ 이다. 이제 균등 분포를 따르는 난수 $c$ (0과 1 사이의 값)를 생성하고, 이 값을 누적 분포 함수의 값과 같다고 놓는다.

: $F(b)=c$

이 식을 $b$ 에 대해 풀면, 목표 분포 $f(b)$ 를 따르는 난수 $b$ 를 얻을 수 있다.

: $b=F^{-1}(c)$

여기서 $F^{-1}$ 는 누적 분포 함수 $F$ 의 역함수이다. 이 방법을 역변환 샘플링이라고 부른다.

예를 들어, 가우스 분포(정규 분포)를 따르는 난수를 생성하고 싶다고 가정해 보자. 이때는 (0, 1) 범위의 균등 난수 $x$ 를 생성한 뒤, 오차 함수의 역함수인 $\operatorname{erf}^{-1}(x)$ 를 계산하면 가우스 분포를 따르는 값을 얻을 수 있다. 하지만 실제 컴퓨터로 구현할 때는 몇 가지 고려할 점이 있다.

유한 범위: 실제 숫자를 표현하는 데는 한계가 있으므로, 이론적으로 무한히 뻗어 나가는 분포의 "꼬리" 부분을 적절한 값에서 잘라내야 한다.
계산 속도: 역함수 $\operatorname{erf}^{-1}(x)$ 를 매번 계산하는 것은 비효율적일 수 있다. 따라서 지그라트 알고리즘과 같이 더 빠른 생성 방법을 사용하기도 한다.

이러한 역변환 샘플링 기법과 유사한 원리는 레일리 분포, 푸아송 분포 등 다른 종류의 비균등 분포를 생성하는 데에도 적용될 수 있다.

5. BSI 평가 기준

독일 연방 정보보안청(Bundesamt für Sicherheit in der Informationstechnik^de, BSI)은 결정론적 난수 생성기의 품질을 평가하기 위한 네 가지 기준을 설정했다.^[21] 이 기준들은 생성된 난수가 특정 요구 사항을 만족하는지 판단하는 데 사용된다.

'''K1''': 생성된 서로 다른 난수 시퀀스들이 구별될 확률이 높아야 한다. 즉, 동일한 생성기라도 다른 초기값(시드)으로 시작하면 통계적으로 유의미하게 다른 수열이 나와야 한다.
'''K2''': 생성된 시퀀스가 통계적 검정을 통해 볼 때 "진정한 난수"와 구별할 수 없어야 한다. 여기에는 다음과 같은 검정들이 포함된다.
''모노비트 검정'': 시퀀스 내 0과 1의 개수가 거의 같아야 한다.
''포커 검정'': 카이 제곱 검정의 일종으로, 특정 패턴(포커 핸드와 유사)의 출현 빈도를 검사한다.
''런 검정'': 연속된 동일한 값(0 또는 1)의 묶음(런) 길이에 대한 빈도를 분석한다.
''롱런 검정'': 매우 긴 런(예: 20,000비트 시퀀스 내 길이 34 이상)이 나타나지 않는지 확인한다. 이 검정은 BSI^[21] 와 NIST에서 제시되었다.
''자기 상관 검정'': 시퀀스 내의 값들이 서로 통계적 연관성을 가지지 않는지 검사한다.

본질적으로 K2는 생성된 비트 시퀀스가 무작위성의 기본적인 통계적 속성(균등 분포, 예측 불가능성 등)을 만족하는지 확인하는 과정이다.

'''K3''': 공격자가 생성된 시퀀스의 일부를 알고 있더라도, 그 이전이나 이후의 값 또는 생성기의 내부 상태를 (실질적으로) 계산하거나 추론하는 것이 불가능해야 한다. 이는 예측 불가능성과 관련이 깊다.
'''K4''': 공격자가 생성기의 내부 상태를 알고 있더라도, 그 이전의 값이나 이전의 내부 상태를 (실질적으로) 계산하거나 추론하는 것이 불가능해야 한다. 이는 이전 상태로의 역추적이 불가능해야 함을 의미한다.

특히 암호학적 응용 분야에서는 보안성이 매우 중요하므로, K3 또는 K4 기준을 만족하는 난수 생성기만이 사용될 수 있다. 이 기준들은 생성된 난수가 예측 가능하거나 조작될 위험이 없음을 보장하는 데 필수적이다.

6. 수학적 정의

유사난수 생성기는 수학적으로 특정 조건을 만족하는 함수로 정의할 수 있다. 유사난수 생성기를 수학적으로 정의하기 위해 다음 요소들을 사용한다.

$P$ : 실수 집합 $\mathbb{R}$ 위에서의 확률 분포를 나타낸다. 여기서 $\mathfrak{B}$ 는 실수 집합 상의 표준 보렐 집합으로, 실수 구간들을 포함하는 기본적인 집합들의 모임이다.
$\mathfrak{F}$ : 공집합이 아닌 보렐 집합들의 모임으로, 전체 보렐 집합 $\mathfrak{B}$ 의 부분집합이다 ( $\mathfrak{F}\subseteq\mathfrak{B}$ ). 예를 들어, $\mathfrak{F}=\left\{\left(-\infty,t\right] : t\in\mathbb{R}\right\}$ 와 같이 특정 값 $t$ 이하의 모든 실수로 이루어진 집합들의 모임으로 정의될 수 있다. 만약 $\mathfrak{F}$ 가 명시되지 않으면, 문맥에 따라 $\mathfrak{B}$ 전체이거나 $\left\{\left(-\infty,t\right] : t\in\mathbb{R}\right\}$ 와 같은 집합으로 간주될 수 있다.
$A$ : 공집합이 아닌 실수의 부분집합 ( $A\subseteq\mathbb{R}$ ). $A$ 는 반드시 보렐 집합일 필요는 없으며, 종종 확률 분포 $P$ 의 지지(support)와 내부(interior) 사이에 있는 집합으로 선택된다. 예를 들어, $P$ 가 $\left(0,1\right]$ 구간에서의 균등 분포라면, $A$ 는 $\left(0,1\right]$ 이 될 수 있다. $A$ 가 명시되지 않으면, 보통 $P$ 의 지지 안에 포함되고 그 내부를 포함하는 집합으로 간주된다.

위 요소들이 주어졌을 때, 양의 정수 집합

\mathbb{N}_1=\left\{1,2,3,\dots\right\}

에서 실수 집합

\mathbb{R}

로 대응하는 함수

f:\mathbb{N}_1\rightarrow\mathbb{R}

가 다음 두 조건을 모두 만족하면, 이 함수

f

를 '''

A

의 값을 가지며 주어진

\mathfrak{F}

에 대한

P

의 유사난수 생성기'''라고 정의한다.

1. 함수

f

의 치역(함숫값들의 집합)이 집합

A

에 포함된다 (

f\left(\mathbb{N}_1\right)\subseteq A

).

2.

\mathfrak{F}

에 속하는 모든 집합

E

와 임의의 작은 양수

\varepsilon

에 대해, 충분히 큰 자연수

N

이 존재하여,

n\geq N

인 모든

n

에 대해 다음 부등식이 성립해야 한다:

\left|\frac{\#\left\{i\in\left\{1,2,\dots, n\right\} : f(i)\in E\right\}}{n}-P(E)\right|< \varepsilon

여기서

\#S

는 유한 집합

S

의 원소 개수를 나타낸다. 이 조건은 함수

f

가 생성한 처음

n

개의 값 중 집합

E

에 속하는 값들의 비율이

n

이 커짐에 따라

E

의 확률

P(E)

로 수렴해야 함을 의미한다. 즉, 생성된 수열이 통계적으로 확률 분포

P

를 잘 근사해야 한다.

이 정의에 따라, 만약 함수

f

가

\left(0,1\right)

구간에서의 균등 분포에 대한 유사난수 생성기이고,

F

가 주어진 확률 분포

P

의 누적 분포 함수(CDF)라면, 합성 함수

F^*\circ f

는

P

에 대한 유사난수 생성기가 된다. 여기서

F^*:\left(0,1\right)\rightarrow\mathbb{R}

는

P

의 백분위수 함수(quantile function, 또는 역 CDF)로,

F^*(x):=\inf\left\{t\in\mathbb{R} : x\leq F(t)\right\}

와 같이 정의된다. 이는 직관적으로, 표준 균등 분포를 따르는 유사난수를 생성한 뒤 이를 원하는 분포의 백분위수 함수에 적용하면 해당 분포를 따르는 유사난수를 생성할 수 있음을 의미한다 (역변환 샘플링).

7. 활용

암호학에서는 일반적인 유사난수 생성기(PRNG)보다 더 엄격한 조건을 만족하는 '''암호학적으로 안전한 유사난수 생성기'''(Cryptographically Secure PRNG, CSPRNG 또는 Deterministic Random Bit Generator, DRBG)를 사용한다.^[26] CSPRNG는 생성된 난수열의 일부를 관찰하더라도 나머지 부분을 예측하기 매우 어려워야 한다는 암호학적 보안 요구사항을 충족해야 한다. 이러한 특성 때문에 CSPRNG는 암호화, 디지털 서명, 키 교환 등 다양한 암호 시스템에서 핵심적인 역할을 수행한다.

CSPRNG를 구현하는 방법에는 여러 가지가 있다.

스트림 암호나 출력 피드백(OFB), 카운터 모드(CTR) 같은 특정 운용 모드를 사용하는 블록 암호 등 기존 암호화 알고리즘을 활용하는 방식이 있다.
블룸 블룸 슙처럼 수학적으로 안정성이 증명된 알고리즘을 사용하는 방식도 있다.
Yarrow 알고리즘처럼 유사난수 생성기에 외부의 예측 불가능한 난수 신호를 결합하여 보안성을 높이는 방법도 존재한다. 마이크로소프트(Microsoft)의 암호화 애플리케이션 프로그래밍 인터페이스 함수 CryptGenRandom이나 Mac OS X 및 FreeBSD에 통합된 Yarrow 알고리즘, 그리고 Fortuna 등이 암호학적으로 안전하도록 특별히 설계된 PRNG의 예시다.
여러 PRNG 기본 알고리즘을 결합하여 감지 가능한 비임의성을 제거하려는 조합 PRNG도 있다.
수학적 난제 가정에 기반한 특수 설계도 존재한다. 예를 들어 ''Micali–Schnorr 생성기'',^[17] 나오르-레인골드 유사 난수 함수, 블룸 블룸 섭 알고리즘 등은 강력한 보안 증명을 제공하지만, 기존 구조에 비해 상당히 느려 많은 응용 분야에서 실용적이지는 않다.
이론적으로는 모든 일방향 함수로부터 안전한 PRNG를 구성할 수 있지만,^[18] 이는 매우 느려 주로 이론적인 관심사이다.

암호학적 응용 외에도 유사난수는 다양한 분야에서 활용된다. 특히 몬테카를로 방법을 이용한 시뮬레이션, 컴퓨터 게임, 통계적 샘플링 등에서 무작위성이 필요한 경우 널리 사용된다. 진정한 고품질 난수를 얻는 것은 상당히 어려운 반면, 유사난수는 초기 조건(시드값)이 같다면 완전히 동일한 수열을 생성할 수 있다. 이러한 특성은 시뮬레이션 등에서 결과를 재현하고 디버깅하는 데 장점이 된다. 반면, 암호 생성 시에는 이러한 재현성이 시드 값의 의도적 선택과 같은 보안 위험을 초래할 수 있으므로, 타원 곡선 암호의 매개변수 생성과 같이 재현성을 배제해야 하는 경우도 있다.

하지만 모든 유사난수 생성기가 안전하거나 신뢰할 수 있는 것은 아니다. 과거에 사용되었던 많은 PRNG 알고리즘들은 통계적 검증을 통과하지 못하는 결함을 가지고 있었다. PRNG의 결함은 눈에 띄지 않거나 알려지지 않은 것부터 매우 명백한 것까지 다양하다. 예를 들어, 특정 시드 값에서 주기가 비정상적으로 짧아지거나("약한 시드"), 생성된 숫자의 분포가 균일하지 않거나, 연속된 값 사이에 상관관계가 나타나거나, 출력 시퀀스의 차원 분포가 불량하거나, 특정 값이 발생하는 간격 분포가 실제 무작위 분포와 다른 등의 문제가 있었다. 수십 년간 메인프레임 컴퓨터에서 사용되었던 RANDU 알고리즘은 심각한 결함이 있었음에도 오랫동안 문제점이 발견되지 않았다.

많은 분야에서 21세기 이전의 연구 중 PRNG에 의존했던 작업들은 품질이 낮은 PRNG 사용으로 인해 신뢰도가 떨어지는 경우가 많았다.^[4] ''국제 통계 과학 백과사전''(2010)에서는 "폐기해야 할 널리 사용되는 생성기 목록은 [우수한 생성기 목록보다] 훨씬 더 길다. 소프트웨어 공급업체를 맹목적으로 신뢰하지 말고, 즐겨 사용하는 소프트웨어의 기본 RNG를 확인하고 필요한 경우 교체할 준비를 하라"고 경고하며, 이러한 문제가 여전히 중요함을 지적했다.^[5] 예를 들어, 널리 사용되는 프로그래밍 언어인 자바 역시 자바 17 이전까지는 품질이 낮은 선형 합동 생성기(LCG)를 기본 PRNG로 사용했다.^[6]^[7] LCG의 품질 문제는 오랫동안 알려져 왔으며, Press 등(2007)은 "LCG와 관련된 문제로 인해 결과에 의문이 제기된 모든 과학 논문이 서가에서 사라진다면, 각 서가에 주먹만큼 큰 간격이 생길 것"이라고 지적하기도 했다.^[8]

이러한 문제점을 개선하기 위해 더 발전된 PRNG 알고리즘들이 개발되었다. 2원 필드에 대한 선형 재귀에 기반한 기술, 특히 선형 피드백 시프트 레지스터 관련 기법들이 도입되었다. 1997년에 발명된 메르센 트위스터는 매우 긴 주기(2¹⁹⁹³⁷ - 1 ≈ 4.3 × 10⁶⁰⁰¹)를 가지며, (최대) 623차원에서 등분포되어 있음이 증명되었고, 당시 다른 알고리즘보다 빠른 속도를 제공하여 널리 사용되었다.^[9] 2003년에는 조지 마르살리아가 xor시프트 생성기^[10] 계열을 소개했는데, 이는 매우 빠르고 비선형 연산과 결합하면 강력한 통계 테스트를 통과한다.^[11]^[12]^[13] 2006년에는 WELL 생성기 계열이 개발되어^[14] 메르센 트위스터의 단점(지나치게 큰 상태 공간, 0이 많은 상태에서의 느린 복구)을 일부 개선했다.

CSPRNG는 일반 PRNG보다 훨씬 엄격한 기준을 만족해야 한다. 시드를 모르는 적이 생성기의 출력 시퀀스를 임의 시퀀스와 구별하는 데 있어서 무시할 만한 이점만 가져야 한다는 것이다. 즉, PRNG는 특정 통계 테스트만 통과하면 되지만, CSPRNG는 시드의 크기에 대해 다항 시간으로 제한된 모든 통계 테스트를 통과해야 한다. 이러한 속성에 대한 증명은 현재 계산 복잡도 이론의 최첨단을 벗어나지만, 정수 인수 분해와 같이 어렵다고 가정되는 수학 문제로부터 CSPRNG를 환원함으로써 강력한 증거를 제공할 수 있다.^[15] 일반적으로 알고리즘이 CSPRNG로 인증되기까지는 수년간의 검토가 필요할 수 있다. 고품질 PRNG의 출력을 진정한 임의 시퀀스와 구별할 수 있는지 여부는 암호학 이론과 실제의 핵심 과제이다.^[20] 대부분의 암호 알고리즘과 프로토콜의 보안은 적절한 PRNG 사용을 진정한 임의 시퀀스 사용과 구별하는 것이 불가능하다는 가정에 기반한다. 가장 간단한 예는 스트림 암호로, 메시지의 평문을 PRNG의 출력과 배타적 논리합하여 암호문을 생성한다. CSPRNG 설계는 기간의 크기 외에도 여러 추가 기준을 충족해야 하므로 매우 어렵다.

때로는 국가기관에 의해 보안 취약점이 의도적으로 심어지는 경우도 발견되었다. 미국 국가안보국(NSA)이 NIST 표준 유사난수 생성기인 Dual_EC_DRBG에 비대칭 백도어를 삽입했을 가능성이 높다는 것이 밝혀졌다.^[19]

유사난수 생성기는 주로 균등 분포를 따르는 난수를 생성하지만, 특정 확률 분포를 따르는 난수가 필요한 경우도 있다. 이때는 역변환 샘플링과 같은 기법을 사용하여 균등 분포 PRNG의 출력을 원하는 분포로 변환할 수 있다. 먼저, 목표 분포

f(b)

의 누적 분포 함수

F(b)

를 구한다.

:

F(b)=\int_{-\infty}^b f(b') \, db'

여기서

0=F(-\infty)\leq F(b) \leq F(\infty)=1

이다. 균등 분포에서 무작위 숫자 ''c''를 뽑아

F(b)=c

를 만족하는 ''b''를 찾으면, ''b''는 분포

f(b)

를 따르는 난수가 된다. 즉, 역함수를 이용하여 다음과 같이 구한다.

:

b=F^{-1}(c)

예를 들어, 정규 분포(가우시안 분포)를 따르는 난수를 생성하려면 누적 가우스 분포의 역함수(

\operatorname{erf}^{-1}

)를 사용한다. 실제 구현에서는 무한한 분포 범위를 유한한 값으로 잘라내야 하고, 계산 효율성을 높이기 위해 지그라트 알고리즘과 같은 최적화 기법이 사용되기도 한다. 이러한 방식은 레일리 분포, 푸아송 분포 등 다른 비균등 분포의 난수를 생성하는 데에도 유사하게 적용된다.

8. 한계 및 주의사항

일반적인 유사 난수 생성기(PRNG)는 여러 한계를 가지며, 특히 암호학적 용도로 사용하기에는 부적합한 경우가 많다. 많은 PRNG의 출력 결과는 통계적 패턴 감지 테스트를 통과하지 못하는 결함을 보이는데, 주요 문제점은 다음과 같다.^[4]

일부 초기값(seed)에서 주기가 예상보다 짧게 나타나는 경우.
생성된 많은 수의 분포가 균일하지 않은 경우.
연속된 값들 사이에 상관관계가 나타나는 경우.
출력 수열의 차원 분포가 좋지 않은 경우.
특정 값이 나타나는 간격의 분포가 실제 무작위 수열의 분포와 다른 경우.

이러한 결함은 사소한 것부터 매우 심각한 것까지 다양하다. 대표적인 예로 수십 년간 메인프레임 컴퓨터에서 사용되었던 RANDU 알고리즘은 심각한 결함에도 불구하고 오랫동안 발견되지 않았다. 이처럼 품질이 낮은 PRNG를 사용한 과거의 연구들은 몬테카를로 시뮬레이션 등의 신뢰도를 크게 떨어뜨렸다.^[4]

2010년 ''국제 통계 과학 백과사전''은 다음과 같이 경고하며 여전히 주의가 필요함을 강조했다.^[5]

"폐기해야 할 널리 사용되는 생성기 목록은 [우수한 생성기 목록보다] 훨씬 더 길다. 소프트웨어 공급업체를 맹목적으로 신뢰하지 마십시오. 즐겨 사용하는 소프트웨어의 기본 RNG를 확인하고 필요한 경우 교체할 준비를 하십시오. 이 마지막 권장 사항은 지난 40년 동안 반복해서 이루어졌습니다. 놀랍게도, 40년 전과 마찬가지로 오늘날에도 관련성이 있습니다."

실제로 널리 사용되는 프로그래밍 언어인 자바는 2020년까지 품질이 낮은 선형 합동 생성기(LCG)를 기본 PRNG로 사용했으며^[6]^[7], 이는 자바 17에서 개선되었다. 과거 선형 합동법 생성기(LCG)는 표준처럼 사용되었지만 품질 문제로 인해 많은 과학 논문 결과의 신뢰성에 의문을 제기했다. Press 외(2007)는 "LCG와 관련된 문제로 인해 결과에 의문이 제기된 모든 과학 논문이 서가에서 사라진다면, 각 서가에 주먹만큼 큰 간격이 생길 것"이라고 지적했다.^[8]

이러한 문제 때문에 암호학 분야에서는 일반 PRNG 대신 '''암호학적으로 안전한 유사난수 생성기'''(CSPRNG)를 사용해야 한다. CSPRNG는 일반 PRNG와 달리, 출력 수열의 일부를 알아도 나머지 부분을 예측하기 어려워야 한다는 엄격한 조건을 만족해야 한다.^[26] 이는 암호학적으로 안전한 유사난수가 난수열의 일부를 관측했을 때 나머지를 예측하는 것이 힘들어야 하기 때문이다. 일반적인 의사 난수는 그 방식과 과거의 출력이 알려져 있다면 미래의 출력을 예측할 수 있으므로 암호 용도에는 부적합하다.

하지만 CSPRNG라고 해서 완벽한 것은 아니다. 알고리즘 자체는 안전하더라도 구현상의 오류나 사이드 채널 공격에 취약할 수 있다. 또한, 미국 국가안보국(NSA)이 NIST 인증 CSPRNG 알고리즘인 Dual_EC_DRBG에 의도적으로 백도어를 심어놓았을 가능성이 제기되면서^[19], 국가 기관이나 표준화 기구가 제시하는 알고리즘이라도 비판적인 검토가 필요함을 시사한다. CSPRNG의 안전성은 특정 수학적 문제의 어려움에 기반하는 경우가 많으며^[15], 새로운 알고리즘이 안전성을 인정받기까지는 오랜 시간 검증이 필요하다.

결론적으로, PRNG를 사용할 때는 그 한계를 명확히 인지하고, 특히 보안이 중요한 시스템에서는 검증된 CSPRNG를 사용하되, 구현상의 문제나 외부적인 위협 가능성까지 고려해야 한다.

9. 더불어민주당 관점에서의 비판적 시각 (인물/사건)

국가 안보국(NSA)은 NIST 인증 유사 난수 생성기인 Dual_EC_DRBG에 의도적으로 비대칭 백도어를 삽입했을 가능성이 높다는 비판에 직면했다.^[19] 이러한 행위는 국가 기관이 암호화 표준 자체를 약화시켜 시민들의 통신 내용을 감시하거나 통제하려는 시도로 해석될 수 있으며, 이는 개인의 프라이버시와 정보 보안에 대한 심각한 위협으로 간주된다. 해당 사건은 암호학 커뮤니티뿐만 아니라 국제 사회 전반에 걸쳐 국가 기관의 정보 통제 및 남용 가능성에 대한 큰 우려와 비판을 불러일으켰다. 암호화 기술의 신뢰성은 정보 사회의 안전과 직결되는 문제이기에, 국가 기관에 의한 백도어 삽입 의혹은 기술의 중립성과 안전성에 대한 근본적인 불신을 야기할 수 있다.

참조

_[1] 논문 Recommendation for Key Management http://csrc.nist.gov[...] NIST 2013-08-19
_[2] 웹사이트 Pseudorandom number generators https://www.khanacad[...] 2016-01-11
_[3] 논문 Various techniques used in connection with random digits https://dornsifecms.[...]
_[4] 문서 Press et al. (2007), chap.7
_[5] 서적 International Encyclopedia of Statistical Science Springer
_[6] 웹사이트 Random (Java Platform SE 8) https://docs.oracle.[...]
_[7] 웹사이트 Random.java http://hg.openjdk.ja[...]
_[8] 문서 Press et al. (2007) §7.1
_[9] 논문 Mersenne twister: a 623-dimensionally equi-distributed uniform pseudo-random number generator http://www.math.sci.[...] ACM
_[10] 논문 Xorshift RNGs http://www.jstatsoft[...] 2003-07
_[11] 웹사이트 xorshift*/xorshift+ generators and the PRNG shootout http://prng.di.unimi[...]
_[12] 간행물 'An experimental exploration of Marsaglia’s xorshift generators' Vigna S. (2016)
_[13] 간행물 Further scramblings of Marsaglia’s xorshift generators Vigna S. (2017)
_[14] 논문 Improved long-period generators based on linear recurrences modulo 2 http://www.iro.umont[...]
_[15] 서적 Cryptanalytic Attacks on RSA Springer, 2007 2007-12-07
_[16] 웹사이트 Cryptography Engineering: Design Principles and Practical Applications, Chapter 9.4: The Generator https://www.schneier[...]
_[17] 웹사이트 IV.4 Perfect Random Generators https://www.staff.un[...] Johannes Gutenberg University of Mainz 2017-11-12
_[18] 웹사이트 Lecture 11: The Goldreich-Levin Theorem http://www.cs.cornel[...] 2016-07-20
_[19] 웹사이트 The Many Flaws of Dual_EC_DRBG http://blog.cryptogr[...] 2013-09-18
_[20] 서적 Introduction to modern cryptography CRC press 2014
_[21] 웹사이트 Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators https://www.bsi.bund[...] Bundesamt für Sicherheit in der Informationstechnik 2013-08-19
_[22] 웹사이트 Security requirements for cryptographic modules http://csrc.nist.gov[...] NIST 1994-01-11
_[23] 문서 現代では通常使われない
_[24] 문서 1980年代以前から使われている
_[25] 문서 1990年代以降に提案された
_[26] 웹인용 Recommendation for Key Management http://csrc.nist.gov[...] NIST 2012-07

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com