타원 곡선 암호화 : 간단한 소개

타원 곡선 암호화 개념 정리

본 글은 Andrea Corbellini의 Elliptic Curve Cryptography: a gentle introduction을 번역한 글입니다. 4편의 시리즈 중 첫 번째 글에 해당되며, 나머지 시리즈의 번역본도 일주일 간격으로 업로드할 예정입니다. 원 저작물은 CC-BY에 의해 보호받습니다. 오타 또는 오역이 있다면 알려주시면 감사하겠습니다!


타원 곡선 암호화 : 간단한 소개

많은 사람들이 ECC, ECDH 또는 ECDSA에 대해 들어본 적이 있을 것이다. 이 중 첫 번째인 ECC는 Elliptic Curve Cryptography(타원 곡선 암호화)의 줄임말로, 나머지 두 개는 ECC에 기반한 알고리즘이다.

오늘날 우리는 현대의 Web과 IT 세계를 떠받치는 3개의 핵심 기술인 TLS, PGP, SSH에서 타원 곡선 암호화를 찾을 수 있다. Bitcoin과 다른 암호 화폐는 말할 것도 없다.

ECC가 유명해지기 전에, 거의 모든 공개 키 알고리즘은 RSA, DSA, DH 등 모듈러(modular) 연산에 기반한 대안적인 암호 시스템에 기반을 두고 있었다. RSA 등의 암호 체계는 오늘날에도 여전히 중요하고, 종종 ECC와 나란하게 사용되고 있다. 하지만, RSA 등의 암호 체계의 원리는 쉽게 설명되어질 수 있고, 많은 사람들에게 이해되었으며, 개략적인 구현이 쉽게 작성되어질 수 있는 반면, ECC의 기반은 여전히 많은 사람들에게 수수께끼로 남아 있다.

4편의 시리즈를 통해, 필자는 타원 곡선 암호화의 세계에 대한 간단한 소개를 작성하고자 한다. 필자의 목표는 ECC에 대한 완벽하고 자세한 가이드(인터넷에는 이에 대한 정보가 차고 넘친다)의 제공이 아닌, ECC가 무엇이고, 왜 안전하다고 여겨지는지에 대한 간단한 개요의 제공이다. 필자는 또한 시각적인 interactive tool과 script를 통한 예제를 함께 제공할 것이다.

구체적으로, 다음과 같은 토픽을 다룰 예정이다.

  1. 실수(real number) 상에서의 타원 곡선과 군(group)의 법칙 (이 글에서 다룰 내용)
  2. 유한체(finite fields)에서의 타원 곡선과 이산 로그 문제(discrete logarithm problem)
  3. 키 쌍(공개키-개인키)의 생성과 2개의 ECC 알고리즘 : ECDH와 ECDSA
  4. ECC의 안전성을 깨뜨리기 위한 알고리즘과, RSA와의 비교

이 글을 이해하기 위해서, 당신은 집합론의 간단한 내용과 기하학, 모듈러 연산 등을 알아야 하고, 대칭형 암호 체계, 비대칭형 암호 체계와 어느 정도 친숙해야 한다. 또한, 당신은 “쉬운” 문제와 “어려운” 문제에 대한 분명한 이해가 있어야 하고, 암호학에서 그들의 역할을 이해해야 한다.

타원 곡선

우선, 타원 곡선은 무엇인가? Wolfram MathWorld는 완벽하고 완성된 정의를 제공하지만, 우리의 목적을 위해 타원 곡선을 다음 등식에 의해 나타내어지는 점들의 집합으로 정의한다.

y^2=x^3+ax+b

단, 4a^3+27b^2\ne0 이다. (이 조건은 특이 곡선(singular curve)을 제외하기 위해 필요하다.) 위 등식은 타원 곡선의 Weierstrass normal form으로 불린다.

image
b=1 이고, a2 에서 -3 으로 감소할 때의 서로 다른 타원 곡선 모양

image
특이 곡선의 종류: 왼쪽은 첨점(cusp)을 가진다 (y^2=x^3). 오른쪽은 자기 자신을 가로지른다 (y^2=x^3-3x+2). 둘 다 유효한 타원 곡선이 아니다.

ab 의 값에 따라, 타원 곡선은 평면 상에서 다른 모양을 가질 수 있다. 위의 그림에서도 볼 수 있고 쉽게 확인할 수 있듯이, 타원 곡선은 x 축에 대하여 대칭적이다.

우리의 목적을 위해, 타원의 일부분으로서 무한 원점(point at infinity)을 고려할 필요가 있다. 지금부터, 무한 원점은 0(zero)이라는 기호로 나타낼 것이다.

