Steven's Blog

Appearance

On this page

如果使用了相同的随机数,为什么会泄露私钥.

椭圆曲线签名算法原理 ​

假设私钥为k,那么公钥K=kGK=kG,其中G为G点(就是椭圆曲线的公共参数,可以忽略). 签名的过程如下:

  1. 选择随机数n,计算P=nGP=nG,P实际上就是曲线上的一个点
  2. 计算s=m+krns=\frac {m+kr} n,其中m就是公共信息,比如是一个以太坊交易的Hash值. 这里的r是P的x坐标.
  3. 将消息m和签名{r,s}发送给接收方 接收方在事先知道公钥K的情况下,就很容易验证签名和m是否是对应关系. 验证签名的过程: 计算$\frac {mG} s + \frac {rK} s $,然后与nG比较,如果相等说明是对应关系.其中r是nG这个点的x坐标

为什么这样可以呢,来看一下简单的推导过程:

\begin{eqnarray} & \frac {mG} s + \frac {rK} s \\ =& \frac {mG} s + \frac {r(kG)} s \\ =& \frac {(m+rk)G} s \\ =& \frac {n(m+rk)G} {m+kr} \\ =& nG \end{eqnarray}

注意: s=m+krns=\frac {m+kr} n

go实现的签名 ​

以下代码来自btcd

go
// signRFC6979 generates a deterministic ECDSA signature according to RFC 6979 and BIP 62.
func signRFC6979(privateKey *PrivateKey, hash []byte) (*Signature, error) {

	privkey := privateKey.ToECDSA()
	N := S256().N
	halfOrder := S256().halfOrder
	k := nonceRFC6979(privkey.D, hash) //这里的k对应的是上述公式中的n
	inv := new(big.Int).ModInverse(k, N) //n^(-1)
	r, _ := privkey.Curve.ScalarBaseMult(k.Bytes()) //r是上述公式中的r,就是P的x坐标
	r.Mod(r, N) //r%N

	if r.Sign() == 0 {
		return nil, errors.New("calculated R is zero")
	}

	e := hashToInt(hash, privkey.Curve) //这个e可以认为是代签名消息m,这里是将hash转换成一个256位的整数来参与计算
	s := new(big.Int).Mul(privkey.D, r) //s=rG
	s.Add(s, e) // s=s+e
	s.Mul(s, inv) //s=s*(n^(-1))
	s.Mod(s, N) //s=s%N  这五行代码就是计算`$s=\frac {m+kr} n$`

	if s.Cmp(halfOrder) == 1 { 
		s.Sub(N, s) //s不能超过N/2
	}
	if s.Sign() == 0 {
		return nil, errors.New("calculated S is zero")
	}
	return &Signature{R: r, S: s}, nil
}

go实现的签名验证过程 ​

以下代码来自go标准库的crypto/ecdsa/ecdsa.go

go
// Verify verifies the signature in r, s of hash using the public key, pub. Its
// return value records whether the signature is valid.
func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
	// See [NSA] 3.4.2
	c := pub.Curve
	N := c.Params().N

	if r.Sign() <= 0 || s.Sign() <= 0 {
		return false
	}
	if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
		return false
	}
	e := hashToInt(hash, c)

	var w *big.Int
	if in, ok := c.(invertible); ok {
		w = in.Inverse(s)
	} else {
		w = new(big.Int).ModInverse(s, N)
	}

	u1 := e.Mul(e, w)
	u1.Mod(u1, N)
	u2 := w.Mul(r, w)
	u2.Mod(u2, N)

	// Check if implements S1*g + S2*p
	var x, y *big.Int
	if opt, ok := c.(combinedMult); ok {
		x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
	} else {
		x1, y1 := c.ScalarBaseMult(u1.Bytes())
		x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
		x, y = c.Add(x1, y1, x2, y2)
	}

	if x.Sign() == 0 && y.Sign() == 0 {
		return false
	}
	x.Mod(x, N)
	return x.Cmp(r) == 0
}

使用了相同的随机数n,为什么能推出私钥 ​

如果使用了相同的随机数n,那么签名中的{r,s}中的r肯定也是相同的,因为r是nG的x坐标. 那么来看看推到的过程.

s_1=\frac {m_1+kr} n \\ s_2=\frac {m_2+kr} n \\ s_1-s_2= \frac {m_1-m_2} n \\ n=\frac {m_1-m_2} {s_1-s_2}

有了n以后,那么来看一下k的计算过程:

s=\frac {m+kr} n \\ k=\frac {sn-m} r

验证 ​

也就是说,那怕只用了一次相同的k,私钥都会泄露.

go
import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"encoding/hex"
	"errors"
	"log"
	"math/big"
	"testing"

	"github.com/btcsuite/btcd/btcec"
)

