1. 난수 생성(Random Number Generation, RNG)의 구분
ㅇ TRNG (True RNG, 순수 난수 생성)
- 물리적 자연현상의 예측하기 어려운 물리적 잡음,변동을 이용하여 난수를 생성
- 例) 동전,주사위 던지기, 특별하게 설계된 전자적 장치에 의함 (백색소음 발생 등)
ㅇ PRNG (Pseudo RNG, 의사 난수 생성)
- 확률 알고리즘에 의함 (실제 난수 생성이 아닌 의사 난수 생성 임)
. 본질적으로 결정론적 알고리즘이지만,
. 생성된 수열이 통계적으로 무작위처럼 보이도록 설계됨
* 여기서, 의사 난수 이란?
. 비록 완전한 랜덤은 아니지만,
. 길이가 아주 길고, 순환(반복)적인 수열을 발생시키며,
. 아주 긴 수열에서 거의 완벽한 랜덤(무작위) 수열에 가까운 통계적 특성을 보이는 등
2. 의사 난수의 필요 특성
ㅇ 균등성 (Uniformity)
- 난수의 값이 특정 범위에 편중되지 않고 균등하게 분포
ㅇ 독립성 (Independence)
- 서로 다른 난수 사이에 통계적으로 유의미한 의존성이 없어야 함
ㅇ 재현성 (Reproducibility)
- 동일한 Seed를 사용하면 동일한 난수열을 재생성할 수 있음
- 시뮬레이션 및 프로그램 시험에서 매우 중요한 특성
ㅇ 긴 주기 (Long Period)
- 동일한 수열이 다시 반복되기까지 가능한 한 긴 주기를 가져야 함
ㅇ 낮은 상관성 (Low Correlation)
- 연속적인 난수 사이에 뚜렷한 상관관계가 나타나지 않아야 함
ㅇ 통계적 무작위성 (Statistical Randomness)
- 다양한 통계적 검정에서 무작위 수열과 구별하기 어려운 특성을 보여야 함
ㅇ 예측 불가능성 (Unpredictability)
- 현재까지 관찰된 출력으로부터 이후의 출력이나 내부 상태를 쉽게 예측할 수 없어야 함
- 특히 CSPRNG에서 중요
3. 의사 난수의 생성 방법
ㅇ 선형 합동에 의한 방법 (LCG, Linear Congruential Generator,선형 합동 생성기)
- 정의식 (알고리즘)
. Xn+1 = (a Xn + c) mod m, (n ≥ 0)
- 선택 가능 모수 넷
. X0 : 종자 (Seed) (0 ≤ X0 ≤ m)
. a : 승수 (Multiplier) (0 ≤ a ≤ m)
. c : 증분 (0 ≤ c ≤ m)
. m : 계수 (Modulus) (m ≥ 0)
- 호출 형태
. 가장 처음에는 시드(seed)라는 초기값을 입력으로 하여, 난수 생성 알고리즘을 호출하고,
. 그 이후에는 이전에 만들어낸 수를 입력으로 하여, 일련의 난수 생성 알고리즘을 호출하게 됨
- 생성값 : 통상, [0,1) 사이에 일련의 실수를 생성 함
. 즉, Ui = Xi / m
- 특징
. 그이전 난수 Xn으로부터 그다음 난수 Xn+1을 만들어내도록 함
. 항상 작업 시작 전에, 시드(seed)라는 초기값 X0이 필요함
.. 같은 시드에 대해, 항상 예측가능한, 같은 결과를 만들어 냄
. 반복 구간(한번 나온 수열이 계속 되풀이 됨)이 있게됨
.. 따라서, 선택 가능 모수(a,m,c)를 잘 선택해 두어야 함
. 결국, 최장 반복 구간을 얻고자 함
- 1949년 데릭 헨리 레머(Derrick Henry Lehmer)에 의해 최초 제안
ㅇ LFSR (선형귀환이동레지스터)에 의한 방법
- PRBS를 발생시키는 가장 편리하고 빠른 방법
- 이동 레지스터의 일부 비트를 선형적으로 조합하여 새로운 비트를 생성하는 방식
- 간단한 하드웨어로 매우 빠르게 구현 가능
- PRBS (의사 난수 이진 수열) 발생에 널리 사용
- 통신 분야에서는, 오류검출, 스크램블링, 시험 신호 발생 등에 활용
- 적절한 귀환 다항식을 사용하면, 최대길이 수열(Maximal-Length Sequence)을 생성 가능
ㅇ 기타 PRNG
- Mersenne Twister (MT)
. 매우 긴 주기를 갖고 통계적 특성이 우수
. 시뮬레이션,수치계산 등에 널리 사용
. 암호학적 난수 생성에는 부적합
- Xorshift / xoroshiro / xoshiro 계열
. XOR, 시프트 등의 단순한 연산을 이용
. 빠르고 구현이 간단
- PCG (Permuted Congruential Generator)
. LCG 기반 상태 전이에 출력 변환을 결합하여 난수 품질을 개선
- CSPRNG (Cryptographically Secure PRNG, 암호학적 의사 난수 생성기)
. 공격자가 출력값을 관찰하더라도 다음 난수를 쉽게 예측할 수 없도록 설계
. 암호키, 토큰, 인증값 등 보안 용도에 사용
. 일반적인 PRNG와 달리 통계적 무작위성뿐 아니라 예측불가능성이 중요
4. 의사 난수의 검정
※ 실제 난수와 의사 난수 간에 유의미한 차이를 측정하여 무작위성을 검정하게 됨
ㅇ 검정 목적
- 생성된 수열이 통계적으로 무작위 수열에 충분히 가까운지 확인
ㅇ 주요 검정 대상
- 분포의 균등성 : 특정 값이나 구간에 치우치지 않는가
- 독립성 : 앞의 값이 뒤의 값에 통계적으로 영향을 주지 않는가
- 상관성 : 값들 사이에 유의미한 상관관계가 존재하지 않는가
- 패턴 : 반복,군집,주기 등의 비정상적인 패턴이 나타나지 않는가
- 주기 : 충분히 긴 주기를 갖는가
ㅇ 대표적인 통계적 검정
- 빈도 검정 (Frequency Test)
- 카이제곱 검정 (Chi-Square Test)
- 자기상관 검정 (Autocorrelation Test)
- Runs Test
- Entropy 관련 검정 등
※ 통계적 검정을 통과했다고 해서, 해당 수열이 진정한 의미에서 완전한 난수임을 증명하는 것은 아님
- 단지 주어진 검정에서 무작위성을 저해하는 통계적 특성이 발견되지 않았음을 의미