타원 곡선 암호화 : 유한체와 이산 로그

타원 곡선 암호화 개념 정리

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


타원 곡선 암호화 : 유한체(finite field)와 이산 로그(discrete logarithm)

이 포스트는 "타원 곡선 암호화: 간단한 소개"의 두 번째 시리즈이다.

이전 포스트에서, 우리는 실수 상에서 군을 정의하기 위해 어떻게 타원 곡선을 활용할 수 있는지 보았다. 특히, 우리는 점 덧셈(point addition)에 대한 규칙을 정의했다: 3개의 일직선상에 있는 점이 있을 때, 그들의 합은 0 이다 (P+Q+R=0). 우리는 점 덧셈을 계산하기 위해서 기하학적 방법과 대수적 방법을 사용하였다.

그 후 우리는 스칼라 곱 (nP=P+P+ \cdots +P)을 도입했고 우리는 스칼라 곱을 계산하는 “쉬운” 알고리즘 (double and add 알고리즘)을 찾아냈다.

지금부터 우리는 타원 곡선의 정의역을 실수의 집합이 아닌 유한체로 제한하고 무엇이 바뀌는지 볼 것이다.

p 를 법(modulo)으로 한 정수 체(field)

유한체는 우선, 원소의 개수가 유한개인 집합이다. 유한체의 예시는 p 가 소수일 때, p 를 법으로 한 정수의 집합이다. 이 집합은 보통 \mathbb{Z} / p, GF(p) 또는 \mathbb{F}_p 로 표시된다. 우리는 마지막 표기법을 따를 것이다.

체에는 덧셈 (+), 곱셈 (·)의 2가지 이항 연산이 있다. 두 연산 모두 닫혀 있으며 (closure), 결합 법칙(associative)과 교환 법칙(commutative)을 만족한다. 두 연산 각각에 대해 유일한 항등원(identity element)이 존재하며, 모든 원소에 대해 유일한 역원(inverse element)이 존재한다. 마지막으로, 곱셈은 덧셈에 대해 분배 법칙(distributive)을 만족한다. 즉, x \cdot (y+z)=x \cdot y + x \cdot z 이다.

p 를 법으로 한 정수의 집합은 0 부터 p-1 까지의 모든 정수로 구성된다. 덧셈과 곱셈은 모듈러 연산(modular arithmetic)에서처럼 작동한다 ("clock arithmetic"으로도 알려져 있다). 다음은 \mathbb{F}_{23} 에서 연산의 예시이다.

  • 덧셈(addition) : (18+9)\bmod{23}=4
  • 뺄셈(subtraction) : (7-14)\bmod{23}=16
  • 곱셈(multiplication) : 4 \cdot 7 \bmod{23}=5
  • 덧셈에 대한 역원(additive inverse) : -5\bmod{23}=18
    실제로, (5+(-5))\bmod{23}=(5+18)\bmod{23}=0 이다.
  • 곱셈에 대한 역원(multiplicative inverse) : 9^{-1}\bmod{23}=18
    실제로, 9\cdot 9^{-1}\bmod{23}=9\cdot 18\bmod{23}=1 이다.

만약 이 식들이 친숙하지 않다면 당신은 모듈러 연산에 대한 입문서가 필요할 것이다. Khan Academy을 참고하면 도움이 될 것이다.

이전에 말했듯이, p 를 법으로 한 정수의 집합은 체이므로, 위에서 언급된 모든 특성들을 만족한다. p 가 소수라는 조건은 매우 중요함을 명심하자! 4 를 법으로 한 정수의 집합은 체가 아니다. 2 가 곱셈에 대한 역원을 가지지 않기 때문이다 (예를 들어, 방정식 2\cdot x\bmod{4}=1 은 해를 가지지 않는다.)

p 를 법으로 한 나눗셈

