타원 곡선 암호(ECC)

x^2+y^2=1 를 만족하는 유리수 점은 몇 개가 존재할 것인가? 그것들을 체계적으로 찾을 방법은 없는가? 무한개. 찾는 방법은 아래와 같이 하나의 해 (-1,0)에서 유리수 기울기를 가지는 직선과 원의 교점을 구하면 된다. 기울기 한 값마다 한 점씩 나오므로, 유리수의 집합만큼의 점들을 찾을 수 있다.

1. find one such point : x=(-1,0) for example
2. draw a line that pass through x, y=rx+s s.t. 0=-r+s so s=r or y=rx+r
3. put this to x^2+y^2=1, then x^2+(r(x+1))^2 or (1+r^2)x^2+2r^2x+r^2-1=0
4. so, x=(-2r^2+2)/2(r^2+1)=(1-r^2)/(1+r^2), r이 유리수이니 당연히 x도 유리수이다.
5. (x,y)=((1-r^2)/(1+r^2), 2r/(1+r^2))

• 

그러면 x^2+y^2=3을 만족하는 유리수 점은 몇 개가 존재할 것인가? Do it yourself.
A,B,C가 서로소인 답 x=A/C, y=B/C를 생각하자. 서로소가 아니면 약분하면 결국 서로소인 답을 찾을 것이다. 이제 원래 방정식에 대입하면 A^2+B^2=3C^2인 정수해가 존재하느냐의 문제로 환원된다. 그러한 정수 해는 없다. 이유는 A혹은 B는 3의 배수일 수 없으며, A^2+B^2=0 mod 3인 정수해가 존재하지 않기 때문이다.

타원곡선에도 앞의 방법을 적용할 수 있을까? 타원 곡선 y^2=x^3-2의 하나의 해를 찾으면 (3,5)가 가능하다. 이제 이 점을 지나는 직선의 방정식 y=rx+(5-3r) 을 원래 방정식에 대입하면 (x-3)(x^2+(3-r^2)x+3r^2-10r+9)=0을 얻고, 예를 들어 r=1을 넣으면 x^2+2x+2=0을 얻는다. 앞서의 경우와 달리, 유리수의 해에서 시작해서 얻은 답이 유리수가 아니거나 이 경우처럼 아예 실수 해가 없는 경우가 발생한다.

1621년 프랑스 수학자 Bachet(Claude Gaspar Bachet Sieur de Mezirac,1581-1638)은 디오판토스의 저서를 라틴어로 번역하여 소개한 학자로 알려져 있다. 1621년 수학자 Meziriac은 그의 저서에 위의 문제, 즉 y^2=x^3+c 의 하나의 해 (x,y)를 찾았을 때, 그에 해당하는 다른 유리수 해를 어떻게 찾을 것인가?를 적고, 그 해가 ( (x^4-8cx)/4y^2, (-x^6-20cx^3+8c^2)/8y^3 ) 이라고 적는다. 이것을 Bachet’s equation이라고 부른다. 그가 어떻게 그 해를 찾았는지는 mystery이다.

그러나 그래프를 그려보면 대강의 방법을 추측할 수 있다. 아래는 y^2=x^3-2의 그래프이다. 어떤 하나의 유리수 해를 찾았을 때, 그 점을 지나는 아무런 직선이나 그으면 다른 유리수 점을 찾을 수 없는 경우가 많다. 그러나, 아래 모양을 보면 만약 그 점에서 접선을 그으면 다른 점과 만날 가능성이 높아 보인다.

• 

