2 Party ECDSA 이해와 구현 - 2

Jay Han

2023년 2월 19일 • 7 min read

2Party ECDSA의 핵심 아이디어는 private key \(d\)를 구성하는 두 요소 \(d_1\), \(d_2\)를 서로 공유하지 않고도 private key \(d\)를 이용한 \(r\)과 \(s\)를 계산하자는 것이다.

이 글에서는 Lindell 2017 의 아이디어를 기반으로 설명한다.

사전지식 - 동형암호

동형암호(Homomorphic Encryption)는 암호화된 상태에서 원문을 알지 못해도 원문에 대한 연산을 수행한 결과(물론 암호화된 상태로)를 얻어낼 수 있는 성질을 가진 암호체계이다.

다음과 같은 성질이 성립하면 동형암호라고 한다.

\(E(a) +_e E(b) = E(a+b)\), 따라서 \(D(E(a) +_e E(b)) = a+b\)
\(x \times_e E(m) = E(xm)\), 여기서 \(x\)는 상수

여기서 \(+_e\)와 \(\times_e\)는 단순 덧, 곱셈은 아니고 동형암호 연산을 위하여 따로 정의된 연산이다.

Paillier는 이러한 동형암호 시스템 중 하나이고 2P ECDSA에 사용된다. 이 암호체계는 public key로 암호화 하고 private key로 복호화하는 비대칭 암호 체계이다.

동형암호의 특징은 2P ECDSA의 전개 과정에서 유용하게 쓰인다. 암호화된 상태에서 연산을 해도 평문에 대한 연산 결과(후 암호화한)와 같은 결과를 얻기 때문에 두 플레이어가 서로의 정보를 평문으로 노출하지 않고 연산을 수행할 수 있게 해준다.

2Party ECDSA 의 과정은 키 생성 과정과 서명 과정으로 크게 나뉜다.

사전 설정

타원 곡선과 그에 대한 generator point \(G\), 서명할 메시지 \(m\)은 공통지식이다. 그리고 \(m\)을 실제 서명에 사용할 수 있는 형태로 hash 및 비트연산을 한 값을 \(z \in Z_p\) 라 한다.

서명에 필요한 private key \(d\)는 Player들이 임의로 생성한 \(d_1\), \(d_2\)의 곱( \(d = d_1 \cdot d_2\))이다.

nonce \(k\)역시 player들이 임의로 생성한 \(k_1\), \(k_2\)의 곱(\(k = k_1 \cdot k_2\))이다.

각 Player들은 서로 정보를 공유하지 않고 \(d_1\)과 \(d_2\), \(k_1\)과 \(k_2\)를 생성하여 가지고 있는다.

키 생성 과정

P1이 \(d_1 G = Q_1\)을 계산하고 P2가 \(d_2 G = Q_2\)를 계산하여 서로 공유한다.
P1은 \(d_1 Q_2 = d_1 d_2 G = dG = Q\)를 계산할 수 있고, 마찬가지로 P2도 \(d_2 Q_1 = d_1 d_2 G = dG = Q\)를 계산할 수 있다.
위에서 계산한 \(Q\)는 private key \(k\)에 대응하는 public key다.

서명 과정 - \(r\)계산 파트

P1이 \(k_1 G = R_1\) , P2가 \(k_2 G = R_2\)를 계산하여 서로 공유한다.
P1은 \(k_1 R_2 = k_1 k_2 G = kG\)를 계산할 수 있고, 마찬가지로 P2도 \(k_2 R_1 = k_2 k_1 G = kG\)를 계산할 수 있다.
\(kG\)의 \(x\)좌표를 \(r\)이라고 하자. 여기까지는 일반적인 ECDSA와 비슷하다.

P1, P2는 \(k\)를 모름에도 \(r\)을 계산했다. 이제 \(s\)를 계산할때는 \(d\)를 알아야하는데 \(d\)를 모름에도 계산이 가능할까? 이때부터 동형암호를 활용하기 시작한다.

서명 과정 - \(s\) 계산 파트

