IT/정보보안
[암호학] 비대칭키 - ECC, Elliptic Curve Cryptostystem
액트
2019. 11. 26. 12:25
타원 곡선 암호(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개 지점에서 곡선과 교차한다.
4. 타원 곡선 상에서의 연산
- 타원 곡선을 이용한 암호화를 알기 위해서는 타원 곡선 상의 덧셈 연산을 이해해야 한다.
- 예시로 타원곡선상의 P와 Q의 덧셈 연산을 설명해보자면, P와 Q를 지나는 직선이 타원과 만나는 교점(R)을 x축으로 대칭시킨 점을 P + Q = R로 정의한다.
- 아래 그림의 두 번째 그래프는 같은 값을 가지고 있는 P를 구하는 타원 곡선이다. 덧셈 연산과 같이 P의 접접을 타원 곡선으로 이은 교점(R)을 x축으로 대칭시킨 점을 2P=R 로 정의한다.
- 세 번째 그래프는 x축에 대칭되는 값을 가지고 있는 P, -P를 구하는 타원 곡선이다. 이는 대칭 값이기 때문에 0이다.
수학적으로는 아래와 같이 표시한다.
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으로 들어간다.
- 이때 람다식을 구할 때 확장 유클리드 알고리즘을 이용하여 람다를 구할 수 있다.
- (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를 생성하기 위한 장비로도 사용되어진다.