rkm0959

This post attempts to (in a half-mathematical, half-intuitive way)

• briefly explain zero-knowledge proofs and their definitions
• show an example with Schnorr's protocol for proving knowledge of discrete log
• introduce the integer commitment scheme of Damgard and Fujisaki (2001)
• introduce diophantine sets, and diophantine proof of knowledge (2003)

I'm also attempting to write a demonstration for this paper. (with additional assumptions and simplifications) Here's the link.

1. Zero Knowledge Proofs

Here's a very well-written introduction for zero-knowledge proofs by Matthew Green. 

Zero-knowledge proofs are proofs that reveals nothing except for the assertion that the statement one is trying to prove is correct. For example, if I want to prove to a verifier that "I have this secret value $x$ satisfying some property", I want to do so without giving any extra information on $x$. At the same time, we want this proof to have the fundamentals of our intuition of a "proof" - that is, the verifier can be convinced of the proof if the statement is true, and the verifier can reject the proof if the statement is false.

To summarize, we want

• Completeness : If statement is true, the verifier properly following the protocol can verify the proof.
• Soundness : If statement is false, the verifier properly following the protocol can reject the proof with overwhelming probability.
• Zero-knowledge : If statement is true, the verifier learns nothing except for the fact that the statement is true.

We call people (prover, verifier) that are properly following a protocol to be honest.

We call people (prover, verifier) that are not properly following a protocol to be malicious.

For example, a malicious prover may want to forge a "proof" for a statement that is not true.

Also, a malicious verifier may want to extract some extra knowledge from the proof by not following the protocol precisely.

So we have this "learns nothing except for the fact that the statement is true" thing : how do we formalize it in mathematical terms?

The proofs we will deal in this writeup will be interactive proofs - proofs where the prover and verifier interact with each other to see whether the prover's claim is true of not. Also, the proof protocol will not be deterministic. Therefore the "proof script" - the complete interaction of the honest prover and verifier - will follow some distribution. If we simulate this proof protocol "precisely" by only using the statement that is being asserted, this will intuitively be a good definition of "zero-knowledge". Summarizing, we have two distributions : 

• The distribution of the actual "proof script" between the honest prover and the verifier
• The distribution of the simulated "proof script" designed by only using the statement that is being asserted

Now we can truly define what it is to be "zero-knowledge" - 

• Perfect Zero-Knowledge : No matter what verifier does, there's a simulated "proof script" that follows the exact same distribution with the actual "proof script" - so it is impossible to gather any extra knowledge, even with infinite computational resources
• Statistical Zero-Knowledge : The same as perfect zero-knowledge, but now the two distributions does not need to be the same - only "close". How do we determine if two distributions are close? Check out statistical distance. 
• Computational Zero-Knowledge : The same, but the two distributions are computationally hard to distinguish.
• Honest-Verifier Zero-Knowledge : We now add the assumption that the verifier is honest. 

• Prover generates a random $r \in [0, p)$ and sends $g^r$ to the verifier.
• Verifier issues a random challenge $c \in [0, p)$ and sends $c$ to the prover.
• Prover sends $z = (r + cx) \pmod{p}$ to the Verifier. 
• Verifier checks if $g^z = g^r y^c$ is true. If not, the proof is false.
• They repeat the process until the probability that a malicious prover got away with a fake proof is small as desired.

• Completeness : If prover does know $x$, we see that $g^z = g^{r+cx} = g^r y^c$ is indeed true, so the verifier accepts it.
• Soundness : Here's an intuitive explanation that can be outlined to a proof. If some prover can answer the verifier's challenge with a high probability, the prover should know the value of $(r + cx) \pmod{p}$ for many values of $c$. From these values, one can easily recover the value of $x$. Therefore, we have proved that the prover must actually know $x$ in order to answer the challenges well.
• Zero-Knowledge : The actual proof script is $(g^r, c, (r + cx) \pmod{p})$ for i.i.d. $r, c \in [0, p)$. This is equal to the distribution of $(g^z y^{-c}, c, z)$ for i.i.d. $c, z \in [0, p)$. Therefore, we can perfectly simulate the proof script only using $g, y$ and the statement $g^x = y$. 

This proves that the Schnorr's Protocol is honest-verifier perfect zero knowledge. 

If the challenge is selected in $[0, 1]$ (binary challenge) the protocol can be proved to be perfect zero-knowledge.

• It is hard to generate a collision pair - i.e. $m \neq m'$ such that $H(m) = H(m')$.
• It is hard to find a preimage - i.e. given $H(m)$, it is hard to recover $m$.
• A small change in the message $m$ leads to a huge change in the hash $H(m)$.

Now what we can do is announce to the world that you have made a prediction with hash $H(m)$. 

• Binding : Once you commit $m$, you cannot go back to another message $m'$.
• Hiding : No one can recover the value of $m$ from $H(m)$, so it hides the value of $m$.

Commitment schemes are of similar nature. Here, we will specifically look at integer commitment.

We want the cool properties of binding and hiding, and we want them to be defined clearly. Here's how we do it.

• Consider a deterministic commitment function $C$ that takes two integers as input.
• To commit an integer $x$, we generate a random integer $r$ and use $C(x, r)$ as our commitment value.
• The constraints on $x$ and the interval of $r$ to be selected from uniformly will be determined later.

• Binding : It is difficult to find $x, x', r, r'$ such that $x \neq x'$ and $C(x, r) = C(x', r')$.
• Hiding : For any $x, x'$, the distributions of $C(x, \cdot)$ and $C(x', \cdot)$ are equal/statistically close.

• Summation Protocol : If prover has three integers $a, b, c$ such that $a + b = c$ and their respective commitment $A, B, C$, they can prove that $a + b = c$ in a zero-knowledge way using only the commitment values $A, B, C$. 
• Multiplication Protocol : If prover has three integers $a, b, c$ such that $ab = c$ and their respective commitment $A, B, C$, they can prove that $ab = c$ in a zero-knowledge way using only the commitment values $A, B, C$. 

In other words, the prover can claim that "these commited values actually have this sum/product relation" in a zero-knowledge way.

It turns out that there is such a method, and it was devised by Damgard and Fujisaki in this paper. 

To make explaining things much easier, we will cover only a part of the results shown in the paper. To be exact,

• We will only cover a specific case of the originally much, much more general construction of the scheme.
• We will not discuss the details of the proof of why the schemes are valid, but discuss some intuition & insights.
• Some protocols outlined below are not from the paper - these are mostly my thoughts & guesses.
• We will only consider the honest-verifier case - the transformation from honest-verifier case to the general case is dealt in the paper.
• The paper for Diophantine Argument of Knowledge also deals with extensions of this scheme. We do not deal with them here.

Now we discuss the actual scheme by Damgard and Fujisaki. We first need to describe the setup process.

• Setup - Part 1. The verifier takes two distinct, large safe primes $P, Q$ and let $n = PQ$. From the definition of safe primes, we can write $P = 2p+1$, $Q = 2q+1$ with $p, q$ being a prime. The verifier then constructs an element $h \in \mathbb{Z}_n^{\times}$ such that $h$ has order $pq$. From now on, we will work in the cyclic group $\langle h \rangle \le \mathbb{Z}_n^{\times}$ for our commitments. 
• Setup - Part 2. Assume that $n$ is a $k$-bit modulus - then anyone who knows $n$ also knows that the cyclic group generated by $h$ has order less than $2^B$ for $B = k$. This is an important piece of information for statistical zero-knowledge.
• Setup - Part 3. The verifier generates $\alpha$ randomly from $[0, 2^{B+k})$, and sets $g = h^{\alpha}$. The verifier sends $n, g, h$ to the prover, and the verifier proves the knowledge of $\alpha$ such that $g = h^{\alpha}$ in a zero-knowledge way. This can be done with a binary challenge process similar to Schnorr's protocol. It's important to note that since factorizing $n$ is hard, the prover does not know the order of $h$.
• Note that the prover also knows the values of $B$ and $k$, since they can be easily derived from $n$.
• Setup - Part 4. We also need an additional parameter $C$ - an higher value of $C$ will result in lower error probability, but at the same time we need $C$ to satisfy one of our assumptions below. Because we are dealing with a specific case of a much general construction in the paper, setting $C$ as high as $pq$ is not an issue. For more insight on selecting $C$, it is recommended to refer to the original paper.

Now that we know what we are working with - integers modulo $n$ as commitment, we can outline some assumptions.

While there are actually more assumptions involved, using the safe prime construction only leaves us with two - 

• Strong Root Assumption : Basically, if one is given a random $y \in \langle h \rangle$, then it is hard to find $x \in \langle h \rangle$ and $t \ge 2$ such that $y = x^t$.
• Small Order Assumption : Basically, it is hard to find a $\sigma$ and $b \in \langle h \rangle$ such that $0 < \sigma < C$ and $b \neq 1$ and $b^\sigma = 1$. 

In the safe prime construction, we can just replace the two with the Strong RSA assumption, alongside with a suitable value of $C$.

Now we discuss how to commit integers. To commit an integer $x$, the prover selects some $r \in [0, 2^{B+k})$ and makes a commitment as $C(x, r) = g^x h^r$. It can be proved that this commitment scheme has the (statistical) hiding property and the binding property. 

Also, from now on, we assume that the integers being commited are in some finite interval $[-T, T]$. This is a required assumption for proofs to be zero-knowledge. Of course, a malicious prover can try to commit integers that are not in this interval - therefore, the verifier must also ask for a proof that the integer is indeed in this interval. The method for this "range proof" will be outlined in the next section.

Now we discuss the proofs between the prover and the verifier. There are many things we want to prove, these include

• Proving you know how to open : Assume the prover has some integer $x$ and its commitment $C$. The prover now wants to prove the knowledge of $x, r$ such that $C = C(x, r)$ - can it be done without leaking information on $x, r$?
• Summation Protocol : If prover has three integers $a, b, c$ such that $a + b = c$ and their respective commitment $A, B, C$, they can prove that $a + b = c$ in a zero-knowledge way using only the commitment values $A, B, C$. 
• Multiplication Protocol : If prover has three integers $a, b, c$ such that $ab = c$ and their respective commitment $A, B, C$, they can prove that $ab = c$ in a zero-knowledge way using only the commitment values $A, B, C$. 

Proving you know how to open

• Keynotes : We imitate Schnorr's protocol - but the range we choose our parameters from needs to be selected carefully.
• Step 0. Prover has some commitment $C = C(x, r)$ and would like to prove they know how to open.
• Step 1. Prover chooses some random $y \in [0, TC 2^k)$ and $s \in [C 2^{B+2k})$, sends $d = g^y h^s$.
• Step 2. The verifier issues a challenge $e \in [0, C)$ and sends it to the prover.
• Step 3. Prover sends $u = y + ex$ and $v = s + er$ - verifier checks $g^u h^v = dc^e$

Summation Protocol

• Keynotes : The key is that if $A = g^a h^{r_1}$, $B = g^b h^{r_2}$, $C = g^c h^{r_3}$ with $a + b = c$, we know the discrete logarithm of $C(AB)^{-1} = h^{r_3-r_1-r_2}$ over base $h$. Since the prover cannot calculate the discrete logarithm of $g$ over $h$, this can be a proof.
• Step 0. Prover has three commitments $A, B, C$ of $a, b, c$ and would like to prove $a + b = c$.
• Step 1. Prover first proves that they can open the commitments $A, B, C$ in a zero-knowledge way.
• Step 2. Prover then proves the knowledge of discrete logarithm of $C(AB)^{-1}$ over base $h$ in a zero-knowledge way. Since we have assumed honest-verifier setting, it can be done in a way similar to Schnorr's protocol. Of course, we have to be careful about the range we choose our parameters from. The same applies for the Setup stage, where the verifier proves the knowledge of $\alpha$ to the prover. For details, refer to the original paper, page 5. This completes the proof of $a + b = c$, in a zero-knowledge way.

Multiplication Protocol

• Keynotes : The key is that if $A = g^a h^{r_1}$, $B = g^b h^{r_2}$, $C = g^c h^{r_3}$ with $ab = c$, we have $C = A^b h^{r_3 - br_1}$.
• Step 0. Prover has three commitments $A, B, C$ of $a, b, c$ and would like to prove $ab = c$.
• Step 1. Prover chooses random $y \in [0, TC2^k)$, $s_2 \in [0, C 2^{B+2k})$, $s_3 \in [0, TC2^{B+2k})$.
• Step 2. Prover sends $d_2 = g^y h^{s_2}$, $d_3 =  A^y h^{s_3}$ to the verifier.
• Step 3. Verifier issues challenge $e \in [0, C)$ and sends it to the prover.
• Step 4. Prover sends $u = y + eb$, $v_2 = s_2 + er_2$, $v_3 = s_3 + e(r_3 - br_1)$ to the verifier.
• Step 5. Verifier checks if $g^u h^{v_2} = d_2 B^e$, $A^u h^{v_3} = d_3 C^e$ holds.

We will now (very) briefly sketch how the each protocols are proved to be zero-knowledge. The stuff going on is basically

• Proving Completeness : Trivial - just substitute all values in and check if the equation is true.
• Proving Soundness : "Standard proof techniques for soundness" + Assumptions (Strong Root, Small Order, Strong RSA, etc)
• Proving Zero-Knowledge : Done by simulation - the choice of the intervals in which we select our parameters comes into play here.
• Additional Notes : It's very important that the prover does not know the order of $h$ - for example, if the prover knew the order $pq$, they can forge a commitment of $x$ into a commitment of $x + pq$ easily. However, this condition makes it hard for the prover to truly generate a "uniform random distribution" (for example, in Schnorr's protocol, the prover generates the integer in $[0, p)$, where $p$ is the group order) - and this is why we need statistical zero-knowledge instead of the "perfect" variant. It's quite tricky...

4. Diophantine Sets and Diophantine Argument of Knowledge

Now let's think about what we can do with our integer commitment scheme. Working with integers in $[-T, T]$, we can 

• Prove $a + b = c$ with only commitments, in a zero-knowledge way. 
• Prove $ab = c$ with only commitments, in a zero-knowledge way.

It's clear that by using addition and multiplication protocols we can actually prove that we have computed an integer coefficient multivariable polynomial on some input. In other words, we can prove that $y = f(x_1, x_2, \cdots , x_n)$, for some integer coefficient polynomial that both prover & verifier know using only the commitment values for $x_i$'s and $y$ in a zero-knowledge way. Here's an easy example.

• Prover has some values $x_1, x_2, x_3, x_4$ that satisfies $x_4 = x_1x_2 + x_3$. How to prove it?
• Prover calculates $x_5 = x_1x_2$ and commits $x_1, x_2, x_3, x_4, x_5$.
• Prover can now prove $x_5 = x_1x_2$ and $x_4 = x_3 + x_5$ in a zero-knowledge proof, only using commitments.

While that's cool and already has quite a lot of applications, it's quite limited. There are plenty of prepositions that one would like to prove that does not have the form of "I evaluated a integer coefficient polynomial"... - or are there?

To dig deeper here, we need the notion of Diophantine Sets. 