// hashToInt converts a hash value to an integer. There is some disagreement
// about how this is done. [NSA] suggests that this is done in the obvious
// manner, but [SECG] truncates the hash to the bit-length of the curve order
// first. We follow [SECG] because that's what OpenSSL does. Additionally,
// OpenSSL right shifts excess bits from the number if the hash is too large
// and we mirror that too.
// This is borrowed from crypto/ecdsa.
func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
	orderBits := c.Params().N.BitLen()
	orderBytes := (orderBits + 7) / 8
	if len(hash) > orderBytes {
		hash = hash[:orderBytes]
	}

	ret := new(big.Int).SetBytes(hash)
	excess := len(hash)*8 - orderBits
	if excess > 0 {
		ret.Rsh(ret, uint(excess))
	}
	return ret
}

// PrivKeyFromBytes returns a private and public key for `curve' based on the
// private key passed as an argument as a byte slice.
func privKeyFromBytes(curve elliptic.Curve, pk []byte) (*ecdsa.PrivateKey,
	*ecdsa.PublicKey) {
	x, y := curve.ScalarBaseMult(pk)

	priv := &ecdsa.PrivateKey{
		PublicKey: ecdsa.PublicKey{
			Curve: curve,
			X:     x,
			Y:     y,
		},
		D: new(big.Int).SetBytes(pk),
	}

	return priv, &priv.PublicKey
}

func getPrivateKey(hash1, hash2 []byte, r, s1, s2 *big.Int, pub *ecdsa.PublicKey) (*ecdsa.PrivateKey, error) {
	c := btcec.S256()
	m1 := hashToInt(hash1, c)
	m2 := hashToInt(hash2, c)
	ss1 := []*big.Int{s1, new(big.Int).Sub(c.N, s1)}
	ss2 := []*big.Int{s2, new(big.Int).Sub(c.N, s2)}
	//这里这么处理是因为s1,s2有可能因为超过了N/2,而进行了N-s,这里只能进行四种组合测试.
	for _, s1 = range ss1 {
		for _, s2 = range ss2 {
			s := new(big.Int).Sub(s1, s2)
			m := new(big.Int).Sub(m1, m2)
			s = s.Mod(s, c.N)
			s = s.ModInverse(s, c.N)
			n := s.Mul(s, m)

			k := new(big.Int).Mul(s1, n)
			k = k.Sub(k, m1)
			r.ModInverse(r, c.N)
			k = k.Mul(k, r)
			k = k.Mod(k, c.N)
			log.Printf("k=%s", k.Text(16))
			//通过k来生成公钥,如果匹配,说明私钥正确
			priv, pub2 := privKeyFromBytes(btcec.S256(), k.Bytes())
			if pub2.X.Cmp(pub.X) == 0 && pub2.Y.Cmp(pub.Y) == 0 {
				return priv, nil
			}
		}
	}
	return nil, errors.New("not found private key")
}

/*
privkey=eaf02ca348c524e6392655ba4d29603cd1a7347d9d65cfe93ce1ebffdca22694
pubkey=045ceeba2ab4a635df2c0301a3d773da06ac5a18a7c3e0d09a795d7e57d233edf1001aa641732e6a703be89a7fb8568df05675111fcddd519e0cc6c2dd72cd73f8
hash1=00010203040506070809 sig1 r=e8f0817ae1ad2c1c35770dc8fff5f0ed513769e39e2af6e8e0b4f42e5a60251d,s=2c77219de3f968d38434e89a68428c1c30892e891e02708849137ebb61301794
hash2=00010203040506070810 sig2 r=e8f0817ae1ad2c1c35770dc8fff5f0ed513769e39e2af6e8e0b4f42e5a60251d,s=344d47eb5b12343bdc8f80eed6c910f2b543359b1373b7dabac1ba2658d23906
尝试通过相同的r来恢复私钥
*/
func TestGetPrivkey(t *testing.T) {
	c := btcec.S256()
	pubkeybin, err := hex.DecodeString("045ceeba2ab4a635df2c0301a3d773da06ac5a18a7c3e0d09a795d7e57d233edf1001aa641732e6a703be89a7fb8568df05675111fcddd519e0cc6c2dd72cd73f8")
	if err != nil {
		t.Fatal(err)
	}
	pub, err := btcec.ParsePubKey(pubkeybin, c)
	if err != nil {
		t.Errorf("privkey: %v", err)
		return
	}
	hash1 := []byte{0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9}
	hash2 := []byte{0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x10}
	s1, _ := new(big.Int).SetString("2c77219de3f968d38434e89a68428c1c30892e891e02708849137ebb61301794", 16)
	s2, _ := new(big.Int).SetString("344d47eb5b12343bdc8f80eed6c910f2b543359b1373b7dabac1ba2658d23906", 16)
	r1, _ := new(big.Int).SetString("e8f0817ae1ad2c1c35770dc8fff5f0ed513769e39e2af6e8e0b4f42e5a60251d", 16)
	priv, err := getPrivateKey(hash1, hash2, r1, s1, s2, pub.ToECDSA())
	if err != nil {
		t.Error(err)
	} else {
		log.Printf("priv=%s", priv.D.Text(16))
	}

}