118. CRT (Chinese Remainder Theorem, 중국인의 나머지 정리)

⚠️ 이 문서는 해커가 암호문 덩어리를 통째로 서버에 던졌을 때 서버가 무거운 거북이(RSA 순정 복호화)처럼 끙끙대며 푸는 대신, 데이터를 두 개의 가벼운 덩어리로 쪼개어 번개처럼 빠르게 풀어버린 뒤 다시 하나로 찰싹 합쳐버리는, RSA 서버 효율을 4배 폭증시키는 마법의 최적화 엔진 CRT를 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: CRT(중국인의 나머지 정리)는 아주 거대한 수(예: $N=p \times q$)를 기준으로 한 복잡한 나머지 연산을, 작고 가벼운 두 개의 소수($p$와 $q$)를 기준으로 한 두 개의 쉬운 연산으로 쪼갠 뒤 나중에 하나의 정답으로 합치는 고대 중국의 수학적 편법이다.
  2. 가치: 모바일 앱이나 웹 서버가 수만 명의 사용자에게 RSA 복호화나 전자서명($M = C^d \pmod N$)을 날릴 때, 무거운 $N$ 덩어리로 한 번에 계산하는 대신 $p$와 $q$로 쪼개어 계산(CRT 적용)함으로써 CPU 연산 속도를 무려 4배나 기적처럼 폭발적 상승시킨다.
  3. 한계/융합: 극강의 스피드를 얻었지만, 부작용으로 서버가 쪼개서 계산하는 중간 과정에 해커가 전기 충격(오류 주입 공격, Fault Injection)을 가하면 치명적인 비밀키 단서가 줄줄 새어나오는 취약점(벨칼 공격)이 생겨, 현대 아키텍처는 이를 막기 위한 무결성 쉴드를 추가로 융합해야만 한다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

자물쇠를 잠그는 RSA 암호화($M^e \pmod N$)는 $e$값이 보통 65537처럼 작은 숫자라서 서버가 1초도 안 되어 뚝딱 처리한다. 문제는 자물쇠를 여는 **RSA 복호화나 내가 도장을 찍는 전자서명 ($C^d \pmod N$)**이다. 이 해독 열쇠 $d$는 600자리가 꽉 차는 어마무시한 괴물 숫자다. 네이버 같은 거대 웹 서버에 1만 명이 동시에 접속해 HTTPS 연결을 시도하면, 서버는 1만 번의 괴물 같은 서명($d$ 거듭제곱)을 하다가 램과 CPU가 타버리며 뻗어버린다.

"결과는 똑같게 유지하면서 이 무식한 해독 속도를 획기적으로 줄일 꼼수 없을까?" 암호학자들은 3세기에 중국의 수학자 손자가 쓴 산술서에서 기가 막힌 꼼수를 주워왔다. "거대한 바윗덩어리($N$) 한 개로 낑낑대며 계산하지 말고, 바윗덩어리의 원래 재료였던 두 개의 주먹돌($p$와 $q$)로 쪼개서 각각 가볍게 계산한 뒤, 나중에 중국인 마법 공식으로 딱 풀칠해서 합쳐버리자!" 이것이 바로 RSA-CRT다.

📢 섹션 요약 비유: 100kg짜리 돌덩이(N)를 혼자서 산꼭대기까지 들고 올라가는 게 기존의 무식한 RSA 복호화입니다. CRT는 이 돌을 50kg짜리 조각 2개($p, q$)로 쪼갠 뒤, 양손에 하나씩 가볍게 들고 뛰듯이 올라가서 꼭대기에서 본드로 찰싹 붙이는 엄청난 속도 최적화 요령입니다.

Ⅱ. CRT의 작동 원리: 쪼개고 합치기 (Divide and Conquer)

본래 서버가 계산해야 할 무식한 공식은 이렇다: $M = C^d \pmod N$. (단, $N = p \times q$)

CRT를 적용한 똑똑한 서버는 이 공식을 통째로 계산하지 않고 비밀의 방에서 꺼내온 $p$와 $q$를 활용해 다음과 같이 처리한다.

