Coppersmith Method - RSA

 

 

이번에는 RSA 하면 빼놓을 수 없는 사람, Coppeersmith 에 대해서 설명해보고자 한다. 암호학을 공부한 지 얼마 되지 않았지만, Coppersmith 는 정말 천재가 분명할 정도로 암호학에 큰 기여를 했다고 생각한다. 그 중에서도 오늘은 암호학의 혁신 중 하나였던 Coppersmith Method 에 대해서 포스팅해보려고 한다.

😍 Coppersmith Method 😍

Background

Coppersmith Method 은 Modulus 상에 존재하는 다항식의 근을 구할 수 있도록 해주는 알고리즘이다.

$x^2 + x + 1 = 0$ 이라는 방정식을 한번 생각해보자. 조금만 생각해 봐도 어렵지 않게 근의 공식 등을 이용해서 근을 구해낼 수 있다. 하지만, 이 방정식에 Modulus 계산이 추가되면, 아예 결이 다른 문제로 변질되게 된다. 

간단하게 $x^3 + x + 1 = 0 (\text{mod 112383})$ 이라는 방정식을 생각해봐도 쉽사리 문제가 풀리지 않는다는 것을 알 수 있다. 그런데 Coppersmith 는 이 방식을 수학적 기술로 가능하게 만든 것이다. 

 

그럼 Coppersmith 는 어떻게 modulus 상에서의 다항식 근을 구할 수 있었을까??

How

앞선 설명에서, modulus 가 있는 방정식과 비교해서, modulus 가 없는 방정식이 상대적으로 매우 쉽게 풀 수 있다고 했다. Coppersmith 도 이 아이디어에 착안하여 modulus 가 존재하는 방정식에서 modulus 를 없애는 방식을 Base 로 하여 Copphersmith Method 를 고안해내었다. $$ C = m^e \text{ (mod N)}$$

 

위는 전형적인 RSA 암호에서 쓰이는 암호화 과정이다. $m$ 이 plaintext, $C$ 가 ciphertext 가 되는 방정식이다. 의도대로라면, N 의 factorization 은 시간상 불가능하기 때문에 쉽게 $m$ 을 복원해낼 수 없다. 

 

하지만, $m < N^{1/e}$ 라는 조건이 있다면 어떻게 될까? $m^e < N$ 과 동치가 되기 때문에, $C = m^e$라고도 표현할 수 있을 것이다. (나머지가 생기지 않기 때문) 따라서 modulus 가 제거되어 정수집합 내에서의 방정식이라고 치환할 수 있게 된다. 

 

이에 착안하여 다시 Coppersmith Method 를 보도록 하자. Coppersmith Method 를 식으로 표현하면 다음과 같다. 

$$f(x) = 0 \text{ (mod a)}$$그럼, $|f(x_0)| < a $ 인 $x_0$ 들의 경우에는, $f(x_0) = 0$ 이라는 정수집합 방정식으로 치환할 수 있다. 하지만, $|f(x_0)| < a$ 라는 조건은 실전에서 사용하기가 매우 어렵다. 따라서 이를 $x$ 에 관한 조건으로 바꾸는 작업이 필요하다!! 

 

이제부터 본격적인 수학 이야기가 등장한다.

Howgrave-Graham Theorem

이 이론은 $f(x) = 0 \text{ (mod a) }$ 를 $f(x) = 0$ 으로 바꾸어줄 수 있게 하는 이론이다. 먼저, 이 이론에 대해서 설명하기 전에, 몇가지 정의들을 내리고 접근해보자. 

1. 함수 $f$ 의 계수들을 가지고 vector 로 나타낸 것을 coefficient vector 이라고 한다. $[ a_0, a_1, \cdots, a_k ]$ 이라고 표현할 수 있겠다. 

2. 함수 $f$ 의 노름 (norm) 을 coefficient vector 의 norm 으로 정의한다. 즉, $||f||^2 = \sum a_i^2$ 이다.

자, 이제 Howgrave-Graham 이론의 조건에 대해서 이야기해보도록 하자. 

 

1. 어떤 $X$ 에 대해서, $|x_0| < X$ 를 만족하는 $x_0$ 는 $f(x_0) = 0 \text{ (mod a)} $이다.

 

2. $||f(xX)|| < \frac{a}{\sqrt{n}}$ 를 만족한다. 

 

이 두 조건을 만족하게 되면, 정수 집합 내에서 $f(x_0) = 0$ 을 만족하게 된다. 

 

