암호론 논문 리딩 #1: Blum-Blum-Shub PRNG (1)

논문 내용을 그대로 옮기는게 아니라, 내 생각/이해가 꽤 섞여있으니 참고. 틀린 점 있으면 지적 환영 :)

"A Simple Unpredictable Pseudo-Random Number Generator" - Blum, Blum, Shub

1. Introduction

PRNG는 seed라고 하는 일종의 초기값을 주었을 때, 빠른 방식으로 랜덤해보이는 비트 수열 하나를 생성하는 방법이다. 

여기서 중요한 단어는 "랜덤해보이는"인데, 이게 참 애매한 단어다. 결정론적인 알고리즘을 통해서 랜덤해보이는 수열을 생성한다는 것 자체가 꽤 신기한 접근이다. 하지만 암호론에서 우리는 공격자가 PRNG와 진짜 랜덤한 수열을 구분하지 못하기를 원하면서 PRNG를 활용한다. 그러니 우리는 PRNG의 "랜덤해보이는" 점을 실제로 확인할 여러 통계적 방법을 (Frequency Test/Serial Test/Poker-k Test/Run Test) 쓴다. 하지만 이 방법들은 naive한 방법이라는 생각이 든다.

그래서 여기서 새로운 접근을 하는데, 어떤 PRNG로 제작한 길이 $L$ 비트 수열을 보고, 다음 $L+1$번째 비트를 예측하는 것이 얼마나 어려운지를 따지는 것이다. 우리의 궁극적인 목표는, 다항식 시간에 $\frac{1}{2}$ 초과의 확률로 $L+1$번째 비트를 예측하지 못하도록 하는 것이다. 즉, 다항식 시간으로 뭘 해봤자, 그냥 동전 던지는 수준을 벗어나지 못하도록 하자는 것이다. 비슷하게, $L$ 비트 수열을 보고, 그 전에 어떤 수열이 나왔는지 복원이 불가능하도록 한다. "CSPRNG"를 참고하자.

엄밀하게 이야기를 하려면, (확률적) 튜링 기계 이야기가 나와야 하는 것 같다. 이 부분은 잘 모르므로 생략한다.

이 논문에서는 $1/P$ generator와 $x^2 \pmod N$ generator를 소개하는데, 두 번째 방식이 굉장히 좋다고 소개한다.

첫 번째 방식으로는 완전히 예측가능한 비트 수열이 제작되고, 비트 수열 일부분으로 수열 전체를 효율적으로 복원할 수 있다.

두 번째 방식은 우리가 원하는 안전성을 보장한다. 단, 몇 가지 정수론적 가정이 필요하다고 한다. 이는 뒤에서 서술한다.

두 방식 모두 써먹을 곳이 있다고 하는데, 우리가 원하는 암호론에 써먹을 수 있는 것은 $x^2 \pmod N$ generator다.

2. Notations & Definitions

일단 최대한 논문의 notation을 활용한다. 자연수 $N$에 대하여 $|N|_b = \lfloor 1 + \log_b N \rfloor$를 $N$의 $b$진법 전개 길이라고 하고, $|N| = |N|_2$라 하자. 또한, $\Sigma = \{ 0, 1, \cdots b-1 \}$에 대하여 $\Sigma^*$를 $\Sigma$의 원소로 이루어진 유한 수열의 집합, $\Sigma^\infty$를 $\Sigma$의 원소로 이루어진 무한 수열의 (한 방향으로) 집합이라 하자.

$x \in \Sigma^*$에 대하여 $|x|$는 $x$의 길이이고, $\Sigma^k$는 길이 $k$인 $\Sigma^*$의 수열의 집합이다.

$x \in \Sigma^\infty$에 대해 $x^k$는 $x$의 첫 $k$개 원소로 이루어진 부분 수열이고, $x_k$는 $x$의 $k$번째 원소다. 0-index 활용.

$\mathbb{N}$은 양의 정수로 이루어진 parameter 집합이다. 이제 각 $N \in \mathbb{N}$에 대하여, $X_N \subset \{0, 1\}^n$을 seed의 집합이라 하자.