P1은 Paillier 암호화를 위한 public key \(pk_{p1}\)를 생성하여 공개한다.
P1은 d1을 \(pk_{p1}\)으로 암호화한 \(E_1 (d_1 )\)을 P2에 공유한다. 이를 ckey라고 하자.
P2는 \(k_2^{-1}z\)를 계산한 후 이를 \(pk_{p1}\)으로 암호화하여 \(E_1 ( k_2^ {-1} z)\)를 계산함.
P2는 \(k_2^{-1} \cdot r \cdot d_2\)를 계산한 후, 이를 ckey와 Paillier 곱(\(\times_e\))으로 연산하여
\((k_2 ^{-1}\cdot r \cdot d_2 )\times_e E_1(d_1) = E_1(k_2 ^{-1}\cdot r \cdot d_2 \cdot d_1) = E_1(k_2^{-1}rd)\) 을 얻는다.
여기서 동형암호의 성질 중 하나인 암호문에 상수곱을 했을때 원문에 상수곱을 한것을 암호화한 결과를 얻는다는 성질이 이용된다. 즉 P2는 \(d_1\)을 모름에도 \(rd\)부분을 계산할 수 있다. 물론 암호화된 값이라 뭔지 알수는 없다.
P2는 위 3번의 계산결과와 4번의 계산결과를 Paillier 덧셈(\(+_e\))하여,
\(E_1(k_2^{-1}rd) +_e E_1 (k_2^{-1} z) = E_1(k_2^{-1} (z+rd))\) 를 얻는다.
여기까지의 결과인 \(E_1(k_2^{-1} (z+rd))\)은 \(k_1\)만 있으면 \(k^{-1}(z+rd)\)로 만들어낼 수 있게된다. Lindell 2017에서는 이 결과값을 almost signature라고 부른다. P2는 5번의 결과를 P1에게 공유한다.
P1은 자신의 Paillier private key를 이용하여 복호를 수행하면
\(D_1 (E_1(k_2^{-1}(z+rd))) = k_2^{-1} (z+rd)\)을 얻을 수 있고, 여기에 자신이 갖고 있는 \(k_1\)의 역원을 곱하여
\(k_1^{-1} k_2^{-1}(z+rd) = k^{-1}(z+rd) = s\) 을 계산한다.
[r,s]를 생성했고 이는 메시지 \(m\)에 대한 디지털 서명이다.

P1은 P2의 도움으로 실제 private key \(d\), nonce \(k\)를 알지 못함에도 서명 [r,s]를 계산했다.

위 과정 중 핵심아이디어를 코틀린 코드로 써보면 다음과 같다.

키생성 과정

val Q1 = basePointMultiplier.multiply(ecp.g, d1)
val Q2 = basePointMultiplier.multiply(ecp.g, d2)

val q = Q1.multiply(d2)

서명 과정 - r계산

// basePointMultiplier는 타원곡선 위 상수곱을 위한 객체
val k1G = basePointMultiplier.multiply(ecp.g, k1)
val k2G = basePointMultiplier.multiply(ecp.g, k2)

val p = k2G.multiply(k1).normalize() // R2 = k2G, p = k1(k2G) = kG
val r = p.affineXCoord.toBigInteger().mod(ecp.n)

서명 과정 - s계산

val ctx = ppkey.publicKey.createUnsignedContext() // ppkey = Paillier private key
val ckey = ctx.encrypt(d1) // ckey 생성

val k2Inv = BigIntegers.modOddInverse(ecp.n, k2)
val k2Inv_z = (k2Inv*e).mod(ecp.n)
val k2Inv_z_enc = ckey.context.encrypt(k2Inv_z) // Enc(k2^-1 * z)

val k2Inv_r_d2 = (k2Inv*r*d2).mod(ecp.n)
val k2Inv_r_d2_d1_enc = ckey.multiply(k2Inv_r_d2) // Enc(d1) * (k2^-1 * r * d2) = Enc(d1 * k2^-1 * r * d2) = Enc(k2^-1 * r * d)

val almostSig = k2Inv_z_enc.add(k2Inv_r_d2_d1_enc) // almostSig generated

val k1Inv = BigIntegers.modOddInverse(ecp.n, k1)
val s = (almostSig.decrypt(ppkey).decodeBigInteger().multiply(k1Inv)).mod(ecp.n)

소스코드

이 글에서 설명한 2Party ECDSA 과정을 구현해본 코드는 아래 Github 저장소에 있다. 해당 코드의 main() 함수는 같은 메시지에 대해 2Party ECDSA와 일반 ECDSA을 각각 수행하여 비교한다.

데모 목적으로 만든것이기 때문에 nonce \(k\)는 주어진 값을 사용하도록 하였다.

Paillier 암호화를 위해 Javallier 라이브러리를 활용하였다. 기존 방식과의 비교를 위해 bouncycastle 라이브러리를 활용하였다.