8장. 난수 비트 생성과 스트림 암호

개요

PRNG/TRNG 원리, 선형 합동 생성기, BBS, 블록 암호 기반 PRNG, 스트림 암호, RC4, 진난수 생성기, Intel DRNG

난수 비트 스트림은 키 생성, 암호화, 논스 등 다양한 보안 응용에서 필수적이다. 이 장에서는 의사난수 생성기(PRNG), 블록 암호 기반 PRNG, 스트림 암호(RC4), 진난수 생성기(TRNG)를 다룬다.

학습 목표

• 난수의 무작위성과 예측 불가능성 개념을 설명한다.
• TRNG, PRNG, PRF의 차이를 이해한다.
• 블록 암호를 이용한 PRNG 구성 방법을 설명한다.
• 스트림 암호와 RC4의 구조를 개관한다.

---

8.1 의사난수 생성 원리

난수의 용도

• 키 분배 및 상호 인증의 논스(nonce)
• 세션 키 생성
• RSA 공개키의 소수 생성
• 스트림 암호의 키스트림 생성

난수의 두 가지 요구사항

요구사항	설명
무작위성 (Randomness)	균일 분포 + 독립성
예측 불가능성 (Unpredictability)	이전 값으로 다음 값 추론 불가

TRNG vs PRNG vs PRF

유형	입력	출력	결정론적
TRNG	물리적 엔트로피 소스	난수 비트 스트림	아니오
PRNG	시드(seed)	개방형 의사난수 비트 스트림	예
PRF	시드 + 문맥 특정 값	고정 길이 의사난수 값	예

PRNG와 PRF는 동일한 알고리즘을 사용할 수 있으며, 출력 길이만 다르다.

PRNG 요구사항

무작위성 (NIST SP 800-22):

• 균일성: 0과 1의 출현 확률이 각각 $1/2$
• 확장성: 부분 수열도 무작위성 테스트 통과
• 일관성: 다양한 시드에서 일관된 결과

예측 불가능성:

• 순방향: 이전 비트로 다음 비트 예측 불가
• 역방향: 생성된 값으로 시드 추론 불가

시드: TRNG로 생성하는 것이 권장됨 (SP 800-90A)

---

8.2 의사난수 생성기

선형 합동 생성기 (Linear Congruential Generator)

$X_{n+1} = (aX_n + c) \bmod m$

파라미터	설명
$m$	모듈러스 ($m > 0$)
$a$	승수 ($0 < a < m$)
$c$	증분 ($0 \leq c < m$)
$X_0$	시드 ($0 \leq X_0 < m$)

권장 설정: $m = 2^{31} - 1$ (소수), $a = 7^5 = 16807$, $c = 0$

취약점: 파라미터를 알면 $X_0, X_1, X_2, X_3$으로 $a, c, m$을 역산 가능 → 암호학적으로 안전하지 않음

BBS (Blum Blum Shub) 생성기

암호학적으로 안전한 PRNG(CSPRBG)이다.

알고리즘:

1. $p \equiv q \equiv 3 \pmod{4}$인 두 큰 소수 선택
2. $n = p \times q$
3. $\gcd(s, n) = 1$인 시드 $s$ 선택

$X_0 = s^2 \bmod n$ $X_i = X_{i-1}^2 \bmod n$ $B_i = X_i \bmod 2 \quad \text{(최하위 비트 추출)}$

보안: $n$의 소인수분해 난이도에 기반. next-bit test를 통과하는 것이 증명됨.

---

8.3 블록 암호 기반 PRNG

CTR 모드 PRNG

while (len(temp) < 요청 비트 수):
    V = (V + 1) mod 2^128
    output_block = E(Key, V)
    temp = temp || output_block

OFB 모드 PRNG

while (len(temp) < 요청 비트 수):
    V = E(Key, V)
    temp = temp || V

ANSI X9.17 PRNG

3중 DES(EDE)를 사용하는 강력한 PRNG이다.

$R_i = \text{EDE}([K_1, K_2],\; V_i \oplus \text{EDE}([K_1, K_2],\; DT_i))$ $V_{i+1} = \text{EDE}([K_1, K_2],\; R_i \oplus \text{EDE}([K_1, K_2],\; DT_i))$

• $DT_i$: 현재 날짜/시간 값
• $V_i$: 시드 값
• $R_i$: 의사난수 출력

NIST CTR_DRBG

SP 800-90A에서 정의한 카운터 모드 기반 DRBG이다. Intel DRNG에서 사용된다.

파라미터	3DES	AES-128	AES-192	AES-256
outlen	64	128	128	128
keylen	168	128	192	256
seedlen	232	256	320	384
reseed_interval	$\leq 2^{32}$	$\leq 2^{48}$	$\leq 2^{48}$	$\leq 2^{48}$

동작 단계:

1. 초기화: 엔트로피 소스에서 seedlen 비트를 받아 Key와 V 생성
2. 생성: CTR 모드로 의사난수 블록 생성
3. 갱신: reseed_interval에 도달하면 새 엔트로피로 Key와 V 재생성

---

8.4 스트림 암호

구조

키를 PRNG에 입력하여 **키스트림(keystream)**을 생성하고, 평문과 바이트 단위로 XOR한다.

