算法抗攻击风险量化浅析
伍思义 诺方信息技术有限责任公司
摘要：本文列举国外若干算法攻击团队的攻击数据记录，对目前世界最流行的两种算法的抗攻击风险与电子商务安全试做一量化分析，供发展电子商务安全系统参考。
有矛就有盾，反之亦然。随着人类的进步与技术发展，矛与盾的斗争永远不会终结。算法技术与算法攻击技术也是如此，就像古今中外没有"常胜"将军一样，从来不存在绝对的安全。安全都是相对的，只能做到在一定的时间、空间与技术、经济范围内的安全。如欲超出此范围来做安全是永远也做不到的，也是没有意义的。尤其对电子商务安全更是如此，它具有空间范围大（全球）、时效周期较短、且要求成本低廉，并使众多的客户和商家都能用起来。因此，只要能做到使攻击者欲在其时效周期内攻破，其所花代价甚高于他所能得到的信息价值（数百万、乃至数仟万比1），因而非常不值得时，我们就有理由说这是安全的。这种安全的实效、技术、经济的统一是构造设计电子商务安全系统的最基本原则之一。
以下，对目前世界应用最广、最流行的的两种算法的抗攻击风险做一简要分析评估。
一、 关于RSA非对称算法
公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人首先发明的（论文"New Direction in Cryptography"） 。但目前最流行的RSA是由分别取自三位发明此算法的数学家（Ronald Rivest, Adi Shamir 和Len Adleman）的名字的第一个字母来构成的。
RSA算法研制的最初理念与目标是旨在解决DES算法秘密密钥利用公开信道传输分发困难的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。
RSA算法的保密强度随其密钥的长度增加而增强。但是，密钥越长，其加解密所耗的时间也越长。因此，要根据所保护信息的敏感程度与攻击者破解所要花的代价值不值得和系统所要求的反应时间来综合考虑决定。尤其对于商业信息领域更是如此。
但是，RSA同其它数学问题一样，也是存在有条件、有特例的。即在不论其密钥长度如何增加，以及如何选取其加、脱密参数，它至少存在有9个不能被加密的明文电文。如当明文是"0"、"+1"或"-1"时，它是不能被RSA加密的。余下的6个不能被加密的明文与其加密参数相关， 只要被偶然发现就有可能被人用∮（n）求解法，将RSA方式破开。
尽管如此，在RSA的开发中，编程者总是可以将这些特例分别地单独处理，将它们弄乱，使得攻击者摸不着头脑。
因此，从1977年RSA诞生以来，它经受了无数次的攻击考验，证明它仍然是一个优秀的非对称算法，可以做到安全。20多年来，RSA得到了世界上的最广泛的应用，并于1992年ISO国际标准化组织在其颁布的国际标准X.509中,将RSA算法已正式纳入国际标准。1999年美国参议院已通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。
以下列出美国麻省理工学院RSA129（N=10129素因子分解攻击研究小组Hal Abelson, Jeff Schiller, Brian lamacchia和Derek Atkins. 根据他们对PGP RSA（MPQS）算法攻击研究的结果如下；（注：1995，Simson Garfinkel 《Pretty Good Privacy》极好的保密系统一书）。
RSA-129 (429-bit key) 4600 MIPS-YEARS
即相当于要4600台VAX11/780联合运行一年的时间或一台Pentium100运行46年时间才能将一个N*10129的大数分解找到其P.Q.
采用RSA算法的安全管理：
1) 要严格管理、保存好自己的PIN IC卡。如PIN的物理保护失败，或私钥丢失与用户的口令被窃同时发生时，用户应及时挂失。
2) 密钥的更换周期
现代密码学的特征是算法可以公开。保密的关键是如何保护好自己的密钥，而破密的关键则是如何能破解得到密钥。
系统的安全主管者，要根据本系统实际所使用的密钥长度与其所保护的信息的敏感程度、重要程度以及系统实际所处安全环境的恶劣程度，参照以上的分析数据，在留有足够的安全系数的条件下来确定其密钥和证书更换周期的长短。同时，将已废弃的密钥和证书放入黑库归档，以备可能后用。
密钥更换周期的正确安全策略是系统能够安全运行的有力保障，是系统的安全管理者最重要、最核心的日常工作任务。
二、关于DES对称算法
为了建立适用于计算机系统的商用密码，美国商业部的国家标准局NBS于1973年5月和1974年8月两次发布通告，向社会征求密码算法。在征得的算法中，由IBM公司提出的算法lucifer中选。1975年3月， NBS向社会公布了此算法，以求得公众的评论。1977年1月以数据加密标准DES（Data Encryption Standard)的名称正式向社会公布。随后DES的应用范围迅速扩大到涉及美国以外的公司、甚至某些美国军事部门也使用了DES，引起了美国国家安全局的忧虑。因此，里根总统曾于1984年9月签署了一项命令，即NSDD-145号命令，下令责成美国防部的国家安全局负责组织、研制一种新的数据加密标准CCSE（Commercial Communication Security Endorsement)商用通信安全保证程序于1988年取代DES。后来由于遭到整个最大的金融界用户以其不符合他们的要求为由的强烈反对，美国政府在其国会的压力下才撤销了里根这个NSDD-145号命令。
DES诞生20余年，随着攻击技术的发展，DES经受了考验。DES本身又有发展，如衍生出可抗差分分析攻击的变形DES以及密钥长度为128比特的三重DES等。
以下是基于1997年的技术统计分析的攻击结果，JALAL FEGHHI等人98年9月给出DES加密抗攻击的情况如下表所述：(摘自由Jalal Feghhi, Jalil Feghhi, Peter Willians 《Digital Certificates》一书中的第51页，该书于1998/9由加拿大出版)
|
破解所需 攻击者 平均时间 类型 密钥长度 |
个人攻击 |
小组攻击 |
院、校网络攻击 |
大公司 |
军事情报机构 |
|
40（bits） |
数周 |
数日 |
数时 |
数毫秒 |
数微秒 |
|
56 |
数百年 |
数十年 |
数年 |
数小时 |
数秒钟 |
|
64 |
数千年 |
数百年 |
数十年 |
数日 |
数分钟 |
|
80 |
不可能 |
不可能 |
不可能 |
数百年 |
数百年 |
|
128 |
不可能 |
不可能 |
不可能 |
不可能 |
数千年 |
上表中攻击者配有如下计算机资源的攻击能力
|
攻击者类型 |
所配有的计算机资源 |
每秒处理的密钥数 |
|
个人攻击 |
1台高性能桌式计算机及其软件 |
217-224 |
|
小组攻击 |
16台高性能桌式计算机及其软件 |
221-224 |
|
院、校网络攻击 |
256台高性能桌式计算机及其软件 |
225-228 |
|
大公司 |
配有价值1百万美元的硬件 |
243 |
|
军事情报机构 |
配有价值1百万美元的硬件及先进的攻击技术 |
255 |
注：2000年的技术比97年预计将提高400倍左右。
另据美国（华尔街报）1999年3月8日报导，由Verisign公司（一个信息保密安全公司）经理 Anil Pereira分析指出，欲破解一个秘密密钥长度为128位的DES加密要比破解一个秘密密钥长度为40位的DES加密要困难300X1042倍（300 Septillion倍）。也就是说，如以300MC奔腾CPU的PC机破解40位DES加密要花3个小时计，那么用同样的PC机来破解一个128位DES加密就要花去900 X1042小时。这在一个人的有生之年是不可能做到的。目前尚无报导是否有数百人同时用数百台大型计算机利用互联网分布处理来破128位DES加密的事情。但可以肯定，这种做法所花代价对于普通的商密来讲，是十分不值的。
所以128比特密钥的三重DES，至少在今后的十年内仍然是安全的，尽管美国又在征集下一世纪的算法标准。
1997年4月15日，美国国家标准和技术研究所（NIST）又发起征集下一世纪的AES（Advanced Encryption Standard）密码算法标准的活动。
1997年9 月12月在联邦登记处（FR）公开发布了征集AES候选算法的通告，并提出了对AES的基本技术要求。即候选算法要比三重DES快，与三重DES一样安全，分组长度为128比特，密钥长度为128、192和256比特。
1998年8月，NIST召开了第一次AES候选会议，宣布对15个候选算法的若干讨论结果。作为第一轮评测于1999年4月15日结束。
15个候选算法情况是：其中5个来自美国（HPC、MARS、RC6、SAFERT和TWOFISH）；2个来自加拿大（CAST-256和REAL）；澳大利亚（LOK197）、比利时（RIJNDAEL）、哥斯达黎加（FROG）、法国（DFC）；德国（MAGENTA）、日本（EZ）、韩国（CRYPTON）和挪威（SERPENT）各一个。
第二轮评测将从15个候选算法中选出5个，最后再在这5个优选算法中评选出一个算法作为正式的AES标准，计划在2001年正式出台。
所以尽管美国早在97年就发起了征集本世纪的密码算法标准AES，如AES已定下来了，恐怕要取代原有的DES系统至少还要花五年左右的时间。
参改文献：
1）《计算机安全必读》
公安部计算机管理监察司主编 群众出版社91年出版
2）卿斯汉《网络安全的核心-密码算法和安全协议》
3）范元书等《AES算法的综合分析》
1999年10月苏州会议论文集《中国计算机学会信息保密专业委员会 论文集第九卷》。
4）《Pretty Good Privacy》 by Simson Garfinkel. 1995
5)《Digital Certificates》 by Jalal Feghhi,Jalil Feghhi,and Peter Willians 98.9 Canada