컴퓨터는 어떻게 난수를 만들까?

 

컴공 비전공자로서 순수한 개인적 호기심에 검색해보고 정리한 것입니다. 틀린 내용이 있다면 언제든지 지적해주세요. 저는 조금 슬프겠지만요.

 

---

Q. 컴퓨터는 어떻게 난수를 만들까?

A. 컴퓨터는 난수를 만들 수 없다. 정확하게는 완벽히 예측 불가능한 난수를 외부의 도움 없이 소프트웨어만으로는 만들 수 없다. 무슨 말이냐고?

 

컴퓨터는 주어진 task를 주어진 조건에 따라 주어진 순서대로 실행하는 기계이다. 즉 컴퓨터는 우연에 의하는 선택을 할 수 없다. 유식한 말로는 결정적 유한 오토마타(Deterministic Finite Automata; DFA)라고 부른다.^[1] 어려운 말 써서 미안하지만 사실 나도 뭔지 모르니까 그냥 그런게 있다보다 하고 넘어가자.

 

컴퓨터, 정확히는 소프트웨어가 하는 모든 일은 아래의 범주에 속한다.^[2]

• 메모리에 저장된 수를 연산
• 두 수를 비교
• 비교의 결과에 따라 어느 task를 수행할지 결정

모두 deterministic한 수행들이므로 이것만으로는 난수를 만들 방법이 없어보인다. 그리고 실제로도 없다. 그래서 소프트웨어가 만드는 난수를 의사난수(pseudo random number)라고 부른다. 의사난수란 얼핏 보기엔 unpredictable해 보이지만 사실 정해진 계산을 통해 생성되는 완벽히 predictable한 숫자들이다. 난수생성기(Random Number Generator; RNG)의 한 가지 예를 들어보자.^[2]

위 그림은 1-10 사이의 정수 난수생성기이다. 아무 숫자나 왼쪽에 넣어보자. 4를 넣었다.

왼쪽에 넣은 숫자 4를 seed라고 부른다. 계산 결과 6이 나왔다. 이제 결과인 6을 왼쪽에 넣어보자.

이번엔 9가 나왔다. 한 번만 더 해보자. 9를 왼쪽에 넣으면 오른쪽에서는 8이 나온다.

이 과정을 반복하면 아래와 같은 의사난수수열을 얻을 수 있다.

이 예시에서 7과 11은 아무렇게나 고른 수는 아니다. 예를 들어 11 대신 10를 넣는다면 전혀 랜덤하지 않은 수열이 만들어진다. 심지어 seed에 따라 계속 같은 숫자만 나올 수도 있다. 사실 위 예시도 10번 만에 첫 seed인 4가 다시 나와버려서 주기가 고작 11인 수열을 만든다. 주기가 더 긴 수열을 만들려면 11보다 더 큰 수를 써야 한다. 궁금하다면 페르마의 소정리를 검색해보자.

 

어쨌거나 결과로 얻은 수열만 보면 충분히 무작위로 보이기는 한다. 하지만 이 방법은 몇 가지 치명적인 문제가 있다.^[2]

1. Seed가 같으면 생성되는 난수수열도 동일하다. 따라서 seed부터 무작위로 고를 수 있어야 한다. 가장 심플한 방법은 system clock을 이용하는 방법이다. 밀리초(millisecond; ms) 단위의 숫자들은 어느 정도는 랜덤하다고 볼 수 있다. 실제로 파이썬에서도 이 방법을 채택하고 있다.^[3]
2. RNG의 정보를 알고 있다면 꽤 높은 정확도로 다음에 생성될 난수를 알 수 있다. 예를 들어 위 RNG에서 11이라는 숫자를 미리 알고 있다면 생성되는 숫자들을 이용해 seed가 몇인지 추정할 수 있고 그 이후에 생성될 난수도 모두 알 수 있다. 이때부터는 난수를 난수라 부를 수 없다.

이렇게 생각해볼 수도 있다. 밀리초 단위의 숫자가 어느 정도 랜덤하다면 그 숫자를 그대로 사용하면 되지 않을까? 밀리초가 불안하다면 마이크로초(microsecond) 단위의 숫자를 사용하면 어떨까? System clock이 14:15:36.909302로 추출되면 여기서 마지막 숫자를 이용하는 방법은 가능하지 않을까?

 

