Singular Elliptic Curves
서론
최근 타원 곡선에 대해서 공부하면서 피상적으로 이해하던 부분을 좀 더 깊이 이해하는 단계에 들어서고 있습니다. 특히 수학에 대해서 배우는 것은 좋아하지만 고등 수학 위로 배운 것이 없어, 많은 재미를 느끼고 있습니다.
그러면서 해소된 궁금점은 바로 “Discriminant가 왜 0이면 안 되는 것일까?” 였습니다. 타원 곡선에 대한 Wikipedia article 을 살펴보면, $y^2 = x^3 + ax + b$ 꼴의 short Weierstrass equation에 대해서 Discriminant $\Delta = -16(4a^3 + 27b^2)$ 가 0이 아니여야 한다는 조건을 달고 있습니다. Discriminant가 0이라면, 이 타원 곡선은 singular한 타원 곡선이라고 합니다.
그런데 살펴보면 Discriminant가 0이어도 타원 곡선에서의 덧셈과 곱셈은 잘 정의가 됩니다. 이리 저리 점들을 가지고 놀아봐도, 다른 타원 곡선에 비해서 ECDLP를 푸는 것이 쉬워보이지도 않고요. 그렇다면 Discriminant가 0이 되면 어떤 특징이 있기에 문제가 되는 걸까요?
본론
Discriminant
우선 Discriminant가 0이라는 것은, $x^3 + ax + b = 0$에서 중근 $x$가 존재한다는 것을 의미합니다. 이는 두 가지 경우로 더 세분화할 수 있습니다.
- 삼중근을 가지는 경우: 이 경우는 $x^3$으로 치환이 가능합니다.
- 중근과 다른 근 하나를 가지는 경우: 이 경우는 $x^2(x+a)$로 치환이 가능합니다.
각 경우를 살펴봅시다.
$y^2=x^3$의 경우
$y^2 = x^3$의 경우 $(0, 0)$에서만 덧셈과 곱셈이 정의되지 않습니다. 다른 점에 대해서는 모두 정의가 가능합니다. 이렇게 정의가 불가능한 점을 singular point, 정의가 가능한 다른 점들을 non-singular point라고 합니다.
이 때 흥미로운 사실은 곡선 상의 점 $(x, y)$에 대해서, $(x, y) \to \frac{x}{y}$ 의 형태로 치환이 가능하다는 것입니다. 더 나아가서, 이렇게 치환한 값에 대해서 덧셈과 곱셈을 수행했을 때, 치환하기 전의 점들에 대해서 곱셈과 덧셈을 수행한 뒤 치환한 값과 동일하다는 놀라운 사실 또한 성립합니다.
이에 대한 증명은 어렵지 않습니다.
$t_i = x_i/y_i$로 정의하고 $(x_1, y_1) + (x_2, y_2) = (x_3, y_3)$ 관계의 점 셋에 대해서 생각해봅시다.
만약 $(x_1, y_1) \neq (x_2, y_2)$ 라면, 덧셈 공식에 따라서 $x_3 = (\frac{y_2 - y_1}{x_2 - x_1})^2 - x_1 - x_2$가 성립합니다. 여기에서 $x_i = (y_i / x_i)^2 = 1/t_i^2$, $y_i = x_i / t_i = 1 / t_i^3$ 이라는 관계를 통해 값들을 $t_i$로 치환해봅시다.
$t_3^{-2} = (\frac{t_2^{-3} - t_1^{-3}}{t_2^{-2} - t_1^{-2}}) ^2 - t_1^{-2} - t_2^{-2}$
$(t_2^{-3} - t_1^{-3})/(t_2^{-2} - t_1^{-2}) = (t_1^3 - t_2^3)/(t_1^3t_2 - t_1t_2^3) = (t_1^2 + t_1t_2 + t_2^2) / (t_1^2t_2 + t_1t_2^2)$ 이므로, 식의 우변을 다음과 같이 묶을 수 있습니다.
$(\frac{t_2^{-3} - t_1^{-3}}{t_2^{-2} - t_1^{-2}}) ^2 - t_1^{-2} - t_2^{-2} = \frac{(t_1^2 + t_1t_2 + t_2^2)^2}{t_1^2t_2^2(t_1+t_2)^2} - \frac{1}{t_1^2} - \frac{1}{t_2^2} = \frac{(t_1^2 + t_1t_2 + t_2^2)^2 - (t_1^2 + t_2^2)(t_1 + t_2)^2}{t_1^2t_2^2(t_1+t_2)^2}$
윗항을 정리하면 $t_1^2 t_2^2$만 남기 때문에, 결국 식을 다음과 같이 정리할 수 있습니다.
$t_3^{-2} = (t_1 + t_2)^{-2}$
또한 덧셈 공식의 $y$ 부분에 대해서도 동일하게 적용하면, $t_3^{-3} = (t_1 + t_2)^{-3}$ 이라는 결과를 얻을 수 있습니다. 곧, $t_3 = t_1 + t_2$임을 알 수 있습니다.
$(x_1, y_1) = (x_2, y_2)$ 인 경우에도 비슷하게 증명을 진행해 $t_3 = t_1 + t_2$ 라는 결과를 얻을 수 있습니다. 곧, $(x, y) \to \frac{x}{y}$ 의 형태로 치환하더라도 동일한 관계가 성립합니다.
곧, ECDLP를 푸는 문제는 $F_p$에서 나눗셈을 하는 문제로 바뀌어버립니다. 매우 쉬워졌죠?
$y^2 = x^2(x+a)$ 의 경우
$y^2 = x^2(x+a)$ 또한 $y^2 = x^3$과 동일하게 $(0, 0)$만이 singular point입니다. 그리고 비슷한 형태로 치환이 가능한데, 이 경우는 조금 특이합니다. $\alpha ^ 2 = a$인 $\alpha$가 존재할 경우, $(x, y) \to \frac{y + \alpha x}{y - \alpha x}$ 로 치환하면 되며, 이 경우는 점의 덧셈이 치환된 수의 곱셈과 동일한 관계를 가지게 됩니다. 예를 들어서, 점 $P_1$, $P_2$와 치환한 값 $a_1$, $a_2$가 있을 때, $P_1 + P_2$를 치환한 값은 $a_1 a_2$라고 할 수 있습니다.
이 과정의 증명은 훨씬 복잡해지기 때문에 생락하고자 합니다. 증명은 위와 비슷하게 $t_i = \frac{y_i + \alpha x_i}{y_i - \alpha x_i}$ 라고 정의한 뒤, 점 $(x_1, y_1) + (x_2, y_2) = (x_3, y_3)$에 대해 $t_3 = t_1t_2$임을 보이면 됩니다.
실습
$y^2 = x^3$의 경우
다음과 같은 경우를 생각해봅시다.
p = 333757995332810618145773370739634879557
a, b = 0, 0
# y^2 = x^3 (mod p)
G = Point(4, 8)
P = k * G
# P = Point(135751533945741369397004641988263527917, 284466628648913598993600483962062966114)
k의 값을 구하려면 $(P_x / P_y) / (G_x / G_y)$를 구하면 됩니다.
from Crypto.Util.number import inverse
p = 333757995332810618145773370739634879557
t = 135751533945741369397004641988263527917 * inverse(284466628648913598993600483962062966114, p)
t %= p
t *= inverse(4, p) * 8
t %= p
print(p) # 12345678
답은 12345678이었습니다!
$y^2 = x^2(x+a)$ 의 경우
다음과 같은 경우를 생각해봅시다.
p = 333757995332810618145773370739634879557
a, b = 123, 74195852942824640800920200592778123263
# y^2 = x^3 + ax + b (mod p) that 4 * a**3 + 27 * b**2 = 0 (mod p)
G = Point(1, 163743484375733637098803352354337644764)
P = k * G
# P = Point(163279230740986137705361371065337775891, 80320803232464398971954693727558296148)
이 경우는 우선 인수분해를 진행해봅시다. 여기에서부터는 sage를 사용합니다.
sage: p = 333757995332810618145773370739634879557
sage: F = GF(p)
sage: a = F(123)
sage: b = F(74195852942824640800920200592778123263)
sage: R.<x> = PolynomialRing(F)
sage: f = x^3 + a * x + b
sage: f.factor()
(x + 291246145830203844206022466976440915629) * (x + 21255924751303386969875451881596981964)^2
x를 x_ - 21255924751303386969875451881596981964로 치환해봅시다.
sage: f_ = f.subs(x=x - 21255924751303386969875451881596981964)
sage: f_
x^3 + 269990221078900457236147015094843933665*x^2
sage: G = (F(1), F(163743484375733637098803352354337644764))
sage: P = (F(163279230740986137705361371065337775891), F(80320803232464398971954693727558296148))
sage: G = (G[0] + 21255924751303386969875451881596981964, G[1])
sage: P = (P[0] + 21255924751303386969875451881596981964, P[1])
이제 $\alpha$를 구한 뒤 $F_p$ 위의 값으로 치환해봅시다.
sage: a = F(269990221078900457236147015094843933665).square_root()
sage: a
125966347002381539411335275895157375147
sage: u = (G[1] + a*G[0]) / (G[1] - a*G[0])
sage: v = (P[1] + a*P[0]) / (P[1] - a*P[0])
sage: u
107164893907544222047468862935035346350
sage: v
71610097826140983550674914184719590255
마지막으로 discrete_log 함수를 통해 k가 무엇인지 구해봅시다.
sage: discrete_log(v, u)
3133731337
sage: u ^ 3133731337
71610097826140983550674914184719590255
k가 3133731337 이라는 것을 알 수 있습니다.
결론
Discriminant가 0인 타원 곡선 (singular한 타원 곡선)이 어떤 문제점을 갖고 있는지 알아볼 수 있었습니다.
일반적으로 타원 곡선 관련 문제가 나오면 Discriminant가 0이 아닌 nonsingular elliptic curve를 주기 때문에 관련해서 궁금증을 풀 수 있는 방법도 없었고, 이와 관련한 CTF write-up도 찾아보기 힘들었습니다.
다행히도 이번에 타원곡선 암호에 대한 공부를 시작하면서 읽고 있는 참고 문헌의 책에서 관련 내용이 있어서 읽으면서 어떤 문제점이 있는지 알아볼 수 있었고, 더 나아가서 Python과 sage를 통해 어떻게 공격을 구현할 수 있는지 알아볼 수 있었습니다.
책에서는 $y^2 = x^2(x+a)$에서 $a$의 square root가 없는 경우에 대해서도 해당 값을 복소수의 $i$와 같이 제곱해서 $a$가 되는 수 $\alpha$를 정의한 뒤 이를 통해서 비슷하게 할 수 있다고 하고 있습니다. 다만 이 경우 sage의 discrete_log 함수를 사용할 수 없기 때문에 직접 discrete log를 푸는 함수를 작성할 필요가 있겠습니다.
참고 문헌
- L. C. Washington, Elliptic Curves: Number Theory and Cryptography, 2nd Edition, CRC Press, Boca Raton (2008).