랜덤 문자열 생성기가 몰래 편향되는 이유 — 모듈로 편향과 거부 샘플링

가이드 · 2026-08-19 최종 확인

랜덤 ID 생성기 대부분은 "무작위 바이트를 뽑아서 알파벳 길이로 나눈 나머지로 문자를 고른다"는 방식을 씁니다. 직관적으로 안전해 보이지만, 알파벳 길이가 256의 약수가 아니면 이 단순한 나머지 연산 자체가 특정 문자를 미세하게 더 자주 뽑아내는 모듈로 편향(modulo bias)을 만듭니다. 이 가이드는 그 편향이 왜 생기는지, 그리고 실제로 이를 없애는 거부 샘플링(rejection sampling)이 어떻게 동작하는지 계산 원리와 실제 코드로 설명합니다.

1. 모듈로 편향이 생기는 이유

암호학적으로 안전한 난수 생성기(crypto.getRandomValues())로 바이트 하나를 뽑으면 0~255 사이 256가지 값이 완전히 균등한 확률로 나옵니다. 문제는 이 값을 알파벳 문자로 바꾸는 다음 단계입니다. 알파벳 길이가 N일 때 byte % N으로 인덱스를 정하면, 256이 N으로 나누어떨어질 때만 모든 문자가 정확히 같은 횟수만큼 매핑됩니다. N이 256의 약수가 아니면, 나머지(256 mod N)만큼의 "여분" 바이트 값들이 앞쪽 문자에 한 번씩 더 매핑되면서 균등하지 않은 분포가 생깁니다.

2. 왜 이게 보안에서 문제가 되나

편향된 문자 선택은 알파벳 크기 N에서 이론상 얻을 수 있는 최대 엔트로피(문자당 log2(N) 비트)보다 실제 엔트로피를 살짝 낮춥니다. 개별 ID 하나로는 체감되지 않지만, 대량의 ID를 뽑아 통계 공격이나 충돌 확률 계산에 활용하는 고보안·고빈도 환경에서는 이 미세한 편향이 이론적 안전 마진을 갉아먹습니다. 이런 이유로 잘 만들어진 랜덤 문자열 라이브러리(예: 실제 nanoid npm 패키지)는 반드시 편향 제거 로직을 내장합니다.

3. 해법: 거부 샘플링(Rejection Sampling)

거부 샘플링은 "256을 N으로 나눈 몫만큼의 배수 구간"만 유효한 값으로 인정하고, 그 밖의 여분 바이트 값은 그냥 버리고 다시 뽑는 방식입니다. 즉 Math.floor(256/N)*N보다 작은 바이트만 사용하고, 그 이상은 버립니다. 이렇게 하면 남는 값의 범위가 항상 N의 정확한 배수가 되므로 % N 연산이 완전히 균등해집니다. 대가는 가끔 바이트 하나를 버리고 다시 뽑아야 한다는 것뿐이며, 통계적 편향은 완전히 사라집니다.

4. 이 사이트의 NanoID 생성기는 실제로 어떻게 하나

nanoid-generator.html의 실제 생성 함수를 보면 정확히 이 방식을 구현하고 있습니다:

바이트 값이 Math.floor(256/알파벳길이)*알파벳길이보다 작을 때만 그 바이트를 사용해 문자를 추가하고, 그 이상 값은 조용히 건너뜁니다(거부). 목표 길이만큼 문자가 안 모이면 추가로 바이트를 더 뽑는 while 루프로 보충합니다. 이는 앞서 설명한 거부 샘플링을 정확히 구현한 것으로, 62자·26자처럼 256의 약수가 아닌 알파벳을 써도 모든 문자가 완전히 동일한 확률로 나오도록 보장합니다.

5. 알파벳을 256자 넘게 입력하면 생기는 함정

거부 샘플링에는 한 가지 전제가 필요합니다 — 알파벳 길이가 256 이하여야 한다는 것입니다. 알파벳이 256자를 넘으면 바이트 값(0~255) 하나로 표현 가능한 문자 종류의 범위 자체를 벗어나므로, 거부 필터가 단 하나의 바이트도 통과시키지 못해 생성이 무한정 멈추는 문제가 생길 수 있습니다. 이 때문에 안전한 구현은 반드시 알파벳 길이를 256자로 상한을 두어야 합니다.

자주 묻는 질문