난수 생성기

숫자는 어디서 오는가

추첨에는 브라우저의 암호학적으로 안전한 난수 생성기인 crypto.getRandomValues를 씁니다. 운영 체제가 모은 엔트로피로 시드를 만들며, 출력을 관찰해도 다음에 나올 값에 대해 쓸 만한 정보를 전혀 얻을 수 없도록 설계되어 있습니다.

쉽게 떠오르는 대안인 Math.random은 종류가 다릅니다. 속도를 위해 만든 빠른 의사 난수 생성기(보통 xorshift128+)로, 시계 상태 같은 것으로 시드를 만들고 내부 상태가 작아서 출력 몇 개만으로도 상태를 복원해 나머지를 예측할 수 있습니다. ECMAScript 명세는 이를 암호학적 목적으로 써서는 안 된다고 분명히 말합니다.

경품 당첨자를 뽑는 정도라면 이 차이가 문제 되는 경우는 드뭅니다. 그래도 여기서 쓰는 이유는 비용이 들지 않기 때문이고, 가끔만 믿을 수 있는 생성기는 언제나 믿을 수 있는 생성기보다 따져 보기가 더 어렵기 때문입니다.

나머지 연산의 편향

난수를 범위 안에 넣는 간단한 방법은 범위 크기로 나머지를 구하는 것이지만, 범위가 생성기의 값 범위를 나누어떨어뜨리지 못하면 미묘하게 틀립니다.

0~255의 무작위 바이트로 1~10 사이의 수를 구한다고 해 봅시다. 가능한 바이트는 256개, 답은 10개이며, 256은 10의 배수가 아닙니다. 열 개의 답 중 여섯 개에는 26개의 바이트가 대응하고 나머지 네 개에는 25개가 대응하므로, 앞의 여섯 개가 나머지보다 약 4% 더 자주 나옵니다. 범위가 1~100이면 편향이 더 커지고, 1~200이면 더욱 커집니다.

해결책은 기각 샘플링입니다. 생성기 값 범위의 윗부분에서 불균형을 일으키는 값이 몇 개인지 계산하고, 그 값이 나오면 버리고 다시 뽑습니다. 여기서는 범위의 정확한 배수 중 가장 큰 값을 넘는 수를 접어 넣지 않고 버립니다. 가끔 한 번 더 뽑는 비용이 들지만, 범위 안의 모든 수가 정확히 같은 확률로 나옵니다. 이 사이트의 비밀번호 생성기와 UUID 생성기도 같은 루틴을 씁니다.

중복 없이 뽑기

중복 없음 모드는 비복원 추출을 합니다. 로또 번호, 경품 추첨, 목록에서 무작위로 일부를 고를 때 원하는 방식입니다. 한 번 뽑힌 값은 풀에서 빠지므로 한 결과 안에 같은 수가 두 번 나오지 않습니다.

그러려면 범위 안의 값이 요청한 개수 이상이어야 합니다. 네 개짜리 범위에서 서로 다른 여섯 개를 뽑을 수는 없으며, 이때 도구는 무한히 반복하지 않고 그렇다고 알려 줍니다. 이것이 제약하는 것은 순서가 아니라 집합이라는 점에 주의하세요. 수는 여전히 무작위 순서로 뽑히므로, 결과는 정렬된 표본이 아니라 무작위 부분 집합을 섞은 것입니다. 순서대로 보고 싶다면 정렬 옵션을 따로 쓸 수 있습니다.

이 도구가 맞지 않는 용도

경품 추첨, 주사위, 테스트 데이터, 어떤 일부터 할지 정하기처럼 사람들이 운에 맡기는 수많은 작은 결정에는 좋은 도구입니다.

