완벽하게 공정한 난수 발생기는 왜 존재할 수 없을까?

로또 추첨, 게임의 아이템 드롭, 암호 키 생성. 우리는 매일 무작위를 믿으며 살아가고 있다. 그런데 한 번 이렇게 생각해보자.

어떤 것에도 영향을 받지 않는, 완벽하게 공정한 난수 발생기를 만들 수 있을까?

결론부터 말하면 불가능하다. 하지만 그 이유를 따라가다 보면 공정하다는 말의 진짜 의미와, 그럼에도 우리가 믿을 수 있는 난수를 얻는 방법이 보인다. 이 글의 그래프는 모두 직접 코드를 짜서 실행한 실험 결과이다.

---

1. 아무것에도 영향받지 않는 알고리즘은 아무것도 하지 않는다

먼저 영향을 받지 않는다는 조건부터 끝까지 밀어붙여 보자.

알고리즘이 입력에조차 영향을 받지 않는다면, 무엇을 넣든 항상 같은 값을 내놓는다. 그건 그냥 return 42 같은 상수 함수이며 쓸모가 없다.

게다가 알고리즘은 공중에 떠서 돌아가지 않는다. CPU, 메모리, 계산 모델 위에서 돌아가고, 그 환경의 영향(부동소수점 오차, 하드웨어 차이)을 받는다. 그리고 "공짜 점심은 없다(No Free Lunch)" 정리가 말해 주듯, 어떤 알고리즘이 잘 작동한다는 건 언제나 "데이터가 이럴 것이다"라는 가정에 기대고 있다는 뜻이다.

그래서 현실적인 질문은 "의존성을 0으로 만들 수 있나?"가 아니라 "무엇에 의존하지 않게 만들 수 있나?"이다.

---

2. 알고리즘은 무작위성을 만들어 낼 수 없다

그럼 다시 난수 발생기로 돌아와보자. 가장 먼저 부딪히는 벽은 이것이다.

컴퓨터 알고리즘은 결정론적이라는 것. 같은 입력이 들어가면 반드시 같은 출력이 나온다. 그렇다면 알고리즘이 만든 난수는 사실 입력(시드)에 의해 전부 정해진 숫자열일 뿐이다. 컴퓨터 과학의 아버지 중 한 명인 폰 노이만은 산술적 방법으로 난수를 만들려는 사람은 "죄를 짓고 있는 것"이라고 농담하기도 했다.

그래서 이것이 얼마나 쉽게 무너지는지 직접 확인해 보았다. 파이썬의 기본 random 모듈(메르센 트위스터)에 무작위 시드를 넣고, 시드는 모르는 채로 출력값 624개만 관찰했다. 이 출력으로 내부 상태를 거꾸로 계산해 복원한 뒤, 이후 값을 예측해보았다.

파란 선은 실제 출력, 주황 점은 예측값. 다음 1,000개를 하나도 빠짐없이 맞혔다.

통계적으로는 고르게 분포하는 난수지만, 누군가 결과를 맞히려 드는 상황(추첨, 도박, 암호)에서는 전혀 공정하지 않다.

즉, 무작위성은 알고리즘 안에서 생겨날 수 없고, 반드시 바깥에서 가져와야 한다. 이것이 끊을 수 없는 첫 번째 의존성이다.

---

3. 그래서 세상에서 무작위를 빌려온다

바깥 어디에서 가져올까?

정답은 결과를 예측하기 어려운 물리 현상들이다. 이를 엔트로피 원천이라고 부른다.

원천	무엇의 영향을 받나
동전, 주사위	던지는 힘, 공기 저항, 초기 조건 (고전 물리라 원리상 결정되어 있음)
회로의 열잡음, 타이머 떨림	온도, 전자의 운동, CPU 부하
마우스 움직임, 키 입력 간격	사람의 행동
라바램프 벽 (Cloudflare의 실제 사례)	램프 속 왁스의 유체 운동

실제 원천은 어떤 모습일까? 내 PC에서 타이머를 연속으로 두 번 읽고, 그 간격(100ns 단위 틱 수)이 홀수면 1, 짝수면 0으로 5만 번씩 20회 측정해서 기록해보았다.

주황 선이 타이머 원천이다. 1의 비율이 회차마다 26%에서 93%까지 오간다. 파란 선은 5장에서 설명할 폰 노이만 처리를 거친 결과다.

같은 PC, 같은 코드인데도 측정할 때마다 결과가 크게 달라진다. CPU 부하, 클럭 변화, 백그라운드 작업이 모두 이 원천에 영향을 주기 때문이다.
그렇기에 "아무것에도 영향을 받지 않는" 원천은 없다. 동전조차 던지는 순간의 조건을 완벽히 안다면 결과를 계산할 수 있다.

그렇다면 공정한 난수란 도대체 무엇일까?

---

4. "공정하다"의 진짜 의미: 원인이 없는 게 아니라, 아무도 모르는 것

여기서 관점을 바꿔야 한다.

공정한 난수 = 결과가 공격자나 관찰자가 알 수 있는 어떤 정보와도 독립적인 것

