Coppersmith's Attack

$N=pq$에서 $N$이 주어졌을 때, $p,q$를 찾는 소인수분해 문제는 현대 수학으로 풀기 어렵다.

하지만 만약 $p$의 힌트가 조금이라도 유출된다면 이야기는 완전히 달라진다.

 

The Weakness

RSA 키 생성 속도를 높이기 위해서, 소수 $p$를 완전히 랜덤하게 뽑는 대신 특정한 형태로 만들었다.

 

$p = k \cdot M + (65537^a \pmod{M})$

 

• $M$ : 처음 $n$개의 소수를 모두 곱한 거대한 상수 (예 : $2 \cdot 3 \cdot 5\cdot \cdot \cdot \cdot \cdot p_n$)
• 65537 : RSA에서 흔히 쓰이는 공개 지수 $e$
• $k,a$ : 비밀 값

RSA 키를 만들려면 1024비트나 2048비트짜리 거대한 소수 $p$를 찾아야한다. 보통은 다음과 같이 한다.

1. 랜덤한 숫자 하나를 뽑는다.
2. 그 숫자가 2로 나누어지는지, 3으로 나누어지는지, 5로 나누어지는지... 작은 소수들로 계속 나눠본다 (Trial Division)
3. 안 나누어지면, Miller-Rabin과 같은 정밀한 소수 판별법을 사용한다.

문제는 이러한 연산이 컴퓨터 입장에서는 엄청나게 느린 연산이라는 점이다. 랜덤하게 뽑은 숫자의 대부분은 2,3,5 같은 작은 소수의 배수라서 어차피 탈락한다. 이걸 일일이 나누기로 확인하는 것은 시간 낭비이다.

 

"처음부터 2,3,5,7 같은 작은 소수들로는 절대 안 나누어지는 숫자만 뽑아낼 수 없을까?"

 

이 아이디어를 실현하기 위해서 도입한 것이 $M$ (Primorial)이다.

• $M = 2 \times 3 \times 5 \times \dots \times p_n$ (처음 $n$개 소수의 곱)

이 $M$을 이용해서 숫자를 $p = k \cdot M + R$ 형태로 만든다고 하자. 그러면 나머지 $R$이 $M$과 서로소라면 $p$도 $M$의 약수들로는 절대 나누어 떨어지지 않는다.

즉, 나눗셈 검사를 아예 생략하고 바로 정밀 검사로 넘어갈 수 있다. 따라서 속도가 빨라지게 된다.

 

그럼 이제 $M$과 서로소인 나머지 $R$을 계속 만들어내야 한다. 그냥 랜덤하게 $R$을 뽑아서 서로소인지 확인하면 또 시간이 걸리게 된다. 따라서 $65537^a$를 사용한다.

1. 65537은 소수이다.
2. $M$은 2,3,5, ... 같은 작은 소수들의 곱이다. (보통 65537보다 훨씬 작은 소수를 사용한다.)
3. 따라서 65537은 $M$의 약수가 아니다.
4. 소수의 거듭제곱($65537^a$)는 당연히 $M$과 겹치는 약수가 하나도 없다.

결론적으로 $a$ 값을 1,2,3, ... 이렇게 바꾸기만 하면, $M$과 서로소인 완벽한 후보 숫자들 ($R$)이 계산만으로 쏟아져 나오게 된다.

 

 

문제점

 

$p$를 $M$으로 나눈 나머지를 생각해보자.

$p \equiv 65537^a \pmod{M}$

 

우리는 $a$의 값을 모르지만, $a$가 가질 수 있는 범위는 크지 않다. 만약 공격자가 Brute-force 또는 Pohlig-Hellman 알고리즘을 통해서 $a$를 알아낼 수 있다면 우리는 $p$를 $M$으로 나눈 나머지 $R$을 알게된다.

 

$p= k \cdot M + R$

 

여기서 $M$은 $p$ 크기의 약 절반($N^{1/4}$이상)에 해당하는 매우 큰 수다. 즉, 우리는 소수 $p$의 절반 이상의 비트를 이미 알고 시작하는 셈이다.

 

이걸 쉽게 비트 단위로 설명해보자.

보통 2048비트 RSA 키를 사용한다면, 소수 $p$는 약 1024비트이다. 이 $p$를 맞히려면 동전을 1024번 던져서 앞/뒤를 다 맞히는 것만큼 어렵다. ($2^{1024}$의 확률).

 