여기서 $n = |N|$이다. 이제 $X = \{(N, x) : N \in \mathbb{N}, x \in X_N\}$을 seed domain이라 하자.

여기서 우리는 $X$를 $X_N$들의 disjoint union으로 생각할 수 있다. 앞으로도 계속 써먹을 접근법이다.

특히, $X^n = \{(N, x) : N \in \mathbb{N}, |N| = n , x \in X_N\}$을 길이 $n$인 seed의 집합이라 하자.

충분히 큰 자연수 $n$에 대하여, $\mu_n$을 $X^n$ 위에서의 확률분포라고 하자. 이제 $U = \{ \mu_n \}$이 $X$ 위에서의 accessible 확률분포라는 것은, 충분히 큰 자연수 $n$을 입력으로 받고, $X^n$의 원소 중 하나를 $n$에 대한 다항식 시간에 $\mu_n$과 비슷한 확률분포로 뽑아내는 확률적 알고리즘이 존재한다는 것이다. 

여기서 "비슷한"의 정의를 엄밀하게 해야겠다. 알고리즘이 실제로 $X^n$의 원소를 뽑아내는 확률분포를 $\mu'_n$이라 하면, 임의의 $t > 0$을 고정했을 때 충분히 큰 $n$에 대하여 $\sum_{(N,x) \in X^n} | \mu_n ( N, x) - \mu'_n (N, x) | < \frac{1}{n^t}$가 성립해야 한다. 컴퓨터가 확률적으로 할 수 있는 일은 fair coin toss 뿐이라고 가정한다.

이제 $X$가 seed domain이고 $U$가 $X$ 위의 accessible 확률분포라면, $(X, U)$를 seed space라고 한다.

때에 따라서, $U$를 생략하고 그냥 $X$를 seed space라고 부를 수 있다.

이제 본격적으로 PRNG를 수학적으로 정의할 수 있다. $\Sigma = \{0 ,1, \cdots , b-1\}$이라 하자. 

$b$진법 pseudo-random sequence generator $G$를 정의하려면, seed space $X$가 우선 필요하다.

$G$는 $X$의 원소 하나를 $\Sigma^\infty$로 보내는 함수이다. 그런데 효율적으로 수열을 생성하는 것이 목적이니, 조건을 하나 추가한다. 각 정수 $s \ge 0$에 대하여, 적당한 정수 $t \ge 0$이 있어 $\mu_n (N, x) \neq 0$을 만족하는 모든 $(N, x)$에 대하여 $G(N, x)$의 첫 $n^s$개의 원소가 $\mathcal{O}(n^t)$ 시간에 계산될 수 있어야 한다. 

이제 $G(N, x)$를 seed $(N, x)$로 $G$에 의해 생성된 pseudo-random sequence라고 정의한다. 

seed space $X$ 위에서의 transformation $T$란, 다항식 시간에 계산될 수 있는 함수 $T : X \rightarrow X$다. 

단, 충분히 큰 $n$에 대하여 $T(X^n) \subset X^n$이어야 하고, $T$는 확률분포 $\mu_n$을 보존해야 한다. 

즉, 각 $A \subset X^n$에 대하여 $\mu_n (A) = \mu_n (T^{-1}(A))$가 성립해야 한다. 

이제 각 seed $x \in X^n$에 대하여, $x, Tx, T^2 x, \cdots$를 $x$의 orbit (under $T$)라 하자.

때에 따라서, $x_0 = x$, $x_k = T^k x$를 정의하기도 한다. 이 경우 $x_{k+1} = T(x_k)$가 성립한다.

seed space $X$를 states $\Sigma$로 보내는 다항식 시간에 계산될 수 있는 함수 $B$를 partition이라 한다.

이제 $\langle X, T, B \rangle$로 구성된 시스템을 하나 생각해보자. 여기서 $X$는 seed space, $T$는 transformation, $B$는 partition이다. 

그러면 단순하게 $G(N,x)$의 $k$번째 원소를 $B(T^k x)$로 정의하여, pseudo-random sequence generator를 얻을 수 있을 것이다.

여기서 생각할 수 있는 것은, 만약 $T^{-1}$이 잘 정의되고 계산 가능하다면, 뒤쪽으로 수열을 생성하여 "양쪽으로 무한한" 수열을 만들 수 있다는 것이다. 

