Known attack for RSA

Kang-MyeongSeok_Survey-of-RSA-Attacks_presentation.pdf

1.32MB

Kang-MyeongSeok_Survey-of-RSA-Attacks_report.pdf

5.24MB

 

현대암호학개론 수업의 보고서 조사의 일환으로 RSA의 well-known attack 을 정리했습니다.
Report.pdf 와 Presentation.pdf 을 읽어주시면 감사하겠습니다. 

 

As part of a report for the course Introduction to Modern Cryptography, I have organized and summarized well-known attacks on RSA.

Please Read Report.pdf and Presentation.pdf.

 

\documentclass{article}
\usepackage{kotex}
\usepackage{graphicx}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{url}
\usepackage{float}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

\newtheorem{definition}{정의}

\title{A Survey of RSA Attacks}
\author{Kang. MyeongSeok}
\date{12.23.2025}

\begin{document}

\maketitle

\section{Introduction}

RSA는 가장 널리 배포된 공개키 암호 시스템 중 하나이다.
RSA 구현에서의 파라미터 선택, 패딩 방식, 그리고 공격자가 얻는 부가 정보의 형태에 따라 RSA는 서로 다른 수학적 공격에 노출될 수 있다.

본고는 RSA를 RSA problem으로 정식화하고,
이것과 소인수분해 문제간의 관계를 정리한다.
이후 공격을 (i) 잘못된 설계/파라미터로 즉시 성립하는 나이브 공격,
(ii) Coppersmith 기법에 기반한 부분정보 복원 공격,
(iii) 소인수분해를 직접 목표로 하는 수론적 알고리즘으로 분류하여 각각의 개요를 제시한다.

\section{Recall: RSA in Security}

RSA는 가장 널리 사용되는 공개키 암호 시스템 중 하나이다.
본 절에서는 강의 09장 \emph{Public-Key Encryption}에서 다루어진 RSA를 기반으로,
\emph{RSA problem}을 중심으로 RSA의 안전성을 \emph{game-based security} 관점에서 정식화하고,
이 안전성이 \emph{factoring problem}과 어떤 관계를 가지는지를 정리한다.

\subsection{Textbook RSA}

RSA 암호는 Rivest, Shamir, Adleman에 의해 1978년에 제안되었다.
두 개의 큰 소수 $p, q$를 선택하여
\[
N = pq
\]
로 정의하고, 이를 공개 모듈러로 사용한다.
RSA 공개키는 $pk = (N, e)$로 주어지며,
개인키는 $sk = (N, d)$로 구성된다.

개인키 $d$는 다음 조건을 만족하도록 정의된다.
\[
ed \equiv 1 \pmod{\varphi(N)},
\]
여기서 $\varphi$는 Euler totient function으로,
\[
\varphi(N) = \left| \{ m : 1 \le m \le N,\ \gcd(m,N)=1 \} \right|
\]
로 정의된다.
소수 $a$에 대해 $\varphi(a)=a-1$이며,
$\varphi$는 multiplicative function이므로
\[
\varphi(N) = \varphi(pq) = (p-1)(q-1)
\]
가 성립한다.

암호화 과정에서 송신자는 평문 $m$에 대해 $c \equiv m^e \pmod{N}$ 를 계산하여 암호문 $c$를 전송한다.
복호화 과정에 대해, $ ed \equiv 1 \Rightarrow ed = k \varphi(N) + 1 $ 이므로
\[
c^d \equiv m^{ed} \equiv m^{k\varphi(N)+1} \equiv m \pmod{N}
\]
이 성립함을 Euler 정리 $m^{\varphi(N)} \equiv 1$를 통해 보장할 수 있다.
따라서 Textbook RSA는 correct 하다.

\subsection{RSA Problem as a Security Game}

RSA의 안전성은 trapdoor permutation을 기반으로 하여  security game 형태로 정의된 \emph{RSA problem}으로 정의된다.

\begin{figure}[h]
  \centering
  \includegraphics[width=0.85\textwidth]{image/rsa_game.png}
  \label{fig:rsa_game}
  \caption{사진출처 - 현대암호학개론 Lecture Note 9}
\end{figure}

\begin{definition}[RSA 문제]

RSA 키 생성 알고리즘을 통해 $(pk, sk) = ((N,e),(N,d))$가 생성되었다고 하자.
균등하게 선택된 $y \in \mathbb{Z}_N^*$가 주어질 때,
공격자는 다음 조건을 만족하는 $x \in \mathbb{Z}_N^*$를 찾는 문제를 푼다.
\[
x^e \equiv y \pmod{N}.
\]
\end{definition}

이 게임에서 공격자가 성공한다는 것은,
RSA 암호화 함수 $f(x)=x^e \bmod N$을 효율적으로 역으로 계산할 수 있음을 의미한다.
RSA 가정(RSA assumption)이란,
임의의 공격자가 이 게임에서 성공할 확률이 무시 가능하다는 가정을 말한다.

즉, RSA 가정 하에서 RSA는 one-way function 이며,
공격자는 암호문으로부터 평문을 계산적으로 복원할 수 없다.

\subsection{Between the RSA Problem and Factoring}

RSA 문제와 소인수분해 문제 사이에는 환원 관계가 존재한다.
소인수분해에 대한 효율적인 adversary가 존재한다고 가정하자.
$N$ 을 소인수분해하여 $p, q$를 알면 $\varphi(N) = (p-1)(q-1)$을 계산할 수 있고, 개인키
\[
d \equiv e^{-1} \pmod{\varphi(N)}
\]
를 효율적으로 구할 수 있다.
개인키 $d$와 암호문 $c$ 로부터
$m \equiv c^d \pmod{N}$을 계산할 수 있으므로,
RSA 역연산은 즉시 가능해진다.

