의사난수 생성기

우리가 물질계를 관찰할 떄 무작위의 변동을 어디서나 볼 수 있습니다 우리는 무작위의 숫자를 노이즈라고 불리는 무작위의 변동을 측정하며 만들 수 있습니다 노이즈를 측정하는 것을 샘플링이라 하고 샘플링을 하면 숫자를 얻을 수 있습니다 하나 둘 셋 넷 예를 들면 우리는 이러한 텔레비전 정적 전류를 시간에 따라 측정해 진정한 무작위의 순서를 만들 수 있습니다 이 난수를 숫자에 따라 방향이 달라지는 길을 이 난수를 숫자에 따라 방향이 달라지는 길을 그려서 상상해 볼 수 있습니다 이것은 랜덤워크라고 불립니다 어떤 스케일에도 패턴이 생기지 않죠 이 수열에 각 지점에서 다음 움직임은 항상 예측 불가능합니다 무작위의 과정들은 항상 비결정론적이라고 합니다 다음 수를 예측할 수 없기 때문이죠 반면에 기계들은 결정론적입니다 기계의 시행은 항상 예측 가능하고 반복 가능하죠 1946년에 존 폰 노이만은 군에서 계산에 관련된 일을 하였고 특히 수소폭탄을 디자인하는 일에도 동참하였습니다 노이만은 ENIAC이란 컴퓨터를 사용해 핵분열에 일어나는 화학반응을 계산하려고 시도했었습니다 하지만 이를 계산하기 위해선 빠르게 난수를 만들 수 있어야 했고 필요시 계속될 수 있어야 했습니다 그런데 ENIAC은 제한된 내부기억장치가 있어서 긴 임의의 숫자를 저장할 수 없었습니다 그래서 노이만은 다음과 같은 무작위성을 기계적으로 구현하는 알고리즘을 만들었습니다 첫째로 seed라는 난수를 정해야 했습니다 이 숫자는 노이즈를 측정하거나 혹은 시각을 밀리초로 표현했을때 얻을 수 있었습니다 그 다음 seed는 단순한 계산에 입력됩니다 이 seed를 제곱하여 그 결과의 중간을 출력합니다 그리고 출력값을 다음 seed로 사용합니다 또 이 과정은 필요한 만큼 반복할 수 있습니다 이것은 중앙제곱법이라고 불립니다 그리고 이것이 의사난수 수열 만들기의 시작입니다 그리고 이것이 의사난수 수열 만들기의 시작입니다 이 수열의 무작위성은 최초의 seed의 무작위성에만 의존합니다 같은 seed를 입력하면 같은 수열이 나오게 됩니다 그러면 무작위로 만든 수열과 의사난수의 수열을 만드는 방법의 차이점이 뭘까요 이 수열을 랜덤워크로 그려봅시다 처음엔 비슷하게 생겼지만 빨리 만들면 달라집니다 이 의사난수의 수열은 결국엔 반복됩니다 이 현상은 알고리즘에서 최초의 seed가 다시 나올 때 나타나고 이 수열은 그 뒤로 반복됩니다 따라서 이 의사난수의 수열이 반복하기 전의 길이는 주기라고 불리고 이 주기는 최초 seed의 길이에 제한됩니다 만약 두 자리의 seed를 사용하면 알고리즘이 이 seed를 다시 사용하기 전에 최대 백 개의 숫자를 만들어낼 수 있습니다 그 후 이 수열은 반복됩니다 세 자리의 seed는 반복되기 전에 천 개의 숫자를 만들 수 있습니다 그리고 네 자리의 seed는 반복되기 전까지 만 개의 수를 만들수 있습니다 하지만 만약 어머하게 큰 seed를 사용한다면 이 수열의 주기는 반복되기 전까지 몇 조 개의 수가 있을 수 있습니다 하지만 이 두 가지 방법의 차이점은 중요합니다 의사난수의 수를 만들면 일어날 수 없는 수열이 생깁니다 예를 들어, 앨리스가 완전히 임의의 시프트 20개인 수열을 만든다면 이는 모든 경우의 시프트 수열 더미에서 일정하게 고르는 것과 같습니다 이는 모든 경우의 시프트 수열 더미에서 일정하게 고르는 것과 같습니다 이 더미는 26의 20제곱의 페이지가 있고 어마어마한 크기를 갖게되죠 만약 바닥에서 위를 향해 빛을 비추면 더미 위에 있는 사람은 이 빛을 2억년동안 못 볼 정도로 큽니다 이것을 앨리스가 4자리 무작위의 seed를 사용한 의사난수의 수열을 만들 때와 비교해 봅시다 의사난수의 수열을 만들 때와 비교해 봅시다 이것은 만 개의 seed중에 고를 수 있는 것이라서 앨리스는 오직 만 개의 서로다른 수열을 만들 수 있습니다 이것은 모든 가능한 수열 중에 아주 적은 부분을 차지합니다 무작위로 정하는 것에서 의사난수를 이용한 시프트로 바꾸면 키 공간을 매우 작은 seed공간으로 축소시키는 것입니다 그래서 의사난수의 수열을 무작위의 수열과 구별 못하게 만드려면 컴퓨터가 모든 seed를 보고 같은 수열을 찾는 것이 비현실적이어야 합니다 이는 컴퓨터 과학에서 가능한 것과 합리적인 시간 안에 가능한 것을 구분 하는 이유입니다 우리가 자전거 자물쇠를 살 때 같은 논리를 씁니다 우리는 누구나 모든 수의 조합을 자물쇠가 열릴 때까지 시도해 볼 수 있다는 것을 압니다 하지만 이는 며칠이 걸릴 것입니다 그래서 8시간 동안은 안전하다고 볼 수 있죠 의사난수를 만들 떄 seed의 길이가 늘어남에 따라 보안성도 높아집니다 만약 세상에서 가장 빠른 컴퓨터가 모든 seed를 시행하기 위해 몇 백년이 필요한다면 완전히 안전하다고 하기보단 현실적으로 안전하다고 할 수 있습니다 컴퓨터들이 빨라지면 seed의 길이도 이에 따라 길어져야 합니다 의사난수성은 앨리스와 밥이 미리 무작위 수열 전체를 공유하지 않아도 되게 해줍니다 대신, 그들은 비교적 짧은 seed를 공유한뒤 똑같이 확산 시켜서 필요할 때 같은 무작위의 수열을 얻을 수 있습니다 그런데 만약 이 seed를 공유하기 위해 만날 수 없게 되면 어떻게 될까요?