ECDSA 개요

ECDSA(Elliptic Curve Digital Signature Algorithm)는 DSA의 한 변형으로 타원곡선(elliptic curve) 기술을 사용하여 디지탈 서명을 수행하는 알고리즘이다. ECDSA는 앞 장에서 설명한 ECC 기술에 기반하여 DSA 서명을 수행하는 것이라 할 수 있다. ECC에서 설명한 바와 같이, ECDSA는 타원곡선(elliptic curve)에 위치한 점의 곱셈 연산(스칼라 곱셈)이 일방향 함수의 기능을 한다는 점에 기반한 것이다. 타원곡선에서 시작점(base point)에서 N번 곱셈 연산을 수행했을 때 종료점을 쉽게 구할 수 있지만, 시작점과 종료점만을 아는 상태에서 시작점에서 얼마만큼의 곱셈 연산을 수행해야 종료점이 되는지 알기 어렵다는 점에서 타원곡선의 곱셈 연산은 일방향 함수의 기능을 갖는다.

RSA와 DSA의 Key는 상대적으로 크지만, ECDSA는 Key가 매우 작다는 장점이 있다. 오늘날 모바일 기기들과 같이 작은 연산과 저장 능력을 가진 디바이스에서는 RSA/DSA 보다 ECDSA가 훨씬 더 효율적이다. 예를 들어, 키 사이즈의 경우, 3072bit의 RSA 키는 ECDSA에서 256bit 키로 대체되어 동일한 보안 레벨을 유지할 수 있다.

ECDSA 키 생성

ECDSA의 키 생성은 기본적으로 ECC의 키 생성과 동일하다. ECDSA의 키는 개인키(private key)와 공개키(public key)를 쌍으로 생성하는데, ECDSA의 개인키(d)는 (도메인 파라미터 n 을 사용하여) 1 ~ n-1 까지의 정수 중 하나를 랜덤하게 선택하면 된다. ECDSA의 공개키는 개인키를 생성자(G) 파라미터에 곱한 Q = d*G 를 통해 구하게 된다.

ECC/ECDSA에서 생성자나 공개키는 점(point)을 가리키는데, 점은 (x, y) 쌍으로 되어 있다. 점의 값을 표현하는 방법은 2가지 인데, 압축된(compressed) 포맷을 사용할 수도 있고, 압축되지 않는(uncompressed) 포맷을 사용할 수도 있다. 압축 포맷은 앞에 0x02를 붙이고 x값만을 갖게 된다. 이때, y값은 타원곡선 식에 x값을 넣어 구할 수 있다. 압축되지 않은 포맷은 앞에 0x04를 붙이고, 이어 x값과 y값을 붙이게 된다.

ECDSA 서명과 검증

ECDSA 서명은 기본적으로 DSA 서명과 동일한 알고리즘을 사용하는데, 단지 이산 거듭제곱 대신 타원곡선의 스칼라곱셈을 사용한다.

ECDSA 서명

DSA와 마찬가지로 ECDSA 서명은 메시지를 해시하여 메시지 다이제스트를 만든 후 개인키를 사용하여 서명 요소 (r, s)를 만들어 내는 과정이다. ECDSA 개인키를 d, 서명하고자 하는 메시지를 m, 메시지를 해싱하는 해시함수를 H 라고 했을 때, ECDSA 서명은 다음과 같은 과정을 통해 서명 (r, s)를 산출한다.

1. {1, ..., n-1} 사이의 랜덤한 수 k를 선택한다.
2. k*G 를 계산하여 결과값 (x1, y1)을 구한다.
3. r = x1 mod n 식을 사용하여 r을 계산한다. 매우 드물지만 r=0 이면, 다른 k를 선택해서 반복한다.
4. s = (k^-1 (H(m) + dr)) mod n 식을 사용하여 s를 계산한다. 만약 s=0 이면, 다른 k를 선택하여 처음부터 다시 계산한다. 여기서 해시함수는 H(m)을 통해 도메인 파라미터 n과 같은 비트길이를 리턴하는 함수로 가정하는데, 만약 해시함수 H()가 더 긴 비트길이를 리턴한다면, H(m)의 해시값으로부터 좌측에서 n의 비트길이만큼만을 취한다.
5. (r, s) 쌍이 디지탈 서명이다.