따라서 소인수분해 공격자를 사용하여
RSA 문제에 대한 공격자를 구축할 수 있다.
\[
\text{RSA Inversion} \;\leq\; \text{Factoring}.
\]
즉, RSA는 최소한 소인수분해만큼은 안전하다고 말할 수 있다.

\begin{figure}[h]
  \centering
  \includegraphics[width=0.7\textwidth]{rsa_problem_inv.png}
  \caption{사진출처 - 암호론 Lecture Note 7-2}
  \label{rsa_problem_inv}
\end{figure}

반면, 역의 성립은 아직 알 수 없는데, 보다 단계적으로 살펴보면,
\[
N \xrightarrow{\text{factor}} (p,q)
\xrightarrow{} \varphi(N)
\xrightarrow{} (e, d)
\xrightarrow{} (c, m)
\]
라는 순방향 과정에서,

먼저 $(p, q)$ 를 알고 있다면 $N$ 을 $p \times q$ 로 소인수분해할 수 있음은 자명하다

$\varphi(N)$을 알고 있다면 $p+q = N+1 - \varphi(N)$ 을 알고, 이것을 이용하여 $(p,q)$를 계산할 수 있다,

또한 $(e,d)$가 모두 주어질 경우,
$\varphi(N)$ 를 결정적 다항 시간에 복원할 수 있음이 2004년에 Jean-Sebastien Coron 와 Alexander May 에 의해 증명되었다 \cite{cryptoeprint:2004/208}.

즉,
\[
(e,d) \;\Rightarrow\; \varphi(N) \;\Rightarrow\; (p,q)
\]
는 deterministic polynomial-time 환원이 가능하다.

반면, 
\[
(c,m) \;\Rightarrow\; d
\]
가 가능한지 여부는 여전히 open problem이다. 이 단계에 의해, 역방향 환원은 open problem 으로 남아 있다.

\subsection{Computing the modular inverse via EEA}

앞 절에서 보았듯이,
$\varphi(N)$을 알고 있다면 RSA 개인키 $d$는
\[
ed \equiv 1 \pmod{\varphi(N)}
\]
를 만족하는 정수로 정의된다.
즉, $d$는 $e$의 $\varphi(N)$에 대한 모듈러 역원이다.
해당 역원을 실제로 계산하는 효율적인 알고리즘으로
\emph{확장 유클리드 호제법(Extended Euclidean Algorithm)}이 있다.

\paragraph{문제 재정의.}
RSA 키 생성 과정에서 $e$는
\[
\gcd(e,\varphi(N)) = 1
\]
을 만족하도록 선택된다. (그렇지 않을 경우 역원은 없다).
따라서 Bezout 정리에 의해, 어떤 정수 $d,k$가 존재하여,
\[
ed + k\varphi(N) = 1
\]
이 성립한다.
이때 위 식을 만족하는 $d$ 는
\[
ed \equiv 1 \pmod{\varphi(N)}
\]
를 또한 만족하므로,
$d$는 곧 구하고자 하는 값이 된다.
따라서 문제는 주어진 두 정수 $a,b$에 대해
$ax + by = \gcd(a, b)$ 를 만족하는 $x$ 를 효율적으로 계산하는 것이다.

\paragraph{Extended Euclidean Algorithm}
확장 유클리드 호제법은
두 정수 $a,b$에 대해
\[
\gcd(a,b) = xa + yb
\]
를 만족하는 정수 $(x,y)$를
$O(\log a)$에 계산하는 알고리즘이다.
일반적인 유클리드 호제법의 나눗셈 과정
\[
\begin{aligned}
b &= q_1 a + r_1,\\
a &= q_2 r_1 + r_2,\\
&\;\vdots\\
r_{k-2} &= q_k r_{k-1} + r_k,\\
r_{k-1} &= q_{k+1} r_k
\end{aligned}
\]
을 역으로 추적하여,
$\gcd(a,b)$를 $a,b$의 정수 선형결합으로 표현한다.

이때 확장 유클리드 호제법의 핵심은,
구체적으로, 모든 단계 $i$에 대해 정수 $x_i, y_i$가 존재하여
\[
r_i = a x_i + b y_i
\]
가 성립하게 만든 뒤, $r_i = \gcd(a, b)$ 일 떄의 $(x_i, y_i)$ 를 취한다.

초기값으로
\[
r_{-1} = b = a\cdot 0 + b\cdot 1,\qquad
r_0 = a = a\cdot 1 + b\cdot 0
\]
이므로
\[
(x_{-1},y_{-1}) = (0,1),\quad (x_0,y_0) = (1,0)
\]
로 둘 수 있다.
이제 유클리드 호제법의 점화식
\[
r_{i-2} = q_i r_{i-1} + r_i
\]
에서,
\[
r_i = r_{i-2} - q_i r_{i-1}
     = a(x_{i-2} - q_i x_{i-1}) + b(y_{i-2} - q_i y_{i-1})
\]
가 되어,
\[
x_i = x_{i-2} - q_i x_{i-1},\qquad
y_i = y_{i-2} - q_i y_{i-1}
\]
라는 재귀 관계를 얻는다.

이 과정을 마지막 나머지 $r_k = \gcd(a,b)$에 대해 적용하면,
\[
\gcd(a,b) = a x_k + b y_k
\]
를 만족하는 $(x,y)$를 계산할 수 있다.

\paragraph{RSA 개인키의 계산.}
RSA의 경우,
\[
a = e,\qquad b = \varphi(N)
\]
로 두고 계산한다 계산에는 로그 시간이 요구된다.
확장 유클리드 호제법으로 얻은 $d$는
음수일 수도 있으므로,
\[
d \leftarrow d \bmod \varphi(N)
\]
으로 정규화한다.
이렇게 얻은 $d$는
\[
ed \equiv 1 \pmod{\varphi(N)}
\]
를 만족하며, 복호화에 사용된다.