키, 비밀번호, 토큰을 만드는 도구는 아닙니다. 무작위성이 부족해서가 아니라 그런 것에는 특정한 길이와 문자 집합이 필요하기 때문이며, 그 용도에는 비밀번호 생성기를 쓰세요. 참가자들이 결과를 믿어야 하는 공개 추첨에도 적합하지 않습니다. 페이지에 나타난 숫자는 그것이 나타나는 순간을 보지 못한 사람에게 아무것도 증명하지 못합니다. 검증 가능한 추첨에는 공개된 시드와 추첨 전에 이루어진 약속이 필요하며, 이는 전혀 다른 설계입니다.

의사난수, 암호학적 난수, 그리고 진짜 난수

의사난수 생성기는 결정론적인 함수입니다. 시작 상태가 같으면 언제까지나 같은 수열을 만들어 냅니다. 재현성이 중요한 시뮬레이션에서는 장점이지만, 누군가 다음 값을 예측하려 들 수 있는 곳에서는 약점이 됩니다. JavaScript의 Math.random은 보통 xorshift128+이며, 빠른 대신 내부 상태가 작아서 출력 몇 개만 모아도 복원할 수 있습니다.

암호학적으로 안전한 생성기는 출력을 아무리 많이 관찰해도 나머지에 대한 쓸모 있는 정보를 얻을 수 없도록 만들어집니다. 시드는 운영체제가 모으는 엔트로피, 즉 타이밍 지터와 인터럽트 패턴, RDRAND 같은 하드웨어 명령에서 얻고 주기적으로 다시 시드를 넣습니다. 브라우저의 crypto.getRandomValues와 유닉스의 /dev/urandom이 흔히 쓰이는 인터페이스이며, 둘 다 충분히 빨라서 보안을 사실상 공짜로 얻는 셈입니다.

열잡음이나 방사성 붕괴 같은 물리 현상에서 얻는 진짜 난수는 하드웨어 모듈이나 random.org 같은 서비스로 존재합니다. 하지만 거의 모든 용도에서는 필요하지 않습니다. 시드가 잘 주어진 암호학적 생성기는 누구든 실제로 돌려 볼 수 있는 어떤 검정으로도 진짜 난수와 구별할 수 없기 때문입니다.

치우침 없이 목록을 섞는 법

직관적인 셔플, 즉 무작위 비교 함수로 정렬하는 방법은 틀렸습니다. 게다가 대충 봐서는 알아채기 어려운 방식으로 틀렸습니다. 비교 정렬은 순서가 일관된다는 것을 전제로 하므로, 무작위 비교 함수를 넘기면 특정 순열에 크게 치우친 분포가 나오고 결과는 정렬 구현에 따라서도 달라집니다. 섞인 것처럼 보이지만 실제로는 섞이지 않은 것입니다.

올바른 알고리즘은 Fisher-Yates입니다. 목록을 끝에서부터 훑으면서 각 위치마다 0부터 그 위치까지, 그 위치를 포함해 무작위 인덱스를 골라 맞바꿉니다. 모든 순열이 같은 확률로 나오고 선형 시간에 끝납니다. 거의 모든 언어의 표준 라이브러리에 올바른 구현이 있고, 없더라도 이 반복문은 네 줄이면 됩니다.

부분집합을 뽑는 일은 같은 연산을 일찍 멈추는 것뿐입니다. 앞의 k개 자리까지만 섞고 그것을 가져가면 됩니다. 무작위 인덱스를 뽑아 중복을 버리는 방식도 동작하지만, k가 목록 길이에 가까워질수록 성능이 크게 나빠집니다. 바로 그 지점에서 급하게 짠 구현들이 눈에 띄게 오래 맴돌기 시작합니다.

무작위 수열이 실제로 보이는 모습

사람은 무작위성을 판단하는 데 서툴고, 실수의 방향은 늘 한쪽으로 치우쳐 있습니다. 실제 무작위 데이터에는 직관이 허용하는 것보다 훨씬 많은 뭉침이 나타납니다. 동전을 백 번 던지면 앞면이 여섯 번, 일곱 번 연달아 나오는 일은 수상한 게 아니라 오히려 일어나기 쉬운 일이고, 긴 연속이 전혀 없는 수열이야말로 사람이 꾸며냈을 가능성이 큽니다.