증명은 생략하려고 했지만, 앞서서 수학 이야기가 펼쳐질 것이라고 해놓고 생략하면 너무 멋이 없어서 결국 포스팅하기로 결정했다. 수식이 계속 이어질 것이니 잘 이해해보자. 

 

- WITH 코시 슈바르츠 부등식 

 

$\left ( \sum |c_i|X^i \right )^2 \leq \left ( \sum \left ( c_iX^i \right )^2  \right ) \times \left ( \sum 1 \right ) = ||f(xX)||^2 \times n$ 로 식을 적을 수 있게 된다. (여기서 각 항의 계수들은 $c_i$ 로 적었다)

 

여기서 양변에 제곱근을 취해주면 $ \left ( \sum |c_i|X^i \right ) \leq ||f(xX)|| \times \sqrt{n}$ 로 변화시킬 수 있다. 

 

따라서 처음부터 식을 적어보면 $|f(x_0)| = \sum c_ix_0^i \leq \sum |c_ix_0^i| \leq \sum |c_i|x_0^i \leq \sqrt{n} \times ||f(xX)|| < a$ 로 식을 정의할 수 있다.

 

따라서 $|f(x_0)| < a$ 라는 결과가 도출되게 된다. (앞서 정의했던 2번째 조건에 의해)

 

modulus 였던 $a$ 보다 작은 함숫값이 형성되기 때문에, 어떤 $X$ 보다 작은 $x_0$ 은 modulus 를 제거한 하나의 정수 집합에서의 방정식으로 표현할 수 있게 되는 것이다. 

 

자, 이제 Coppersmith Method 를 사용하기 위한 Lemma 들은 모두 설명했다. ( 사실 LLL algorithm 이 남긴 했지만 이 부분은 생략하는 것이 블로그의 목적에 더 알맞을 것 같다. 궁금한 사람들은 RBTree 님의 블로그에 들어가서 보고 오자.)

 

그럼 전체적인 Coppersmith Method 에 대해서 설명해보도록 하자. 

Coppersmith Method

전체적인 Coppersmith Method 의 흐름을 보여주기 위해서 예시로 우리가 풀고 싶은 하나의 방정식을 정의해보자. $f_a(x) \equiv 0 \text{ (mod a)}$ 라는 방정식을 풀고 싶다고 할 때, 과연 우리는 어떻게 앞선 Lemma 를 적용시킬 수 있을까?

 

여기서 LLL 알고리즘의 아름다움이 나오게 된다. LLL 알고리즘을 통해서 $f_a(x)$ 와 $\text{mod a} $ 를 $f(x)$ 와 $\text{mod }a^m$ 으로 변형시킬 수 있다!! 그러면서 자연스럽게 modulus 의 크기를 늘려줌으로써 Howgrave - Graham 이론의 조건을 완화시킬 수 있게 된다. 

 

출처 :&nbsp;https://rbtree.blog/posts/2020-03-10-coppersmiths-method/Coppersmith.pdf

끝이라기엔 정작 Coppersmith Method 가 주된 포스팅 주제였는데, 배보다 배꼽이 더 큰 포스팅이 되어버릴까봐 간략하게만 어떻게 LLL 알고리즘을 사용하는지 적어보도록 하겠다.

소인수를 알 수 없는 N 이 있고, N 의 약수인  b 가 존재한다고 가정하자. 가장 보편적으로 나오게 되는 RSA 암호의 형식이기 때문에 이렇게 가정해보도록 하자. 

$g_{i,j}(x) = N^{m-i}x^jf_b^i(x)$ 로 함수 $g$ 를 정의할 수 있다. 여기서 함수 $g$ 의 최고차항은 $N^{m-i} \times X^{\delta i + j}$ 로 표현할 수 있을 것이다. ( 함수 $f_b$ 의 차수는 $\delta$ 이다.) 

잘 생각해보면, $f_b(x) = 0 \text{ (mod b)}$ 라는 방정식을 만족하는 하나의 근 $x_0$ 에 대해서, 함수 $g$ 를 바라보게 되면, $g(x) = 0 \text{ (mod }b^m ) $ 을 만족한다는 사실 또한 알 수 있을 것이다. 따라서 이 $g$ 들로 이루어진 방정식 또한 modulus 상의 계산을 만족하는 것을 알 수 있다. 

여기서 LLL 알고리즘을 사용하여, 정의했던 함수인 $g$ 들로 이루어진 vector 들을 LLL 알고리즘으로 돌려, 가장 작은 벡터를 찾게 되면 여러 $\beta,  \delta,  \epsilon $ 등의 변수들을 조건삼아서 $X = \frac{1}{2} N^{\frac{\beta^2}{\delta}-\epsilon}$ 으로 정의할 수 있다. ($b > N^{\beta}$)

