처음 배우는 암호학 ch2 무작위성

무작위성(randomness)는 암복호화의 모든 곳에 등장

없으면 모든 연산이 예측이 가능하기 때문에 암복호화 자체가 불가능 

 

무작위한 비트는 무작위한다는 것은 흔히 일어나는 착각임

무작위성 식별할 때 사람들이 흔히 저지르는 오류 다음과 같음.

 

비무작위성을 무작위성으로 오해 :  단지 무작위해 보인다고해서 무작위하게 생성되어있다고 생각하는 오류

무작위성을 비무작위성으로 오해 : 우연한 패턴을 보고 이유가 있을거라고 생각하는 오류

 

확률 분포 : 모든 가능성 나열

가능성이 모두 같으면 균등분포(uniform distribution) , 비균등분포는 편향됨(biased)

 

 

 

 

엔트로피 : 불확실성의 측도  

엔트로피가 높으면 발견되는 확실성이 낮아집니다. 

 

확률 분포의 엔트로피 계산 가능 

확률 x 로그 곱들의 음의 합

-p1 x log(p1) - p2 x log (p2) ... -pNx log(pN)

log(1/2^n) = -n (음의 합 쓰는 이유)

ex) 128 비트의 균등분포의 엔트로피

균등분포일 때 엔트로피 최대 -> 불확실성 최대화

ex) 동전 던지기

확률이 1/2 이기 때문에 다음과 같아진다.

만약 앞, 뒤가 나올 확률이 다르다면

 

1에 가까울 수록 높은 엔트로피 

---

 

난수발생기(RNG) 와 의사난수발생기(PRNG) 

PRNG는 엔트로피원으로부터 무작위 비트를 산출하는 암복호화 알고리즘이다. 

RNG 는 엔트로피원을 통해 무작위 비트를 생성한다. PRNG 의 엔트로피원이다. 또한 생성하기 어려울 때가 많다. 

 

양자 난수 발생기(Quantum random number generator) 을 사용 하면 역학에서의 무작위성을 제공해서 진짜 무작위성을 제공할 수 있다. 하지만 실제로는 편향이 가능하다. 또 RNG 와 동일하게 빠르지 못하다. 

 

RNG와 PRNG는 다르다. 

PRNG는 RNG에 의존하지만 다르게 작동한다. 

결정론적 방식으로 생성하고 최고의 엔트로피을 제공한다. 

 

PRNG의 작동방식 

:PRNG는 주기적으로 RNG으로부터 받은 난수비트를 통해 큰 메모리의 버퍼 내용을 갱신 

메모리의 버퍼는 엔트로피 풀(entropy pool) 라고 한다. 

갱신과정에서 PRNG는 풀의 비트를 뒤섞어서 통계적 편향 제거

비트열 생성을 위해 DRBG 실행 -> 더 긴 비트열로 확장

같은 입력을 두번 제공 x 

 

PRNG 

init() : 엔트로피 풀과 PRNG의 내부상태 초기화

refresh(R): R을 통해 엔트로피풀 갱신(흔히 RNG에서) == reseeding 

next(N) : N개의 의사비트 생성후 엔트로피 풀 갱신

 

PRNG 

-암호 PRNG

-비암호 PRNG

 

여기서 비암호 PRNG는 사용하면 안됨. 

단지 확률분포에만 신경 쓸 뿐 예측 가능성(prediction resistance)은 신경을 안 씀. 그렇기에 이후 비트를 예측 가능하다. 

 

무작위성 문제 발생 요인

1. 불충분한 엔트로피우너

2. 시동 시점의 엔트로피 부족

3. 비암호 PRNG

4. 무작위성은 강하지만 표본 추출에 문제가 있는 사례 

 

읽을 거리

-논문 

-응용프로그램의 PRNG 악점 찾아보기("random generator bug")