원래 함수를 미분하면 2ydy=3x^2dx 혹은 dy/dx=3x^2/2y, 접선의 방정식은 (y-y1)^2=(3x1^2(x-x1)으로 되므로, 접선과 원래의 곡선과의 만나는 점을 찾으면 Bachet의 답이 나온다.

• 

만약 y^2=x^3+ax^2+bx+c의 한 해 x를 안다면, 다른 해는 X=(x^4-2bx^2-8cx+b^2-4ac)/4y^2 이다. 이제 하나의 유리수 해 P를 알고 있을 때, 타원 곡선위의 다른 유리수 점을 찾는 방법은 다음과 같다.

1. Compute the tangent line of the curve at this point.
2. Compute the intersection with the curve, (-2P) then reverse the sign of y (2P)
3. The point you obtain is also a rational solution.

이것이 항상 성공하는 것은 아니다. 예를 들면, y=0인 점을 만나거나(nP=0), X=x, Y=y 로 더 이상 새로운 점이 없는 경우에는 성공할 수 없다. 그러면 이렇게 막힘 없이 계속 진행하여 무한개의 유리수해를 구할 가능성은 얼마나 있을까? 이전 포스팅에 했던 얘기를 간단히 아래에 다시 적어보자.

1908년 수학자 Beppo Levi(1875-1961)는 1908년 Levi’s conjecture 혹은 torsion conjectur를 통해서 다음 내용을 발표하고 1977년 Barry Mazur(1937~)는 이것을 증명한다. 60년만에 해결된 문제의 증명은 가볍게 skip.

• 

군이론에서 torsion group 혹은 periodic group이란 각 원소들이 finite order (유한 차수)를 가지는 군을 말한다. 가환군(Abelian group) A의 torsion subgroup은, 차수가 유한한 원소들만을 골라 subgroup을 만든 군을 말한다. Torsion-free abelian group이란, 1 외의 모든 원소의 order가 무한한 경우를 말한다. (Z,+), (R,+), (Q,+)등은 모두 torsion free abelian group이다.

===================

보통 desktop의 암호 알고리듬은 대칭키와 비대칭키 알고리듬이 있다. 대칭키는 암호화와 복호화에 양쪽에서 동일한 키를 가지고 암호하는 방식이고, 비대칭키는 양쪽이 동일할 필요가 없다. 비대칭키 방식에서는 부호측 키(공개키)와 복호측 키(개인키)가 서로 다른 경우이다. 대칭키 알고리즘에는 DES (data encryption astandard), AES(advanced encryption algorithm), ARIA(academy research institute agency)등이 있으며, 유무선 공유기혹은 기타 사이트에서 AES128, AES256 등을 선택한 경험이 있는 분도 있을 것이다. 비대칭키 방식은 DSA(digital signature algorithm), RSA(Rivest Shamir Adleman), ECC(elliptic curve cryptography) 등이 사용된다. ECC가 바로 eliptic curve에 기반한 암호화 방식이다.

• 

• 

대칭키 방식은 양쪽이 같은 키를 가지고 있으니 복잡한 알고리듬으로 부호와 복호를 하면 될 것이다. 그런데, 문제는 어떻게 양쪽이 같은 key를 가질 수 있느냐는 것이다. 그 키를 누군가가 해킹하면 곤란하기에 주기적으로 key를 바꿀 필요성이 당연히 있지만, 그 과정에서 두 사람이 매번 몰래 만날 수는 없을 것이다. 비대칭키 알고리듬은, 서로가 다른 키를 가지고, 특히 한쪽 키는 정보가 공개되어도 문제가 없는 암호알고리듬이니 엄청 복잡할 것이다. 인터넷에서 자료 하나를 다운 받을 때마다 이렇게 비대칭키로 암호화하는 것은 불필요하다. 따라서, 현대적 암호화 방식은 대칭키 방식의 키를 교환할 때, 비대칭키 알고리듬을 적용하는 것이다. 가장 대표적인 방식이 Diffie-Hellman (1977)이라고 부르는 방식이다. RSA개발 과정에 관한 재미있는 스토리들이 있지만, 본 게시의 목적이 타원곡선이론에 대한 이해에 있기에, 타원곡선 이론 기반의 암호화 방식에 대해서 간략히 조사해 보자.

아래 에니메이션 그림을 보면, 타원곡선 대수 방법에 따라 C=A+B 를 구하고, 다시 그점과 A를 잇는 점과 타원의 교점을 구하여 D=A+C=2A+B, E=D+A=3A+B로 계속 새로운 점을 찾아내는 것을 볼 수 있다. A와 B를 알려주고, 만약 100만번의 연산을 해서 도달하는 점은? 이렇게 질문하면 그렇게 어렵지 않게 풀 수 있다. 조금만 생각해 보면 100만번의 연산을 하지 않아도 비교적 효율적으로 더하는 방법을 찾을 수 있을 것이다. 그러나, 반대로 타원곡선위의 어떤 점 P를 주고, 이 점은 A에서 몇번 만에 도달할 수 있느냐? 란 질문을 던지면 이것은 참으로 해결하기 어려운 문제가 된다. 타원 곡선 암호는 이 질문을 암호화에 적용한 것이다.

Video Player

 

무한체 상에서 숫자를 다루기는 어려우니, 유한체 상의 타원곡선을 생각해 보자. 아래는 y^2=x^3-x+1이라는 곡선을 그린 것이다. 같은 곡선을 F_97 즉, GF(97) 상에서 그려보면 오른쪽 그림과 같은 전혀 곡선 같지 않은 타원곡선을 얻게 된다.

• 

유한체 상에서 앞서의 방법을 그대로 적용하여 A점에서 시작해서 B,C,D,E를 찾는 과정은 아래 애니메이션으로 설명된다. 숫자로 적으면 (x,y)=(70,6), (76,48), -, (82,6), (69,22) 를 찾을 수 있다.

Video Player

 

이 과정을 이해했다면, 이것으로 어떻게 암호화에 이용할지에 대한 감이 조금은 잡힐 것이다. 이제 타원곡선 암호 알고리듬을 적어보자
G: 생성자(generator), 타원곡선위의 임의의 점
p: 개인키(private key), P보다 작은 특정한 소수(prime)
Q: 공개키(public key), Q=pG
이제 점 G를 p번 더하여 Q=pG를 구한다. 당연히 타원곡선 더하기 방법으로 더한다. Q는 앞서 얘기한 데로 쉽게 구할 수 있다. 그러나, Q를 상대방에게 알려주고 p가 무엇인지를 물어보면, 당연히 그것은 평생 계산해도 구하기 힘들다. 이러한 문제를 ECDLIP(elliptic curve discrete logarithm problem)이라고 부른다. 따라서, Q는 마음놓고 상대방에게 공개키로 제공한다.

암호화의 양측에서 알고 있는 정보는 G와 Q 이다 (물론, 갈로아필드에 대한 모든 정보도). 이제, 공개키를 알고 있는 상대방 B가 보내려는 문자 x가 있다고 하자. 보내는 측 B에서는 f(x,n)=(y1, y2)=(nG, x+nQ)=(nG,x+npG)를 상대편에게 전송한다. n은 random 한 정수이다. 복호하는 측 A는 자신의 private key p를 가지고 있으므로, y2-py1= x+npG-npG=x 로 원래 정보를 복원할 수 있다.

보통 p와 n, 갈로아 필드의 체의 수가 엄청 큰 수이기에 긴 문장에 대해서 이렇게 매번 복/부호화를 행하는 것은 너무 많은 연산량을 요구한다. 따라서, 이러한 과정은 보통은 인증정보나 키를 교환하는 정도에 머문다. 실제 main text는 공개키 방식으로 암호화를 해야 하는데, 이 경우 동일한 key를 양쪽이 어떻게 소유할 수 있을까, 그리고 이것을 가끔씩 갱신가능하게 만들까 하는 것이 키배분 문제이다 (key distribution problem). 이것은 1977 Diffie와 Hellman이 해결하여 오늘날까지도 그 기본 아이디어는 그대로 사용된다.

키를 교환하려는 양즉은 (pA, QA=pAG)와 (pB, QB=pBG) 라는 (pri key, pub key)를 가지고 있다. 물론, 공개키 QA와 QB는 상대편에도 공개되어 있다. 이제, A측에서는 tA=pAQB 를 계산해서, B측에서는 tB=pBQA를 계산해서 상대편에게 각각 전달한다. 이것을 중간에 해킹하더라도 각자 어떤 private key를 가지고 있는지는 전혀 알 수 없다. ECDLIP 문제이기 때문이다. 이제 A측에서는 B에게서 전달받은 정보 tB에 자신의 private key pA를 곱한다, 즉, (pA)(tB)=pApBG 를 계산한다. 반대로 B는 A측에 받은 정보 tA를 가지고 같은 연산 즉, (pB)(tA)=pBpAG=pApBG를 얻는다. 서로가 상대방의 private를 모르지만, 둘은 이제 같은 대칭키를 가지게 된다. 이 과정에서 두 사람 외, 다른 사람들은 아무리 자세히 관찰해도 그 키에 관한 정보를 얻을 수 없다. 이것을 Elliptic-curve Diffie–Hellman 알고리듬이라고 부른다.