이렇게 두 가지입니다.
시작해 보겠습니다.
1장에서 언급했듯이, 타원곡선상의 두 점(하나인 경우도)으로부터 새로운 점을 계산해낼 수 있습니다.
이 과정을 다시 따라가 보겠습니다.
타원곡선 E : y2 = x3 + Ax +B 상의 두점
P1 = (x1, y1), P2 = (x2, y2)
이 두점을 잇는 직선을 L 이라고 하고 그 직선과 타원곡선 E 와 만나는 새로운 점을 P3' , 그리고 이 점을 x축 대칭이동한 점을
P3 라고 하고 이를 다음과 같이 정의한다.
P3 = P1 + P2
이제 두 점 P1, P2에 대해 가능한 경우를 생각해 보면은 두 점이 다를 때, 같을 때, 그리고 한 점이 ∞일 때로 나눌 수 있습니다.
1. P1 ≠ P2 ≠ ∞
이 경우 두 점을 지나는 직선의 방정식은 다음과 같습니다.
y = m(x-x1) +y1, m은 기울기
이제 이 직선과 타원곡선 E와의 교차점을 구할 수 있습니다.
(m(x - x1) +y1)2 = x3 + Ax +B
<=> 0 = x3 - m2x2 + ...
3차항의 계수가 1이므로 3차 방정식의 근의 공식을 사용할 수 있겠죠?(1장 참조)
x = m2 - x1 - x2
y = m(x - x1) + y1
이 점은 곧 P3‘ 이므로 x축 대칭이동하면 P3 = (x3, y3)을 구할 수 있겠습니다.
x3 = m2 - x1 - x2
y3 = -m(x3 - x1) + y1 = m(x1 - x3) - y1
1.1. x1 = x2, y1 ≠ y2
이 경우 P1과 P2는 수직선상에 있으며 ∞ 와 교차한다.
∞는 x축 대칭이동해도 ∞ 이다.
결국 P1 + P2 = ∞ 이다.
2. P1 = P2 = (x1, y1)
이제 접선을 생각해보자. 접선을 생각하는 이유를 우선 설명하면, 앞 서 두 점의 합을 생각할 때 두점을 지나는 선을 생각했는데,
이 두 점이 점점 가까워진다고 생각해보세요. 결국 최종적으로 두 점이 같을 때, 두 점을 지나는 직선은 접선이 됨을 알 수 있죠?..
E 상에서 x1, y1에서의 접선의 기울기는 다음과 같아요(음함수의 미분, implicit differentiation)
m = (3x12 +A)/2y1
단, y1 = 0 인 경우는 수직선이므로 1.1.과 같은 결과를 같게 됩니다.
그럼 y1 ≠ 0 경우 P3 = (x3, y3) 은 다음과 같습니다.
x3 = m2 - 2x1
y3 = m(x1 - x3) - y1
3. P2 = ∞
P1과 P2를 지나는 직선 L은 P3'에서 만나게 됩니다. 그런데 P3'은 곧 P1' 가 되죠?(직선이 ∞ 에서 만나는 것은 곧 수직선이라는
의미니까요)
그러니까 P1 + ∞ = P1 이 됩니다. 이것은 타원곡선 E상의 어떠한 점에 대해서도 성립합니다.
추가로 ∞ + ∞ = ∞ 도 성립하겠죠?
-------------------------------------------
자~ 이제 위의 경우들을 정리해서 써보겠습니다.
타원곡선 E : y2 = x3 + Ax +B 상의 두점
P1 = (x1, y1), P2 = (x2, y2)
에 대해서 P1 + P2 = P3 = (x3, y3) 이라고 하면,
1. x1≠x2
x3 = m2 - x1 - x2
y3 = m(x1 - x3) - y1
where m = (y2 - y1)/(x2 - x1)
2. x1 = x2, y1 ≠ y2
P1 + P2 = ∞
3. P1 = P2 , y1 ≠ 0
x3 = m2 - 2x1
y3 = m(x1 - x3) - y1
where m = (3x12 + A)/2y1
4. P1 = P2 , y1 = 0
P1 + P2 = ∞
5. 타원곡선 E 상의 모든 P에 대해
P + ∞ = P
이렇게 다섯가지 경우로 나누어 연산을 할 수 있겠습니다.
알아둘 것은..P1과 P2가 필드 L(A, B를 포함)의 좌표인 경우 P1 + P2 역시 L의 좌표가 됩니다.
즉 E(L)은 덧셈에 대해 닫혀 있습니다.
이제 정리로 써보겠습니다.
Theorem.
타원곡선 E 상에서 점들의 합은 다음 성질을 갖는다.
1. (commutativity) P1 + P2 = P2 +P1
2. (existence of identity) P + ∞ = P
3. (existence of inverses) P + P' = ∞ 를 만족하는 P'이 존재한다. P'을 보통 -P로 표기한다.
4. (associativity) (P1 + P2) + P3 = P1 + (P2 + P3)
즉, 타원곡선 E상의 점들은 ∞ 를 항등원으로 갖는 additive abelian group이다.
________________________________________________
이번엔 타원곡선의 점 P를 스칼라 곱 연산하는 방법에 대해 설명드리겠습니다.
곱하기는 더하기를 반복하면 됩니다.(간단;;)
근데 좀더 빨리 계산하는 방법으로 successive doubling이라는 게 있다네요..
19P를 successive doubling으로 계산하면
2P, 2P+2P = 4P, 4P+4P = 8P, 8P+8P = 16P, 16P+2P+P = 19P
이렇게 됩니다.(뭐..별거 아니죠?)
그리고 마지막으로 discrete logarithm problem에 대해 언급을 하겠습니다.
일반적으로(?)는 임의의 수 a를 k번 곱한 결과가 c라고 할 때, c와 a를 보고 k를 알아내기 어렵다는 의미로 쓰이는데요..(곱셈에 관한 문제)
타원곡선에서는 덧셈에 관한 문제가 된다고 합니다.
즉, kP와 P를 보고 k(P가 몇번 더해졌는지)를 알기 어렵다는 의미지요...(뒷장에서 자세히 다루도록 하겠습니다.)
이제 조금 타원곡선과 암호와의 관계가 드러나는 느낌이네요.^^..
점점 힘이 들지만...화이팅하도록 하겠습니다.(최소한 스스로에게는 도움이 된다고 생각하며..)
최근 덧글