\section{Naive Attacks}

본 절에서는 RSA에 대한 가장 기본적인 공격 시나리오를 다룬다.
이 공격들은 구조적으로 단순하지만,
부적절한 파라미터 선택으로 인해 RSA의 안전성을 즉시 붕괴시킬 수 있다는 점에서
중요한 의미를 가진다.
특히 공개 지수 $e$가 지나치게 작은 경우와,
RSA 모듈러스 $N=pq$에서 두 소수 $p,q$의 차이가 작은 경우를 중심으로 살펴본다.

\subsection{Small Public Exponent Attacks}

RSA에서 공개 지수 $e$와 평문 $m$이 모두 충분히 작은 경우,
RSA 암호는 모듈러 연산이 개입되기 전에 붕괴될 수 있다.
암호문은
\[
c \equiv m^e \pmod{N}
\]
로 계산되는데,
만약
\[
m^e < N
\]
가 성립한다면, 위 식은 단순히 정수 등식
\[
c = m^e
\]
로 귀결된다.
이 경우 공격자는 암호문 $c$에 대해 정수 $e$-제곱근을 계산함으로써
\[
m = \lfloor \sqrt[e]{c} \rfloor
\]
를 직접 복원할 수 있다.

특히 $e=3$과 같은 매우 작은 공개 지수가 사용될 경우,
실제 환경에서도 충분히 실용적인 공격이 가능하다.

