Blockchain 01

2019-09-22

Digital Signatures

전자서명은 손으로 쓴 서명과 두 가지 점에서 같은 특성을 가지고 있다.

첫번째는 한 사람의 서명은 그 사람만이 할 수 있지만 다른 모든 사람이 그것이 유효함을 식별할 수 있어야 한다.

두번째는 이 서명이 특정한 문서에만 묶여져(tied) 다른 문서의 동의나 승인에 쓰일 수 없어야 한다.

Digital signature scheme

  • (sk, pk) := generateKeys(keysize)

  • sig := sign(sk,message)

  • isValid := verify(pk,message,sig)

isValid는 공개키 pk에 대해 서명이 유효할 때 true, 아니면 false를 반환한다.

앞서 언급한 두가지 특성을 만족히키는지를 확인해보자.

첫번째 특성은 단순히 서명이 유효한지 확인하면 된다.

만약 나의 비밀키 sk로 내가 서명을 하고 후에 누군가가 공개키 pk로 서명의 유효성을 확인하려 한다면 서명은 정확히 인증되어야 한다.

두번째 특성은 서명을 위조하는 것이 계산상 불가능해야 한다는 것이다.

어떤 사람이 한 사람의 공개키를 알고 다른 곳에 쓰여진 그의 서명을 봤을지라도 서명을 위조할 수 없어야 된다.

ECDSA generation & verification

sk d: P 보다 작은은 소수이며 Zn에서 random select 한다.(1≤d≤n=2^256)

pk Q: Q(x , y) = G(x0 , y0)^d, 즉 G를 d번 더한 값이다.

G와 Q를 안다고 해도 계산시간이 너무 크기 때문에 d를 알 수 없다.

이산 로그 문제
거듭제곱 연산 p^n은 O(2log₂n)에 그 값을 찾을 수 있다. 하지만 p^x=Q가 되는 x를 찾을 때, 1≤x≤2^160의 경우 time = 2¹⁶⁰이다. 즉, 이산 로그의 효율적 알고리즘은 존재하지 않지만, 그 반대 방향인 거듭제곱 연산은 간단히 계산할 수 있다. 이를 이산 로그 문제(discrete log problem)이라 한다.

D = (q, a, b, G, n, h)

σ sign(skA, m) -> verify(pkA, m, σ)

Alice의 서명을 Bob이 verify한다.

Alice

Alice는 Zn에서 1 ≤ d ≤ n-1인 d값을 랜덤으로 고르고,

공개키 Q: Q(xQ , yQ) = G^d를 생성한다.

공개키가 유효할려면 다음을 만족해야 한다.

  1. Q != O

  2. xQ, yQ ∈ GF(q)

  3. yQ^2 = xQ^3 + axQ + b

  4. nQ = O

  5. If any check fails -> Q is invalid

Sign(sk,m): 
k <$- Zn 

G^k = (x1, y1)

r <- x1 mod n

s <- k⁻¹(H(m) + d*r) mod n

r <- x1 mod n

σ = (s, r)

Bob

bc0301

Bob은 x2 mod n의 값을 r과 비교하여 서명을 검증한다.

Schnorr Signature

bc0302