[정보보안] 4. 난수

1. 난수란?

확률적인 현상의 표현이다. 확률변수라고도 한다.

2. 난수의 조건

1. 주기성이 없을 것: 예측이 불가능할 것
2. 무작위성: 같은 확률이 아닐 것
3. 재현 불가능성: 같은 난수가 다시 나타나지 않을 것(이를 진성난수라고 함)
4. 계산시간이 짧을 것(컴퓨터 수행시간)

• 일양성과 독립성
  • 일양성: 확률의 값은 0과 1 사이의 값인 성질
  • 독립성: 앞에 나온 확률과 무관한 성질

3. 난수 발생 방법

• 디지털 컴퓨터에 의한 방법
• 프로그램에 의한 방법

디지털 컴퓨터에 의한 방법

• mid square method(MSM: 중앙제곱방식)
• mid product method(MPM: 중앙승산방식)
• k product method(KPM: 상수승산방식)
• 3가지 방법 모두 우수한 방법이다.

프로그램에 의한 방법

• Congruential Generator

4. 난수의 발생 과정

Mid Square Method

• 폰 노이만이 제안한 방법이다.

1. 난수로 원하는 자리수 크기의 숫자를 임의로 선정한다.
2. 그 수를 제곱한다.
3. 난수를 발생시키기 원하는 자리수만큼 가운데 n을 선택하여 난수로 사용한다.
4. 2단계로 돌아가서 반복한다.

• 예제
  • 25를 선택하여 난수 5개를 발생시켜 보시오.
    1. 25 * 25 = 0625 → 0.62
    2. 62 * 62 = 3844 → 0.84
    3. 84 * 84 = 7056 → 0.05
    4. 05 * 05 = 0025 → 0.02
    5. 02 * 02 = 0004 → 0.00
    • 이렇게 난수가 갑자기 뚝 떨어지는 현상을 degenerative 현상이라고 한다.

Mid Product Method

1. 2개의 초기 숫자를 선정하여 곱한다.
2. 곱한 결과 숫자의 가운데 부분을 100으로 나누어 난수로 사용한다.
3. 2개의 숫자 중 앞의 것을 버리고 2단계 과정에서 얻어진 숫자와 대체한다.
4. 2단계로 돌아가서 반복한다.

• 예제
  • 27, 88을 선택하여 난수 5개를 발생시켜보시오.
    1. 27 * 88 = 2376 → 0.37
    2. 88 * 37 = 3256 → 0.25
    3. 37 * 25 = 0925 → 0.92
    4. 25 * 92 = 2300 → 0.30
    5. 92 * 30 = 2760 → 0.76

K Product Method

Mid Product Method의 과정 중 2단계에서 새로운 상수를 지정하지 않고 상수 하나를 고정시켜서 사용한다.

• 예제
  • 27, 88을 선택하여 난수 5개를 발생시켜보시오(27을 상수로 고정).
    1. 27 * 88 = 2376 → 0.37
    2. 27 * 37 = 0999 → 0.99
    3. 27 * 99 = 2673 → 0.67
    4. 27 * 67 = 1809 → 0.80
    5. 27 * 80 = 2160 → 0.16

Additive Congruential Generator, ACG(가산 콘그루엔셜 방법)

1. 임의로 선정된 n개의 숫자가 있다.
2. 이 수들과 나누어서 나머지를 사용할 숫자 m을 선정한다(mod m).
3. 임의로 선정된 n개의 숫자 중 처음과 마지막을 더하고 m으로 나누어 나온 나머지를 사용한다.

$$X_{n+1}=X_{n+i-1}+X_i \bmod{m}$$

