타원곡선

타원곡선(elliptic curve)은 $y^{2}=x^{3}+ax+b$ 형태의 방정식으로 나타나는 곡선으로서, 첨점이나 교차점 등의 특이점이 없는 것으로 중근을 갖지 않는 임의의 3차 혹은 4차 다항식 P에 대해 y2 = P(x)는 곡면 종수 1의 비특이 평면 곡선의 방정식이며, 보다 일반적으로는 종수가 1인 임의의 비특이 대수 곡선을 타원 곡선이라 한다.

개요

타원곡선은19세기 타원함수론과 함께 발전하였으나 타원하고 별로 상관이 없고, 형태상으로는 타원보다는 중괄호에 가까운 모양 으로서 '타원곡선'이란 이름이 붙은 이유는 타원의 둘레를 구하기 위한 적분에서 유래했던 역사적 이유 지만, 현재는 그것과 전혀 상관없이 사용 되고 있으며, 항목이 등재된 이유는 이름이 혼동스러워서인 것은 아니고, 수학 전반에서 엄청난 중요성을 갖고 있기 때문이다. 같은 대상을 실해석학에서, 복소해석학에서, 대수기하학에서, 정수론에서 모두 이야기할 수 있는 경우는 그렇게 많지 않다. 보통 y좌표가 무한대라는 설정인 무한점을 추가하는데, 이 무한점은 매우 중요하다.번외로 타원곡선에 대한 Birch and Swinnerton-Dyer 추측 은 클레이 연구소가 선정한 7개의 밀레니엄 문제 중 하나 이다.

정의

실수 위에서의 타원곡선은 a와 b가 고정된 실수일 경우에 방정식 $y^{2}=x^{3}+ax+b$ 을 만족하는 (x, y)점들의 집합을 의미한다. 우변인 x3+ax+b가 중근을 갖지 않으면, 즉 4a3+27b2 ≠ 0 이면타원곡선은 군을 정의 할 수 있는 대수적 특성을 제공하는 것이다. 원점이 주어진 대수곡선 이란 순서쌍 $(M,x_{0})x_{0}\in M,{\displaystyle M}$ M은 대수곡선)을 의미한다. 임의의 체의 표수에서, 타원곡선은 일반적으로 다음과 같은 같은 꼴의 식의 해의 집합으로 나타낼 수 있다.

1. 타원곡선은 특이점을 가지지 않는다.
2. 타원곡선은 복소수체의 경우 위상수학적으로 원환면곡면 으로 종수가 1이다.
3. 대수 곡선을 정의하는 식을 만족시키는 점 $(x,y)\in k^{2}$적어도 하나 존재하여 점은 무한대에 있을 수도 있으며, 적어도 하나의 유리점을 가진다.

$y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}$ 만약 체의 표수가 2나 3이 아닌 경우, 타원곡선은 다음과 같은 꼴의 식의 해의 집합으로 나타낼 수 있다.$y^{2}=x^{3}-px-q$ 여기서(1,x,y) (1,x,y)는 사영 평면의 동차좌표이고, 원점은(0,0,1) (0,0,1)이 된다. 이 점은(x,y) (x,y)평면에서의 무한대에 해당하며, (x,y) (x,y) 평면에 무한대를 추가하여 사영 평면을 취한 뒤, 타원곡선을 사영 평면 속의 곡선으로 간주한다. 체의 표수가 3인 경우, 일반적인 타원곡선은 다음과 같은 꼴의 식의 해의 집합으로 나타낼 수 있어 $y^{2}=4x^{3}+b_{2}x^{2}+2b_{4}x+b_{6}$ 체의 표수가 2인 경우는 위의 일반적인 표현을 사용하여야 한다.

역사

타원 적분(elliptic integral)에서 그 이름을 땄다. 이름과는 달리, 타원과 직접적인 관련이 없으며, 타원은 2차 곡선이므로, 곡선으로서 타원 곡선(3차 곡선)이 아니다. 현재 타원곡선으로 불리는 대상은 디오판토스가 최초로 이고, 디오판토스는$y(a-y)=x^{3}-x$꼴의 타원곡선에 대하여 기술하였다. 피에르 드 페르마와 아이작 뉴턴, 카를 구스타프 야코프 야코비, 카를 바이어슈트라스, 앙리 푸앵카레 등이 타원곡선에 대하여 연구 하였으며, 존 테이트 등이 타원곡선 이론을 수론과 연관지었다. 앤드루 와일스는 타원곡선에 대한 모듈러성 정리(의 상당 부분)을 증명하여, 이를 통해 페르마의 마지막 정리를 증명 하여 유한체에 대한 타원곡선은 암호론에서 타원곡선 암호를 정의하는 데 사용 한다.

