Page 264 - 《软件学报》2021年第9期

2888 Journal of Software 软件学报 Vol.32, No.9, September 2021

emerging of BPRNG, new challenges will be confronted with the study of cryptographic algorithms. Therefore, it is important to
investigate the cryptographic primitives against the BPRNG. This study first reviews the research background of the cryptographic
primitives against the BPRNG, and then summarizes the existing schemes in this field.
Key words: PRNG; BPRNG; BPRNG resistance; cryptographic algorithms

迄今为止,大多数密码原语的安全性都依赖于高质量的不可预测的随机数 [1−4] .密码学中,我们通常用伪随
机数生成器(pseudorandom number generator,简称 PRNG)来生成随机数.而实际上,很多人为因素会导致 PRNG
生成的随机数不安全 [1−3,5] .通常,我们称不安全的 PRNG 为存在后门的 PRNG(backdoored pseudorandom number
generator,简称 BPRNG).在信息安全领域,后门是指可以绕过安全控制而获取对程序或系统访问权的方法.后门
的最主要目的就是方便以后再次秘密进入或者控制系统.此处,我们所研究的后门主要是指存在于密码组件
PRNG 里的后门,这种后门使得 PRNG 产生的用于密码算法中的随机数,对于那些已知此后门的人来说是可预
测的.知道后门的攻击者因可预测随机数,他很可能会成功破解相应的密码算法,这将严重地威胁到密码算法的
安全性.正如在 2014 年 SXSW 大会(South By Southwest Conference)上斯诺登所言,攻击者在攻击加密算法时,
真正受到攻击的其实是加密算法中使用的 PRNG,而非算法本身.所以,研究抵抗随机数后门攻击的密码算法是
非常有意义且有必要的.
说起对密码算法的威胁,量子计算机也是其中之一.近年来,量子信息科学的研究和发展催生了量子计算
[6]
[6]
机 ,而量子计算机的强大计算能力对传统密码算法,尤其是对公钥密码算法产生了严重威胁 .例如,Shor 算法
就是一个分解大整数问题和求解离散对数问题的有效量子算法 [6,7] .Shor 算法的出现,严重威胁了基于大整数分
解困难问题和离散对数困难问题的公钥密码算法,如 RSA,ECC,ElGamal 算法等.文献[6]总结了现有的量子算法
及其对传统公钥密码算法的威胁,并梳理了量子计算机在物理实现上的发展历史及相应成果.到目前为止,虽然
国际上很多著名的公司都纷纷加入量子计算机的研制之中,但距离通用的量子计算机的大规模使用还需要很
长时间.因此,在量子计算机真正取代传统计算机之前,随机数后门攻击成为威胁现有密码算法的主要因素.研
究抗随机数后门攻击的密码算法是亟待解决的问题.
据统计,目前主要有两类影响 PRNG 工作过程的因素 [1,2,5,8−10] .
• 第 1 类影响因素是“漏洞”.例如,2006 年 9 月~2008 年 5 月发生在 Debian Linux 操作系统上的安全漏洞,
一名程序员删除了 OpenSSL 密码库里的部分代码,导致该系统中 PRNG 的种子密钥仅剩 15 位
熵 [11] .信息论中,熵用来表示一个数的不确定性,熵越大,数的不确定性越高.随后,传输层协议(transport
layer security,简称 TLS)和安全套接字层协议(secure sockets layer,简称 SSL)被曝出其服务器的重要组
件使用了有后门的 PRNG 而使协议存在安全漏洞 [12] ;
• 第 2 类影响因素被称为“恶意颠覆”,其目的是减弱 PRNG 生成随机数的随机性.一个典型的例子是双椭
圆曲线伪随机数生成器 Dual EC PRNG,Dual EC PRNG 是 NSA 设计的一个伪随机数生成器算法,由
NIST 列入算法标准 [1,2,5,8−10,13,14] .此后,Dual EC PRNG 一直被广泛使用,直至 2014 年,该算法被曝出存
在后门,即生成的随机数可预测 [15] .在实际应用中,Dual EC PRNG 被著名网络公司 Juniper Network 应
用于其所生产的 NetScreen VPN 路由器的操作系统中.在文献[16]中,作者详细分析了 NetScreen VPN
路由器所存在的该随机数后门攻击.
[5]
Dual EC PRNG 由两个算法组成 ——密钥生成算法 K 和随机数生成算法 G,可将其记为二元组 PRNG=
2
3
(K,G).Dual EC PRNG 是基于定义在有限域 F p 上的椭圆曲线 y =x +ax+b 设计的,这里,p 是一个素数.椭圆曲线上
d
的所有点组成群 G,其生成元为 g,阶为 q.密钥生成算法 K 随机选取群元素 Q∈G 和一个指数 d∈Z q ,计算 P=Q ,
输出公私钥对(pk,sk),其中,pk=(P,Q)对外公开,sk=d 保密.S 表示一个状态空间,S=Z q .随机数生成算法 G 输入 s i ∈S
i s
和公钥 pk,计算 s i+ 1 = P 作为下一个状态值,计算 r′ = Q i s 1 + ,将 r′ 的最后 16 位值去掉,用剩余位的值作为随机数
i+
i+
1
1
r i+1 ,算法 G 的输出为(s i+1 ,r i+1 ).需要注意的是:这里,椭圆曲线上点的运算都是对其横坐标进行运算.Dual EC
PRNG 的后门攻击是指一个攻击者如果已知私钥 d 和连续的两个随机数 r 1 ,r 2 的值,将 r 1 ,r 2 所对应的状态值记为
16
s,s 1 ,那么他可以有效地恢复出 s 2 的值.具体地,攻击者可以先对 r 1 进行后 16 位添加,恢复出 r′ ,共有 2 种可能性,
1