8000 MIPS Year
걸린다.a^x(mod n)
은 빠른 시간에 구할 수 있다. 지수연산과 나머지 연산만하는 쉬운 계산이다.y = a^x(mod n)
인 지수 x 값을 구하는 것은 매우 어렵다.n = pq
ϕ(n) = (p - 1)(q - 1)
과 서로소인 수 e를 임의로 선택ed = 1(mod ϕ(n))
이 되는 d를 구함공개키 = (e, n)
, 개인키 = (d, p, q)
C = P^e(mod n)
P = C^d(mod n)
유한체
상에서 정의된 타원곡선 군
에서의 이산대수
문제에 기반y^2 = x^3 + ax + b
로 정의되는 타원곡선상에서 덧셈 연산
타원곡선 위에 있는 점들만을 대상으로 연산을 고려
타원곡선상의 덧셈 연산은 아래와 같이 정의된다.
R = kP
와 같의 정의했을 때 k를 구하는 것은 수학적으로 매우 어려운 문제