특징

그림 1. 타원곡선y2=x3-9x-1와 타원곡선 위의 덧셈

• 그림 1은 y2=x3-9x-1 인 타원곡선이다. 실수 위에서의 타원곡선 군은 해당 타원곡선 위의 모든점들과 무한대 점이라고 명명된 특수 점으로 구성되고 여기에 덧셈이 정의된다. 점 P(x1 , y1)과 점 Q(x2, y2)를 더하기 위해서 P와 Q를 잇는 선을 그으면 타원곡선 위의 다른점 R과 교차한다. 만약 P=Q이면 점 P에 대한 접선을 그으면 된다. 계산한 점 R을 X축에 대칭을시킨 다른 점 S가 P+Q로 정의된다.

• 군 (Group)

군은 하나의 이항 연산자에 대해서 특수한 조건을 갖고 있는 수의 집합으로 모든 정수는 덧셈에 대해서 군을 이룬다. 정수를 정수와 더하면 정수가 나올것이고 덧샘은 결합법칙이 성립하는 연산 으로 정수 안에는 덧샘의 항등원인 0이 있고, 역원인 음수가 있다. 예를들면 42의 역원은 -42이고 항등원은 0이라면, 모든 정수가 덧셈에 대해서 군을 이룬다. 정수와 같이 덧셈에 대한 군을 덧셈군이라 부르고, 곱샘에 대해서 군이 성립하면 곱샘군이다. 요약하면 군은 정의된 연산자에 대해서 닫혀있어야 하고, 연산자에 대해서 결합법칙이 성립되어야 하며, 군 안에는 항등원과 역원이 있어야 한다. 군은 역원이 없으며, 2의 곱셈에 대한 역원은 1/2인데 이는 정수가 아닌 유리수 라고 하면 유리수에는 0이 있는데, 0은 곱셈에 대한 역원이 존재하지 않는다.(1/0은 계산할 수 없다)따라서 0을 제외한 유리수가 곱셈군을 이룬다. 또는 모든 타원곡선에는 다음과 같은 두 점을 더하는 매우 신기한 연산이 있다. 두 점 P = (x1 , y1)와 Q = (x2 , y2) 가 있다고 할 때, 이들의 합 P+Q는 이렇다.

1. P와 Q를 잇는 직선 l은 타원곡선과 다른 한 점 R = (x3 , -y3)에서 만난다.
2. R을 x축에 대칭시킨 S = (x3 , y3)가 P+Q가 된다.
3. 예외규칙 으로 무한점 ∞에 대해서는 "∞을 지나는 직선은 y축과 평행한 직선이다" 라는 규칙을 적용시키는데 l이 y축에 평행해서 다른 일반 점하고 안 만날 때는, R은 ∞로 정의 하고, P=∞일 때는, l은 'Q를 지나고 y축에 평행한 직선'이 된다.
4. 예외규칙 으로 l이 다른 한 점 R에서 만나지 않을 경우에는, l은 P 또는 Q에서 접할 것이고 이 때 R은 l이 접하는 점이 된다.
5. 예외규칙 으로 P=Q인 경우에는 l은 'P에서 그은 접선'으로 정의 하는데 l이 다른 한 점 R에서 만나지 않는다면 l은 P에서 변곡점을 가져야 하며, 이 때 R은 P로 생각한다.
6. 예외규칙 으로 ∞에서 그은 접선은 ∞에서 변곡점을 가진다. ∞를 x축에 대칭시키면 ∞이다.

• 타원곡선 군에서의 덧셈의 특성

