2 Party ECDSA의 이해와 구현 - 1
2 Party ECDSA은 타원곡선 위에서의 디지털 서명을 private key의 공유 없이 두 entity의 참여로 수행할 수 있는 방식이다.
private key의 share를 분산 보관하면서 디지털 서명이 필요할 때 key의 복구 없이도 유효한 서명을 만들어낼 수 있는 방식이다.
이 연재에서는 2 Party ECDSA의 개념을 살펴보고 실제 코드로 구현을 하면서 이해를 하고자 한다. 이번 글에서는 그에 앞서 DSA 개념과 ECDSA(Elliptic Curve Digital Signature Algorithm)의 작동 방식을 살펴본다.
디지털 서명 알고리즘
서명: 특정 행동을 내가 했다고 남이 검증할 수 있게 하는 장치
보통 비대칭 암호에서는 public key로 encryption을 하고 private key로 decryption을 하게 돼있다.
단순히 생각해보면, 어떤 메시지를 특정 player A가 보냈다고 검증하고 싶으면 암호화 된 스트링을 같이 보내서 "이걸 복호화하면 원래 메시지가 나오니 이건 내가 한게 맞아"라고 하면 될것 같지만, 암호화는 public key로 할수 있기때문에 누구나 만들어낼 수 있고, 복호화는 A의 private key가 있어야하므로 불가능하다.
디지털 서명(NIST 1991)은 public key를 이용하여 private key를 통해 만들어진 signature를 검증하게 하는 방법을 제공함으로써 player A의 private key 없이도 player A의 행위를 검증할 수 있게 한다.
Private key를 이용해서 서명하고 싶은 메시지에 대해 이러저러한 연산을 한 후 두개의 숫자쌍 [r, s] 를 만들고 이를 디지털 서명으로 한다. 그리고 나서 public key를 이용해서 이 [r, s]가 유효한지 검증하여 메시지를 내가 작성했다고 검증할 수 있게 한다.
이 DSA(Diginal Signing Algorithm)를 타원곡선 위에서 하는 ECDSA는 블록체인상에서 transaction을 서명하는 기본 도구로 쓰인다.
타원곡선 위에서의 서명
서명 만드는 과정
\(d\) = private key (\(Z_p\)위의 숫자)
\(k\) = 임의의 nonce (\(Z_p\)위의 숫자). 메시지를 서명할 때 마다 랜덤하게 생성하는 것이 좋다.
타원곡선은 정해져있다. 예) secp256k1. 그 위의 generator point는 G라고 하자.
다음 과정에서 나오는 generator point G에 대한 상수배 연산은 타원 곡선 위에서의 그룹연산이다. 타원 곡선 위에서의 연산의 정의를 참고하자.
- \(dG = Q_a\)를 계산한다. \(Q_a\)는 타원곡선 위의 점이다. \(Q_a\)를 public key라 부르고 공개한다.
- \(k G = P\) 를 계산한다. \(P\)는 타원곡선 위의 점
- \(P\)의 x좌표를 \(r\)이라고 하자.
- \(r = P.x\) — (1)
- \(z = H(m)\) → 메시지 \(m\)을 적당히 해시하고 조작하여 \(Z_p\) 안에 떨어지게 만든다. 통상 SHA1을 쓴다음에 bit 몇개를 조작하여 사용한다.
- \(s = k^{-1}(z + rd) \mod p\) 을 계산한다. — (2)
- 여기서 \(k^{-1}\)는 \(Z_p\) 에서 \(k\)와 곱해서 1이 나오는 수 (곱셈의 역원)
- 이렇게 만들어진 \([r,s]\)를 메시지 \(m\)에 대한 서명이라고 한다.
서명 검증 과정
검증을 원하는 player가 [r, s] 를 받았으면 다음과 같이 검증을 해볼 수 있다.
받은 [r, s]로 \(P' = s^{-1} z G + s^{-1} r Q_a\) 를 계산한다. \(G, z, Q_a\)는 이미 공개된 값이다. 각각, 타원곡선의 generator point, 메시지의 해시값, public key이다.
\(P'\)는 타원곡선위의 점인데, \(P'\)의 x좌표가 \(r\)과 같다면, \(Q_a\)가 public key인 private key \(d\)로 사인한 서명이다. 아니면 이 서명은 유효한 것이 아니다.
왜 성립할까?
\(s\)의 계산식에서 유도를 해나가면,
\[\begin{align*} s &= k^{-1} (z+rd) \\ k &= s^{-1} (z+rd) \\ kG &= s^{-1} (z+rd) G \\ kG &= s^{-1} zG + s^{-1} rdG \\ \tag{1} kG &= s^{-1} zG + s^{-1} rQ_a \end{align*}\]
이 나온다. (1)식의 우변은 \(P'\)을 계산한 식과 방법이 같다. 그리고 \(kG\)의 x좌표를 \(r\)이라고 했으니, \(P'\)의 x좌표가 r과 같다면 유효한 r과 s임을 알 수 있다.
예제 코드
많이 사용되는 암호화 라이브러리인 bouncy castle에 ECDSA 구현 부분이 있는데 이를 살펴보면 위에서 설명한 방법을 어떻게 구현했는지 알 수 있다.
public BigInteger[] generateSignature(byte[] message) {
ECDomainParameters ec = key.getParameters();
BigInteger n = ec.getN();
BigInteger e = calculateE(n, message); // z, 즉 메시지 해시
BigInteger d = ((ECPrivateKeyParameters)key).getD(); // private key
if (kCalculator.isDeterministic()) {
kCalculator.init(n, d, message); // 메시지마다 달라지는 nonce k
} else {
kCalculator.init(n, random);
}
BigInteger r, s;
ECMultiplier basePointMultiplier = createBasePointMultiplier();
do // generate s
{
BigInteger k;
do // generate r
{
k = kCalculator.nextK();
ECPoint p = basePointMultiplier.multiply(ec.getG(), k).normalize(); // P = kG를 계산한다.
r = p.getAffineXCoord().toBigInteger().mod(n); // P의 x좌표를 r로 세팅한다.
}
while (r.equals(ZERO));
s = BigIntegers.modOddInverse(n, k).multiply(e.add(d.multiply(r))).mod(n); // s = k^-1(z+rd)를 계산한다.
}
while (s.equals(ZERO));
return new BigInteger[]{ r, s };
}