공개키 암호 기법에 스칼라 곱셈이 활용되는 이유는 타원곡선에서 스칼라 곱셈 역산이 어렵기 때문이다.
규칙적인 패턴도 보이지 않는다. 이런 계산식을 비대칭성을 띈다고 한다. 순방향 계산은 쉽지만 그 반대 방향 계산이 어려운 문제를 말한다.
ex) 12(47,71) 구하는건 쉬운데, s(47,71) = (194,172) 에서 s 구하는건 어렵다.
비트코인에서는 secp256k1 타원곡선을 사용한다.
타원곡선은 $y^2 = x^3 + ax + b$ 인데 secp256k1 는 a=0, b=7 인 곡선이다.
유한체 위수(order) p 값(소수)은 2**256 - 2**32 - 977 다.
생성점 $G_x$ 값은 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 다.
생성점 $G_y$ 값은 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 다
G(생성점) 의 유한순환군 위수 n 값은 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 다. 이 값은
$2^256$ 과 비슷한 값인데 위의 p 값이 n 값보다는 크다.
cf) 매끄러운 설명을 위해서는 유한순환군에 대한 추가 설명이 필요할듯
$eG = P$ 에서 e 는 비밀키, G 는 생성점, P 는 공개키다.
e 와 G 를 알고 있으면 공개키 P 는 쉽게 구할 수 있다. 하지만 G 와 P 를 안다고 하더라도 e 를 구하는 알고리즘은 없다.
서명 생성
비밀키를 알고있는 쪽에서 서명을 생성한다.
먼저 임의의 256 비트 숫자 k 값을 선정한다. 서명마다 k 값은 반드시 달라야하고 재사용은 안된다. k 값이 공개되면 비밀키는 드러난다.
cf) p119 에 이유설명있음
$kG = R$ 즉 생성점 G에 k 값을 스칼라곱해서 나온 R 값을 구한다. R 값은 좌표이며 R(r, y) x좌표를 r이라 하고 r만 구하면 된다(r을 통해서 y값을 구할 수 있으므로). 이걸 왜하냐면 서명을 인증하기 위한 목표물로 생각하면 된다.
이어서 다음의 방정식이 있다. 이 방정식을 활용해서 검증에 사용할건데 왜 저 방정식을 사용하는가는 너무 깊어지고 책에서도 설명이 없다. 그냥 받아들이자.
$uG + vP = kG = R$
서명자는 k를 임의의 값으로, u,v 는 0이 아닌 값으로 선정한다. G와 P 는 알려진 값이다.
비밀키 e 를 알아야만 정확한 u, v 값을 제공할 수 있기 때문에 u, v 를 제공하는 사람이 비밀키 e 를 알고 있다고 가정하는 것이 타당하다.
서명과 검증을 하기 위해서 서명해시(Signature Hsh) 를 위 방정식에 포함시킨다(z 로 표기).
u = z/s 그리고 v = r/s 다.
v 계산에 r 이 포함되어 있기 때문에 검증하고자 하는 값을 새긴것과 같다.
$uG + vP = kG = R$
=> $uG + veG = kG$
=> $u + ve = k$
=> $z/s + re/s = k$
=> $(z + re)/s = k$
=> $s = (z + re)/k$ 이 s 가 서명 알고리즘이다.
서명에서 검증자에게 전달하는 정보는 r과 s다.
서명 검증
검증하고자 하는 서명은 한쌍 (r, s) 으로 이뤄진 정보다.
$uG + vP$ 를 계산해 새로운 R 을 구한다.
u = z/s, v = r/s 인데 보내온 메세지의 해시값으로 z 도 같이 전달한다. 그러므로 검증자는 z,r,s 모두 알고 있다.
$uG + vP$
=> $(z/s)G + (r/s)P$
=> $(z/s)G + (re/s)G$
=> $((z +re)/s)G$
여기 s 에 서명 알고리즘 $s = (z + re)/k$ 을 대입한다.
그러면 $kG$ 가 되고 새로운 R 을 얻을 수 있게된다.
새로운 R(r, y) 의 x좌표 r과 서명으로 주어진 r 값이 같으면 서명은 유효하다고 판단한다.
여기 에 설명했듯이, 스칼라 곱셈이 공개키 암호 기법의 핵심이다.
공개키 암호 기법에 스칼라 곱셈이 활용되는 이유는 타원곡선에서 스칼라 곱셈 역산이 어렵기 때문이다. 규칙적인 패턴도 보이지 않는다. 이런 계산식을 비대칭성을 띈다고 한다. 순방향 계산은 쉽지만 그 반대 방향 계산이 어려운 문제를 말한다. ex) 12(47,71) 구하는건 쉬운데, s(47,71) = (194,172) 에서 s 구하는건 어렵다.
비트코인에서는 secp256k1 타원곡선을 사용한다. 타원곡선은 $y^2 = x^3 + ax + b$ 인데 secp256k1 는 a=0, b=7 인 곡선이다.
유한체 위수(order) p 값(소수)은
2**256 - 2**32 - 977다. 생성점 $G_x$ 값은0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798다. 생성점 $G_y$ 값은0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8다 G(생성점) 의 유한순환군 위수 n 값은0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141다. 이 값은 $2^256$ 과 비슷한 값인데 위의 p 값이 n 값보다는 크다.cf) 매끄러운 설명을 위해서는 유한순환군에 대한 추가 설명이 필요할듯
$eG = P$ 에서 e 는 비밀키, G 는 생성점, P 는 공개키다. e 와 G 를 알고 있으면 공개키 P 는 쉽게 구할 수 있다. 하지만 G 와 P 를 안다고 하더라도 e 를 구하는 알고리즘은 없다.
서명 생성
비밀키를 알고있는 쪽에서 서명을 생성한다. 먼저 임의의 256 비트 숫자 k 값을 선정한다. 서명마다 k 값은 반드시 달라야하고 재사용은 안된다. k 값이 공개되면 비밀키는 드러난다. cf) p119 에 이유설명있음
$kG = R$ 즉 생성점 G에 k 값을 스칼라곱해서 나온 R 값을 구한다. R 값은 좌표이며 R(r, y) x좌표를 r이라 하고 r만 구하면 된다(r을 통해서 y값을 구할 수 있으므로). 이걸 왜하냐면 서명을 인증하기 위한 목표물로 생각하면 된다.
이어서 다음의 방정식이 있다. 이 방정식을 활용해서 검증에 사용할건데 왜 저 방정식을 사용하는가는 너무 깊어지고 책에서도 설명이 없다. 그냥 받아들이자.
$uG + vP = kG = R$
서명자는 k를 임의의 값으로, u,v 는 0이 아닌 값으로 선정한다. G와 P 는 알려진 값이다. 비밀키 e 를 알아야만 정확한 u, v 값을 제공할 수 있기 때문에 u, v 를 제공하는 사람이 비밀키 e 를 알고 있다고 가정하는 것이 타당하다.
서명과 검증을 하기 위해서 서명해시(Signature Hsh) 를 위 방정식에 포함시킨다(z 로 표기).
u = z/s 그리고 v = r/s 다. v 계산에 r 이 포함되어 있기 때문에 검증하고자 하는 값을 새긴것과 같다.
$uG + vP = kG = R$ => $uG + veG = kG$ => $u + ve = k$ => $z/s + re/s = k$ => $(z + re)/s = k$ => $s = (z + re)/k$ 이 s 가 서명 알고리즘이다. 서명에서 검증자에게 전달하는 정보는 r과 s다.
서명 검증
검증하고자 하는 서명은 한쌍 (r, s) 으로 이뤄진 정보다. $uG + vP$ 를 계산해 새로운 R 을 구한다.
u = z/s, v = r/s 인데 보내온 메세지의 해시값으로 z 도 같이 전달한다. 그러므로 검증자는 z,r,s 모두 알고 있다. $uG + vP$ => $(z/s)G + (r/s)P$ => $(z/s)G + (re/s)G$ => $((z +re)/s)G$
여기 s 에 서명 알고리즘 $s = (z + re)/k$ 을 대입한다. 그러면 $kG$ 가 되고 새로운 R 을 얻을 수 있게된다. 새로운 R(r, y) 의 x좌표 r과 서명으로 주어진 r 값이 같으면 서명은 유효하다고 판단한다.