난수 생성기

난수 생성기는 다음에 무엇이 나올지 짐작하기 어려운 수를 필요할 때마다 뽑아 주는 부품입니다. 대부분은 처음 받은 값 하나에서 계산으로 수를 이어 뽑습니다. 계산이라서 그 속을 아는 사람에게는 다음 수가 보입니다. 그래서 남이 못 맞혀야 하는 값은 속을 못 들여다보게 만든 생성기로 따로 뽑습니다.

상세

이 절은 난수 생성기가 무엇을 받아 무엇을 내놓는지부터 봅니다. 그다음 작은 식 하나를 손으로 돌려 봅니다. 계산으로 뽑은 수가 어떻게 이어지고 언제 되풀이되는지 확인합니다.

뒤쪽 소절은 쓰임을 가릅니다. 값을 들켜도 괜찮은 곳과 들키면 사고가 나는 곳은 서로 다른 생성기를 씁니다.

섞어 둔 카드 더미에 빗대면

카드 한 벌을 잘 섞어 엎어 둔 모습을 떠올려 봅니다. 위에서부터 한 장씩 뒤집으면 보는 사람은 다음 카드를 짐작하기 어렵습니다. 섞은 순서를 적어 둔 사람에게는 다음 카드가 훤히 보입니다.

무엇을 받아 무엇을 내놓나

난수 생성기(RNG, Random Number Generator)는 부를 때마다 수를 하나씩 내놓습니다. 이렇게 나온 수가 난수입니다. 목록을 섞거나 추첨할 때처럼 프로그램이 무작위로 골라야 하는 곳에서 부릅니다.

난수가 지켜야 하는 첫째 성질은 균등 분포입니다. 나올 수 있는 값이 전부 같은 확률로 나와야 합니다. 한쪽 값이 더 자주 나오면 추첨이 공정하지 않게 됩니다.

둘째 성질은 예측할 수 없다는 것입니다. 앞에 나온 값을 아무리 모아도 다음 값을 짐작할 수 없어야 합니다. 이 성질이 깨지면 공격자가 로그인 토큰 같은 값을 미리 계산해 냅니다.

많은 생성기가 처음에 값 하나를 받습니다. 이 값이 시드(seed)입니다. 시드는 생성기가 어디서부터 수를 뽑기 시작할지 정합니다. 앞의 카드 비유로는 섞은 순서에 해당합니다.

계산으로 뽑는 유사난수 생성기

컴퓨터가 따로 장치를 달지 않고 수를 얻는 길은 계산뿐입니다. 그래서 대부분의 난수 생성기는 수를 계산으로 만듭니다. 계산은 같은 입력에 늘 같은 결과를 내므로, 이 수는 진짜 무작위가 아니라 무작위처럼 보이기만 합니다. 이런 생성기가 유사난수 생성기(PRNG, Pseudo-Random Number Generator)입니다.

유사난수 생성기는 안에 값 하나를 들고 있습니다. 이 값이 상태입니다. 부를 때마다 상태를 정해진 식으로 바꿉니다. 바뀐 상태에서 출력을 하나 꺼냅니다.

flowchart TD
    S["시드"] --> A["상태 1"]
    A --> B["상태 2"]
    B --> C["상태 3"]
    A -.-> O1["출력 1"]
    B -.-> O2["출력 2"]
    C -.-> O3["출력 3"]

상태는 한 줄로 이어집니다. 출력은 그 줄에서 곁가지로 나옵니다. 줄 맨 앞의 시드가 첫 상태입니다. 그래서 시드와 식을 알면 출력 전부를 다시 만들 수 있습니다.

가장 단순한 식 하나가 선형 합동 생성기입니다. 지금 상태에 수 a 를 곱하고 c 를 더합니다. 그 결과를 m 으로 나눈 나머지가 다음 상태입니다. 아래는 a 를 5, c 를 3, m 을 16 으로 잡고 시드 7 에서 출발한 것입니다.

int x = 7;             // 시드
x = (5 * x + 3) % 16;  // 6
x = (5 * x + 3) % 16;  // 1
x = (5 * x + 3) % 16;  // 8
x = (5 * x + 3) % 16;  // 11

이 식은 상태를 곧 출력으로 씁니다. 6·1·8·11 은 흩어져 보입니다. 그래도 한 줄 한 줄은 곱셈과 나머지 계산입니다. 시드 7 과 식을 아는 사람은 같은 수를 똑같이 뽑습니다.

