Elliptic curve cryptography 개요
타원곡선 암호기술(Elliptic-curve cryptography, ECC)은 1985년 Neal Koblitz와 Victor Miller에 의해 개발된 암호 기술로서, 타원곡선 이론에 기반한 암호 방식이다.
수학에서 타원곡선(Elliptic curve)은 y2 = x3 + ax + b 라는 방정식으로 정의되는 곡선을 말하는데, a와 b 값에 따라 다른 곡선 형태와 크기를 갖게 된다. 타원곡선을 사용하는 암호화 기술인 Elliptic Curve Cryptography (ECC)는 유한체(Finite Field) 상의 타원곡선이 갖는 대수적 구조에 기반하여 공개키 암호 시스템을 구축한 것이다.
타원곡선(Elliptic curve)에 기반한 ECC를 사용하는 암호화 기술로는, 타원곡선을 사용하여 Diffie–Hellman 키 교환을 구현한 Elliptic Curve Diffie–Hellman (ECDH), DSA를 타원곡선을 사용하여 구현한 Elliptic Curve Digital Signature Algorithm (ECDSA), Schnorr 서명 방식에 기반한 Edwards-curve Digital Signature Algorithm (EdDSA), 타원곡선을 사용한 암호화 방식인 Elliptic Curve Integrated Encryption Scheme (ECIES) 등이 있다. 즉, 타원곡선 암호기술은 키 교환, 암호화, 디지탈 서명 등에서 두루 사용될 수 있다.
ECC에서 사용되는 암호키는 RSA에 비해 상대적으로 작으며, 이 때문에 ECC는 적은 메모리를 사용하며 빠른 성능을 갖게 된다. 아래 표는 대칭 암호에 상응하는 보안 레벨을 갖기 위해 비대칭 암호인 RSA와 ECC에서 얼마만큼의 키 사이즈를 가져야 하는지는 비교한 표이다. 일반적으로 ECC는 대칭 암호키 사이즈의 2배에 해당하는 크기를 가지며, RSA에 비해 상대적으로 매우 적은 크기를 가지게 된다.
| 대칭키(Symmetric) 암호 | RSA | ECC |
|---|---|---|
| 56 | 512 | 112 |
| 80 | 1024 | 160 |
| 112 | 2048 | 224 |
| 128 | 3072 | 256 |
| 192 | 7680 | 384 |
| 256 | 15360 | 512 |
암호화 알고리즘이 어느 정도의 보안 레벨인지를 표현하기 위해서 그 암호를 해킹하는데 얼마만한 에너지가 필요한 지를 따져 보았을 때, RSA 228bit Key를 해킹하는데는 티스푼 하나의 물을 끊일 정도의 에너지가 필요한 반면, ECC 228bit Key를 해킹하는데는 지구상의 모든 물을 끊일 정도의 에너지가 필요하다고 한다.
타원곡선(Elliptic curve)
타원곡선은 y2 = x3 + ax + b 라는 방정식(Weierstrass normal form)으로 정의되는 곡선을 말하는데, 이는 우리가 보통 알고있는 타원(ellipse) 모양을 가리키는 것이 아니라, a와 b 값에 따라 여러 모양의 곡선을 가지게 된다.
타원(ellipse)은 2차 방정식에 기반하지만, 타원곡선(elliptic curve)은 3차 방정식을 사용하며 처음에 타원 둘레의 길이를 구하기 위해 만들어져서 타원곡선이라 부른다.
유한체 상에서의 타원곡선
타원곡선 암호기술(ECC)에서는 실수가 아닌 유한체(finite field) 상의 타원곡선을 사용한다. 즉, ECC는 타원곡선의 (x, y)를 유한체 상의 요소들로 제한하는 것이다. 타원곡선 암호에서는 특히 유한체 중 소수체(prime field)와 이진 확장체(binary extension field)를 사용하고 있다. 유한체의 한 종류인 소수체는 정수를 소수 p로 나눈 나머지 집합으로 흔히 GF(p) 혹은 Fp로 표기하며, Fp는 {0, 1, 2, ..., p-1} 과 같은 집합을 갖는다. 소수체 상의 타원곡선은 아래 식과 같이 각 점의 요소가 소수 유한체의 요소이며, 타원곡선의 식에 모듈러 연산 (mod p)를 적용한 것이다.
ECC는 크게 Prime Curve 혹은 Binary Curve 상에서 정의될 수 있는데, 위에서 설명한 소수체 상에서 정의되는 것을 Prime Curve라 하고, GF(2m) 으로 표현되는 이진 확장 유한체 상에서 정의되는 것을 Binary Curve라 한다.
실수의 타원곡선이 연속적이고 무한한 범위를 갖는 반면, ECC에서 사용하는 타원곡선은 소수체(GF(p)) 혹은 이진 확장 유한체(GF(2m))를 사용하여 점들이 유한하면서 불연속적인 정수값을 갖게 된다. Prime Curve를 사용하는 ECC에서 타원곡선은 E: y2 = x3 + ax + b (mod p) 와 같이 정의된다. 예를 들어, p = 71 인 유한체(F71) 상에서 타원곡선 E: y2 = x3 + 7을 사용한다면, x = 11 일 때, y2 = 113 + 7 (mod 71) = 1338 mod 71 = 60 이 된다. 이때, y2 = 60 (mod 71)을 구하기 위해, 1부터 70까지 순차적으로 y에 대입(전수조사)해 보면, y가 29와 42일 때 60이 나오는 것을 알 수 있다. 아래 그림은 타원곡선 y2 = x3 + 7을 사용할 때, 소수 p가 71인 유한체에서 사용되는 전체 포인트들을 표시한 것이다. 여기서 Fp 상의 타원곡선은 실수에서와 마찬가지로 아벨군의 조건들을 만족한다.
유한체 상의 타원곡선은 연산에서 항상 모듈러 연산(mod p)을 적용하기 때문에, x, y 값이 p-1 보다 크면 모듈러 연산을 통해 나머지 값을 구하게 된다. 또한, 연산에서 음수값이 나오면, 이는 다시 해당 음수값에 상응하는 양수값으로 변환하여 사용한다. 이러한 모듈러 연산으로 인해, 유한체 상의 타원곡선은 x축에 대칭인 -y 값을 갖지 않고, 양수로 변환된 값을 갖는다. 즉, 그래프 상에서 y는 모두 양수이고 중간 지점의 y값을 기준으로 대칭인 모양을 갖는다.
타원곡선 이산 로그 문제
이산 로그 문제(DLP)는 이산 거듭 제곱의 역으로, ga (mod p) ≡ b 에서 g와 b가 주어졌을 때 a를 구하는 문제이다. ga (mod p)를 계산하는 이산 거듭 제곱은 쉽지만, g와 b만 주어졌을 때 a를 구하기는 매우 어렵다는 점에서 이산 로그 문제는 일방향 함수로 사용된다.
타원곡선 이산 로그 문제(Elliptic Curve Discrete Logarithm Problem, ECDLP)는 타원곡선에서의 이산 로그 문제를 일컫는 것으로, nP = X에서 P와 X를 알고 있을 때 n을 구하는 문제이다. 타원곡선의 스칼라 곱셈에 의해 nP를 빠르게 계산할 수 있지만, 반대로 n을 찾아내는 것은 매우 어렵다는 점에서 ECDLP는 DLP와 같이 일방향 함수로 사용된다. ECDLP는 이산 로그 문제를 타원곡선에 적용한 것으로 통상적으로 포인트 나눗셈 문제라고 부르지 않고 기존 암호시스템의 관습에 따라 타원곡선 이산 로그 문제라고 부른다.
타원곡선에서 스칼라 곱셈은 Double-and-Add 방법과 같은 알고리즘을 사용하여 빠르게 계산될 수 있다. Double-and-Add 방법은 nP에서 n을 이진수로 변환하고, 각 비트를 체크하면서 포인트 더블링과 포인트 덧셈을 하면서 nP 값을 빠르게 계산하는 방법이다.
EC 도메인 파라미터
ECC를 사용하기 위해서는 어떤 타원곡선(Elliptic curve)을 사용할 것인지, 생성자(generator)를 어떤 것으로 할 것인지, 유한체 집합의 범위 등을 결정해야 하는데, 이것이 Elliptic Curve(EC)의 도메인 파라미터이다. EC 도메인 파라미터는 Prime Curve (Fp)의 경우 (p, a, b, G, n, h) 이며, Binary Curve(F2^m)의 경우 (m, f, a, b, G, n, h) 이다.
일반적으로 이들 도메인 파라미터들은 직접 생성해서 사용하지 않고, NIST(National Institute of Standards and Technology)나 SECG(Standards for Efficient Cryptography Group) 등에서 발표한 표준 곡선(Standard Curve, Named Curve, Well Known Elliptic Curve)을 사용하는데, 이들 표준 곡선에는 NIST P-256, NIST P-384, secp256k1, secp384r1, sect283k1 등과 같이 곡선을 명명하는 이름이 붙어 있다. SECG에서 정의된 도메인 파라미터들은 http://secg.org 웹사이트에 자세히 소개되어 있다.
SECG의 명칭들은 secp256k1, secp256r1 등과 같이 되어 있는데, 여기서 256 이란 숫자는 256 bit 크기의 소수 p를 사용한다는 의미이다. 256 숫자 뒤에는 k 또는 r이 나오는데, k는 Koblitz 타원곡선을 가리키고 r은 랜덤하게 선택되어졌다는 의미의 random을 가리킨다. Koblitz 타원곡선은 군(group) 연산을 효율적으로 할 수 있는 특성이 있다고 알려져 있다. 랜덤 커브는 a, b 계수가 랜덤하게 선택되고 검증되었다는 점에 더 안전하다고 알려져 있다. (주: 하지만 랜덤 커브에 백도어가 있을지도 모른다는 의혹이 있는데, 아직 공식적으로 확인된 바는 없다.)
비트코인을 비롯한 많은 암호화폐가 사용하는 secp256k1는 Koblitz 곡선을 사용하고 있으므로 백도어에 대한 의혹은 없다. 미국 NSA는 미국 정부용으로 랜덤 커브를 사용하도록 권장하고 있으며, 기존에는 NIST P-256을 권장하다가 최근에는 보다 강화된 NIST P-384를 권장하고 있다. NIST P-256은 secp256r1 혹은 prime256v1와 동일한 것이다.
EC 도메인 파라미터를 직접 정의하는 것은 시간이 오래 걸릴 수 있고, 또한 잘못하면 보안상 문제가 있을 수 있는 곡선을 정의할 수 있으므로 일반적으로 표준 곡선에 정의된 도메인 파라미터를 사용한다. 잘 정의된 안전한 타원곡선의 경우, 오직 전수조사 공격(Brute Force Attack)에 의해서만 해를 찾을 수 있다.
예를 들어, 비트코인은 SECG에서 정한 표준 곡선인 secp256k1 도메인 파라미터를 사용한다. secp256k1은 256비트 크기의 파라미터들을 가지며, 소수체 Fp 상에 다음과 같은 6개의 도메인 파라미터 (p, a, b, G, n, h)를 사용한다.
p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F a = 0 b = 7 G = (compressed) 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 (uncompressed) 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8 n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C h = 1
도메인 파라미터 (p, a, b, G, n, h)는 다음과 같은 의미를 갖는다.
| 파라미터 | 의미 |
|---|---|
| p | 유한체 집합의 크기를 결정하는 모듈러스 소수 p를 말하며, 포인트 x, y는 항상 {0, 1, ..., p-1} 집합 안에 존재하는 정수가 된다. 즉, 유한체 상의 타원곡선 y2 = x3 + ax + b (mod p) 에서의 p를 가리킨다. |
| a | 타원곡선 y2 = x3 + ax + b 에서의 x의 계수를 가리킨다. |
| b | 타원곡선 y2 = x3 + ax + b 에서의 상수 b를 가리킨다. |
| G | 타원곡선의 생성자(Generator)를 일컫는 것으로, 생성자 G는 자신을 계속 더해서 부분군 집합을 생성하게 된다. G가 생성할 수 있는 군의 요소수를 포인트 G의 위수라고 하고 이것이 아래의 n 값이다. 생성자 G는 포인트이므로 (x, y) 쌍으로 되어 있는데, y는 x로부터 계산될 수 있으므로, x만을 표시하거나 아니면 x, y를 함께 표시할 수 있다. 전자를 압축된(compressed) 포맷이라 하고 이를 표시하기 위해 앞에 0x02 를 붙이고 x값만을 적는다. 후자는 압축되지 않은(uncompressed) 포맷으로 앞에 0x04를 붙이고 뒤에 x, y값을 차례로 적는다. |
| n | 생성자 G가 타원곡선에서 자신을 계속 더해 가면서 생성하는 점들의 갯수를 의미한다. 생성자 G가 부분순환군을 생성할 때, 해당 부분군의 크기를 n으로 표시한다. 즉, G를 n번만큼 더하면 항등원 즉 무한원점(O)이 되며, 이는 n*G = O 로 표시할 수 있다. G가 생성하는 포인트들은 n번만큼마다 순환 반복된다. |
| h | 타원곡선에서 소수 p 모듈러 연산을 통해 생성된 전체 점들의 갯수를 N이라 하고, 생성자 G가 생성하는 부분군의 점들의 갯수를 n 이라 했을 때, h = N / n 으로 정의하고 이를 부분군의 Cofactor 라고 부른다. |
아래는 표준곡선의 하나인 secp256k1 곡선의 도메인 파라미터를 정의한 예제로서, 이와 같은 방식으로 여러 표준곡선들의 파라미터들을 정의할 수 있다.
using System.Numerics;
public static class NamedCurves
{
public static ECCurve Secp256k1
{
get => GetSecp256k1();
}
private static ECCurve GetSecp256k1()
{
var domParams = new ECDomainParams();
// p (little endian)
var pbytes = new byte[]
{
0x2F, 0xFC, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x00
};
domParams.P = new BigInteger(pbytes);
// a, b
domParams.a = 0;
domParams.b = 7;
// G (little endian)
var gxbytes = new byte[]
{
0x98, 0x17, 0xF8, 0x16, 0x5B, 0x81, 0xF2, 0x59,
0xD9, 0x28, 0xCE, 0x2D, 0xDB, 0xFC, 0x9B, 0x02,
0x07, 0x0B, 0x87, 0xCE, 0x95, 0x62, 0xA0, 0x55,
0xAC, 0xBB, 0xDC, 0xF9, 0x7E, 0x66, 0xBE, 0x79,
};
var gybytes = new byte[]
{
0xB8, 0xD4, 0x10, 0xFB, 0x8F, 0xD0, 0x47, 0x9C,
0x19, 0x54, 0x85, 0xA6, 0x48, 0xB4, 0x17, 0xFD,
0xA8, 0x08, 0x11, 0x0E, 0xFC, 0xFB, 0xA4, 0x5D,
0x65, 0xC4, 0xA3, 0x26, 0x77, 0xDA, 0x3A, 0x48,
};
var gx = new BigInteger(gxbytes);
var gy = new BigInteger(gybytes);
domParams.G = new ECPoint(gx, gy);
// n (little endian)
var nbytes = new byte[]
{
0x41, 0x41, 0x36, 0xD0, 0x8C, 0x5E, 0xD2, 0xBF,
0x3B, 0xA0, 0x48, 0xAF, 0xE6, 0xDC, 0xAE, 0xBA,
0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x00
};
domParams.n = new BigInteger(nbytes);
// cofactor h
domParams.h = 1;
return new ECCurve(domParams);
}
}
// ECCurve 클래스
public class ECCurve
{
public ECDomainParams DomainParams { get; }
public ECCurve(ECDomainParams ecParams)
{
DomainParams = ecParams;
}
public bool IsPointOnCurve(ECPoint q)
{
var y2 = BigInteger.ModPow(q.Y, 2, DomainParams.P);
var x3 = BigInteger.ModPow(q.X, 3, DomainParams.P);
var res = (x3 + DomainParams.a * q.X + DomainParams.b) % DomainParams.P;
return y2 == res;
}
}
public struct ECDomainParams
{
public BigInteger P { get; set; }
public BigInteger a { get; set; }
public BigInteger b { get; set; }
public ECPoint G { get; set; }
public BigInteger n { get; set; }
public int h { get; set; }
}
아래는 ECC 추상클래스를 예시한 것으로, 파생클래스에서 DefineDomainParameters() 을 정의하여 EC 파라미터를 지정할 수 있도록 한 것이다.
public abstract class ECC
{
protected RandomNumberGenerator rng;
protected ECParams ecParams;
public ECC()
{
this.rng = RandomNumberGenerator.Create();
this.ecParams = DefineDomainParameters();
}
protected abstract ECParams DefineDomainParameters();
protected BigInteger GetRandom()
{
var nbytes = ecParams.n.ToByteArray();
int nLen = nbytes.Length;
if (nbytes[nLen - 1] == 0x00) nLen--;
BigInteger k = 0;
var dbytes = new byte[nLen + 1];
while (true)
{
rng.GetBytes(dbytes);
// to make BigInteger positive number
dbytes[dbytes.Length - 1] = 0x00;
k = new BigInteger(dbytes);
if (k > 0 && k < ecParams.n)
{
break;
}
}
return k;
}
#region EC operations : ...생략...
public ECPoint ECAdd(ECPoint P, ECPoint Q) { }
public ECPoint ECDouble(ECPoint P) { }
public ECPoint ECMultiply(BigInteger n, ECPoint G) { }
#endregion
}