IV. 곱셈 구조 · 10/16

모듈러 거듭제곱과 RSA

연속 제곱법, 공개키 암호

읽음 0/0 갱신 2026-06-30

개요 — 동기·문제의식

$5^{100000000000000}\bmod12830603$ 을 계산하라면 어떻게 할까? 직접 거듭제곱하면 결과가 우주의 원자 수보다 많은 자릿수를 가진다 — 종이는커녕 컴퓨터 메모리로도 감당 못 한다.¹ 그런데 이 계산은 암호학에서 매일 일어난다. 연속 제곱(successive squaring) 은 이 난제를 $O(\log k)$ 번의 곱셈으로 풀어내는 알고리즘이다. 그리고 "곱하긴 쉽고 인수분해는 어렵다"는 비대칭과 결합하면, 누구나 공개키로 암호화할 수 있지만 비밀키 없이는 절대 복호화할 수 없는 RSA 공개키 암호가 만들어진다. Fermat·Euler 정리가 순수하게 이론적인 정리에서 인터넷 보안의 기반으로 변신하는 지점이 바로 여기다.

직관

연속 제곱의 핵심 통찰은 단순하다: $a^k$ 를 구하려고 $a$ 를 $k-1$ 번 곱할 필요가 없다. $a^1, a^2, a^4, a^8,\dots$ 처럼 제곱을 거듭하면 지수가 매번 두 배가 되고, $k$ 의 이진법 전개가 어떤 거듭제곱들을 곱해야 하는지 정확히 알려준다. $k$ 가 $100$ 자리 수라도 이진수로는 약 $332$ 비트이므로, 표 하나(약 $332$ 줄)만 만들면 끝난다 — $\log_2 k$ 에 비례하는 일이지 $k$ 에 비례하는 일이 아니다.¹

RSA의 직관은 "자물쇠와 열쇠를 분리"하는 것이다. 자물쇠(공개키 $N,e$)는 누구나 가질 수 있고 메시지를 잠그는(암호화하는) 데 쓰지만, 열쇠(비밀키 $d$)가 없으면 못 연다. 자물쇠를 봐도 열쇠를 못 만드는 이유는 $N=pq$ 의 소인수 $p,q$ 를 알아야 $d$ 를 계산할 수 있는데, $N$ 만 보고 인수분해하는 것이 계산적으로 막막하기 때문이다(곱셈은 쉽고 인수분해는 어렵다).

정의

(연속 제곱, Algorithm 16.1) $a^k\bmod m$ 을 계산하려면:¹ 1. $k$ 를 이진 전개 $k=2^{u_0}+2^{u_1}+\cdots$ (즉 $0,1$ 비트열)로 쓴다. 2. $a^1, a^2, a^4, a^8,\dots\pmod m$ 의 표를 이전 값을 제곱해서 만든다(매번 $\bmod m$ 으로 줄이므로 다루는 수가 $m^2$ 을 넘지 않는다). 3. $k$ 의 이진 전개에서 $1$ 인 자리에 대응하는 표의 값들만 골라 곱하고 $\bmod m$ 으로 줄인다.

단계	횟수
표 만들기(제곱)	$\approx\log_2k$ 회
최종 곱셈	$\approx\log_2k$ 회
합계	$O(\log k)$ 회 곱셈 — $k$ 가 $1000$ 자리여도 약 $3322$ 회

(RSA 공개키 암호계, Diffie–Hellman 1976 / Rivest–Shamir–Adleman 1977)² 1. 큰 소수 $p,q$ 선택, $N=pq$, $\varphi(N)=(p-1)(q-1)$. 2. 공개 지수 $e$ 선택 ($\gcd(e,\varphi(N))=1$); 공개키 $(N,e)$. 3. 비밀 지수 $d\equiv e^{-1}\pmod{\varphi(N)}$ (확장 Euclid, 나눗셈과 최대공약수) — 비밀키. 4. 메시지를 $0\le x<N$ 인 정수로 부호화. 암호화 $c\equiv x^e\pmod N$. 복호화 $x\equiv c^d\pmod N$.

무엇을 공개하나	무엇을 비밀로 하나
$N$, $e$ (공개키)	$p$, $q$, $\varphi(N)$, $d$ (비밀키)

주요 정리

정리 (RSA 복호화의 정당성).² $\gcd(x,N)=1$ 이면 $c^d\equiv x^{ed}\pmod N$ 이고, $ed\equiv1\pmod{\varphi(N)}$ 이므로 Euler 정리에 의해 $x^{ed}=x^{1+k\varphi(N)}=x\cdot(x^{\varphi(N)})^k\equiv x\cdot1^k=x\pmod N$.

