Elliptic Curve Cryptography(ECC)

왜 타원 곡선(ECC)을 도입해야만 했는가? (Motivation)

기존의 곱셈 기반 DLP(RSA, Diffie-Hellman 등)는 높은 보안 수준을 유지하기 위해 기하급수적으로 긴 키 길이가 필요합니다. 하지만 ECC는 훨씬 짧은 키로 동일한 보안 수준을 달성할 수 있어 연산과 메모리 측면에서 압도적으로 효율적입니다.

앞서 우리가 일반 모듈러 연산($\mathbb{Z}_p^*$) 기반의 암호(RSA, 일반 Diffie-Hellman, Elgamal)가 1024 bits라는 거대한 키를 필요로 한다는 것을 배웠죠. 이 장은 그 한계를 극복하려는 수학자들의 아이디어입니다.

• Security Levels (보안 등급 비교 표): 이 표는 기말고사에서 ECC의 장점을 서술할 때 무조건 적어야 하는 핵심 근거입니다.

• 해커가 $2^{80}$번 연산해야 깰 수 있는 기본 보안 등급(80 bits security)을 달성하기 위해:

  • 기존 RSA / D-H: 1024 bits의 키가 필요함.
  • ECC: 단 160 bits의 키만 있으면 됨.

• 국가 기밀 수준인 Top Secret Level(192 bits security)을 달성하려면 RSA는 무려 7680 bits가 필요한 반면, ECC는 384 bits면 충분합니다.

Motivation & Idea (핵심 목표):

• 더 짧은 피연산자(Shorter operands)를 가지는 새로운 공개키(PK) 시스템을 찾자.
• 기존의 $\mathbb{Z}_p^*$ 공간보다 DLP 풀기가 훨씬 더 어려운 새로운 Cyclic group(순환 군)을 찾아내면, 키 길이를 확 줄일 수 있지 않을까? 그 해답이 바로 타원 곡선(EC)이 된 것입니다.

타원 곡선의 수학적 정의 (Definition of EC)

타원 곡선은 유한체 $Z_p$ (단, $P \ge 3$) 위에서 다음 방정식을 만족하는 점 $(X, Y)$들의 집합입니다.

The Equation (Weierstrass Equation):
$y^2 \equiv x^3 + ax + b \pmod p$

필수 조건 2가지 (Constraints):

• Point at Infinity ($\mathcal{O}$): 무한원점이라고 부르는 가상의 점이 반드시 포함되어야 합니다. 이 점은 나중에 ECC 덧셈 연산에서 숫자 '0'(항등원)과 같은 역할을 합니다.

• Non-singular condition: $4a^3 + 27b^2 \not\equiv 0 \pmod p$
  곡선이 뾰족해지거나(Cusp) 스스로 교차하는(Self-intersection) 이상한 점이 없도록 보장해 주는 판별식 조건입니다.

교수님의 밑그림 설명 (EX)
아래 그려진 원($x^2 + y^2 = r^2$)이나 타원($ax^2 + by^2 = r^2$) 그림은 "이름은 타원(Elliptic) 곡선이지만, 우리가 아는 기하학의 일반적인 타원형 모양이 절대 아니다"라는 것을 강조하기 위해 비교용으로 그려두신 겁니다. 실제 실수 범위에서의 타원 곡선은 물방울이 옆으로 누운 것 같거나 두 조각으로 나뉜 특이한 형태를 띱니다.

특징: X축을 기준으로 완벽하게 대칭(Symmetric)을 이룹니다. 기하학적으로는 연속된 선처럼 보이지만, 암호학에서는 $Z_p$ 상의 흩어진 정수 점(Discrete integer dots)들만 사용합니다.

왜 ECC를 쓰는가?" $\rightarrow$ "기존 그룹($\mathbb{Z}_p^*$)보다 DLP가 훨씬 어려워서, 훨씬 짧은 키(Shorter key)로 동일한 보안성(Security levels)을 제공하므로 계산과 메모리 측면에서 압도적으로 효율적이다."

타원 곡선의 기하학적 특징

• Symmetric to X-axis (X축 대칭): 가장 중요한 특징입니다! 식을 보면 $y^2 = x^3 + ax + b$ 이므로, $y$ 값을 풀면 무조건 $\pm$ (플러스/마이너스) 두 개의 값이 나옵니다. 즉, 곡선 위의 어떤 점 $P(x, y)$가 있다면, 무조건 그와 X축 대칭인 점 $(x, -y)$도 곡선 위에 존재합니다. 이 성질이 덧셈의 핵심이 됩니다.