\subsection{Hastad's attack with no padding}

실제 구현에서 RSA의 공개 지수는
\[
e = 2^{16} + 1 = 65537
\]
이 자주 사용된다.
이는 square-and-multiply 알고리즘을 이용할 때
모듈러 거듭제곱 연산의 계산 비용을 크게 줄일 수 있기 때문이다.

그러나 공개 지수 $e$가 고정된 상태에서
동일한 메시지 $m$을 서로 다른 RSA 모듈러스
$N_1, \dots, N_e$에 대해 암호화하는 경우,
새로운 취약점이 발생한다.
각 암호문은
\[
c_i \equiv m^e \pmod{N_i}
\]
의 형태를 가지며,
CRT를 사용하여
다음과 같은 합동식의 해를 효율적으로 계산할 수 있다.
\[
x \equiv m^e \pmod{\prod_{i=1}^{e} N_i}.
\]

이때 $m^e < \prod_{i=1}^{e} N_i$가 성립하면,
공격자는 $m=\sqrt[e]{m^e}$ 로
평문 $m$을 복원할 수 있다.
이 공격은 Hastad에 의해 구체적으로 작성되었다. \cite{doi:10.1137/0217019}.

\subsection{Fermat's Factorization with Small $|p-q|$}

RSA 모듈러스 $N=pq$에서 두 소수 $p,q$가 서로 매우 가까운 경우,
Fermat의 인수분해 방법을 통해 $N$을 효율적으로 소인수분해할 수 있다.
이 방법은 $N$을 두 제곱수의 차
\[
N = a^2 - b^2 = (a-b)(a+b)
\]
의 형태로 표현하는 것을 목표로 한다.

Fermat 인수분해는 $k=\lceil \sqrt{N} \rceil$부터 시작하여
$k^2-N$이 완전제곱수인지 여부를 순차적으로 검사한다. $k=a$ 일 때 $k^2 - N = b^2$ 이다.
$(p, q)$는
\[
a = \frac{p+q}{2}, \qquad b = \frac{p-q}{2}
\]
로 얻어지며, $N=(a-b)(a+b)$로 인수분해된다.

알고리즘의 반복 횟수는 초기값 $\lceil \sqrt{N} \rceil$에서
$a=\frac{p+q}{2}$에 도달할 때까지의 증분 횟수에 해당하며,
이는 근사적으로 $\Theta(\frac{|p-q|^2}{8\sqrt{N}})$ 에 비례한다.
따라서 $p$와 $q$가 충분히 가까운 경우,
Fermat 인수분해는 매우 빠르게 종료된다. 

이러한 이유로 RSA 키 생성 과정에서는
$p$와 $q$가 비정상적으로 가까워지지 않도록 하는 것이 일반적으로 권장되고, 구체적으로는 $|p-q| > N^{1/4}$ 가 제안된다.

실제로 $p$와 $q$의 차이가 충분히 크지 않은 RSA 키가 사용되어
보안 취약점이 발생한 사례가 보고된 바로는 CVE-2022-26320가 존재한다.
\cite{cve202226320}.

\section{Coppersmith-based Attacks}

\begin{figure}[h]
  \centering
  \includegraphics[width=0.7\textwidth]{image/coppersmith_lattice.png}
  \caption{$f(x)=x^2 + ax + b$일 때 도출되는 lattice}
  \label{coppersmith_lattice}
\end{figure}

Coppersmith 기반 공격은 부분적인 정보만으로도 파라미터를 복원하는 공격 기법이다.
이 절에서는 Coppersmith 알고리즘과, 여러 $N$ 을 사용한 암호화 값을 알 때 그리고 $p-q$가 작을 때 소인수분해를 수행할 수 있음을 간략히 보인다.

\subsection{Coppersmith의 statement}
Coppersmith algorithm 은 $\mod N$ 아래에서 다항함수의 근을 다항시간 내에 찾는 알고리즘이다.

\begin{theorem}[Coppersmith (univariate small roots)]
\label{thm:coppersmith-univariate}
$N\in \mathbb{Z}_{>0}$, $f\in \mathbb{Z}[x]$를 최고차항 계수가 $1$인 $d$차 다항식이라 하자.
$\epsilon\ge 0$에 대해 $X := N^{1/d-\epsilon}$라 두면,
주어진 $(N,f)$로부터
\[
|x_0|<X,\qquad f(x_0)\equiv 0\pmod N
\]
을 만족하는 모든 $x_0$를 다항시간에 찾을 수 있다.
\end{theorem}

알고리즘은 LLL algorithm 에 기반한다. LLL 알고리즘은 아래를 deterministic 하게 poly time 내에 찾을 수 있다.

\begin{theorem}[LLL reduction]
\label{thm:lll}
$n$차원 정수 격자 $\mathcal{L}\subset\mathbb{R}^n$가
기저 $\mathbf{b}_1,\dots,\mathbf{b}_n$으로 주어졌다고 하자.
LLL 알고리즘은 다항시간 내에
새로운 기저 $\mathbf{b}'_1,\dots,\mathbf{b}'_n$을 계산하며,
그 첫 번째 벡터는 다음을 만족한다:
\[
\|\mathbf{b}'_1\|
\;\le\;
2^{\frac{n-1}{4}}\cdot \lambda_1(\mathcal{L}),
\]
여기서 $\lambda_1(\mathcal{L})$는
격자 $\mathcal{L}$의 최단 비영벡터의 길이이다.
\end{theorem}


% LLL algorithm 의 statement %

\subsection{proof (sketch)}
\label{subsec:coppersmith-proof}

\paragraph{전제}
다항식 $h(x)=\sum_{i=0}^{d} a_i x^i\in \mathbb{Z}[x]$에 대해, 다항식을 각 계수를 이어 쓴 벡터로 보고
\[
\|h\|^2 := \sum_{i=0}^{d} |a_i|^2
\]
로 정의한다. 아래가 성립한다.

\begin{lemma}[Theorem by Howgrave-Graham]
\label{lem:HG}
$h\in \mathbb{Z}[x]$가 $d$차이고 $X\in\mathbb{Z}_{>0}$라 하자.
만약
\[
\|h(xX)\| < \frac{N}{\sqrt{d}}
\]
이고 $|x_0|<X$가 $h(x_0)\equiv 0\pmod N$을 만족하면, $\mathrm{modular}$ 와 무관하게  $h(x_0)=0$ 이다.
\end{lemma}

\begin{proof}
$h(x_0) < N$ 임을 보이자. $|x_0|<X$이므로 $|x_0/X|<1$.
\[
|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} |a_i X^i|.
\]
Cauchy--Schwarz 부등식에 따라
\[
\sum_{i=0}^{d}|a_i X^i|\le \sqrt{d}\,\|h(xX)\| < N.
\]
$N\mid h(x_0)$이고 $|h(x_0)|<N$이므로 $h(x_0)=0$이다.
\end{proof}

\paragraph{아이디어}
우리가 원하는 것은 $f(x_0)\equiv 0\pmod N$인 작은 $x_0$를 찾는 것이다.
Lemma \ref{lem:HG}에 의해, 어떤 $h$가 있어서
\[
h(x)\equiv 0\pmod N ,\qquad \|h(xX)\|\ \text{가 충분히 작게}
\]
이면, $x_0$는 modular가 없는 정수 방정식 $h(x)=0$의 근이다.

\paragraph{matrix 구축}
$\deg f=d$, $f$의 최고차항 계수가 $1$이라 하자 (상수곱하여).
어떤 정수 $m\ge 1$가 있어, 다음 다항식들을 고려한다.
\[
g_{u,v}(x) := N^{m-v}\, f(x)^v\, x^u,
\qquad 0\le u\le d-1,\ \ 0\le v\le m.
\]
만약 $f(x_0)\equiv 0\pmod N$이면 $f(x_0)^v\equiv 0\pmod{N^v}$이므로
\[
g_{u,v}(x_0)\equiv 0\pmod{N^{m}} \quad (\forall u,v).
\]
이다. $n=d(m+1)$ 이라고 하자. 이것은 $g$의 개수와 같으며, $f$가 $d$차이므로 모든 $(u, v)$가 하나의 $n$ 값에 대응된다.

이제 $x\mapsto xX$를 넣고, $g_{u,v}(xX)$의 계수벡터들을 상수항이 1열에 오도록 쌓아 lattice $L\subset \mathbb{Z}^{n}$를 만든다.
행렬은 상삼각 형태가 되며, 따라서 행렬식은 최고차항의 곱과 같다.

\paragraph{determinant와 LLL bound.}
$f$의 최고차항 계수를 1로 가정했으므로, 
$g_{u,v}(xX)$의 최고차항 계수는 $X^{u+dv}N^{m-v}$이다.
곱하여
\[
\det(L)= X^{\frac{n(n-1)}{2}}\cdot N^{\frac{dm(m+1)}{2}}.
\]
를 안다.

LLL 알고리즘은 다항시간에 짧은 벡터를 찾아준다.
LLL이 산출한 비영벡터 $b\in L$의 길이는 대략
\[
\|b\|
\ \lesssim\
2^{\frac{n-1}{4}}\cdot \det(L)^{1/n}.
\]
적절히 정리하면
\[
\|h(xX)\| \le (\sqrt{2}X)^{\frac{n-1}{2}}\cdot N^{m/2}
\]
꼴의 상계를 얻는다.

\paragraph{부등식의 적용}
Lemma \ref{lem:HG}를 적용하기 위해서는 $\|h(xX)\| < \frac{N^m}{\sqrt{n}}$가 성립해야 한다.
LLL로 얻은 $h$에 대한 상계를 대입하면 충분조건으로
\[
(\sqrt{2}X)^{\frac{n-1}{2}} \cdot N^{m/2}
< \frac{N^m}{\sqrt{n}}
\]
를 얻는다.
이를 정리하면
\[
X^{n-1} < \frac{N^{m}}{2^{\frac{n-1}{2}}\, n}
\]
이며, $n=d(m+1)$를 대입하고 $m\to\infty$로 보내면 $X < N^{1/d}$ 가 도출된다.
다만 실제로는 여유가 필요하므로, X 의 최상위 비트가 0이라고, 즉
\[
X = \frac{1}{2}N^{1/d-\varepsilon}
\]
를 가정하자.
이 경우 전제가 성립하므로 앞서 밝힌 lemma 를 적용할 수 있다.

만약 LLL 이후 얻은 후보 근이 검증에 실패하면,
$x_0$의 MSB가 $1$이라고 가정하여
\[
x = x' + X
\]
로 치환해 동일 과정을 반복하면 된다. 다항 시간 알고리즘을 두 번 사용하여 해를 구할 수 있으므로, 알고리즘은 다항 시간 내에 작동한다.

\paragraph{결론.}
이렇게 얻은 $h$의 근 $x$ 는
\[
h(x_0)\equiv 0\pmod{N^m}\quad\Rightarrow\quad h(x_0)=0
\]
을 만족하므로, 작은 근 $x_0$를 정수 다항식의 근으로 찾아낼 수 있다.

\subsection{Hastad's Attack}
앞서 보였던 알고리즘으로,
low public exponent 가 가정된 broadcast 상황에서의 공격을 수행할 수 있다.

\paragraph{plain broadcast.}
3.2 절에서 보였던 공격과 같은 공격.
$e=3$이라 하고, 서로소인 모듈러스 $N_1,N_2,N_3$에 대해
동일한 메시지 $M$을 각각
\[
C_i \equiv M^3 \pmod{N_i}\qquad (i=1,2,3)
\]
로 보냈다고 하자. 공격자는 $(C_i,N_i)$를 모두 안다고 하자.
CRT로
\[
C \equiv M^3 \pmod{N_1N_2N_3}
\]
인 $C$를 복원할 수 있다. 만약 \emph{정수로} $M^3 < N_1N_2N_3$이면,
그냥
\[
C = M^3
\]
가 되므로 정수 세제곱근으로 $M$을 즉시 복원한다.

\paragraph{방어.}

따라서. low public exponent 환경에서 동일한 메시지를 여러 수신자에게
그대로 broadcast하면 평문이 복원가능하다.
가장 자연스러운 방어 아이디어는
각 수신자에게 전달되는 메시지를 조금씩 다르게 만드는 것이다.

수신자 $i$에게 메시지 $M^{e_i} \pmod{N_i}$를 그대로 보내는 대신,
\[
(M + i\cdot 2^m)^{e_i} \pmod{N_i}
\]
를 보내는 방식을 생각할 수 있다.
이 방식은 각 수신자에게 서로 다른 메시지를 전달하므로,
제시한 공격을 막는 것처럼 보인다.

이를 더 일반화하여 다음과 같은 전송 모델을 생각할 수 있다.
메시지를 전달하고자 하는 수신자들이
\[
P_1, P_2, \dots, P_k
\]
이고, 각 수신자 $P_i$에 대해 어떤 다항식
\[
f_i(x) \in \mathbb{Z}_{N_i}[x]
\]
를 하나 선택한 뒤,
\[
C_i \equiv f_i(M)^{e_i} \pmod{N_i}
\]
를 전송하는 방식이다.
공격자가 알 수 있는 정보는
\[
(N_i, e_i, f_i, C_i)
\]
이다.

이 상태에서 메시지 $M$을 직접 복원하는 것은 어려워 보인다.
그러나 충분히 많은 정보가 주어진다면,
Coppersmith의 small-root 기법으로 공격가능하다.

\paragraph{generalized broadcast attack.}
서로소인 자연수
\[
N_1, N_2, \dots, N_k
\]
가 주어져 있고, 각 $1\le i\le k$ 에 대해, $g_i(x)$
가 차수 $d$ 이하의 다항식이며,
어떤 $M < N_{\min}$에 대해
\[
g_i(M) \equiv 0 \pmod{N_i}
\quad (1 \le i \le k)
\]
가 성립한다고 가정하자. ($k > d$)이때 모든 $(N_i, g_i)$가 주어지면,
$M$은 다항식 시간에 복원 가능하다.

\paragraph{변수 구성. }
먼저 각 $g_i$의 최고차항 계수는 $1$이라고 가정할 수 있다.
중국인의 나머지 정리를 이용해
\[
T_i \equiv \delta_{i,j} \pmod{N_j}
\]
를 만족하는 계수 $T_1,\dots,T_k$를 잡고,
\[
g(x) := \sum_{i=1}^k T_i g_i(x)
\]
를 정의한다.
$N := \prod_{i=1}^k N_i$라 하면,
\[
g(x) \in \mathbb{Z}_N[x], \qquad
g(M) \equiv 0 \pmod N
\]
가 성립한다.
또한 $g(x)$ 역시 $\mathbb{Z}_N[x]$에서 최고차항 계수가 $1$인 다항식이며,
\[
\deg g = d
\]
이다.

\paragraph{Coppersmith 조건.}
우리가 찾고자 하는 근은 $x=M$이다.
가정에 의해
\[
M < N_{\min}.
\]
한편,
\[
N = \prod_{i=1}^k N_i \ge (N_{\min})^k
\quad\Rightarrow\quad
M < N^{1/k}.
\]
가정 $k>d$로부터
\[
M < N^{1/d}
\]
가 성립하므로,
이는 Coppersmith의 단변수 small-root 정리를 적용할 수 있는 조건을 만족한다.
따라서 $M$은 다항식 시간에 복원 가능하다.

\paragraph{RSA에 적용 ($e=3$).}
RSA에서
\[
g_i(x) := f_i(x)^3 - C_i
\]
로 두면 $d=3$이다.
따라서 서로 다른 세 개 이상의 모듈러스에 대해
\[
C_i \equiv f_i(M)^3 \pmod{N_i}
\]
가 주어지는 경우,
위 정리를 적용하여 평문 $M$을 복원할 수 있다.
이는 메시지를 단순히 `조금씩 다르게', 심지어는 다항식을 적용하여 보내는 방식이
low public exponent 환경에서는
본질적인 방어책이 되지 못함을 보여준다.


\subsection{Coppersmith's Short Pad Attack}
\label{subsec:shortpad}
``짧은 패딩(short random bits)'' 재전송 시나리오를
Coppersmith 관점으로 정리한다. 핵심은 ``같은 본문 + 짧은 랜덤 꼬리''가
서로 작은 차이의 관련 메시지(related messages)를 만든다는 점이다.

\paragraph{Franklin-Reiter related-message attack}
에는 $e=3$에서 다음 lemma를 보일 수 있다.

\begin{lemma}[Related messages at $e=3$]
\label{lem:related-e3}
$e=3$이고 $(N,e)$가 RSA 공개키라 하자.
서로 다른 $M_1,M_2\in \mathbb{Z}_N^\ast$와 일차식 $f(x)=ax+b\in \mathbb{Z}_N[x]$ ($b\neq 0$)가 있어
\[
M_1 \equiv f(M_2)\pmod N
\]
를 만족한다고 하자.
또한 $C_1\equiv M_1^e\pmod N$, $C_2\equiv M_2^e\pmod N$가 주어졌다고 하자.
그러면 $(N,e,C_1,C_2,f)$만으로 $M_1,M_2$를 빠르게 복원할 수 있다.
\end{lemma}

\begin{proof}[스케치]
$M_2$는
\[
g_1(x):=f(x)^e - C_1,\qquad g_2(x):=x^e - C_2
\]
의 공통근이므로 $(x-M_2)$는 $\gcd(g_1,g_2)$의 인수다.
$\gcd(g_1,g_2)$를 구하면, $e=3$에서 최대공약수가 일차식이 되어 $M_2$가 떨어진다.
\end{proof}

\paragraph{Short pad 시나리오.}
Alice가 메시지 본문 $M$에 $m$비트 정도의 랜덤 패딩을 붙여 RSA로 암호화한다고 하자.
이를 정수로 모델링하면
\[
M_1 = M\cdot 2^m + r_1,\qquad M_2 = M\cdot 2^m + r_2,
\qquad 0\le r_1,r_2 < 2^m.
\]
공격자가 두 암호문
\[
C_1 \equiv M_1^e \pmod N,\qquad C_2 \equiv M_2^e \pmod N
\]
을 확보한다고 하자. 이때 두 메시지는
\[
M_1 = M_2 + (r_1-r_2)
\]
의 관계를 가지고, 차이
\[
x := r_1-r_2
\]
가 충분히 작다.($|x|<2^m$).

\paragraph{다변수 Coppersmith로의 환원.}
미지수를
\[
y := M_2,\qquad x := r_1-r_2
\]
로 두면 다음 합동식을 동시에 만족한다.
\[
y^e \equiv C_2 \pmod N,\qquad (y+x)^e \equiv C_1 \pmod N.
\]
즉,
\[
F_1(x,y):=(y+x)^e-C_1 \equiv 0\pmod N,\qquad
F_2(x,y):=y^e-C_2 \equiv 0\pmod N.
\]
여기서 $x$는 작은 범위(약 $2^m$)로 제한된다.
Coppersmith의 \emph{다변수} small-root 기법(Howgrave-Graham류 확장)은
이러한 구조에서 $(x,y)$를 찾는 방향으로 작동한다.
실제로는 lattice를
\[
N^{k}\cdot F_1(x,y)^{\alpha} F_2(x,y)^{\beta}\cdot x^i y^j
\]
꼴의 다항식들을 적절히 모아 구성하고, LLL로 작은 노름의 조합을 만든 뒤,
모듈러 근을 정수근으로 승격시켜 작은 $x$를 계산 가능하다고 한다.

\paragraph{복원.}
$x$를 얻으면
\[
M_1 \equiv (M_2 + x)\pmod N
\]
관계로부터 (혹은 위 시스템을 다시 풀어) $M_2$를 구하고,
마지막으로
\[
M = \left\lfloor \frac{M_2}{2^m}\right\rfloor
\]
로 원문을 복원한다.

\subsection{small $|p-q|$}
\label{subsec:small-p-q}

RSA 공개값 $N=pq$에서 두 소수 $p,q$가 서로 매우 가까운 경우, 구체적으로는
\[
|p-q| < N^{1/4}
\]
이면 Coppersmith 방법을 이용하여 $N$을 다항시간에 인수분해할 수 있다.
``$p-q$가 작다''는 정보를 정수근 문제로 환원한 후, Coppersmith 의 알고리즘을 적용한다.

\paragraph{재정의1}
$p\approx q\approx \sqrt{N}$라 가정하고
\[
p = q + x
\]
로 두자. 여기서 $x=p-q$는 작은 정수이다.
그러면
\[
N = q(q+x) = q^2 + xq
\]
이고, 이를 $q$에 대한 이차식으로 보면
\[
q^2 + xq - N = 0.
\]
이제
\[
f_x(y) := y^2 + xy - N \in \mathbb{Z}[y]
\]
를 정의하면, $(x,q)$는
\[
f_x(q)=0
\]
을 만족하는 정수 해이다.

그러나 $x$와 $q$를 동시에 모르는 상황에서는
$x$를 작은 미지수로 취급하는 것이 핵심이다.
이를 위해 다음과 같이 중심을 $\sqrt{N}$로 이동한다.

\paragraph{함수 구축}
$q \approx \sqrt{N}$이므로
\[
q = \lfloor \sqrt{N} \rfloor + y
\]
로 두면, $|y|$ 역시 작다. (y 는 음수)
이를 대입하면
\[
N = (\sqrt{N}+y)(\sqrt{N}+y+x)
= N + (2y+x)\sqrt{N} + y(y+x).
\]
정리하면
\[
(2y+x)\sqrt{N} + y(y+x) = 0.
\]
양변을 $\sqrt{N}$로 나누고 정수 계수 다항식으로 만들기 위해 적절히 정리하면,
$(x,y)$에 대한 다변수 다항식
\[
F(x,y) := y^2 + xy + 2y\sqrt{N} + x\sqrt{N}
\]
이 존재하며,
$(x,y)$는 이 다항식의 근이 된다. 이때,
\[
|x| \ll N^{1/4}, \qquad |y| \ll N^{1/4}
\]
이다.

\paragraph{Coppersmith 적용}
위 상황은 본질적으로
\[
F(x,y) \equiv 0 \pmod N
\]
을 만족하는 작은 $(x,y)$를 찾는 문제이며,
이는 Howgrave--Graham 확장 형태의
\emph{다변수 Coppersmith small-root 정리}의 직접적인 적용 대상이다.

일반적인 결과에 따르면,
차수 $d=2$인 다변수 다항식에 대해
\[
|x|,|y| < N^{1/4-\varepsilon}
\]
이면 LLL 기반 lattice 구성으로 $(x,y)$를 다항시간에 복원할 수 있다.
$x$가 복원되면
\[
p-q = x,\qquad
p = \frac{\sqrt{x^2+4N}+x}{2},\quad
q = p-x
\]
로 $p,q$를 계산할 수 있다.

% \paragraph{요약.}
% \begin{itemize}
%   \item $p-q$가 충분히 작으면 인수분해 문제는 small-root 문제로 환원된다.
%   \item 해당 small-root는 다변수 Coppersmith 기법으로 복원 가능하다.
%   \item 따라서 ``서로 가까운 소수로 만든 RSA 모듈러스''는 구조적으로 취약하다.
% \end{itemize}

\section{Factorization-based Attacks}

앞 절들에서는 벡터공간 이용한 공격을 살펴보았다.
해당 절에서는, 보다 직접적으로
$N=pq$의 소인수분해 자체를 목표로 하는 공격을 살펴본다.

\subsection{Pollard's $p-1$ Algorithm}
\label{subsec:pollard-pminus1}

소인수 분해 알고리즘 중 대표적인 예로 Pollard의 $p-1$ 알고리즘이 있다.

\paragraph{Statement.}
RSA 모듈러스
\[
N = pq
\]
에서 한 소수 $p$에 대해
\[
p-1
\]
이 \emph{작은 소수들만으로 이루어진 수(smooth number)}라면,
이를 이용해 $p$를 효율적으로 찾아낼 수 있다.

\paragraph{수론적 배경.}
임의의 $a \in (\mathbb{Z}/p\mathbb{Z})^\times$에 대해,
Fermat의 소정리에 의해
\[
a^{p-1} \equiv 1 \pmod{p}
\]
가 성립한다.
따라서 어떤 정수 $M$이
\[
p-1 \mid M
\]
을 만족하면,
\[
a^M \equiv 1 \pmod{p}
\]
가 된다.
반면 일반적으로는
\[
a^M \not\equiv 1 \pmod{q}
\]
일 가능성이 높다.
이 차이를 이용하면 $p$를 $N$에서 분리해낼 수 있다.

\paragraph{알고리즘의 구성.}
정수 $B>0$를 smoothness bound라 하자.
$p-1$은 $B$-smooth 하다.

\[
p-1 = \prod_{i} \ell_i^{e_i}
\quad\text{with all } \ell_i \le B.
\]
다음 수를 정의한다:
\[
M := \mathrm{lcm}\bigl(1,2,3,\dots,B\bigr)
= \prod_{\ell \le B} \ell^{\lfloor \log_\ell B \rfloor}.
\]
이때 만약 $e_i \leq \lfloor \log_l B \rfloor$ 이라면
\[
p-1 \mid M
\]
이 성립하게 되고, 임의의 $a$ ($2 \le a \le N-1$)에 대해
\[
a^M \equiv 1 \pmod{p}
\]
가 된다.

이제
\[
d := \gcd(a^M - 1, N)
\]
을 계산한다.
가능한 결과는 다음 세 가지이다:
\[
d = 1,\quad d = p,\quad d = N.
\]
이 중
\[
1 < d < N
\]
이면, $d$는 $N$의 비자명한 인수이며
\[
d = p
\]
가 된다. 만약 $d=N$ 이면, 다른 $B$ 로 같은 과정을 시도해볼 수 있다.

\paragraph{시간 복잡도.}
실행 시간은 $B$에 의해 결정된다.
\[
M=\mathrm{lcm}(1,2,\dots,B)
\]
를 직접 계산할 필요는 없으며, $a^M$ 만이 필요하기 때문에,
반복적인 modular exponentiation으로
\[
a \leftarrow a^{\ell^{\lfloor\log_\ell B\rfloor}} \pmod{N}
\quad(\ell \le B \text{ prime})
\]
을 순차적으로 수행한다.
따라서 알고리즘의 주요 연산은
$O(\pi(B))$회의 modular exponentiation이며,
각 연산은 $O(\log N)$비트 정수에 대한 거듭제곱이므로
전체 시간 복잡도는
\[
O\bigl( \pi(B) \log B \cdot (\log^2 N)\bigr) \simeq O\bigl(B \cdot (\log^2 N)\bigr)
\]
로 평가할 수 있다.

\paragraph{성공 조건 및 결론.}
Pollard의 $p-1$ 알고리즘이 성공하려면
\[
p-1 \text{ 이 } B\text{-smooth}
\]
이어야 한다. 이 조건이 만족되면,
$M$은 $p-1$의 배수일 수 있고 알고리즘은 높은 확률로 성공한다. 따라서 실제 RSA 키 생성에서는,
$p-1$, $q-1$이 모두 큰 소인수를 갖도록 설계하는 것이 필수적이다.

\subsection{Williams' $p+1$ Algorithm}

Williams의 $p+1$ 알고리즘은 Pollard의 $p-1$ 알고리즘과 유사한 아이디어를 적용한 소인수분해 기법이다.
Pollard $p-1$이 $p-1$의 smoothness에 의존하는 반면,
Williams $p+1$ 알고리즘은
\[
p+1
\]
의 smoothness를 이용한다.
따라서 $p-1$이 큰 소인수를 포함하도록 설계된 RSA 모듈러스에 대해서도,
$p+1$이 smooth한 경우에는 여전히 취약하다.

\paragraph{아이디어.}
$p-1$ 알고리즘은 곱셈군 $(\mathbb{Z}/p\mathbb{Z})^\times$의 크기가 $p-1$임을 이용한다.
Williams의 알고리즘은 이를 확장하여,
이차 확장체 $\mathbb{F}_{p^2}$에서의 군 구조를 활용한다.

특히,
\[
\mathbb{F}_{p^2}^\times
\]
는 크기가 $p^2-1=(p-1)(p+1)$인 순환군이며,
이 안에서 norm이 $1$인 원소들의 집합은
차수가 $p+1$인 subgroup을 이룬다.
Williams $p+1$ 알고리즘은 이 부분군에서의 거듭제곱 연산을 통해
$p+1$을 제거하는 데 목적이 있다.

\paragraph{Lucas 수열과 연산 정의.}
실제로 $\mathbb{F}_{p^2}$에서의 연산을 직접 구현하지 않고,
Williams는 Lucas 수열을 이용하여 계산을 수행한다.
정수 $D$에 대해,
다음과 같은 Lucas 수열 $V_n(P,Q)$를 정의한다:
\[
V_0 = 2,\qquad V_1 = P,\qquad
V_{n} = P V_{n-1} - Q V_{n-2}.
\]
보통 $Q=1$로 두며,
이때 $V_n(P,1)$은 $\mathbb{F}_{p^2}$에서
노름이 $1$인 원소의 $n$제곱에 해당한다.

\paragraph{알고리즘의 구성.}
smoothness bound $B>0$를 정하고
\[
M = \mathrm{lcm}(1,2,\dots,B)
\]
로 둔다.
적절한 매개변수 $P$를 선택한 뒤,
Lucas 수열을 이용하여
\[
V_M(P,1) \pmod{N}
\]
을 계산한다.
그 다음
\[
d = \gcd\bigl(V_M(P,1)-2,\,N\bigr)
\]
을 계산한다.

만약
\[
1 < d < N
\]
이면 $d$는 $N$의 비자명한 인수이며,
$d=p$가 된다.

\paragraph{Lucas 수열.}
Williams $p+1$ 알고리즘은
확장체 $\mathbb{F}_{p^2}$에서의 거듭제곱 연산을
정수 연산으로 모사하기 위해
\emph{Lucas 수열}을 사용한다.
정수 $P,Q$에 대해 Lucas 수열 $V_n(P,Q)$는
\[
V_0 = 2,\qquad V_1 = P,\qquad
V_n = P V_{n-1} - Q V_{n-2}
\]
로 정의된다.
특히 $Q=1$인 경우,
$V_n(P,1)$은
\[
V_n = \alpha^n + \beta^n
\]
으로 표현되며,
여기서 $\alpha,\beta$는
$x^2 - Px + 1 = 0$의 근이다.

이때 $\alpha\beta=1$이므로
$\alpha$는 $\mathbb{F}_{p^2}^\times$의 원소이고,
$\beta=\alpha^{-1}$이다.
따라서
\[
V_n(P,1)=\alpha^n+\alpha^{-n}
\]
가 성립한다. 특히,
\[
\alpha^{p+1}=1 \quad\text{in } \mathbb{F}_{p^2}^\times
\]
가 성립하므로,
만약 $p+1\mid M$이면
\[
\alpha^M = 1
\]
이고 결과적으로
\[
V_M(P,1)=\alpha^M+\alpha^{-M}=1+1=2 \pmod{p}
\]
가 된다.

\paragraph{시간 복잡도 및 비교.}
Williams $p+1$ 알고리즘의 시간 복잡도는
Pollard $p-1$ 알고리즘과 동일하게
smoothness bound $B$에 의해 지배되며,
\[
O\bigl(B\cdot (\log^2 N)\bigr)
\]
로 평가된다.

\paragraph{성공 조건.}
Williams의 $p+1$ 알고리즘이 성공하려면, 마찬가지로
\[
p+1 \text{ 이 } B\text{-smooth}
\]
이어야 한다.
이 조건이 성립하면,
Lucas 수열의 성질에 의해
\[
V_M(P,1) \equiv 2 \pmod{p}
\]
가 되며, 높은 확률로 $\gcd(V_M(P,1)-2,N)=p$를 얻게 된다.

따라서 RSA 키 생성에서는, $p+1$, $q+1$ 또한 큰 소인수를
갖도록 설계하여야 한다.

\bibliographystyle{plain}
\bibliography{references}

\end{document}