DSA에서와 마찬가지로, 개인키(d)와 함께 랜덤 수 k는 외부에 노출되지 말아야 한다. 만약 k가 알려진다면, 역으로 계산해서 개인키가 노출될 가능성이 있다. 또한, 랜덤 k는 서명할 때마다 매번 다른 값을 사용하여, 동일한 메시지라도 매번 다른 디지탈 서명을 만들도록 해야 한다.

ECDSA 검증

ECDSA 검증은 메시지(m)와 서명(r, s)를 받아들여 공개키(Q)로 메시지에 대한 서명이 맞는지를 검사하는 과정이다. 메시지를 해싱하는 해시함수를 H 라고 했을 때, ECDSA 서명은 다음과 같은 과정을 통해 검증한다.

1. 상대의 공개키(Q)가 타당한지 체크한다. Q는 무한원점(O)이 아니어야 하고, 타원곡선상에 있는 점이어야 하며, n*Q = O 이어야 한다.
2. r, s의 범위가 0 < r < n, 0 < s < n 인지 체크한다.
3. w = s^-1 mod n 을 계산한다.
4. u1 = H(m)*w mod n 을 계산한다. 여기서 해시함수는 H(m)을 통해 도메인 파라미터 n과 같은 비트길이를 리턴하는 함수로 가정하는데, 만약 해시함수 H()가 더 긴 비트길이를 리턴한다면, H(m)의 해시값으로부터 좌측에서 n의 비트길이만큼만을 취한다.
5. u2 = r*w mod n 을 계산한다.
6. (x1, y1) = (u1*G + u2*Q) mod n 을 계산한다. 만약 (x1, y1)가 무한원점(O)이면 잘못된 서명이다.
7. v = x1 % n 을 계산한다.
8. v가 r과 동일하면 맞는 서명이다.

ECDSA의 서명과 검증 과정은 타원곡선(EC)를 사용하는 것을 제외하고는 기본적으로 DSA와 동일한 메카니즘을 사용한다.

아래 클래스는 ECDSA에서 해싱된 메시지에 대해 서명을 생성하는 메서드(SignHash)와 그 서명을 검증하는 메서드(VerifyHash)를 예시한 것이다.

public class ECDSA : ECC
{
    private ECKey key;
    private BigInteger MAX_S = 
        BigInteger.Parse("7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0", 
        NumberStyles.AllowHexSpecifier);

    public ECDSA(ECKey key)
    {
        this.key = key;
    }

    // 서명
    public (BigInteger r, BigInteger s) SignHash(byte[] hash)
    {
        var n = ecParams.n;
        BigInteger r = 0;
        BigInteger s = 0;

        BigInteger hm = new BigInteger(hash, true, true);

        while (s == 0)
        {
            // choose random k
            var k = GetRandom();
            ECPoint kG = ECMultiply(k, ecParams.G);

            BigInteger x1 = kG.X;

            // r
            r = x1 % n;
            if (r == 0) continue;

            // s
            var k_1 = ExtendedGCD.ModInverse(k, n);
            s = (k_1 * (hm + this.key.D * r)) % n;

            // BIP 62 : choose Low S value only
            if (s > MAX_S)
            {
                s = 0;  // try another k
            }
        }

        return (r, s);
    }
    
    // 서명 검증
    public bool VerifyHash(byte[] hash, byte[] r, byte[] s)
    {
        var n = this.ecParams.n;
        var q = this.key.Q;
        BigInteger R = new BigInteger(r, true, true);
        BigInteger S = new BigInteger(s, true, true); ;

        // validate public key
        var curve = new ECCurve(ecParams);
        if (q.IsInfinity ||
            !curve.IsPointOnCurve(q) ||
            !ECMultiply(ecParams.n, q).IsInfinity)
        {
            return false;
        }

        // check (r, s)
        if (R <= 0 || R > n || S <= 0 || S > n) return false;

        // hash
        BigInteger hm = new BigInteger(hash, true, true);

        // verify
        var w = ExtendedGCD.ModInverse(S, n);
        var u1 = (hm * w) % n;
        var u2 = (R * w) % n;
        var t1 = ECMultiply(u1, ecParams.G);
        var t2 = ECMultiply(u2, q);
        var t3 = ECAdd(t1, t2);
        if (t3.IsInfinity)
        {
            return false;
        }
        var v = t3.X % n;

        return v == R;
    }		

    //... 생략 ...
}