Pseudorandom Numbers generation의 원리
Random Numbers(난수)가 사용되는 곳들
- Key distribution
- Session key generation
- symmetric stream encryption에서 bit stream 생성
- RSA public-key encryption 알고리즘에서 key 생성
난수의 특성
- Randomness
- Uniform distribution: 나오는 값들의 분포가 동일 -> 0과 1에서 각각의 개수(분포)가 동일해야 한다.
- Independence: 긴 sequence를 봤을 때, 부분 부분 간의 관계성이 없어야 한다.
- Unpredictability
- 앞에서 동전 앞이 나와도, 다음에 뭐가 나올지 몰라야 한다.
- Forward unpredictabiliy: 지금 나온 값을 봐도, 다음에 나올 값을 몰라(예측할 수 없어)야 한다.
- Backward unpredictabiliy: 지금 나온 값을 보고, seed를 예측할 수 없어야 한다.
Pseudorandom Numbers
완전히 랜덤 하게 출력하기는 어려워서, 마치 난수처럼 보이는 pseudorandom number를 사용한다.
seed를 넣어서 deterministic 한 알고리즘을 돌림.
TRNG(True Random Number Generator)
진짜 난수 생성기 -> 진짜 랜덤
물리적인 환경에서 가져온 entropy source를 사용함.
- 하드디스크가 회전하면서 전자기적 움직임(오류를 포함), 마우스 움직임, 시스템 시간 등을 사용 -> seed로 사용
- 이러한 아날로그 source를 binary output으로 변환하여 사용한다.
bias 처리 과정이 필요할 수 있다.
- 동전을 던지는데, 실제로 앞면이 나올 확률이 더 높다면, 이런 비율을 조정해 줘야 한다.
NIST SP 800-90B
PRNG(Psedorandom Number Generator)
Deterministic algorithm
- input이 정해지면 output이 정해짐
- 즉, seed 값을 잘 보호해야 함.
NIST SP 800-90A에 정의됨
PRF(Pseudorandom Function)
PRNG는 반복해서 계속 stream을 생성하지만, PRF는 필요한 만큼의 bit만 생성
Randomness와 Unpredictability를 측정할 테스트
- Frequency test: 0과 1의 개수 카운트
- Runs test: 연속되어 나오는 길이(예: 11112)를 제한
- Maurer's universal statistical test: 정보 손실 없이 sequence 압축
Pseudorandom Numbers generators
PRNG 설계
randomizing input 데이터 효과를 이용하는 암호 알고리즘
- 대칭 블록 암호
- 비대칭 암호 -> 공개키 암호
- hash function & MAC
PRNG: Linear congruential generators
Xn+1 = (aXn+c) mod m
이런 식으로 작동되는 난수 생성기는 unpredictable 하지 않다.
즉, 암호키 생성 시 사용하기에 적절하지 않다. -> rand 함수 같은 거 사용하면 안 됨
단순 시뮬레이션을 위해서는 써도 좋음.
Block cipher에 사용되는 Pseudorandom Numbers generation
CTR mode(카운터 모드)
NIST SP 800-90A, ANSI standard X9.82, RFCC4086
OFD mode
ANSI standard X9.82, RFCC4086
Stream Cipher
Stream Cipher 설계 원칙
- cycle이 굉장히 길어야 한다.
- TrueRandom Number처럼 보여야한다.
- 키의 길이가 최소 128bit이어야 한다.
- 비슷한 길이의 block cipher와 비슷한 안전서을 가져야한다.
예제
- RC4
- Salsa20
- ChaCha20
True Numbers generators
TRNG는 randomness를 위해서 nondeterministic source를 사용한다.
- 오디오나 디스크에서 나오는 예측 불가능한 소스들을 이용해서 TRN를 만든다.
- 여기에 있는 bias를 제거하는 과정이 conditioning이다.
Conditioning
TRNG entropy source의 bias를 제거하는 과정
conditioning algorithm/deskewing algorithm 사용
Biased
후처리 과정 거쳐서 처리
Entorpy rate
1111 -> enrtopy 낮음, 13354 -> enrtopy 높음
entropy rate가 높아야 랜덤하다고 볼 수 있다.
Intel이 제공하는 Digital Random Number Generator
-
Instruction으로 RDSEED와 RDRAND 제공
-
RDSEED: 다른 PRNG의 seed를 가지고 싶을 때 사용
#진짜 랜덤 #Non-Deterministic #srand 느낌 -
RDRAND: 그 이외에는 RDRAND를 사용하면 됨.
#PRNG #rand 느낌
출처
https://hororolol.tistory.com/482?category=897521
[Cryptography and Network Security: Principles and Practices]