스트리밍 서비스의 음악 셔플 기능이 대개 전혀 무작위가 아닌 이유가 여기에 있습니다. 진짜 셔플은 같은 아티스트를 세 번 연속으로 트는 일이 꽤 자주 일어나서 사용자들이 고장 났다고 신고할 정도입니다. 그래서 알고리즘은 일부러 아티스트를 흩뜨려 놓습니다. 덜 무작위하지만, 사람들이 셔플이라는 말로 떠올리는 것에는 더 가깝습니다.

함께 경계할 만한 직관이 두 가지 더 있습니다. 하나는 반대 결과가 이어지면 이제 나올 때가 됐다고 여기는 도박사의 오류이고, 다른 하나는 충돌이 예상보다 훨씬 잘 일어난다는 생일 효과입니다. 스물세 명이면 생일이 겹칠 확률이 반반이 됩니다. 둘 다 무작위성이 얼마나 잘 뭉치는지를 잘못 가늠하는 같은 착각에서 나옵니다.

매번 같은 숫자가 필요할 때

시뮬레이션, 절차적으로 생성되는 콘텐츠, 통계 작업은 모두 재현성이 필요합니다. 같은 시드가 같은 수열을 만들어야 결과를 다시 검토하고 버그를 재현할 수 있기 때문입니다. 암호학적 생성기는 시드를 일부러 지정할 수 없으므로 여기서는 정확히 잘못된 도구입니다.

보통은 작고 충분히 검증된 의사난수 생성기, 즉 PCG나 xoshiro, 오래된 코드라면 메르센 트위스터를 골라 시드를 명시적으로 넣고 기록해 둡니다. 테스트에서는 실패할 때 시드를 출력해 두는 것만으로 간헐적인 실패가 재현 가능한 실패로 바뀌는데, 이것이 고쳐지는 버그와 누군가 꺼 버리는 테스트를 가르는 차이입니다.

두 생성기는 분리해 두고, 시드를 준 쪽이 보안과 관련된 코드로 새어 들어가지 않게 하십시오. 문제를 만드는 패턴은 테스트 데이터를 섞는 데에도, 토큰을 만드는 데에도 같은 유틸리티 함수를 쓰는 경우입니다. 그 순간부터 결정론적인 수열이 지켜서는 안 될 것을 지키게 됩니다.

사람들이 공정하다고 받아들이는 추첨 만들기

공정함에는 두 가지 측면이 있습니다. 방식과 증거입니다. 여기서 방식은 건전합니다. 암호학적 난수원에 기각 표본추출을 더해 범위 안의 모든 값이 같은 확률로 나옵니다. 반면 증거는 웹페이지가 제공할 수 없는 것입니다. 화면에 숫자가 떠도, 그 자리에서 지켜보지 않은 사람에게는 아무것도 증명되지 않기 때문입니다.

추첨에 돈이나 의무가 걸려 있다면 표준적인 방법은 커밋 후 공개 방식입니다. 응모가 마감되기 전에 응모자 목록과 시드의 해시를 공개하고, 마감 뒤에는 공개된 방법으로 추첨을 진행한 다음 시드를 공표해 누구나 결과를 다시 계산할 수 있게 합니다. 주최자에 대한 신뢰가 누구나 검산할 수 있는 산수로 바뀌는 셈입니다.

누가 먼저 발표할지, 어떤 일부터 시작할지, 마지막 한 장의 표를 누가 가질지 같은 일상적인 경우에는 그런 절차가 필요하지 않습니다. 여기서 중요한 공정함은 그 자리에 있는 모두가 같은 결과를 동시에 보는 것입니다. 누군가 자기 화면을 보고 숫자를 읽어 주는 것보다 모두에게 보이는 추첨이 나은 이유가 바로 이것입니다.