되풀이되는 주기

위 식을 계속 돌리면 열여섯 번째에 다시 7 이 나옵니다. 상태가 가질 수 있는 값이 0 부터 15 까지 열여섯 가지뿐이기 때문입니다. 같은 상태가 한 번 다시 나오면 그 뒤는 앞과 똑같이 흘러갑니다.

다시 처음으로 돌아오기까지의 길이가 주기입니다. 상태가 클수록 주기를 길게 만들 수 있습니다. 실무에서 쓰는 생성기는 상태를 훨씬 크게 잡습니다. 주기가 한 바퀴 다 돌기 전에 프로그램이 먼저 끝납니다.

같은 시드가 내는 같은 수열

유사난수 생성기는 같은 시드를 받으면 같은 수열을 냅니다. 이 성질을 재현성이라고 부릅니다. 무작위 데이터로 돌린 테스트가 실패했을 때 같은 시드로 다시 돌리면 같은 실패를 다시 볼 수 있습니다.

Java 의 java.util.Random 으로 보면 이렇습니다.

var a = new Random(42);
var b = new Random(42);
a.nextInt() == b.nextInt()  // true

두 객체는 따로 만들었지만 시드가 같아서 첫 값이 같습니다. 둘째 값과 셋째 값도 계속 같습니다.

이 성질은 시드를 공격자가 짐작할 수 있을 때 약점이 됩니다. new Random(System.currentTimeMillis()) 처럼 현재 시각을 시드로 직접 넣는 코드가 흔합니다. 공격자는 그 시각 앞뒤의 값 몇 개만 시드로 넣어 보면 같은 수열을 다시 만들어 냅니다.

물리 현상에서 얻는 참난수

계산이 아닌 곳에서 무작위를 얻는 방법도 있습니다. 전자 회로의 열잡음처럼 미리 알 수 없는 물리 현상을 재서 수로 바꿉니다. 이런 생성기가 참난수 생성기(TRNG, True Random Number Generator)입니다.

운영체제도 비슷한 재료를 씁니다. 키보드를 누른 시각이나 디스크 인터럽트가 들어온 시각을 아주 잘게 잰 값이 그런 재료입니다. 인터럽트는 장치가 프로세서에 일이 생겼다고 알리는 신호입니다. 이런 시각의 끝자리는 미리 짐작하기 어렵습니다.

모은 값이 얼마나 짐작하기 어려운지를 엔트로피라고 합니다. 엔트로피가 클수록 공격자가 값을 맞히기 어렵습니다. 운영체제는 이런 값을 엔트로피 풀이라는 곳에 조금씩 모아 둡니다.

참난수는 느리고 양이 적습니다. 물리 사건이 일어나는 만큼만 나오기 때문입니다. 값이 한쪽으로 조금 쏠려 있기도 합니다. 그래서 이 재료는 곧장 쓰기보다 아래 암호학적 난수 생성기의 시드로 넣습니다.

다음 값을 못 맞히게 만든 암호학적 난수 생성기

암호학적 난수 생성기(CSPRNG, Cryptographically Secure Pseudo-Random Number Generator)는 출력을 아무리 모아도 다음 값을 맞힐 수 없게 만든 유사난수 생성기입니다. 이것도 계산으로 수를 뽑습니다. 차이는 시드와 식에 있습니다.

앞의 선형 합동 생성기는 출력이 곧 상태였습니다. 출력 하나를 본 사람은 다음 값을 바로 계산합니다. 식이 단순하면 상태를 숨겨도 출력을 모아 상태를 되짚어 낼 수 있습니다. 암호학적 난수 생성기는 시드와 식 두 곳에서 이 되짚기를 막습니다.

시드로는 운영체제의 엔트로피 풀에 모아 둔 값을 씁니다. 공격자가 짐작할 수 없는 시드라서 수열을 다시 만들 출발점이 없습니다.

식으로는 출력만 보고 상태를 거꾸로 풀 수 없는 계산을 씁니다. 예를 들면 암호학적 해시 함수나 블록 암호가 그런 계산입니다. 출력을 아무리 모아도 상태로 거슬러 올라갈 수 없으니 다음 값도 계산하지 못합니다.

Java 에서는 java.util.Random 이 유사난수 생성기입니다. java.security.SecureRandom 은 암호학적 난수 생성기입니다. 토큰을 Random 으로 뽑으면 출력을 모은 공격자가 다음 토큰을 계산해 냅니다.