증명 보기

증명 스케치(일반 $x$, $\gcd(x,N)>1$ 인 경우 포함). $N=pq$ 가 서로 다른 소수의 곱일 때는 $x$ 가 $p$ 또는 $q$ 의 배수인 예외적인 경우도 성립한다. $\bmod p$ 로 보면: $p\mid x$ 이면 양변이 $0$, 자명히 성립. $p\nmid x$ 이면 $ed\equiv1\pmod{p-1}$ 이므로 Fermat 소정리로 $x^{ed}\equiv x\pmod p$. 같은 논법을 $\bmod q$ 에 적용하고, CRT로 두 합동을 합치면 $x^{ed}\equiv x\pmod{pq}$. 즉 메시지가 $p$ 나 $q$ 와 공약수를 가지는 (실제로는 거의 일어나지 않는) 경우도 RSA는 정확히 작동한다.

정리 (안전성의 근거, 인수분해 환원). 공격자가 $N,e$ 를 알아도 $\varphi(N)=(p-1)(q-1)=N-p-q+1$ 을 구하려면 $p+q$ 를 알아야 하고, $p+q$ 를 알면 $p,q$ 는 이차방정식 $X^2-(p+q)X+N=0$ 의 두 근이므로 $N$ 의 인수분해와 사실상 동치다.² 즉 "RSA를 깬다" $\Longleftrightarrow$ "$N$ 을 인수분해한다"(적어도 알려진 가장 직접적인 공격에서는). $50$–$100$ 자리 수는 현대 알고리즘으로 인수분해되지만, $100$ 자리 이상의 소수 두 개를 쓰면 현재 알려진 어떤 방법으로도 현실적 시간 안에 $N$ 을 인수분해할 수 없다.

왜 가설 $\gcd(e,\varphi(N))=1$ 이 필요한가. $d\equiv e^{-1}\pmod{\varphi(N)}$ 이 존재하려면 $e$ 가 $\varphi(N)$ 을 법으로 가역이어야 하고, 이는 정확히 $\gcd(e,\varphi(N))=1$ 일 때다(나눗셈과 최대공약수). 이 조건이 깨지면 복호화 지수 자체가 존재하지 않는다.

예제

예제 1 (연속 제곱, 새 사례). $5^{117}\bmod19$. $117=64+32+16+4+1$(이진 $1110101_2$). 표(제곱을 거듭): $$5^1\equiv5,\ 5^2\equiv6,\ 5^4\equiv17,\ 5^8\equiv4,\ 5^{16}\equiv16,\ 5^{32}\equiv9,\ 5^{64}\equiv5\pmod{19}.$$ $5^{117}=5^{64}\cdot5^{32}\cdot5^{16}\cdot5^4\cdot5^1\equiv5\cdot9\cdot16\cdot17\cdot5\pmod{19}$. 차례로 줄이면 $5\cdot9=45\equiv7$, $7\cdot16=112\equiv17$, $17\cdot17=289\equiv4$, $4\cdot5=20\equiv1\pmod{19}$. 답: $5^{117}\equiv1\pmod{19}$. (검산: $19-1=18$, $\gcd(5,19)=1$ 이므로 Fermat에 의해 $5^{18}\equiv1$; $117=18\cdot6+9$ 이지만 $5^9\bmod19$ 를 따로 계산해도 $1$ — 우연이 아니라 $5$ 가 $\bmod19$ 에서 위수 $9$ 의 원소이기 때문.)

예제 2 (Silverman의 RSA, 검증). $p=12553,\ q=13007$ → $N=163276871$, $\varphi(N)=163251312$. $k=79921$ 으로 인코딩한 "To be or not to be"가 $149419241,\ 62721998,\dots$ 로 암호화된다.² 직접 계산해도 $N=pq=163276871$, $\varphi(N)=N-p-q+1=163276871-12553-13007+1=163251312$ — 합치한다.