따라서, 여러 변수들을 조건에 맞체 잡아주기만 한다면, Coppersmith Method 를 사용하여, 방정식을 상대적으로 쉽게 풀어낼 수 있다. 

Practice

그럼 직접 코드를 보면서 실제로는 어떤 식으로 쓰일 수 있는지 보도록 하자. 이번 공부를 하면서 RBTree 님의 블로그를 1000번 정도 들어간 것 같고, 많고 다양한 사이트들에 대한 정보도 얻으며 비슷한 (거의 동일한) 문제를 제작해보았다. 

tiny roots

그럼, 코드를 살펴보도록 하자.

from Crypto.Util.number import *

p = getPrime(1024)
q = getPrime(1024)
assert p > q

n = p * q
e = getPrime(128)

beta = 0.4
epsilon = beta ** 2 / 7

upper_bound = p.bit_length()
lower_bound = int(n.bit_length() * (beta ** 2 - epsilon))

MSB = p & (pow(2,upper_bound) - pow(2,lower_bound))

# encryption
ciphertext = pow(FLAG,e,n)

print(f'Here is the flag : {ciphertext}\n')
print(f'I don\'t know the secret key... except some bits of p...\n{MSB}\n')
print(f'But I know the public key !! Can You make it??\n({n},{e})')

마지막 부분을 보면, upper bound 와 lower bound 를 설정해서 p 와 and 연산을 진행한다. 이 뜻은 lower bound 부터 upper bound 에 해당하는 비트들만을 남긴다는 뜻이 되기 때문에, lower bound 아래부터는 알 수 없는 비트들이 이어지게 될 것이다.

 

p 에 대한 parity bits 들을 출력해주었기 때문에, 문제의 의도는 아마도 p 의 일부분을 가지고 n 을 소인수분해하여 기본적인 RSA 암호를 파괴하라는 것이 아닐까 싶다. (푸핫)

 

이 문제에서는 정확히 $X$ 의 값을 계산했다. N 의 거듭제곱꼴을 계산하기 힘드니 $log$ 함수를 이용해서 문제를 만들어냈는데, $\frac{1}{2} N^{ {\frac{ \beta^2 }{ \delta }} - \epsilon}$ 에 $log$ 를 씌우게 되면 $\text{n.bit_length()} \times (\beta^2 - \epsilon)$ 으로 계산되게 된다. ( 여기서 방정식은 1 차 방정식이 나오기에 $\delta$ 는 1이다.) 따라서 여기에 다시 2의 거듭제곱을 계산해주면 $X$ 가 완성된다. 

 

결국 우리는 그대로 대입해주면 문제를 해결할 수 있다. 

from Crypto.Util.number import *
flag = 22492103123920788566454020484604339106134872650742745073391512501050506129771305948928035866535637341505425529084179721882383102079143024731397748507187387934275458350642485568464490304178775216945067031543580644415604813201561755934104373446659569197912824406390477678269408665711776195005658698163441877602214914022338234828353522009440871618156310903726242712995717883683584295220123698766729160977264967508521147707627483921014457438490696390810954428796570691819519425176749918009488582858075560919673618171630106427382202899839616189777693069389827244665900578389930978934439293709745792001621534806757068565505
mask = 177376544737836537358848709698797910837308855345061193615390947134942814024740805585465865242303830353471802614674176223815624459859801244223738281190255897249400782766885506935974648077631183301125138497014459511575357027735370348650450059315998401755052098075642617236823830493603351432334099401848913920000
n,e = 24998297096673150182169249215362354242007739410413318575126157135522454459650464839515367449973589872351881588111232458359974156442759925478269348164600608994047506827654217250363002726550685615195642603168866469240543854748805930296027622682611606161248677612758987033657190784676451784033316444357416540404528215755182617067978225391180373837618722386579966738041103029246826236268998063730920284199010801978445169850020974296002328912355942246224612047246859607259251694465518357860628929093115820723422805933720160134026887165191219451114178035318550244534948457197309229817069441497372353040006761953630520952319,219036592185538135344738307892518971121

beta = 0.4
epsilon = beta**2 / 7

P.<x> = PolynomialRing(Zmod(n))
f = x + mask

p = int(f.small_roots(beta = beta, epsilon = epsilon)[0]) + mask
q = n // p

phi = n - p - q + 1
d = inverse(e,phi)

flag = pow(flag,d,n)
print(long_to_bytes(int(flag)).decode())

Zmod 상에서는 p 또한 0 으로 인식되기 때문에 p 를 구할 수 있다.