$C = P \oplus k \qquad P = C \oplus k$

• One-Time Pad와 유사하나 진난수 대신 의사난수 사용
• 동일 키로 두 메시지를 암호화하면 $C_1 \oplus C_2 = P_1 \oplus P_2$로 평문 노출 위험

설계 고려사항

1. 긴 주기: 키스트림의 반복 주기가 길어야 함
2. 통계적 무작위성: 0/1 균등 분포, 256개 바이트 값 균등 출현
3. 충분한 키 길이: 128비트 이상 권장

블록 암호 vs 스트림 암호

특성	스트림 암호	블록 암호
속도	일반적으로 빠름	AES HW 가속 시 빠름
코드 크기	작음	상대적으로 큼
키 재사용	위험	가능
적합한 응용	데이터 스트림, 통신 채널	파일 전송, 이메일, DB

---

8.5 RC4

1987년 Ron Rivest가 설계한 바이트 지향 스트림 암호이다.

S 벡터 초기화

// 초기화
for i = 0 to 255:
    S[i] = i
    T[i] = K[i mod keylen]

// 초기 순열
j = 0
for i = 0 to 255:
    j = (j + S[i] + T[i]) mod 256
    Swap(S[i], S[j])

스트림 생성

i, j = 0
while (true):
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    Swap(S[i], S[j])
    t = (S[i] + S[j]) mod 256
    k = S[t]    // 키스트림 바이트

특징

항목	내용
키 길이	1256바이트 (82048비트)
상태	256바이트 순열 배열 S
주기	$> 10^{100}$
속도	출력 바이트당 8~16 기계어 연산

RC4의 보안

• WEP 프로토콜에서의 취약점은 RC4 자체가 아닌 키 생성 방식의 문제
• [ALFA13]의 키스트림 편향(bias) 공격으로 반복 암호화된 평문 복구 가능
• IETF RFC 7465: TLS에서 RC4 사용 금지
• NIST SP 800-52: 정부 용도 RC4 사용 금지

---

8.6 진난수 생성기 (TRNG)

엔트로피 소스

비결정론적 물리 현상을 이용하여 난수를 생성한다.

소스	예시
전자적 잡음	열 잡음, 결합 인버터 회로
음향/영상 입력	마이크 잡음, 렌즈 캡 씌운 카메라
디스크 드라이브	공기 난류에 의한 회전 속도 변동
사용자 입력	키 입력 타이밍, 마우스 움직임

PRNG vs TRNG 비교

특성	PRNG	TRNG
효율성	높음	낮음
결정론	결정론적	비결정론적
주기성	주기적 (매우 긴 주기)	비주기적

컨디셔닝 (Conditioning)

TRNG 출력의 편향(bias)을 제거하고 엔트로피를 극대화하는 처리이다.

방법	설명
해시 함수	$m$비트 입력을 $n$비트 해시로 변환 ($m \geq n$)
블록 암호	AES 등으로 입력 비트를 스크램블

건강 테스트 (Health Testing)

SP 800-90B에서 권장하는 엔트로피 소스 모니터링 테스트이다.

반복 계수 테스트 (Repetition Count Test):

• 동일 값이 연속 $C$번 이상 나타나면 오류 보고
• $C = \lceil 1 + \frac{-\log(W)}{H} \rceil$, $W$: 허용 오탐 확률, $H$: 최소 엔트로피

적응 비율 테스트 (Adaptive Proportion Test):

• $N$개 연속 샘플에서 특정 값의 빈도가 $C$회 이상이면 오류 보고

Intel DRNG

Intel 프로세서 칩에 내장된 하드웨어 난수 생성기이다.

단계	구성	출력
엔트로피 소스	결합 인버터 쌍 + 열 잡음	512비트 단위, 4Gbps
컨디셔너	AES CBC-MAC (CMAC)	256비트, 편향 제거
DRBG	AES CTR_DRBG	128비트 단위, 시드당 최대 511블록

명령어:

• RDRAND: DRBG 출력에서 16/32/64비트 의사난수 획득
• RDSEED: 컨디셔너 출력에서 하드웨어 생성 시드 획득

---

주요 용어

한국어	영어	설명
의사난수 생성기	PRNG	시드 기반 결정론적 난수 생성
의사난수 함수	PRF	고정 길이 의사난수 출력
진난수 생성기	TRNG	물리적 엔트로피 기반 난수 생성
시드	Seed	PRNG 초기 입력값
키스트림	Keystream	스트림 암호의 의사난수 출력
선형 합동 생성기	Linear Congruential Generator	$X_{n+1} = (aX_n + c) \bmod m$
BBS 생성기	Blum Blum Shub	소인수분해 난이도 기반 CSPRBG
CTR_DRBG	CTR_DRBG	CTR 모드 기반 NIST 표준 DRBG
스트림 암호	Stream Cipher	키스트림과 XOR로 암호화
RC4	RC4	바이트 지향 순열 기반 스트림 암호
엔트로피 소스	Entropy Source	물리적 무작위성 제공 장치
컨디셔닝	Conditioning	편향 제거 및 엔트로피 극대화 처리
편향	Skew/Bias	0과 1의 불균등 분포