1단계: 작게 쪼개어 가볍게 계산 (Divide)

  • 거대한 $N$(600자리) 대신, 그 절반 크기인 소수 $p$(300자리) 세상과 $q$(300자리) 세상으로 문제를 2개 분리한다.
  • 해독 열쇠 $d$ 도 $p-1$ 과 $q-1$ 로 나누어 반 토막 낸 작고 귀여운 $d_P$, $d_Q$ 로 바꾼다.
  • 계산 1: $M_1 = C^{d_P} \pmod p$ (속도가 엄청 빠름)
  • 계산 2: $M_2 = C^{d_Q} \pmod q$ (역시 속도가 엄청 빠름)

2단계: 마법의 짬뽕 공식으로 합치기 (Combine)

  • 이제 가볍게 얻어낸 결과물 두 개($M_1, M_2$)를 고대 중국인의 CRT 공식을 활용하여 촥! 하고 비벼버린다.
  • 결과: 놀랍게도 이 짬뽕 된 결과물은 우리가 무식하게 $C^d \pmod N$ 을 통째로 계산해서 얻은 원본 평문 $M$과 단 1비트의 오차도 없이 완벽하게 똑같이 튀어나온다.
┌───────────────────────────────────────────────────────────────────────────────┐
│           순정 RSA vs RSA-CRT 최적화 연산 속도 및 아키텍처 비교               │
├───────────────────────────────────────────────────────────────────────────────┤
│                                                                               │
│ 🐢 [ 무식한 오리지널 RSA 복호화 ]                                             │
│   거대 암호문 C ───(600자리 괴물 열쇠 d 로 무한 거듭제곱)───▶ 복구된 평문 M   │
│   * 결과: 너무 무거워서 연산 속도 최악. 서버 뻗을 지경.                       │
│                                                                               │
│ 🚀 [ 똑똑한 RSA-CRT 병렬 복호화 ]                                             │
│                 ┌──▶ (p 세상에서 가벼운 d_P 로 풀기) ──▶ M1 ──┐               │
│   거대 암호문 C ──┤                                       ├ 합체!             │
│                 └──▶ (q 세상에서 가벼운 d_Q 로 풀기) ──▶ M2 ──┘               │
│                                                          ▼                    │
│                   고대 중국 수학 공식(CRT)으로 본드칠 ───▶ 완벽한 평문 M      │
│                                                                               │
│ ★ 기적의 속도업 (x4):                                                         │
│   숫자 길이가 반으로 줄면 컴퓨터의 곱셈 시간은 1/4로 줄어드는 마법칙 덕분에,  │
│   두 개로 쪼개서 풀어도 원래보다 **4배 더 빠르게** 해독 완료!                 │
└───────────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] "두 개로 쪼개서 두 번 풀면 결국 시간이 2배 걸리는 거 아닌가요?" 초보자들의 착각이다. 컴퓨터 연산에서 숫자의 길이가 $1/2$ 로 줄어들면, 덧셈이나 곱셈에 걸리는 시간은 $1/4$ 로 급격하게 줄어든다(2차 방정식의 원리). 따라서 $1/4$ 시간짜리 계산을 두 번(p와 q) 하더라도, 결국 총소요 시간은 원래 통째로 하던 시간의 딱 **반의반(1/4)**밖에 안 걸린다. 서버 퍼포먼스가 400% 폭발하는 이유다.

  • 📢 섹션 요약 비유: 10층짜리 블록 탑을 한 번에 쌓으려니 손이 덜덜 떨려서 1시간이 걸렸습니다. CRT는 친구랑 둘이서 바닥에서 각각 5층짜리 탑을 5분 만에 뚝딱 만든 뒤, 하나를 번쩍 들어서 위에 찰칵! 하고 합체시켜 총 10분 만에 10층 탑을 완성하는 기가 막힌 잔머리입니다.

Ⅲ. 치명적 급소 (벨칼 공격, Bellcore Attack)

