[암호학] 비대칭키 - ECC, Elliptic Curve Cryptostystem

---

[암호학] 비대칭키 - ECC, Elliptic Curve Cryptostystem

---

타원 곡선 암호(ECC, Elliptic Curve Cryptostystem)

 

1. 개요

• 키의 길이가 매우 커야 한다는 단점이 있는 RSA와 ElGamal 알고리즘을 보완하기 위해 개발된 알고리즘
• 동일한 수준의 보안성을 제공하면서 키의 길이는 짧아도 되는 암호 시스템이다. 
• 타원곡선 군에서의 이산대수의 문제에 기초한 공개키 암호 알고리즘이다.
• ECC는 전자상거래의 핵심기술이다.
• 160비트 ECC는 1024비트의 RSA키와 동일한 보안 수준이다.

항목	ECC 방식	RSA 방식
기반구조	WPKI(무선)	PKI(유선)
속도	빠름	느림
키 크기	상대적으로 작은 키	ECC에 비해 큰 키
적용	소영 Mobile 환경	인프라가 다소 구현된 환경

 

2. 특징

• 다양한 암호방식 설계가 용이하며, H/W와 S/W로 구현하기가 용이하다. 
• 스마트카드나 무선통신 단말기 등과 같이 메모리와 처리능력이 제한된 응용분야에 특히 효율적이다.

 

3. 타원 곡선의 정의

$y^{2} = x^{3} + ax + b$

타원곡선 그래프

• 타원곡선 그래프는 x축을 중심으로 대칭되며, 비 수직선에 대해 최대 3개 지점에서 곡선과 교차한다.

ECC 알고리즘, 타원곡선 그래프

 

4. 타원 곡선 상에서의 연산

• 타원 곡선을 이용한 암호화를 알기 위해서는 타원 곡선 상의 덧셈 연산을 이해해야 한다.
• 예시로 타원곡선상의 P와 Q의 덧셈 연산을 설명해보자면, P와 Q를 지나는 직선이 타원과 만나는 교점(R)을 x축으로 대칭시킨 점을 P + Q = R로 정의한다.
• 아래 그림의 두 번째 그래프는 같은 값을 가지고 있는 P를 구하는 타원 곡선이다. 덧셈 연산과 같이 P의 접접을 타원 곡선으로 이은 교점(R)을 x축으로 대칭시킨 점을 2P=R 로 정의한다.
• 세 번째 그래프는 x축에 대칭되는 값을 가지고 있는 P, -P를 구하는 타원 곡선이다. 이는 대칭 값이기 때문에 0이다.

ECC 알고리즘, 타원 곡선의 덧셈 연산

수학적으로는 아래와 같이 표시한다.

ECC 알고리즘, 타원 곡선의 덧셈 연산의 수학적 표시

 

5. 갈루아 필드 상에서의 타원 곡선(Elliptic Curves Over GF(p))

• 갈루아 필드는 유한체(Finite Field)를 의미하는데 유한개의 원소를 가지는 체를 뜻한다.
• x, y 좌표계에서 무한하지 않고 유한하게 한정된 곳에 존재한다.
• GF를 만들기 위해 모듈러(Modular)를 사용하고 mod P를 할 때 P는 소수로 정의한다.

갈루아 필드의 예시)

$E : y^{2} = (x^{3} + x)  over Z_{23}  (p = 23) $

갈루아 필드의 예시

• 위의 그래프가 무엇을 나타내는지 파악해 보자.
• 만약 x=9라고할 때 $y^{2} mod 23 = (729+9) mod 23 = 738 mod 23 = 2$ 이다.
• 이때 만족하는 y는 $5*5 mod 23 = 2$ 이므로 y는 5가 될 수 있다.
• 갈루아 필드의 p가 조금만 더 커지면 y를 쉽게 찾을 수 없게 되는 것을 활용해 암호학해 적용한 것이다.

 

6. ECC 에서의 Private-Key 와 Public-Key

• Private-Key d :   P 보다 적은 소수(Prime)로, 난수생성기로 생성한다.
  
• Public-Key Q :  $Q(x , y) = d x G(x_{0} , y_{0})$ 즉, 타원곡선의 '+'으로 만들어진다.
  
• “d x G” 란 “G를 d번 더한 값”을 의미 한다.( Q = G + G + …….G + G +G )
  
• G는 이미 알려져 있고, Q는 키 생성후 공개되어 진다.
• 하지만, G 와 Q를 안다고 해서, d 값을 유추해 내기가 굉장히 어렵다. 
  
• 이것을 ECDLP(Elliptic Curve Discrete Logarithm Problem)라고 부르며, 이러한 속성으로 인해 공개키 암호기술로 사용되어지게 되었다.

 

1) 실제로 이제 어떻게 계산하는지 한번 해보자.

• 우리는 현재 $G(α) = (2,7)$ 이라고 가정하고(지금부터 G를 α로 쓰겠습니다.)
• $2α = (x_{2}, y_{2})$를 계산해보자. 
• 우선 처음에 값은 하나밖에 없으니 doubling으로 들어간다.

ECC 에서의 Private-Key 와 Public-Key

 

• 이때 람다식을 구할 때 확장 유클리드 알고리즘을 이용하여 람다를 구할 수 있다.
• (13을 11로 나누면 2가 되고 14 mod 11을 하면 3^(-1)이 됨을 알 수 있다.)
• (이때 곱셈으로 변한 값을 mod 11씩 해주면 3^(-1) mod 11 은 4임을 알 수 있다.
• 이제 우리는 α, 2α, 3α, ... , kα를 구할 수 있게 된다.
• 이때 k*α는 '+'혹은 2α 공식을 이용하여 구할 수 있게 된다.
• 비밀키 * α = 공개키
• α = (2,7)  2α = (5,2)  3α = (8,3)
• 4α = (10,2)  5α = (3,6)  6α = (7,9)
• 7α = (7,2)  8α = (3,5)  9α = (10,9)
• 10α = (8,8)  11α = (5,9)  12α = (2,4)

 

7. 갈루아 필드 상에서의 암호화 / 복호화

갈루아 필드 상에서의 암호화 / 복호화

• 위와 같이 갈루아 필드 상의 타원 곡선이 존재하고 공개키 α = (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이 된다.

 

8. 타원 곡선 암호학(ECC)을 쓰기 유용할 때

• 계산 능력이 제한적일 때 (무선 장치, PC카드)
• 집적 회로 공간이 제한될 때 (무선 장치, PC 카드)
• 빠른 속도를 필요로 할 때
• 서명, 검증 또는 인증이 필요할 때
• 서명된 메시지를 저장하거나 전송할 때 (특히 짧은 메시지의 경우)
• 대역폭이 제한될 때 (무선 통신 및 일부 컴퓨터 네트워크)

 

9. ECC를 사용할 때 주의할 점

난수 생성기(Random Number Generatio)의 중요성

• RSA에 비교한 ECC의 약점은, 사용되는 Private-key의 bit 수가 적다는 것이다.
• Private-key는 난수 생성기를 통해서 만들어 지기 때문에, 품질이 떨어진(?) 난수 생성기를 사용할 경우, 공격자에 의해 Private-Key가 예측될 수 있다.
• 2013년에, Android 폰에 저장된 비트코인 지갑이 털리는 사건이 발생했는데, 원인은 안드로이드폰에서 동작되는 난수 생성기를 사용했기 때문이라고 보도되었다. 
• 추가로, HSM 장비는 H/W적으로 Random Number를 Cenerator 하는 기능을 제공하고 있으므로, 예측하기 어려운 Private-key를 생성하기 위한 장비로도 사용되어진다.