[정보보안] 난수 생성기 (Random Number Generator)

1. 난수 생성기 분류

암호에서 가장 중요한 것은 키(Key)이다. 암호 알고리즘에서의 키, 운용모드에서 IV(Initial Vector), 프로토콜의 일시값(nonce) 등에 키가 정말 중요하게 사용된다. 그런데 이 키는 어떻게 생성하는걸까? 바로 이 난수 발생기를 이용해 키를 만들어 낸다.

 

난수는 불특정한 배열 순서를 가지는 불규칙한 임의의 수열을 말한다. 이 난수를 만드는 방법은 크게 세가지로 구분된다.

 

• TRNG (True Random Number Generator, 진 난수 생성기): 비결정적인 실제 물리적인 현상(Entropy Source)를 입력으로 사용하는 진짜 난수 생성기이다. (e.g. 키보드 타이밍, 마우스 움직임, 열 잡음 등)
• PRNG (Pseudo Random Number Generator, 의사 난수 생성기): 고정된 값인 시드(Seed)를 입력받아 결정론적(Deterministic) 알고리즘을 통해 비트열을 생성한다. 시드와 알고리즘을 알면 재현이 가능하기 때문에 의사 난수라고 한다.
• PRF (Pseudo Random Function, 의사 난수 함수): 고정된 길이의 의사 난수 비트열을 생성하며, 주로 문맥 기반의 값을 생성하는 데 활용된다.

	PRNG (전통적 방식)	PRF (함수 방식)
모델	상태 기반 재귀 모델 ($S_{i+1} = f(S_{i})$)	입력-출력 매핑 모델 ($y = f(K, x)$)
계산 방식	Sequential: 이전 단계의 결과가 필수적임	Random Access: 인덱스 입력 시 즉시 계산 가능
주요 특징	스트림 암호 등 연속적 난수 생성에 유리	특정 위치의 난수 추출이나 키 유도 함수에 유리

PRNG와 PRF는 정의 설명만으로 뭐가 다른건지 애매하다. PRNG는 순차적으로 랜덤 넘버를 생성한다. 10번째 난수를 생성하려면 순차적으로 1부터 10까지 실행해야한다. PRF는 난수 형성은 2개의 인수를 넣어서 바로 다이렉트로 10번째 난수를 결정론적으로 임의 접근을 통해 생성할 수 있다. 

 

TRNG를 사용할 수 있으면 가장 좋겠지만 우리는 컴퓨터 상에서 알고리즘 적으로 난수 발생을 구현해야하기 때문에 실제 리얼월드의 물리적인 현상을 활용하기는 어렵다. 따라서 우리는 의사 난수 생성 PRNG, PRF를 암호에 사용하게 된다.

---

2. PRNG 요구사항

PRNG는 다음과 같은 특성이 보장되어야한다.

• 임의성(Randomness): 비트 분포가 균일해야 하며(0과 1의 빈도가 거의 동일), 수열의 부분 집합이 독립적이어야 한다.
• 비예측성(Unpredictability): 이전 비트들을 알더라도 다음 비트를 예측할 수 없어야 하며(전 방향 비예측성), 생성된 값으로부터 시드를 역추적할 수 없어야 한다. (후 방향 비예측성)
• 시드 보안성: Seed 자체가 TRNG에 의해 생성된 예측 불가능한 난수여야 한다.

 

PRNG는 선형성을 가지면 안된다. 선형성을 가지면 계수와 절편을 알면 바로 예측이 가능하기 때문이다. 

과거 초기 선형합동생성기(LCG)의 난수 발생 알고리즘은 아래와 같다.

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

이 방법은 공격자가 일부 출력값만 알아도 파라미터 $a$, $c$, $m$을 유추하여 전체 수열을 결정해버릴 수 있다. 따라서 이 방법은 암호학적으로 취약한 방법이다.

 

그래서 도입된게 CSPRNG라는게 있다. 

CSPRNG (Cryptographically Secure Pseudo Random Number Generator): 암호학적으로 안전한 PRNG

$$ \text{CSPRNG = PRNG + 출력의 비예측성(Unpredictability)} $$

 

CSPRNG에서는 $n$개의 연속된 출력 비트 $S_1, ..., S_n$이 주어졌을 때, 다항 시간내에 $n+1$번째 비트 $S_{n+1}$을 예측할 수 있는 확률이 $1/2$보다 높지 않으면 된다. 비예측성의 세부조건은 아래와 같다.

• 전 방향 비예측성 (Forward Unpredictability): 이전 비트들을 알더라도 다음 출력 비트를 예측할 수 없어야 한다.
• 후 방향 비예측성 (Backward Unpredictability): 생성된 값들로부터 초기값인 시드(Seed)를 유추할 수 없어야 한다.

 

이러한 CSPRNG의 예시로는 Blum Blum Shub (BBS), 운용모드의 카운터 모드 등이 있다.