# 난수 생성기 (Random Number Generator)

## 1. 개요
**난수 생성기(Random Number Generator, RNG)**란 무작위성(Randomness)을 가진 숫자 수열을 생성하는 장치나 알고리즘을 의미한다.

컴퓨터는 기본적으로 입력값이 같으면 항상 동일한 결과값을 출력하는 결정론적(Deterministic) 시스템이다. 그러나 현대의 컴퓨터 과학과 암호학에서는 보안 키 생성, 시뮬레이션, 통계적 샘플링, 게임 로직 구현 등을 위해 예측 불가능한 값이 필수적이다. 따라서 컴퓨터 시스템은 소프트웨어적 알고리즘이나 하드웨어적 물리 현상을 이용하여 '무작위성'을 모사하거나 추출하는 메커니즘을 사용한다.

## 2. 의사 난수 생성기 (PRNG)
**의사 난수 생성기(Pseudo-Random Number Generator, PRNG)**는 초기값인 **시드(Seed)**를 바탕으로 수학적 알고리즘을 적용하여 난수처럼 보이는 수열을 생성하는 방식이다.

시드는 난수 수열의 시작점을 결정하는 값으로, 일반적으로 구현의 편의를 위해 현재 시스템 시간(`time.time()`) 등을 사용한다. 하지만 시스템 시간은 예측 가능하기 때문에 보안이 중요한 환경에서는 취약점이 될 수 있으며, 이를 보완하기 위해 더 복잡한 엔트로피 소스를 시드로 활용한다.

### 2.1 작동 원리 및 특징
PRNG는 실제 무작위가 아니라 정해진 공식에 의해 계산된 값의 나열이다. 따라서 다음과 같은 특성을 갖는다.
- **결정론적 특성**: 동일한 시드 값을 입력하면 항상 동일한 난수 수열이 생성된다.
- **주기성(Periodicity)**: 수열이 무한히 이어지지 않고, 일정 시간이 지나면 다시 처음의 수열로 돌아오는 주기가 존재한다.
- **효율성**: 계산 속도가 매우 빠르며, 메모리 사용량이 적다.

### 2.2 대표적인 PRNG 알고리즘
| 알고리즘 | 설명 | 특징 |
| :--- | :--- | :--- |
| **선형 합동 생성기 (LCG)** | $X_{n+1} = (aX_n + c) \pmod m$ <br>( $a$: 곱셈 계수, $c$: 증분, $m$: 모듈러스) | 구현이 매우 간단하나 주기성이 짧고 통계적 품질이 낮음 |
| **메르센 트위스터 (MT)** | 매우 긴 주기($2^{19937}-1$)를 가지는 알고리즘 | 일반적인 시뮬레이션 및 통계 분석에 널리 쓰이나 암호학적으로는 불안전함 |
| **Xorshift** | XOR 연산과 비트 시프트(Bit Shift) 연산만을 사용하는 방식 | 연산 속도가 극도로 빠르며 가벼운 애플리케이션에 적합함 |

### 2.3 시드 값에 따른 결과 예시 (LCG 알고리즘 가정)
*아래 값은 이해를 돕기 위한 예시 값이며, 사용되는 알고리즘과 파라미터에 따라 달라질 수 있다.*

| 시드 값 (Seed) | 1번째 생성 값 | 2번째 생성 값 | 3번째 생성 값 | 비고 |
| :--- | :--- | :--- | :--- | :--- |
| `12345` | 0.12345 | 0.84211 | 0.45678 | 시드 A의 수열 |
| `12345` | 0.12345 | 0.84211 | 0.45678 | 시드 A와 동일하므로 결과 동일 |
| `67890` | 0.91234 | 0.23156 | 0.77890 | 시드 B의 수열 (결과 다름) |

## 3. 진성 난수 생성기 (TRNG)
**진성 난수 생성기(True Random Number Generator, TRNG)**는 알고리즘이 아닌 외부의 물리적 현상에서 발생하는 예측 불가능한 노이즈를 측정하여 난수를 생성하는 장치이다.

### 3.1 생성 원리
TRNG는 자연계의 불확정성을 이용한다. 대표적인 소스는 다음과 같다.
- **열 잡음(Thermal Noise)**: 저항기 내 전자의 불규칙한 움직임으로 발생하는 전압 변동.
- **방사능 붕괴**: 원자핵이 붕괴하는 시점의 무작위성.
- **광전 효과**: 광자가 감지기에 도달하는 불규칙한 시간 간격.

### 3.2 PRNG와의 차이점
TRNG는 시드 값이 필요 없으며, 이론적으로 주기가 존재하지 않는다. 하지만 하드웨어 장치가 필수적이므로 생성 속도가 느리고, 하드웨어 결함이나 외부 환경(온도, 전자기파)의 영향으로 인해 편향(Bias)이 발생할 수 있다는 단점이 있다.

### 3.3 PRNG vs TRNG 비교
| 구분 | 의사 난수 생성기 (PRNG) | 진성 난수 생성기 (TRNG) |
| :--- | :--- | :--- |
| **기반** | 수학적 알고리즘 | 물리적 현상 |
| **결정론** | 결정론적 (시드 동일 시 결과 동일) | 비결정론적 (매번 다른 결과) |
| **속도** | 매우 빠름 | 상대적으로 느림 |
| **주기성** | 존재함 | 없음 |
| **재현 가능성** | 시드를 통해 재현 가능 | 재현 불가능 |

