ECHC 암호 스키마
관련 수학 배경지식

(1) 타원곡선 (Elliptic Curve)의 정의
\Bbbk 를 임의의 체(field)라고 하고 타원곡선  \mathbb {E} 은 다음 방정식을 만족하는 점들의 집합이라고 하자.
{\begin{alignedat}{2}y^{2}&=x^{3}+Ax+B\\\end{alignedat}}  여기서  \ A,B\in \Bbbk  임이 성립한다. 이 때 이 방정식을 타원곡선에 대한 바이어슈트라스 방정식(Weierstrass equation)라고 한다. 또한, 타원곡선은 ``무한점(point at infinity)''을 포함하고 있고,  \infty 로 표기한다. 이 점은 쉽게  y-좌표의 맨 위에 있을 때임을 알 수 있다. 하지만  y-축의 맨 아래도 맨 위로 간주할 경우를 말하는 것이다.  {\overline {\Bbbk }}는  \Bbbk 의 대수적 폐포(algebraic closure)라 하며  \Bbbk 위에서의 타원곡선은  \mathbb {E} ({\overline {\Bbbk }})로 표기하고 다음과 같이 정의한다.
\mathbb {E} ({\overline {K}})=\left\{\infty \right\}\cup \left\{(x,y)\in {\overline {\Bbbk }}\times {\overline {\Bbbk }}\mid y^{2}=x^{3}+Ax+B\right\}
p를 소수,  a,b를 법  p에 대해서 0이 아닌 정수라고 하자. 이제, 다음을 만족하는 정수  k가 존재함을 고려하자.
a^{k}\equiv b{\pmod {p}}  위 식에서  k를 찾는 것을 이산 로그 문제(discrete logarithm problem)라고 한다.  k+(p-1) 또한 해이므로, 답  k는 법  p-1에서 정의되고 있음을, 혹은 만약  a^{d}\equiv 1{\pmod {p}}를 만족한다면  p-1의 약수  d임을 고려하자. 이러한 문제를 타원곡선에 대한 이산 로그 문제로 바라볼 수 있다. 타원곡선 위의 점  A,B에 대하여 적당한 정수  k가 존재해서  B=kA(=A+A+\cdots +A)이 성립한다고 하자. 우리는  k를 찾기 원하고 일반적으로 이 타원곡선에 대한 이산 로그 문제의 좋은 공격은 존재하지 않는다. 소수  p에 대하여  \mathbb {E} 를 법  p에 대한 타원곡선이라고 하고,  n을  nA=\infty 를 만족하는 최소의 양의 정수라고 하자.  만약  n이 작은 소인수를 가진다고 하면 그것은  n을 나누는 소수의 거듭제곱을 법으로 하는 이산 로그  k를 계산하는 것이 가능하다. 그러면 중국인 나머지정리(Chinese remainder theorem)를 적용하여  k를 찾을 수 있다.
(2) 유리수체  \mathbb {Q} 위에서 타원곡선의 군(Group) 구조
유리수체  \mathbb {Q} 위에서 정의된 타원곡선  \mathbb {E} 을 고려하자. 이 타원곡선  \mathbb {E} 위의 두 점  P_{1}=(x_{1},y_{1}),  P_{2}=(x_{2},y_{2})를 고려하고 타원곡선  \mathbb {E} 의 방정식은  y^{2}=x^{3}+Ax+B로 주어졌다고 하자. 이 때,  P_{1},P_{2}\neq \infty 이라 하자. 우리는 다음 각 상황에 대한  \mathbb {E} 위의 점  P_{3}를 구할 수 있다. 첫번째 경우는  P_{1}와  P_{2}를 지나는 직선을 그린다. (만약  P_{1}=P_{2}인 경우는 선  L은 점  P_{1}에서의 접선(tangent line)이다.) 선  L과 타원곡선  \mathbb {E} 의 교점  P_{3}^{'}를 얻을 수 있다.     P_{3}^{'}를  x-축에 반사시켜서 얻은 점을  P_{3}=(x_{3},y_{3})라 하자. 마지막으로 우리는 군 법칙을 다음과 같이 정의할 수 있다.
P_{1}+P_{2}=P_{3}
만약  x_{1}\neq x_{2}이면  m={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}일 때  x_{3}=m^{2}-x_{1}-x_{2},\;y_{3}=m(x_{1}-x_{3})-y_{1}이다.
만약  x_{1}=x_{2} 이지만  y_{1}\neq y_{2}이면  P_{1}+P_{2}=\infty 이다.
만약  P_{1}=P_{2} 이고  y_{1}\neq 0이면  m={\frac {3x_{1}^{2}+A}{2y_{1}}}일 때  x_{3}=m^{2}-2x_{1},y_{3}=m(x_{1}-x_{3})-y_{1}이다.
만약  P_{1}=P_{2} 이고  y_{1}=0이면  P_{1}+P_{2}=\infty 이다.  
더욱이  \infty 와  P를 지나는 선은  x-축과 수직이다. 이 선은 타원곡선  \mathbb {E} 의  P=(x,y)와  (x,-y)를 지난다. 점  P를  x-축에 반사시키면 점  (x,-y)를 얻는다. 그러므로  P+\infty =P임을 알 수 있다. 또한,  (x,y)와  (x,-y)를 지나는 선은 수직이므로 타원곡선  \mathbb {E} 와의 교점은  \infty 이다. 결과적으로  (x,y)+(x,-y)=\infty 임을 얻는다. 이 때,  \infty 는  \mathbb {E} 에서 항등원의 역할을 하기 때문에  -(x,y)=(x,-y)라고 정의하여야 하고, 이 사실은  (x,-y)는  (x,y)의 역원임을 의미한다.
(3) 유한체  \mathbb {F} _{p} 위의 타원곡선의 군(Group) 구조
\mathbb {F} _{p}위에서 정의된 타원곡선을 고려하자. 여기서  p는 홀수 소수이고  \mathbb {F} _{p}는 유한 소체이다. 그리고  a,b\in \mathbb {F} _{p}는  4A^{3}+27B^{2}\not \equiv 0{\pmod {p}}를 만족한다고 하면 매개변수  A,B\in \mathbb {F} _{p}를 가지는 유한체  \mathbb {F} _{p} 위에서 정의된 타원곡선  \mathbb {E} (\mathbb {F} _{p})은 다음 방정식의 해 혹은 점  P=(x,y)으로 구성된다.
y^{2}\equiv x^{3}+Ax+B{\pmod {p}}  이외의 점  {\mathcal {O}}은 무한점을 의미한다. 방정식  y^{2}\equiv x^{3}+Ax+B{\pmod {p}}은  \mathbb {E} (\mathbb {F} _{p})을 정의하는 방정식으로 불린다. 주어진 점  P=(x_{p},y_{p})에 대해서,  x_{p}는  P의  x-좌표, 그리고  y_{p}는  P의  y-좌표라고 불린다.  \mathbb {E} (\mathbb {F} _{p})에서 원소의 개수는  \#\mathbb {E} (\mathbb {F} _{p})라고 표현한다. `하세 정리'(Hasse Theorem)는 다음과 같이  \#\mathbb {E} (\mathbb {F} _{p})를 계산하는 방법을 소개한다.  만약  \mathbb {E} (\mathbb {F} _{p})는 유한체  \mathbb {F} _{p}에서의 타원곡선이면,
p+1-2{\sqrt {p}}\leq \#\mathbb {E} (\mathbb {F} _{p})\leq p+1+2{\sqrt {p}}
\mathbb {E} (\mathbb {F} _{p})에서의 군 법칙은 다음과 같다.
무한점끼리 합하는 규칙:            {\mathcal {O}}+{\mathcal {O}}={\mathcal {O}}  2. 무한점과 어떤 다른 점을 합하는 규칙:          모든  \;(x,y)\in \mathbb {E} (\mathbb {F} _{p})에 대해서, \;(x,y)+{\mathcal {O}}={\mathcal {O}}+(x,y)=(x,y)  3. 점들이 각각 구별되거나,  y-좌표가 0일 때,  x-좌표가 같은 두 점을 합하는 규칙:          모든  \;(x,y)\in \mathbb {E} (\mathbb {F} _{p})에 대해서,  \;(x,y)+(x,-y)={\mathcal {O}}  4.  x-좌표가 다른 두 점을 합하는 규칙 :  (x_{1},y_{1})\in \mathbb {E} (\mathbb {F} _{p})과  (x_{2},y_{2})\in \mathbb {E} (\mathbb {F} _{p})를  x_{1}\neq x_{2}를 만족하는 점이라고 하자. 그러면
(x_{1},y_{1})+(x_{2},y_{2})=(x_{3},y_{3})이고, 다음과 같다:            x_{3}\equiv \lambda ^{2}-x_{1}-x_{2},\;y_{3}\equiv \lambda (x_{1}-x_{3})-y_{1}, 그리고  \lambda \equiv {\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}{\pmod {p}}  5. 동일한 점끼리 합하는 규칙(double a point):  (x_{1},y_{1})\in \mathbb {E} (\mathbb {F} _{p})을  y_{1}\neq 0을 만족하는 점이라고 하자.       x_{3}\equiv \lambda ^{2}-2x_{2},\;y_{3}\equiv \lambda (x_{1}-x_{3})-y_{1}, 그리고  \lambda \equiv {\frac {3x_{1}^{2}+A}{2y_{1}}}{\pmod {p}}
\mathbb {E} (\mathbb {F} _{p}) 위에서의 점들의 집합은 더하기 연산을 가지는 군 형태이며 그 군은 가환군(abelian group)이다.(모든 점  P_{1},P_{2}\in \mathbb {E} (\mathbb {F} _{p})에 대해서,  P_{1}+P_{2}=P_{2}+P_{1}을 만족하는 것을 의미한다.) 주어진 정수  k와 점  P\in \mathbb {E} (\mathbb {F} _{p})에 대해서, 스칼라 곱은 점  P를  k번 더하는 과정과 같다. 이 스칼라 곱의 결과는  kP로 표현된다.
(4) 모델의 정리(Mordell's Theorem)
\mathbb {E} 를 표수가 0인 체(field)  \Bbbk 위에서 정의된 타원곡선(Elliptic Curve)라고  N을 양의 정수라고 하면 다음이 성립한다.
\epsilon [N]  \cong (\mathbb {Z} /N\mathbb {Z} )^{2}
단,  \epsilon [N] =\{P\in \mathbb {E} :[N]P={\mathcal {O}}\}
 =\{P\in \mathbb {E} :[N]P={\mathcal {O}}\}이다.