PRNG, 제대로 이해하기

 

***************** INDEX *****************

 

🎲 Random Number

🎫 Randomness

⚛️ Entropy

🔗 RNG

🎟 PRNG

 

********************************************

---

Random Number ?

난수는 예측 불가능성을 만족하기 위해 무작위하게 생성되는 값을 말합니다.

이름에서 알 수 있듯이 정말 랜덤한 값을 뜻하죠.

 

암호학에서 난수는 굉장히 중요한 요소입니다. 

아래와 같은 상황에서 사용하곤 합니다.

 

1. 대칭키 자체, 공개키 암호에서의 개인키

2. 블록암호 운용모드 - 초기화 벡터(IV), 카운터(CTR) 생성

3. 패스워드 기반 암호 - 솔트(Salt) 생성

 

 

그런데, 사용되는 난수들은 정말 랜덤할까요? 

 

아주 예전에 C언어를 배울 때 난수를 처음 알게 되었는데,

그 때 교수님께서 진짜 랜덤은 아니지만 비슷하게 만든 값이라고 소개해주셨던 것이 생각납니다.

그 때는 그 설명이 뭔가했는데, 이번에 암호학을 배우면서 제대로 알 수 있게 되었어요.

 

이 글을 읽는 분들도 궁금증이 해결되었으면 좋겠네요 🙌🏻

 

 

 

난수의 성질

무작위성 Randomness : 통계적인 편중이 없이 수열이 무작위로 되어 있는 성질로 '아무렇게' 처럼 보이는 성질.

예측 불가능성 Unpredictability : 과거의 의사난수열로부터 다음 생성될 수를 예측할 수 없는 성질.

재현 불가능성 Reconstruction is impossible : 같은 수열을 재현할 수 없다는 성질

 

이 글의 카테고리는 암호학입니다.

암호학의 시각으로 난수를 다시 한 번 파악해봅시다.

 

암호학에서 사용할 수 있는 난수의 조건을 따져야 합니다.

각 성질을 충족하는지에 따라 난수를 약한 의사난수/강한 의사난수/진성난수로 구별합니다.

 

 

✔️ 무작위성 randomness

통계적인 성질을 조사했을 때, 치우침이 없으면 무작위하다고 판단합니다.

난수가 무작위성만 가진다면 안전할까요?  ❌ 무작위하다고만 해서 예측할 수 없다는 건 불충분합니다. 

무작위성만 가지는 난수 👉🏻 약한 의사난수 (Pseudo Random)

 

✔️ 예측 불가능성 Unpredictability

공격자가 모든 의사난수열을 얻는다고 할지라도 다음에 출력될 난수를 예측할 수 없어야 합니다.

아래에서 언급하겠지만, 의사난수 생성기(PRNG)의 Seed 또한 강한 의사난수입니다.

일반적으로 PRNG에서 사용되는 알고리즘 자체는 공격자가 알고 있기 때문에

의사난수를 생성하기 위한 초기값이 되는 값(seed)는 알려져서는 안됩니다(예측 불가능해야 함). 

 

예측 불가능성을 가지는 난수 👉🏻강한 의사난수(Pseudo Random)

강한 의사난수는 당연히 무작위성을 가집니다.

강한 의사난수를 가질 때부터 암호 기술에 사용할 수 있습니다.

그래서 암호 시스템에 사용되기 위해서는 적어도 예측 불가능성을 가져야합니다.

 

✔️ 재현 불가능성 Reconstruction is impossible

진정한 난수를 이루는 조건이 아닌가 싶은데요.
재현 불가능성을 가지는 난수 👉🏻진성 난수 (True Random)

 

하지만, 컴퓨터의 특성상 규칙적으로 동일한 매커니즘을 갖기 때문에 한계가 있습니다.

그래서 재현불가능한 물리현상으로부터 정보를 얻을 수 있습니다.

예를 들어 당일의 온도나 습도, 소리의 변화 등, 사용자의 마우스 커서의 움직임, 키 스트록의 입력 변화 값 등이 있죠.