1. 무한대 점은 O로 표기하며 타원곡선 위의 임의의 점 P에 대해서 P+O=P가 성립 되며, 무한대 점은 덧셈상의 항등원이 된다.
2. 타원곡선 위의 임의의 점 P에 대해서 P+Q=O를 만족하는 점 Q가 존재하는데 Q=-P로 나타내며 뺄셈 R-S는 R+(-S)로 정의 되고, 점 -P는 점 P의 X축의 대칭점이 되기 때문에 점 P의좌표가 (x, y)이면 점 -P의 좌표는(x, -y)이 된다.
3. 타원곡선 위의 임의의 점 P, Q와 R에 대해서 P+(Q+R)=(P+Q)+R이 성립한다. 타원곡선 위의 임의의 점 P와 Q에 대해서 P+Q=Q+P가 성립 하므로 타원곡선 군은'가환군'이 된다.

• 타원곡선 위에서의 기하학적 연산

타원곡선 위에서의 기하학적 연산은 그대로 대수적인 연산으로도 설명 이 된다. (x1, y1), (x2, y2), (x3, y3)을 각각 점 P, Q, S=P+Q의 좌표라 한다면, 점 P+Q의 좌표(x3, y3)을 통해서 표현 하고자 x1, x2, y1, y2 을 통해서 표현하고자 한다. R = (x3, y3)=-S 가 성립 되므로 y=αx+β 를 점 P와 Q를 지나는 선의 방정식이라 하면 이렇게된다.

만약, (αx+β)2 = x3+ax+b가 성립 하면 점 P와 Q를 지나는 선 위의 점(x, αx+β)는 타원곡선위의 점이 되고, 3차 방정식 x3 - (αx+β)2 + ax+b의 각각의 근에 대하여 한 개의 교차점 이 존재하게 된다. (x1, αx1+β)와 (x2, αx2+β)는 타원곡선 위의 두 점 P와 Q이기 때문에 이미 x1, x2가 근임을 알고 있다. 차수가 가장 높은 항의 계수가 1인 다항식에서 그 다항식에 존재하는 모든 근들의 합은 차수가두 번째로 높은 항의 계수에‘-’를 붙은 값과 동일하기 때문에 x1+ x2 + x3 = α2 이 된다. 나머지 근은 x3 = α2 - x1 - x2와 y3 = αx3+β = y1 + α(x3 - x1)이 된다. 그러므로 P+Q는 이렇다. P+Q에서 P=Q가 되며 는 점 P에서의 미분 값이 되기 때문에 음함수 미분을 하면 2yy'=3x2 / 2y1 가 된다.

< 예제 >

y2 = x3-17x+16 에 의해서 정의되는 타원곡선 위의 두 점 P=(0, -4), Q=(1, 0) 이 주어졌을 때, P+Q는 다음과 같이 구할 수 있다. 즉, x1=0 , y1 =-4, x2 =1, y2 =0 을 식-1에 대입을 하면 을 얻게 됨으로 P+Q=(15, -56) 이 된다.실수 계산은 일반적으로 느리며 또한 반올림에 따른 오차로 인하여 정확하지가 않기 때문에암호 응용에는 적합하지 않아서, 암호시스템 구축을 위해서는 유한체위에서 정의된 타원곡선 군이 이용된다.P가 소수일 때 유한체 GF(P)상에서의 타원곡선은 a,b∈GF(P)의 경우에 방정식 y2 mod p =x3+ax+b mod p을 만족하는(x, y)점들의 집합과 무한대 점 O를 의미 하고 x,y∈GF(P)이며, 4a3 + 27b ≠0 (mod p)이면 타원곡선 군이 정의 된다.

• 타원곡선 이산대수 문제