무한 원점을 명백하게 고려하고 싶다면, 타원 곡선의 정의를 다음과 같이 수정할 수 있다.

\{(x, y)\in\mathbb{R}^2\ |\ y^2=x^3+ax+b,\ 4a^3+27b^2\ne0\}\ \cup\ \{0\}

군(Groups)

수학에서 군(group)은 덧셈(addition)이라고 불리고 기호 +로 표시되는 이항 연산을 정의한 집합이다. 집합 \mathbb{G} 가 군이 되기 위해서는 덧셈이 반드시 정의되어야 하며, 다음의 4가지 특성을 만족해야 한다.

  1. 닫힘(closure): ab\mathbb{G} 의 원소라면, a+b\mathbb{G} 의 원소이다.
  2. 결합 법칙(associativity): (a+b)+c=a+(b+c) 이다.
  3. a+0=0+a=a 를 만족하는 항등원(identity element) 0 이 존재한다.
  4. 모든 원소는 역원(inverse) 을 가진다. 다시 말해, \mathbb{G} 의 원소 a 에 대해 a+b=0 을 만족하는 \mathbb{G} 의 원소 b 가 존재한다.

만약 다음 5번째 조건을 만족시킨다면,

  1. 교환 법칙(commutativity): a+b=b+a 이다.

이 군은 아벨 군(abelian group) 으로 불린다.

통상적인 덧셈의 개념에 따르면, 정수의 집합 \mathbb{Z} 는 군이다. (더 나아가, \mathbb{Z} 는 아벨 군이다.) 하지만 자연수의 집합 \mathbb{N}=\{0,\ 1,\ 2,\ ...\} 은 4번째 조건을 만족시키지 않기 때문에, 군이 아니다.

군은 매우 유용하다. 왜냐하면, 만약 우리가 위의 4가지 특성을 만족시킴을 보이면, 우리는 다른 특성들 또한 만족시킴을 추가적인 증명 없이 바로 알 수 있기 때문이다. 예를 들어, “항등원은 유일하다.”, “역원은 유일하다.” 등의 특성을 알 수 있다. 다시 말해, 모든 a 에 대해 a+b=0 을 만족하는 b 는 유일하다 (또한 b-a 로 쓸 수 있다). 직접적으로든 간접적으로든, 위의 특성과 더불어 군의 다른 특성들은 후에 우리에게 매우 중요하게 쓰일 것이다.

타원 곡선에서 군의 법칙

우리는 타원 곡선 상에서 군을 정의할 수 있다. 구체적으로,

  • 군의 원소들은 타원 곡선 상의 점들이다.
  • 항등원은 무한 원점(0)이다.
  • P역원x 축에 대하여 대칭인 점이다.
  • 덧셈은 다음 규칙에 의해 정의된다: 일직선 상에 있는, 영점(zero-point)이 아닌 세 점 P, Q, R 에 대해, P+Q+R=0 이다.
Three aligned points

일직선 상에 있는 세 점의 합은 0 이다.

마지막 규칙에 따르면, 우리는 오직 일직선 상에 있는 3개의 점만 필요하고, 세 점은 순서에 상관 없이 일직선 상에 있다. 즉, 만약 P, Q, R 가 일직선 상에 있다면, P+(Q+R)=Q+(P+R)=R+(P+Q)=\cdots=0 이다. 이러한 방식으로, 우리는 직관적으로 우리가 정의한 + 연산자가 결합 법칙, 교환 법칙을 모두 만족함을 보였다. 즉, 이 군이 아벨 군임을 알 수 있다.

지금까지는 순조로웠지만, 임의의 두 점의 덧셈은 실제로 어떻게 계산할 수 있을까?

기하학적 덧셈(Geometric addition)

우리가 정의한 군이 아벨 군이기 때문에, 우리는 P+Q+R=0P+Q=-R 로 쓸 수 있다. 이 등식으로부터, 우리는 두 점 PQ 의 합을 기하학적인 방법을 통해 이끌어 낼 수 있다. PQ 를 지나는 선분을 그렸을 때, 이 선분은 곡선의 세 번째 점 R 와 교차할 것이다 (이는 P, Q, R 가 일직선상에 있다는 사실로부터 유추할 수 있다). R 의 역원인 -R 가 바로 P+Q 의 결괏값이다.

image
PQ 를 지나는 직선을 그려 보면, 이 직선은 세 번째 점 R 와 교차한다. R 와 대칭적인 -RP+Q 의 결괏값이다.