예제 3 (손으로 풀 수 있는 작은 RSA 전 과정). $p=7,\ q=13$: $N=91$, $\varphi(N)=6\cdot12=72$. $e=5$ ($\gcd(5,72)=1$ ✓). 확장 Euclid로 $d\equiv5^{-1}\equiv29\pmod{72}$ ($5\cdot29=145=2\cdot72+1$ ✓). 메시지 $x=8$ 을 암호화: $c=8^5\bmod91=32768\bmod91=8$... 다시 계산하면 $c\equiv8\pmod{91}$ 인지 직접 확인: $8^2=64$, $8^4=64^2=4096\equiv4096-45\cdot91=4096-4095=1\pmod{91}$, $8^5=8^4\cdot8\equiv1\cdot8=8\pmod{91}$. 즉 $c=8$(우연히 자기 자신으로 암호화됨, $8$ 이 $\bmod91$ 에서 위수 $4$ 인 원소이기 때문). 복호화: $c^d=8^{29}\bmod91$. $29=4\cdot7+1$, $8^4\equiv1$ 이므로 $8^{29}=(8^4)^7\cdot8\equiv1\cdot8=8\pmod{91}$ ✓ 원래 메시지 $8$ 회복.

예제 4 (지수가 우연히 자명한 경우의 함정). 예제 3처럼 $x$ 가 법에 대해 작은 위수를 가지면 암호문이 평문과 같아지는 등 패턴이 노출될 수 있다 — 이래서 실전 RSA는 $p,q$ 를 무작위 거대 소수로, 메시지를 패딩(OAEP 등)해 이런 우연한 구조를 없앤다. (이 위키는 순수 수학적 RSA만 다루며 실전 보안 디테일은 범위 밖.)

예제 5 (왜 인수분해가 어려운가 — 규모 감각). $N=10^{128}+1$ 형태의 $128$ 자리 수를 시행 나눗셈으로 인수분해하면 $\sim10^{64}$ 회의 나눗셈이 필요하다 — 현재 모든 컴퓨터를 합쳐도 우주 나이 안에 끝나지 않는다.³ 반면 $p,q$ 가 주어지면 곱 $N=pq$ 는 즉시 계산된다 — 바로 이 "곱셈은 빠르고 분해는 느리다"는 비대칭이 안전성의 전부다. prime distribution, 산술의 기본정리 참고.

예제 6 ($\gcd(x,N)>1$ 인 예외 케이스도 작동함을 확인). $N=91=7\cdot13$, $e=5,d=29$(예제 3과 동일 키)로 $x=7$(즉 $\gcd(x,N)=7\ne1$)을 암호화: $c=7^5\bmod91$. $\bmod7$: $7\equiv0$ 이므로 $c\equiv0\pmod7$. $\bmod13$: $7^5\bmod13$, Fermat으로 $7^{12}\equiv1$, $7^5$ 는 그대로 계산 — $7^2=49\equiv10,\ 7^4\equiv100\equiv9,\ 7^5\equiv9\cdot7=63\equiv11\pmod{13}$. CRT로 합치면 $c\equiv63\pmod{91}$ (직접 검산: $7^5=16807=184\cdot91+63$ ✓). 복호화 $c^d=63^{29}\bmod91$ 도 같은 방식(또는 정리에 의해 자동으로) $7$ 을 되돌린다 — $x$ 가 $N$ 과 공약수를 가져도 정리가 보장하는 대로 RSA가 깨지지 않는다.

흔한 오해와 함정

"$e$ 는 아무 수나 된다" — 틀림. $e$ 는 반드시 $\varphi(N)$ 과 서로소여야 역원 $d$ 가 존재한다. $\gcd(e,\varphi(N))>1$ 이면 $x^e\bmod N$ 이 가역 연산이 아니어서 서로 다른 메시지가 같은 암호문으로 충돌할 수 있다.
"$N$ 을 비밀로 하면 더 안전하다" — 거꾸로다. $N,e$ 는 공개되어야 누구나 암호화할 수 있다(공개키 암호계의 정의). 비밀로 지켜야 하는 것은 $p,q,\varphi(N),d$ 뿐이다.
"$\varphi(N)$ 을 구하지 않고도 $d$ 를 구할 수 있다" — 알려진 가장 직접적인 경로는 $\varphi(N)$ 을 거치며, 이는 $N$ 의 인수분해와 동치다. 따라서 안전성은 전적으로 인수분해의 어려움에 의존한다(다른 공격 경로가 전혀 없다는 뜻은 아니다 — 키 생성·패딩 부주의로 깨진 실전 RSA 사례도 많다. 이는 구현의 문제이지 수학 자체의 결함은 아니다).
연속 제곱을 "그냥 $a$ 를 $k$ 번 곱하는 더 빠른 트릭" 정도로 오해 — 핵심은 곱셈 횟수가 $k$ 에서 $\log_2k$ 로 지수적으로 줄어든다는 점이다. $k$ 가 두 배가 돼도 연속 제곱은 한 단계만 늘어나지만, 직접 곱셈은 곱셈 횟수가 두 배로 는다.
암호화·복호화 지수를 혼동 — $c\equiv x^e\pmod N$ (공개키로 암호화), $x\equiv c^d\pmod N$ (비밀키로 복호화). $e,d$ 의 역할을 바꾸면 정의가 깨진다(단, $ed\equiv1\pmod{\varphi(N)}$ 의 대칭성 덕에 RSA는 서명 등 반대 순서로도 쓸 수 있다 — 이는 응용의 영역).

