ECC 알고리즘, ECDH와 ECDSA

지난 시간에는 ECC알고리즘에 대해서 알아보았기 때문에

이번에는 이어서 ECC알고리즘의 종류에 대해서 알아보려고 한다.

 

ECC알고리즘 중에서 대표적으로 ECHD와 ECDSA가 사용되는데

이 두 가지 알고리즘의 특징과 용도를 알아보려고 한다.

 

ECDH(Elliptic-curve Diffie–Hellman)

먼저 ECDH에 대해서 알아보기 전에 앞서 Diffie Hellman에 대해서 알아야 한다.

Diffie Hellman은 이산대수 문제인 모듈러 지수 연산을 이용하는데,

암복호화나 서명/검증을 하기 위한 것이 아닌  키 교환 알고리즘을 통해 대칭키를 공유하는 데 사용된다.

 

ECDH의 경우 이 Diffie Hellman에서 사용한 모듈러 지수 연산대신 타원 곡선 알고리즘을 통해 키교환을 하는 알고리즘이라고 보면 된다.

키 교환 방법은 아래와 같다.

1. 영희와 철수가 각각 개인키 da, db를 생성한다.

2. G값을 활용하여 공개키 Ha, Hb를 생성한다

3. Ha, Hb를 서로 교환한다.

4. 교환된 키값을 이용하여 daHb, dbHa값을 구한다.

5. 이때 생성된 S=dadbG값이 

 

여기서 생성하는 G(x, y)의 값은 아래 타원 곡선 알고리즘 중 하나를 선택하여 생성하게 된다.

 

ECDSA(Elliptic Curve Digital Signature Algorithm)

ECDSA는 DSA 대신에 타원곡선 기술을 사용한 전자서명에 사용되는 알고리즘이다. DSA의 경우 RSA와 마찬가지로 상대적으로 Key의 길이가 크지만 ECDSA의 경우 이를 보완하여 Key의 길이가 작다는 장점이 있다. ECDSA의 경우 주로 모바일 기기들에서 사용되는데 빠른 연산이 필요하기 때문에 주로 ECDSA방식을 통한 전자서명/검증을 한다.

 

ECDSA의 서명 생성 과정은 아래와 같다.

1. 1~n-1에서 random number k를 선택한다. 

2. P(xp, yp) = kG(x, y) 값을 계산한다. G는 ECDH와 동일하게 타원 곡선 알고리즘  중 하나를 선택하여 생성한다.

3. r ≡ xp(mod n)을 만족하는 r을 계산한다.

   만약 r = 0일 경우 k값을 다시 선택하여 계산한다.

4. s ≡ k^-1(z + rda) (mod n)을 계산한다.

   만약 s ≡ 0 (mod n)이면 k를 다시 선택하여 위 과정을 반복한다.

 

다음으로 검증 방법은 아래와 같다.

1. u1 ≡ s^-1z(mod n)를 계산

2. u2 ≡ s^-1z(mod n)를 계산

3. P(xp, yp) = u1G + u2Ha를 계산

4. r ≡ xp(mod n)이면 유효한 서명 검증 완료.