量子计算(一)RSA加密算法

密码学的发展分为三个阶段:加密算法的保密(古典密码学),密钥的保密(对称加密),私钥的保密(非对称加密)。在对称加密的情况下,如果文件的接收方需要解密文件,就必须要拿到密码,文件发送者不得不对每个文件都设置一个密码,管理困难并且密码的保存和传输的安全性直接关系到加密算法本身。那么非对称加密就应运而生了。1977年,三维在MIT工作的R\S\A提出了RSA算法,并延用至今,加密用的密码(私钥)和解密用的密码(公钥)分离开来,我们公布公钥就可以保证传输安全了。根据公钥推导私钥就成为了密码学的攻防的焦点。

非对称加密的安全性依赖于数学难题的破解。比如RSA算法的破解需要用到素数的因式分解,大数的因式分解是很困难的,现有数学方法可以给出计算时间复杂度很高的算法。1999年,RSA-155 (512 bits)被成功分解,花了五个月时间(约8000 MIPS年)和224 CPU hours在一台有3.2G中央内存的Cray C916计算机上完成。

395058745832651445264197678006144819960207764603049364541393760515793556265294506836097278424682195350935443058704902519956553357102097992264849779494429556033388495837466721394368393204672181522815830368604993048084925840555281177×  11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

2009年,RSA768被破解:

12301866845301177551304949583849627207728535695953347921973224521517264005072636575187452021997864693899564749427740638459251925573263034537315482685079170261221429134616704292143116022212404792747377940806653514195974598569021434133347807169895689878604416984821269081770479498371376856891  2431388982883793878002287614711652531743087737814467999489×  3674604366679959042824463379962795263227915816434308764267  6032283815739666511279233373417143396810270092798736308917
 
破解复杂度随着密钥长度的增加是指数级上升的,所以目前的RSA1024依然被冉伟是相对安全的,RSA-2048被认为是绝对安全的。
 
计算机破解RSA依赖穷举,1994年Shor算法提出,利用量子算法可以大大加速RSA的破解,量子计算将时间负责度为指数级的算法,变成了时间复杂度为O(N),空间复杂度为O(N)的算法。
 
虽然量子计算机在十几年内仍无法得到应用,但是其出现危害极大,所以现在进行加密研究时,会针对量子计算的解密能力进行评估。
 
量子计算机是现今唯一能指数级加速算法的硬件,其与传统计算机架构完全不同,下一章节再详细介绍。

发表评论