• 예제
  • 다음의 수에서 난수 12개를 발생시키고 난수의 안정도를 해석하시오.
    • 5, 3, 8, 9, 1, m = 10
    1. 주어진 수를 mod 10 하여 세팅한다. → 0.5, 0.3, 0.8, 0.9, 0.1
    2. 이후로 맨 처음과 맨 뒤 수를 더해가면서 다음 난수를 생성한다.
       1. (5 + 1) mod 10 = 6 → 0.6
       2. (3 + 6) mod 10 = 9 → 0.9
       3. (8 + 9) mod 10 = 7 → 0.7
       4. (9 + 7) mod 10 = 6 → 0.6
       5. (1 + 6) mod 10 = 7 → 0.7
       6. (6 + 7) mod 10 = 3 → 0.3
       7. (9 + 3) mod 10 = 2 → 0.2
       → 0.5, 0.3, 0.8, 0.9, 0.1, 0.6, 0.9, 0.7, 0.6, 0.7, 0.3, 0.2

Linear Congruential Generator, LCG(선형 콘그루엔셜 방법)

• Hull, De Bull이 제안했다.

1. 하나의 초기 숫자를 설정한다.
2. 3개의 상수에 의한 수식을 대입하여 난수를 발생시킨다.
   • 조건 - $a<m, c<m,0<m$
3. $$X_i=(aX_{i-1}+C)\bmod{m},\
   R_i=X_i/m$$

• 예제
  • 다음의 조건에서 난수 4개를 발생시키고 난수의 안정도를 해석하시오.
    • $m=16, a=5, c=3, X_0=7$
    1. $X_1=(5*7+3)\bmod{16}=6, R_1=6/16=0.375$
    2. $X_2=(5*6+3)\bmod{16}=1, R_2=1/16=0.063$
    3. $X_3=(5*1+3)\bmod{16=8, R_3=8/16=0.500}$
    4. $X_4=(5*8+3)\bmod{16=11, R_4=11/16=0.6875}$

5. 난수의 안정도 검증

1. Chi-square 검증

• 어떤 분포든 제한 없이 적용할 수 있고 사용이 쉽다.
• 도수 분서 작성 시 계급구간이 너무 크다는 단점이 있다.
• 사용되지 않는다.

2. Kolmogorov-Smirnov 검증

일양성에 대한 검증을 하는 방법이다.

1. 발생된 난수를 작은 것부터 크기 순으로 나열한다.
2. D의 값을 구한다.
3. $$D^+=\max(\frac{i}{N}-R_i)\
   D^-=\max(R_i-\frac{(i-1)}{N})$$
4. 검증 통계랑인 D를 구한다.
5. $$D=\max[D^+,D^-]$$
6. 유의수준(임계값)과 난수의 개수에 대한 K-S 표를 이용한다.
7. 적합성 검증과 판단을 수행한다.
   • $D>D_a$ → 난수 불안정
   • $D<D_a$ → 난수 안정

• K-S 테이블

• 

• 예제
  • 난수 0.44, 0.81, 0.14, 0.05, 0.93, a = 0.05일 때 안정도를 구하시오.
    1. 난수들을 크기 순으로 나열한다. → 0.05, 0.14, 0.44, 0.81, 0.93
    2. D의 값을 구한다.
       • $D^+=\max{(\frac{1}{5}-0.05, \frac{2}{5}-0.14, \frac{3}{5}-0.44, \frac{4}{5}-0.81, \frac{5}{5}-0.93)}$
       • $D^+=\max{(0.15, 0.26, 0.16, -, 0.07)}=0.26$
       • $D^-=\max{(0.05-\frac{0}{5},0.14-\frac{1}{5},0.44-\frac{2}{5},0.81-\frac{3}{5},0.99-\frac{4}{5})}$
       • $D^-=\max{(0.05, -, 0.04, 0.21, 0.13)} = 0.21$
       • $D=\max{(D^+, D^-)}=0.26$
       • $n=5, a=0.05$ 이므로 K-S 표에서 임계값을 찾으면 0.565이다.
       • $D=0.26, D_a=0.565$ 이므로 이 난수들은 안정된 상태이다.