• Diophantine Sets : A set $S \subset \mathbb{Z}^k$ is called Diophantine if and only if there exists a integer coefficient multivariate polynomial $P$ such that $v \in S \iff \exists w \in \mathbb{Z}^{k'} \text{  s.t.  } P(v, w) = 0$, i.e. if $v \in S$ iff $v$ is a part of a solution for a fixed Diophantine equation.
• In the above definition, we call $P$ as a representing polynomial of $S$, and $w$ as a witness.

This notion leads us to a much more versatile approaches for a proof. If $S$ is Diophantine and I want to prove $v \in S$, I can

• Find a representing polynomial $P$ of $S$ and publicize it along with the full formula & proof for $P$.
• To prove $v \in S$, find a witness $w$. Prove $P(v, w) = 0$ using integer commitment scheme.

This is the fundamental idea of Diophantine Argument of Knowledge, abbreviated as DARK.

The obvious question is "what sets are Diophantine?" : after all, it should cover a lot of different sets for this to have practical meaning.

Here's one of the more surprising results in mathematics - 

• Computably Enumerable Sets : A set $S$ is computably enumerable if and only if there is an algorithm that halts if the input is a member of $S$, and runs forever if otherwise. Equivalently, a set $S$ is computably enumerable if there is an algorithm (not necessarily halts) that enumerates the members of $S$. Obviously, a lot of sets we deal with are computably enumerable.
• Matiyasevich's Theorem (MRDP Theorem) : [Diophantine Sets] = [Computably Enumerable Sets]

so a metric ton of sets are Diophantine. However, to put into practical use, more questions must be asked.

• How do we even find the suitable representing polynomial $P$? How do we prove it?
• If we found $P$, how do we find the witness $w$? Is the size (number of bits) of $w$ reasonable/practical?

Therefore, we deal with special Diophantine sets that 

• have representing polynomial $P$ (we can actually construct)
• has a polynomial time algorithm to compute the witness $w$, which has polynomial length.

In this paper, we narrow down our choices even further, by adding the constraint

• the length of our witness has to be subquadratic to the length of the input

which is important for practical uses. Now our question is "what can we prove under these constraints?".

5. Tricks, Range Proofs, Exponential Relations, and Bounded Arithmetic

Tricks

Here we outline some tips and tricks that we will use later on. Suppose we have two Diophantine sets $S_1$ and $S_2$, with respective representing polynomials $P_1, P_2$. How do we deal with $S_1 \cap S_2$ or $S_1 \cup S_2$? These will be our way to deal with and/or operations on prepositions. 

• $S_1 \cap S_2$ : We use $P_{\cap}(v, w_1, w_2) = P_1(v, w_1)^2 + P_2(v, w_2)^2$ as our polynomial.
• $S_1 \cup S_2$ : We use $P_{\cup}(v, w_1, w_2) = P_1(v, w_1) \cdot P_2(v, w_2)$ as our polynomial.

It's relatively clear that these two work as desired, and witnesses can be transported over as well.

Range Proofs

We have a homework from chapter 3 - we have to prove a value is in some range for the scheme to work.

To prove $-T \le x \le T$, it suffices to prove $T-x \ge 0$ and $T+x \ge 0$. Therefore, it suffices to have a scheme that proves an integer is nonnegative. To do this, it suffices to have a nice representing polynomial $P$ for nonnegative integers, with witness easy to find.

• Construction : We use the polynomial $P(x, a, b, c, d) = x - a^2 - b^2 - c^2 - d^2$.
• Proof (representation) : Obviously, if $P(x, a, b, c, d) = 0$, we have $x = a^2 + b^2 + c^2 + d^2 \ge 0$. On the other hand, if we have $x \ge 0$, we can write it as $a^2 + b^2 + c^2 + d^2$ by Lagrange's Four Square Theorem.
• Proof (efficiency) : It is clear that the witness size is not an issue here. We show that it's feasible to find $a, b, c, d$ such that $a^2 + b^2 + c^2 + d^2 = x$. A quick outline of an (probabilistic) algorithm is as follows - 
• Algorithm : If $x$ is small, we can simply brute force over $a, b, c, d \in [0, \sqrt{x}]$. If $x$ is large, take $c$ as a random value in $[0, \sqrt{x}]$ and $d$ as a random value in $[0, \sqrt{x-c^2}]$. Now, we pray that $x - c^2 - d^2$ is actually a prime of the form $4k+1$. Heuristically, with Prime Number Theorem, we can see that there exists a good probability that this holds. Now all we need to do is write $x-c^2-d^2$ as a sum of two squares. There exists a few fast algorithms that writes a $4k+1$ prime as a sum of two squares - check out this cool thread.

Now we can argue stuff like $a \ge b$ in our proofs, and it gives us much more versatility! 

Exponential Relations

Here, our goal is to prove $c =  a^b$. Our views on representation polynomial are a bit different since we now have a view that is focused on practical applications - we will change it as follows. This turns out to be important for proving $c = a^b$ zero-knowledge.

• If $v \in S$, we should be able to efficiently find a polynomial length $w$ such that $P(v, w) = 0$.
• If $v \notin S$, we should not be able to efficiently find a polynomial length $w$ such that $P(v, w) = 0$ - one way to prove this "not able to efficiently find" thing, is to prove that all the fake "witness" $w$ with $P(v, w) = 0$ has very large length.

We can now enjoy the following theorem, and I will not even try to type this out or code this.

Let's decipher this. Since the expressions (E1-E10) are all prepositions that can be written as a polynomial equation, we can combine them as a one big integer coefficient multivariate polynomial $P$ with our "trick". Basically, if $\mu_1^{\mu_2} = \mu_3$, we can efficiently find our witness for $P$ that has subquadratic length. If $\mu_1^{\mu_2} \neq \mu_3$, either the witness for $P$ does not exist, or the witness has a large length, $\Omega(\mu_3 \log \mu_3)$ - which makes it impractical to use as a fake "proof" that $\mu_1^{\mu_2} = \mu_3$. We can also take care of edge cases like $\mu_1=0, 1$, $\mu_2 = 0, 1, 2$, $\mu_3=0$ easily with our "trick" as well. This shows that we can completely prove $a^b = c$ with DARK, zero-knowledge. 

Bounded Arithmetic

Now that we have a lot of tools at hand, we can take a look at what we can do.

• Bounded Arithmetic : We work over the nonnegative integers, and only use the following operations
• $0$, $\sigma$, $+$, $\cdot$, $\le$, $-$, $|x|$, $\lfloor x/2 \rfloor$, $\lfloor x/2^k \rfloor$, $\sharp$
• $0, +, \cdot , \le , \lfloor x/2 \rfloor , \lfloor x/2^k \rfloor$ have usual definitions.
• $\sigma(x)$ is simply $x$'s next integer, $x + 1$. 
• $-$ is a bit different because we are working over nonnegative integers, $x-y$ is actually $\max(x-y, 0)$.
• $|x|$ is the bitwise length of $x$, i.e. $\lfloor \log_2 (x) \rfloor + 1$, excluding the case $x = 0$. $x \sharp y$ is defined as $2^{|x| \cdot |y|}$

Since we now have and/or of prepositions, addition, multiplication, exponentiation ready to be proved in a zero-knowledge way, we can combine these with relative ease to show that all of those operations can be used, and proved in a zero-knowledge way. It seems that bounded arithmetic is quite researched, and a lot of useful prepositions can be written using the bounded arithmetic language.

Here's an outline of proof - 

• $0, +, \cdot$ : We already know how to prove these by our integer commitment scheme.
• $ \le $ : We studied how to do range proofs - simply proof $b - a \ge 0$ to show $a \le b$. 
• $ - $ : $a - b = c$ is either ($a = b+ c$ and $c \ge 0$) or ($a \le b$ and $c = 0$), so combine.
• $|x|$ : Deal with the case $x=0$ separately, and write $y = |x|$ as $2^{y-1} \le x \le 2^y-1$. Now do range proofs & exponentiation.
• $\lfloor x/2 \rfloor$ : $y = \lfloor x/2 \rfloor$ is simply $x = 2y$ or $x = 2y + 1$, so combine them.
• $\lfloor x/2^k \rfloor$ : $y = \lfloor x/2^k \rfloor$ is simply $x = 2^ky + z$ and $0 \le z \le 2^k-1$, so combine them.
• $\sharp$ : Since we can do proofs for $|x|$ and proofs for exponentiation, combining is quite trivial.

There are definitely more content in this paper, including some practical applications and reduction of proof size.

There's also a relatively new paper in 2019 that is much harder and very interesting. Might try to read this one...

main.pdf

Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, Vashek Matyas - 2017

1. Introduction

이 논문은 2017년의 논문으로, 제목처럼 많이 사용되는 RSA 공개키를 소인수분해하는 방법을 다룬다. 

앞선 논문 리딩에서 언급했듯이 RSA 공개키를 소인수분해하면 RSA 기반 암호는 깨진다. 이는 Textbook RSA든 RSA-OAEP든 마찬가지다.

그러니 이 논문은 당연하게도 많은 사람들에게 충격을 주었고, 실제로 이 논문 때문에 시스템을 교체한 곳도 많다고 한다.

논문의 제목처럼, 이 공격은 저번에도 언급된 Coppersmith's Attack과 관련이 깊다. 그러니 이에 대한 이해가 필수적이다.

이번 논문 리딩에서는 Lattice에 대한 기본적인 내용을 훑고, Coppersmith's Attack에 대한 내용을 증명과 함께 살펴본다.

그 후, 본격적으로 논문을 읽으면서 많이 사용되는 RSA 공개키들이 어떻게 생성되고, 이들이 어떠한 약점을 가지고 있는지 살펴본다. 

2. Brief Introduction to Lattices

사실 나도 잘 모르는 분야지만, 이 논문을 읽는데 필요한 지식들을 간단하게 나열해본다. 자세한 건 나도 빨리 배워야한다.

우리가 다룰 Lattice란, 쉽게 말해서 $\mathbb{R}^n$의 선형독립인 벡터 $v_1, v_2, \cdots, v_d$가 있을 때, $\{ \sum_{i=1}^d a_i v_i  | a_i \in \mathbb{Z} \}$에 해당한다. 

즉, $\mathbb{R}^n$의 subspace를 생각하되 가능한 계수를 $\mathbb{Z}$로 한정시켜서 생각하는 것이다.

이러한 Lattice가 주어졌을 때, 생각할 수 있는 어려운 문제들이 있다. 이들을 간단하게 소개한다.

Shortest Vector Problem: Lattice에 속하는 nonzero vector 중 가장 norm이 작은 것을 구한다.

Closest Vector Problem: Lattice에 속하는 vector 중 주어진 벡터에 가장 가까운 것을 구한다.

이 문제들은 상당히 어려운 것으로 알려져 있고, 이는 곧 Lattice가 암호학에 쓰이는 이유가 된다. (양자내성암호)

Shortest Vector Problem에 대해서 조금 더 논의를 해보자. 

Geometry of Numbers에서 가장 중요한 정리 중 하나인 Minkowski's Theorem을 생각해보자. 이를 활용하면, invertible한 $n \times n$ 행렬 $A$의 column으로 생성되는 Lattice에서 가장 짧은 nonzero vector의 norm이 최대 $\sqrt{n} \cdot \text{det}(A)^{1/n}$임을 어렵지 않게 증명할 수 있다.

그런데 이건 단순히 존재성의 여부이고, 실제로 계산하기에는 매우 어렵다. 

생각해보면, Lattice의 기저가 orthogonal인 경우에는 Shortest Vector Problem이 매우 쉽다는 것을 알 수 있다.

그러니 Lattice 자체는 그대로 유지하면서, 기저를 orthogonal하게 바꾸고 싶다는 전략이 나온다.

단순한 $\mathbb{R}^n$ 공간이었다면 Gram-Schmidt가 가능하지만, 여기서는 정수 계수를 유지해야 하므로 쉽지 않다.

이를 대신하는 알고리즘이 LLL 알고리즘이다. 자세한 디테일은 나도 모르므로 생략하지만, 다음 결과는 중요하다.

이 알고리즘을 통해서, 크기가 $2^{(n-1)/4} \cdot \text{det}(A)^{1/n}$ 이하인 nonzero vector를 찾을 수 있다는 것이다.

또한, LLL 알고리즘은 $n$에 대한 다항시간에 작동하므로, 효율적인 알고리즘이다.

3. Coppersmith's Attack

여기서는 Coppersmith's Attack이 무엇인지를 다룬다. 기본적으로 변수 1개인 경우를 다룬다.

다항식 $h(x) = \sum_{i=0}^n a_i x^i$에 대하여, $||h||^2 = \sum_{i=0}^n |a_i|^2$이라고 하자.

Theorem. (Coppersmith) $N$은 자연수고, $f \in \mathbb{Z}[x]$는 최고차항의 계수가 $1$인 $d$차 다항식이다. $\epsilon \ge 0$을 잡고, $X = N^{1/d - \epsilon}$이라 하자. $N, f$가 주어졌을 때, $|x_0| < X$와 $f(x_0) \equiv 0 \pmod{N}$을 만족하는 $x_0$를 모두 다항식 시간에 찾을 수 있다. 

이 정리를 증명하고, 실제로 $x_0$를 어떻게 찾는지까지 생각해보자.

그 전에 필요한 사전지식이 하나 더 있는데, 바로 다항식을 $\mathbb{Z}[x]$의 원소로 봤을 때 정수근을 찾는 것은 쉽다는 것이다.

이에 대한 내용을 알기 위해서는, 먼저 $\mathbb{F}_p$ 위에서 다항식의 인수분해가 쉽다는 것을 알아야 한다. 이 자료 참고.

그러니 (아마) 충분히 큰 $p$를 잡고 $\mathbb{F}_p$ 위에서의 다항식의 근을 찾은 다음 실제로 근이 되는지를 보면 될 것이다.

이제 본격적으로 Coppersmith's Theorem을 증명한다. 우선 핵심적인 Lemma를 소개한다.

Lemma. $h(x) \in \mathbb{Z}[x]$는 $d$차 다항식이고, $X$는 자연수다. 

$||h(xX)|| < N/\sqrt{d}$이며, $|x_0| < X$가 $h(x_0) \equiv 0 \pmod{N}$을 만족한다면, $h(x_0) = 0$이다.

Proof of Lemma. 접근의 방식 자체는 어렵지 않다. 목표는 $|h(x_0)|<N$을 보이는 것이다.

$|h(x_0)| = \left| \sum_{i=0}^d a_i x_0^i \right| = \left| \sum_{i=0}^d a_i X^i \left( \frac{x_0}{X} \right)^i \right| \le \sum_{i=0}^d \left| a_i X^i \left( \frac{x_0}{X} \right)^i \right| \le \sum_{i=0}^d |a_i X^i|$이다.

위 식의 우변은 Cauchy-Schwarz 부등식에의하여 $\sqrt{d} ||h(xX)||$ 이하가 되고, 다시 조건에 의하여 $N$ 미만이 된다. 증명 끝.

이제 새로운 전략이 나온다. $f(x) \equiv 0 \pmod{N}$의 근을 모두 찾고 싶다면, $f$의 배수인 다항식 중 norm이 작은 것을 하나 찾자.

만약 norm이 충분히 작은 다항식이 나온다면, 그 다항식의 정수근을 찾는 것으로 위 과정을 대체할 수 있다.

$\pmod{N}$을 생각하면서 근을 찾는 것보다 그냥 정수다항식의 정수근을 찾는 것이 훨씬 쉬우므로, 이는 괜찮은 전략이다.

이는 결국 $f(x), xf(x), x^2f(x), \cdots$를 잘 조합해서 작은 norm을 만드는 문제가 되고, Shortest Vector Problem의 냄새가 난다.

하지만 이렇게 단순한 방법으로는 좋은 다항식을 찾기 어렵다는 것을 알 수 있고, 약간의 트릭이 필요하다.

트릭은 $N$ 대신 $N$의 거듭제곱을 생각하는 것이다. $g_{u, v} (x) = N^{m-v} f(x)^v x^u$라는 다항식을 생각하자.

이때, $0 \le u \le d-1$이고 $0 \le v \le m$이다. $m$은 임의로 잡은 값이며 추후에 결정되는 자연수이다.

만약 $x_0$가 $f(x_0) \equiv 0 \pmod{N}$을 만족하면, $g_{u,v}(x)$는 자동으로 모두 $N^m$의 배수이다.

그러므로 바라보는 대상을 $g_{u,v}$로 바꾸고, norm에 대한 제약조건을 $N^m$에 대한 조건으로 바꿔주자.

이제 $n = d(m+1)$이라 하자. $g_{u, v}(xX)$의 차수는 $u + vd$이므로, 이는 $0$부터 $n-1$까지의 값을 순서대로 갖는다.

$g_{u,v}(xX)$의 계수들을 벡터로 보고 Lattice를 만든 후, 이를 행렬로 생각해보자. 이 행렬은 자명하게 triangular하다.

$g_{u,v}(xX)$의 최고차항의 계수가 $X^{u+dv} \cdot N^{m-v}$이므로, 이 행렬의 determinant는 이를 각 $u \in [0, d)$, $v \in [0, m]$에 대하여 곱한 값인 $X^{n(n-1)/2} \cdot N^{dm(m+1)/2}$가 된다. 이제 LLL 알고리즘을 돌려서 'Shortest Vector'를 찾자.

여기서 얻는 'Shortest Vector'의 길이는 최대 $2^{(n-1)/4} \left( X^{n(n-1)/2} \cdot N^{dm(m+1)/2} \right)^{1/n}$이다.

이는 정리하면 최대 $(\sqrt{2}X)^{(n-1)/2} \cdot N^{m/2}$가 되고, 우리의 목표는 이 값이 $N^m / \sqrt{n}$ 미만이 되는 것이다.

그런데 식을 정리해보면 $X = N^{1/d - \epsilon}$일 때 생각보다 잘 부등식이 정리가 되지 않음을 알 수 있다.

이를 해결하기 위해서, $X = \frac{1}{2} N^{1/d - \epsilon}$을 생각해서 우선 Coppersmith's Theorem의 약한 버전을 증명하자.

그 후, $X$의 상위 비트에 대해서 brute force를 진행하면서 각각의 경우에 대하여 위 정리를 반복해서 사용해주자.

그러면 $X$가 $N^{1/d - \epsilon}$인 경우에 대해서도 다항식 시간에 해를 모두 구할 수 있다는 것을 알 수 있고, 나아가 $\epsilon = 0$인 경우까지도 다룰 수 있다.

이 알고리즘은 변수가 두 개인 경우로 확장될 수 있으며, 이를 통해서 다음 결과도 얻을 수 있다.

Theorem. (Coppersmith) $N = pq$가 $n$-bit RSA modulus라 하자. 

이때, $p$의 $n/4$ least significant bits을 알거나 $p$의 $n/4$ most significant bits를 알면, $N$을 다항식 시간에 소인수분해 할 수 있다.

실제로 이 정리에 해당하는 공격을 수행하기 위해서, 변수가 하나인 형태의 Coppersmith's Attack을 사용할 수도 있다.

위 식에서 $N = pq$라고 하면, 우리는 $N$은 알지만 $p$는 모르는 상태다.

만약 충분히 큰 $r$에 대해서 $u = p \pmod{2^r}$을 알고 있다면, 결국 $2^r x + u$라는 일차식이 $\pmod{p}$에서 작은 근을 갖는다는 것을 알 수 있다.

이를 최고차항의 계수가 $1$이도록 바꿔주면 $x + u \cdot (2^{-r} \pmod{N})$이라는 일차식을 얻는다.

우리는 실제로 $p$를 모르지만, $p$의 배수 $N$을 알고 있으므로 Coppersmith's Attack의 모든 부분을 수행할 수 있다.

즉, norm이 $p^m / \sqrt{n}$ 이하인 다항식을 만들기 위해서 $N$을 사용하는 방식을 택할 수 있다.

위 방법을 그대로 사용하면 부등식 계산 부분에서 뭔가 잘 안된다는 것을 알 수 있다.

대신, $x^i f(x)^m$ 형태의 다항식을 몇 개 추가해주면 LLL 알고리즘이 잘 돌아갈 조건을 제공함을 알 수 있다. 이 구현 참고. 

직관적으로 생각해보면, $N$을 사용한 다항식은 계수가 지나치게 큰 것이므로 ($p$를 모르니 그 배수를 쓴 것이니) $x^i f(x)^m$ 형태의 다항식을 추가해서 이를 희석시킨 것이라고 생각해도 될 것 같다. 아무튼 하면 된다 :) 이제 본격적으로 논문을 읽어보자.

