Skip to content
Beside the Wheel

타원곡선

수학
대수학

y^2 = x^3 + ax + b

image

  • 그래프가 타원 모양은 아니고, 타원의 호 길이를 구하는 타원 적분의 역함수에서 나타나는 형태라 타원 곡선으로 불린다.

  • 타원 곡선에서 점 덧셈: 곡선 위의 두 점에 대해 어떤 연산을 거쳐 곡선에 존재하는 제 3의 점을 얻는 과정

    • 일반 덧셈 연산과 유사한 몇 가지 성질을 만족한다.
      • 항등원 존재 (I + A = A가 되는 점 I, 무한원점이라 부름)
      • 역원 존재 (A + (-A) = I임)
      • 교환법칙 성립
      • 결합법칙 성립

점 덧셈 공식

타원곡선 위의 두 점 P₁(x₁, y₁)과 P₂(x₂, y₂)에 대한 덧셈 P₃ = P₁ + P₂는 다음과 같이 계산된다.

경우 1: P₁ ≠ P₂인 경우 (점 덧셈)

결과 좌표

x₃ = s² - x₁ - x₂
y₃ = s(x₁ - x₃) - y₁

공식 유도 과정

  • 타원 곡선에서 점 덧셈의 정의가

    • 두 점 P₁과 P₂를 지나는 직선을 그린다
    • 이 직선이 타원곡선과 만나는 제3의 점을 찾는다
    • 그 점을 x축에 대해 대칭이동한 점이 P₃ = P₁ + P₂이다

  • 이므로, 두 점 P₁(x₁, y₁)과 P₂(x₂, y₂)를 지나는 직선의 방정식을 먼저 구하면

    y = s(x - x₁) + y₁

  • 직선의 방정식을 타원곡선 방정식 y² = x³ + ax + b에 대입하면

    [s(x - x₁) + y₁]² = x³ + ax + b
    -> s²(x - x₁)² + 2s(x - x₁)y₁ + y₁² = x³ + ax + b
    -> x³ - s²x² + (a + 2s²x₁ - 2sy₁)x + (b - s²x₁² + 2sx₁y₁ - y₁²) = 0

  • 비에트의 정리(Vieta’s formulas)를 적용하면

    • 3차 방정식 x³ + px² + qx + r = 0의 세 근을 α, β, γ라 할 때, 근과 계수의 관계는

      • α + β + γ = -p (세 근의 합 = x² 계수의 음수)
      • αβ + βγ + γα = q (두 근씩 곱한 합 = x 계수)
      • αβγ = -r (세 근의 곱 = 상수항의 음수)

    • 위에서 얻은 3차 방정식 x³ - s²x² + (a + 2s²x₁ - 2sy₁)x + ... = 0에서

      • x² 계수가 -s²이므로 p = -s²
      • 세 근이 x₁, x₂, x₃’이므로
      • 비에트의 정리에 의해: x₁ + x₂ + x₃' = -p = -(-s²) = s²
    x₁ + x₂ + x₃' = s²

  • 따라서

    x₃ = s² - x₁ - x₂
    y₃ = -y₃' = s(x₁ - x₃) - y₁

경우 2: P₁ = P₂인 경우 (점 두배)

  • 기울기 계산

    s = (3x₁² + a) / (2y₁)

    여기서 a는 타원곡선 방정식 y² = x³ + ax + b의 계수이다.

  • 결과 좌표

    x₃ = s² - 2x₁
    y₃ = s(x₁ - x₃) - y₁

경우 3: 특수한 경우

  • P₁ = I: P₁ + P₂ = P₂
  • P₂ = I: P₁ + P₂ = P₁
  • x₁ = x₂이고 y₁ = -y₂인 경우: P₁ + P₂ = I

점 덧셈 공식 유도 과정

1. 기하학적 해석

점 덧셈의 기하학적 의미는 다음과 같다:

  1. 두 점 P₁과 P₂를 지나는 직선을 그린다
  2. 이 직선이 타원곡선과 만나는 제3의 점을 찾는다
  3. 그 점을 x축에 대해 대칭이동한 점이 P₃ = P₁ + P₂이다

