Random Number Generator : 난수발생기

난수 혹은 의사 난수 생성은 많은 암호 함수에서 필요합니다. 

필수 조건은 스트림이 예상할 수 없는 수여야 합니다. 

 

 

의사 난수 생성의 원리

 

 난수(Random)란 특정한 배열 순서나 규칙을 가지지 않는 연속적인 임의의 수입니다. 18047320974109470 이렇게 아무런 규칙을 가지고 있지 않습니다. 

 

의사난수(Pseudo random number) 는 우리가 보기엔 규칙이 없어 보이지만 실제로는 긴 주기를 가지고 있는 즉 난수처럼 보이는 난수가 아닌 수 인 것 입니다. Pseudo code 도 실행은 안되는 코드 뼈대같은 거죠?  

 

1.임의성 

  1) 균일분포 : 0과 1의 출현 빈도 거의 동일해야함

  2) 독립성 : 수열의 어느 부분을 보고 전이나 후의 수열을 예측할 수 없어야함 -> 즉 연관성이 없어야함

ex) 2 4 6 8 10 다음 수는?  :12 

이와 같으면 안됩니다! 이건 독립적이지 않은 겁니다. 

 

2.비예측성

  수열의 잇따른 다음 수의 순서에 대해 예측이 불가능해야함. (독립성과 비슷한 맥락이네요)

 

 

 

난수 생성기

1.TRNG(True Random Number Generator) 

이름에서 느껴지듯이 찐, 난수 생성기입니다. 

보통 자연소리(키보드 입력이나 전파라든가 시스템 클럭의 순간 값) 같은 랜덤한 소스를 입력에 사용합니다.

 

대개 밑에 나오는 PRNG의 Seed 값을 만드는데 사용됩니다. 

 

2.PRNG(Pseudo Random Number Generator)

의사난수 발생기입니다. 

고정값 Seed를 입력받아 알고리즘을 이용해 출력 비트열을 생성합니다. 

만약 Seed 값을 사용자가 안다면 쉽게 뚫릴 수 있습니다. 그렇기 때문에 TRNG를 사용하는 거겠죠?

참고) C언어의 srand() 함수도 이 Seed를 이용합니다. 

 

3.PRF(Pseudo Random Function)

고정된 길이의 의사 난수 비트열을 생산하는데 사용. 

PRNG와 다른 점 -> Seed 뿐만 아니라 외부의 값을 사용 

 

 

 

 

PRNG 의 요구 사항 

-Seed 를 알지 못하는 공격자가 난수열을 예측할 수 없어야함 

-임의성(Randomness)

  1) 균일성 : 0과 1 은 거의 동일하게 존재

  2) 확장성 : 무작위로 추출되어도 랜덤해야함 -> 어떤 길이라도 랜던

  3) 일관성 : 생성기의 동작은 초기값 전반에 대해 일관

-비예측성 

-시드요구사항 

  1) Seed 예측 불가능(TRNG)

  2) Seed 는 난수 또는 의사난수

 

 

 

 

Linear Congruential generator 선형합동생성기 -> modular 연산 

 

선형 합동 방법

 생성된 수의 노출 가능성 

공격자가 선형 합동 알고리즘 사용과 파라미터를 알 경우 형성된 한 수만 알아도 나머지 수 파악 가능

선형합동 알고리즘 사용 여부만 알아도 나머지 수 알 수 잉ㅆ슴

 

해결 방법

 - 내부 시스템 클럭 사용 -> 매번 새로운 Seed 

 - 현재 클럭 값에 난수 더해 mod m 의 값 사용

 

다음은 Seed 값을 이용해 PRNG를 쉽게 복호화 해버리는 예제입니다. 

 

위와 같이 연립을 이용해 A,B의 값을 구할 수 있음

 

이렇듯 PRNG 의 보안성이 떨어지기 때문에 암호학적으로 안전한 의사난수 : CSRPNG 를 사용합니다. 

 

CSPRNG = PRNG + 'OUTPUT MUST BE UNPREDICTABLE"

의사 난수 생성기에서 보안성을 높인 겁니다. 

 

 

예시) Blum Blum Shub 생성기 - CSPRNG의 초기 사례

P,Q 는 Prime Number / N은 open 된 number / Bi 하위 비트가 0인지 1인지 출력

즉 한번에 한 비트 밖에 난수를 생성하지 못한다. -> 느림. 

 

BBS 의 속도가 너무 느리기 때문에 그에 대한 해결점을 ㅗ

 

CSPRNG by block cipher 

카운터를 통해  session keys from master key 

Pseudorandom Number Generation from a counter 

다음은 이에 대한 미국 표준입니다. 

 

 

 

핵심 

1.TRNG에 대한 이해

2. CSPRNG 왜 필요한지

3. BBS 안 쓰고 BLOCK CIPHER 쓰는 이유 -> 빠르니깐

4. PRNG 가 무엇인지 특성 잘 이해하기

 

그럼 오늘의 수업 정리를 마치겠습니다!

좋아요와 구독 눌러주세요ㅎㅎ