난수(Random). 진짜 난수와 가짜 난수

고품질의 난수를 만드는 것은 컴퓨터 과학에서 꽤 인기있는 토픽이었다.

난수, 그러니까 랜덤값은 단순히 응용프로그램 수준에서 무작위의 값을 뿌려주는 용도로도 사용되지만, 깊이 들어가면 보안에서도 중요한 위치를 차지하고 있기 때문이다.

보안과 난수, 예측 가능성

상당수의 보안 관련 알고리즘들은 난수를 매우 깊게 활용한다.
모든 시스템 전반에 널리 쓰이는 공개키 알고리즘, 대칭키 알고리즘 같은 핵심 암호화 기법만 해도 난수를 기반으로 결정론적 처리에서 나올 수 있는 보안 취약점을 우회-보완한다.

근데 사실 진짜 난수를 만드는 것은 매우 어려운 일이다.
대부분의 소프트웨어/하드웨어 수준 구현은 진짜 난수가 아닌 의사(Pseudo) 난수라고 불리고, 어떻게든 추측할 방법이 존재한다.

난수 생성의 구성요소

난수 생성은 크게 2가지 부분으로 구성된다.
랜덤성을 부여하는 "시드(Seed)"와, 시드를 기반으로 최종 랜덤값을 만드는 "알고리즘"이다.

시드도 중요하지만 알고리즘 자체도 분포나 성능 등에 영향을 많이 미치기 때문에, 이런저런 알고리즘들이 많이 나와있다. 하지만 여기서는 개별 알고리즘들에 대해서 다루지는 않겠다.
난수의 품질을 결정하는 최종 요소는 어쨌든 "시드"이기 때문이다.

가장 단순한 난수 시드: 시간

난수가 가져야 하는 기본적인 특성은, 거의 항상 다른 값이 나와야 한다는 것이다.
그럼 그걸 구현하는 가장 간단한 방법이 뭘까?

바로 시간이다.

대부분의 하드웨어 장치에는 타이머가 내장되어있고, 시간은 계속해서 변화하니까 난수로서의 기본 요건은 충족한다고 할 수 있다.

그래서 20세기, 초기의 난수 구현은 저 C 코드처럼 시간값을 기반으로 구현되는 경우가 많았다.
70-80년대까지만 하더라도 이 방법론이 지배적이었다.

이 접근법의 문제는, 추측이 너무 쉽다는 것이다. 시간을 기반으로 하기 때문에, 그걸 언제 시도했는지만 알 수 있다면 대략적으로 어떤 값이 나왔다는 것을 때려맞출 수 있다.

그래서 보안이 중요한 사례들에서는 더 이상 이런 방법을 쓰지 않는다.

근데 그렇다고 시간 난수를 아예 안쓰는건 아니고, 보안이 중요하지 않은 경우에는 많이 쓴다.
브라우저 자바스크립트에 있는 Math.random만 해도 시간값 가져다가 난수를 만든다. 이래나저래나 가장 빠르고 만들기 쉬운 방법이기 때문이다.

시드: 하드웨어 노이즈

지금 시점에서 "시간 시드"의 가장 합리적인 대안은 하드웨어 노이즈를 사용하는 것이다.

다음 C++ 코드는 하드웨어 노이즈 기반의 난수를 만든다.

저 random_device가 그 시드에 대한 기능이다.

이건 내부적으로 이런저런 하드웨어 장비들에서 발생하는 불규칙한 패턴들을 끌어다가 부수적으로 활용하는 건데, 이런걸 "엔트로피"라고 부른다.

엔트로피의 원천으로 삼을만한 소스는 꽤 많다. OS에서 인터럽트가 발생할때마다 그 미묘한 시간 간극/변동을 수집하기도 하고, 키보드 입력, 마우스 사용 시간, I/O 타이밍, 등 다양한 소스를 활용할 수 있다. 실제로도 그러고 있고.

대부분의 주요 OS 커널에서는 노이즈에 기반한 랜덤값 시드를 미리 만들어서 제공해준다.
Linux의 경우에는 /dev/urandom이라는 파일에 랜덤값을 수집해서 넣어준다. 읽어서 쓰기만 하면 된다.

방금 C++ 코드도 사실 내부적으로는 이걸 읽어서 시드로 쓴다.

아무튼 이 방법은 꽤 품질이 좋은 난수를 만들어낸다고 할 수 있다.
각각의 하드웨어 내에서 불규칙하게 발생하는 패턴값을 도대체 어떻게 알고 추측을 하겠는가?

그래서 대부분의 상황에서는 이 정도의 시드값 구성으로도 추측이 거의 불가능한 고품질 난수를 만들 수 있고, 대부분의 개발자들은 여기에 만족한다.

하지만 이론적으로는 여전히 완전한 난수는 아니다. 하드웨어 특성을 알고, 타이밍을 측정할 수 있고, 이런저런 변수들을 다 고려할 수 있다는 거의 불가능에 가까운 전제를 깔면 추측이 진짜 불가능한건 아니기 때문이다.

직접 하드웨어 시드 구성

일반적인 컴퓨터들의 하드웨어 노이즈로도 부족하다고 느낀다면, 아예 자체적으로 하드웨어를 구성해서 난수를 뽑는 방법도 있다.

그 중에 가장 흥미롭고도 유명한 사례가 Cloudflare의 Lava lamp다.

https://www.cloudflare.com/ko-kr/learning/ssl/lava-lamp-encryption/
거의 무작위로 깜빡이는 전등을 잔뜩 깔아두고, 그걸 사진으로 찍은 다음에 그 사진을 소스로 쓰는 것이다.
실제로 유용한 엔트로피 중 하나로 쓰고 있고, 현재진행형이다.

여기서 얻을 수 있는 재밌는 통찰은, 꼭 우아한 방법이 아니어도 된다는 것이다.

이거 말고도 이중 진자를 깔아두고 쓴다거나 하는 방법도 있다.

진짜 난수 시드?: 방사성 붕괴

그럼에도 불구하고, 진짜 난수를 만드는 것이 불가능한건 아니다. (현재 알려진 바로는)
양자역학이 개입되기 시작하면 추측 불가능한 영역이 생기게 되는데, 그 대표적인 경우가 방사성 붕괴 시간이다.

https://byjus.com/physics/radioactive-decay/
현대 물리학 이론으로는 방사성 원소가 언제 붕괴될지 알 수 없기 때문이다. 그러니까 대충 어느 정도 지나면 통계적으로 어느 정도 줄어들지는 알지만(반감기), 각각의 원소 단위가 언제 붕괴할지는 모른다.

그래서 실제로 원소가 붕괴되는 시간을 기록해서 사용한다면 진짜 난수를 만들 수 있다.

물론 비용이 천문학적으로 커지기 때문에, 이걸 의미있게 사용하는 사례는 별로 없는 것으로 안다.

NIST를 비롯해 일부 장비를 가진 기관에서는 이걸 API로 제공하긴 하더라.

근데... 쓰는 사람이 있나? 모르겠다.

참조
https://en.wikipedia.org/wiki//dev/random
https://www.cloudflare.com/ko-kr/learning/ssl/lava-lamp-encryption/