타원곡선 알고리즘(ECC, Elliptic Curve Cryptography)

▣ 타원곡선 알고리즘(ECC, Elliptic Curve Cryptography)

타원곡선암호(ECC, Elliptic Curve Cryptography)는 타원곡선을 기반으로 한 암호방식

대표적인 공개키 방식

타원곡선암호 기술은 기존 RSA 암호방식에 대한 대안으로 1985년도에 제안된 방식

비트코인이 타원곡선암호 기술 방식에 속하는 타원곡선 디지털서명 알고리즘(ECDSA; Elliptic Curve Digital Signature Algorithm) 암호 알고리즘을 사용하고 있음

 

타원곡선 암호가 RSA나 엘가말 암호과 같은 기존 공개 키 암호 방식에 비하여 갖는 가장 대표적인 장점은 보다 짧은 키를 사용하면서도 그와 비슷한 수준의 안전성을 제공한다는 것임

특히 무선 환경과 같이 전송량과 계산량이 상대적으로 열악한 환경에 적합

 

 

타원곡선 암호화 알고리즘 키생성
G : 생성자, 타원곡선 상의 임의의 점
x : 개인키, P보다 작은 소수(Prime)로, 난수 생성기로 생성
Q : 공개키, 개인키로부터 연산

 

점 P=(x, y)가 타원곡선 상에 위치해 있을 때 두 점 P, Q와 임의의 정수 x에 대해 다음과 같은 방정식을 정의

이때 x의 값을 구하는 것이 타원곡선 이산대수 문제인데, 공개키 Q는 Q = xG = G + G + ... + G 으로 G를 x번 덧셈을 한 값임

Q = xG 수식에서 x와 G를 이용하여 Q를 구하기 쉽지만, 알려진 G값과 Q값을 통해 x값을 구하기 어려운 점을 이용

이러한 것을 ECDLP(Elliptic Curve Discrete Logarithm Problem)라고 부름

 

위와 같이 갈루아 필드 상의 타원 곡선이 존재하고

공개키 α = (2,7)인 상태에서 어떤 사람 A가 B에게 x(10,9)라는 평문을 보내고 싶어한다.

A가 선택한 비밀키 pk = 7이라 가정하자.

그리고 A가 선택한 난수 k = 3이라 가정하자.

이제 ECC에서 암호화 공식은 다음과 같다.

y1과 y2를 구할 것인데 그전에 β를 구해보자.

β는 위의 식에 나와있듯이 pk * α이다.

y1 = k*α이고 ( k는 Random Value, α는 공개키 )

y2 = x + k*β이 된다. ( x는 Plaintext )

위의 k, α, x 및 addition, doubling을 우리는 알고 있으니 y1, y2를 구할 수 있다.

이제 이 y = (y1,y2)를 B에게 보내면 B는 다음과 같이 복호화 과정을 거치면 된다

 

복호화 공식은 x = y2 - pk*y1이고 여기서 pk = 7이니 x = y2 - 7*y1이 된다.

---

2021년 104번

정답 : 1번

타원곡선 암호기술(ECC)은 타원곡선 방정식에 수학적 배경을 두고 있음