타원곡선 암호

"타원곡선"은 특정한 암호체계가 아니다.
타원곡선들은 공개키 암호체계에서 요구되는 복잡한 수학 연산을 수행하는 또 다른 방법을 단순히 제공하는 것이다.

타원곡선 암호(ECC)
장점 : 타원곡선인 경우가 아닌 경우와 비교해 같은 수준의 보안성을 위해 필요한 비트 수가 적다는 것
단점 : 타원곡선이 복잡해 타원곡선의 수학에는 비용이 다소 더 든다는 점

그러나 전체적으로 볼 때 타원 곡선은 계산적 장점을 제공.
그래서 ECC는 휴대용 장비 같은 자원이 제한되는 환경에서 특별히 선호된다.

타원곡선 E는 아래 함수 그래프의 형태이다.
E : y^2 = x^3 + ax + b

∞로 표현되는 무한대의 특수한 점도 함께 포함한다.


위 그림은 타원곡선 상에서 두 점의 함을 찾는데 사용되는 방법도 설명하고 있다.
두 점 P1, P2 더하기 위해 두 점을 지나는 선을 그린다. 일반적으로 그 선은 곡선상에서 서로 다른 점과 만난다.

만약 그렇게 만나면 이 다른 점은 x축에 반사되어 그 합을 P3으로 얻는다. 

P3 = P1 + P2

타원곡선에서 필요한 유일한 수학은 바로 덧셈이다. 
암호를 위해 점들의 이산 집합이 요구된다.

이것은 다음과 같이 원래의 타원곡선 공식에 "mod p"를 더하면 수행될 수 있다.

y^2 = x^3 + ax + b (mod p)

예를 들어 아래의 타원곡선을 생각해 보자.

y^2 = x^3 + 2x + 3 (mod 5)   --- ①

이 곡선 상의 모든 점 (x,y)에 대해 가능한 x값과 이와 일치하는 y값을 계산해 나열해 보자.
 
x = 0 ==> y^2 = 3 ==> 해가 없음 mod 5
x = 1 ==> y^2 = 6 = 1 ==> y = 1,4 mod 5
x = 2 ==> y^2 = 15 = 0 ==> y = 0 mod 5
x = 3 ==> y^2 = 36 = 1 ==> y = 1,4 mod 5
x = 4 ==> y^2  = 75 = 0 ==> y = 0 mod 5

① 식의 타원곡선 상의 점들은 다음과 같다.
(1,1), (1,4), (2,0), (3,1), (3,4), (4,0), ∞

이제 두 점을 합하는 알고리즘을 살펴보자

주어진 조건 : 곡선  E: y^2 = x^3 + ax + b (mod p)
                   E 상에서 P1 = (x1,y1), P2 = (x2,y2)
구하고자 하는 해: P3 = (x3,y3) = P1 + P2

알고리즘
x3 = m^2 - x1 - x2 (mod p)
y3 = m(x1 - x3) - y1 (mod p)

m 값
만약 P1과 P2가 같지 않다면 (if P1 ≠ P2)
(y2 - y1) * (x2 - x1)^-1 mod p
만약 P1과 P2가 같다면 (if P1 = P2)
(3x1^2+a) * (2y1)^-1 mod p

특수한 경우 1 : if m = ∞ 이면 P3 = ∞
특수한 경우 2 : 모든 점 P는 ∞ + P = P  

예제 문제 ( 위 에서 사용한 E 곡선 그대로 사용 mod 5 )

P3 = (1,4) + (3,1)

m = (1 - 4) * (3 - 1)^-1 mod 5 = -3 * 2^-1 mod 5 = -3 mod 5 * 2^-1 mod 5 = (2 * 3) mod 5 = 6 mod 5 = 1 mod 5
m = 1

x3 = 1^2 - 1 - 3 = -3 mod 5 = 2 mod 5
y3 = 1 * (1 - 2) - 4 = -5 mod 5 = 0 mod 5

P3 = (2,0)
P3 점도 y^2 = x^3 + 2x + 3 (mod 5)이 곡선 위의 한 점이라는 것을 확인할 수 있다.
0 =  8 + 4 + 3 = 15 mod 5 = 0 mod 5

이제 타원곡선 상에서 덧셈을 할 수 있으므로 다음 글에선 ECC 디피-헬먼(디피-헬먼 타원곡선 암호 버전)에 대해 알아보겠다.