이러한 기하학적 방법은 잘 작동하지만, 약간의 수정이 필요하다. 특히, 몇 가지 질문에 대한 답변이 필요하다.

  • P=0 이거나 Q=0 이라면? 분명히, 우리는 어떤 직선도 그을 수 없다 (0xy 평면에 존재하지 않는다). 하지만 우리가 0 을 항등원으로 정의했음을 고려할 때, 모든 PQ 에 대해 P+0=P 이고 0+Q=Q 이다.
  • P=-Q 라면? 이 경우에는, 두 점을 지나는 직선은 수직이고, 어떤 세 번째 점과도 교차하지 않는다. 하지만 PQ 의 역원이므로, 역원의 정의에 의해 P+Q=P+(-P)=0 이다.
  • P=Q 라면? 이 경우에는, 이 점을 지나는 직선이 무수히 많이 존재하므로, 이 지점에서 문제는 약간 복잡해진다. 하지만 점 Q'\ne P 를 고려해보자. 만약 Q'P 에 계속 가까워지게 만든다면 어떻게 될까?
    image
    두 점이 가까워질수록, 두 점을 지나는 직선은 곡선의 접선이 된다.

    Q'P 에 가까워질수록, PQ' 를 지나는 직선은 곡선의 접선이 된다. 이를 고려할 때, P 에서의 접선과 곡선이 교차하는 다른 점 R 에 대해 P+P=-R 라 말할 수 있다.
  • P\ne Q 이지만, 세 번째 점 R 가 존재하지 않는다면? 바로 이전의 케이스와 매우 유사하다. 사실, 이 경우는 PQ 를 지나는 직선이 곡선에 접하는 경우이다.
    image
    만약 직선이 곡선과 오직 두 점에서만 만난다면, 이는 이 직선이 곡선에 접함을 의미한다. 두 점의 합의 결과가 두 점 중 접점의 대칭점이라는 것은 위의 예시를 통해 쉽게 알 수 있다.

    P 가 접점이라고 가정하자. 이전의 케이스에서, 우리는 P+P=-Q 로 서술했다. 이 등식은 이번 케이스에서는 P+Q=-P 로 서술된다. 만약 Q 가 접점이라면, P+Q=-Q 가 올바른 식이 된다.

기하학적 방법은 이제 완료되었고 모든 케이스를 고려해 보았다. 자와 연필만 있다면 우리는 타원 곡선 상의 모든 점에 대해 덧셈을 수행할 수 있다. 만약 당신이 시도해보기를 원한다면, 타원 곡선에서의 덧셈 계산을 위해 필자가 만든 HTML5/JavaScript 시각화 툴을 사용해 볼 수 있다.

대수적 덧셈(Algebraic addition)

만약 컴퓨터를 이용해 두 점의 덧셈을 하고 싶다면, 우리는 기하학적 방법에서 대수적 방법으로 전환할 필요가 있다. 위에서 언급된 규칙들을 등식으로 전환하는 것은 쉬워 보일 수 있지만, 실제로 이 작업은 3차 방정식의 풀이를 요구하기 때문에 매우 싫증날 수 있다. 이러한 이유로, 필자는 결과만을 작성할 것이다.

첫 번째로, 가장 짜증나는 코너 케이스를 제거하고 생각해 보자. 우리는 P+(-P)=0 임을 알고, 또한 P+0=0+P=P 임을 알고 있다. 따라서, 우리의 등식에서 이 두 케이스를 제외하고, 영점(zero-point)이 아니고 대칭적이지 않은 두 점 P=(x_P,\ y_P)Q=(x_Q,\ y_Q) 를 고려해보자.

만약 PQ 가 다른 점이라면 (x_P\ne x_Q), 이 두 점을 지나는 직선은 기울기를 갖는다.

m={y_P-y_Q\over x_P-x_Q}

이 직선과 타원 곡선이 만나는 점 R=(x_R,\ y_R) 는 다음과 같다.

\begin{array}{rcl} x_R &=& m^2 - x_P - x_Q \\ y_R &=& y_P + m(x_R - x_P) \\ &=& y_Q+m(x_R-x_Q) \end{array}

그러므로 (x_P,\ y_P)+(x_Q+\ y-Q)=(x_R,\ -y_R) 이다 (부호에 주목해보고, P+Q=-R 임을 기억하자).