flowchart TD
    N["열잡음 · 인터럽트 시각"] --> P["엔트로피 풀"]
    P -->|시드| C["암호학적 난수 생성기"]
    C --> T["토큰 · 암호 키 · 솔트"]
    X["고정한 값 · 현재 시각"] -->|시드| R["유사난수 생성기"]
    R --> U["목록 섞기 · 테스트 데이터 · 시뮬레이션"]

위 갈래는 시드부터 공격자가 짐작할 수 없는 재료에서 옵니다. 아래 갈래는 시드를 남이 알아도 되는 일에 씁니다. 위 갈래 끝의 솔트는 비밀번호를 해시하기 전에 덧붙이는 무작위 값입니다.

원하는 범위로 옮길 때 생기는 쏠림

생성기가 내는 수는 대개 정해진 비트 수만큼의 정수입니다. 쓰는 쪽은 0 부터 9 까지처럼 좁은 범위를 원합니다. 흔히 나머지 연산으로 범위를 줄입니다.

이 방법은 값을 한쪽으로 쏠리게 합니다. 0 부터 15 까지 고르게 나오는 수를 10 으로 나눈 나머지로 바꿔 보면 드러납니다. 아래 표는 원래 값이 어느 나머지로 가는지를 보입니다.

0 부터 5 까지는 원래 값 두 개에서 나옵니다. 6 부터 9 까지는 하나에서만 나옵니다. 그래서 앞쪽 여섯 개가 뒤쪽 넷보다 두 배 자주 나옵니다. 이 쏠림을 모듈로 편향이라고 부릅니다.

막는 방법은 범위를 넘치는 값을 버리는 것입니다. 위 예라면 10 이상이 나올 때 버리고 다시 뽑습니다. 그러면 0 부터 9 까지가 같은 확률로 남습니다. Random 의 nextInt(10) 처럼 범위를 받는 함수는 안에서 이 버리기를 합니다.

한 번 뽑는 비용

유사난수 생성기는 한 번 부를 때 곱셈과 덧셈 같은 연산 몇 개만 합니다. 그래서 한 번 뽑는 시간은 O(1), 곧 몇 번째 수를 뽑든 일정합니다. 쓰는 메모리는 상태 하나의 크기로 정해져 있습니다.

암호학적 난수 생성기도 한 번 뽑는 시간은 일정합니다. 대신 그 한 번이 해시나 암호 계산이라 훨씬 무겁습니다. 수백만 개를 뽑는 시뮬레이션에서는 이 차이가 쌓여 전체 시간을 늘립니다.

쓸 때와 안 쓸 때

아래 표는 하려는 일마다 어느 생성기를 쓰는지 가립니다. 표에 나오는 nonce 는 암호 계산에 한 번만 쓰고 버리는 값입니다.

앞쪽 세 줄은 값을 들켜도 손해가 없는 일입니다. 가운데 두 줄은 공격자가 값을 맞히면 계정이나 암호가 뚫립니다. 여기에 유사난수 생성기를 쓰면 출력을 모은 사람이 다음 값을 계산해 냅니다.

마지막 줄은 생성기 종류와 따로 봐야 합니다. 난수는 겹칠 확률을 낮출 뿐 겹침을 없애지 못합니다.

관련 항목

난수 생성기의 하위 종류

유사난수 생성기 · 참난수 생성기 · 암호학적 난수 생성기 · 하드웨어 난수 생성기

유사난수 생성기를 구현한 알고리즘

선형 합동 생성기 · 메르센 트위스터 · Xorshift · PCG · ChaCha20 · HMAC_DRBG · CTR_DRBG

난수 생성기의 품질을 재는 성질

균등 분포 · 주기 · 재현성 · 엔트로피 · 예측 불가능성 · 모듈로 편향 · 통계적 검정

난수 생성기에 들어가는 시드와 그 재료

시드 · 엔트로피 풀 · 열잡음 · 인터럽트 · getrandom

난수 생성기로 뽑는 보안 값

토큰 · 세션 식별자 · 암호 키 · 솔트 · nonce · 초기화 벡터 · UUID

난수 생성기를 부르는 기법

셔플 · 피셔-예이츠 셔플 · 몬테카를로 방법 · 무작위 샘플링 · 지수 백오프 · 지터 · 속성 기반 테스트

난수 생성기와 헷갈리는 이웃

해시 함수 · 유사난수 함수 · 암호학적 해시 함수 · 블록 암호 · 일련번호