원인이 있어도 괜찮다. 그 원인에 아무도 접근할 수 없으면 공정하다.

운영체제는 바로 이 원리로 난수를 만든다. 하드웨어 잡음, 인터럽트 타이밍 같은 엔트로피를 긁어모아 섞은 뒤 제공한다. 파이썬에서는 secrets 모듈이 이를 사용한다.

import secrets

def fair_int(lo, hi):
    return lo + secrets.randbelow(hi - lo + 1)

여기서 흔한 실수가 하나 있다. 랜덤값 % 6 + 1처럼 나머지 연산으로 범위를 맞추는 것이다. 0~7 사이의 난수를 % 6하면 0과 1은 두 가지 값(0과 6, 1과 7)에서 나오고, 나머지는 한 가지 값에서만 나온다.

각 60만 번 측정. % 6 방식(주황)은 1과 2가 25%씩, 나머지가 12.5%씩 나왔다. 거부 샘플링(파랑)은 모두 16.7% 기준선에 맞는다.

randbelow는 범위를 넘는 값을 버리고 다시 뽑는 거부 샘플링으로 이 문제를 피한다.

---

5. 편향은 지울 수 있다: 폰 노이만의 트릭

그렇다면 원천 자체가 치우쳐 있다면? 3장의 타이머처럼, 혹은 앞면이 70% 나오는 찌그러진 동전밖에 없다면?

놀랍게도 편향된 동전으로도 공정한 결과를 만들 수 있다. 폰 노이만이 제안한 방법은 간단하다.

1. 동전을 두 번 던진다.
2. 앞-뒤가 나오면 1, 뒤-앞이 나오면 0을 기록한다.
3. 같은 면이 두 번 나오면(앞-앞, 뒤-뒤) 버리고 다시 던진다.

왜 공정할까? 앞면 확률을 0.7이라고 하면:

• 앞-뒤가 나올 확률 = 0.7 × 0.3 = 0.21
• 뒤-앞이 나올 확률 = 0.3 × 0.7 = 0.21

곱셈은 순서를 바꿔도 값이 같다. 그래서 편향이 얼마든 두 확률은 항상 같다. 실제로 앞면 70% 동전을 두 번씩 20만 회 던져 봤다.

앞-뒤 21.0%, 뒤-앞 21.1%. 이론값과 소수점 한 자리까지 일치한다. 회색은 버리는 경우다.

코드로 옮기면 몇 줄이면 된다.

def von_neumann(bits):
    it = iter(bits)
    for a, b in zip(it, it):  # 두 개씩 짝지음
        if a != b:
            yield a  # 10 → 1, 01 → 0, 00/11 → 버림

편향을 5%부터 95%까지 바꿔 가며 같은 실험을 반복했다.

주황 선(원천)은 설정한 편향을 그대로 따라가지만, 파란 선(출력)은 모든 구간에서 49.6%~50.5% 사이에 머문다.

결과가 원천의 편향값에 의존하지 않는다. 3장 그래프의 파란 선도 같은 원리이며, 26%~93%로 요동치는 타이머 원천이 폰 노이만 처리 후에는 50% 근처에 붙어 있다.

물론 대가가 없는 것은 아니다. 70% 편향이면 입력 100비트당 약 21비트만 남고, 편향이 심할수록 더 많이 버려진다.

알고리즘은 무작위성을 만들 수는 없지만, 원천의 편향으로부터는 벗어나게 해 줄 수 있다. 이런 도구를 일반화한 분야를 랜덤니스 추출기(randomness extractor)라고 부른다.

---

6. 그래도 지울 수 없는 전제: 독립성

폰 노이만 트릭에는 숨은 전제가 하나 있다. 각 던지기가 서로 독립이어야 한다는 것.

만약 원천이 "직전 결과를 따라가는" 성질을 갖고 있다면 어떻게 될까? 두 가지 경우로 실험해 보았다.

• 시뮬레이션: 직전 값과 같은 값을 낼 확률을 50%에서 95%까지 바꿔 가며 원천을 만들었다.
• 실측: 3장의 타이머 원천을 그대로 썼다.

두 경우 모두 폰 노이만 처리를 한 뒤, 아주 단순한 예측 규칙으로 다음 값을 맞혀 봤다. 직전 100개 출력에서 "같은 값이 이어진 경우"와 "값이 바뀐 경우" 중 많았던 쪽을 따라 찍는 것이다.

왼쪽: 원천이 직전 값을 따라갈수록 적중률이 올라 최대 65%에 이른다. 오른쪽: 실제 타이머 원천은 1의 비율이 49.9%로 완벽해 보이지만, 다음 값을 66.1% 확률로 맞힐 수 있었다.

이것이 핵심이다. 폰 노이만 트릭은 0과 1의 비율은 맞춰 주지만, 결과끼리 이어진 패턴은 지우지 못한다. 비율만 보면 공정해 보이는데, 4장의 정의로 보면 전혀 공정하지 않다. 50% 대신 66%로 맞힐 수 있는 추첨은 공정한 추첨이 아니다.