만약 결과가 맞다는 걸 확인하고 싶다면, R 가 곡선 위의 점인지, P, Q, R 가 일직선상에 있는지 확인해야 한다. 점들이 일직선상에 있음을 확인하는 건 쉽지만, R 가 곡선 상에 있는지 확인하기 위해서는 지루한 3차 방정식을 풀어야 하기 때문에 쉽지 않다.

대신에, 예시를 들어 보자. 우리의 시각화 툴에 따르면, 곡선 y^2=x^3-7x+10 상의 두 점 P=(1,\ 2)Q=(3,\ 4) 에 대해 두 점의 합은 P+Q=-R=(-3,\ 2) 이다. 우리의 등식이 이를 만족하는지 확인해 보자.

\begin{array}{rcl} m &=& \frac{y_P - y_Q}{x_P - x_Q} = \frac{2 - 4}{1 - 3} = 1 \\ x_R &=& m^2 - x_P - x_Q = 1^2 - 1 - 3 = -3 \\ y_R &=& y_P + m(x_R - x_P) = 2 + 1 \cdot (-3 - 1) = -2 \\ &=& y_Q + m(x_R - x_Q) = 4 + 1 \cdot (-3 - 3) = -2 \end{array}

실제 결과와 일치함을 확인할 수 있다!

이 등식은 심지어 P 또는 Q 중 하나가 접점이라도 성립한다. 두 점 P=(-1, \ 4)Q=(1,\ 2) 에 대해 시도해 보자.

\begin{array}{rcl} m &=& \frac{y_P - y_Q}{x_P - x_Q} = \frac{4 - 2}{-1 - 1} = -1 \\ x_R &=& m^2 - x_P - x_Q = (-1)^2 - (-1) - 1 = 1 \\ y_R &=& y_P + m(x_R - x_P) = 4 + -1 \cdot (1 - (-1)) = 2 \end{array}

우리는 P+Q=(1,\ -2) 라는 결과를 얻었고, 이는 시각화 툴의 결과와 같다.

P=Q 인 경우는 약간 다르게 다뤄져야 한다. x_Ry_R 의 식은 같지만, x_P=x_Q 임을 고려하면, 우리는 다른 기울기 식을 써야 한다.

m={3x^2_P+a \over 2y_P}

예상했던 대로, m 의 식은 다음 식의 1차 도함수이다.

y_P=\pm \sqrt{x^3_P+ax_P+b}

이 결과의 타당성을 증명하기 위해서는, R 가 타원 곡선 상의 점이라는 사실과, PR 를 지나는 직선이 곡선과 오직 2개의 교차점만을 가진다는 사실을 확인하면 된다. 하지만 이전과 같이, 이 사실을 증명하지 않는 대신 예시를 통해 확인해보자. 두 점 P=Q=(1,\ 2) 에 대해,

\begin{array}{rcl} m &=& \frac{3x_P^2 + a}{2 y_P} = \frac{3 \cdot 1^2 - 7}{2 \cdot 2} = -1 \\ x_R &=& m^2 - x_P - x_Q = (-1)^2 - 1 - 1 = -1 \\ y_R &=& y_P + m(x_R - x_P) = 2 + (-1) \cdot (-1 - 1) = 4 \end{array}

이므로, P+P=-R=(-1,\ -4) 임을 확인할 수 있다!

위에서 살펴 보았던 식들을 유도하는 과정은 매우 지루하더라도, 이 식들은 매우 간단하다. 이 결과는 우리가 다룬 타원 곡선이 Weierstrass normal form 인 덕분이다. 그렇지 않았다면, 위의 식들은 매우 길고 복잡해졌을 것이다!

스칼라 곱(Scalar multiplication)

덧셈 말고도, 우리는 다른 연산: 스칼라 곱(Scalar multiplication) 을 정의할 수 있다.

nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}

위 식에서 n 은 자연수이다. 필자는 스칼라 곱에 대한 시각화 툴 또한 만들어 놓았다.

위의 식을 보면, nP 를 계산하는 것은 n 번의 덧셈을 필요로 하는 것처럼 보인다. 만약 n 을 2진법으로 나타냈을 때 k 개의 2진 숫자로 구성된다면, 이 알고리즘의 시간 복잡도는 O(2^k) 일 것이고, 이는 매우 좋지 않다. 하지만 더 빠른 알고리즘이 존재한다.

그 중 하나는 double and add 알고리즘이다. 이 알고리즘의 계산 규칙은 예시를 통해 더 잘 설명될 수 있다. n=151 을 고려해보자. 이것의 2진 표현은 10010111_2 이다. 이러한 2진 표현은 2의 거듭제곱들의 합으로 전환될 수 있다.