• Cyclic Group을 위한 조건:

  • 원소(Elements): 곡선 위에 있는 점들의 $(x, y)$ 좌표 (정수)
  • 그룹 연산(Group operation): 일반적인 숫자 덧셈이 아니라, "점과 점을 더하는 특수한 기하학적 덧셈($P+Q$)"을 새롭게 정의해야 합니다.

Point Addition (점의 덧셈) & Point Doubling (점의 두 배)

이 그래프 필기는 두 가지의 다른 덧셈 방식을 보여주고 있습니다. 시험에서 그림을 주고 "이게 무슨 연산인지 설명하라"고 자주 나옵니다.

A. Point Addition ($P + Q = R$) : 서로 다른 두 점 더하기

1. 곡선 위의 두 점 $P$와 $Q$를 잇는 직선을 그립니다. (초록색 선)
2. 그 직선을 쭉 연장하면, 곡선과 만나는 제 3의 교점($(x_3, y_3)$ 빨간색 점)이 반드시 하나 생깁니다. (3차 방정식이므로 교점은 최대 3개)
3. 그 교점을 X축에 대해 대칭 이동(뒤집기) 시킵니다. ($y$ 부호만 반대로 바꿈: $(x_3, -y_3)$)
4. 뒤집혀서 찍힌 그 점이 바로 $P$와 $Q$를 더한 최종 결과값인 $R$입니다.

B. Point Doubling ($V + V = 2V$) : 같은 점 두 번 더하기

1. 점 $P$와 $Q$가 점점 가까워져서 완전히 하나로 합쳐진 점 $V$가 있다고 상상해 봅시다.
2. 이때는 두 점을 잇는 선이 아니라, 점 $V$에서의 접선(Tangent line)을 긋습니다. (파란색 선)
3. 마찬가지로 접선을 쭉 연장하여 곡선과 만나는 제 3의 교점을 찾습니다.
4. 그 교점을 X축에 대해 대칭 이동시키면, 그 점이 바로 $V$를 두 번 더한 결과값 $2V$가 됩니다.

Analytical Expression (수식으로 풀기 위한 빌드업)
그래프로 그리는 건 이해했으니, 이제 컴퓨터가 계산할 수 있도록 수식(Analytical expression)으로 만들어야 합니다.
Idea:타원 곡선 방정식 $E: y^2 = x^3 + ax + b$
두 점 $P, Q$를 지나는 직선 방정식 $\ell: y = s \cdot x + m$ (여기서 $s$는 기울기)
Find (교점 찾기): 두 방정식을 연립해서 풉니다. 직선의 $y$ 값을 곡선의 $y$ 자리에 대입합니다.
$(s \cdot x + m)^2 = x^3 + ax + b \pmod p$
이 3차 방정식을 풀면 세 개의 해($x_1, x_2, x_3$)가 나오는데, 우리가 이미 $P(x_1)$, $Q(x_2)$의 위치를 알고 있으므로 나머지 교점인 $x_3$ 좌표를 쉽게 계산해 낼 수 있습니다.

기말고사에서는 주로 "두 점 $P$와 $Q$의 좌표를 주고, 수식을 이용해 $P+Q$의 좌표를 구하라"는 계산 문제가 출제됩니다.

타원 곡선 덧셈 공식 (The Formula)

이 공식들은 무조건 달달 외우셔야 합니다. (오픈북이 아니라면요!)
두 점 $P(x_1, y_1)$와 $Q(x_2, y_2)$를 더해서 $R(x_3, y_3)$를 만드는 공식입니다.

최종 좌표 구하는 공식 (공통):

$x_3 \equiv s^2 - x_1 - x_2 \pmod p$

$y_3 \equiv s \cdot (x_1 - x_3) - y_1 \pmod p$

기울기 $s$ 구하는 공식 (상황에 따라 다름):
Add (서로 다른 두 점 더할 때, $P \neq Q$):

$s \equiv \frac{y_2 - y_1}{x_2 - x_1} \pmod p$

Double (같은 점을 두 번 더할 때, $P = Q$):

$s \equiv \frac{3x_1^2 + a}{2y_1} \pmod p$