4. RSA Key Generation, and RSALib

RSA 키는 어떻게 만들까? 예를 들어 1024 비트 키를 만들고 싶다고 하자. 

그러면 512 비트 소수 $p, q$를 찾아서, $N=pq$를 잡고, $e = 2^{16}+1$이라 한 다음, $d$를 $ed \equiv 1 \pmod{\phi(N)}$이 성립하도록 잡으면 된다. 

안전성을 위해서는 $p, q$가 갖춰야 할 여러 조건들이 있고, 이에 대해서는 앞선 리딩에서 다뤘다.

하지만 결론적으로 웬만하면 랜덤한 $p, q$를 잡으면 된다는 사실 역시 알고 있다.

소수 정리에 의해서 $x$ 근처의 자연수가 소수일 확률은 매우 대충보면 $1/\log x$ 정도다.

그러니까 랜덤한 자연수를 잡고, Miller-Rabin 등 소수 판별 알고리즘을 돌리는 것을 소수가 나오기 전까지 반복하면 소수를 얻을 수 있다.

그런데 RSA 키를 가능한 빠르게 생성하고 싶다고 가정하자. 어떻게 위 과정을 최적화할 수 있을까?

기본적으로 소수를 찾는 과정이 가장 느리므로, 이 과정을 더 빠르게하면 좋을 것 같다.

당장 랜덤한 자연수를 찍으면 2부터 100까지의 소수 중 하나의 배수가 될 확률이 상당히 높을텐데, 이거라도 미리 거르면 좋을 것 같다.

그래서 RSALib는 다음과 같은 방법을 채택했다. $n$이란 자연수를 먼저 설정하는데, 이는 RSA 키의 길이에 따라서 결정된다.

그 후, $M$을 첫 $n$개의 소수의 곱으로 설정한다. 이제 랜덤한 $k, a$를 잡아서 $k \cdot M + (65537^a \pmod{M})$을 소수 후보로 잡는다.

이렇게 하면 첫 $n$개의 소수는 약수로 갖지 않게 된다는 것이 자명해지고, 소수 판별을 반복하는 횟수가 줄어든다.

그런데 생각해보면, $M$은 여러 소수의 곱이니 원시근이 없고, $65537^a \pmod{M}$은 $M$과 서로소인 모든 나머지를 표현하지 못한다.

다르게 말하면 이는 이 새로운 방식이 생성할 수 없는 소수들이 있고, 실제로 이 방식은 랜덤하지 않다는 것이다.

또한, $p, q$가 이 방식으로 생성되었다면, $N \pmod{M}$ 역시 $65537$의 거듭제곱으로 표현할 수 있다.

$M$은 큰 값이지만 smooth 하므로, Pohlig-Hellman Algorithm으로 $N \equiv 65537^c \pmod{M}$인 $c$를 찾을 수 있다.

이는 생성된 키 $N$이 제대로 계산되었는지 (RSALib로 생성되었는지) 확인하는 방법이 될 수도 있다.

다시 강조하지만, $M$과 서로소인 나머지 중 $65537^a \pmod{M}$으로 표현될 수 있는 값의 비율은 매우 낮다.

이제 이 RSA 키의 특수한 형태를 극도로 활용하여, $N$을 아예 소인수분해하는 방법을 찾아보자.

5. The ROCA Vulnerability

생각보다 아이디어는 그렇게 어렵지 않다. $p = k \cdot M + (65537^a \pmod{M})$이라 하자.

만약 우리가 $a$를 안다면, $p$의 하위 비트를 아는 것이 되며 이는 Coppersmith's Attack을 사용할 환경을 제공한다.

$T$를 $\pmod{M}$에 대한 $65537$의 order라고 하자. $c$를 $N \equiv 65537^c \pmod{M}$인 값이라고 하자.

$T, c$는 모두 어렵지 않은 정수론 알고리즘을 (order-finding algorithm, Pohlig-Hellman) 사용하여 계산할 수 있다.

이제 $a$를 $c/2$부터 $c/2 + T/2$까지를 brute-force하면서 계산하면, $p$가 걸리던 $q$가 걸리던 뭔가 걸린다.

즉, Coppersmith 공격을 약 $T/2$번 반복하면, $N$을 소인수분해 할 수 있다. 여기서 $T$가 작으면 좋겠다는 생각을 할 수 있다.

이를 위해서 일종의 최적화를 한다. $M'|M$인 $M'$을 잡되, 다음 조건을 모두 만족하도록 하자.

조건 1: $\pmod{M'}$에 대한 $65537$의 order가 작은 편이다.

조건 2: $M'$이 충분히 커서, $p \pmod{M'}$을 고정하면 Coppersmith's Attack을 수행할 수 있다. 즉 $M' > N^{1/4}$.

$M'$을 최적화하는 과정은 휴리스틱, 그리디, 전탐색 등을 든든하게 섞어서 해시코드 식 접근을 했다고 한다.

이제 이 과정을 모두 합치면 $N$을 소인수분해 할 수 있다. 대표적인 구현은 이 코드를 참고하자.

"Twenty Years of Attacks on the RSA Cryptosystem" - Dan Boneh

RSA에 대한 공격을 가장 자세하게 잘 다루는 review paper인 것 같다. 인용 횟수가 900번 근처다...

논문 리딩은 기본적으로 복습을 하면서 더 배우려고 하는 것이기 때문에, 내가 배운 내용도 조금씩 추가하면서 쓰겠다.

또한, Lattice를 제대로 알아야 (특히 LLL) 더욱 자세하게 글을 쓸 수 있을 것으로 보인다. 일단은 맛만 보는 걸로.

#1: Introduction

RSA는 카이사르 암호와 함께 가장 유명한 암호체계 중 하나일 것이다. 1977년 공개된 이 암호체계는 지금도 사용되고 있다. 

많이 사용되는 체계인만큼, 많은 암호학자들은 이 체계의 허점을 찾기 위해서 수많은 공격 방법들을 제시해왔다. 

공격 방법을 탐구하는 과정을 통해서, 암호학자들은 RSA를 안전하게 구현하고 활용하는 방법을 더욱 알아가게 되었다.

논문의 목적은 이러한 공격들을 돌아보면서, 공격을 위한 수학적 도구에는 어떤 것이 있으며, 이를 막는 방법을 알아보는 것이다.

먼저 Textbook RSA를 살펴보자. $p, q$를 크기가 비슷한 큰 소수라 하고, $N=pq$라 하자. 두 자연수 $e, d$는 $ed \equiv 1 \pmod {\phi(N)}$을 만족하는 자연수다. 여기서 $\phi(N) = (p-1)(q-1)$이다. 이때 $N$을 RSA modulus, $e$를 encryption exponent, $d$를 decryption exponent라고 부른다. $\langle N, e \rangle$은 모두 공개되어 있고 (공개키), 메세지를 암호화하는데 사용할 수 있다. 한편, $\langle N, d \rangle$은 비밀이며 (비밀키), 암호화된 메세지를 받는 사람만이 알고 있다. 메세지를 받는 사람은 비밀키를 이용하여 실제 메세지를 확인할 수 있다. 여기서 메세지란, $M \in \mathbb{Z}_N^{*}$을 말한다. $M$을 암호화하려면, $C \equiv M^e \pmod{N}$을 계산하면 된다.

이를 복호화하려면, $M \equiv C^d \pmod{N}$을 계산하면 된다. 여기서 $ed \equiv 1 \pmod{ \phi(N)}$과 오일러의 정리를 이용한다.

RSA 함수를 $x \rightarrow x^e \pmod{N}$으로 정의하자. $d$를 알면, 이 함수의 역을 쉽게 구할 수 있다.

슬슬 One-Way Function의 느낌이 나온다. 이러한 상황에서, 암호학자들은 $d$를 trapdoor라고 부른다.

trapdoor가 있는 one-way function은 전자서명 등에서 활용될 수 있다. 여기서 RSA의 유용함을 알 수 있다.

메세지 $M$을 내가 보냈다는 것을 인증하려면, 비밀키 $d$를 이용하여 $M^d \pmod{N}$을 사람들에게 주면 된다. 

그렇다면, 다른 사람들은 공개키 $e$를 이용하여 $M \equiv (M^d)^e \pmod{N}$, 즉 실제 메세지를 얻는다.

여기서는 $d$에 대한 정보가 없을 때, RSA 함수의 역함수를 계산하는 난이도에 대해서 다루도록 한다.

즉, $N, e, C$가 주어진 경우, $C$의 discrete $e$-th root modulo $N$을 구하는 난이도에 대해 다루는 것이다.

당연히 전수조사의 방법이 있으나, 이는 역시 당연하게도 매우 비효율적이다. 불가능하다고 보는 게 맞겠다.

우리가 관심이 있는 대상은 당연히 실제로 사용될 수 있는 공격들, 특히 다항식 시간을 필요로 하는 공격들이다.

실제 RSA를 이용한 암호체계는 단순한 RSA 함수 응용의 범주를 넘어간다. 안전한 암호가 되려면 빡빡한 기준을 통과해야 한다.

단순하게 RSA 함수를 이용하여 암호화를 하면, 메세지 $M$에 대한 non-trivial information을 손쉽게 얻을 수 있다.

대표적으로, $M$의 modulo $N$에 대한 Jacobi Symbol의 값을 매우 간단하게 얻을 수 있다.

또한, 단순하게 RSA 함수를 이용하여 암호화를 하면 adaptive chosen ciphertext attack에 아주 간단하게 당한다.

복호화를 하고 싶은 $C \equiv M^e \pmod{N}$이 있다고 하자. $2^eC$를 복호화하는 쿼리를 날려보자.

그러면 얻는 답은 $(2^eC)^d \equiv 2C^d \equiv 2M \pmod {N}$이다. 여기서 $M$을 복원하는 것은 쉬운 일이다.

그러니 실제로 RSA를 이용해서 암호화를 하려면, "랜덤함"으로 적당히 간을 쳐서 암호화를 할 필요가 있다. 여기서는 다루지 않는다.

RSA를 사용하기 위해서는, 먼저 큰 소수 $p, q$를 잡는다. 랜덤하게 큰 수를 잡고 적당한 소수 판정법을 쓰면 된다.

그 후 $N = pq$를 얻은 뒤, 적당한 $e$를 잡고 modulo inverse를 계산하는 알고리즘으로 $d$를 계산한다.

물론, 소수는 충분히 많기 때문에, 이러한 방법으로도 RSA key pair를 효율적으로 생성할 수 있다. 

RSA를 공격하는 가장 생각하기 쉬운 방법은 사실 그냥 $d$를 찾는 것이다. $d$를 어떻게 찾을 수 있을까?

가장 쉬운 접근은 역시 $\phi(N)$을 찾는 것이다. 그런데 이는 $N$을 소인수분해하는 것과 동치임을 쉽게 파악할 수 있다.

소인수분해가 얼마나 어려운 문제인지는 꽤 잘 알려져 있다. GNFS가 현재까지는 가장 빠르지만, 여전히 느리다.  

하지만, 쉽게 소인수분해가 가능한 수 역시 존재한다. 예를 들어보면, Pollard의 $p-1$ 알고리즘이 있다.

만약 $p-1$이 작은 소수들의 곱으로 표현이 된다면, 이 알고리즘을 통해서 $N=pq$를 인수분해 할 수 있다.

비슷한 접근으로, Williams의 $p+1$ 알고리즘도 존재한다. 이런 알고리즘으로 인수분해가 가능한 $N$은 사용하면 안된다. 

어쨌든, 인수분해가 가능하다면 RSA는 쉽게 깰 수 있다. 반대는 어떨까? 

즉, RSA를 효율적으로 깰 수 있으면 인수분해 역시 효율적으로 할 수 있을까? 이는 open problem이다.

만약 "가능하다"가 답이라면, chosen ciphertext attack으로 RSA를 깰 수 있다고 한다.

한편, $N$의 인수분해를 알면 우리는 $d$를 쉽게 계산할 수 있다. 반대는 어떨까?

즉, $d$를 안다면 $N$의 인수분해를 쉽게 계산할 수 있을까? 이는 "가능하다"가 답이다. 증명을 보자.

Theorem. RSA의 기본 조건을 만족하는 $e, d, N$을 아는 경우 $N$을 소인수분해 할 수 있다.

