랜덤 숫자 추첨기 알고리즘: Math.random vs CSPRNG, Fisher-Yates 셔플 가이드
무료 · 암호화 난수 기반 · 중복 없는 공정 추첨
이벤트 당첨자를 뽑거나 복권 및 경품 번호를 추첨할 때 가장 중요한 기준은 **'결과의 공정성과 예측 불가능성'**입니다. 단순히 화면에 무작위 수치가 노출되는 것처럼 보이더라도, 내부 구현 방식에 편향(Bias)이 존재하거나 난수 패턴을 예측할 수 있다면 추첨의 신뢰도는 무너집니다.
흔히 프로그래밍에서 사용하는 JavaScript의 Math.random() 함수는 난수처럼 보이는 수열을 생성하는 의사 난수 생성기(PRNG)로, 보안과 엄밀한 무작위성이 요구되는 추첨에는 부족함이 있습니다.
본 가이드에서는 Math.random()과 웹 암호화 API인 crypto.getRandomValues()의 보안 차이, 모든 순열이 동일한 확률로 선택됨을 보장하는 Fisher-Yates 셔플 알고리즘의 수학적 증명, 대용량 또는 스트림 데이터에서 효율적으로 무작위 추출하는 Reservoir Sampling(저수지 샘플링), 그리고 카이제곱 검정 수식을 통한 공정성 검증 기법과 실무 이벤트 추첨 팁까지 종합적으로 해설합니다.
1. Math.random() vs crypto.getRandomValues(): 암호학적 난수(CSPRNG)의 원리
컴퓨터는 본질적으로 정해진 알고리즘을 수행하는 결정론적(Deterministic) 시스템입니다. 따라서 순수 소프트웨어만으로는 완전한 무작위 난수를 만들 수 없으며, 수학적 알고리즘을 통해 '난수처럼 보이는 의사 난수(Pseudo-Random Number)'를 계산해 냅니다.
Math.random()의 특징과 한계 (PRNG)
Math.random()은 **의사 난수 생성기(PRNG, Pseudo-Random Number Generator)**를 바탕으로 동작합니다. V8 등 현대 자바스크립트 엔진은 내부적으로 xorshift128+ 또는 LCG(Linear Congruential Generator) 계열의 알고리즘을 활용합니다.
- 시드(Seed) 기반 결정론: 초기 시드값과 내부 상태가 정해지면 이후 생성되는 모든 수열이 고정됩니다.
- 예측 가능성: 난수 몇 개를 연속으로 관찰하면 이전 상태나 다음 나올 숫자를 수학적으로 완전히 재구성하여 예측할 수 있습니다.
- 조작 위험: 경품 추첨이나 이벤트 당첨자 선정 시 악의적인 공격자가 난수의 다음 패턴을 계산해 당첨률을 높이는 부정행위가 일어날 수 있습니다.
crypto.getRandomValues()의 우수성 (CSPRNG)
반면 crypto.getRandomValues()는 **암호학적으로 안전한 의사 난수 생성기(CSPRNG, Cryptographically Secure PRNG)**를 사용합니다.
- 엔트로피 소스(Entropy Source): 운영체제(OS) 수준에서 마우스 커서 움직임, CPU 인터럽트 미세 타임스탬프, 하드웨어 키보드 입력 노이즈 등 물리적 현상에서 난수 엔트로피를 수집합니다.
- 역산 불가능성: 과거에 생성된 난수들을 모두 파악하더라도 다음 생성될 난수를 예측하거나 내부 시드를 역추적하는 것이 비트 단위에서 불가능에 가깝습니다.
- 공정성 보장: 현금성 경품, 경품 추첨, 암호키 생성 등 신뢰성과 공정성이 핵심인 모든 업무에는 반드시 CSPRNG를 활용해야 합니다.
2. Fisher-Yates 셔플 알고리즘 원리 및 균등 분포 수학적 증명
명단이나 숫자 배열을 무작위로 섞거나 중복 없이 K개의 당첨자를 추출할 때 개발자들이 가장 흔히 범하는 실수는 array.sort(() => Math.random() - 0.5) 코드를 사용하는 것입니다.
잘못된 셔플: array.sort(() => Math.random() - 0.5) 의 치명적 편향
이 로직은 짧은 배열에서는 작동하는 듯 보이지만 **심각한 통계적 편향(Bias)**을 야기합니다. N개의 요소가 가질 수 있는 모든 가능한 순열(Permutation)의 총 경우의 수는 (N!) (N 팩토리얼)입니다. 그러나 자바스크립트의 정렬 알고리즘(QuickSort, Timsort 등)에서 무작위 비교 함수를 호출할 때 발생하는 내부 결정 트리 경우의 수는 (2^M) 또는 (N^N) 형태를 가집니다. 수학적으로 (N^N)은 (N!)의 정수 배수가 될 수 없으므로, 어떤 순열 조합은 다른 조합에 비해 더 자주 나타나는 확률적 불균형이 100% 필연적으로 발생합니다.
Fisher-Yates (Durstenfeld) 셔플의 동작 메커니즘
Fisher-Yates 셔플(Durstenfeld 현대적 변형)은 배열의 뒤쪽(N-1)부터 시작하여 아직 확정되지 않은 앞쪽 영역(0 ~ i)에서 무작위 인덱스 j를 하나 선택해 두 위치의 요소를 맞바꾸는(Swap) 방식입니다.
- 시간 복잡도: (O(N)) (배열을 단 한 번 순회)
- 공간 복잡도: (O(1)) (추가 배열 생성 없이 제자리 셔플)
Fisher-Yates 셔플의 균등 분포 확률 증명
크기가 (N)인 배열에서 특정 요소가 위치 i에 배치될 확률을 수학적으로 계산해 보겠습니다.
배열의 마지막 위치((N-1))에 특정 요소가 무작위 선택될 확률: [ P_N = \frac{1}{N} ]
마지막에서 두 번째 위치((N-2))에 특정 요소가 선택될 확률 (앞 단계에서 선택되지 않고, 이번 단계에서 선택될 확률): [ P_{N-1} = \left(1 - \frac{1}{N}\right) \times \frac{1}{N-1} = \frac{N-1}{N} \times \frac{1}{N-1} = \frac{1}{N} ]
일반화하여 k번째 위치에 해당 요소가 최종 선택될 확률: [ P_k = \frac{N-1}{N} \times \frac{N-2}{N-1} \times \dots \times \frac{k-1}{k} \times \frac{1}{k-1} = \frac{1}{N} ]
따라서 배열 내 모든 N개의 요소가 어떠한 임의의 위치에 배치될 확률은 정확히 (\frac{1}{N})로 완벽하게 동일하며, 가능한 모든 (N!)개의 순열 패턴이 출현할 확률 역시 각각 (\frac{1}{N!})로 균등함이 증명됩니다.
3. 중복 없는 추출 알고리즘: Reservoir Sampling (저수지 샘플링)
만약 1부터 1,000,000(백만)까지의 거대한 숫자 범위에서 중복 없이 10개를 뽑아야 하거나, 전체 응모자 수를 미리 알 수 없는 실시간 스트림 데이터에서 K명을 무작위 추첨하려는 경우 전체 배열을 메모리에 생성한 뒤 셔플하는 방식은 극심한 메모리 및 CPU 자원 낭비를 유발합니다.
이때 활용할 수 있는 최적의 무작위 추첨 알고리즘이 **Reservoir Sampling (저수지 샘플링)**입니다.
저수지 샘플링의 작동 절차
크기가 (K)인 저수지(Reservoir) 배열을 준비하고, 스트림 데이터를 하나씩 읽어들이며 다음과 같이 처리합니다.
- 첫 (K)개의 요소는 조건 없이 저수지 배열에 채웁니다.
- i번째 요소 ((i > K))가 입력되면, 0부터 i까지의 무작위 정수 j를 생성합니다.
- 생성된 j가 (j < K) 조건을 만족하면, 저수지의 j번째 요소를 현재 i번째 입력값으로 교체합니다.
저수지 샘플링 균등 확률 수학식
전체 데이터 개수가 (N)개일 때, 최종 단계가 끝난 후 특정 요소가 저수지 배열에 당첨자로 남아있을 확률은 다음과 같이 수식화됩니다:
[ P(\text{당첨}) = \frac{K}{i} \times \left(1 - \frac{1}{i+1}\right) \times \left(1 - \frac{1}{i+2}\right) \times \dots \times \left(1 - \frac{1}{N}\right) ]
[ P(\text{당첨}) = \frac{K}{i} \times \frac{i}{i+1} \times \frac{i+1}{i+2} \times \dots \times \frac{N-1}{N} = \frac{K}{N} ]
이 수식이 보여주는 바와 같이 전체 데이터 크기 (N)을 사전에 몰라도, 단 한 번의 순회((O(N)) 시간 복잡도)와 (O(K))라는 최소한의 메모리만으로 전체 N개 중 K개를 완벽히 공정하게 비복원 추출할 수 있습니다.
무료 · 암호화 난수 기반 · 중복 없는 공정 추첨
4. 추첨 공정성 검증: 카이제곱 ((\chi^2)) 적합도 검정 및 모듈로 편향 제거
추첨 도구나 이벤트 시스템이 특정 번호나 참가자에게 편중되지 않고 균등하게 난수를 추출하는지 검증하기 위해서는 통계학적 검정이 필요합니다.
카이제곱 적합도 검정 통계량 수식
총 (N)번의 추첨 실험을 진행하여 생성된 (K)개의 범주에 대해 실제 관측 빈도를 (O_i), 이론적 기대 빈도를 (E_i = \frac{N}{K})라고 정의할 때, 카이제곱 통계량 (\chi^2)는 다음과 같습니다:
[ \chi^2 = \sum_{i=1}^{K} \frac{(O_i - E_i)^2}{E_i} ]
- 귀무가설 ((H_0)): 난수 추출 알고리즘은 편향 없이 완전한 균등 확률 분포를 따른다.
- 자유도 ((df)): (K - 1)
- 판정 기준: 계산된 (\chi^2) 통계량이 설정한 유의수준((\alpha = 0.05))에서의 카이제곱 임계치(Critical Value)보다 작다면, 해당 추첨기는 통계적으로 **"편향이 없는 공정한 추첨기"**로 채택됩니다.
모듈로 편향 (Modulo Bias) 방지 수식
crypto.getRandomValues()로 구한 32비트 무작위 정수(0 ~ (2^{32}-1))를 우리가 원하는 범위 ([0, M-1])로 변환할 때 단순히 % M (모듈로 연산)을 적용하면 모듈로 편향이 일어납니다. (2^{32})가 (M)의 배수가 아닌 이상, 앞쪽 일부 숫자들이 뽑힐 확률이 미세하게 높아집니다.
이를 수학적으로 완벽하게 제거하기 위해 거절 샘플링(Rejection Sampling) 한계값을 구합니다:
[ \text{Rejection Limit} = 2^{32} - (2^{32} \pmod{M}) ]
추출된 난수 (R)이 (R \ge \text{Rejection Limit})에 해당하면 해당 값을 버리고 새로 난수를 추출함으로써 완전한 균등 확률(Perfect Uniform Distribution)을 달성합니다.
5. 완벽한 공정 추첨을 위한 TypeScript / JavaScript 구현 예제
아래 코드는 CSPRNG 보안 난수 기반 모듈로 편향 제거, Fisher-Yates 셔플, Reservoir Sampling을 모두 포함한 완전한 TypeScript 예제입니다.
/**
* CSPRNG 기반 무작위 정수 생성 (모듈로 편향 완전 제거)
* @param min 최소값 (포함)
* @param max 최대값 (포함)
*/
export function getRandomIntSecure(min: number, max: number): number {
if (min > max) {
throw new Error("min은 max보다 작거나 같아야 합니다.");
}
const range = max - min + 1;
if (range === 1) return min;
const maxUint32 = 0xffffffff; // 2^32 - 1
const limit = maxUint32 - (maxUint32 % range);
const array = new Uint32Array(1);
let randomValue: number;
do {
crypto.getRandomValues(array);
randomValue = array[0];
} while (randomValue >= limit);
return min + (randomValue % range);
}
/**
* CSPRNG 기반 Fisher-Yates 중복 없는 무작위 추출 (K개)
* @param array 원본 응모자/숫자 배열
* @param k 추출할 당첨자 수 (미지정 시 전체 셔플)
*/
export function pickRandomItems<T>(array: T[], k?: number): T[] {
const result = [...array];
const count = k !== undefined ? Math.min(k, result.length) : result.length;
for (let i = result.length - 1; i > result.length - 1 - count; i--) {
const j = getRandomIntSecure(0, i);
[result[i], result[j]] = [result[j], result[i]];
}
return result.slice(result.length - count);
}
/**
* 대용량 범위/스트림 데이터 저수지 샘플링 (Reservoir Sampling)
* @param min 범위 시작값
* @param max 범위 끝값
* @param k 뽑을 당첨자 수
*/
export function reservoirSampleRange(min: number, max: number, k: number): number[] {
const total = max - min + 1;
const sampleCount = Math.min(k, total);
const reservoir: number[] = [];
// 1. 초기 K개 저수지 채우기
for (let i = 0; i < sampleCount; i++) {
reservoir.push(min + i);
}
// 2. i번째 요소 무작위 교체 판정
for (let i = sampleCount; i < total; i++) {
const currentValue = min + i;
const j = getRandomIntSecure(0, i);
if (j < sampleCount) {
reservoir[j] = currentValue;
}
}
return reservoir;
}
6. 실무 이벤트 당첨자 선정 시 공정성 확보 팁
온라인 이벤트, 경품 추첨, 서포터즈 선정 등 시비 요소가 발생할 수 있는 업무에서는 알고리즘의 우수성뿐만 아니라 운영 프로세스의 투명성 확보가 매우 중요합니다.
사전 시드(Seed) 및 해시(SHA-256) 공지 (Commitment Scheme)
- 추첨 시작 전 참가자 명단의 SHA-256 해시값이나 타임스탬프 기반 시드값을 공식 게시판에 미리 공개합니다.
- 추첨 후 해당 시드 및 알고리즘으로 누구나 동일 결과를 재현할 수 있음을 보여주면 조작 의혹을 완전히 해소할 수 있습니다.
화면 녹화 및 검증 로그 보존
- 명단 입력부터 추첨 버튼 클릭, 결과 화면 출력까지의 전체 화면을 녹화 영상으로 남겨 업로드합니다.
- 추첨 당시 추출된 난수 값과 시각 타임스탬프 로그를 보존하여 필요한 경우 즉시 제출합니다.
중복 데이터 및 정형화 처리
- 동일인의 중복 응모(전화번호, 이메일, 계정 ID)를 추첨 알고리즘 실행 전 백엔드에서 1건으로 정형화(Normalization)하여 제거합니다.
클라이언트 브라우저 기반 무작위 추첨 도구 활용
- 서버 측 추첨 조작 가능성을 배제하기 위해 브라우저의
crypto.getRandomValues()를 직접 실행하는 클라이언트 추첨 도구를 활용하는 것이 좋습니다.
- 서버 측 추첨 조작 가능성을 배제하기 위해 브라우저의
자주 묻는 질문 (FAQ)
Q1. Math.random()으로 뽑은 당첨자는 법적 문제가 생기나요?
소규모 사내 이벤트나 단순 재미용 추첨이라면 Math.random()으로도 문제될 확률은 적습니다. 그러나 고가의 현금성 경품이나 공공기관/기업 공식 이벤트에서는 난수 예측 가능성과 편향 시비를 차단하기 위해 반드시 CSPRNG 보안 난수 알고리즘을 사용해야 합니다.
Q2. 1등부터 뽑는 것과 5등부터 뽑는 것의 당첨 확률 차이가 있나요?
Fisher-Yates 알고리즘 등 완전 균등 무작위 셔플을 사용하는 경우 추출 순서와 무관하게 모든 응모자의 당첨 확률은 정량적으로 완벽히 동일합니다. 이벤트 진행 연출상 낮은 등수부터 발표하는 것이 흥미를 유발하기에 권장됩니다.
Q3. 중복 허용(복원 추출)과 중복 제외(비복원 추출)는 언제 구분해 쓰나요?
로또 번호 생성이나 경품 이벤트 당첨자 선정처럼 한 번 뽑힌 번호/사람이 다시 뽑히면 안 되는 경우에는 비복원 추출(중복 제외)을 사용하며, 주사위 던지기나 당첨 확률 게임처럼 매번 동일 확률을 유지해야 하는 경우 복원 추출(중복 허용)을 선택합니다.