2. 대수적 유도 (P₁ ≠ P₂인 경우)

  • 두 점 P₁(x₁, y₁)과 P₂(x₂, y₂)를 지나는 직선의 방정식은 (기울기 s = (y₂-y₁) / (x₂-x₁))

    y = s(x - x₁) + y₁

  • 직선의 방정식을 타원곡선 방정식 y² = x³ + ax + b에 대입:

    [s(x - x₁) + y₁]² = x³ + ax + b
    -> s²(x - x₁)² + 2s(x - x₁)y₁ + y₁² = x³ + ax + b
    -> s²x² - 2s²x₁x + s²x₁² + 2sxy₁ - 2sx₁y₁ + y₁² = x³ + ax + b
    -> 0 = x³ + ax + b - s²x² + 2s²x₁x - s²x₁² - 2sxy₁ + 2sx₁y₁ - y₁²
    -> 0 = x³ - s²x² + (a + 2s²x₁ - 2sy₁)x + (b - s²x₁² + 2sx₁y₁ - y₁²)

  • 비에타의 정리(Vieta’s formulas)는 다항식의 근과 계수 사이의 관계를 나타낸다. 여기서 근이 같은 두 방정식의 미지수 x의 같은 차수의 계수들은 서로 같아야 하므로 이 방정식을 표준 형태 (x-α)(x-β)(x-γ) = x³-(α+β+γ)x²+(αβ+βγ+γα)x - αβγ = 0와 비교하면:

    • -(α+β+γ) = -s² (x² 계수)
    • 세 근은 x₁, x₂, x₃’ (직선과 타원곡선의 세 교점의 x좌표)

  • x₃' = s² - x₁ - x₂

  • y = s(x - x₁) + y₁를 이용하면 y₃' = s(x₃' - x₁) + y₁

  • 기하학적 정의에 따라 y₃’ = -y₃이므로: y₃ = -y₃' = -s(x₃ - x₁) - y₁ = s(x₁ - x₃) - y₁

x₃ = s²-x₁-x₂
y₃ = s(x₁-x₃) - y₁

P₁ = P₂인 경우

  • P₁ = P₂인 경우, 즉 점 접선의 기울기는 암시적 미분으로 구한다

    y² = x³ + ax + b
    2y(dy/dx) = 3x² + a
    dy/dx = (3x² + a) / (2y)
    

    s = (3x₁² + a) / (2y₁)

  • 이후 과정은 일반 덧셈과 동일하다. 단, x₁ = x₂이므로

x₃ = s²-2x₁
y₃ = s(x₁-x₃) - y₁

유한체에서의 점 덧셈

유한체 𝔽ₚ 위의 타원곡선에서는 모든 연산이 mod p로 수행된다:

s = (y₂ - y₁) × (x₂ - x₁)⁻¹ (mod p)
x₃ = s² - x₁ - x₂ (mod p)
y₃ = s(x₁ - x₃) - y₁ (mod p)

여기서 나눗셈은 곱셈의 역원을 곱하는 것으로 대체된다 (페르마의 소정리 이용).

  • 유한체에서 정의된 타원 곡선
    • 유한체 위의 타원곡선은 좌표 (x, y)가 모두 유한체의 원소인 점들의 집합임
    • modular 연산이 적용되기 때문에 (접힌 점들이 포함되어서) 일반적인 그래프와 모양이 달라보일 수 있다
    • y^2항 때문에 y축의 중간값(100)을 지나는 수평축을 기준으로 대칭

스칼라 곱셈

  • 스칼라 곱셈은 타원곡선 위의 한 점을 여러 번 더하는 연산이다.

    • 표기: nP = P + P + ... + P (n번)
    • 예시: 3P = P + P + P

  • 어떤 점에 스칼라 값을 계속 증가시키면서 곱하면 무한원점에 도달한다.

  • 스칼라 곱셈은 단순히 반복 덧셈으로 계산하면 비효율적이므로, 이진 표현을 이용한 Double-and-Add 알고리즘을 사용한다. 이 방법을 사용하면 O(n) 대신 O(log n) 시간에 계산할 수 있다.

    예시: 7P를 계산하는 경우
    7 = 111₂ (이진수)
    

    1. P (1₂)
    2. 2P = P + P (10₂)
    3. 3P = 2P + P (11₂)
    4. 6P = 2(3P) (110₂)
    5. 7P = 6P + P (111₂)

  • 타원곡선 이산 로그 문제(ECDLP, Elliptic Curve Discrete Logarithm Problem)는 다음과 같이 정의된다:

    • 타원곡선 위의 두 점 P와 Q가 주어졌을 때
    • Q = nP를 만족하는 정수 n을 찾는 문제
    • 여기서 P는 base point(생성점), Q는 결과 점, n은 찾고자 하는 스칼라

  • 일반적인 유한체에서의 이산 로그 문제와 비교하여, 타원곡선 이산 로그 문제는 더 어렵다

    • 일반 DLP: Index Calculus 등의 준지수(subexponential) 알고리즘 존재
    • ECDLP: Baby-step Giant-step, Pollard’s rho 등 O(√n) 알고리즘이 최선
    • 여기서 n은 타원곡선 위 점의 개수(order)
    • 따라서 동일한 보안 수준을 달성하기 위해 타원곡선 암호가 더 짧은 키 길이를 사용할 수 있다.

  • 타원곡선 연산은 계산이 비대칭적이라는 성질도 있다

    • 순방향은 쉬움 (n과 P가 주어졌을 때 Q = nP를 계산하는 것)
      • Double-and-Add 알고리즘으로 O(log n) 시간에 계산 가능
    • 역방향은 어려움 (P와 Q가 주어졌을 때 n을 찾는 것)
      • 현재 알려진 가장 효율적인 알고리즘도 지수 시간 복잡도
      • 유한체의 크기가 충분히 크면 사실상 계산 불가능

참고

관련글
wastomcat 구성요소was웹서버와 WAS대수학체통계학t-value통계학윌콕슨 순위합 검정수학곱셈공식