#2: Elementary Attacks

첫 번째로 살펴볼 것은 메세지 자체가 크기가 작은 경우이다. 만약 $M$이 크기가 작고, 크기가 비슷한 두 자연수의 곱으로 표현될 수 있다고 하자. 이 경우, 간단한 meet-in-the-middle attack을 통해서 메세지를 복원할 수 있다. Key의 크기가 커도 메세지의 크기가 작으면 소용없다는 점을 간과한 경우 발생하는 문제다. 

이와 같이 RSA를 잘못 활용한 경우 이를 공격하는 방법을 여기서 더 소개한다.

두 번째로 살펴볼 것은, 모든 사람들에게 공통된 $N$을 사용하게 하는 경우 발생하는 문제점이다. 

각 사람들마다 서로 같은 $N$을 주는 대신, 각 사람들에게 $e_i, d_i$를 부여하면 어떻게 될까? (물론, $p, q$는 알려주지 않는다)

다른 사람의 공개키 $e_i$를 봐서 $d_i$를 계산할 수 없으므로 ($p, q$는 모르니까) 이 방법은 잘 먹힐 것처럼 생겼다.

하지만 앞에서 보았듯이, $e_i, d_i, N$을 알면 효율적으로 $N$을 소인수분해 할 수 있다. 그러니 이렇게 하면 나라 망한다.

즉, 모든 사람들이 서로 다른 $N$을 갖도록 해야 안전한 암호체계를 만들 수 있다.

세 번째로 살펴볼 것은, "blinding"이란 것이다. Eve가 Alice에게 메세지 $M \in \mathbb{Z}_N^{*}$에 대한 전자서명을 원한다고 하자.

즉, $M^d \pmod{N}$을 원하는 것이다. 물론 호구가 아닌 이상 Alice가 Eve의 말을 듣고 전자서명을 하지는 않는다.

하지만, Eve가 적당한 $r \in \mathbb{Z}_N^{*}$를 랜덤하게 잡고, $M' \equiv r^eM \pmod{N}$을 계산했다고 하자.

이제 Eve는 Alice에게 $M'$에 대한 전자서명을 부탁한다. Alice는 $r$의 존재도 모르고 그러니 $M$도 모른다.

이제 Alice는 큰 문제가 없게 생긴 $M'$에 대한 전자서명을 줄 수도 있다. 이때, 그 전자서명의 값은 $rM^d \pmod{N}$이 된다.

결국 Eve는 $r$의 modulo inverse를 취해줘서 $M^d \pmod{N}$의 값을 얻게 된다. 전자서명이 뚫린 것이다.

물론, 실제 RSA를 이용한 전자서명이 이렇게 간단하지는 않으므로, 걱정은 하지 않아도 된다. 

또한, 논문에 의하면 blinding이 가능하다는 점을 이용하여 "anonymous digital cash"를 구현할 수 있다고 한다. 

#3: Low Private Exponent

애초에 작은 $d$ 값을 왜 사용하고 싶어하는 걸까? 이유는 시간에 있다. $d$가 작을수록 decryption에 필요한 시간이 줄어들기 때문이다. 

적은 계산 시간은 솔깃하지만, 작은 $d$ 값은 보안성 입장에서 볼 때 매우 위험하다. 다음 공격을 소개한다. 