혹은 방사선 관측기의 출력도 있습니다.

이 부분은 RNG를 알아볼 때 다시 언급될 것입니다.

 

 

 

 

Randomness ?

암호학에서 아주 중요한 역할이죠. 

아무렇게나 보이는 성질입니다.

 

무작위성의 확률분포

아래의 엔트로피를 설명하기 전에 확률분포에 대해 알아보도록 합시다.

무작위 과정 Randomized Process의 모든 가능한 결과는 확률분포로 특정지어 집니다.

절대 일어나지 않는 다는 의미인 0부터 반드시 일어난다는 1까지의 숫자로 표시됩니다.

 

확률분포는 모든 다능한 결과를 포함해야하며,반드시 모든 확률의 합이 1이어야 합니다.

확률분포는 균등분포와 비균등분포가 있습니다.

 

균등분포 uniform distribution: 모든 확률이 같은 확률분포.

비균등분포 non-uniform distribution: 모든 확률이 동일하지 않은 분포.

 

 

 

Entropy

엔트로피는 아주 유명한 개념이죠.

바로 불확실성의 측도, 즉 시스템에 존재하는 무질서의 측도(Measure)입니다.

즉 '얼마나 무작위한가? 얼마나 불확실한가'를 수치로 표시한 것입니다.

난수의 무작위성을 수치로 표현할 수 있겠죠.

 

 

확률분포의 엔트로피

확률분포를 통해 이 엔트로피를 계산할 수 있습니다.

표본 공간이 n개인 확률 분포에서의 엔트로피는 아래의 수식을 통해 구할 수 있습니다. 

 

 

수식에 대한 감을 잡기 위해 균등분포를 이루는 무작위 128-bit 키의 엔트로피를 같이 구해보도록 합시다.

 

하나의 128-bit키를 이루는 확률은 $\frac{1}{2^{128}}$이므로,

$-(\frac{1}{2^{128}}\times\log(\frac{1}{2^{128}}))\times2^{128}$ 으로 식을 세울 수 있습니다. 

 

따라서, 128이 나오게 되죠.

 

 

분포에 따른 엔트로피의 특징은 분포가 균등하지 않을수록 엔트로피가 낮아지고, 무작위성이 작아진다는 것입니다.

즉, 어떤 확률으로 편향되어 있으면 엔트로피는 낮아집니다.

 

 

RNG

RNG는 Random Number Generator로, 난수 생성기를 의미합니다.

그렇다면, 난수는 어떻게 생성할 수 있을까요?

 

난수를 만드는 경우에 대해 위에서 한 번 언급했는데요.

다시 정리하자면 다음과 같습니다.

 

✔️ 아날로그 정보를 사용하여 엔트로피를 수집

ex. 온도, 습도, 소리 등의 데이터

하지만 측정이 어려울 때가 많습니다.

 

✔️ 사용자의 활동을 통한 엔트로피 수집

커서의 움직임, 키보드 키 스트록 시퀀스, 네트워크나 디스크 활동

하지만 공격자로 부터의 조작과 악용에 취약하다는 점이 있습니다.

 

✔️ 양자 난수 발생기

이론적으로 True Random을 얻을 수 있지만, 빠르게 산출하지 못하는 기술적 어려움이 있습니다.

 

 

그래서 고안된 것이 짧은 진성 난수열을 통해 긴 난수열을 생성하는 방법입니다.

이것이 바로 의사난수발생기 Pseudo Random Number Generator입니다.

 

참고로, 난수 발생기는 그림과 같이 존재합니다.

 

 

 

미리 참고로 말씀드리자면,

TRNG (진성난수발생기)를 통해 PRNG (의사난수발생기)의 Seed값을 생성합니다.

 

 

 

PRNG

PRNG는 Pseudo Random Number Generator의 약자로, 의사 난수 발생기라고 합니다.

 

