타원 곡선 암호화(ELLIPTIC CURVE CRYPTOGRAPHY)

1. 기본 개념

타원 곡선은 유한체 𝔽_q 위에서 다음 Weierstrass 방정식을 만족하는 점들의 집합으로 정의되며, 무한 원점을 포함해 아벨 군 구조를 형성한다:
$$
y^2 = x^3 + ax + b,\quad 4a^3 + 27b^2 \neq 0
$$
이 곡선 위에서 정의된 군 연산(점 덧셈·스칼라 곱셈)을 이용해 공개키 암호화가 가능하다 [get_url_content][1].

2. 군 연산

• 점 덧셈(P + Q): P, Q를 지나는 직선이 곡선과 만나는 점 R′를 x축에 대칭 이동해 R = P + Q로 정의한다.
• 점 이중화(2P): P에서의 접선이 곡선과 만나는 점 R′를 대칭 이동해 2P로 정의한다.
• 스칼라 곱(xP): 덧셈 연산을 반복해 구하며 큰 정수 계수 스칼라 곱셈은 계산이 쉽지만, 이로부터 원래 스칼라 x를 구하는 것은 어려워 ECDLP(Elliptic Curve Discrete Logarithm Problem)를 형성한다 [2][3].

3. 유한체 위 타원 곡선

유한체 𝔽_q(주로 q가 소수 p 혹은 2^m) 위에 정의하며, Hasse 정리에 따라 곡선 위 점의 개수 N은
$$
|N – (q + 1)| \le 2\sqrt{q}
$$
를 만족한다. 이로써 안전한 곡선 파라미터(점의 순서) 선택이 가능하며, 이상적 곡선 검증 알고리즘(Schoof’s algorithm)도 존재한다 [4][5].

4. 불변량 및 판별식

• 판별식(Discriminant): Δ = –16(4a³ + 27b²). Δ ≠ 0일 때 곡선이 비특이(smooth)하다.
• j-불변량(j-invariant):
  $$
  j = 1728 \frac{4a^3}{4a^3 + 27b^2}
  $$
  동일한 j 값을 가지는 곡선은 대수적 동형(isomorphic)이다 [6][7].

5. 좌표 표현

• 아핀 좌표(Affine): 일반적인 (x,y) 표현.
• 프로젝트 좌표(Projective, Jacobian, Lopez–Dahab): z를 추가해 역연산(분수)의 비용을 제거, 점 덧셈·이중화 성능을 최적화한다 [8].

6. 주요 알고리즘

• 스칼라 곱셈: Double-and-Add, Montgomery Ladder 방식으로 구현하여 상수 시간(constant-time) 연산을 지원한다 [9].
• 타원곡선 이산로그 문제(ECDLP): 주어진 P, Q = kP에서 k를 찾는 문제로, Pollard Rho 기법이 최선의 일반적 공격법이다. 계산 복잡도는 $$O(\sqrt{n})$$이며, 곡선 차수 n 선택 시 보안 수준을 결정한다 [10][11].
• Schoof’s 알고리즘: Hasse 정리와 CRT를 이용해 𝔽_q 위 점 수를 다항식 시간에 계산한다 [5].

7. 보안성 및 파라미터

• 보안 수준: 256-bit ECC 키는 약 3072-bit RSA에 해당하는 보안을 제공한다.
• 곡선 선택: secp256k1, secp256r1(NIST P-256) 등 산업 표준 곡선과, Curve25519 같은 몽고메리 형(curve) 등이 사용된다 [1][3].
• 특수 공격: Pohlig–Hellman(약한 큰 인수 순서 분해), Weil/Tate pairing 공격(짧은 체 특수 곡선), anomalous curve 공격 등을 고려해야 한다 [11].

8. 결론

타원 곡선 암호화는 짧은 키로 높은 보안을 제공하며, 유한체 위 군 이론과 비교적 복잡한 수학 기반으로 설계된다. 점 연산 최적화, 다양한 좌표 표현, 안전한 곡선 파라미터, 그리고 최신 알고리즘이 결합해 현대 암호 시스템의 핵심으로 자리잡고 있다.

출처
[1] 타원곡선 암호 – 위키백과, 우리 모두의 백과사전 https://ko.wikipedia.org/wiki/%ED%83%80%EC%9B%90%EA%B3%A1%EC%84%A0_%EC%95%94%ED%98%B8
[2] 기초 암호학(4) – ECC(타원곡선 암호화 알고리즘) – 나를위한노트 https://developer-mac.tistory.com/83
[3] 타원곡선암호 (Elliptic Curve Cryptography) 정리 – 잉여의 생각저장소 https://chocolate-life.tistory.com/6
[4] Hasse’s theorem on elliptic curves – Wikipedia https://en.wikipedia.org/wiki/Hasse’s_theorem_on_elliptic_curves
[5] Schoof’s algorithm – Wikipedia https://en.wikipedia.org/wiki/Schoof’s_algorithm
[6] 1.5 Elliptic curve discriminant and j-invariant – Fiveable https://library.fiveable.me/elliptic-curves/unit-1/elliptic-curve-discriminant-j-invariant/study-guide/KqeAwJOVKLN6HoSR
[7] j-invariant – Wikipedia https://en.wikipedia.org/wiki/J-invariant
[8] [PDF] Projective Coordinates of Elliptic Curves – Koc Lab http://koclab.cs.ucsb.edu/teaching/ccs130h/2018/09projective.pdf
[9] Montgomery Ladder in ECC – Cronokirby https://cronokirby.com/notes/2021/04/montgomery-ladder/
[10] Implementation of Pollard Rho Attack on Elliptic Curve Cryptography … https://pubs.aip.org/aip/acp/article-pdf/doi/10.1063/1.4930641/12974838/030019_1_online.pdf
[11] [PDF] cryptrec: security level of cryptography – ecdlp mathematical problem https://www.cryptrec.go.jp/exreport/cryptrec-ex-1029-2001.pdf
[12] 타원곡선 알고리즘(ECC, Elliptic Curve Cryptography) https://swingswing.tistory.com/285
[13] [PDF] elliptic curve cryptography – Department of Mathematics https://math.uchicago.edu/~may/REU2017/REUPapers/CoatesWelsh.pdf
[14] [PDF] Chapter 4 – Elliptic Curves over Finite Fields – Koc Lab http://koclab.cs.ucsb.edu/teaching/ecc/eccPapers/Washington-ch04.pdf
[15] [PDF] Tropical Elliptic Curves and j-invariants. https://fse.studenttheses.ub.rug.nl/9772/1/Tropical_Elliptic_Curves.pdf
[16] [PDF] 18.783 Elliptic Curves Lecture 15 https://math.mit.edu/classes/18.783/2022/LectureSlides15.pdf
[17] [암호학] 4. 타원곡선암호 – velog https://velog.io/@jeong0982/%EC%95%94%ED%98%B8%ED%95%99-4
[18] 수학의 난제를 넘어 비트코인의 핵심 기술로, 타원곡선 암호 – Naver Blog https://blog.naver.com/with_msip/223030590993
[19] The j-invariant of an elliptic curve in Weierstrass normal form in … https://math.stackexchange.com/questions/3987656/the-j-invariant-of-an-elliptic-curve-in-weierstrass-normal-form-in-terms-of-its
[20] Bounding the modular discriminant of an elliptic curve in the j-invariant https://mathoverflow.net/questions/48544/bounding-the-modular-discriminant-of-an-elliptic-curve-in-the-j-invariant