마지막으로, 앞으로 자연수들을 비트 수열로 간주하고 (natural identification) 이를 다룰 것이다. 

또한, $Z_n^{*}$를 $n$과 서로소인 $n$ 미만 자연수들로 이루어진 multiplicative group이라 하자. 

 

3. The $1/P$ generator

$b$진법 $1/P$ generator를 정의해보자. 이를 위해서는 parameter 집합, seed domain, accessible한 확률분포, 그리고 $G$가 필요하다.

parameter 집합은 $\mathbb{N} = \{ P : P \in \mathbb{N}, P > 1 , \operatorname{gcd}(P, b) = 1 \}$이다. 

seed domain $X$는 각 $\mathbb{N}$에 속하는 각 $P$에 대해서 $Z_P^{*}$를 disjoint union한 것이다. (자연수를 비트 수열로 본다)

$X$는 $\{r/P : P \in \mathbb{N}, r \in Z_P^{*} \}$와 identify할 수 있다. 이는 $[0, 1)$ 위에서 dense한 집합이다.

이제 accessible한 확률분포를 정의하자. $\mu_n(P, r) = u_n(P) \cdot v_P(r)$로 정의한다.

여기서 $u_n$은 $|P| = n$인 $P$에 대한 uniform distribution이다. $v_P$ 역시 $Z_P^{*}$ 위의 uniform distribution이다.

유한집합에서 하나의 원소를 uniform random하게 고르는 것은 어렵지 않으므로, $U = \{\mu_n\}$은 accessible하다.

이제 $G$를 정의하자. $G : X \rightarrow \Sigma^\infty$를 하나 만들어야 한다.

$X = (P, r)$이라 할 때, $G((P, r))$은 $r/P$를 $b$진법 전개한 수열이다. 이를 생성하는 것은 당연히 어렵지 않다.

그러니 $G$는 우리가 원하는 조건을 잘 만족하는 PRNG가 되겠다. 

무언가 많고 복잡하게 썼지만, 결국 우리는 분모가 $b$와 서로소인 $0$과 $1$ 사이의 분수를 하나 적당하게 잡은 다음, 이를 $b$진법 전개하겠다는 것이다. 

나쁘지 않은 접근이다. 이제 이 PRNG를 state와 transformation의 언어로도 서술할 수 있다.

여기서 $T$는 $X$에서 $X$로 가는 함수로, (여기서 $X$를 $[0, 1)$의 부분집합으로 identify) $T(x) = bx \pmod {1}$이 되겠다.

이제 partition $B$는 $B(x) = \lfloor bx \rfloor$로 생각할 수 있음 역시 자명하다. 

결국 $T, B$는 우리가 생각하는 일반적인 $b$진법 전개 알고리즘을 그대로 보여주는 것들이다. 

4. The generator $x^2 \pmod N$

비트 수열을 생성하는 $x^2 \pmod N$ generator를 정의해보자. 위에서 논의한 것처럼, 필요한 구조들을 하나씩 살펴보자.

parameter 집합은 서로 다르고, 같은 길이를 갖는 $3 \pmod {4}$ 형태의 소수 $P, Q$의 곱으로 나타낼 수 있는 모든 자연수다.

즉, $N = PQ$, $P, Q$는 소수, $|P| = |Q|$, $P \neq Q$, $P \equiv Q \equiv 3 \pmod {4}$인 $N$의 집합이다.

또한, seed domain $X$는 각 $\mathbb{N}$에 속하는 각 $N$에 대하여 $\pmod{N}$의 이차잉여의 집합을 disjoint union한 것이다.

이제 확률분포를 정의해야 한다. $\mu_n (N, x) = u_n(N) \cdot v_N(x)$라고 하자.

여기서 $u_n$은 $|N|=n$인 $N$에 대한 uniform distribution이고, $v_N$은 $\pmod{N}$의 이차잉여의 집합에 대한 uniform distribution이다.

이 확률분포 역시 accessible 하다. $|N|$의 길이를 고정한 상태에서 $N$ 하나를 uniform하게 뽑아보자.