Theorem. (Wiener's Attack) $N = pq$고, $q < p < 2q$라 하자. $d < \frac{1}{3} N^{1/4}$라 하자.

$ed \equiv 1 \pmod{\phi(N)}$인 $N$과 $e < \phi(N)$이 주어졌을 때, $d$를 효율적으로 복원할 수 있다.

이 attack을 회피하면서 빠르게 decryption을 할 수 있는 방법은 없을까? Wiener는 이런 방법을 2개 제시했다.

이 방법들은 안전성이 증명된 것은 아니나, 최소한 Wiener's Attack은 회피할 수 있다. 

첫 번째 방법은 $e$를 키우는 것이다. 위 증명을 살펴보면, $e < \phi(N)$을 사용하였다.

이를 대신하여, 큰 자연수 $t$를 잡고 $e' = e + t \cdot \phi(N)$을 이용하자. 당연히 $d$의 값에는 변화는 없다.

위 증명과 같은 방식으로 계산을 하면, $e' > N^{1.5}$일 경우 $d$가 아무리 작아도 이 방법으로 공격을 할 수는 없음을 확인할 수 있다.

물론, encryption exponent를 키우면 encryption에 소모되는 시간이 매우 커진다. 일종의 trade-off라고 봐야겠다.

두 번째 방법은 CRT를 이용하는 것이다. 복호화 과정의 결과값을 $\pmod{p}$와 $\pmod{q}$에 대해 따로 계산하자는 것이다.

만약 $d_p \equiv d \pmod{p-1}$과 $d_q \equiv d \pmod{q-1}$이 둘 다 작다면, 이는 효율적으로 계산할 수 있다.

물론, 실제 결과값을 얻고 싶다면 CRT를 이용해주면 된다. 핵심 아이디어는, $d_p, d_q$가 작더라도 $d$가 클 수 있다는 것이다. 그런데 다음이 성립한다.

Theorem. 위 방법을 사용할 때, adversary는 $\mathcal{O}(\operatorname{min}(\sqrt{d_p}, \sqrt{d_q}))$ 시간에 $N$을 소인수분해 할 수 있다.

그러니 결론은 위 최적화를 사용하더라도 적당히 사용해야 한다는 것이다. $d_p , d_q$ 역시 보안을 위해서는 잘 잡아야 한다는 것이다.

Wiener's Attack의 $d$에 대한 bound는 이후 더욱 개선되었다. $d < N^{0.292}$면 $N, e$를 통해 $d$를 복원할 수 있다는 것을 Boneh와 Durfee가 증명하였다. 

또한, $d < N^{0.5}$라면 $N, e$를 통해 $d$를 복원할 수 있다는 것이 강력한 추측이다. 이는 open problem이다.

#4: Low Public Exponent

이제는 $e$가 작은 경우를 다룬다. 작은 $e$가 매력적인 이유는 encryption에 드는 시간이 줄어들기 때문이다.

하지만 앞서 $d$에 대해서 살펴본 내용들과 마찬가지로, 작은 $e$를 사용하면 다양한 공격의 표적이 될 수 있다.

$e$로 사용할 수 있는 가장 작은 값은 $3$이지만, 아래에 제시된 공격들을 막기 위해 $e=2^{16}+1$이 자주 사용된다.

아래에서 다룰 공격들의 중심에는 Coppersmith의 정리가 있다. 이를 완전히 이해하려면 Lattice에 대한 이해가 필수적이다.

아직은 내가 Lattice를 배우지 않았으니, 지금은 단순히 statement를 적고 넘어간다. 나중에 더 깊은 내용을 추가하는 것이 목표다.

Theorem. (Coppersmith) $N$은 자연수고, $f \in \mathbb{Z}[x]$는 최고차항의 계수가 $1$인 $d$차 다항식이다. $\epsilon \ge 0$을 잡고, $X = N^{1/d - \epsilon}$이라 하자. $N, f$가 주어졌을 때, $|x_0| < X$와 $f(x_0) \equiv 0 \pmod{N}$을 만족하는 $x_0$를 모두 다항식 시간에 찾을 수 있다. 

이 정리의 첫 번째 활용 사례로, Hastad's Broadcast Attack을 알아보자. 

만약 Alice가 메세지 $M$을 여러 사람들에게 전송하고 싶다고 하자. 각 사람들은 $N_i , e_i$를 공개키로 가지고 있다.

그러면 Alice는 $M^{e_i} \pmod{N_i}$를 각각 계산한 다음 이를 각 사람들에게 전송한다. Eve가 이 값들을 전부 확보했다고 가정하자.

가장 간단한 예시로, $e_i$의 값들이 전부 $3$인 경우를 생각해보자. 그러면 값을 $3$개만 확보해도 Eve는 $M$을 복원할 수 있다.

Eve가 $C_1 \equiv M^3 \pmod{N_1}$, $C_2 \equiv M^3 \pmod{N_2}$, $C_3 \equiv M^3 \pmod{N_3}$을 안다고 가정하자. 

그러면 $N_1 , N_2, N_3$가 전부 서로소라고 가정하자. (아니라면, 소인수분해가 간단하게 될 것이다)

이제 중국인의 나머지 정리에서, $M^3 \pmod{N_1N_2N_3}$를 얻을 수 있다. 그런데 $M^3 < N_1N_2N_3$이니, $M$을 얻는다.

이 공격에 대한 간단한 방어를 생각할 수 있다. 각 사람들에게 메세지의 아주 일부를 바꿔서 보내는 것이다.

즉, $i$번째 사람에게 $M^{e_i} \pmod{N_i}$ 대신 $(M+i \cdot 2^m)^{e_i} \pmod{N_i}$를 (물론 $i$와 함께) 보내는 것이다.

여기서 $m$은 $M$의 비트 개수이다. 이 방법은 매우 간단하지만, 위 공격을 막을 수 있을 것으로 보인다.

더욱 일반적으로, 메세지를 전달하고 싶은 사람 $P_1, P_2, \cdots, P_k$가 있을 때, $i$번째 사람에게 $M$을 직접 암호화하는 대신, $f_i \in \mathbb{Z}_{N_i} [x]$를 하나 잡은다음 $f_i(M)$을 암호화하여 (물론, $f_i$와 함께) 보내는 방법을 생각할 수 있다. 이제, Eve가 얻을 수 있는 정보는 다항식 $f_i$와 $e_i, N_i$, $C_i \equiv f_i(M)^{e_i} \pmod{N_i}$이다.  

이 상태에서 Eve가 $M$을 도출하는 것은 매우 어려워보인다. 하지만 충분히 많은 정보를 확보하면 가능하다. Coppersmith's Theorem의 위력을 확인해보자.

Theorem. (Hastad's Attack) $N_1, N_2, \cdots , N_k$는 서로소인 자연수이다. $N_{min} = \operatorname{min}(N_1, N_2, \cdots, N_k)$라 하자. 각 $1 \le i \le k$에 대하여, $g_i \in \mathbb{Z}_{N_i}[x]$는 차수가 $d$ 이하인 다항식이라 하자. $g_i(M) \equiv 0 \pmod{N_i}$이 각 $1 \le i \le k$에 대해서 성립하는 $M < N_{min}$이 유일하고, $k>d$가 성립한다고 가정하자. 이때, $1 \le i \le k$에 대하여 $N_i , g_i$를 전부 알 경우 $M$을 다항식 시간에 찾을 수 있다.

그러니 Eve는 $g_i = f_i^{e_i} - C_i$를 잡은 다음, Hastad's Attack을 활용하여 $M$을 복원할 수 있다.

위 정리의 statement를 다시 읽어보면, 이 공격은 $e_i$의 값들이 작을 때 더욱 강력함도 알 수 있다.

실제로 Broadcast Attack에 대한 방어를 하고 싶다면, "랜덤함"으로 적당히 간을 쳐주면 된다고 한다. 

두 번째 공격은 Franklin-Reiter Related Message Attack이다. $N, e$가 Alice의 공개키라고 하자. 

이제 Bob이 $M_1, M_2 \in \mathbb{Z}_{N}^{*}$를 Alice에게 보내려고 한다.

그런데, 알려진 다항식 $f \in \mathbb{Z}_N [x]$가 있어 $M_1 \equiv f(M_2) \pmod{N}$이 성립한다고 하자.

Bob이 단순하게 $C_1 \equiv M_1^e \pmod{N}$과 $C_2 \equiv M_2^e \pmod{N}$을 계산했다고 하자.

이제, $C_1, C_2$가 주어졌을 때 Eve가 $M_1, M_2$를 복원할 수 있음을 보일 수 있다.

이 공격은 일반적으로 $\mathcal{O}(e^2)$ 정도의 시간을 필요로 한다고 한다. 

일반적인 경우의 증명은 빡센 대수학을 필요로 한다고 하므로, 여기서는 $e=3$이고 $f$가 일차식인 경우를 보인다.

Lemma. $e=3$이라 하고, $N, e$가 RSA를 위한 공개키라고 하자. $M_1 \neq M_2 \in \mathbb{Z}_N^{*}$가 적당한 $f = ax+b \in \mathbb{Z}_N [x]$에 대하여 $M_1 \equiv f(M_2) \pmod{N}$을 만족한다고 하자. 단, $b \neq 0$이다. 이때, $N, e, C_1, C_2, f$를 알면 $M_1, M_2$를 $\mathcal{O}(\log^2 N)$ 시간에 구할 수 있다. 

위 공격을 더욱 강화한 것이 Coppersmith's Short Pad Attack이다. 메세지 $M$에 "랜덤함"으로 간을 해서 암호화를 해야 안전하다고 이미 언급했다.

"랜덤함"으로 간을 하는 가장 간단한 방법은, $M$의 끝에 몇 개의 random bit를 추가하는 것이다. 

하지만 이렇게 간을 대충하면 위험하고, 이를 보여주는 것이 Coppersmith's Short Pad Attack이다.

시나리오는 대강 이런 느낌이다. Alice가 Bob에게 메시지 $M$을 전달하려고 한다. 

이때 Alice는 $M$의 끝에 몇 개의 random bit를 추가하여 암호화한 다음 Bob에게 전송한다. 이를 Eve가 중간에 연결망을 끊어 Bob이 이를 받지 못하게 한다.

그러면 Alice는 $M$의 끝에 몇 개의 random bit를 다시 추가하여 암호화한 다음 Bob에게 다시 전송하게 될 것이다.

이렇게 되면 Eve는 중간에서 같은 메시지의 (물론, 다른 random bit를 갖는) 암호문을 두 개 확보한다. 이제 Eve는 $M$을 복원할 수 있다.

Theorem. (Coppersmith's Short Pad Attack) $N, e$는 RSA 공개키이고, $N$은 $n$-bit이다. $m=\lfloor n/e^2 \rfloor$라 하자. $M \in \mathbb{Z}_N^{*}$는 길이가 $n-m$ 이하인 메시지이고, $M_1 = 2^m M +r_1$, $M_2 = 2^m M+r_2$라 하자. 이때, $r_1, r_2$는 $0 \le r_1, r_2 < 2^m$을 만족하는 서로 다른 정수다. $N, e$와 $C_1, C_2 \equiv M_1^e, M_2^e \pmod{N}$을 알 때, $M$을 다항식 시간에 얻을 수 있다. 

여기서 $e=3$인 경우, 추가되어야 하는 random bit의 길이가 전체 메시지의 $1/9$ 이상은 되어야 함을 알 수 있다.

물론, $e=2^{16}+1 = 65537$을 사용하면, 이 공격에 당할 염려는 사실상 없다고 봐도 무방하다.

마지막으로 살펴볼 내용은 Partial Key Exposure Attack이다. Eve가 열심히 뚫어서 $d$의 일부를 얻은 시나리오를 생각해보자.

이 정보를 가지고 $d$ 전체를 확보할 수 있을까? 답은, $e$가 작으면 충분히 가능하다라는 것이다.

$e < \sqrt{N}$인 경우 $d$의 일부를 이용하여 $d$ 전체를 복원하는 것이 가능하다는 결과도 있다고 한다.

이런 결과가 있는 만큼, 웬만하면 $d$ 전체를 안전하게 보관하는 것이 좋다는 결론을 얻을 수 있다.

계속 등장하고 계신 Coppersmith 선생님의 멋지고 중요한 결과를 하나 더 소개한다. 

Theorem. (Coppersmith) $N = pq$가 $n$-bit RSA modulus라 하자. 

이때, $p$의 $n/4$ least significant bits을 알거나 $p$의 $n/4$ most significant bits를 알면, $N$을 다항식 시간에 소인수분해 할 수 있다.

이를 이용하여, Partial Key Exposure Attack이 실제로 가능함을 어렵지 않게 증명할 수 있다.

Theorem. (Boneh, Durfee, Frank's Partial Key Exposure Attack) $N, d$는 RSA 비밀키이고, $N$은 $n$-bit다. 

$d$의 $\lceil n/4 \rceil$ least significant bits를 알면, $d$ 전체를 $e \log_2 e$에 비례하는 시간에 복원할 수 있다.

추가적으로, $e$가 작은 경우에는 $d$의 most significant bits를 쉽게 얻을 수 있음도 알 수 있다.

$ed - k(N-p-q+1)=1$인 $0 < k \le e$가 있다. $k$를 고정하고 생각하면, $\lfloor \frac{kN+1}{e} \rfloor$가 $d$의 좋은 근사가 됨을 알 수 있다.

정확하게 계산을 해보면 (Wiener's Attack에서 했던 계산이다) 실제 차이가 $3 \sqrt{N}$ 이하임을 알 수 있다.

즉, $e$가 작은 경우에는 $d$의 앞쪽 절반 정도의 most significant bits에 해당하는 후보군을 간단하게 얻을 수 있다.

특히, $e=3$인 경우에는 $k=2$가 강제되고 ($\pmod{3}$을 관찰하면 된다) 그러니 $d$의 앞쪽 절반을 전부 알 수 있다.

놀랍게도 #4에서 증명을 생략한 Coppersmith의 정리들은 전부 Lattice를 활용하는 것으로 알고 있다. Lattice가 많이 사기인듯. 

#5: Implementation Attacks

Implementation Attack은 RSA 함수의 성질 자체를 이용하여 공격을 하는 것이 아니라, RSA 구현체의 성질을 이용하여 공격을 한다.

가장 대표적으로 알려진 것은 Timing Attack이다. decryption을 위해서는, $M \equiv C^d \pmod{N}$을 계산해야 한다.

이 과정은 일반적인 binary exponentiation으로 구현되어 있을 가능성이 높다. 이는 다음과 같은 알고리즘이다.

$d=d_nd_{n-1} \cdots d_0$라고 하자. $C=1$, $z=M$이라고 하자. 각 $i=0, 1, \cdots n$에 대하여, 다음을 반복한다.

만약 $d_i=1$이라면, $C$를 $C \cdot z \pmod{N}$으로 바꾼다. 그 후, $z$를 $z^2 \pmod{N}$으로 바꾼다.

Eve가 적당한 $M_1, M_2, \cdots , M_k \in \mathbb{Z}_N^{*}$에 대해서 $M_i^d$를 계산하는데 걸리는 시간 $T_i$를 측정했다고 하자.

$d$가 홀수임은 자명하므로, $d_0=1$이고 첫 번째 스텝이 끝난 시점에 $C = M$, $z = M^2 \pmod{N}$임을 안다. 

이제부터 본격적으로 경우가 나뉘기 시작한다. 만약 $d_1=1$이라면, 기계는 $C \cdot z = M^3 \pmod{N}$을 계산한다.

$d_1 = 0$이라면, 이를 계산할 필요가 없다. $t_i$를 기계가 $M_i \cdot M_i^2 \pmod{N}$을 계산하는데 걸리는 시간이라고 하자.

이때, $t_i$의 값은 기계에 대한 정보를 충분히 얻으면 (Eve는 컴잘알이다) 사전에 얻을 수 있다고 가정한다. 

핵심적인 관찰은, $d_1 = 1$인 경우 $t_i$와 $T_i$ 사이의 correlation이 존재한다는 것이다. 

하지만 $d_1=0$이라면, $t_i$와 $T_i$는 independent한 것으로 보인다. 그러니 correlation을 기반으로 $d_1$의 값을 찾을 수 있다.

이 순서대로 계속하면, $d_2, d_3, \cdots , d_n$을 전부 복구하여 $d$를 계산할 수 있고 암호를 깰 수 있다.

더욱 자세한 내용과, 이 공격을 구현하는 방법을 알고자 한다면 NEERC 2017의 Editorial을 읽는 것을 추천한다. (나는 아직 안 읽었다)

놀랍게도, 이 대회의 H번이 정확히 이 구현을 요구하는 문제였다. 심지어 이 대회의 K번은 Knapsack Cryptosystem의 특수한 경우를 깨는 문제였다. 

위 공격과 비슷한 맥락으로, 기계가 사용한 전력을 이용하여 공격을 하는 방법 역시 있다고 한다. 

이를 방어하는 방법에는 크게 두 가지가 있다. 첫 번째 방법은, 계산 시간의 측정을 무의미하게 만드는 것이다. 

즉, 계산을 하는 도중에 적당한 딜레이를 추가하여, 위 공격에 필요한 사실들을 전부 거짓으로 만들어주면 된다.

두 번째 방법은, 앞서 언급한 "blinding"을 활용하는 것이다. 기계가 $M^d$를 계산해야 한다고 하자.

그러면 기계는 단순하게 $M^d$를 계산하는 대신, 랜덤한 $r \in \mathbb{Z}_N^{*}$를 잡고 $M' = M \cdot r^e \pmod{N}$을 계산한다.

그 후, $M'^d \equiv r \cdot M^d \pmod{N}$을 binary exponentiation으로 계산하고 modulo inverse를 이용해 $M^d \pmod{N}$을 얻는다.

이렇게 되면 핵심적인 부분인 거듭제곱을 랜덤하고 Eve가 값을 모르는 $M'$에 적용하므로, Eve는 위 공격을 활용할 수 없다.

두 번째로 볼 것은 Random Fault를 활용한 공격이다. 앞서 다루었듯이, CRT를 활용하여 $M^d \pmod{N}$을 빠르게 계산하는 방법이 존재한다.

$d$가 있다면, $d_p \equiv d \pmod{p-1}$과 $d_q \equiv d \pmod{q-1}$을 얻은 뒤 $C_p \equiv M^{d_p} \pmod{p}$, $C_q \equiv M^{d_q} \pmod{q}$를 계산한다.

이제, CRT를 활용하여 $C \equiv M^d \pmod{N}$을 빠르게 계산할 수 있다.

계산을 조금 해보면, (FFT를 활용하지 않는 단순 곱셈을 가정할 때) 이 방법으로 약 $4$배 정도의 속도 개선이 가능함을 알 수 있다.

그러니 이런 계산 방법은 상당히 매력적인 방법이고, 실제로 많은 구현체에서 활용된다고 한다.

기계에서 버그가 발생하여, 잘못된 값을 계산했다고 하자. 특히, $C_p$와 $C_q$ 중 정확히 한 값이 틀리게 계산되었다고 하자.

일반성을 잃지 않고, $C_p$는 제대로 계산되었으나 $C_q$는 잘못 계산되었다고 하고, 잘못 계산된 값을 $\hat{C_q}$라 하자.

그렇다면 CRT를 통해서 얻어진 $C$의 값은 잘못 계산될 것이며, 이 값을 $\hat{C}$라 하자.

Eve가 $M$을 가지고 와서 기계에게 $M^d \pmod{N}$을 계산해달라고 했는데, 위 오류가 발생했다고 하자.

$\hat{C}^e \not\equiv M \pmod{N}$이 성립하므로, Eve는 오류가 발생했음을 확인할 수 있다.

그런데 $\hat{C}^e \equiv M \pmod{p}$이고, $\hat{C}^e \not\equiv M \pmod{q}$이므로, $\text{gcd}(\hat{C}^e - M, N)$을 계산하면 $N$의 소인수분해를 얻을 수 있다.

공격이 성공하려면 $M$에 대한 정보를 Eve가 들고 있어야 하며, 계산 과정에서 $M$을 바꾸는 일이 없어야 한다.

즉, $M^d \pmod{N}$을 계산하기 전에 $M$에 random bit를 추가하는 등의 방식으로 "랜덤함" 한 스푼을 추가하면 이 공격을 막을 수 있다.

훨씬 간단한 방법으로는, 기계가 값을 출력하기 전에 제대로 계산을 했는지 확인하는 것이 있다. 실수를 했다면, 다시 계산하면 된다.

다양한 암호 체계가 이처럼 기계의 오류를 통해서 깨질 수 있다는 것이 밝혀졌다고 한다. 

마지막으로, Bleichenbacher's Attack on PKCS 1을 살펴본다. 암호학자들이 암호에 대한 빡빡한 기준을 갖는 이유를 알게 해주는 공격이다.

$N$은 $n$-bit RSA modulus고, $M$은 $m$-bit 메시지이며 $m<n$이라 가정하자. 

RSA 암호화를 진행하기 전에, $M$에 random bits를 추가하여 $n$-bit로 만드는 것은 나쁘지 않은 아이디어다.

"랜덤함"으로 간을 쳐주는 나쁘지 않은 방법이 되기 때문이다. 이는 실제로 공개키 암호 표준이었던 PKCS 1에서 사용된 접근이다.

"랜덤함" 간을 친 후, 메시지는 0x00 0x02 [random bits] 0x00 [메시지] 형태를 갖추게 된다. 

앞에 있는 16개의 bit는 랜덤함으로 간을 쳤다는 것을 알리기 위한 신호의 의미를 갖는다. 뒤의 0x00은 여기서부터 진짜 메시지라는 것을 알려주는 신호다.

암호화된 메세지를 Alice의 기계가 받으면, 기계는 이를 decrypt하고 첫 16개의 bit를 확인한다. 그 후, random bits를 전부 제거하여 메시지를 얻는다. 

그런데, 어떤 기계는 첫 16개의 bit가 0x00 0x02가 아닐 때 "invalid ciphertext"라는 에러 메시지를 보내줄 수도 있다.

이 점을 정말 제대로 활용한 것이 Bleichenbacher's Attack이다. 이 에러 메시지로 할 수 있는 게 생각보다 많다.

Eve는 ciphertext $C$가 있고, 이를 복호화하고자 한다. 이를 위해서, Eve는 랜덤한 $r \in \mathbb{Z}_N^{*}$를 하나 잡는다.

그 후, $C' \equiv r^eC \pmod{N}$을 계산하고, $C'$을 Alice의 기계에 보내준다. 

이제 Eve는 에러 메시지의 여부를 통해서 $C'^d \pmod{N}$의 첫 16개의 bit가 0x00 0x02인지 확인할 수 있다.

그러니, 에러 메시지의 존재는 Eve의 입장에서는 일종의 oracle이 된다. 

참 도움이 안 될 것 같은 정보지만, Eve는 이를 활용하여 효율적으로 $C$를 복호화할 수 있음을 보였다. 

Bleichenbacher의 당시 논문에 의하면, 대략 $2^{20}$번의 시행으로 $C$를 복호화할 수 있다고 한다.

이는 adaptive chosen ciphertext attack이 실제로 가능하다는 것을 보여준 대표적인 사례이다. 

즉, 암호학자들이 ACCA까지 보는 게 쓸데없는 일이 아니라는 것이다. (이는 예전에 내가 가졌던 의문에 대한 답이 된다)

#6: Conclusion - Selection of Parameters

앞에서 다룬 공격 외에도, 타원곡선을 이용한 공격, Cycling Attack 등 수많은 공격들이 존재한다. 

위에서 다룬 내용들과, 다루지 않은 공격들을 통하여 우리는 어떤 parameter가 공격에 취약한지 알 수 있었다.

이는 다르게 말하면, 위 내용을 통해서 RSA를 안전하게 사용하기 위해서는 어떻게 parameter를 설정해야 하는지도 알 수 있다는 것이다.

• $N$의 크기는 2048-bit 정도로 큰 것을 사용해야 한다. $N$의 소인수분해가 어려워야 하기 때문이다.
• $p$와 $q$의 크기는 비슷해야 한다. 타원곡선을 이용한 공격을 막아야 하기 때문이다.
• $q-p$는 충분히 커야 한다. $\sqrt{N}$ 근처의 수를 탐색하여 소인수분해하는 것을 막아야 하기 때문이다.
• $p-1$은 큰 소인수를 가져야 한다. Pollard의 $p-1$ 알고리즘을 막아야 하기 때문이다.
• $p+1$은 큰 소인수를 가져야 한다. Williams의 $p+1$ 알고리즘을 막아야 하기 때문이다.
• $r$이 $p-1$의 최대 소인수일 때, $r-1$이 큰 소인수를 가져야 한다. Cycling Attack을 막아야 하기 때문이다.
• $d$는 작으면 안된다. Low Private Exponent에 해당하는 공격을 막아야 하기 때문이다.
• $e$는 작으면 안된다. Low Public Exponent에 해당하는 공격을 막아야 하기 때문이다.
• 일반적으로 사용되는 $e$의 값은 $e = 2^{16} + 1$이다.
• 랜덤한 소수 $p, q$는 높은 확률로 암호학적으로 안전한 소수가 된다고 한다.

다음으로 읽을 논문을 찾아야 하는데, 뭘 읽어야 할지 잘 모르겠다. 일단 수업 내용부터 제대로 따라가야 할 것으로 보인다. 

논문을 읽어가면서 블로그 포스팅을 쓰는거라, 꽤 부족한 점이 많을 것 같다. 많은 지적과 보완은 환영이다.

"Minimalism in Cryptography: The Even-Mansour Scheme Revisited" - Orr Dunkelman, Nathan Keller, Adi Shamir

#1: Introduction

논문의 제목이 보여주듯이, 이 논문의 주제 Even-Mansour Scheme은 가장 단순한 암호화 방법을 고안하는 과정에서 등장한 개념이다. 특히, Even-Mansour Scheme은 가장 단순하고 안전한 블록암호를 고안하는 과정에서 등장했다. 이 논문에서는 Even-Mansour Scheme에 대한 기본적인 내용과 함께, 그의 변형에 대한 공격과 보안성에 대해서 다룬다. 여기서 제시한 공격이 다른 곳에서도 꽤 잘 먹히는듯 하다. 자세한 내용은 후술한다.

#2: The Even-Mansour Scheme

먼저 Even-Mansour Scheme을 정의하고, 기본적인 보안성에 대한 증명과 공격에 대한 내용을 다루어보자.

$n$-bit string에 대한 공개된 permutation $\mathcal{F}$ 하나를 잡는다. 또한, $n$-bit whitening key $K_1, K_2$를 비밀키로 하자. 

이제 $EM_{K_1, K_2}^{\mathcal{F}} (P) = \mathcal{F}(P \oplus K_1) \oplus K_2$로 정의한다. 정말 간단한 암호화 과정이다.

우리가 가정하는 adversary는 다음 두 쿼리를 (다른 말로는, oracle을) 활용해서 공격을 할 수 있다.

adversary는 $E(P) = EM_{K_1, K_2}^{\mathcal{F}} (P)$를 계산할 수 있고, $D(C) = (EM_{K_1, K_2}^{\mathcal{F}})^{-1} (C)$를 계산할 수 있다. 이를 $E$-oracle이라고 한다.

또한, 우리의 adversary는 $\mathcal{F}$-oracle을 불러서, $\mathcal{F}(x)$와 $\mathcal{F}^{-1} (y)$를 계산할 수 있다.

즉, plaintext의 암호화 결과, ciphertext의 복호화 결과를 oracle을 통해서 알 수 있고, $\mathcal{F}$를 이용한 연산도 할 수 있다.

adversary의 목표로 가능한 것은 크게 두 가지로 나뉜다. 첫 번째는 "existential forgery attack"이란 것으로, adversary가 $E(P)=C$가 성립하는 새로운 순서쌍 $(P, C)$를 찾는 것이다. 두 번째는 조금 더 전형적인, 암호화된 메세지 $C$가 주어졌을 때 $E(P)=C$가 성립하는 $P$를 찾는 것이다. 공격의 복잡도는 $E$-oracle의 횟수와 그 종류와 (즉, known/chosen/adaptive chosen) $\mathcal{F}$-oracle의 횟수로 결정된다. $\mathcal{F}$ 자체는 알려져 있지만, $\mathcal{F}$-oracle을 지나치게 많이 활용하면 시간상 문제가 있을 것이다. $E$-oracle은 실제로 뚫어서 얻어내야 하는 것이니, 이 역시 지나치게 많이 쓰기에는 어려움이 있을 것이다. 그러니, 두 oracle의 활용 횟수를 모두 고려하도록 한다. 공격의 성공 확률이란, (첫 번째 경우) 한 번의 시도를 통해서 새로운 $(P, C)$ 순서쌍을 찾거나, (두 번째 경우) $E(P)=C$인 $P$를 찾을 확률으로 정의한다. 이제 본격적으로 보안성과 공격 방식에 대해서 논의할 수 있겠다.

adversary가 $D$번 $E$-oracle을 사용하고, $T$번 $\mathcal{F}$-oracle을 사용했다고 하자. 여기서 $D$는 data의 약자이고, $T$는 time의 약자인 것 같다. 왜 이런 약자를 사용하는지는 꽤 당연한 것 같다. 중요한 사실은, adversary의 성공 확률이 $\mathcal{O}(DT/2^n)$이라는 것이다. 그러니, 기본적으로 공격을 하려면 $DT$가 $\Omega (2^n)$ 정도는 되어야 한다. 여기서 oracle의 총 사용 횟수가 $\Omega(2^{n/2})$ 정도는 되어야 함도 알 수 있다. 증명의 outline을 살펴보자. 

$E$-oracle을 $s$번, $\mathcal{F}$-oracle을 $t$번 활용하면 얻는 것은 $E$-pair와 $\mathcal{F}$-pair의 집합 $S = \{ (P_i, C_i) \}_{i=1,2, \cdots s}$와 $T = \{(X_j, Y_j)\}_{j=1,2, \cdots ,t}$다. 

이제 $K_1$이 $S, T$에 대하여 나쁘다는 것은, $i, j$가 존재하여 $P_i \oplus K_1 = X_j$가 성립한다는 것이다. 그렇지 않다면, $K_1$은 좋다고 하겠다. 비슷하게, $K_2$가 $S, T$에 대하여 나쁘다는 것은, $i, j$가 존재하여 $Y_j \oplus K_2 = C_i$가 성립한다는 것이다. 그렇지 않다면 $K_2$는 좋다고 하겠다. 또한, $K_1, K_2$가 둘 다 좋다면 $(K_1, K_2)$를 $S, T$에 대하여 좋은 쌍이라고 하겠다. 좋은 쌍의 개수는 적어도 $(2^n-st)^2$ 이상이니, $2^{2n} - 2st \cdot 2^n$만큼은 있다. 또한, $(K, \mathcal{F})$가 (물론, $K = (K_1, K_2)$다) $S, T$와 consistent 하다는 것은, $C_i = K_2 \oplus \mathcal{F}(P_i \oplus K_1)$과 $\mathcal{F}(X_j) = Y_j$이 모든 $i, j$에 대하여 성립한다는 것이다. 

Step 1: 비밀키와 permutation에 대한 모든 분포가 uniform하다고 가정했을 때, $(K, \mathcal{F})$가 $S, T$와 consistent하다는 가정에서 $K=k$가 성립할 조건부확률이 모든 $S, T$에 대해 좋은 키 $k \in \{0, 1\}^{2n}$에 대하여 같다는 것을 보인다. 베이즈 정리에서, 이는 $K=k$일 때 $(K, \mathcal{F})$가 $S, T$와 consistent 할 확률이 모든 좋은 키 $k \in \{0, 1\}^{2n}$에 대하여 같음을 보이면 충분하다. $k=(k_1, k_2)$가 좋은 키라고 가정하자. $k$를 고정하고 생각을 하면, $E$-pair의 집합 $S$를 $\mathcal{F}$-pair의 집합 $S'$으로 바꿀 수 있다. $(P_i, C_i)$를 $(P_i \oplus k_1, C_i \oplus k_2)$로 바꿔주면 된다. 또한, $k$가 좋은 키이므로 $S'$과 $T$는 아예 겹치지 않는다. 그러니 consistent 할 확률은 결국 $\mathcal{F}$가 서로 다른 $s+t$개의 pair와 consistent 한 것과 동치이다. 이는 $k$와 무관함이 자명하다. 증명 끝.

Step 2: 성공 확률은 정답에 해당하는 키가 나쁜 키가 되어있을 확률과 정답에 해당하는 키가 좋은 키인 상황에서 adversary가 답을 얻어내는데 성공할 확률의 합 이하임을 증명한다. 이걸 열심히 계산하고 식을 정리하면, 우리가 원하는 결과를 얻을 수 있다고 한다. 논문에서는 뒤에 관련 논의가 사용되지 않는다는 이유로 자세한 설명을 생략했다. Step 2의 내용은 Even-Mansour를 제시한 오리지널 논문에 있다. 이는 나중에 정리해서 올리도록 노력해보겠다.

이 증명을 통해서, 키에 대한 non-trivial information을 얻는 것 역시 $DT = \Omega (2^n)$을 필요로 함을 알 수 있다.

증명 자체가 "좋은 키는 그냥 adversary가 보기엔 다 똑같다"라는 느낌이 강하니까, 직관적으로도 잘 이해되는 부분이다.

이전에 제시된 Even-Mansour에 대한 attack이 간략하게 설명되어 있는데, 간략하게 설명되어 있어서 그런지 이해하기가 조금 어려운 것 같다. 

이 논문에 제시된 공격들이 더욱 강력하므로, 그 공격들만을 우선 읽어보고 다시 돌아와야 할 것 같다.

#3: The Slidex Attack and a Tight Bound on the Security of the Even-Mansour Scheme

우선 기존에 알려진 공격 방법인 Slide with a Twist Attack을 살펴보자. 

만약 두 plaintext $P, P^*$가 $P \oplus P^* = K_1$을 만족한다고 하자. 이제 이를 암호화하면 어떻게 될까?

$E(P) = \mathcal{F}(P \oplus K_1) \oplus K_2 = \mathcal{F}(P^*) \oplus K_2$고, 마찬가지로 $E(P^*) = \mathcal{F}(P) \oplus K_2$가 성립한다.

그러니 결론적으로 $E(P) \oplus \mathcal{F}(P) = E(P^*) \oplus \mathcal{F}(P^*)$를 얻는다. 이제 공격을 설계해보자.

adversary가 이미 알고 있는 plaintext/ciphertext 순서쌍 $(P_i, E(P_i))$을 총 $2^{(n+1)/2}$개 들고 있다고 하자. 

즉, $E$-oracle을 "known" 형태로 이용한다. 이제 $\mathcal{F}$-oracle을 $2^{(n+1)/2}$번 사용하여, $\mathcal{F}(P_i)$를 얻는다. 

커다란 배열을 하나 준비하고, $(E(P_i) \oplus \mathcal{F}(P_i), i)$를 정렬된 형태로 저장한다. 

이제 $E(P_i) \oplus \mathcal{F}(P_i) = E(P_j) \oplus \mathcal{F}(P_j)$인 $i, j$를 효율적으로 찾을 수 있다.

이제, $K_1 = P_i \oplus P_j$, $K_2 = E(P_i) \oplus \mathcal{F}(P_j)$를 계산하고 이를 실제 키로 추측한다.

birthday paradox의 입장으로 생각하면, $P_i \oplus P_j = K_1$이 성립하는 $i, j$가 존재할 확률은 꽤 높다.

또한, 실제로 collision이 일어나는 순서쌍의 개수는 평균적으로 크지 않을 것이라는 점도 직관적으로 이해할 수 있다.

이 공격에서 $D = T = 2^{(n+1)/2}$이고, $DT = 2^{n+1}$이다. 여기서 $DT = \Omega (2^n)$임도 확인할 수 있다.

Slidex Attack은 위 과정을 일부분 변형해서 생각한다. 두 plaintext $P, P^*$가 $P \oplus P^* = K_1 \oplus \Delta$를 만족한다 하자.

이 경우, 식을 전개해보면 $E(P) = \mathcal{F}(P^* \oplus \Delta) \oplus K_2$와 $E(P^*) = \mathcal{F}(P \oplus \Delta) \oplus K_2$를 얻는다.

즉, $E(P) \oplus \mathcal{F}(P \oplus \Delta) = E(P^*) \oplus \mathcal{F}(P^* \oplus \Delta)$를 얻는다.

이제 $d \le n$을 하나 잡고, 다음과 같은 공격을 시도할 수 있겠다.

먼저 이미 알고 있는 plaintext/ciphertext 순서쌍 $(P_i, E(P_i))$를 $2^{(d+1)/2}$개 들고 있다고 하자.

즉, $E$-oracle을 "known" 형태로 이용한다. 이제 $\Delta_1, \Delta_2, \cdots $를 총 $2^{n-d}$개 준비한다.

각 $\Delta_l$에 대하여, $\mathcal{F}$-oracle을 이용하여 $\mathcal{F}(P_i \oplus \Delta_l)$을 각 $i = 1, 2, \cdots , 2^{(d+1)/2}$에 대해 계산한다.

커다란 배열을 하나 준비하고, $(E(P_i) \oplus \mathcal{F}(P_i \oplus \Delta_l) , i)$를 정렬된 형태로 저장한다. 배열은 총 $2^{n-d}$개 있을 것이다. 이 중 아무 곳에서나 collision이 일어나면, 즉 $E(P_i) \oplus F(P_i \oplus \Delta_l) = E(P_j) \oplus F(P_j \oplus \Delta_l)$이면, $K_1 = P_i \oplus P_j \oplus \Delta_l$, $K_2 = E(P_i) \oplus F(P_j \oplus \Delta_l)$을 실제 키로 추측한다.

비슷하게, $P_i \oplus P_j \oplus \Delta_l = K_1$인 $i, j, l$이 있을 확률은 꽤 높다. 

또한, 실제로 collision이 일어나는 순서쌍의 개수는 평균적으로 크지 않을 것이라는 점도 직관적으로 이해할 수 있다.

이 공격에서 $D = 2^{(d+1)/2}$이고, $T = 2^{(d+1)/2} \cdot 2^{n-d}$이다. 그러니 여기서도 $DT = 2^{n+1}$이다.

이 새로운 공격의 장점은 역시 $d \le n$을 마음대로 선택할 수 있다는 점이 되겠다. 

#4: The New Single-Key Even-Mansour Scheme

이제 Even-Mansour Scheme의 변형에 대해서 다룬다. 지금까지는 비밀키가 $K_1, K_2$ 두 개가 있었다. 비밀키를 두 개 사용하지 말고, 그냥 하나의 비밀키를 두 번 사용하면 어떨까? 이 생각으로 등장한게 Single-Key Even-Mansour Scheme이다.

$\mathcal{F}$는 $n$-bit string에 대한 공개된 permutation이고, $K$는 $n$-bit 비밀키다.

이때, $SEM_{K}^{\mathcal{F}} (P) = \mathcal{F}(P \oplus K) \oplus K$라 하자. $K_1 = K_2 = K$라고 보면 되겠다.

공격에 대한 기본적인 정의는 동일하다. 또한, 놀랍게도 보안성에 대한 증명은 기존 Even-Mansour와 동일하다고 한다.

결국, Single-Key Even-Mansour에서도 공격을 제대로 하려면 $DT = \Omega (2^n)$을 필요로 한다고 한다.

그러니, 비밀키로 필요한 bit의 개수를 절반으로 줄이면서 동일한 수준의 보안성을 유지할 수 있다는 결론을 얻는다.

Single-Key Even-Mansour에 대한 공격을 생각해보자. 당연히 위에서 다룬 모든 공격은 여기서 적용된다.

하지만, Single-Key의 경우에는 더욱 간단한 공격 방식이 존재한다. 물론, 복잡도는 여전히 $DT = \Omega (2^n)$이다.

$P$를 plaintext라고 하고, $x = P$, $y = P \oplus K$, $z = \mathcal{F}(P \oplus K)$, $w = E(P) = \mathcal{F}(P \oplus K) \oplus K$라 하자.

여기서 중요한 점은 $x \oplus w = y \oplus z$라는 점이다. 이제 $D \le 2^n$을 아무거나 하나 잡자.

adversary가 이미 plaintext/ciphertext 순서쌍 $(P_i ,E(P_i))$를 $D$개 들고 있다고 하자.

즉, $E$-oracle을 "known" 형태로 이용한다. 이제 배열을 준비하고 $(P_i \oplus E(P_i), i)$를 정렬된 상태로 들고 있는다.

이제 임의의 값 $X_1 , X_2, \cdots X_{2^n/D}$를 잡고, $\mathcal{F}$-oracle을 이용한다. 

각 $j$에 대하여, $X_j \oplus \mathcal{F}(X_j)$를 들고 가서 미리 준비해놓은 배열에서 탐색한다. 

만약 $P_i \oplus E(P_i) = X_j \oplus \mathcal{F}(X_j)$인 $i, j$를 찾았다면 $K = P_i \oplus X_j$를 키로 추측한다.

분석 자체는 Slide with a Twist Attack과 큰 차이가 없으므로, 여기서도 생략한다.

#5: The Security of Other Variants of the Even-Mansour Scheme

첫 번째 variant는 XOR 대신 덧셈을 사용하는 Even-Mansour Scheme이다. 

즉, $AEM_{K_1, K_2}^{\mathcal{F}}(P) = \mathcal{F}(P + K_1) + K_2$다. 여기서 모든 덧셈은 $\pmod{2^n}$으로 한다.

이 variant가 기존 Even-Mansour Scheme 이상의 보안성을 가짐은 같은 방법으로 증명할 수 있다.

즉, 여기서도 성공적인 공격을 위해서는 $DT = \Omega (2^n)$이 기본적으로 필요하다.

앞선 공격들은 은근히 XOR 연산의 성질들을 많이 사용하였다. 대표적으로, $A \oplus B = C$면 $A = B \oplus C$라는 점을 꽤 사용하였다.

하지만 slidex attack에 대하여 조금 더 생각하면 이 variant에 대한 공격도 할 수 있다.

두 plaintext $P, P^*$가 $P + P^* = -K_1 + \Delta$를 만족한다고 하자.

그러면 $E(P) = \mathcal{F}(P + K_1) + K_2 = \mathcal{F}(-P^* + \Delta) + K_2$고, $E(P^*) = \mathcal{F}(-P+\Delta) + K_2$를 얻는다.

즉, $E(P) + \mathcal{F}(-P+\Delta) = E(P^*) + \mathcal{F}(-P^* + \Delta)$를 얻는다.

결국 똑같은 방법으로 배열에 $(E(P_i) + \mathcal{F}(-P_i + \Delta), i)$를 저장하면 된다.

분석과 공격의 자세한 디테일은 역시 위에서 설명한 공격들과 큰 차이가 없으므로, 여기서는 생략한다.

두 번째 variant는 permutation 대신 involution을 사용하는 Even-Mansour Scheme이다.

involution 구조 자체가 암호론에서 꽤 자주 등장하는 구조이니, 이를 Even-Mansour에 적용한 것이다.

$\mathcal{I}$를 $n$-bit string의 집합에 대한 involution 중 하나라 하자. 

이제 $IEM_{K_1, K_2}^{\mathcal{I}} (P) = \mathcal{I}(P \oplus K_1) \oplus K_2$라 정의하자.

involution을 이용하니, $\mathcal{F}$-oracle 대신 $\mathcal{I}$-oracle이라는 이름으로 바꾸어서 논의하겠다.

이 경우, $K_1 \oplus K_2$의 값을 $E$-oracle을 $2^{(n+1)/2}$번 활용하여 얻을 수 있다. $\mathcal{I}$-oracle은 사용하지 않는다.

$E(P) = C$이고 $E(P^*) = C^*$라 하자. 만약 $P \oplus C^* = K_1 \oplus K_2$라면, $P \oplus K_1 = C^* \oplus K_2$가 된다.

또한, $\mathcal{I}$가 involution이므로 $\mathcal{I}(P \oplus K_1) = \mathcal{I}^{-1} (C^* \oplus K_2)$를 얻는다.

그런데 $C = \mathcal{I}(P \oplus K_1) \oplus K_2$이고, $P^* = \mathcal{I}^{-1} (C^* \oplus K_2) \oplus K_1$이다.

그러니 식을 정리하면 $C \oplus K_2 = P^* \oplus K_1$이고, 즉 $P \oplus C = P^* \oplus C^*$를 얻는다.

이제 쉽다. $E$-oracle을 "known" 형태로 $2^{(n+1)/2}$번 사용한 다음, $(E(P_i) \oplus P_i, i)$를 정렬한 상태로 준비하고 collision을 찾기만 하면 된다. 

여기서 $E(P_i) \oplus P_i = E(P_j) \oplus P_j$라면, $P_i \oplus E(P_j) = K_1 \oplus K_2$를 추측하면 된다. 

즉, adversary는 $DT = \Omega (2^n)$을 만족하지 않으면서 non-trivial information을 얻을 수 있다.

즉, 기존 Even-Mansour의 보안성을 가지지 않는 variant임을 알 수 있다. 왜 그럴까?

기존 증명을 생각해보면, 비밀키를 고정했을 때 주어진 input/output 쌍과 consistent 하게 될 확률이 비밀키와 무관함을 이용하여 증명을 했다. 그런데 여기서는 involution 구조가 있어서, $\mathcal{I}(x)=y$라는 정보는 강제로 $\mathcal{I}(y)=x$라는 정보를 추가한다. 이 점을 더 생각해보면, consistent 하게 될 확률이 비밀키에 의해 달라질 수 있음을 알 수 있다. 어떻게 보면, 공격 자체가 이 점을 상당히 활용하고 있음도 알 수 있다.

신기한 점은, involution 구조에 Single-Key Even-Mansour를 덮으면 이런 문제가 없다는 것이다. 다른 말로 하면, involution 구조를 가정하면 Single-Key가 Two-Key보다 보안성이 강력하다는 것이다. 암호화 과정 전체가 involution이 되고, 계산을 조금 해보면 consistent 하게 될 확률이 비밀키에 의해 달라지지 않음을 확인할 수 있다. 정확하게 말하면, 증명에서 등장하는 $S'$과 $T$ 사이의 dependency가 비밀키와 무관함을 알 수 있다. 여러모로 흥미로운 결과가 된다.

추가적인 관찰은, Two-Key로 암호화를 한 상태에서 $K_1 \oplus K_2$의 값이 유출이 되면, 결과적으로 비밀키 하나로 암호화를 한 것과 동일하다는 것이다. 

어쨌든, involution을 활용하고자 할 때 비밀키를 두 개 쓰는 것은 위험하다.

이제 involution 구조에 XOR 대신 덧셈을 사용하면 어떻게 되는지 보자.

동일한 과정을 거쳐서 $K_1 + K_2$를 복원할 수 있다. $C^* - P = K_1 + K_2$를 가정으로 하고 계산하면 된다.

이제 $K_1 + K_2$를 안다는 가정에서, 암호화 과정은 결국 $CISEM(P) = \mathcal{I}(P+K_1) - K_1$과 동일하게 된다.

이는 기존 Even-Mansour과 동일한 보안성을 가짐을 알 수 있다. 공격도 비슷하게 할 수 있다.

한편, involution 구조에 XOR 대신 덧셈을 사용할 때 두 키가 같다면, 즉 $K_1 = K_2$라면, 여기서 $2K_1$을 복원할 수 있다. 

즉, $K_1$을 사실상 (비트 하나 제외하고) 복원할 수 있다. 이건 그냥 암호가 제대로 깨진 것이라고 봐야 한다.

그러니 덧셈을 활용한 Even-Mansour에 single-key variant를 추가하고 싶다면, $CSEM(P) = \mathcal{F}(P+K_1) - K_1$을 이용하는 것이 더욱 보안성 측면에서 좋다. $\mathcal{F}$가 involution인 경우에도 보안성이 입증되어 있기 때문이다.

이 모든 내용을 정리하는 표가 논문의 Table 2로 제시되어 있다. 중요한 표이니, 여기에도 올린다.

#6: Memoryless Attacks on the Even-Mansour Scheme

이제 목표는 메모리를 적게 사용하면서 Even-Mansour를 공격하는 것이다. 지금까지 살펴본 공격들은 배열에 $E$-oracle을 통해서 얻을 값들을 정렬된 상태로 저장한다. 하지만 우리가 $2^{n/2}$ 스케일의 데이터를 저장하기에는 무리가 있다. 그러니 메모리를 절약하면서 Even-Mansour를 공격하는 방법을 다루는 것은 충분한 가치가 있는 일이라고 볼 수 있다. 여기서는 $D, T$가 $\mathcal{O}(2^{n/2})$이면서, 메모리는 상수만큼만 필요한 공격을 제시한다. 

특히, 이는 앞서 제시한 slide with a twist 공격을 변형한 것으로 볼 수 있는 공격 방식이다.

메모리를 절약하는 알고리즘 중 잘 알려진 것은 Floyd의 cycle detection 알고리즘이다. 여기서도 이를 활용한다.

결국 우리는 $E(P) \oplus F(P)$가 겹치는 것을 찾고 싶은 것이니, cycle detection을 활용할 수 있다.

$P_1$을 임의로 잡고, $P_1$에 대한 $E, \mathcal{F}$-oracle을 이용하여 $E(P_1)$, $\mathcal{F}(P_1)$을 계산한다. 이를 통해서 $P_2 = E(P_1) \oplus \mathcal{F}(P_1)$을 계산한다. 이 과정을 총 $\mathcal{O}(2^{n/2})$번 반복하여, $P_1, P_2, \cdots $를 얻는다. 여기에서 Floyd의 cycle detection 알고리즘을 돌리면, $E(P_i) \oplus \mathcal{F}(P_i) = E(P_j) \oplus \mathcal{F}(P_j)$인 $P_i, P_j$를 찾을 수 있고, 여기서 키를 추측할 수 있다. 기본적인 분석은 slide with a twist attack과 동일하다. 여기서 중요한 점은, Floyd의 알고리즘을 이용했기 때문에 메모리는 상수만큼만 필요하며, $E$-oracle을 날리는 $P_i$가 이전 계산 결과에 depend 하기 때문에 여기서는 "known" 형태로 $E$-oracle을 사용하는 것이 아니라, "adaptive chosen" 형태로 $E$-oracle을 사용해야 한다. 조금 더 강력한 oracle을 사용해야 한다고 보면 되겠다.

또한, 여기서는 $E$-oracle을 $\mathcal{O}(2^{n/2})$ 급으로 사용할 수 없는 경우, 확장하기가 어려움을 알 수 있다.

slidex attack은 $E$-oracle의 사용횟수와 $\mathcal{F}$-oracle의 사용 횟수에 대한 tradeoff를 제공하지만, 이를 memoryless 방식으로 확장하기에는 어려움이 있다. 그래서 $D << 2^{n/2}$를 가정한 상태에서 memoryless attack을 하는 방법은 이 논문에서 제시한 하나의 open problem이다. single-key variant에서도 마찬가지로 이를 생각할 수 있다. $D, T$가 $\mathcal{O}(2^{n/2})$이면서 memoryless attack을 하는 것은 어렵지 않으나, $D << 2^{n/2}$를 가정한 상태에서 memoryless attack을 하는 것은 어렵다. 이 역시 하나의 open problem으로 남기면서, 논문의 main text는 끝난다.

#7: The $x^2 \pmod N$ generator is unpredictable.

우선 $P, Q$가 서로 다른 $3 \pmod {4}$ 소수라 하고, $N=PQ$라 하자. 여기서 우리는 $N$과 서로소인 quadratic residue만을 다루겠다. 

$QR_N$을 $N$과 서로소인 $N$의 이차잉여들의 집합이라 하자. $QR_N$의 집합의 크기가 $\phi(N)/4$임은 자명하다. 

간단한 정수론으로, 다음 사실들을 쉽게 증명할 수 있다. 증명은 기초적이므로 생략한다.

Fact 1: 각 quadratic residue는 총 4개의 서로 다른 discrete square root를 가진다.

Fact 2: 4개의 서로 다른 discrete square root 중, 정확히 하나가 quadratic residue가 된다.

Fact 3: 여기서 우리는 $x \rightarrow x^2 \pmod{N}$이 $QR_N$에서 $QR_N$으로 가는 전단사함수임을 알 수 있다.

이제 $x_0 \in QR_N$, $x_{i+1} = x^2_i \pmod{N}$, $b_i = x_i \pmod{2}$라 할 때, 우리가 무엇을 할 수 있는지 생각해보자.

Fact 1: $N$을 알고, $x_0$를 알면, 빠르게 $x_1, x_2, \cdots $와 $b_1, b_2, \cdots$를 계산할 수 있다. 자명하다.

Fact 2: $N$의 소인수분해를 알고 $x_k$를 알면, 빠르게 $x_{k-1}, x_{k-2}, \cdots$와 $b_k , b_{k-1}, \cdots$를 알 수 있다.

이는 discrete square root를 계산하는 것이 어렵지 않기 때문이다. Tonelli-Shanks를 생각해도 되고, 애초에 $3 \pmod{4}$ 소수를 다루니 그냥 단순하게 계산할 수도 있다. 이제 CRT를 덮어주면 계산을 다항식 시간에 충분히 할 수 있을 것이다. 어렵지 않은 이야기.

Fact 3: $x_k$를 알 때 $x_{k-1}, x_{k-2} , \cdots$를 계산하는 것은 $N$의 소인수분해를 찾는 것 이상으로 어렵다. 

강력한 사실이다. 이걸 보이기 위해서는, $x_k$를 알 때 $x_{k-1}$을 쉽게 계산할 수 있다면 $N$의 소인수분해 역시 쉽게 계산할 수 있음을 보이면 충분하다. $N$에 대한 Jacobi Symbol의 값이 $-1$인 $x$를 하나 잡고, $y \equiv x^2 \pmod {N}$을 생각하자. 이제 $y$를 기준으로 역추적을 하면, $x'^2 \equiv y \pmod{N}$인 이차잉여 $x'$을 얻을 수 있을 것이다. 이제 $x'+x$와 $N$ 사이의 최대공약수를 찾아서 $N$을 소인수분해할 수 있다.

그런데 사실 우리의 진짜 목표는 $x_i$들이 아니라 그들의 parity인 $b_i$들이다. 

$x_i$라는 정보들이 우리에게 $b_i$를 역추적/예측을 하는데 있어서 얼마나 도움을 줄까? 이를 엄밀하게 정의할 필요가 있다.

다항식 $f$를 고정하고, $0 < \epsilon \le 1/2$인 실수 $\epsilon$를 고정하자. 다항시간에 작동하는 확률적 알고리즘이 $N$에 대하여 $x_0 \in QR_N$가 주어졌을 때 $x_{-1}$의 parity를 guessing 하는데 $\epsilon$-advantage가 있다는 것은, $\frac{\sum_{x_0 \in QR_N} P(\text{correct})}{\phi(N)/4} \ge \frac{1}{2} + \epsilon$이라는 것이다. 여기서 $P(\text{correct})$란, $x_0$가 input으로 주어졌을 때 $x_{-1}$의 parity를 성공적으로 출력할 확률이다. 비슷한 방식으로, $x_0$가 주어졌을 때 $x_0$가 quadratic residue인지 guessing 하는데 $\epsilon$-advantage가 있다는 것이 무엇인지를 정의할 수 있다. 여기서 주의할 점이 있는데, Jacobi Symbol을 활용하여 이차잉여가 아닌 값들 일부를 다항시간에 분류할 수 있다. quadratic residue에 대한 $\epsilon$-advantage를 정의할 때는, Jacobi Symbol의 값이 $1$인 원소가 주어졌을 때 이 값이 quadratic residue인지 판별하는 문제를 생각한다. 당연하지만, Jacobi Symbol이 $1$인 원소 중 정확히 절반이 quadratic residue다. 그러니 위 정의와 비슷한 정의를 그대로 가져다가 쓸 수 있겠다. 분모만 $\phi(N)/2$로 바꾸면 된다.

이제 다음을 순서대로 증명한다. 아이디어가 확실히 느낌 있다.

Step 1: $\epsilon$-advantage for guessing parity can be converted to $\epsilon$-advantage for guessing quadratic residuosity

Step 2: $\epsilon$-advantage for guessing QR can be amplified to a $1/2-\epsilon$-advantage for guessing QR

이 시점에서 우리는 $\epsilon$-advantage가 있다면 QRP의 난이도에 대한 우리의 가정에 모순이 발생함을 얻는다.

즉, $N$의 소인수분해를 모르는 시점에서 우리는 $\epsilon$-advantage 조차 얻을 수 없다. 그냥 동전 던지라는 거다.

Step 1: $x$가 Jacobi Symbol $1$을 갖는 원소라고 하자. 우리의 목표는 $x$가 quadratic residue인지 판별하는 것이다.

$x_0 = x^2 \pmod{N}$이라 하면, $x_0$의 discrete square root 중 Jacobi Symbol $1$을 갖는 것은 $x$와 $N-x$다. 

$N$이 홀수이므로, 두 값은 다른 parity를 갖는다. 그러니 parity를 잘 찍는 것과 quadratic residue를 잘 찍는 것은 동치다.

Step 2: 통계학에 가깝다. 그냥 테스트를 반복해서 적용하면 된다. 실제로 서술하는 것은 꽤 까다로울 듯.

내 이해가 맞다면 Step 2가 없어도 어쨌든 QRP의 난이도에 대한 가정에 모순이 발생할 것이다. 

이제 $x_0$ 하나를 가지고 $x_{-1}$의 parity를 보는 것에 대한 논의가 끝났다. 이제 진짜 우리가 다루고자 하는 것을 보자.

$b_1, b_2, b_3, \cdots b_k$를 알고 있을 때, $b_0$를 높은 확률로 결정할 수 있을까? 다시 엄밀하게 정의를 하자.

Predictor $P$는 $N$과 $b_1b_2 \cdots b_k$를 (단, $k$는 $|N|$에 대한 다항식에 bound 된다) 입력 받아서, $0$ 또는 $1$을 출력하는 확률적 알고리즘이다. $P$가 $\epsilon$-advantage가 있다는 것은, 적당한 $k \le \operatorname{poly}(|N|)$이 있어 $x \in QR_N$에 대하여 $b_i(x)$를 $x^{2^i} \pmod {N}$의 parity라 할 때, $b_1(x), b_2(x), \cdots b_k(x)$와 $N$을 input으로 받아서 predictor가 $b_0(x)$를 출력할 평균적인 확률이 (모든 $x$를 고려했을 때) $\frac{1}{2} + \epsilon$ 이상이라는 것이다. 

말이 많지만, 어쨌든 위에서 다룬 $\epsilon$-advantage와 큰 그림의 차이는 없다. 목표는 역시 $\epsilon$-advantage가 없다는 것이다.

증명은 어렵지 않다. $x_0 \in QR_N$을 잡은 다음 $x_0x_1 \cdots x_k$를 predictor에게 주자.

그러면 이 predictor는 $x_{-1}$의 parity를 줘야 하는데, 이건 앞에서 불가능하다고 설명했다.

직관적으로도 크게 받아들이기 힘든 내용은 아니라고 생각한다. $x$와 $x^2 \pmod{N}$ 사이의 one-way 느낌을 잘 써먹는 것 같다.

next-bit test를 통과하면 모든 polynomial statistical test를 통과함이 잘 알려져 있다. 

여기서는 증명까지 제시하는 것 같은데, 통계학이 꽤 필요한 것 같아서 잠시 남긴다. 직관적으로 이해 불가능하지는 않은듯.

생각을 해보면, 우리는 $x^2 \pmod{N}$에서 (가장 작은) 비트 하나씩을 PRNG에 써먹고 있다.

비트를 여러 개 PRNG에 넣는 것은 어떨까? 그러면 효율은 꽤 좋아질 것이다. 이 질문은 2005년에 답이 나온 것 같다.

일단 결론만 말하자면, $\mathcal{O}(\log \log N)$개의 비트까지는 뽑아도 된다고 한다. 얘는 나중에 읽는 걸로.

가뜩이나 비효율적인 알고리즘으로 평가받는 Blum-Blum-Shub의 성능을 조금이나마 높일 수 있는 좋은 질문거리다.

#8: Lengths of periods of sequences produced by the $x^2 \pmod N$ generator

이제 이 generator를 제대로 써먹으려면 실제로 어떤 성질을 가지는 수열이 생성되는지 탐구할 필요가 있다.

일단 처음으로 볼 내용은 역시 주기성이다. 주기의 길이가 길었으면 좋겠는게 우리의 마음이니, 이를 위해서 $P, Q, x_0$를 어떻게 잡으면 좋을지 생각해보자.

(주기가 있는 점은 자명한 것이, $x \rightarrow x^2$이 $QR_N$에서 $QR_N$으로 가는 전단사함수다)

$x_0 \in QR_N$에 대하여, $\pi (x_0)$을 수열 $x_i = x^{2^i}_0 \pmod N$의 주기라고 정의하자.

$\lambda$를 Carmichael의 $\lambda$ 함수라 하자. 처음으로 보일 사실은 $\pi (x_0) | \lambda ( \lambda (N))$이다.

증명 (Sketch): 먼저 $\operatorname{ord}_N x$를 $x$의 $\pmod{N}$에서의 order라고 정의하자.

$x \in QR_N$이면 $\operatorname{ord}_N x$는 홀수임을 보인다. 그러니 $2^{\lambda (\operatorname{ord}_N x_0)} \equiv 1 \pmod{ \operatorname{ord}_N x_0}$다.

한편, $\pi (x_0)$는 $2^{\pi (x_0)} \equiv 1 \pmod{ \operatorname{ord}_N x_0}$를 만족하는 최소의 자연수다. 그러니 $\pi (x_0) | \lambda (\operatorname{ord}_N x_0)$를 만족해야 하고, $\operatorname{ord}_N x_0 | \lambda(N)$이다.

$a|b$면 $\lambda (a) | \lambda (b)$가 성립한다. 그러므로 $\pi (x_0) | \lambda (\lambda (N))$을 얻고 증명 종료.

전부 Carmichael 함수와 order에 대한 기초적 지식이 있으면 쉽게 증명할 수 있는 사실들이다.

자연스럽게 우리의 목표는 주기를 $\lambda ( \lambda (N))$로 만들고, 이 값을 크게 하는 것이다. 가능하다.

$N$을 잡되, $\operatorname{ord}_{\lambda(N)/2} (2) = \lambda ( \lambda(N))$이 성립하도록 한다.

$x_0 \in QR_N$을 잡되, $\operatorname{ord}_N (x_0) = \lambda(N)/2$가 성립하도록 한다. 이때 $\lambda (\lambda( N)) = \pi (x_0)$가 성립한다.

증명 (Sketch): 위의 증명을 따라가면 큰 차이없이 증명을 할 수 있다.

$\pi (x_0)$는 $2^{\pi (x_0)} \equiv 1 \pmod {\operatorname{ord}_N (x_0)}$를 만족하는 최소의 자연수다.

그런데 $\operatorname{ord}_N (x_0) = \lambda(N)/2$가 성립한다. 

그러니 $\pi (x_0) = \operatorname{ord}_{\lambda(N)/2} (2) = \lambda (\lambda (N))$이 성립해 증명이 끝난다.

문제는 저런 $N$과 $x_0$를 잘 잡을 수 있겠냐는 것이다. 이것 역시 가능하다. 먼저 $N$에 대한 논의를 하자.

소수 $P$가 좋다는 것은, $P = 2P_1+1$, $P_1 = 2P_2 + 1$이라 썼을 때 $P_1, P_2$ 역시 홀수 소수라는 것이다.

$N = PQ$가 좋다는 것은, $P, Q$가 서로 다른 홀수 소수고 $P, Q$가 모두 좋은 소수라는 것이다.

$N = PQ$가 좋은 수고, $2$가 $P_1$, $Q_1$ 중 최대 하나의 이차잉여일 때, $\operatorname{ord}_{\lambda(N)/2} (2) = \lambda ( \lambda (N))$이 된다.

증명 (Sktech): 역시 어렵지 않다. 우선 $\lambda (N) = 2 P_1 Q_1$이므로, $\lambda(N)/2 = P_1 Q_1$이다.

이제 $\operatorname{ord}_{P_1 Q_1} (2)$를 봐야하는데, 이는 $\operatorname{ord}_{P_1} (2)$와 $\operatorname{ord}_{Q_1} (2)$의 최소공배수다. 

$\operatorname{ord}_{P_1} (2)$는 $P_2$거나 $2P_2$임이 자명하다. 정확하게는, $2$가 $P_1$의 이차잉여라면 $P_2$고 아니면 $2P_2$다.

마찬가지로, $\operatorname{ord}_{Q_1}(2)$는 $Q_2$거나 $2Q_2$임이 자명하다. 정확하게는, $2$가 $Q_1$의 이차잉여라면 $Q_2$이고 아니면 $2Q_2$이다.

그러니 $2$가 $P_1$, $Q_1$ 중 최대 하나의 이차잉여라면, 두 $\operatorname{ord}$ 값의 최소공배수는 $2P_2Q_2$가 된다.

그런데 $\lambda ( \lambda (N)) = \lambda (2P_1Q_1) = 2P_2Q_2$가 되므로 증명이 끝난다. 

이런 $N$이 무한함을 증명하는 것은 어려운 일이지만, 우리는 어쨌든 저 조건을 만족하는 $N$을 찾기만 하면 된다.

또한, 이러한 $N$을 확률적 알고리즘으로 다항시간에 찾는 것은 충분히 가능하다고 생각하는 것이 reasonable하다. 

대충 $P, P_1, P_2$가 소수인 사건이 독립적이라는 가정을 하고 생각을 하면 될 것이다.

이제 $x_0$에 대한 논의를 하자. 얘는 어렵지 않다. 위수 $\lambda (N)$을 갖는 원소를 찾은 뒤 이를 제곱하면 된다.

위수가 $\lambda (N)$인 원소를 찾으려면, $P, Q$ 각각에 대한 원시근을 잡은 뒤 CRT를 사용하면 된다.

$P, Q$의 원시근의 개수는 각각 $\phi (P-1)$, $\phi(Q-1)$이고 이들은 상당히 큰 수들이다. 

예를 들어, $\phi (x) > \frac{x}{6 \log \log x}$임이 알려져 있다. 그러니 이를 통해서 $x_0$를 잡는 것이 어렵지 않음을 알 수 있다.

애초에 위 방식대로 $N$을 구축한다면, 원시근 여부를 판정하는 것도 빠르게 할 수 있다. 이미 $P-1$, $Q-1$의 소인수분해를 알기 때문이다.

그러니 $x_0$도 적당히 잡을 수 있고, 우리는 매우 큰 주기를 갖도록 수열을 생성할 수 있다. 

이제 문제는 우리가 실제로 써먹는 값은 parity이므로, 실제 주기를 알려면 $b_0, b_1, \cdots $의 주기와 $x_0 , x_1 , \cdots$의 주기 사이의 관계를 알아야 한다는 것이다. 

하지만 이 부분은 이 논문에서는 open problem으로 나와있다. 아직 관련 문헌은 찾지 못했다.

#9: Algorithms for determining length of period and random accessing

주기에 대한 이야기를 계속한다. 여기서 우리의 목적은 $x_0$가 주어졌을 때 $\pi (x_0)$를 계산하고, $x_i$를 효율적으로 계산하는 것이다.

여기서는 $N = P \cdot Q$이고, $P, Q$는 서로 다른 $3 \pmod {4}$ 소수라고 가정한다.

$N, \lambda (N) , \lambda (\lambda (N))$과 $\lambda ( \lambda (N))$의 소인수분해를 안다면, $\pi (x_0)$를 효율적으로 계산할 수 있다.

위수를 빠르게 계산하는 일반적인 방법을 그대로 적용할 수 있기 때문이다. 

정확하게 말하자면, $(x_0)^{2^{\lambda (\lambda(N))/d} \pmod {\lambda(N)}} \pmod {N} \equiv x_0 \pmod{N}$인 최대의 $d| \lambda (\lambda(N))$을 찾으면 된다.

$\lambda (\lambda(N))$의 소인수분해를 알고 있으니, 소인수를 하나씩 지워보는 방식으로 빠르게 $d$를 찾을 수 있다.

또한, $N, \lambda (N)$을 알면 $x_i$ 역시 binary exponentiation을 활용하여 빠르게 계산할 수 있다. 이는 자명하다.

또한, $N, \lambda (N)$을 알면 $x_{-i}$ 역시 빠르게 계산할 수 있다. $N$을 소인수분해할 수 있다면, 답을 $P, Q$에 대해서 각각 계산한 뒤 이를 CRT로 합치면 된다. 

각 소인수에 대해서 답을 계산하는 것은 $\pm x^{(P+1)/4}$가 $x$의 discrete square root임을 이용하면 계산할 수 있다. 

이제 $N$을 소인수분해하는 것이 문제가 된다. 이는 Miller-Rabin이 탄생한 논문에서 그 방식이 설명되어 있다. 

먼저 $a$의 Jacobi Symbol 값이 $-1$인 $1 < a < N$을 하나 잡자. 

그러면 $a$가 $P ,Q$ 중 하나에 대해서는 이차잉여고, 하나에 대해서는 비이차잉여가 된다.

이제 $a^{\lambda(N)/2}$를 계산해보자. 이는 $a$가 $P$의 이차잉여면 $1 \pmod {P}$고, 비이차잉여면 $-1 \pmod {P}$다.

마찬가지로, $a$가 $Q$의 이차잉여면 $1 \pmod {Q}$고, 비이차잉여면 $-1 \pmod {Q}$다. 이제 끝났다.

단순히 $a^{\lambda(N)/2} - 1 \pmod {N}$과 $N$ 사이의 최대공약수를 취하면 된다. 이는 $\lambda (N)$을 알고 있으니 할 수 있다.

반대로, $x_0$에 대해서 $\pi (x_0)$를 알려주고, 각 $i$에 대해 $x_i$를 효율적으로 계산해주는 oracle이 있다면, $N$을 소인수분해 할 수 있다. 

Jacobi Symbol 값이 $-1$인 $y$를 하나 랜덤하게 찾자. 이제 $x_0 = y^2 \pmod{N}$을 잡자.

oracle을 불러서, $\pi (x_0)$의 값을 계산하자. 그 후, 다시 oracle을 불러서 $z = x_{\pi(x_0) - 1}$를 계산하자.

이는 $z^2 \equiv x_0 \pmod {N}$을 만족함이 자명하다. 또한, $z \in QR_N$임 역시 자명하다.

그러니 $y+z$와 $N$의 최대공약수를 취하면 $P$ 또는 $Q$가 계산된다. 증명 끝. 아이디어 참 좋다.

#10: Applications

우선 $1/P$ generator의 쓸모를 보자. de Bruijn sequence를 생성했다는 점도 꽤 흥미로운 점임은 분명하다.

논문에서는 길이 $2|P|_b+1$의 부분수열로는 $P$를 복원할 수 있으나, 길이 $|P|_b-1$의 부분수열로는 $P$에 대한 아무런 정보를 얻지 못한다는 점에 집중했다.

길이 $2|P|_b+1$의 부분수열을 반으로 쪼개서 두 사람에게 주면, 각 사람은 $P$를 복원할 수 없으나 협력하면 $P$를 복원할 수 있다.

이 점은 꽤 암호학적으로 쓸모가 있는 것 같다. shift-register sequence과도 큰 관계가 있다고 한다.

LCG와는 분명히 관계가 있을 것 같은데 LFSR이 등장하는 배경은 잘 모르겠다. 이건 물어봐야 할 듯.

$x^2 \pmod N$ generator는 공개키 암호에 사용할 수 있다. Encryption/Decryption Scheme을 다음과 같이 생각해보자.

Alice는 $N_A = P_A \cdot Q_A$를 공개키로 설정한다. 단, $P_A, Q_A$는 서로 다른 $3 \pmod {4}$ 소수이며, $|P_A| = |Q_A|$다.

물론, Alice는 $P_A$와 $Q_A$ 자체는 비밀로 한다. 이제 Bob은 $k$-bit 메세지 $(m_1, m_2, \cdots , m_k)$를 Alice에게 보내고 싶다.

단, $k$는 $|N_A|$에 대한 다항식에 bound 된다. 이제 Encryption을 위해서, Bob은 공개키 $N_A$를 활용한 one-time pad를 구축한다.

$x_1 \in QR_{N_A}$를 하나 뽑고 (원소 하나 잡고 제곱하면 된다) $(N_A, x_1)$을 seed로 하는 $x^2 \pmod N$ generator를 이용하여, $b_1, b_2, \cdots b_k$를 생성한다.

이제 Bob은 $(m_1 \oplus b_1, m_2 \oplus b_2, \cdots m_k \oplus b_k)$와 함께 $x_{k+1}$의 값을 Alice에게 보낸다.

Alice는 $N_A$의 소인수분해를 들고 있으니, $x_{k+1}$을 기반으로 $x_1, x_2, \cdots x_k$를 계산할 수 있다.

이를 이용하여 $b_1, b_2, \cdots b_k$를 계산하고, 다시 원래 메세지인 $(m_1, m_2, \cdots m_k)$를 얻는다.

이 복원과정을 하려면 $N$의 소인수분해를 들고 있어야 함은 앞서 한 QRP의 난이도에 대한 가정에 의해 성립한다.

실제로, $N_A$의 소인수분해를 모르는 사람이 $b_1, b_2, \cdots b_k$ 중 하나의 비트를 정확하게 guess 하는데 $\epsilon$-advantage가 있다고 하자.

그러면 이를 활용하여 QRP에 대한 $\epsilon$-advantage를 얻을 수 있다. 아이디어는 위에서 다룬 것과 비슷하다. 

Jacobi Symbol의 값이 $1$인 $x$를 하나 잡자. $1 \le l \le k$를 하나 랜덤하게 잡고, $x_{l+1} = x^2 \pmod {N_A}$이라 하자.

이를 기반으로, $x_{k+1}$까지 계산을 하자. 그 후, $N_A$과 $x_{k+1}$을 주고 비트 하나를 $\epsilon$-advantage를 가지고 guess 하게 하자. 

그러면 $l$번째 bit에 대한 parity를 줄 확률이 $1/k$가 된다. 실제로 $l$번째 bit를 guess 할 때까지 계속 이 과정을 반복하자.

이제 $l$번째 bit를 guess 했다고 하자. 만약 $l$번째 bit가 $x$의 parity와 같다면 $x$가 이차잉여라고 답하면 된다. 

아니면 $x$가 비이차잉여라고 답하면 된다. 이제 이를 통해서 QRP 문제에 대한 $\epsilon$-advantage를 얻을 수 있다. 증명 끝.

그러니 QRP의 난이도에 대한 가정이 참이라면, 이 Encryption은 상당히 안전하다.

$x^2 \pmod N$ generator를 이용하여 randomness를 amplify하는 접근도 소개하고 있다.

또한, 짧은 시드로 매우 긴 random sequence를 제작할 수 있다는 면에서 강점이 있다고 한다.

확실히 아는 게 많을수록 다루기 쉬운 sequence라는 점에서 좋은 점이 많은 것 같다.

애초에 이 논문을 읽은 목적이 blum-blum-shub PRNG를 깨는게 소인수분해만큼 어렵다는 증명을 배우기 위해서였다.

QRP 문제는 매우 어렵다고 여겨지지만, 소인수분해만큼 어려운지는 아직 알려지지 않았다고 한다.

실제로 이 증명을 보려면 후속 논문을 읽어야 할 것 같다. 일단 다음에 읽고 싶은 논문은 RSA에 대한 review paper와, Even-Mansour Scheme에 대한 논문이다.

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

"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의 모든 것을 파악하고 예측할 수 있다. 약하다.