CRT 덕분에 세상의 모든 웹 서버(Nginx, Apache)는 날개를 달았다. 라이브러리(OpenSSL) 설정엔 무조건 RSA-CRT 모드가 기본으로 켜져 있다. 하지만 1997년 댄 보네(Dan Boneh)가 CRT의 소름 끼치는 부작용을 찾아냈다. "계산 과정 하나를 망가뜨리면 비밀키가 토해져 나온다(Fault Injection Attack)!"

  1. 오류 주입 공격: 해커가 서버 컴퓨터의 전압을 순간적으로 살짝 낮추거나, 레이저를 쏴서 CPU를 괴롭힌다.
  2. 반쪽의 실패: 서버가 $p$ 세상 계산($M_1$)과 $q$ 세상 계산($M_2$)을 하다가, 해커의 레이저에 맞아 $p$ 쪽 계산만 값이 꼬이고(에러), $q$ 쪽 계산은 정상적으로 마쳐서 둘을 합쳐버린다.
  3. 기형아 탄생: 서버가 뱉어낸 '기형 서명(에러가 섞인 암호문)'과 '정상 서명'을 해커가 훔쳐서 최대공약수(GCD) 연산 한 번만 쓱 돌리면? 놀랍게도 시스템의 심장인 비밀 소수 $q$ 값이 화면에 벌거벗은 채로 튀어나온다. 비밀키($d$)가 완벽히 탈탈 털린 것이다.

실무 방어책: 오늘날 서버들은 CRT로 초스피드 서명을 찍어내고 나서, 그걸 사용자에게 바로 던져주지 않는다. 자기가 깐 꼼수가 실수 없이 잘 합쳐졌는지, 자기의 공개키($e$)로 한 번 슬쩍 검산(Verify)해 본다. 정상이면 내보내고, 1비트라도 깨진 기형아라면 입을 꾹 닫고 에러를 뿜어 해커의 유출 공격(Drop)을 방어한다.

Ⅳ. 결론

"이론 암호학이 공학적 최적화를 만나 현실의 벽(퍼포먼스)을 돌파한 빛나는 사례." 수학 교과서에만 존재하던 3세기의 중국인의 나머지 정리(CRT)는 21세기 디지털 세상의 목구멍을 틔워준 메시아다. 이 가볍고 우아한 쪼개기 마법 덕분에 스마트폰의 콩알만 한 배터리로도 무거운 전자서명과 인터넷 결제를 1초 안에 펑펑 날릴 수 있게 되었다. 비록 오류 주입이라는 부작용을 안고 있지만, 가벼운 검증 로직 한 줄만 덧대면 400%의 속도 향상이라는 달콤한 과실을 영원히 누릴 수 있는 현대 암호 공학의 절대 필수 탑재(Default) 엔진이다.

📌 관련 개념 맵

  • 전제 지식: RSA 복호화 및 서명 원리, 모듈로 연산
  • 수학적 목표: 연산 복잡도(Time Complexity) 감소, 퍼포먼스(Throughput) 최적화
  • 치명적 부작용: 오류 주입 공격 (Fault Injection Attack) / 하드웨어 결함 유도 공격
  • 방어 융합: 서명 생성 후 자체 검증(Verification) 로직 필수 추가

👶 어린이를 위한 3줄 비유 설명

  1. 비밀 편지(암호)를 풀 때, 큰 돋보기 한 개로 끙끙대며 100글자를 다 읽으려면 1시간이 걸려서 너무 힘들었어요.
  2. 그래서 똑똑한 요리사가 큰 돋보기를 반으로 쪼개서 양손에 들고(CRT 최적화), 편지를 반반씩 나눠서 휙휙 읽은 다음 머릿속에서 하나로 딱! 합쳤더니 무려 4배나 빨리 읽어냈죠.
  3. 다만, 한쪽 돋보기에 먼지가 묻어 글자를 잘못 합치면(오류 주입 공격), 도둑한테 내 진짜 비밀번호 단서를 흘려버릴 수 있어서 다 풀고 나서 꼭 한 번 다시 읽어봐야(검증) 한답니다!