椭圆曲线和Dual_EC_DRBG后门

Fri 20 December 2013

这两天爆出NSA收买RSA将NSA推荐的算法，Dual_EC_DRBG，设置为BSafe中默认的随机数生成算法。为了推广这种算法，其实早在2007年NSA就执意将其写入了NIST（美国国家标准技术管理委员会）的确定性随机数生成器推荐标准（Special Publication 800-90，SP800-90），即使它速度极慢。同年Dual_EC_DRBG就在Crypto 2007会议上被指出存在被植入后门的可能，但不能认定算法设计者是否知道后门的参数，也不能认定NIST有意在算法中植入后门。2013年9月Edward Snowden泄漏的内部备忘录显示NSA曾向某加密算法植入后门，再到12月路透社爆出RSA被收买，现在看起来是NSA精心选取参数值下后门。有意思的是，比特币也使用了ECC来生成随机数，但是比特币神秘创始人中本聪在2009年发明比特币的时采用了小众的secp256k1的曲线参数而不是有问题的secp256r1（NIST P-256），神奇地躲过了密码学子弹。

那么Dual_EC_DRBG漏洞在哪，为什么随机数生成器的漏洞会让加密算法被攻破？先要从椭圆曲线和随机数生成器说起。

椭圆曲线

椭圆曲线密码学（Elliptic curve cryptography，ECC）由Koblitz和Miller分别独立提出，是迄今为止安全性最高的一种公钥密码算法。椭圆曲线E的形式是：

$$y^2=x^3+ax+b, a,b \in F_p$$

有限域Fq，q一般是2的m次方或大素数p ...