签名是用于消息的认证,保证该条消息不被伪造。本文主要讨论RSA签名、DSA、ECDSA 和 Schnorr 签名算法。
RSA签名
安全性建立在大数分解问题
公钥:E、N
私钥:D、N
签名:签名 = 消息^D mod N
验证:消息' = 签名^E mod N ,如果消息'==消息则验证成功
DSA
由NIST(美国国家标准技术研究所)1991年制定的数字签名技术规范,是Schnorr算法的变体。
安全性建立在离散对数问题
密钥生成(1024bits):
- 生成素数 p,
- 找到 p-1 的一个素数 q,且
- 找到 ord(a)=q 的元素 a,a 生成了拥有 q 个元素的子群
- 生成随机数,0 < d < q
- b =
mod p
- 则密钥对为:
= (p,q,a,b),
= (d)
签名生成:
- 随机生成一个整数最为随机的临时密钥
,且满足 0 <
< q。
- 计算 r = (
mod p) mod q
- 计算 s = (SHA(x)+d * r)
mod q
签名的验证:
- 计算辅助值 w =
mod q
- 计算辅助值
= w * SHA(x) mod q
- 计算辅助值
= w * r mod q
- v = (
mod p) mod q
- v' = r mod q,如果 v == v' 则签名正确
Golang SDK dsa 签名过程代码:
for attempts = 10; attempts > 0; attempts-- {
k := new(big.Int)
buf := make([]byte, n)
for {
_, err = io.ReadFull(rand, buf)
if err != nil {
return
}
//生成随机数密钥
k.SetBytes(buf)
// priv.Q must be >= 128 because the test above
// requires it to be > 0 and that
// ceil(log_2(Q)) mod 8 = 0
// Thus this loop will quickly terminate.
if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
break
}
}
//求密钥的逆
kInv := fermatInverse(k, priv.Q)
//计算 r
r = new(big.Int).Exp(priv.G, k, priv.P)
r.Mod(r, priv.Q)
if r.Sign() == 0 {
continue
}
z := k.SetBytes(hash)
//计算s
s = new(big.Int).Mul(priv.X, r)
s.Add(s, z)
s.Mod(s, priv.Q)
s.Mul(s, kInv)
s.Mod(s, priv.Q)
if s.Sign() != 0 {
break
}
}
ECDSA
安全性建立在基于椭圆曲线的离散对数问题
密钥的生成:
-
使用曲线 E
- 模数为 p
- 系数为 a 和 b
- 生成元为 G,G 生成的循环群的阶(即元素的个数)为 n
选择一个随机数 d,0 < d < n
计算 K = dG
密钥对则为:
= (K),
= (d)
签名的生成(x 为消息):
- 随机生成一个整数最为临时密钥
,且 0 <
< q。
-
=
G
- r =
mod n
- s = (hash(x)+d * r)
mod n
签名的验证:
- 计算辅助值 w =
mod n
- 计算辅助值
= w * hash(x) mod n
- 计算辅助值
= w * r mod n
-
=
G +
K
- 如果
== r mod n,则签名有效
Golang SDK ecdsa 签名过程代码:
for {
for {
k, err = randFieldElement(c, csprng) //生成临时密钥
if err != nil {
r = nil
return
}
//计算 k的逆
if in, ok := priv.Curve.(invertible); ok {
kInv = in.Inverse(k)
} else {
kInv = fermatInverse(k, N) // N != 0
}
//计算 r
r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
r.Mod(r, N)
if r.Sign() != 0 {
break
}
}
e := hashToInt(hash, c)
//计算 s
s = new(big.Int).Mul(priv.D, r)
s.Add(s, e)
s.Mul(s, kInv)
s.Mod(s, N) // N != 0
if s.Sign() != 0 {
break
}
}
pubkey recovery:
从签名信息中恢复公钥
比特币跟以太坊都有实现,但最终的签名信息序列化格式不同
// btc 中的格式
<(byte of 27+public key solution)+4 if compressed >< padded bytes for
signature R><padded bytes for signature S>
// 以太坊中的格式
[R || S || V] format where V is 0 or 1.
以太坊中的 go 实现也引用了btcd的代码,所以需要转换一下,具体可参考以太坊代码signature_nocgo.go
另:btc签名脚本中同时含有签名和公钥
公钥长度:
- compressed: 65 byte (1+32+32)
- uncompressed: 33 byte (1+32 )
Schnorr
有疑问加站长微信联系(非本文作者)
![](https://static.golangjob.cn/static/img/footer.png?imageView2/2/w/280)