우리는 곧 \mathbb{F}_p 상에서 타원 곡선을 정의할 것이다. 하지만 그 전에 우리는 \mathbb{F}_p 에서 x/y 가 무엇을 의미하는지에 대한 명확한 개념이 필요하다. 간단히 쓰자면, x/y=x\cdot y^{-1} 이고, 풀어 말하자면, x 나누기 yxy 의 곱셈에 대한 역원을 곱한 것과 같다. 이 사실은 놀랍지 않지만, 나눗셈을 하는 방식에 대한 기초적인 방법을 제공한다. 어떤 숫자의 곱셈에 대한 역원을 찾은 후 곱셈을 수행하면 된다.

곱셈에 대한 역원을 찾는 것은 확장된 유클리드 알고리즘을 통해 “쉽게” 계산될 수 있고, 계산 복잡도는 O(\log{p}) (또는 비트의 길이를 고려할 때 O(k))이다.

확장된 유클리드 알고리즘은 주제를 벗어나기 때문에 디테일하게 다루지는 않지만, 다음의 Python으로 구현된 알고리즘을 참고할 수 있다.

def extended_euclidean_algorithm(a, b):
    """
    Returns a three-tuple (gcd, x, y) such that
    a * x + b * y == gcd, where gcd is the greatest
    common divisor of a and b.

    This function implements the extended Euclidean
    algorithm and runs in O(log b) in the worst case.
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    return old_r, old_s, old_t


def inverse_of(n, p):
    """
    Returns the multiplicative inverse of
    n modulo p.

    This function returns an integer m such that
    (n * m) % p == 1.
    """
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x + p * y) % p == gcd

    if gcd != 1:
        # Either n is 0, or p is not a prime number.
        raise ValueError(
            '{} has no multiplicative inverse '
            'modulo {}'.format(n, p))
    else:
        return x % p

\mathbb{F}_p 상에서의 타원 곡선

지금까지 우리는 타원 곡선의 정의역을 \mathbb{F}_p 로 제한하기 위해 필요한 모든 요소를 살펴보았다. 이전 포스트에서 점들의 집합은 다음과 같았다.

\begin{array}{rcl} \left\{(x, y) \in \mathbb{R}^2 \right. & \left. | \right. & \left. y^2 = x^3 + ax + b, \right. \\ & & \left. 4a^3 + 27b^2 \ne 0\right\}\ \cup\ \left\{0\right\} \end{array}

점들의 집합은 다음과 같이 제한된다.

\begin{array}{rcl} \left\{(x, y) \in (\mathbb{F}_p)^2 \right. & \left. | \right. & \left. y^2 \equiv x^3 + ax + b \pmod{p}, \right. \\ & & \left. 4a^3 + 27b^2 \not\equiv 0 \pmod{p}\right\}\ \cup\ \left\{0\right\} \end{array}

0 은 여전히 무한 원점(point at infinity)이고, ab\mathbb{F}_p 의 두 정수이다.


p=19,\ 97,\ 127,\ 487 일 때의 타원 곡선 y^2 \equiv x^3 - 7x + 10 \pmod{p} 이다. 모든 x 에 대해, 최대 2개의 점이 존재한다는 점을 기억하자. 또한 두 점은 y=p/2 에 대해 대칭적이다.

image
타원 곡선 y^2 \equiv x^3 \pmod{29} 는 특이(singular) 곡선이고 (0,\ 0) 에서 3개의 점을 가진다. 이는 유효한 타원 곡선이 아니다.

실수 상에서는 연속적이였던 곡선은 이제는 xy 평면 상에서 불연속적인 점들의 집합이 된다. 하지만 정의역을 제한하더라도, \mathbb{F}_p 상에서의 타원 곡선이 아벨 군(abelian group)을 형성한다는 사실은 증명 가능하다.

점 덧셈(Point addition)

분명히, 우리는 덧셈의 정의를 \mathbb{F}_p 상에서도 작동하도록 살짝 바꿔야 한다. 실수 상에서, 일직선 상에 있는 세 점의 합은 0 이였다 (P+Q+R=0). 우리는 이 정의를 사용할 수 있지만, \mathbb{F}_p 상에서 세 점이 일직선 상에 있다는 것은 무슨 뜻일까?

세 점을 모두 연결하는 직선이 있을 때, 우리는 세 점이 일직선 상에 있다고 말할 수 있다. 여기서는 물론, \mathbb{F}_p 상에서의 직선은 \mathbb{R} 상에서의 직선과 같다고 할 수 없다. 우리는 비공식적으로, \mathbb{F}_p 상에서의 직선은 식 ax + by + c \equiv 0 \pmod{p} 을 만족하는 점 (x,\ y) 의 집합이라고 말할 수 있다 (이 식은 “(\text{mod}\ p)” 에서의 덧셈에 대해 표준 직선 방정식이다).


곡선 y^2 \equiv x^3 - x + 3 \pmod{127} 상에서 점 P=(16,\ 20), Q=(41,\ 120) 의 덧셈을 나타낸 것이다. 세 점을 연결하는 직선 y \equiv 4x + 83 \pmod{127} 이 평면 상에서 어떻게 "반복"되는지를 주목하자.

우리가 군을 다루고 있었음을 고려할 때, 점 덧셈은 우리가 이미 알고 있던 특성들을 만족한다.

  • Q+0=0+Q=Q 이다 (항등원의 정의로부터 알 수 있다).
  • 영점(zero-point)이 아닌 점 Q 에 대해, 역원인 -Q 는 가로 좌표는 같지만 세로 좌표는 반대이다. 또는, 기호에 따라서 -Q=(x_Q,\ -y_Q\bmod{p}) 로 쓸 수 있다. 예를 들어, \mathbb{F}_{29} 에서 곡선 상의 점 Q=(2,\ 5) 에 대해, 역원은 -Q=(2,\ -5\bmod{29})=(2,\ 24) 이다.
  • 또한, P+(-P)=0 이다 (역원의 정의로부터 알 수 있다).

대수 합(Algebraic sum)

모든 식에 "\text{mod}\ p"를 덧붙여야 한다는 점을 제외하고는, 점 덧셈을 위한 식은 이전 포스트의 식과 완전히 동일하다. 따라서, P=(x_P,\ y_P), Q=(x_Q,\ y_Q), R=(x_R,\ y_R) 가 주어졌을 때, P+Q=-R 를 다음과 같이 계산할 수 있다.

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

만약 P\ne Q 라면, 기울기 m 은 다음과 같다.

m = (y_P - y_Q)(x_P - x_Q)^{-1} \bmod{p}

만약 P=Q 라면, m 은 다음과 같다.

m = (3 x_P^2 + a)(2 y_P)^{-1} \bmod{p}

식이 변하지 않은 것은 우연이 아니다. 사실, 이 식은 모든 체 (유한체든 무한체든)에서 적용된다 (특별한 케이스인 \mathbb{F}_2, \mathbb{F}_3 을 제외하고 말이다). 이 사실에 대한 정당화가 필요할 것 같지만, 문제점은 군의 법칙에 대한 증명이 복잡한 수학적 개념을 수반한다는 것이다. 하지만 초등적인 개념만을 사용한 Stefan Friedl의 증명이 있으니, 왜 (거의) 모든 체에서 이 식이 적용되는지에 관심이 있는 독자들은 읽어보길 바란다.

다시 돌아와서, 우리는 기하학적 방법을 정의하지 않을 것이다. 사실, 여기에는 몇 가지 문제점이 있다. 예를 들어, 이전의 포스트에서 우리는 P+P 를 계산하기 위해 곡선에서 P 의 접선을 고려했다. 하지만 연속성이 없이 "접선"을 고려하는 것은 말이 되지 않는다. 우리는 이를 다른 방법으로 해결할 수 있을 뿐더러, 순수한 기하학적 방법은 매우 복잡하고 실용적이지도 않다.

대신에, 당신은 점 덧셈을 위한 interactive tool을 사용해볼 수 있다.

타원 곡선 군의 위수(order)

유한체에서 정의된 타원 곡선은 유한한 개수의 점을 갖는다고 이전에 언급했었다. 우리는 다음의 중요한 질문에 대한 답이 필요하다. 정확히 몇 개의 점이 존재하는가?

우선, 이 군에서 점의 개수를 군의 위수(order) 라고 부른다.

0 부터 p-1 까지의 가능한 모든 x 에 대해 이를 시도해보는 것은 점의 개수를 세기 위한 실현 가능한 방법이 아니다. 이 방법은 O(p) 만큼의 스텝이 필요하고, p 가 크다면 이는 “어려운” 문제가 되기 때문이다.

운이 좋게도, 위수를 계산하기 위한 더 빠른 알고리즘(Schoof의 알고리즘)이 존재한다. 이 알고리즘에 대한 디테일한 설명은 생략하겠다. 더 중요한 것은 이 알고리즘이 다항 시간이 걸린다는 것이고, 이것이 우리에게 필요한 점이다.

스칼라 곱과 순환 부분군(cyclic subgroups)

실수 상에서, 곱셈은 다음과 같이 정의되었다.

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

그리고 여기서 다시 곱셈을 O(\log n) (또는 k 가 비트의 길이일 때 O(k))에 수행하는 double and add 알고리즘을 사용할 수 있다. 필자는 스칼라 곱에 대한 interactive tool을 작성해 놓았다.

\mathbb{F}_p 상의 타원 곡선에서 점의 곱셈은 흥미로운 특성을 가진다. 곡선 y^2 \equiv x^3 + 2x + 3 \pmod{97} 과 점 P=(3,\ 6) 을 고려하자. 이 때 P 의 모든 배수를 계산하면 다음과 같다.
image
P=(3,\ 6) 의 서로 다른 배수는 오직 5개 (0, P, 2P, 3P, 4P) 뿐이고, 이 점들이 순환적으로 반복된다. 타원 곡선 상에서의 스칼라 곱과 모듈러 연산에서의 덧셈 사이의 유사성을 쉽게 알아챌 수 있다.

  • 0P=0
  • 1P=(3,\ 6)
  • 2P=(80,\ 10)
  • 3P=(80,\ 87)
  • 4P=(3,\ 91)
  • 5P=0
  • 6P=(3,\ 6)
  • 7P=(80,\ 10)
  • 8P=(80,\ 87)
  • 9P=(3,\ 91)

여기서 우리는 바로 2가지를 알 수 있다. 첫 번째로, P 의 배수는 오직 5개라는 것이다. 타원 곡선 상의 다른 점은 절대 나타나지 않는다. 두 번째로, 5개의 점이 순환적으로 반복된다는 점이다. 우리는 다음과 같이 쓸 수 있다.

  • 5kP=0
  • (5k+1)P=P
  • (5k+2)P=2P
  • (5k+3)P=3P
  • (5k+4)P=4P

이는 모든 정수 k 에 대해 성립한다. 이 5개의 식은 모듈러 연산자에 의해 하나의 식으로 "압축"될 수 있다. (kP=(k\bmod{5})P)

이 뿐만 아니라, 우리는 이 5개의 점이 덧셈에 대하여 닫혀 있다(closure) 는 것을 확인할 수 있다. 다시 말해, 0, P, 2P, 3P, 4P 중 어떤 2개를 선택해 더하더라도, 결과는 이 5개의 점 중 하나이다. 다시 말하지만, 이 타원 곡선 상의 다른 점은 결과로 나타나지 않는다.

이는 P=(3,\ 6) 외의 모든 점에서도 똑같이 성립한다. 사실, 우리가 통칭의 P 를 선택할 때 다음이 성립한다.

nP + mP = \underbrace{P + \cdots + P}_{n\ \text{times}} + \underbrace{P + \cdots + P}_{m\ \text{times}} = (n + m)P

이는, 우리가 P 의 배수끼리 더하면, P 의 배수를 얻는다는 것을 의미한다 (즉, P 의 배수들은 덧셈에 대하여 닫혀 있다). 이것은 P 의 배수의 집합이 타원 곡선에 의해 형성된 군의 순환 부분군을 형성한다는 사실을 증명하기에 충분하다.

"부분군"은 다른 군의 부분집합인 군이다. "순환 부분군"은 위에서 보았던 예시와 같이, 원소가 순환적으로 반복되는 부분군이다. 점 P 는 순환 부분군의 생성자(generator) 또는 기점(base point) 으로 불린다.

순환 부분군은 ECC와 다른 암호학들의 토대이다. 우리는 그 이유를 다음 포스트에서 살펴볼 것이다.

부분군의 위수(Subgroup order)

우리는 P 에 의해 생성되는 부분군의 위수가 무엇인지 질문을 던져볼 수 있다 (또는 동일하게, P 의 위수가 무엇인지). 이 질문에 대해 답하기 위해 Schoof의 알고리즘을 사용할 수는 없는데, Schoof의 알고리즘은 타원 곡선의 부분군이 아닌 전체에서만 작동하기 때문이다. 이 문제에 접근하기 전에, 우리는 몇 가지가 더 필요하다.

  • 지금까지, 우리는 위수를 군에서 점의 개수로 정의해 왔다. 이 정의는 여전히 유효하지만, 순환 부분군에서 우리는 이전과 동등하지만 새로운 정의가 필요하다: P 의 위수는 nP=0 이 되게 하는 가장 작은 양의 정수 n 이다. 실제로, 우리가 전에 보았던 예제에서, 부분군은 5개의 점을 포함했고, 5P=0 이였다.
  • P 의 위수는 라그랑주의 정리에 의해 타원 곡선의 위수와 연결된다. 라그랑주의 정리는 부분군의 위수가 전체 군의 약수라고 말한다. 다시 말해, 타원 곡선이 N 개의 점을 포함하고 이의 부분군 중 하나가 n 개의 점을 포함한다면, nN 의 약수이다.

예를 들어, 체 \mathbb{F}_{37} 상에서의 곡선 y^2=x^3-x+3 은 위수 N=42 를 갖는다. 이것의 부분군은 위수 n=1, 2, 3, 6, 7, 14, 21 또는 42 를 가질 수 있다. 만약 P=(2,\ 3) 에 대해 시도해본다면, P\ne 0,\ 2P\ne 0,\ ...,7P=0 임을 확인할 수 있고, 따라서 P 의 위수는 n=7 이다.

중요한 점은, 제수(divisor)를 선택할 때 랜덤하게 선택하지 않고, 작은 수부터 선택해야 한다는 것이다. 만약 랜덤하게 선택한다면, 우리는 이 부분군의 위수가 아니지만, 위수의 배수인 n=14 를 선택할 수도 있다.

다른 예시로, 위수 N=37 을 가지는 체 \mathbb{F}_{29} 상에서의 타원 곡선 y^2=x^3-x+1 을 고려해 보자. 37 은 소수이므로, 부분군은 위수 n=1 또는 37 만을 가질 수 있다. 쉽게 추측할 수 있듯이, n=1 일 때, 부분군은 오직 무한 원점(point at infinity)만을 포함한다. n=N 일 때, 부분군은 타원 곡선 상의 모든 점을 포함한다.

기점(base point) 찾기

우리의 ECC 알고리즘을 위해, 우리는 큰 위수를 가지는 부분군을 원한다. 그래서 일반적으로 우리는 타원 곡선을 고르고, 이것의 위수 (N)를 계산하고, 부분군의 위수 (n)로써 높은 제수를 고르고 마지막으로 적절한 기점을 찾는다. 다시 말해, 우리는 기점을 먼저 선택한 후 이것의 위수를 계산하지 않을 것이고, 반대로 할 것이다. 우리는 첫 번째로 충분히 큰 위수를 선택한 후 적절한 기점을 찾을 것이다. 어떻게 이를 할 수 있을까?

첫 번째로, 우리는 하나의 용어를 더 도입해야 한다. 라그랑주의 정리는 h=N/n 이 항상 정수임을 암시한다 (nN 의 제수이기 때문이다). 이 h 는 이름을 가지는데, 부분군의 여인수(cofactor) 라고 불린다.

타원 곡선 상의 모든 점에 대해 NP=0 임을 고려해 보자. 이는 N 이 위수의 모든 후보 n 의 배수이기 때문에 일어난다. 여인수의 정의를 사용하면, 다음과 같이 쓸 수 있다.

n(hP)=0

만약 n 이 소수라고 가정하자 (이유는 다음 글에서 설명하겠지만, 우리는 소수 위수를 선호한다). 위의 형태로 쓰여진 식은, 점 G=hP 가 위수가 n 인 부분군을 생성함을 말한다 (단, G=hP=0 일 때와 같이 부분군의 위수가 1일 때를 제외한다).

이런 면에서, 우리는 알고리즘의 개요를 다음과 같이 작성할 수 있다.

  1. 타원 곡선의 위수 N 을 계산한다.
  2. 부분군의 위수 n 을 선택한다. 알고리즘이 동작하기 위해서, 이 수는 반드시 소수여야 하고 N 의 약수여야 한다.
  3. 여인수 h=N/n 을 계산한다.
  4. 곡선 상의 점 P 를 랜덤하게 선택한다.
  5. G=hP 를 계산한다.
  6. 만약 G0 이라면, 4번째 단계로 돌아가고, 아니라면 우리는 위수가 n 이고 여인수가 h 인 부분군의 생성자를 얻은 것이다.

이 알고리즘이 n 이 소수일 때만 동작함을 기억하자. 만약 n 이 소수가 아니라면, G 의 위수는 n 의 약수 중 하나일 수 있다.

이산 로그(Discrete logarithm)

우리가 연속적인 타원 곡선 상에서 그랬듯, 우리는 다음 문제에 대해 논의해야 한다. 만약 우리가 PQ 를 알고 있다면, Q=kP 를 만족하는 k 는 무엇인가?

타원 곡선에 대한 이산 로그 문제(discrete logarithm problem) 로 알려진 이 문제는, 현대의 컴퓨터 상에서 다항 시간에 작동하는 알고리즘이 알려져 있지 않다는 점에서 “어려운” 문제로 믿어진다. 하지만 이 믿음에 대한 수학적 증명은 없다.

이 문제는 또한 전자 서명 알고리즘 (DSA), 디피-헬만 키 교환 (D-H), ElGamal 알고리즘과 같은 다른 암호 시스템에서 사용되는 이산 로그 문제와 유사하다. 이 문제들이 유사한 이름을 가지는 것은 우연이 아니다. 차이점은, 다른 암호 시스템의 알고리즘에서는 스칼라 곱 대신에 모듈로 지수화(modulo exponentiation)가 사용된다는 것이다. 이러한 이산 로그 문제는 다음과 같이 서술될 수 있다: 만약 ab 가 알려져 있다면, b=a^k\bmod{p} 를 만족하는 k 는 무엇인가?

두 문제는 모두 유한 집합 (더 정확히는, 순환 부분군)을 수반한다는 점에서 "이산"적이다. 그리고 이들은 통상적인 로그와 유사하다는 점에서, "로그"이다.

ECC를 흥미롭게 만드는 점은, 오늘 보았듯이, 타원 곡선에서의 이산 로그 문제가 다른 암호학에서 사용된 비슷한 문제들과 비교했을 때 더 “어렵게” 보인다는 것이다. 이는 우리가 다른 암호 시스템을 사용했을 때와 비슷한 수준의 보안성을 유지하기 위해서 필요한 정수 k 의 비트 수가 더 적음을 암시한다. 이는 이 시리즈의 세 번째 포스트와 마지막 포스트에서 자세히 다룰 것이다.

다음 글에 이어집니다.

오늘은 여기까지이고, 당신이 이 글을 즐겼기를 바란다.

다음 주의 포스트에서는 ECC 알고리즘의 키 쌍 생성(key pair generation), ECDH, ECDSA에 대해 다룰 것이다. 이 내용은 이 시리즈에서 가장 흥미로운 부분 중 하나일 것이다.

1 Like

몇 가지 수식이 제대로 디스플레이 되지 않네요… :roll_eyes:

잠깐 에러였나봐요! 지금은 잘 나옵니다

2 Likes