抗随机数后门攻击的密码算法∗

康步荣,张 磊,张 蕊,孟欣宇,陈 桐

1(软硬件协同设计技术与应用教育部工程研究中心(华东师范大学),上海 2000 62)

2(华东师范大学 软件工程学院,上海 20006 2)

3(密码科学技术国家重点实验室,北京 100 878)

迄今为止,大多数密码原语的安全性都依赖于高质量的不可预测的随机数[1−4].密码学中,我们通常用伪随机数生成器(pseudorandom nu mber generator,简称PRNG)来生成随机数.而实际上,很多人为因素会导致PRNG生成的随机数不安全[1−3,5].通常,我们称不安全的PRNG 为存在后门的PRNG(backdoored pseudorandom number generator,简称BPRNG).在信息安全领域,后门是指可以绕过安全控制而获取对程序或系统访问权的方法.后门的最主要目的就是方便以后再次秘密进入或者控制系统.此处,我们所研究的后门主要是指存在于密码组件PRNG 里的后门,这种后门使得PRNG 产生的用于密码算法中的随机数,对于那些已知此后门的人来说是可预测的.知道后门的攻击者因可预测随机数,他很可能会成功破解相应的密码算法,这将严重地威胁到密码算法的安全性.正如在2014年SXSW 大会(South B y Southwest Con ference)上斯诺登所言,攻击者在攻击加密算法时,真正受到攻击的其实是加密算法中使用的PRNG,而非算法本身.所以,研究抵抗随机数后门攻击的密码算法是非常有意义且有必要的.

说起对密码算法的威胁,量子计算机也是其中之一.近年来,量子信息科学的研究和发展催生了量子计算机[6],而量子计算机的强大计算能力对传统密码算法,尤其是对公钥密码算法产生了严重威胁[6].例如,Shor 算法就是一个分……