그런데 $M$이 약 512비트 (전체의 절반) 크기라고 해보자.

 

$p = k \cdot  M + R$

1. $M$ (512비트) : 알고 있음
2. $R$ (512비트) : $a$를 알아내서 계산했으니 알고 있음
3. $k$ (나머지 512비트) : 모름

우리가 찾아야 할 미지수 $k$는 $p$(1024비트)를 $M$(512비트)으로 나눈 몫이므로, $k$ 자체도 약 512비트 정도밖에 안된다.

즉, 해커 입장에서는 1024자리 비밀번호 중 뒤의 512자리는 이미 알고 있고, 앞의 512자리만 맞히면 되는 상황이 된 것이다. 

 

 

Modeling

이제 문제는 알려진 값, $M, R$과 공개키 $N$을 이용해 미지수 $k$를 찾아라로 바뀐다. $p$는 $N$의 약수이므로 당연히 $N \equiv 0 \pmod{p}$이다. 여기에 $p=k\ cdot M + R$를 대입해보자.

 

$N \equiv 0 \pmod {kM + R}$

 

이 식은 풀기가 까다롭다. 그래서 먼저 우리가 찾고자 하는 $p$의 배수가 되는 다항식 $f(x)$를 만든다.

$x$가 우리가 찾고 싶은 비밀 값 $k$일 때, $0 \pmod{p}$가 되는 식을 세울 수 있다.

 

$f(x) = M \cdot x + R$

 

이 식에 $x=k$를 넣으면 $Mk + R = p$가 되므로, 당연히 $p$의 배수가 된다.

 

$f(k) \equiv 0 \pmod{p}$

 

우리의 목표는 이 방정식을 만족하는 작은 해 $k$를 찾는 것이다. 이것이 바로 Coppersmith's Attack의 핵심, Small Modular Root Problem이다.

 

 

The Coppersmith Method

우리가 현재 알고 있는 것은 이것뿐이다.

$f(k) \equiv 0 \pmod{p}$

 

• $f(x) = M \cdot x + R$
• $k$는 우리가 찾고 싶은 작은 값
• $p$는 모르지만 $N$의 소인수

문제점은 $\pmod{p}$식을 풀고 싶은데, $p$를 모른다는 것이다. 따라서 일반적인 방법으로는 아무것도 할 수가 없다.

 

모듈러 문제의 핵심 난점은 나머지가 0이라는 정보는 $p$를 모르면 쓸 수 없다는 것이다.

그래서 목표를 다음과 같이 바꾼다.

$\pmod{p}$에서 0이 아니라 정수에서 진짜 0을 만들어보자

 

즉, 우리가 원하는 것은 이거다.

$h(k)=0$

이것을 만들 수 있으면 더이상 $p$는 필요가 없다.

 

하지만 그냥은 안 된다. 당연히 이런 생각도 들 수 있다.

$f(k)$가 $p$의 배수니까 $f(k)$가 작으면 그냥 0 아니야?

 

하지만 현실은 이렇다.

• $f(k)$는 보통 매우 크다.
• "작다"를 보장할 방법이 없다.

따라서 어떤 새로운 다항식 $h(x)$를 만들어서 다음 두 조건을 만족시킨다면 어떨까?

1. $h(k) \equiv 0 \pmod p^m$ (여전히 $p$의 배수여야 함)
2. $|h(k)| < p^m$ (절댓값이 $p$보다 작아야 함)

$p$의 배수인데 크기가 $p$보다 작은 수는? 0밖에 없다. 즉, $h(k) = 0$이 되어, 우리는 $p$를 몰라도 그냥 정수 방정식 $h(x)=0$을 풀어서 $k$를 구할 수 있게 된다.

 

 

다시 출발점으로 돌아가자.

$f(k) \equiv 0 \pmod{p}$

• $f(k)$는 $p$의 배수다.
• $f(k)^2$는 $p^2$의 배수다.
• $f(k)^v$는 $f(k)^v$ 의 배수다.
• $p$는 $N$의 인수다.
• 그래서 $N$도 $p$의 배수다.

따라서 이런 식을 만든다.

$g_{u,v}(x) = N^{m-v} \cdot f(x)^v \cdot x^u$

 

이제 여기에 $x=k$를 대입하면

• $f(k)^v$에서 $f(k)^v$
• $N^{m-v}$에서 $p^{m-v}$