\begin{array}{rcl} 151 & = & 1 \cdot 2^7 + 0 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 \\ & = & 2^7 + 2^4 + 2^2 + 2^1 + 2^0 \end{array}

(n 의 2진 표현에서 각 자릿수에 2의 거듭제곱을 곱한 후 더하였다.)

이러한 관점에서, 다음과 같이 쓸 수 있다.

151 \cdot P = 2^7 P + 2^4 P + 2^2 P + 2^1 P + 2^0 P

double and add 알고리즘이 말하고자 하는 바는 다음과 같다.

  • P 를 선택한다.
  • 2배로 하여 2P 를 계산한다.
  • 2PP 를 더한다. (2^1P+2^0P 의 결과를 얻기 위해서)
  • 2P 를 2배로 하여 2^2P 를 계산한다.
  • 위의 결과에 2^2P 를 더한다. (따라서 2^2P+2^1P+2^0P 를 얻는다.)
  • 2^2P 를 2배로 하여 2^3P 를 얻는다.
  • 2^3P 를 이용한 덧셈을 수행하지 않는다.
  • 2^3P 를 2배로 하여 2^4P 를 얻는다.
  • 위의 결과에 2^4P 를 더한다. (따라서 2^4P+2^2P+2^1P+2^0P 를 얻는다.)

결과적으로, 우리는 7번의 doubling(2배로 하기)과 4번의 addition(덧셈)을 통해 151 \cdot P 를 계산할 수 있다.

만약 아직까지 명확하게 이해되지 않는다면, 이 알고리즘을 수행하는 다음의 Python script을 참고할 수 있다.

def bits(n):
    """
    Generates the binary digits of n, starting
    from the least significant bit.

    bits(151) -> 1, 1, 1, 0, 1, 0, 0, 1
    """
    while n:
        yield n & 1
        n >>= 1

def double_and_add(n, x):
    """
    Returns the result of n * x, computed using
    the double and add algorithm.
    """
    result = 0
    addend = x

    for bit in bits(n):
        if bit == 1:
            result += addend
        addend *= 2

    return result

만약 doubling과 adding 둘 다 O(1) 의 연산이라면, 이 알고리즘은 O(\log n) (또는 bit의 길이를 고려할 때 O(k))의 시간 복잡도를 가지고, 이는 처음의 O(n) 알고리즘에 비하면 비약적인 발전이다!

로그(Logarithm)

nP 가 주어졌을 때, 우리는 Q=nP 를 다항 시간(polynomial time)에 계산할 수 알고리즘을 최소 하나는 알고 있다. 하지만 그 반대는 어떨까? 만약 QP 를 알고 있고, n 을 구하는 경우라면? 이 문제는 로그 문제(logarithm problem) 로 알려져 있다. 우리는 기존 암호 체계의 관습에 따르기 위해, “나누기 문제” 대신 "로그 문제"라고 부른다 (우리는 곱셈 대신에 거듭제곱법(exponentiation)을 가진다).

로그 문제에 대한 “쉬운” 알고리즘의 존재 여부는 밝혀지지 않았지만, 곱셈을 다루다 보면 어떤 패턴을 쉽게 볼 수 있다. 예를 들어, 곡선 y^2=x^3-3x+1 과 점 P=(0,\ 1) 을 고려해 보자. 우리는 n 이 짝수라면, nP 는 왼쪽 평면 상의 곡선(x\le0) 위에 있음을 바로 확인할 수 있다. 만약 n 이 홀수라면, nP 는 오른쪽 평면 상의 곡선(x\ge0) 위에 있다. 몇 번의 실험을 더 해보면, 우리는 곡선 상에서의 로그 계산을 효율적으로 수행하는 알고리즘으로 이끌어 주는 패턴을 더 찾을 수도 있다.

하지만 로그 문제에는 여러 변형이 있다. 대표적인 예시로, 이산 로그 문제(discrete logarithm problem)가 있다. 다음 글에서 볼 수 있듯이, 타원 곡선의 정의역(domain)을 축소시킨다면, 스칼라 곱은 “쉬운” 문제로 남지만, 이산 로그는 “어려운” 문제가 된다. 이 양면성은 타원 곡선 암호화를 이루는 핵심 요소가 된다.

다음 글에 이어집니다.

오늘은 여기까지이고, 당신이 이 글을 즐겼기를 바란다. 다음 주에 우리는 유한체(finite field)이산 로그 문제 를 예시, 툴과 함께 다룰 것이다. 이 주제가 흥미롭다면, 다음 글을 주목하자!

2 Likes