단어에서 느낄 수 있듯이 가짜? 모방된? 난수를 생성합니다.

완전한 Random은 아니지만, Random을 따라한 거죠. 

그래서 한자로 의사라고 붙인 것 같아요.

 

의사(疑似: 비교할 의, 비슷할 사 | Pseudo: 가짜의- )

 

 

 

PRNG 구성

 

의사 난수 발생기를 도식화한 그림입니다.

짧은 진성난수인 Seed를 초기값으로 긴 의사난수열을 생성합니다.

 

✔️ Seed

내부상태를 초기화하기 위해 사용되는 진성 난수 (Random한 비트열) 이며,

외부에 알려져서는 안되며 예측가능하면 안되는 비밀 값입니다.

 

✔️ 내부 상태

PRNG가 관리하고 있는 메모리 값을 뜻합니다.

이 값을 기초로 암호화하여 의사 난수를 도출시킵니다.

이 값을 통해 의사난수가 발생하기 때문에 마찬가지로

외부에 알려져서는 안되며 예측가능해서는 안됩니다.

 

 

 

 

조금 더 자세히 보면 아래의 그림과 같습니다.

 

Seed를 통해 내부 상태를 초기화하고 해시함수를 통해 의사 난수열을 생성합니다. 

다음 의사난수열을 생성하기 위해 Seed 값을 1 증가시키고 내부상태를 업데이트합니다.

업데이트된 내부상태를 통해 해시함수를 통해 다음 의사 난수열을 생성합니다.

 

 

일방향 해시 함수를 통해 예측 불가능성을 보장하고,

새로운 값을 도출시키위해 1을 증가하여 내부 상태를 업데이트 합니다.

 

이때, 해시함수를 거친 난수를 내부상태로 업데이트할 수 있을까요?

정답은 안됩니다. 왜일지 한 번 과정을 그려보세요!

 

 

 

ANSI X9.17

암호를 사용한 PRNG의 구체적인 방식입니다.

실제로 많은 곳에서 사용되고 있다고 해서 마지막으로 확인하고 포스팅을 마치도록 하겠습니다.

 

 

실제로 사용하는 PRNG는 위와 같습니다.

그림을 정리해볼게요!

 

1.  Seed의 일부분을 내부상태를 초기화하고, 일부분을 암호화 키로 사용합니다.

2. 현재 시각을 통해 암호화 키를 암호화(A) 합니다.

3. 초기화된 내부상태와 A를 XOR연산을 한 후 암호화 키와 함께 암호화(B)합니다. 

4. B를 의사난수로 사용합니다. (그림에서 내부상태 초기값으로 명시되어 있는데, 의사난수 열입니다.)

5. B의 값을 A와 XOR한 후, 암호화 키를 이용해 암호화(C)합니다.

6. C를 내부상태 값으로 Update합니다.

 

 

그런데, 이 알고리즘을 사용하면 정말 안전할까요?

공격자는 발생기의 알고리즘을 알고 있고, 현재시각을 알 수 있습니다.

하지만 비밀값인 Seed를 통해 생성한 암호화키와 내부 상태 초기값을 알 수 없기 때문에

이 알고리즘은 내부 상태 값과 의사난수 값을 예측할 수 없기 때문에 안전하다고 할 수 있습니다.

 

 

 

그럼 여기까지 PRNG에 대해 알아보았습니다.

마지막으로 가장 중요한 점은 PRNG 알고리즘이라고 해서 검색으로 나오는 것을 무작위로 사용해서는 안됩니다.

 

난수를 사용하는 곳은 암호화도 있지만, 다양한 곳에서 난수를 사용하기 때문에

보안을 생각하지 않은 알고리즘도 있기 때문입니다.

 

보안을 위한 PRNG를 고려한다면 암호학적인 PRNG인지 한 번씩 확인해보시길 바랍니다!

 

 

 

 

피드백이나 수정 부분은 댓글로 남겨주시면 정말 감사하겠습니다 🙌🏻