$P, Q$의 길이가 자동으로 결정되니, $P, Q$를 uniform 랜덤하게 뽑은 다음 조건을 만족하는지 검토하는 것을 반복하면 된다.

여기서 가장 어려운 부분은 $P, Q$의 소수 여부를 결정하는 것과, $PQ$의 길이가 원하는 $|N|$과 같은지 검증하는 것이다.

소수 판별은 다항식 시간에 가능함을 안다. (리만 가설을 가정하면 Miller-Rabin으로도 되고, 지금은 리만 가설 없이도 안다)

$PQ$의 길이를 판별하는 것은 그냥 곱셈을 때리면 되니까 하면 된다. 

또한, $4k+3$꼴 소수의 개수가 충분히 많으니, 랜덤하게 $P, Q$를 뽑아도 다항식 횟수번 이를 반복하면 $P, Q$가 소수인 경우가 나온다. 

$4k+3$꼴 소수의 개수가 충분히 많음을 보이는 것은 Prime Number Theorem의 확장으로 가능하겠다.

$N$을 아는 상태에서 이차잉여 하나를 uniform하게 뽑아보자. 마찬가지로 랜덤한 값 하나를 뽑은 다음 이차잉여인지 판별하면 된다.

이차잉여의 개수는 당연히 충분히 많으니, 판별만 다항식 시간에 하면 된다. 오일러 판정 + 중국인의 나머지 정리로 쉽다.

여기서 $N$을 우리가 만드는 과정에서 $P, Q$를 이미 알고 있다는 점을 이용하였다. 제대로 이해한 건지 잘 모르겠다.

이제 transformation을 정의하자. $X$의 원소 $(N, x)$가 있다면, 이를 $(N, x^2 \pmod N)$으로 보내자.

즉, $N, x$를 seed로 받은 뒤 $N$을 고정하고, $x$를 $x^2 \pmod {N}$으로 계속 바꾸겠다는 것이다.

또한, partition $B$는 $X$의 원소 $(N, x)$가 있을 때, $B((N, x)) = x \pmod 2$로 정의하자.

$T, B$가 다항식 시간에 계산되는 값들임은 자명하다. 그러니 우리는 $(N, x)$를 seed로 하는 PRNG를 하나 만들었다.

5. The assumptions.

우리가 고안한 PRNG들의 성질을 확인하려면, 여러 정수론적 문제들의 난이도에 대한 가정이 필요하다.

Discrete Logarithm Problem과, Quadratic Residuosity Problem이 모두 풀기 어렵다는 가정이다.

DLP는 소수 $P$와 그의 원시근 $b$와 $x \in Z_P^*$가 있을 때, $b^y \equiv x \pmod{P}$인 $y$를 찾는 문제이다.

DLP가 어렵다는 것은, 직관적으로 말하면 모든 input에 대해서 다항식 시간에 DLP를 해결하는 확률적 알고리즘이 없다는 것이다.

논문의 용어를 그대로 가져오면, "any procedure for solving the DLP will be inefficient for a fraction of the input"이다.

엄밀한 정의가 논문에 있는데, 이는 필요할 때 뒤에서 후술하는 것으로 한다. (예쁘게 서술하는 방법을 모르겠다)

QRP는 서로 다른 두 홀수 소수의 곱 $N$이 있을 때, $x$가 주어졌을 때 $x$가 $\pmod N$으로 이차잉여인지 판별하는 문제다.

QRP가 어렵다는 것은, 다항식 시간의 확률적 알고리즘으로 이를 풀 경우 틀릴 확률이 있다는 것이다.

결론적으로는, 다항식 시간의 확률적 알고리즘은 단순히 동전을 던져서 "찍는" 것과 큰 차이가 없게 될 것이다.

논문의 용어를 그대로 가져오면, "any efficient procedure for guessing QRP will be incorrect for a fraction of the input"이다.

비슷하게, 엄밀한 정의가 논문에 있는데, 이는 필요할 때 뒤에서 후술하는 것으로 한다. (예쁘게 서술하는 방법을 모르겠다)

6. The $1/P$ generator is predictable.

먼저 정의 몇 가지를 추가적으로 하고 진행하자. 

