[정보보호] Elliptic Curve Cryptography

ECC는 타원 곡성의 특징을 기반으로 하는 public key crypto 기술(공개키, 개인키 두개 사용)로, 타원 곡선의 특성을 활용하여 작은 bit 크기의 키로도 효율적인 보안을 제공할 수 있다.

이는 비교적 최근 기술이므로 다른 암호화 기술에 비해 분석이 덜 되었지만 그럼에도 불구하고 효율성이 뛰어나다. 

 

 

기본 개념

elliptic curve는 다음과 같은 식의 형태로, 위 식을 만족하는 모든 (x,y)가 집합 E(a,b)에 속한다. 

 

 

---

Finite Elliptic Curves

 

Finite Elliptic Curves는 Zp(소수 p를 사용하여 정의된 정수 집합) 또는 GF(2^m) 상의 타원 곡선이다. ECC에서는 variable과 coefficient가 finite 한 값이어야 한다. 현재 finite field 에서는 geometric interpretation이 명확하지는 않다.

 

Elliptic Curve Cryptography

ECC addition은 modulo multiply와 비슷하고, ECC repeated addition은 modulo exponentiation과 비슷하다. 

ECC에서는 discrete logarithm과 유사한 어려운 문제가 필요하다. 

Q = kP에서 Q,P가 prime curve에 속한다고 하자. k와 P가 주어졌을 때 Q를 계산하는 것은 쉽지만, Q와 P가 주어졌을 때 k를 계산하는 것은 어렵다. 이것을 elliptic curve logarithm problem이라고 한다. 

 

<예제>

P의 k배를 brute force로 하여 Q를 만드는 k 값을 찾았다. 실제 상황에서는 k가 훨씬 더 클 것이므로, brute-force로는 infeasible 하다. 

 

---

 

ECC Diffie-Hellman

 

ECC에서 DH와 유사한 key change를 할 수 있다. 

 

1. suitable curve Eq(a,b)를 고른다.

2. Base point G=(x1,y1)을 고른다. 이 때 nG = O인 n이 존재한다. O는 타원 곡선 상의 원점을 나타내고, n이 큰 소수일수록 elliptic curve logarithm problem이 더 어려워진다. 

3.

4. attacker은 주어진 kG와 G로 k를 찾아야 하는데, elliptic curve logarithm problem에 의해 이는 어렵다. 

 

ECC Encryption / Decryption

이는 ElGmal encryption과 유사하다. 메시지 M을 elliptic curve 위의 Pm으로 encrypt 하고자 한다고 하자. 

먼저 DH처럼 curve와 base point G를 고르고, 다음과 같이 과정을 진행한다. 

 

 

ECC Security

- ECC가 풀기 어려운 이유는 elliptic curve logarithm problem 때문

- elliptic curve logarithm problem을 효율적으로 푸는 알고리즘 중 하나는 Pollard rho method가 있다.

- 같은 수준의 보안을 유지하면서도 ECC는 작은 키를 사용할 수 있기 때문에 계산 상의 이점이 있다.