그럼 이 전제까지 없애는 더 똑똑한 알고리즘을 만들면 되지 않을까? 안타깝게도 수학적으로 불가능하다는 것이 증명되어 있다. 산타-바지라니(1986)는 이전 결과에 조금씩 영향을 받는 원천 하나만으로는, 어떤 결정론적 알고리즘도 공정한 비트를 단 하나도 보장할 수 없음을 보였다.

알고리즘으로 지울 수 있는 의존성은 여기까지다.

---

7. 원인 없는 무작위에 가장 가까운 것: 양자역학

그렇다면 물리학은 어떨까? 고전 물리의 동전은 원리상 결정되어 있지만, 양자 세계는 다르다.

광자 하나를 반투명 거울에 보내면 통과하거나 반사된다. 이때 "사실 미리 정해져 있었는데 우리가 몰랐을 뿐"이라는 설명(국소적 숨은 변수)은 벨 부등식 실험으로 배제되었다. 이 업적으로 알랭 아스페, 존 클라우저, 안톤 차일링거가 2022년 노벨 물리학상을 받았다.

여기서 더 나아가 장치 독립 난수 인증이라는 기술도 있다. 장치를 만든 사람을 믿지 않아도, 벨 부등식이 얼마나 위반되는지만 측정하면 "이 출력은 누구도 미리 알 수 없었다"를 수학적으로 인증할 수 있다. 미국 NIST와 콜로라도대학교는 이 방식을 이용한 공개 난수 서비스를 선보이기도 했다.

하지만 이것조차 "아무것에도 의존하지 않는" 것은 아니다. 두 가지 가정이 남는다.

• 양자역학이 옳다. 지금까지 모든 실험을 통과했지만, 과학 이론은 언제나 잠정적이다.
• 실험자가 측정 설정을 자유롭게 고를 수 있다. 만약 우주의 모든 것이, 실험자의 선택까지 태초부터 정해져 있다면(초결정론) 벨 실험의 결론은 성립하지 않는다. 이 가능성은 반증할 방법이 없다.

---

8. 마지막 벽: 무작위임을 증명할 수 없다

설령 완벽한 난수 발생기가 있다고 해도, 우리는 그것을 확인할 방법이 없다.

어떤 숫자열이 진짜 무작위인지 판정하려면 "이 숫자열을 만드는 더 짧은 규칙이 존재하는가?"를 알아야 한다. 이것을 콜모고로프 복잡도라고 하는데, 이 값을 계산하는 알고리즘은 존재하지 않는다는 것이 증명되어 있다.

통계 검정이 말해 줄 수 있는 건 "치우침을 찾지 못했다"까지이기에, 이를 극단적인 예로 확인해 봤다. 1, 2, 3, 4, 5, 6을 계속 반복하는 수열과 fair_int로 굴린 주사위를 각각 6만 번씩 비교했다.

왼쪽: 빈도 검정(카이제곱)에서 반복 수열은 0.00으로 오히려 fair_int(2.54)보다 "더 공정"하게 나온다. 오른쪽: 하지만 다음 값을 맞히면 반복 수열은 100%, fair_int는 찍기 수준인 16.6%다.

하나의 검정을 통과해도, 아직 시도하지 않은 다른 검정이 언제나 남아 있다. 6장의 타이머 원천이 비율 검정은 통과하고 패턴 검정에서 걸린 것처럼. 그리고 가능한 모든 검정을 다 해 보는 방법은 존재하지 않는다.

---

정리: 우리가 벗어날 수 있는 것과 없는 것

의존성	벗어날 수 있나?	방법 / 근거
원천의 편향	✅ 가능	폰 노이만 트릭, 랜덤니스 추출기
범위 변환의 치우침	✅ 가능	거부 샘플링
관찰자의 예측	✅ 가능	OS 엔트로피 (secrets), 양자 측정
결과끼리의 독립성	❌ 불가능	산타-바지라니 정리
바깥의 엔트로피 원천	❌ 불가능	결정론적 알고리즘은 무작위를 만들 수 없음
물리 법칙에 대한 가정	❌ 불가능	양자역학의 정당성, 측정 선택의 자유
무작위임의 증명	❌ 불가능	콜모고로프 복잡도는 계산 불가능

결론은 어디에도 영향을 받지 않는 공정한 난수 발생기는 존재하지 않는다는 것. 설령 존재하더라도 우리는 그것을 증명할 수 없다.

하지만 그게 절망적인 결론은 아니다. 공정함의 진짜 의미는 "원인이 없는 것"이 아니라 "아무도 결과를 미리 알 수 없는 것"이고, 그런 발생기는 충분히 만들 수 있다. 우리가 할 수 있는 일은 의존성을 없애는 게 아니라 어디에 둘지를 고르는 것이다. 믿을 수 있는 원천에 기대고, 알고리즘으로 편향을 지우고, 남은 가정을 정직하게 인정하는 것. 그것이 우리가 가진 최선의 "무작위"이다.

---