배경지식

1. 개요

Coppersmith Attack은 RSA 암호 시스템에서 특정 조건 하에 모듈러 다항식의 작은 근을 효율적으로 찾아내는 강력한 공격 기법이다. 1996년 Don Coppersmith가 제안한 이 방법은 RSA의 보안성이 단순히 큰 합성수 $N$의 소인수분해 난이도에만 의존하지 않음을 보여주었다.

2. Coppersmith 정리

Coppersmith 정리는 모듈러 다항식 방정식에서 특정 범위 내의 작은 근을 다항 시간 내에 찾을 수 있음을 보장하는 강력한 이론적 도구이다. 이 정리는 LLL 격자 기저 축약 알고리즘을 핵심 기법으로 활용한다.

2.1 문제 정의

주어진 모듈러 다항식 방정식에서 작은 정수해를 찾는 문제를 정의한다.

2.1.1 기본 설정

<aside> 💡

모닉 다항식

최고차 항의 계수가 1인 다항식을 의미한다.

예를 들어, $f(x) = x^3 + 2x^2 - 5x + 7$은 모닉 다항식이다 (최고차 항 $x^3$의 계수가 1).

반면 $g(x) = 3x^3 + 2x^2 - 5x + 7$은 모닉 다항식이 아니다 (최고차 항의 계수가 3).

</aside>

입력: $d$차 모닉 다항식 $f(x)$, 합성수 $N$
목표: $f(x_0) \equiv 0 \pmod{N}$을 만족하는 작은 정수 $x_0$ 찾기
모닉 다항식: 최고차 항의 계수가 1인 다항식, 즉 $f(x) = x^d + a_{d-1}x^{d-1} + \cdots + a_1 x + a_0$

2.1.2 문제의 난이도

무작위 대입의 비효율성

$x_0$의 탐색 공간이 $[-X, X]$라면, 무작위 대입은 $O(X)$ 시간이 필요
$X$가 충분히 크면 (예: $X \approx N^{1/d}$) 계산적으로 불가능

소인수분해와의 관계

일반적인 경우, 이 문제는 $N$의 소인수분해만큼 어려울 수 있음
하지만 $x_0$가 충분히 작으면, 소인수분해 없이도 해를 찾을 수 있음

2.2 정리의 핵심 내용

<aside>

Coppersmith 정리:

$f(x)$가 $d$차 모닉 다항식이고, $N$이 충분히 큰 합성수일 때,

$$ |x_0| < N^{1/d - \epsilon} $$

범위 내의 모든 해 $x_0$는 다항 시간 내에 찾을 수 있다. (여기서 $\epsilon > 0$는 임의의 작은 양수)