ECDLP EC Discret Logarithm Problem

맨 위 그래프를 보면 $P$에서 시작해 $2P, 3P, 4P$를 지나며 점들이 곡선 위를 마치 당구공처럼 불규칙하게 튕겨 다니는 것을 볼 수 있습니다. 이것이 스칼라 곱셈($d \cdot P$)의 기하학적 모습입니다.

• Primitive Element (생성자): 예제에서 $P = (5, 1)$이 그룹의 모든 요소를 만들어내는 시작점 역할을 합니다.
• Wrap-around (순환의 완성): $P$를 계속 더해가다 보면 $18P = (5, 16)$이 됩니다. 모듈러 17의 세계에서 16은 $-1$과 같으므로($16 - 17 = -1$), 이 점은 $(5, -1)$ 즉 $-P$ (역원)가 됩니다.
• Point at Infinity ($\mathcal{O}$): $18P$가 $-P$이므로, 한 번 더 $P$를 더한 $19P = (-P) + P = \mathcal{O}$ (항등원)가 됩니다. $20P$부터는 다시 $P$로 돌아가며 무한히 반복됩니다.
• Group Cardinality ($\#E$): 이 타원 곡선 그룹 안에 존재하는 유효한 점의 총개수입니다. 이 예제에서는 19번 만에 제자리로 돌아오므로 $\#E = 19$가 됩니다. (모듈러 기준인 17과 그룹의 크기인 19는 완전히 다른 숫자임을 명심해야 합니다.)

암호학의 핵심, ECDLP

앞서 점이 불규칙하게 튕겨 다니는 성질을 이용해 만든 수학적 난제가 바로 ECDLP (Elliptic Curve Discrete Logarithm Problem)입니다.

• 문제 정의: 시작점 $P$와 도착점 $T$의 좌표를 알고 있을 때, 도대체 $P$를 몇 번 더해야($d$ 번) $T$에 도착하는지 그 횟수($d$)를 찾아내는 문제입니다. 식으로는 $T = d \cdot P$ 입니다.
• 암호 키와의 매핑 (기말 서술형 단골 포인트):
  • $d = \mathbf{Private\ Key} (K_{pr})$: 송신자만 몰래 알고 있는 정수(Integer) 값입니다. (예제에서 13에 해당)
  • $T = \mathbf{Public\ Key} (K_{pub})$: 네트워크에 모두 공개되는 타원 곡선 위의 점 좌표(Point on the curve)입니다. (예제에서 $(16, 4)$에 해당)
• 왜 안전한가? (One-way Function):
  • 비밀키 $d$를 알 때 공개키 $T$를 구하는 것($d \cdot P$)은 Double-and-Add 알고리즘으로 아주 빠르게 계산할 수 있습니다.
  • 하지만 해커가 공개키 $T$와 시작점 $P$만 보고 비밀키 $d$를 역추적하는 것은, $p$값이 160 bits 이상으로 커지면 사실상 우주 나이만큼의 시간이 걸려 불가능합니다.

왜 타원 곡선(ECC)이 기존 암호(RSA, DH)보다 훨씬 짧은 키로도 똑같이 안전한가?

타원 곡선 위의 점은 몇 개인가? (Hasse's Theorem)

Hasse's Theorem:
$p + 1 - 2\sqrt{p} \le \#E \le p + 1 + 2\sqrt{p}$

수식의 의미 (Very rough approximation):
교수님이 그려주신 막대그래프를 보세요. $p$가 160 bits 크기일 때, $\sqrt{p}$는 그 절반인 80 bits 크기밖에 안 됩니다. 160비트의 어마어마한 수에 비하면 80비트짜리 오차($2\sqrt{p}$)는 먼지 같은 수준($p \gg 1 + 2\sqrt{p}$)입니다.
따라서 타원 곡선 위 점의 총개수 $\#E$는 대략 모듈러 베이스인 $p$의 크기와 거의 같다고 봅니다. ($\#E \approx p$)

★ 시험 포인트 (Notes 부분):
대략적인 크기는 알지만, 특정 공격(Certain attacks)을 방어(thwart)하기 위해서는 $\#E$의 정확한 개수(Exact number)를 반드시 알아야 합니다. 하지만 이 정확한 개수를 알아내는 것 자체가 컴퓨터 연산상 매우 어렵습니다(Computationally difficult).

왜 160 bits면 충분한가? (The Hardness of ECDLP)

이 페이지가 가장 중요합니다. 앞서 수업에서 "현대 암호가 안전하려면 해커가 최소 $2^{80}$ steps의 연산을 하도록 만들어야 한다"고 배웠죠. 이를 ECC에 적용한 증명입니다.

ECDLP를 깨는 가장 빠른 방법:
현재 인류가 아는 가장 강력한 알고리즘(예: Pollard's rho)을 써도 ECDLP를 풀려면 대략 $\approx \sqrt{p}$ steps가 필요합니다.

수학적 증명 (서술형 답안용):
해커가 계산해야 하는 횟수 $\sqrt{p}$가 안전 기준인 $2^{80}$이 되도록 만들려면 $p$는 얼마가 되어야 할까요?
$2^{80} = \sqrt{p} \implies p = (2^{80})^2 = 2^{160}$
즉, $p$의 크기가 $2^{160}$, 비트 길이로는 고작 160 bits만 되면 $2^{80}$ 번의 연산을 강제할 수 있다는 뜻입니다.

최종 결론 (비교):

• ADD DLP (덧셈 기반인 ECC): 160 bits면 충분.
• Mul DLP (곱셈 기반인 일반 Diffie-Hellman / RSA): Index-Calculus 공격 때문에 무려 1024 bits가 필요.

"이것이 바로 스마트폰이나 IoT 기기처럼 메모리와 배터리가 부족한 환경에서 무거운 RSA 대신 가벼운 ECC가 현대 보안의 표준이 된 완벽한 이유입니다."

EC-DH (Elliptic Curve Diffie-Hellman)의 시작

결론적으로 이렇게 훌륭한 ECC를 가지고, 예전에 배웠던 Diffie-Hellman 키 교환을 똑같이 해보자는 것이 EC-DH입니다.

Phase I: Set-up (준비 단계):공개된 네트워크에 사용할 타원 곡선 방정식 $E$와, 모든 계산의 기준점이 될 Primitive element $P(x_p, y_p)$를 세팅합니다.

ECDH Protocol (타원 곡선 디피-헬먼 키 교환)

기존 곱셈 기반의 Diffie-Hellman을 덧셈 기반인 타원 곡선으로 그대로 가져온 프로토콜입니다.

Public Parameters: 앨리스와 밥은 타원 곡선 $E$와 생성자 점 Primitive element $P$를 공유합니다.
Key Generation:

• Alice: 개인키 $a$를 고르고, 공개키 $A = a \cdot P$를 계산해 전송합니다.
• Bob: 개인키 $b$를 고르고, 공개키 $B = b \cdot P$를 계산해 전송합니다.

Shared Secret (공통 비밀키 생성):

• Alice는 받은 $B$에 자신의 개인키 $a$를 곱해 $(X_{AB}, Y_{AB}) = a \cdot B$를 구합니다.
• Bob은 받은 $A$에 자신의 개인키 $b$를 곱해 $(X_{AB}, Y_{AB}) = b \cdot A$를 구합니다.

AES 연동 (Key Derivation): 공통 키가 만들어졌지만, ECC의 X좌표($X_{AB}$)는 보통 160 bits입니다. 우리가 C 언어 프로젝트로 짜려는 AES는 키 길이가 128 bits나 192 bits를 요구하죠. 크기가 안 맞습니다.

• 해결책: 160 bits 중 처음이나 끝의 128 bits만 잘라서 쓰거나, Hash Function을 돌려 원하는 길이로 맞춰서(Padding/Truncation) AES의 키로 사용합니다.

ECDH Example & Proof of Correctness

시험에 "ECDH가 왜 성립하는지 수식으로 증명하시오"라고 나오면 이 페이지 하단의 식을 적으시면 됩니다.

Proof of Correctness (정확성 증명):
$a \cdot B = a \cdot (b \cdot P) = (a \cdot b) \cdot P = (b \cdot a) \cdot P = b \cdot (a \cdot P) = b \cdot A$
결국 앨리스와 밥은 중간에 해커가 도청하더라도, 수학적 결합 법칙을 통해 완벽하게 똑같은 좌표 $(13, 10)$에 도달하게 됩니다.

• 현실적인 문제 제기: 예제에서는 $3 \cdot P$나 $10 \cdot P$처럼 숫자가 작아서 손으로 계산할 수 있지만, 실제 환경에서는 $a$ 값이 $2^{160}$에 달하는 어마어마한 숫자입니다. $P$를 우주 나이만큼 더하고 있을 수는 없겠죠? 이를 해결하기 위한 알고리즘이 바로 다음 장에 나옵니다.

Double-and-Add Algorithm ★기말고사 계산 문제 0순위★

앞서 중간고사 범위에서 거듭제곱을 빨리 하기 위해 배웠던 Square-and-Multiply 알고리즘을 타원 곡선 덧셈에 맞게 이름만 바꾼 것입니다. 이 표를 그리는 방식은 기말고사에 무조건 출제됩니다.

[예제 풀이: $26 \cdot P$ 계산하기]
1. Binary Conversion: 먼저 곱하려는 스칼라 값 26을 이진수로 바꿉니다. $\rightarrow \mathbf{11010_2}$
2. Scan (Left to Right): 가장 왼쪽 비트(MSB)부터 오른쪽으로 하나씩 읽어 내려갑니다.
3. Rule:

• 매 단계마다 무조건 이전 값을 두 배(Double, D) 합니다.
• 만약 현재 읽은 비트가 1이라면, $P$를 한 번 더 더해줍니다(Add, A). 비트가 0이면 더하지 않고 넘어갑니다.
  

결론적으로 26번의 덧셈을 무식하게 다 하는 것이 아니라, 단 4번의 Point Doubling과 2번의 Point Addition만으로 초고속 계산을 끝냈습니다. 하드웨어 엔지니어링 관점에서도 연산 사이클을 획기적으로 줄여주는 아주 우아한 로직이죠.