하지만 이 방법 역시 순환논리에 빠진다. System clock 기반으로 생성한 난수가 찐 난수가 되려면 system clock을 측정하는 코드의 실행시간도 무작위여야 한다.^[4] 코드 실행시간이 무작위가 아니라면 이 방법으로 생성된 난수는 찐 난수가 아니다. 그렇다면 코드 실행 타이밍을 일정하지 않게 만들면 되지 않을까? 그 일정하지 않은 실행 타이밍을 위해 어디선가 또 난수를 생성시켜야 한다. 즉 난수를 생성하기 위해 난수가 필요한 상황이 된다. 그럼 그 난수를 생성하기 위한 또 다른 난수가 필요하고 가정이 무너지고 사회가 무너지고 난 난수를 믿었던 만큼 난 내 컴퓨터도 믿었기에♬

 

결과적으로 소프트웨어적인 방법만으로는 찐 난수는 만들 수 없다. 그럼 어떻게 하면 될까? 소프트웨어가 예측할 수도, 제어할 수도 없으면서 무작위성을 가진 외부의 소스를 이용하면 된다. 이런 무작위성을 엔트로피(entropy)라고도 부른다. 아래는 몇 가지 후보들이다. 이 중 몇 가지는 실제로 리눅스에서 이미 사용 중인 스킬들이다.^{[1, 5, 6]} 더 궁금하다면 [7]에서 /dev/random 파트를 읽어보자. 인텔의 RnRand가 궁금하다면 [8]을 읽어보자.

• 컴퓨터 부팅 시각
• CPU 속도 – 부하, 온도에 영향을 받음
• 컴퓨터 사용자의 행위 – 마우스 커서 위치, 키보드 입력시간 등
• 사운드 카드로 감지되는 신호
• 네트워크 트래픽, 특히 wireless 트래픽

이마저도 불안하다면 아예 컴퓨터를 벗어나 자연계의 무작위성을 이용하는 방법도 있다. 사이버 보안 업체인 클라우드플레어(Cloudflare) 사옥 로비에는 라바램프 100개가 진열된 벽이 있다. 인테리어라도 하려는 것 같지만 사실 난수생성을 위한 장치이다.^[6] 램프를 채운 밀랍과 기름의 움직임은 예측이 불가능해서 충분한 무작위성을 갖는 것으로 볼 수 있다. 정기적으로 찍은 램프의 사진을 이용하면 자연으로부터 얻은 진짜 난수를 생성할 수 있다. 그 외에도 아래와 같은 방법들이 가능하다.^[6]

• 대기의 온도변화 또는 잡음
• 소금, 황산구리 등의 결정
• 박테리아의 성장, 증식
• DNA 시퀀싱 데이터
• 우주배경복사(CMB)
• 진공에서의 양자요동
• 방사성 동위원소의 붕괴

주사위는 랜덤일까? 2012년 폴란드와 스코틀랜드의 연구자들이 공기의 점성, 탁자의 마찰, 중력가속도를 이용하여 주사위를 시뮬레이션 하고 고속촬영을 통해 검증했다고 한다.^[9] 그 결과 1의 눈이 위를 향한 채로 던져진 주사위는 최종적으로 1이 나올 확률이 더 높다고 한다. 궁금하면 [10]을 읽어보자. 사실 나는 읽다 말았다.

 

본 글은 [2]의 영상을 가장 많이 참고하여 만들었다. 영상 뒷부분에는 찐 난수 생성을 위해 프로세서에 들어가는 특별한 회로를 설명해주니 한번 가서 보도록 하자. 참고로 나는 이해 못했다. 이 영상 채널의 주인인 Anton Spraul이 쓴 책도 있다. “How Software Works”라는 책이며 국내에도 “소프트웨어 작동법”이라는 제목으로 번역되어 있다. 목차를 봤는데 나는 사봤자 이해할 수 있는 수준이 아니라서 사지 않기로 했다.

 

참고한 곳들

 

[1] “난수생성”, 나무위키, https://tinyurl.com/ycnelp4j

[2] “Random Numbers (How Software Works)”, YouTube, https://youtu.be/aSlkVy3mbR0

[3] “Why Random Numbers Aren’t Random”, YouTube, https://youtu.be/Nm8NF9i9vsQ

[4] “What’s the problem of using the clock to generate random numbers?”, StackExchange, https://tinyurl.com/yc9v6z28

[5] “Why is it impossible for a computer to generate a truly random number?”, Quora, https://tinyurl.com/y8qcbmpe

[6] “자연현상에서 숫자 추출...이게 다 암호 재료입니다”, 매일경제, https://tinyurl.com/ya3c3d49

[7] “What does “Everything Is a File” Mean in Linux?”, How-To Geek, https://tinyurl.com/txfbq23

[8] “How Computers Generate Random Numbers”, How-To Geek, https://tinyurl.com/kmbnv5v

[9] “Is Anything Truly Random?”, YouTube, https://youtu.be/tClZGWlRLoE

[10] “Dice Rolls are Not Completely Random”, INSIDE SCIENCE, https://tinyurl.com/y73839ea