타원곡선암호
타원곡선암호(ECC; Elliptic Curve Cryptography)는 타원곡선을 기반으로 한 암호방식으로, 대표적인 공개키 방식 중 하나이다.[1] 타원곡선암호 기술은 기존 RSA 암호방식에 대한 대안으로 1985년도에 제안된 방식이다. 비트코인이 타원곡선암호 기술 방식에 속하는 타원곡선 디지털서명 알고리즘(ECDSA; Elliptic Curve Digital Signature Algorithm) 암호 알고리즘을 사용하고 있다.[2] 타원곡선 암호화 알고리즘이라고도 부른다.
목차
개요
타원곡선암호는 타원곡선 군의 연산에서 정의되는 이산대수 문제의 어려움의 이용을 기초로 하는 공개키 암호 알고리즘 시스템으로서 RSA/DSA와 같은 공개키 암호보다 짧은 키 길이와 빠른 연산속도를 가지면서 동일한 수준의 보안 강도를 제공하는 암호 알고리즘이다.[3] 보안을 강화하기 위해서 암호키의 길이는 늘리는 방법이 있지만 그에 따라 암호 연산 속도가 느려진다는 문제가 있다. 그래서 사람들은 RSA방식을 사용하여 암호키 길이를 늘리는 대신 타원곡선암호 기술을 선택하는 경우가 많다. 타원곡선암호는 유한체상의 타원곡선의 수학적 성질을 이용한 암호 기술을 이야기 한다. 공개키 암호화 방식 중 하나로 유한체 위에서의 타원곡선의 대수적 구조를 기반으로 한 이산로그 문제에 착안하여 만들어졌다. 유한체(Finite Field)는 집합에 속해 있는 원소의 수가 한정되어 있으며, 덧셈,곱셈 연산에 대하여 닫혀 있는 집합을 의미한다. 유한체를 사용하는 이유는 암호 연산은 정수를 기반으로 계산해야 하기 때문이다.[2] 타원 곡선의 방정식은 로 표현할 수 있으며 이러한 타원 곡선 암호화로 정도의 경우의 수를 얻을 수 있다.[4] 기존의 공개키 암호보다 적은 비트로 동일한 안전성을 얻을 수 있는 장점이 있고, 빠른 속도로 암호화를 처리하며 키 관리가 용이하기 때문에 채택률이 상승했다. 주로 비트코인의 소유권 증명, 미국 정보의 내부 통신 보호, 애플 서비스의 DNS 정보 암호화 등등에 사용되고 있다. 또한 사물인터넷의 경량 암호화로 한동안 주목을 받았고, 간편결제 인증에서도 사용된 사례가 있다.[5]
개념
타원곡선의 정의
대체로 사용되는 타원곡선 방정식은 다음과 같은 형태의 3차 방정식이다.
그러나 실수상의 타원 곡선은 다음과 같은 특별한 범주 내의 타원 곡선을 이용한다.
타원곡선은 일반적으로 타원 형태의 그래프를 생각하는 편이 더 쉽지만, 타원곡선 그래프의 곡선은 a와 b 각각의 값에 따라 다양한 형태의 타원 곡선을 정의할 수 있다. x축을 중심으로 대칭이 되는 구조이며, 비 수직선에 대해 최대 3개의 지점에서 곡선과 교차한다는 특징이 있다.
타원곡선 상에서의 연산
타원 곡선을 이용한 암호화를 이해하기 위해서는 타원곡선상의 덧셈 연산부터 이해를 해야한다. 따라서 기하학적으로 설명하자면 다음과 같다. 타원곡선 상의 P와 Q의 덧셈 연산은 점 P와 Q를 지나는 직선이 타원과 만나는 제 3의 교점을 x축으로 대칭시킨 점을 P+Q=R로 정의한다. P와 Q가 같은 경우에는 P+P 연산이 되므로 P점에서 접선을 그었을 때 타원과 만나는 제 3의 교점을 x축으로 대칭시킨 점에 해당한다. 또한, 무한대 값 0이 가능하고, P+(-P)=0 으로 P와 x축 -P가 덧셈한 결과 값은 무한대 값이다.
타원곡선의 이산로그 문제에 기반한 타원곡선 암호화
- 타원곡선 암호의 원리 및 키생성
타원곡선 암호는 타원곡선 위의 이산로그 문제가 어렵다는 사실을 이용한 공개키 암호 방식을 말한다. 이러한 타원곡선 암호화를 위한 타원곡선은 임의의 정수 a, b에 대해 정의된 다음과 같은 방정식의 해 (X, Y)의 집합이다.
점 P=(x, y)가 타원곡선 상에 있다는 것은 위의 방정식을 만족시킨다는 의미이다. 또한, 두 점 P, Q와 임의의 정수 x에 대해서 다음과 같은 방정식을 정의할 수 있다.
타원곡선 이산대수 문제는 바로 위와 같은 상황에서 해 x를 구하는 것이다. 이로부터 타원곡선 암호에서 사용하는 키 쌍은 다음과 같이 정의할 수 있다.
- G: 생성자, 임의의 시작 포인트이다.
- x: 개인키, P보다 적은 소수로, 난수생성기로 생성했다.
- Q: 공개키, 개인키로부터 연산한다.
이때의 공개키 Q의 경우, Q = x*G = G+G+...G(x번 덧셈)으로 G를 x번 더한 결과 값이다. Q = xG 수식에서 x와 G를 이용하여 Q를 구하는 것은 쉽지만, G와 Q를 안다고 해서, x의 값을 유추해내는 것은 상당히 어려운 타원곡선 이산대수 문제를 이용한다. G는 타원 곡선상의 임의의 점이며, x*G는 G를 타원곡선상에서 x번 덧셈 연산한 것을 의미한다. 다음은 x*G 연산 과정을 기하학적으로 도식화한 자료이다.
앞에서 설명한 타원곡선상의 덧셈 연산의 P+P 연산으로 다시 되돌아가 살펴보면, 2G=G+G는 점 G에서의 접선이 타원곡선과 만나는 제3의 점을 x축으로 대칭시킨 지점이다. 4G=2G+2G에 해당하는 점에서도 마찬가지로 접선을 그어 타원 곡선과 만나는 점의 x축 대칭 점에 위치한다. G의 상수 배 연산은 이를 계속 반복해서 표현할 수 있고, 이는 타원곡선 상에서 일어나는 특성을 보여준다. 타원곡선은 공개키 암호 체계를 수학적으로 진행하는 한 가지 방법으로 타원곡선을 이용해서 RSA, 엘가말(ElGamal), 디피-헬먼(Diffie-Hellman)의 구현이 가능하다.
- 타원곡선을 이용한 디피-헬먼
타원곡선 디피-헬먼은 타원곡선에 디피-헬먼 키 교환을 적용한 방법이다. 디피-헬먼 키 교환의 핵심은 서로 통신하는 송수신 자가 서로 같은 키를 공유하는 방법이다. 송수신 자를 각각 앨리스와 밥이라고 가정하자. 앨리스와 밥은 각각 개인키로 와 를 선택한다. 그리고 타원곡셈 덧셈 연산을 통해서 계산한 와 를 서로 교환한다. 그러면 앨리스는 밥으로부터 받은 에 개인키 를 타원곡선 덧셈 연산해서 비밀키 S를 생성한다. 반대로 밥 또한 앨리스로부터 받은 에 개인키 를 카원곡선 덧셈 연산을 통해서 앨리스와 동일한 비밀키 S를 생성한다. 따라서 앨리스와 밥은 별도의 비밀키 교환 없이 위와 같은 방식으로 서로 동일한 비밀키를 공유할 수 있다.
- 타원곡선을 이용한 엘가말
밥은 개인키 d를 생성한 후, 개인키 d로부터 타원곡선 상에서 계산된 공개키 를 앨리스에게 전달한다. 앨리스는 평문 P를 밥의 공개키를 이용하여 암호문을 생성해서 밥에게 전달하면, 밥은 밥의 개인키 d를 이용해서 평문 P를 복호화한다. 이 과정에서 암호화와 복호화를 진행할 때 사용되는 곱셈 연산은 앞에서 설명한 타원곡선 덧셈연산 방식을 이용한다. 이산대수 기반의 엘가말과 타원곡선을 이용한 엘가말의 키 생성, 암호화, 복호화 방식을 비교하자면 다음과 같다. 참고로 다음 중 은 임의의 난수이다.[5]
엘가말 공개키 암호 타원곡선 공개키 암호 공개키 개인키 암호화 복호화
특징
타원곡선암호를 쓰기 유용할 때
- 계산 능력이 제한적일 때 (무선 장치, PC 카드)
- 집적 회로 공간이 제한될 때 (무선 장치, PC 카드)
- 빠른 속도를 필요로 할 때
- 서명, 검증 또는 인증이 필요할 때
- 서명 된 메시지를 저장하거나 전송 할 때 (특히 짧은 메시지의 경우)
- 대역폭이 제한될 때 (무선 통신 및 일부 컴퓨터 네트워크[6]
공개키 알고리즘
공개키 암호 알고리즘(public key cryptosystem) 또는 비대칭키 암호 알고리즘이란 개인이 비밀통신을 할 경우엔 대칭키 암호를 사용할 수 있지만, 다수가 통신을 할 때에는 키의 개수가 급증하게 되어 큰 어려움이 따른다. 이런 어려움을 극복하기 위해 나타난 것이 공개키 암호이다. 공개키 암호는 다른 유저와 키를 공유하지 않더라도 암호를 통한 안전한 통신을 할 수 있다는 장점을 갖는다.
공개키 알고리즘은 서로 다른 키를 가지고 있으며 키의 이름은 공개키(Public Key)와 비밀키(Private Key)이다. 이 공개키와 비밀키를 만드는 알고리즘인 공개키 알고리즘은 두 가지 방식으로 분류할 수 있다. 소인수분해 문제를 이용해서 만드는 방법과 이산 로그 문제를 이용해서 만드는 방법이 있다. RSA는 소인수분해 문제를 선택하고 있다면 타원곡선 암호는 이산 로그 문제를 사용하고 있다.[7]
난수 생성기의 중요성
RSA에 비교한 타원곡선암호의 약점은 사용되는 프라이빗 키의 비트 수가 적다는 것이다. 프라이빗 키는 난수 생성기를 통해서 만들어지기 때문에 난이도가 낮다면 공격자에 의해 프라이빗 키가 예측될 위험이 존재한다. 타원곡선을 이용한 전자서명 알고리즘인 ECDSA 암호 알고리즘의 보안성은 사용되는 개인키의 보안성에 의해 좌우 된다. 그렇기 때문에 예측할 수 없는 난수를 가진 개인 키를 생성해야 한다.[2]
국제표준화 동향
각종 국제표준들에서 ECC에 대한 표준화가 활발히 진행되고 있고 실제로 다양한 응용 분야에서 ECC를 지원하고 있다. 표준화는 여러 가지의 다른 H/W와 S/W와의 상호운용성(interoperability)을 보장하고, 암호학적 관점에서 시스템의 안전도를 면밀하게 재검토할 수 있으며, 다양하고 폭넓은 환경에서 시스템을 구현하는 설계자들에게 암호 시스템을 설계할 수 있도록 도와주는 역할을 한다. 현재의 표준화는 ECC의 구현을 위한 많은 표준의 차이로 인해 서로 다르게 구현된 응용 사이에서의 호환성 문제가 대두됨에 따라 상호운용적인 보안솔루션의 개발 및 적용 시 사용자가 직면하는 문제점을 해결하기 위한 표준제정이라는 추세를 보이고 있다. 캐나다의 써티콤이 설립한 SECG(Standards for Efficient Cryptography Group)는 다양한 암호 솔루션 간에 발생하는 상호운용성의 해결, 각 솔루션에 타원곡선암호의 효과적인 편입, 스마트카드나 PDA 같은 제한적인 환경에서뿐만 아니라 일반적인 공개키 기반구조에 ECC가 널리 적용되도록 하기위한 표준화 정보제공 등을 목표로, SEC 1에서는 ECDSA(Elliptic Curve Digital Signature Algorithm: 미국연방표준 전자서명 알고리즘 DSA를 타원곡선을 이용하여 변형한 전자서명), ECDH(Elliptic Curve Diffie-Hellman: 타원곡선을 이용한 키 합의 프로토콜) 등을 포함하고, 선택사항에 대해서는 제약을 두어 여러 표준들 사이에 호환성을 높이고 있으며 SEC 2에서는 유한체의 크기마다 널리 쓰이는 권장 타원곡선 도메인 변수들의 선정기준을 제시하고 있다.[8]
안정성
타원곡선 이산로그에서는 인수분해나 유한체의 이산로그와는 달리 현재까지 알려진 적용 가능한 준지수시간 알고리즘이 존재하지 않고 Pollard-rho 알고리즘을 병렬화시킨 방법이 타원곡선 이산대수 문제를 푸는 가장 효율적인 알고리즘으로 알려져 있다. 이러한 알고리즘들을 피해 타원곡선암호를 안전하게 사용하기 위해서는 약 160비트 이상의 유한체에서 정의된 타원곡선을 사용해야 하며 취약성이 알려진 초특이곡선과 비정규곡선 및 트레이스가 2인 곡선은 반드시 피해야만 한다. 아래 표는 써티콤이 제시한 자료로서 RSA/DSA와 타원곡선에 대한 도메인 변수의 크기를 비교한 것이다. 이 표는 타원곡선암호의 안전도가 키 길이의 증가에 따라 거의 지수 함수적으로 증가하고 있고, 기존의 공개키 암호 시스템에 비해 장기적인 기술의 발전에 따른 키 길이의 증가 비율 면에서도 대단한 장점을 가지고 있음을 확인할 수 있게 해 준다.[8]
- 표. 동일한 안전도를 갖는 도메인 변수들의 크기 비교[8]
Time to break in MIPS(Million Instrucion Per Second) year RSA/DSA (bits) ECC (bits) RSA vs. ECC key size ratio 10^4 512 106 5:1 10^8 768 132 6:1 10^11 1024 160 7:1 10^20 2048 210 10:1 10^78 21000 600 35:1
- RSA
타원곡선암호를 RSA와 비교하면, 타원곡선암호가 RSA보다 더 짧은 키를 사용하지만 안전성 면에서는 RSA와 비슷한 수준을 제공한다. 타원곡선 암호화의 160비트 키 길이의 암호 강도는 이산대수의 특징을 이용한 비대칭키 알고리즘인 RSA 1024 길이의 키 강도와 맞먹는다. 키 값이 점점 커질수록 암호화 레벨은 RSA의 레벨보다 급격하게 상승한다. 타원곡선 암호화 방식은 더 적은 비트로도 동일한 안전성을 얻을 수도 있다. 그러나 단점은 RSA보다 연산이 더 복잡하다는 점이다.[5]
RSA와 타원곡선암호의 키 길이 비교(미국국립표준기술원 권장 키 길이) 대칭 키 크기 RSA 키 크기 타원곡선 키 크기 키 크기 비율 80 1024 160 7:1 112 2048 224 9:1 128 3072 256 12:1 192 7680 384 20:1 256 15360 512 30:1
장점
타원곡선 이론은 대수기하의 한 분야로서 자연스러운 군연산과 그 연산을 수행해주는 효율적인 알고리즘을 가지고 있어 암호학적 응용이 가능하다. 다른 공개키 암호시스템과 비교하여 타원곡선 이론의 장점은 다음과 같다.
- 주어진 유한체상에서 정의된 다양한 타원곡선을 선택할 수 있다. 주어진 소수 중에서 유한체의 부분군을 이용하는 것과 대조적인 모습을 통해 풍부한 타원곡선군을 활용할 수 있는 장점을 가진다.
- 초특이곡선같은 특별한 유형의 타원곡선을 제외하고는 알려진 이산대수 문제를 푸는 가장 효율적인 지수계산 알고리즘을 적용할 수 없어 안전한 암호시스템의 설계가 용이하다.
- 타원곡선암호는 다른 암호시스템과 비교하여 짧은 키 길이를 보유하고 있지만 대등한 안정성을 제공하여 높은 효율성을 보여준다.
- 타원곡선상의 연산은 유한체의 연산을 포함하고 있으므로 H/W와 S/W로 구현하기가 용이하다. 모든 사용자가 동일한 유한체와 유한체 연산을 수행하는 같은 H/W를 사용하더라도 서로 다른 타원곡선을 선택하여 사용할 수 있으며 추가 보안을 위해 주기적으로 타원곡선을 바꿀 수 있다.[9]
블록체인
비트코인 등 블록체인 기반 기술에서는 키 쌍을 생성할 때 타원곡선암호 알고리즘을 사용하며 키 길이는 256 비트 이상을 사용한다. 비트코인은 미국국립표준기술원에서 개발한 secp256k1 표준에 정의된 타원 곡선을 사용하는데, secp256k1 표준에 정의된 타원 곡선 수식은 다음과 같다. 위에엇 설명한 타원곡선 암호화 방식에 따라 개인키와 개인키로부터 계산된 공개키를 모두 생성한다.[5]
국내 현황
국내에서는 타원곡선암호가 가지는 많은 장점에도 불구하고 구현상의 어려움 때문에 접근이 어려운 상황이었으나 근래에 들어서는 타원곡선 암호기술을 탑재한 CSP(Cryptographic Service Provider) 모듈을 개발하고 타원곡선 암호기술을 접목한 무선 공개키 기반 인증 솔루션을 개발하는 등 한 차원 높은 다양한 보안기술 개발에 주력해오고 있다. 이에 따라 PKI(Public Key Infrastructure) 솔루션업체들은 무선인증시스템 구축을 완료했으며 시범 서비스를 거쳐 이르면 오는 9월 중 상용서비스를 시행할 계획이다. 이 서비스가 시작되면 그동안 무선인터넷 환경에서의 전자상거래 활성화에 가장 큰 걸림돌이던 보안 문제가 해결될 것으로 기대된다. 또한, 무선 시장에서의 경쟁력 확보를 위해서는 타원곡선암호의 상용화 기술의 특허를 피하면서 상호호환성과 함께 보다 효율적으로 구현할 수 있는 고속화 기술 및 최적화 방안에 대한 연구가 요구된다고 볼 수 있다.[8]
한계점
타원곡선 암호화 기법은 다른 암호화 기법에 비해 높은 효율을 보여주지만 한계점도 분명 존재한다. 그 한계는 구현의 어려움이다. 실제로 비트코인에서 사용된 타원곡선 암호화 기술도 오랫동안 OpenSSL에 기반한 모듈을 사용하다가 최근들어 자체적인 알고리즘으로 바뀌기도 했다. 현재 사물인터넷 기기들의 가장 큰 문제점이 무거운 공개키 기반 구조를 적용하기 어렵다는 부분인데, 타원곡선암호가 이에 대한 해결책으로 언급되지만 이 역시 구현의 어려움으로 지체되고 있다.[10]
각주
- ↑ ilovemylif, 〈타원곡선암호, Elliptic Curve Cryptography (1)〉, 《네이버 블로그》, 2018-01-17
- ↑ 2.0 2.1 2.2 AEP코리아네트, 〈비트코인에서 사용하는 타원곡선암호기술(ECC)〉, 《네이버 블로그》, 2018-01-05
- ↑ 밤공기후하후하, 〈암호학 - ECC, 타원곡선암호란 무엇인가〉, 《네이버 블로그》, 2018-08-23
- ↑ 〈타원 곡선 암호화〉, 《토큰 포스트》
- ↑ 5.0 5.1 5.2 5.3 김미영, 〈ECC 알고리즘〉, 《아이리포》, 2018-06-28
- ↑ 크로커스, 〈타원 곡선 암호학(Elliptic Curve Cryptography)〉, 《크로커스》, 2018-04-10
- ↑ 그래비티Grabity, 〈타원곡선 암호과 이더리움 전자서명 ( feat. 우주를 줄게 )〉, 《네이버 블로그》, 2019-03-26
- ↑ 8.0 8.1 8.2 8.3 심경아, 〈(정보보호) 타원곡선 암호시스템 급부상〉, 《한국정보통신기술협회》
- ↑ giaysm, 〈타원곡선 암호시스템 급부상〉, 《네이버 블로그》, 2014-12-09
- ↑ 안경잡이개발자, 〈타원곡선암호화 기법(Elliptic Curve Cryptographt)〉, 《네이버 블로그》, 2018-04-28
참고자료
- ilovemylif, 〈타원곡선암호, Elliptic Curve Cryptography (1)〉, 《네이버 블로그》, 2018-01-17
- AEP코리아네트, 〈비트코인에서 사용하는 타원곡선암호기술(ECC)〉, 《네이버 블로그》, 2018-01-05
- 밤공기후하후하, 〈암호학 - ECC, 타원곡선암호란 무엇인가〉, 《네이버 블로그》, 2018-08-23
- 그래비티Grabity, 〈타원곡선 암호과 이더리움 전자서명 ( feat. 우주를 줄게 )〉, 《네이버 블로그》, 2019-03-26
- giaysm, 〈타원곡선 암호시스템 급부상〉, 《네이버 블로그》, 2014-12-09
- 안경잡이개발자, 〈타원곡선암호화 기법(Elliptic Curve Cryptographt)〉, 《네이버 블로그》, 2018-04-28
- 〈타원 곡선 암호화〉, 《토큰 포스트》
- 크로커스, 〈타원 곡선 암호학(Elliptic Curve Cryptography)〉, 《크로커스》, 2018-04-10
- 심경아, 〈(정보보호) 타원곡선 암호시스템 급부상〉, 《한국정보통신기술협회》
같이 보기
- RSA
- 공개키 암호 알고리즘
- 타원곡선 디지털서명 알고리즘(ECDSA)