소수 p에 대해서 GF(p)를 p개의 원소로 구성된 유한체라 하면, 타원곡선 위의 점 P의 위수 t는 tP=O를 만족하는 가장 작은 정수 t로 정의 되고, GF(P)상에서 정의된 타원곡선과 점Q, 그리고위수가 t인 타원곡선 위의 점 P가 주어졌을 때 Q=xP를 만족하는 정수 x∈[0, t-1]을 구하는 것을 타원곡선 이산대수 문제 이다. 타원곡선 이산대수 문제의 가장 직접적인 해결방법은 Q를 구할 때까지 단순히 P, 2P=P+P, 3P=P+P+P, …를 연속적으로 계산하는 것이지만 t의 값이 매우 클 경우에는 실효성이 게 되어 현재까지 알려진 가장 효율적인 알고리즘은 Pollard의 rho알고리즘 으로서 번의타원곡선 덧셈이 소요된다. Pohlig-Hellman알고리즘 역시 적용이 가능하지만 t가 소수일경우에는 실효성이 없어지게 되면, 대부분의 학자들에 의해서 타원곡선 이산대수 문제는 소인수 분해나 이산대수 문제보다 훨씬더 어려운 문제로 인식이 되어진다. 타원곡선 이산대수 문제에 대한 좀 더 적극적인 공격은Pollard의 rho알고리즘에 기반을 두고 병렬처리를 가능하게 하는 특수목적의 하드웨어를 구축하는 것이다. 하지만 이런 공격도 t < 2160 인 경우에는 불가능하게 된다. 현재 타원곡선 암호에 적용 가능한 타원곡선 이산대수의 t값은 단기적으로 150비트, 장기적으로 180비트 이상이 권고 된다.

실수체상의 타원곡선 그래프

체에대한 타원곡선

• 실수체 위의 타원곡선

실수체 상에서, 타원곡선은 실수 a와 b에 대해 방정식 y2 = x3 + a x + b 로 정의되는 평면 곡선으로 1이 아닌 3차항의 계수와 0이 아닌 2차항의 계수는 x,y를 다시 정의함으로써 흡수시킬 수 있기에 우변이 임의의 x의 3차식이면 언제나 이런 형태의 식을 바이어슈트라스 방정식 으로 만들 수 있다. 타원곡선의 정의에는 이 곡선이 비특이하다는 조건이 포함되고, 기하학적으로 말하자면 이는 곡선의 그래프가 첨점이나 교차점이 없다는 뜻으로 판별식 Δ = −16(4a3 + 27b2)이 0이 아니라는 대수적인 조건과 동치이다. 비특이 대수 곡선은 판별식이 양수일 경우 두 개의 연결 성분을 가지고, 음수일 경우에는 하나의 연결 성분만을 가진다. 옆의 그래프에서 첫 번째 곡선의 판별식은 64, 두 번째 곡선의 판별식은 −368이다.

• 복소수체 위의 타원곡선

복소수체에서의 타원곡선은 1차원 아벨 다양체이다. 종수가 1이므로, 기하학적으로 이는 원환면의 모양을 하고 있다. 임의의 타원곡선$y^{2}=4x^{3}-px-q$가 주어졌다면, 원환면으로 여길 수 있으며, 복소 구조를 갖춘 원환면은 격자$\Lambda \subset {\mathbb {C} }$에 대한 몫공간 ${\mathbb {C} }/\Lambda$ 로 여길 수 있다. 그렇다면 이 원환면에서 타원곡선으로 바이어슈트라스 타원함수$\wp (z;\Lambda )$를 사용해 다음과 같은 사상을 정의할 수 있다.

$z\in {\mathbb {C} }/\Lambda$

