读心术：从零知识证明中提取「知识」——探索零知识证明系列(11)

我们拆解下 ECDSA 签名，用交互的方式定义一个类似 ECDSA 的认证方案，交互见下图。

第一步：Alice 仍然是选择一个随机数 k，并将k映射到椭圆曲线上，得到点K，然后发送给 Bob
第二步：Bob 需要产生两个随机数，c和e，然后交给 Alice
第三步：Alice 计算 s，并且发送给 Bob，他来验证s的计算过程是否正确
注：对熟悉 ECDSA 签名方案的读者，这里略作解释，Bob 产生的 c对应被签消息的 Hash 值Hash(m)，而e则是由一个转换函数F(K)来产生。其中F(.)是取椭圆曲线上的点的 x 坐标经过(mod q)得到[6]。
江湖上流传着一个说法：ECDSA 签名方案有个严重的安全隐患，如果在两次签名中使用了同一个随机数，那么签名者的私钥将会暴露出来。其实 Schnorr 签名方案也有同样的问题。
当年 Sony PlayStation 3 的工程师在调用 ECDSA 库函数时，本来应该输入随机数的参数位置上，却传入了一个常数。熟悉密码学的黑客们发现了这个严重的后门。2011年1月，神奇小子 Geohot 公开发布了 Sony PS3 的主私钥，这意味着任何用户都可以轻松拿到游戏机的 root 权限。Sony 随后大为光火…… （后续故事大家可以上网搜）
如果 Alice 在两次交互过程中使用了同一个 K，那么 Bob 可以通过发送两个不同的c和c"来得到s和s"，然后通过下面的公式算出私钥a：
k = (c - c")/(s - s")a = (k * s - c)/e那么我们应该怎么来看这个「安全后门」呢？大家想想看，这个安全后门和我们前面证明过的 Schnorr 协议的可靠性证明几乎一模一样！这个算法正是 ECDSA 认证协议的「可靠性」证明中的「抽取器」算法。只不过在可靠性证明中，为了让 Alice 使用同一个随机数 k来认证两次，「抽取器」需要利用「时间倒流」的超能力。