## 4. 암호학적으로 안전한 의사 난수 생성기 (CSPRNG)
**암호학적으로 안전한 의사 난수 생성기(Cryptographically Secure PRNG, CSPRNG)**는 일반 PRNG의 효율성과 TRNG의 예측 불가능성을 결합한 형태이다.

### 4.1 보안 요구사항
CSPRNG가 되기 위해서는 다음의 조건을 만족해야 한다.
1. **다음 비트 예측 불가능성**: 이전의 출력값들을 모두 알고 있더라도, 다음에 나올 비트를 50% 이상의 확률로 예측할 수 없어야 한다.
2. **상태 복구 불가능성**: 내부 상태(Internal State)가 일부 노출되더라도, 이전의 출력값을 역추적하여 알아낼 수 없어야 한다.

### 4.2 암호학적 활용
암호화 키, **솔트(Salt)**(해시 함수 입력 시 무작위성을 더해 레인보우 테이블 공격을 방지하는 값), **초기화 벡터(IV)**(블록 암호화에서 동일 평문이 동일 암호문이 되지 않도록 하는 값)를 생성할 때는 반드시 CSPRNG를 사용해야 한다. 일반 PRNG를 사용할 경우 공격자가 시드 값을 추측하여 암호 키를 복구할 수 있기 때문이다.

### 4.3 언어별 구현 비교 예시
```python
import random
import secrets # CSPRNG 모듈

# [일반 PRNG] - 예측 가능, 보안 용도로 부적합
# 내부적으로 메르센 트위스터 알고리즘 사용
# 결과값: 0.0 ~ 1.0 사이의 float (부동소수점)
unsafe_val = random.random() 

# [CSPRNG] - 예측 불가능, 보안 용도로 적합
# OS의 엔트로피 소스를 활용
# 결과값: 지정된 길이의 무작위 16진수 문자열 (string)
safe_val = secrets.token_hex(16) 
```

## 5. 난수 생성기의 보안 취약점과 대책

### 5.1 주요 취약점
- **취약한 시드 선택**: 시스템 시간(`time()`)과 같이 예측 가능한 값을 시드로 사용할 경우, 공격자가 생성 시점을 추측하여 난수 수열을 그대로 재현할 수 있다.
- **알고리즘의 한계**: LCG와 같이 선형적인 구조를 가진 알고리즘은 소수의 출력값만으로 다음 값을 수학적으로 계산해낼 수 있다.

### 5.2 엔트로피 풀(Entropy Pool)과 수집
운영체제는 시스템 내의 불규칙한 이벤트(키보드 타이핑 간격, 마우스 움직임, 디스크 I/O 인터럽트 시간 등)를 수집하여 **엔트로피 풀(Entropy Pool)**이라는 저장소에 쌓아둔다. CSPRNG는 이 풀에서 추출한 고품질의 무작위 데이터를 시드로 사용하여 보안성을 높인다. 수집된 엔트로피가 부족할 경우, 시스템은 새로운 이벤트가 발생할 때까지 대기하거나 기존 엔트로피를 확장하여 난수를 생성함으로써 무작위성을 유지한다.

### 5.3 운영체제별 난수 생성 장치
대부분의 현대 OS는 커널 수준에서 엔트로피를 관리하며 인터페이스를 제공한다.
- **Linux/Unix**: 
    - `/dev/random`: 엔트로피가 부족하면 값이 생성될 때까지 블로킹(Blocking)되어 매우 안전하지만 느림.
    - `/dev/urandom`: 엔트로피가 부족해도 PRNG를 통해 값을 계속 생성(Non-blocking). 대부분의 암호학적 용도에 권장됨.
- **Windows**: `BCryptGenRandom` API 또는 `CryptGenRandom` 함수를 통해 CSPRNG 값을 제공한다.

### 5.4 난수 품질 측정 방법 및 도구
생성된 난수가 얼마나 무작위한지를 검증하기 위해 통계적 테스트를 수행한다.
- **Diehard 테스트**: 난수의 분포, 패턴, 주기성 등을 검사하는 매우 엄격한 테스트 세트이다.
- **Dieharder**: Diehard 테스트를 개선하고 확장한 도구로, 더 넓은 범위의 테스트 케이스를 제공하며 현대적인 난수 생성기 검증에 널리 사용된다.
- **NIST SP 800-22**: 미국 표준기술연구소에서 정의한 통계적 테스트 스위트로, 암호학적 난수 생성기 검증의 표준으로 사용된다.

## 6. 요약 및 비교

| 구분 | PRNG | TRNG | CSPRNG |
| :--- | :--- | :--- | :--- |
| **생성 방식** | 수학적 알고리즘 (결정론적) | 물리적 현상 (비결정론적) | 엔트로피 기반 알고리즘 |
| **예측 가능성** | 시드 알면 예측 가능 | 예측 불가능 | 예측 불가능 (수학적 증명) |
| **생성 속도** | 매우 빠름 | 느림 | 빠름 |
| **주기성** | 존재함 | 없음 | 사실상 없음 (매우 김) |
| **주요 용도** | 게임, 일반 시뮬레이션 | 하드웨어 보안 모듈(HSM) | 암호 키, 솔트, 세션 ID 생성 |

분류: 컴퓨터 과학 / 암호학 / 알고리즘