1️⃣

슈노르 서명

ECDSA의 한계

•
ECDSA는 서명의 가변성 문제가 있다.
◦
같은 메시지에 대한 서명값은 항상 두 개가 존재한다.
◦
개인키를 잘 모른다 하더라도 누구든 유효한 서명값을 만들어낼 수 있다.
•
슈노르 서명의 가장 큰 특징은 여러개의 서명을 효율적으로 검증할 수 있다는 점이다.
◦
만약 10-of-10 다중서명이 있다고 가정해 보자.
▪
ECDSA는 모든 서명을 각각 검증하여야 한다.
▪
슈노르 서명은 서명값을 모두 더하는 방식으로 한 번에 검증할 수 있다.
•
사용된 해시함수에 대한 문제
◦
ECDSA는 메시지를 그대로 해시화하여 서명에 사용한다.
◦
따라서 같은 메시지에 대한 재사용의 우려가 있다.
◦
슈노르 서명은 해시값 추출 시 임시 값을 사용하여 메시지가 같아도 다른 해시값이 추출된다.

슈노르 서명 메커니즘

•
키 생성
◦
비트코인에서는 슈노르 서명에서도 타원곡선 secp255k1을 사용한다.
◦
x : 개인키
◦
y : 공개키 (이산 로그 문제에 따라 다음과 같이 정의된다.)
y=gxy=g^x
◦
g : 타원곡선의 기준점
•
다만 서명을 만드는 방식이 조금 다르다.
◦
범례
▪
H : 해시 함수
▪
k : 임시 개인키
▪
r : 임시 공개키
▪
M : 메시지
◦
서명하기
e=H(r∣∣M)s=k−xee=H(r||M) \\ s=k-xe
◦
검증하기
gs=ry−H(r∣∣m)g^s=ry^{-H(r||m)}
◦
증명하기
gs=gk−xe=gk(gx)−egs=ry−egs=ry−H(r∣∣m)g^s=g^{k-xe}=g^k(g^x)^{-e}\\ g^s=ry^{-e}\\ g^s=ry^{-H(r||m)}
◦
우리가 익숙한 타원 방정식으로 변환하면 다음과 같다.
sG=R+P∙H(R∣∣m)sG=R+P\bullet H(R||m)

왜 비트코인에서 슈노르 서명을 채택했을까?

•
BIP0340을 통해 비트코인에 슈노르 서명이 채택되었다.
•
검증 가능한 보안성 (Provable security)
◦
ECDSA는 개인키를 모르더라도 다른 서명이 가능하다. (트랜잭션의 가변성)
◦
하지만 슈노르 서명은 이를 방지할 수 있다.
◦
슈노르 서명에서는 메시지를 그대로 넣지 않고 임의의 값을 포함하여 해시를 수행한다.
◦
메시지의 내용을 알 때 발생할 수 있는 공격에서 더 높은 보안성을 제공한다.
•
비가변성 (Non-malleability)
◦
ECDSA는 같은 메시지에 2개의 서명이 가능하다.
•
선형성 (Linearity)
◦
여러개의 서명 값을 동시에 검증할 수 있다.

비트코인의 슈노르 서명

•
서명하기
◦
입력
▪
개인키 : d
▪
메시지 : m
▪
임시 개인키 : k
◦
도출
▪
공개키 추출 : P = dG
▪
임시 공개키 추출 : R = kG
▪
메시지의 해시 추출 : e = H(R||P||m)
▪
서명값 추출 : s = k+ed
•
검증하기
◦
입력
▪
서명값 : s
▪
임시 공개키 : R
▪
메시지 : m
▪
공개키 : pk
◦
도출
▪
메시지의 해시 추출 : e = H(R||P||m)
◦
검증
▪
만약 sG - eP = R 이면 서명 검증 성공
•
여러개의 서명을 동시에 검증하기
◦
입력
▪
n 개의 서명값 :
s1..ns_{1..n}
▪
n 개의 임시 공개키 :
R1..nR_{1..n}
▪
n 개의 메시지 :
m1..nm_{1..n}
▪
n 개의 공개키 :
pk1..npk_{1..n}
◦
도출
▪
n-1개의 랜덤수 생성 :
a2..na_{2..n}
▪
n 개의 메시지 해시 추출 :
e1..nei=H(Ri∣∣Pi∣∣mi)e_{1..n} \\ e_{i} = H(R_i||P_i||m_i)
▪
이해를 위한 임시변수
as=s1+a2s2+...+ausuaR=R1+a2R2+...+auRuaeP=e1P1+a2e2P2+...+aueuPuas = s_1+a_2s_2+...+a_us_u \\ aR = R_1+a_2R_2+...+a_uR_u \\ aeP = e_1P_1+a_2e_2P_2+...+a_ue_uP_u
◦
검증
asG=aR+aePasG = aR+aeP