[현대암호기초] #03. 무작위성

무작위성: 무작위성이 없으면 모든 연산이 예측가능하므로 암복호화가 불가능하다.

 

무작위성에 대한 오류

비무작위성을 무작위성으로 오해

무작위성을 비무작위성으로 오해

 

+ 클모고로프 복잡도 (Kolmogorov complexity)

: (비트)문자열의 무작위성을 측정한 것으로 유한한 길이를 가진 데이터 열의 복잡성을 나타내는 지표 중 하나

 

+ 확률분포와 무작위성

균등 분포 : 모든 결과의 발생 가능성이 같다.

비균등분포 : 결과의 발생 가능성이 모두 같지는 않은 분포 (많은 확률을 가진 case를 ‘편향되었다’고 한다.)

 

+ 엔트로피

: 불확실성, 시스템에 존재하는 무질서의 측도

- 엔트로피가 높을수록 결과들에서 발견되는 확실성이 낮아진다.

 

확률분포의 엔트로피 : (각 확률 X 그 확률의 이진 로그 곱)의 합의 음의 값

 

 

엔트로피는 확률분포가 균등분포일 때 최대가 된다. : 균등분포가 불확실성을 최대화하기 때문

 

+ 난수 발생기와 의사난수 발생기

 

무작위성의 생성을 위해 필요한 두가지

불확실성의 원천 또는 엔트로피원 :(난수 발생기 RNG)

엔트로피원으로부터 고품질 무작위 비트를 산출하는 암복호화 알고리즘: (의사난수 발생기 PRNG)

 

 

안전하고 실용적인 암호를 만드려면 RNG와 PRNG를 잘 활용해야 한다.

 

RNG : 디지털 시스템 안에서 아날로그 세계의 엔트로피를 이용하여 무작위 비트를 산출한다.

ex) 온도, 잡음, 공기의 난류, 정전기 등등

공격자의 조작과 악용에 취약하고 난수 비트를 생성하는 속도가 매우 느리다.

 

PRNG : 적은 수의 찐 난수 비트들로부터 다수의 인위적인 난수 비트들을 신뢰성 있게 산출하여 RNG의 단점을 보완한다.

 

RNG에서 나온 값을 PRNG로 보완, 확장하여 사용한다.

 

+ PRNG의 작동 방식

의사난수 비트열 생성을 위해 PRNG는 결정론적 난수 비트 발생기(deterministic random bit generator, DRBG) 알고리즘을 실행

+DRBG: 엔트로피 풀에서 가져온 몇 개의 비트를 더 긴 비트열로 확장한다.

DRBG는 결정론적이므로 같은 입력에 대하여 같은 값을 출력한다 따라서 PRNG는 같은 입력을 반복하지 않도록 주의한다.

PRNG의 연산

init()

refresh(R)

next(N)

 

+ PRNG 보안 관련 문제

PRNG는 반드시 역추적 저항성과 예측 저항성을 갖추어야 한다.

 

역추적 저항성(=순방향 비밀성) : 이전에 생성된 비트들을 다시 생성할 수 없다.

: PRNG의 refresh와 next연산에서 내부 상태를 갱신할 때 수행하는 변환이 비가역적이어야 한다.

-> 공격자가 엔트로피풀의 내용을 알아내도 풀의 이전 내용이나 과거의 비트들을 복원할 수 없다.

예측 저항성(=역방향 비밀성) : 이후의 비트들을 예측하는 것이 불가능하다.

: PRNG가 주기적으로 공격자가 알지 못하고 추측하기 힘든 R값으로 refresh를 호출해야 한다.

-> 공격자가 엔트로피풀의 내용을 알아내도 미래의 무작위 비트를 알아낼 수 없다.

 

다시 정리하러 온다 늦어도 이번주 안으로