큰 그림 / 연결

연속 제곱은 Fermat·Euler 정리가 "지수를 $p-1$ 또는 $\varphi(m)$ 으로 줄여도 된다"고 보장하는 사실과 짝을 이루어, 임의로 큰 거듭제곱을 손바닥 위에서 다루게 해준다. RSA의 복호화 정당성은 정확히 Euler 정리의 응용이고, 비밀키 $d$ 를 계산할 때는 확장 Euclid 알고리즘으로 모듈러 역원을 구한다. 안전성은 소수 분포가 큰 소수를 풍부하게 제공한다는 사실과 소수판정이 그런 소수를 실용적으로 찾아준다는 사실 위에 서 있다. 복호화를 더 빠르게 만들 때는 CRT로 $\bmod p$, $\bmod q$ 두 개의 작은 계산으로 쪼갠다(예제 6의 풀이 방식이 바로 이 기법). 더 짧은 키로 같은 안전성을 얻으려는 현대적 시도가 타원곡선 암호(ECC)다 — 인수분해 대신 타원곡선 이산로그 문제의 어려움에 기댄다.

연습문제

$3^{20}\bmod7$ 을 연속 제곱으로 구하라.
$p=5,q=11$ 로 $N,\varphi(N)$ 을 구하고 $e=3$ 의 $d$ 를 찾아라.
위 키로 $x=4$ 를 암호화·복호화하라.
$\bmod13$ 에서 $2^{100}$ 을 연속 제곱으로 구하라.
RSA에서 $e$ 가 $\varphi(N)$ 과 서로소여야 하는 이유를 설명하라.
$6^{55}\bmod23$ 을 연속 제곱(이진 전개 $55=110111_2$)으로 구하라.
$p=11,q=17$ 의 RSA에서 $e=7$ 에 대응하는 $d$ 를 구하라($\varphi=160$).
$\gcd(x,N)>1$ 인 메시지에 대해서도 RSA 복호화가 작동함을 $N=15$($p=3,q=5$), $e=7$($\varphi(15)=8$), $x=6$ 으로 직접 확인하라.

힌트 / 정답

$3^6\equiv1\pmod7$ → $3^{20}=3^{18}\cdot9\equiv1\cdot2=2$.
$N=55$, $\varphi=4\cdot10=40$; $d\equiv3^{-1}\equiv27\pmod{40}$ (∵$3\cdot27=81\equiv1$).
$c=4^3=64\equiv9\pmod{55}$; 복호 $9^{27}\bmod55\equiv4$.
$2^{12}\equiv1\pmod{13}$; $100=12\cdot8+4$ → $2^4=16\equiv3$.
$d=e^{-1}\bmod\varphi(N)$ 이 존재하려면 $\gcd(e,\varphi(N))=1$ 필요(역원 존재 조건, 나눗셈과 최대공약수).
$55=32+16+4+2+1$. $\bmod23$: $6^1=6,6^2=13,6^4=169\equiv8,6^8=64\equiv18,6^{16}=324\equiv2,6^{32}=4$. $6^{55}=6^{32}\cdot6^{16}\cdot6^4\cdot6^2\cdot6^1\equiv4\cdot2\cdot8\cdot13\cdot6\pmod{23}$. $4\cdot2=8$, $8\cdot8=64\equiv18$, $18\cdot13=234\equiv234-10\cdot23=4$, $4\cdot6=24\equiv1$. 답 $1$.
$d\equiv7^{-1}\pmod{160}$. $7\cdot23=161\equiv1\pmod{160}$ → $d=23$.
$\bmod3$: $x=6\equiv0$ → $0^7\equiv0$, 복호 $0^{?}\equiv0\equiv6\pmod3$ ✓(둘 다 $0$). $\bmod5$: $6\equiv1$ → $1^7\equiv1$; 비밀키 $d\equiv7^{-1}\pmod8$, $7\cdot7=49\equiv1\pmod8$ → $d=7$; $1^7\equiv1\equiv6\pmod5$ ✓. CRT로 합치면 $c\equiv6\pmod{15}$, 복호화도 $6$ 으로 되돌아옴 — 정리대로 작동.