区块链中的数学 - 随机数和伪签名

  • blocksight
  • 更新于 2020-11-13 14:31
  • 阅读 5074

随机数在密码学体制中,占据重要的位置,如果不正确使用会带来非常大的安全隐患,历史上发生此类事故也不在少数。伪签名是一个弱问题,可能会对不熟悉的人造成欺骗。

写在前面

上一节是EdDSA的发展及优点,本节介绍以前提到过多次的随机数的影响和伪签名的构造!

本节的基础是之前介绍的各种签名机制,包括Schnorr签名,ECDSA(以scep256k1为例)等,本文不再详细说明,不熟悉的请参见历史文章,否则的话会如雾中看花,一头雾水!

随机数的影响

Schnorr与ECDSA签名过程中,都是用了随机数,潜在的安全隐患是: 如果任意两次签名不幸使用了相同的随机值k,则会暴露出私钥

Schnorr签名泄露

Schnorr签名有多种实现方式,主要是基于指数运算基于椭圆曲线运算两种。

本文以基于椭圆曲线的签名过程来分析。 Schnorr签名过程,简记如下: 生成签名:s = k + H(R||P||m) x 验证签名:sG = R + H(R||P||m)P 其中,k随机值,P公钥, R随机点(kG),m待签名消息, H摘要算法,x私钥

假如两次签名$s_1,s_2$的k相同,即: $s_1= k + H(R||P||m_1) x$ $s_2= k + H(R||P||m_2) x$

整理易得,$ x = ( s_1- s_2) / (H(R||P||m_1) - H(R||P||m_2))$ 私钥就此暴露。

Secp256k1签名泄露

Secp256k1签名过程简记如下: 生成签名:$s = H(m)/k + r/k x$ 验证签名:$sR = H(m)G + rP$   求得R点值:$R = H(m)/sG + r/s * P$   比较r值:$r == R.x$,验证r是否一致。 符号含义同上,不再说明。

假如两次签名$s_1,s_2$的k相同,即: $s_1= H(m_1)/k + r/k x$ $s_2= H(m_2)/k + r/k x$

首先可以计算出: $k = ( s_1-s_2 ) / (H(m_1) -H(m_2))$ 其次,知道了k, 代入可得: $x = ( s_1- H(m_1)/k)k/r$ 或 $x = ( s_2- H(m_2)/k)k/r$

可见,这种情况下破解私钥并不困难。这种问题就曾经出现在索尼公司的PS3产品签名中,以太坊签名也出现过类似事件,参考:https://xz.aliyun.com/t/2718

EcDSA伪签名问题

上一篇我们说了EcDSA签名机制的弱点,其中有一项就是可以一定程度是“伪造”签名,通过签名验证。之所以说是一定程度,就代表不是真正意义上的签名。

依然以Secp256k1为例说明,由签名验证过程可得: R = H(m)/s G + r/s P 如果令 u = H(m)/s, v = r/s, 那么 R = uG + vP 通过随机生成【注:当然也可以刻意选取】u、v的值u',v',使得: u'G + v'P = R' 计算出 r' = R'.x, 从而得到 s' = r'/v, H(m') = u * s'

那么对于消息m',其签名结果为:(r', s')。此签名是可以通过验证检查,所以有效。

这个操作其实有点类似于签名延展性,没有通过私钥,利用已有合法签名构造另外的有效签名。 据说CSW(澳本聪)就曾经利用此方法伪造中本聪的签名,来宣称自己是真的中本聪。

既然说是伪造,就肯定可以鉴别,由于签名中使用了消息的哈希值,可以要求其出示原始消息,由哈希函数的的抗碰撞性可以判断如果是伪造的,是不会知道原始消息的。 当然,最安全的做法是给定一个新的消息,让其签名,如果不知道私钥,是无法对新消息进行签名的。

说到了伪签名,那么Schnorr签名会有这种情况吗?答案是否定的。

其验证等式:sG = R + H(R||P||m)P

若试图随机或者选取特定s值,则无法找到合适的R’和m’,因为R值包含在哈希函数中, 若试图随机或者选取特定R和m值,sG是椭圆曲线乘法,曲线除法不可逆的情况下是无法找到对应的s’值。那么签名结果(r', s')就无法构造。

因此Schnorr签名算法对伪签名是免疫的, 同样的,前几篇说到的爱德华签名机制Ed25519也不会有伪签名的问题。

小结

随机数在密码学体制中,占据重要的位置,如果不正确使用会带来非常大的安全隐患,历史上发生此类事故也不在少数。伪签名是一个弱问题,可能会对不熟悉的人造成欺骗。

之前说了多种签名算法,除了本文提到的,还有RSA签名,sm2, EIGamel签名等,大家可以自行检查是否存在本文所述的问题。

既然又说到了签名问题,那就深入一下,下一篇继续介绍多签名和阈值签名!

欢迎关注公众号:blocksight

相关阅读:

区块链中的数学 - EdDSA签名机制 EdDSA的发展及优点

区块链中的数学 - Ed25519签名

区块链中的数学-蒙哥马利曲线&Curve25519实例

区块链中的数学-ElGamal算法 ElGamal算法签名及验证&实例演练

区块链中的数学-椭圆曲线进行签名和验证过程 secp256签名和验证过程

区块链中的数学- RSA签名过程 RSA签名和安全分析-计时攻击

区块链中的数学-VRF基于ECC公钥体制的证明验证过程 基于椭圆曲线的VRF证明验证过程

Schorr签名与椭圆曲线 Schorr签名与椭圆曲线

区块链中的数学-Schnorr 离散对数签名及素数阶群构造(Schnorr 群) Schnorr签名及Schnorr群

区块链中的数学-Uniwap自动化做市商核心算法解析 Uniwap核心算法解析(中)

点赞 0
收藏 1
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
blocksight
blocksight
江湖只有他的大名,没有他的介绍。