(곡선 방정식 $y^2 = x^3 + ax + b$를 미분해서 얻은 접선의 기울기입니다. 여기서 $a$는 곡선 방정식의 계수입니다.)

[주의 사항 - Remarks & Neutral Element]

• 모듈러 연산에서 분수(나눗셈)는 그냥 나누는 게 아니라, 분모의 역원($^{-1}$)을 구해서 곱해야 합니다. (이게 계산 실수의 주범입니다!)
• 항등원(Neutral Element): $P + \mathcal{O} = P$ 를 만족하는 가상의 무한원점 $\mathcal{O}$가 존재합니다.
  - 역원(Inverse): 점 $P(x, y)$의 덧셈에 대한 역원은 $-P(x, -y)$ 입니다. 절대 $x$ 부호를 같이 바꾸면 안 됩니다!

기출 예상 계산 문제 풀이

문제: $\mathbb{Z}_{17}$ 에서 타원 곡선 $E: y^2 \equiv x^3 + 2x + 2 \pmod{17}$ 이 주어졌다. 점 $P = (5, 1)$ 일 때, 점 $P$를 두 배 한 값인 $2P$의 좌표를 구하시오.

$x_3 \equiv s^2 - x_1 - x_2 \pmod p$

$y_3 \equiv s \cdot (x_1 - x_3) - y_1 \pmod p$

[Step 1: 기울기 $s$ 구하기]
같은 점을 더하는 것(Doubling)이므로 미분 기울기 공식을 씁니다. 여기서 곡선의 계수 $a=2$ 이고, $P$의 좌표는 $x_1=5, y_1=1$ 입니다.

$s \equiv \frac{y_2 - y_1}{x_2 - x_1} \pmod p$

$s \equiv \frac{3x_1^2 + a}{2y_1} \pmod p$

• $s \equiv \frac{3(5)^2 + 2}{2(1)} \pmod{17}$
• $s \equiv \frac{75 + 2}{2} \equiv \frac{77}{2} \equiv \frac{9}{2} \pmod{17}$ ($77 = 17 \cdot 4 + 9$)
• 자, 이제 $2$로 나누는 대신 $2$의 모듈러 $17$ 역원을 곱해야 합니다. $2 \cdot 9 = 18 \equiv 1 \pmod{17}$ 이므로 $2$의 역원은 $9$입니다.
• $s \equiv 9 \cdot 9 = 81 \equiv \mathbf{13} \pmod{17}$ ($81 = 17 \cdot 4 + 13$)
  (기울기 $s = 13$ 을 무사히 구했습니다!)

[Step 2: 새로운 $x_3$ 좌표 구하기]

• $x_3 \equiv s^2 - x_1 - x_2 \pmod{17}$ (여기선 $P=Q$ 니까 $x_2$ 자리에도 $x_1$인 $5$가 들어갑니다.)
• $x_3 \equiv 13^2 - 5 - 5 \pmod{17}$
• $x_3 \equiv 169 - 10 = 159 \pmod{17}$
• $159 = 17 \cdot 9 + 6$ 이므로, $x_3 = \mathbf{6}$

[Step 3: 새로운 $y_3$ 좌표 구하기]

• $y_3 \equiv s(x_1 - x_3) - y_1 \pmod{17}$
• $y_3 \equiv 13(5 - 6) - 1 \pmod{17}$
• $y_3 \equiv 13(-1) - 1 = -14 \pmod{17}$
• 모듈러 연산에서 음수는 양수로 바꿔줘야 합니다. $-14 + 17 = 3$
  따라서, $y_3 = \mathbf{3}$

최종정답:
$2P = (5, 1) + (5, 1) = \mathbf{(6, 3)}$

기말고사 주의사항 (Common Mistakes)
교수님이 시험에서 학생들이 0점을 받는 가장 흔한 실수 두 가지를 직접 언급하셨습니다.

• 일반 산술 덧셈 금지: $P(5, 1)$일 때 $2P$를 구하라고 해서 $(5+5, 1+1) = (10, 2)$라고 적으면 100% 오답입니다. 반드시 위의 Point Doubling 공식을 사용해야 합니다.
• 음수 좌표 처리: 연산 결과로 $Y_3 = -14$ 같은 음수가 나왔을 때 그대로 적으면 안 됩니다. 타원 곡선 위의 점은 양수여야 하므로, 모듈러 연산을 적용해 양수로 바꿔주어야 합니다. (예: $-14 \equiv 3 \pmod{17}$)