$z\mapsto (x,y)=(\wp (z;\Lambda ),\wp '(z;\Lambda ))$

바이어슈트라스 타원함수는 다음과 같은 항등식을 만족시킨다. $\wp '(z;\Lambda )^{2}=4\wp (z;\Lambda )^{2}-g_{2}(\Lambda )\wp (z)-g_{3}(\Lambda )$ 따라서 이는 $(p,q)=(g_{2}(\Lambda ),g_{3}(\Lambda ))$ 인 타원 곡선과의 동형사상이다.

• 수체 위의 타원곡선

유리수체를 비롯한 다른 대수적 수체에 대한 타원곡선은 수론에서 중요한 위치를 차지하는데 수체에 대한 타원곡선의 점들은 보통 유리점 이라 하고, 주어진 수체 K에 대하여, 타원곡선 E의 K-유리점들의 집합 E(K)는 아벨 군을 이룬다. 모델-베유 정리에 따라서, 타원곡선의 유리점군 E(K)는 항상 유한 생성 아벨 군이며, 따라서 그 계수와 꼬임 부분군에 의해 주어진다. 유리수체의 경우, 유리점군의 꼬임 부분군은 메이저 꼬임 정리에 따라 15가지의 가능한 군 가운데 하나이며, 다른 수체의 경우에도 메이저 꼬임 정리와 유사한, 가능한 꼬임 부분군 목록들이 존재한다.

• 유한체 위의 타원곡선

유한체 $\mathbb {F} _{q}$에 대한 타원곡선은 유한 개의 점들로 이루어져 유한군을 이루고 점의 개수를 세는 것은 일반적으로 매우 어려운 문제이며, 수론의 주요 연구 분야 가운데 하나이다. 하세 정리에 따라 $\mathbb {F} _{q}$위의 타원곡선 E에 대하여, 그 점의 수 $\#E({\mathbb {F} }_{q})$는 다음과 같은 상계 및 하계를 가진다. $q+1-2{\sqrt {q}}\leq \#E({\mathbb {F} }_{q})\leq q+1+2{\sqrt {q}}$ 유한체에 대한 타원곡선의 점들이 이루는 유한군은 항상 두 순환군의 곱으로 유한체 ${\mathbb {F} }_{71}$에 대한 타원 곡선 $y^{2}=x^{3}-x$은 72개의 점 을 갖고, 그 군 구조는 2차 순환군과 36차 순환군의 곱이다. $({\mathbb {Z} }/2{\mathbb {Z} })\times ({\mathbb {Z} }/36{\mathbb {Z} })$유한체에 대한 타원곡선은 타원곡선 암호를 정의 하는데 사용한다.

공개키 암호

• 다른 공개키 암호와 비교

RSA공개키 암호나 DSA디지털 서명의 경우에 법 n과 p의 크기가 각각 1024비트 이상이 되고, 타원곡선 암호의 경우에는 160비트 이상이 요구 되므로 타원곡선 암호의 경우에는 RSA나 DSA보다 짧은 키를 가지고도 높은 수준의 안전성이 보장되기 때문에 실제 구현에있어서 안전성과 효율성이 모두 뛰어난 암호로 인식 되고 있다.

< 타원곡선 이산대수와 소인수 분해에 소요되는 계산량 >

$p(bits)$	$t(bits)$	구문 분석 실패 (구문 오류): {\displaystyle √π{t/2} }
공개키	(g,py=g^{2}mod p)	(G,p,Y=xG')
개인키	(x)	(x)
암호화	(c1,c2)=(g^{%} mod p, y^{%}m mod p)	(C1,C2)=(x'G,x'Y+M)
복호화	C1, C2^{%} mod p	C2-xC1

< 타원곡선 이산대수와 소인수 분해에 소요되는 계산량 >

• 타원곡선 공개키 암호

이산대수에 기반을 둔 ElGamal 공개키 암호는 타원곡선 이산대수에 기반을 둔 공개키 암호로 전환된다. 두 시스템에서의 암호화 및 복호화 그리고 공개키 및 개인키를비교하면, 타원곡선 공개키 암호에서는 공개키 G와 Y 그리고 평문 M과 암호문C1과 C2는모두 타원곡선 위의 점으로 두 시스템간의 기본적인 차이점은 ElGamal 공개키 암호에서의지수승과 곱셈작업이 타원곡선 공개키 암호에서는 각각 배수와 덧셈 작업으로 전환되어진다.

< ElGamal 공개키 암호와 타원곡선 공개키 암호 비교 >

	ELGamal 공개키 암호	타원곡선 공개키 암호
공개키	$(g,py=g^{2}modp)$	$(G,p,Y=xG')$
개인키	$(x)$	$(x)$
암호화	$(c_{1},c_{2})=(g^{\%}modp,y^{\%}mmodp)$	$(C_{1},C_{2})=(x'G,x'Y+M)$
복호화	$C_{1},C_{2}^{\%}modp$	$C_{2}-x_{C}{1}$

참고자료

• 우용이, 〈타원곡선〉, 《네이버》, 2017-11-27
• 코원동서, 〈타원곡선 암호 시스템(공개키 암호)〉
• 〈타원곡선〉, 《위키백과》
• 〈타원곡선〉, 《나무위키》

같이 보기

• RSA
• 공개키 암호 알고리즘
• 타원곡선 암호
• 타원곡선 디지털서명 알고리즘

이 타원곡선 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반