$P, b$는 서로소인 $2$ 이상 자연수이고, $r_0$는 $0 < r_0 < P$를 만족하는 자연수이다.

$r_0 / P = 0.q_1q_2q_3 \cdots $라 쓰자. 이는 $b$진법 전개이다. 자명하게 $q_i$들은 주기를 갖는다.

또한, $r_m = b^m r_0 \pmod P$라고 정의하자. 즉, $r_m / P = 0.q_{m+1}q_{m+2} \cdots$가 된다.

$P, b$가 임의의 자연수일 때, generalized de Bruijn sequence of period $P-1$, base $b$란 주기 $P-1$을 갖는 수열 $q_1q_2 \cdots$로, (단, $0 \le q_i < b$) $|P|_b-1$ 길이의 임의의 $b$-ary 문자열이 이 수열에 등장하고, $|P|_b$ 길이의 임의의 $b$-ary 문자열이 이 수열의 주기에 최대 한 번 등장하는 것이다.

이제 본격적으로 $1/P$ generator를 분석해보자. 

Theorem 1. $P$는 소수고 $b \in \{1, 2, \cdots P-1\}$은 $P$의 원시근이다. $r_0 \in \{1, 2, \cdots P-1\}$을 잡자.

이제 $1/P$ generator로 $r_0/P$를 seed로 하여 만든 수열은 de Bruijn sequence of period $P-1$, base $b$가 된다.

증명 (Sketch): 우선 $r_m$이 $P-1$을 주기로 가짐은 $b$가 원시근임에서 자명하다.

그러니 $q_i$들 역시 정확히 $P-1$을 주기로 가짐을 쉽게 보일 수 있으며, 주기성에 대한 논의는 끝난다.

이제 $b$-ary 문자열 $a_1 a_2 \cdots a_s$가 주어진 수열에 존재할 필요충분조건을 생각해보자.

이건 결국 $1 \le k \le P-1$인 $k$에 대하여, $k/P$의 $b$진법 전개의 첫 $s$개의 문자가 $a_1a_2 \cdots a_s$인 것과 같다.

그러니 부등식으로 문제에 접근할 수 있다. 나머지는 아주 간단한 식 전개와 부등식이다. 증명 끝.

이 정리의 결론을 생각해보자. 결국 시드에 관계없이, 임의의 $|P|_b-1$ 길이의 $b$-ary 문자열은 생성된 수열에 존재한다.

그러니 generator로 생성된 $|P|_b-1$ 길이의 부분수열을 확보했더라도, $P$를 실제로 복원하는 것은 불가능하다.

$P$가 충분히 크기만 하면, generator로 만든 수열이 확보한 수열을 무조건 포함할 것이기 때문이다.  

Theorem 2. $P, b$는 $2$ 이상의 서로소인 자연수고, $r_0$는 $0<r_0 < P$를 만족한다. 

여기서 $P$는 소수일 필요가 없다. 이때, 다음 문제들은 전부 $|P|_b$에 대한 다항식 시간에 해결할 수 있다.

문제 1 : 다항식 $f$를 하나 고정한다. $P, b, r_m$과 $1 \le k \le f(|P|_b)$를 하나 입력받는다.

이때, $r_{m-1}$, $r_{m+k}$, $q_m q_{m+1} \cdots q_{m+k}$를 전부 출력한다.

문제 2 : $P, b$와 $q_{m+1} q_{m+2} \cdots q_{m+|P|_b}$를 입력받는다.

이때, $r_m$을 출력한다. (문제 1을 활용하면, 여기서 $q_m$과 $q_{m+|P|_b+1}$도 얻을 수 있다.)

문제 3 : $P$가 $1, 2, \cdots , b$와 전부 서로소라고 가정한다. $b, r_m ,r_{m+1}$을 입력받되, $r_{m+1} \neq r_m \cdot b$다. 

이때, $P$를 출력한다. (문제 1을 활용하면, $q_m q_{m+1} \cdots q_{m+|P|_b}$ 역시 얻을 수 있다.)

문제 4 : $r_0$가 $P$와 서로소라고 가정하자. $b, q_{m+1}q_{m+2} \cdots q_{m+k}$를 입력받는다. (단, $k = \lceil \log_b (2P^2) \rceil$)