합쳐서 $g_{u,v}(k)$는 항상 $p^m$의 배수가 된다.

 

$g_{u,v}(k) \equiv = 0 \pmod{p^m}$

 

 

 

우리는 최종적으로 하나의 좋은 다항식 $h(x)$를 만들고 싶다.

그 $h(x)$는

• $k$에서 $p^m$의 배수
• 동시에 값이 매우 작아야 한다.

$g_{u,v}$는 $k$에서 $p^m$의 배수라는 한 가지 조건만 만족한다.

그래서 여러 $g$를 섞는다.

 

$h(x) = ∑ a_{u,v}g_{u,v}(x)$

 

어떤 정수 계수로 섞어도 $h(k)$는 여전히 $p^m$의 배수다.

남은 문제는 $h(k)$를 작게 만드는 것이다.

 

 

다항식 $h(x)$는 이렇게 생겼다.

$h(x) = c_0 + c_1x + c_2x^2 + \dots $

 

$k$가 작으면, $k^2$도 작고, $k^3$도 작다.

그러면 어떤 값이 $h(x)$값을 키울까 =======> 계수 $c_i$

즉, 계수가 작으면 $k$를 대입했을 때 값도 작아진다.

 

계수가 작은 조합을 어떻게 찾지?

 

여기서 LLL 알고리즘이 사용된다. (다음에 자세히 알아볼 예정)

LLL을 한 문장으로 쉽게 설명하면 정수 조합으로 만들 수 있는 것들 중에서 계수가 전체적으로 작은 조합을 찾아주는 알고리즘이다.

수학적으로 말하면 격자에서 짧은 벡터 찾기라고 할 수 있다.

 

격자가 왜 나오는지 짧게 설명을 해보자면

LLL은 다항식을 이렇게 본다. $3x^2 + 5x + 1 ⇒ (1,5,3)$ .

 

1. 모든 $g_{u,v}(x)$를 전개한다.
2. 각가을 계수 벡터로 바꾼다.
3. 이 벡터들이 만드는 정수 조합 공간을 만든다 → 이것이 격자이다.

결론적으로 LLL은 짧은 벡터 하나를 출력한다. 이 벡터는 여러 $g_{u,v}$ 계수 벡터들의 정수 선형 결합 결과이자 $h(x)$의 계수 벡터가 된다.

 

이제 우리가 얻은 $h(x)$는

1. 설계상 $h(k)$는 $p^m$의 배수
2. LLL 덕분에 계수가 작다.
3. 그래서 $h(k)$의 값도 작다.
4. 파라미터를 잘 고르면 $|h(k)| < p^m$을 만족한다.

그러면 결국엔 $h(k)=0$를 얻을 수 있다.

모듈 연산도 사라지고, $p$도 사라지고 정수 다항식의 근 문제만 남게 된다.

 

이제 할 일은 단순하다.

$h(x)=0$을 풀고 작은 근만 검사하면 그 근이 바로 $k$가 된다.

 

 

Summary

Coppersmith Method는 mod p에서만 의미 있는 식을 정수에서 의미 있는 식으로 바꾸는 기법이다.

이를 위해서 $k$에서 항상 $p^m$의 배수가 되는 다항식 $g_{u,v}$들을 미리 만들고 그 계수들이 만드는 격자에서 LLL로 계수가 작은 조합 $h$를 찾는다.

이 $h$는 $k$에서 매우 작은 값을 가지면서 동시에 $p^m$의 배수이므로 정수에서 0이 될 수밖에 없다.

 

그 결과 $p$를 전혀 몰라도 $k$를 복구할 수 있다.

 

 

Conclusion

공격 과정을 정리하면 다음과 같다.

1. 공개된 $N$과 $M,R$을 이용해 다항식 $f(x) = Mx + R$을 만든다.
2. $g_{u,v}(x)$들을 이용해 거대한 행렬(Lattice)을 만든다.
3. LLL 알고리즘을 돌려 계수가 작은 다항식 $h(x)$를 찾는다.
4. $h(x) = 0$을 다(인수분해 등). 여기서 나온 해가 바로 비밀 값 $k$이다.
5. $p = kM + R$을 계산하여 소수 $p$를 찾고, $N$을 소인수분해한다.

이 공격이 무서운 이유는 $M$이 $N^{1/4}$ 정도만 되어도 공격이 성공한다는 점이다.