랜덤 수

〈컴퓨터정보보안〉 수업 노트

임의의 수 값은 키를 생성하는 데 사용된다. 이 수 값은 nonce라고 불리며, 대부분의 경우에는 무작위적이어야만 한다.

일반적으로 랜덤 수는 통계적으로 uniform하면 랜덤한 것으로 간주된다. 수가 가질 수 있는 모든 경우의 수에 대하여 거의 동등한 확률로 선택될 수 있다면 랜덤이다. (통계적 랜덤)

하지만 암호학에서는 조금 더 많은 것을 요구하는데, 통계적인 랜덤 외에도, 이 수 값이 예측 불가능해야 한다. (암호학적 랜덤)

어떤 값이 1부터 100까지 100개 값 중 하나를 가질 수 있고, 1부터 오름차순으로 차례로 선택되어도 통계적으로는 랜덤하다. 하지만 암호학에서 랜덤 값을 사용하는 이유는 정말로 생성한 값이 무작위적이길 기대하기 때문이므로, 이 방법을 랜덤 수라고 부르기에는 어렵다.

온라인 텍사스 홀덤 포커

ASF Software, Inc.의 온라인 텍사스 홀덤 포커 게임은 덱을 섞는 데 랜덤수를 사용한다. 플레이 카드는 총 52장 있으므로 가능한 덱 상태는 $52!$ 이다.

\[52! > 2^{225}\]

하지만 이 프로그램은 32비트 정수를 덱을 섞는 데 사용하므로, 가능한 상태값은 $2^{225}$ 에 턱없이 부족하다.

하지만 발생 가능한 덱의 순서는 실제로 $2^{32}$ 개의 상태값 정도라도 가지고 있을까?

코드는 파스칼 의사 난수 생성기(PRNG)를 사용해 덲을 섞는다. PRNG의 시드는 자정 00시 00분으로부터 진행된 밀리초 단위의 시간 값이다. 하루는 $60 \times 60 \times 24 = 86400$ 초, $2^{27}$ 밀리초보다 작다. 따라서 난수 생성기는 $2^{32}$ 보다 작은 $2^{27}$ 개의 상태값만을 가진다.

만약 클라이언트가 서버와 시계를 동기화한다면, 오차 범위 내에서 시드 값을 추측할 수 있다. $2^{18}$ 개 경우의 시드 값을 매 순간 테스트하여 랜덤 수를 전면적으로 시도할 수 있고, 이 정도 수준의 값은 실시간으로 시도할 수 있다.

True Randomness

우리가 기대하는 의미의 랜덤은 컴퓨터에서 구현하기에 도전적인 문제이다. 컴퓨터는 항상 결정론적으로 동작하기 때문에, 컴퓨터의 외부 환경에서 발생하는 랜덤 사례를 찾아야 한다.

• 방사능 물질의 붕괴
• 하드웨어 장치: 마우스 움직임, 키보드로의 물리적 상호작용의 정밀한 측정, 네트워크 활동 등…
• 라바 램프