이때, $P$와 $r_m$을 출력한다. (앞선 문제들을 활용하면, $q_m$과 $q_{m+k+1}$ 역시 쉽게 얻을 수 있다.)

증명 (Sketch): 문제 1, 2, 3, 4를 차근차근 해결해보자.

문제 1: $r_{m-1} \equiv b^{-1} r_m \pmod {P}$, $r_{m+k} \equiv b^k r_m \pmod {P}$다.

또한, $r_{m-1}$을 활용하여 $q_m q_{m+1} \cdots q_{m+k}$를 얻는 것은 단순 $b$진법 전개로 할 수 있다.

문제 2: $r_m/P = 0.q_{m+1}q_{m+2} \cdots q_{m+|P_b|} + 0.00 \cdots 0 q_{m+|P_b|+1}q_{m+|P_b|+2} \cdots$다.

그러니 $r_m = P \cdot (q_{m+1}q_{m+2} \cdots q_{m+|P_b|})/b^{|P_b|} + r_{m+|P_b|} / b^{|P|_b}$가 된다.

$0 < r_{m+|P_b|} < P < b^{|P|_b}$이므로, 뒤의 값은 $0$과 $1$ 사이의 값이다. 그러니 앞의 값에 ceil을 취하면 된다.

문제 3: 이제부터 $P$를 모르고 시작한다. $P$를 찾는 방법을 고안해보자.

일단 여기서는 $r_{m+1} - r_m b$가 $0$이 아닌 $P$의 배수이므로, 여기서 단서를 얻을 수 있겠다.

즉, $P$는 $\frac{r_mb-r_{m+1}}{1}$, $\frac{r_m b - r_{m+1}}{2}$, $\cdots$, $\frac{r_m b - r_{m+1}}{b-1}$ 중 하나다. (부등식 입장에서 보면 자명한 사실이다)  

저 수열에서 $1, 2, \cdots b$ 전부와 서로소인 값은 유일함을 쉽게 증명할 수 있고, 그러니 그 값이 $P$가 된다.

$b$에 대한 다항식 시간으로 모든 연산을 할 수 있는데, 여기서 암묵적으로 $b$가 작은 값임을 가정한 것 같다 (확인 필요)

리만 가설을 가정하면 minimum primitive root가 $|P|$의 다항식에 의해 bound 된다고 하니, 괜찮은 것 같다. (확인 필요)

문제 4: $r_m/P = (q_{m+1}q_{m+2} \cdots q_{m+k})/b^k + \epsilon$가 (단, $0 \le \epsilon < 1/b^k$) 성립한다.

그런데 $\epsilon < 1/b^k \le 1/(2P^2) $이므로, $r_m/P$는 $(q_{m+1}q_{m+2} \cdots q_{m+k})/b^k$의 상당히 좋은 rational approximation이 된다. 

실제로, $r_m/P$는 $(q_{m+1}q_{m+2} \cdots q_{m+k})/b^k$의 convergent가 됨을 어렵지 않게 보일 수 있다.  

특히, $(q_{m+1}q_{m+2} \cdots q_{m+k})/b^k$의 convergent 중 $b$진법 전개를 했을 때 처음으로 $q_{m+1}q_{m+2} \cdots q_{m+k}$가 순서대로 등장하는 것이 $r_m/P$가 됨 역시 어렵지 않게 증명할 수 있다. convergent 전개를 할 때 분자/분모는 지수적 속도로 증가하므로, 이 모든 과정은 다항식 시간에 끝난다.

즉, $b$와 길이 $\lceil \log_b (2P^2) \rceil \le 2|P|_b+1$의 부분수열을 확보하면, 다항식 시간에 전/후 수열을 계산할 수 있다.

솔직히 $b$를 아는 것은 수열을 보면 모든 원소가 정확히 $\{0 ,1, \cdots b-1\}$에서 나오니, 어렵지 않을 것이다. 

그러니 길이 $2|P|_b+1$의 부분수열만 확보하면, 이 generator의 모든 것을 파악하고 예측할 수 있다. 약하다.