1. 개요
시스템적으로 임의의 수를 만들어 적용하는 기준을 말한다.2. 상세
역설적이게도, 사실 컴퓨터는 난수를 만들 수 없다. 컴퓨터는 사람과 달리 무의식적인 선택, 또는 우연에 의하는 선택을 할 수 없기에 기본적으로 정해진 입력에 따라 정해진 값을 낼 뿐이다. 전문용어로는 '결정적 유한 오토마타(Deterministic Finite Automata)'. 흔히 보는 랜덤은 정말로 임의의 값이 아니고 특정한 방법으로 계산하거나 몇 밀리초(ms) 단위로 시시각각 변하는 값을 초기값으로 잡고[1] 여러 계산 과정을 거쳐 사람이 볼 때에 마치 임의의 값인 것처럼 보이게 하는 것이다. '의사난수(擬似亂數/Pseudo Random)'라고 한다.흔히 난수표를 쓰는데 난수표가 정해진 이상 결국은 같은 순서로 같은 숫자가 나온다. 패미컴 버전 봄버맨을 시작할 때 1탄의 벽돌들이 대체로 일정하게 배열되는 점을 떠올리면 어느 정도 이해가 갈 것이다. 비슷한 예로 MS-DOS 버전 테트리스에서 나오는 블럭의 순서가 모두 똑같으며, 크레이지 아케이드 테트리스도 난수가 제대로 생성되지 않았던 탓에 테트리스 계의 똥겜으로 전락할 뻔했다. 난수표를 여러 개 만들어 놓고 매번 다른 난수표를 읽히면 이 문제를 해결할 수 있다. 이 난수표를 선택하는 것을 ' 시드'라고 한다. 그런데 시드값이 똑같으면 선택되는 난수표도 똑같기 때문에 시드값도 난수여야 한다. 즉, 난수를 만들려면 난수가 필요한 문제가 발생하는 것.
여러 개선책이 있지만 근본적으로 시드를 기반으로 한 랜덤함수는 완전한 무작위라고 보기가 힘들다. 특정 패턴의 경우 영원히 안 나올 수도 있고[3], 시드값 생성에 요구하는게 너무 적다면 정밀도가 낮을 경우는 전원 패턴이나 타임테이블 논란[4] 같은 극단적인 일도 생길수 있다. 암호화에도 문제가 되는데, 시드 기반 난수로 암호화 키를 생성하는 경우 키 값의 일부를 알고 있다면 나머지 키 값도 유추하는게 가능해질 수 있다. 일반적인 게임에서는 어느정도의 무작위성으로도 충분하지만, 현찰이 오가는 도박 사이트처럼 정말 랜덤이 필요한 경우 시드 기반의 의사랜덤은 쓰지 않는다.
1997년 개발된 MT19937(후술할 메르센 트위스터의 일종이다.)를 예로 들자면, 이 알고리즘으로 생성된 난수는 623개까지 연속된 난수를 뽑아볼 때 각 난수의 처음 32비트는 동일분포가 보장된다(32-bit accuracy). 다만 623에서 단 하나 늘어난 624개의 연속된 난수만 어떻게 확보한다면 시드값을 털어버릴 수 있는 치명적인 문제가 있어서 보안이 필요한 곳에서 쓰려면 좀 꼼수가 필요하다.[5] 결과값을 공개하기 전에 해시 함수로 원본을 알아내지 못하게 한다든가 난수를 한 번에 생성한 후 순서를 뒤섞어서 공개한다든가. 이런 좋은 MT19937이란 알고리즘은 Python, PHP 등 대부분의 프로그래밍 언어에서도 이미 기본으로 쓰고 있는 알고리즘이고, C/C++에서 쓰고 있는 rand() 함수가 언어 역사만큼 오래된 안 좋은 랜덤 알고리즘을 쓰고 있을 뿐이다.
현실을 재현하는 것이 아닌 실용 프로그래밍, 특히 단방향 암호화를 포함한 보안 계열을 제외한 실제 응용 프로그램 설계에선 완전 난수보다 의사 난수가 더 많은 분야에 유용하다. 의사난수의 '같은 시드는 같은 결과를 부른다'를 장점으로 활용해, 네트워크 게임의 플레이어 간 동기화에서부터 리플레이 모드 구현까지[6] 오만 곳에 써먹을 수 있다. 마찬가지로 도박에서 원하는 결과가 나오게 악용할 수 있다. 이런 걸 난수조절이라고 한다.
특히 재화가 현실 금전과 바로 연결되는 랜덤 박스가 BM인 게임은, 이 난수 생성도 예측 불가능한 것으로 해야만 한다.
3. 난수 발생 방식
난수를 발생시키는 수식엔 여러가지가 있는데, 중앙 제곱법과 합동식 방법 등이 있다. 난수 발생 원리에 대해 자세히 알고싶으면 위키피디아를 참고.3.1. 중앙제곱법
영어 : Mid Square Method일본어 : 中二乗法
의 가운데 a자리
X는 난수 수열, a는 원하는 자릿수( 10진법으로), 시드(X0)는 임의의 a자리인 수[7].
Middle-square method. 폰 노이만이 1949년에 고안한 의사난수법. 생성된 품질이 좋지 않기 때문에 그 당시의 컴퓨터면 몰라도 그 이후 시대에는 웬만하면 아래의 선형합동법을 사용한다.[8]
초기 값이 2345이고, 가운데에서 4자리를 선택하여 5개의 난수를 만드는 경우에는 다음과 같다.
#!syntax cpp
#include <stdio.h>
#include <math.h>
int main(void)
{
int i;
long num1 = 1000000, num2 = 100, temp;
double k = 2345, temp1, temp2;
for(i=1; i<=5; i++)
{
temp1 = pow(k, 2);
temp = temp1 / num1;
temp2 = temp1 - temp * num1;
temp = temp2 / num2;
printf("%5d\n", temp);
k = temp;
}
return 0;
}
3.2. 선형합동법
線形合同法 / Linear congruential sequence#!syntax cpp
static UINT32 next = 1;
int __cdecl rand(void)
{
next = next * 1103515245 + 12345;
return (UINT32)(next>>16) & RAND_MAX;
}
void __cdecl srand(unsigned int seed)
{
next = seed;
}
출처
X는 난수 수열. ANSI C 표준은 m = 231, a = 1103515245, c = 12345. 시드는 이 수열에서 X0의 값을 말한다.
__cdecl 은 함수 호출 규약인데, 생략해도 상관없다. 함수에 진입할 때, 나올 때 어떻게 매개변수를 전달하고 처리하는지를 지정하는 컴파일러 키워드이다.
Linear Congruential. 가장 널리 쓰이는 유사난수법.
계산이 매우 빠르기 때문에 초창기부터 컴퓨터에 널리 사용되었으며, 흔히 쓰이는 rand() 함수는 바로 이것이다. 난수분포가 치우쳐 있고, 주기성이 있다는 결점이 있지만 계산속도가 빠르기 때문에 지금도 난수의 품질을 크게 신경쓰지 않는 경우에는 널리 사용된다. 그런데 시드가 같으면 의미도 없기에 보통은 srand(time(0))으로 난수를 초기화한다. 요즘에는 이 과정을 객체 차원에서 수행하는 모듈도 많이 나와 있다.
서울대학교 이인석 교수가 쓴 선형대수 명저 선형대수와 군의 표지가 선형합동법으로 생성된 난수로 빼곡히 채워져있다. [math(a = 1664525, b = 1013904223, x_1=1015568748, m = 2^{32})]이다. 참고로, 표지의 값으로 [math(a, b, x_1, m)]을 구하는 문제가 연습문제로 나와있다.
3.3. 메르센 트위스터
Mersenne-twister. 흔히 mt_rand()라는 이름을 가진다. 메르센 소수라는 것을 이용하며 선형 합동법보다 우수한 난수의 품질과 속도를 인정받아 C++11 부터는 mt19937 이 표준으로 채택되면서 C++11 부터는 아래와 같은 코드로 메르센 트위스터를 이용한 난수생성이 가능하다.#!syntax cpp
#include <iostream>
#include <random>
int main(void)
{
std::random_device random; //하드웨어 리소스를 기반으로 난수를 생성
std::mt19937 engine(random()); //메르센 트위스터 방식으로 난수를 생성하겠다는 선언
std::uniform_int_distribution<int> distribution(0, 100); //난수의 범위와 자료형 정의. rand() % 100과는 다르게 100도 나올 수 있음
auto generated = distribution(engine);
std::cout << generated << std::endl;
}
메르센 트위스터의 작동 원리/수식은 본 문서 타 문단의 알고리즘들과 비교해 훨씬 어렵고 더 복잡하다. 위키백과 참고. 참고로 PHP는 7.1 버전 이전에는 구현이 잘못되어[9] 엉뚱한 난수값을 뱉어냈었다(...).
3.4. XOR 시프트
#!syntax cpp
uint32_t x, y, z, w;
uint32_t xorshift128(void) {
uint32_t t = x;
t ^= t << 11;
t ^= t >> 8;
x = y; y = z; z = w;
w ^= w >> 19;
w ^= t;
return w;
}
Xorshift. XOR과 비트시프트 연산을 사용하는 난수 발생법. 구조상 현대의 컴퓨터에서 연산 속도가 매우 빠르고 품질도 선형합동법보다 좋다. 그렇지만 몇몇 난수 품질 테스트를 통과하지 못하는 경우가 있어 여러 변종이 나와 있다. 아래는 이를 다소 해결한 변종 중 하나인 Xorshift+로 2128 - 1의 주기를 가진다.
#!syntax cpp
#include <stdint.h>
/* The state must be seeded so that it is not everywhere zero. */
uint64_t s[2];
uint64_t xorshift128plus(void) {
uint64_t x = s[0];
uint64_t const y = s[1];
s[0] = y;
x ^= x << 23; // a
s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
return s[1] + y;
}
4. 진짜 난수 측정
앞선 방법은 좋은 아이디어로 그럴 듯한 난수를 만들어내지만 이들이 만들어내는 난수는 결국 어디까지나 의사난수(Pseudo Random)이다. 시드에서도 설명했지만, 진짜 난수는 입력으로 받아야 한다. 인간이 난수를 입력하는 대신, 자연의 무작위성을 측정해서 난수로 변환하면 된다. 해당 자연계를 완전히 흉내내는 것은 불가능에 가깝기에 의사난수와는 달리 패턴을 특정할 수 없다는 강점이 있다. 특히 양자난수의 경우 불확정성 원리에 의해 시뮬레이션이 원천 봉쇄된다.가장 많이 알려진 것은 True Random Number Generator 사이트로, 이 사이트에서 사용하는 하드웨어는 주변 노이즈를 기반으로 난수를 생성한다. ( TRNG) 호주국립대학교(ANU)에서는 양자난수 생성기(QRNG)를 사용하고 있는데, 해당 사이트에서는 진공에서의 양자요동을 측정하여 난수를 생성한다. ( ANU QRNG) ANU의 QRNG와 비슷한 것이 바로 가이거 계수기인데, 가이거 계수기를 때리는 방사선 등을 통해 진짜 난수를 쉽게 생성할 수 있다.
Cloudflare는 라바 램프가 나열된 벽을 찍은 화상에서 노이즈를 추출하여 난수를 생성한다. 설명 참조
보안 기능을 제공해주는 하드웨어인 TPM에는 난수생성이 존재한다. 2021년 10월에 출시된 Windows 11의 필수 요구 사항에 TPM이 포함되어서 TPM 모듈을 사서 장착하거나 펌웨어에서 가상 TPM 기능을 켜는 경우가 많아졌다.
삼성전자의 스마트폰 갤럭시 퀀텀 시리즈에는 SK텔레콤에서 개발한 '양자난수생성칩'을 탑재하여 진짜 난수를 생성하여 보안을 강화시켰다.
Apple Silicon에 탑재되는 Secure Enclave는 TRNG 모듈을 내장하여 랜덤 키, 랜덤 시드, 또는 다른 엔트로피들을 생성할때 TRNG를 통해 진짜 난수를 생성하여 사용한다. 이 TRNG는 여러개의 링 오실레이터를 기반으로 CTR_DRBG 알고리즘을 사용하여 난수를 생성한다. Apple Support 페이지의 Secure Enclave 설명
5. 난수가 아닌 비예측성 현상
디지털에서 흔히 '매번 동일한 결과가 나오지 않는' 대표적인 예시로서 소프트웨어에서의 스레드 경합에 의한 컨텍스트 접근 순서가 있다. 데이터 경합은 여러 스레드가 하나의 데이터에 접근해 읽고 쓸 때 발생하는 현상으로, 가령 여러 스레드에서 반복해서 '똑같은 메모리 위치에 1씩 숫자를 추가해 간다' 라는 작업을 실행시킬 경우 같은 메모리 위치에 접근하기 위해 스레드끼리 경쟁하는 현상이다.위에서 말한 작업을 실행하려면 CPU에서는 최소한 3개의 서로 다른 명령을 수행해야 하는데,
1. 메모리에 들어 있는 현재의 값을 가져온다
2. 값에 1을 더한다
3. 커진 숫자를 메모리에 쓴다
컴퓨터의 구조상, 각각의 스레드가 1번에서 3번까지의 과정을 한꺼번에 한다는 보장이 없다. A 스레드가 '1' 이라는 값을 읽고 열심히 덧셈을 하는 사이, B 스레드가 끼어들어 메모리를 또 읽고는 '현재의 값은 1이군' 하고 자기 작업을 하러 가는 식의 일이 벌어지기 때문이다. 이렇게 되면 여러 스레드가 제각기 +1 하는 작업을 했지만 결과는 '2' 라는 답을 여러번 중복제출하는 것에 지나지 않기 때문에, 명령이 내려진 횟수에 비해 결과 숫자가 더 적어진다.
상식적으로 생각한다면, 컴퓨터가 이론적으로 엄밀하게 동작할 때 이러한 끼어듬 현상은 매번 동일하게 발생해야 할 것이다. 예를 들어 10개의 스레드로 100번 덧셈을 시키면, 같은 CPU의 컴퓨터에서 실행시켰을 때 1000은 아니지만 무조건 950이라는 결과가 나오는 등으로.
그러나 현실에서는 이 '줄어드는 양'이 규칙적이지 않고 오락가락하는데, 이는 이러한 스레드 동작 순서를 관리하는 것이 운영체제 커널의 역할이며, 운영체제는 위에 언급한 프로그램의 실행 이외에 수많은 다른 작업을 동시에 실행하며 각각 모두에게 스레드 순서를 분배하고 있기 때문이다. 이 때 할당(Time slice)을 교체하는 경계선을 보통 일정 시간 주기로 나누는데, 이러한 외부 작업의 상황이 완전히 동일하리라는 보증은 사실상 불가능하므로, 개별 프로그램의 입장에서 보면 '자기 스스로가 생성한 멀티스레드 작업의 실행 순서는 자기가 예측할 수 없다' 를 전제로 작성되어야만 한다. 이것은 멀티스레드 프로그래밍의 기본 원칙이며, 하드웨어가 싱글코어냐 멀티코어냐에 무관하게 컨텍스트 스위칭 환경의 고유한 특성이다.
그러나 반드시 유의할 점은 이것은 어디까지나 '예측불가능성' 이지, '난수성' 이 아니라는 것이다. 이러한 현상을 소스코드로 재현하여도 이는 멀티스레드에 대한 예제코드이지, 절대로 임의의 수를 생성하는 용도로 사용해서는 안 된다. 난수는 수학적으로 의도된 '확률적 분포' 를 추종하도록 알고리즘을 짜거나, 실제로 그러한 확률 엔트로피를 갖는 물리적 현상에서 관측되어야만 한다. 실제로 스레드 경합 코드를 짜면 운영체제에 따라 다르더라도 대부분 매우 거친 분포범위를 가지며[10], 연속으로 실행하면 같은 숫자가 마구 튀어나오는 일이 다반사이다. 이는 비슷한 시스템과 가까운 시점에서 구동되었을 때의 결과들이 생판 다른 시스템과 다른 시점에서 돌렸을 때보다 더 근접할 가능성이 높은 것이며, 난수라는 개념의 근본에 어긋난다.
6. 관련 문서
[1]
정말 극단적인 예를 들면, 0.001초에 누르면 난수는 1, 0.002초에 누르면 난수는 2.... 이런식으로 시간을 난수에 대입시킨것이다. 물론 실제 계산은 더 복잡하다.
[2]
키보드의 키를 누른 시간 간격을 샘플링 한 것, 사용자의 입력 자체,
VeraCrypt에서도 쓰인 마우스 움직임 등.
[3]
예를 들면
아랑전설 3의 숨겨진
초필살기인 잠재능력의 발동 방법은 랜덤 발동과 커맨드 입력 발동 두 가지가 있는데, 랜덤으로 발동되는 확률인 1/1024를 만족하는 난수가 안 나와서 랜덤으로는 절대로 발동이 안 된다.
[4]
정밀도가 낮은 시드값을 써서 문제되었는데, 당시 증상 때문에 시간만 쓴 것으로 추정되었다.
[5]
의사난수인 이상 시드값을 알면 모든 결과를 미리 계산할 수 있다.
[6]
스타크래프트의 리플레이 모드를 생각해 보면 된다. 게임의 시드만 저장하면 AI의 모든 판단을 다 저장할 필요가 없어진다.
[7]
a=6이면 100000 ≤ X0 ≤ 999999 의 범위 중 하나를 쓰라는 말
[8]
결정적으로, 의 값이 0일 때 인 의 모든 값이 0이다(...). 회차마다 난수에 상수를 더해봐도 계속 가다 보면 어느 순간 반복되는 일정한 패턴이 나타난다.
[9]
더 경악할 만한 사실은 해당 링크에서 나온
소스 코드 부분은 이 그릇된 구현을 바로잡았었는데
PHP 주 제작진에 의해 이전으로 롤백된 상황(...).
[10]
이것은 컨텍스트 스위칭의 '경계선' 이라는 희박한 사건에 의존하기 때문이다