现代密码算法研究

基金项目：国家重点基础研究发展规划项目(973计划)(No.2007CB311203)

      信息安全本身包括的范围很大，从安全性需求的角度来说涉及到信息的保密性、完整性、可用性、认证性和不可否认性。其中，密码技术是保障信息安全的核心技术。

      密码学是一门充满挑战的交叉学科，有着悠久而迷人的历史。4 000多年前就有埃及人运用简单的加密手段传递秘密信息的记录。在两次世界大战中，密码学更是扮演了举足轻重的角色。但是，早期密码技术的研究和应用多属于军队、外交和政府行为。20世纪60年代计算机与通信系统的迅猛发展，促使人们开始考虑如何通过计算机和通信网络安全地完成各项事务，从而使得密码技术开始广泛应用于民间，也进一步促进了密码技术的迅猛发展。

      传统密码技术更多被看成是一门艺术，密码学专家常常是凭自己的直觉来进行密码算法的设计和分析。直到1949年Shannon[1]发表《保密系统的通信理论》一文，文章从信息论的角度讨论了加密系统的安全性和设计准则，从此将密码学从艺术带入了系统科学的殿堂。20世纪70年代，IBM公司设计出数据加密标准(DES)分组密码算法，并在1977年被美国联邦政府采纳为联邦信息处理标准。几乎同时，Diffie和Hellman[2]提出了公钥密码学的思想。他们在《密码学的新方向》一文中解决了原有对称密码系统存在的密钥分配问题，并提出了数字签名的新思路。1978年，Rivest、Shamir和Aldleman[3]设计出了第一个在实践中可用的公开密钥加密和签名方案——RSA，从而拉开了现代密码学的序幕。

1 对称加密算法
      密码算法主要分为对称密码算法和非对称密码算法两大类。对称加密算法指加密密钥和解密密钥相同，或知道密钥之一很容易推导得到另一个密钥。通常情况下，对称密钥加密算法的加/解密速度非常快，因此，这类算法适用于大批量数据加密的场合。这类算法又分为分组密码和流密码两大类。

1.1 分组密码
      分组密码算法如图1所示。相对流密码算法来说，分组密码算法不需要存储生成的密钥序列，所以适用于存储空间有限的加密场合。此外，目前使用的分组密码算法的分析和设计过程都相对公开，通常伴随着大型的征集和公开评估活动。这样一来不仅仅增加了算法的透明度，防止攻击者隐藏陷门并使得用户充分相信算法的安全强度；另一方面极大促进了分组密码技术的飞速发展。

      1973年5月13日的美国联邦政府提出征求在传输和存储数据中保护计算机数据的密码算法的建议，这一举措最终导致了DES算法的研制。在公开征得的众多算法中，IBM公司提出的算法Lucifer中选。1975年3月17日，美国国家标准局(NBS)首次公布了此算法，请公众评议。1977年1月NBS正式向社会公布，采纳IBM公司设计的方案作为非机密数据的数据加密标准。DES正式成为美国联邦政府信息处理标准，即FIPS-46标准，同年7月15日开始生效。此后，每隔5年美国国家保密局(NSA)对DES作新的评估，并重新批准它是否继续作为联邦加密标准。

      1997年，美国标准技术研究所(NIST)对DES进行再次评测并宣布：DES算法的安全强度已经不足以保障联邦政府信息数据的安全性，所以NIST建议撤销相关标准，此后DES算法只作为三重数据加密标准(TDES)的一个组成部分使用。同时，NIST开始征集新的数据加密标准高级数据加密标准(AES)[4]，他们要求新算法的分组长度为128，支持可变密钥长度128、192、256比特。1998年，NIST在第一轮AES征集会议上公布了征集到的15个算法，并且邀请全世界的密码研究机构对算法进行安全性等方面的评测。1999年，NIST从中选取了5个优良的算法作为AES的候选算法，它们分别是MARS、RC6、Rijndael、Serpent和Twofish，并通过最终的综合评价确定Rijndael算法为新的数据加密标准，2001年12月正式公布FIPS-197标准。

      欧洲于2000年1月启动了NESSIE工程[5]，该工程的目的是评价出包含分组密码、流密码等在内的一系列安全、高效和灵活的密码算法。至2000年9月，共收集到了17个分组密码算法，同时他们将TDES和AES纳入了评估范围，并作为分组密码算法的评测基准。经过3年2个阶段的筛选，最终确定下列算法为推荐的分组密码算法：MISTY164、Camllia128、SHACAL-2和AES128。
日本政府在2000年成立了密码研究与评估委员会(CRYPTREC)[6]并参考欧洲NESSIE工程的作法对密码算法的安全性和效率等问题进行评估，以备政府使用。评估涵盖了对称密码算法、非对称密码算法、散列函数和随机数生成器4部分。2002年初步拟定了推荐算法的草案，2003年3月确定了推荐算法名单，其中分组密码算法包括：

• 分组长度为64比特的算法：CIPHERUNICORN-E、MISTY1[Ma00]和3-keyTDES。
• 分组长度为128比特的算法：Camellia、CIPHERUNICORN-A、SC2000、Hierocrypt-3和Rijndael128。

      目前，分组密码的设计与分析依然是密码学研究的热点。设计方面主要是寻求更好的设计技术在安全性和效率方面突破AES算法。分析方面主要是可证明安全性理论研究、应用安全性研究及新的攻击方法挖掘。此外，利用分组密码技术设计新的流密码算法、新的Hash函数算法也是研究的热点。

1.2 流密码
      流密码(也叫序列密码)的理论基础是一次一密算法，它的主要原理是：生成与明文信息流同样长度的随机密钥序列，使用该序列按比特加密信息流，得到密文序列，解密变换是加密变换的逆过程。根据Shannon的研究，这样的算法可以达到完全保密的要求。但是，在现实生活中，生成完全随机的密钥序列是不可行的，因此只能生成一些类似随机的密钥序列，称之为伪随机序列。

      流密码内部存在记忆元件(存储器)来存储生成的密钥序列。根据加密器中记忆元件的存储状态是否依赖于输入的明文序列，又分为同步流密码算法(如图2所示)和自同步流密码算法(如图3所示)。

      流密码算法最初主要用于政府、军方等国家要害部门，因此，流密码不像分组密码那样有公开的国际标准，大多数设计、分析成果都是保密的。但是随着流密码的应用需求越来越广泛，从NESSIE工程开始，流密码算法的设计与分析也列上了公开征集评测的日程。

      2000年1月欧洲启动的NESSIE工程中，有6个流密码算法(Leviathan、UIi-128、BMGL、SOBER-t32、SNOW、SOBER-tl)进入了第二阶段评估，但是因为他们都不符合NESSIE的征集准则而最终全部落选。

      2003年3月，日本政府的密码研究与评估委员会(CRYPTREC)推荐了3个流密码算法：MUGI、MULTI-S01和RC4-128。

      ECRYPT[7]是欧洲第6框架研究计划(FP6)下IST基金支持的一个为期4年的项目，该项目启动于2004年2月，分为AZTEC、PROVILAB、VAMPIRE、STVL和WAVILA 5个部分。其中STVL正在进行流密码算法的公开征集评估活动：2004年10月14—15日在比利时举行了一个名为SASC的特别会议，会议的讨论引发了流密码算法的征集活动，并于2004年11月发布了征集公告，这也是对NESSIE没有征集到流密码算法的一个补充。征集活动到2005年4月29日结束，根据4个征集原则，一共征集到了34个流密码算法。2007年4月开始进入第三轮评估，针对软件设计的候选算法有CryptMT(Version3)、Dragon、Rabbit、HC(HC-128和HC-256)、LEX(LEX-128、LEX-192和LEX-256)、NLS(NLSv2加密)、Salsa20和SOSEMANUK。针对硬件设计的候选算法包括DECIM(DECIMv2和DECIM-128)、F-FCSR(F-FCSR-Hv2和F-FCSR-16)、Edon80、Grain(Grainv1和Grain-128)、MICKEY(MICKEY2.0和MICKEY-1282.0)、Moustique、Trivium和Pomaranch (Version 3) 。

      对流密码研究内容集中在如下两方面：
      (1)衡量密钥流序列好坏的标准。通常，密钥序列的检验标准采用Golomb的3点随机性公设，除此之外，还需做进一步局部随机性检验，包括频率检验、序列检验、扑克检验、自相关检验和游程检验，以及反映序列不可预测性的复杂度测试等。但是，究竟什么样的序列可以作为安全可靠的密钥序列，还是一个未知的问题。

      (2)构造线性复杂度高、周期大的密钥流序列。当前最常用的密钥序列产生器主要有：基于线性反馈移位寄存器的前馈序列产生器、非线性组合序列产生器、钟控序列产生器、基于分组密码技术的密钥生成器等。

2 Hash函数
      Hash函数(也称杂凑函数、散列函数)就是把任意长的输入消息串变化成固定长度的输出“0”、“1”串的函数，输出“0”、“1”串被称为该消息的Hash值(或杂凑值)。一个比较安全的Hash函数应该至少满足以下几个条件：

• 输出串长度至少为128比特，以抵抗生日攻击。
• 对每一个给定的输入，计算Hash值很容易(Hash算法的运行效率通常都很高)。
• 对给定的Hash函数，已知Hash值，得到相应的输入消息串(求逆)是计算上不可行的。
• 对给定的Hash函数和一个随机选择的消息，找到另一个与该消息不同的消息使得它们Hash值相同(第二原像攻击)是计算上不可行的。
• 对给定的Hash函数，找到两个不同的输入消息串使得它们的Hash值相同(即碰撞攻击)实际计算上是不可行的。
  

      Hash函数主要用于消息认证算法构造、口令保护、比特承诺协议、随机数生成和数字签名算法中。Hash函数算法有很多，最著名的主要有MD系列和SHA系列，一直以来，对于这些算法的安全性分析结果没有很大突破，这给了人们足够的信心相信它们是足够安全的，并被广泛应用于网络通信协议当中。直到2004年，中国密码学家王小云教授和她的团队将MD4的碰撞攻击复杂度时间降到手工可计算[8]；并将寻找MD5算法实际碰撞的复杂度和SHA-1算法碰撞的理论复杂度分别降为239和263 [9-10]。她们的出色工作，颠覆了这座坚固的大厦，也迫使众多密码学家重新评价目前Hash算法的安全强度，同时思考新的Hash函数算法设计方法。

      NESSIE工程推荐使用的Hash算法有SHA-256/384/512和Whirlpool，日本密码研究与评估委员会推荐使用的算法有SHA-1/256/384/512、 RIPEMD-160。

      ECRYPT也在Hash算法研究方面举办了一系列活动。此外，NIST研究所将于2008年启动新的Hash标准的征集活动。

3 非对称密码算法
      非对称密钥密码体制，即公开密钥密码体制指用户有两个密钥，一个公开密钥，一个私有密钥，并且从私有密钥推导公开密钥是计算不可行的。公钥加密算法在运行速度方面无法和对称加密算法媲美，但是这一思想很好地解决了对称密码学面临的密钥的分发与管理问题，同时对于数字签名问题也给出了完美的解答，并正在继续产生许多新的，优秀的思想和方案。

3.1 基于CA的公钥密码
      公钥密码算法设计的关键是存在多项式时间内不可解的困难问题。最早的也是目前使用最广泛的公钥加密和签名方案是RSA算法，该算法的安全性基于大整数分解问题。

      Diffie和Hellman提出的DH密钥交换方案以及后来的数字签名标准(DSS)和ElGamal加密算法多基于同离散对数问题相关的困难问题。此外，在基于离散对数问题的密码算法中有一类特殊的算法——椭圆曲线和超椭圆曲线密码学(ECC)。这类算法的优点是参数长度较短(见表1)可以达到较高的安全性，因此，非常适合在智能卡等存储空间有限的密码设备上使用。

      在NESSIE工程中共推荐了3个数字签名算法：ECDSA、RSA-PSS、SFLASH。2003年3月，日本政府的密码研究与评估委员会推荐了两个公钥加密算法(RSAES-PKCS1-v1 5、RAS-OAEP)和4个数字签名算法(ECDSA、RSASSA-PKCS1-v1 5、 DSA、RSA-PSS)。

      历经20多年的分析研究，密码学家依然没有彻底攻破基于整数分解和基于离散对数的经典算法，从而增强了人们对于这些算法的信心，但是这并不意味着公钥加密和签名算法的研究可以停滞不前了。首先，虽然在原始计算模型的假设下，目前为止最有效的分解因子解法和离散对数解法都是亚指数时间。但是离散对数问题和分解因子问题始终没有被证明是多项式时间内不可解(NP)问题。其次，即使证明他们是NP问题，也不能确保相应的密码算法是安全的，例如基于背包问题设计的密码算法几乎全军覆没。最后，在量子计算机问世后，这两类问题将存在多项式时间解法[11]。所以，密码学家一直在探寻新的、可以用于设计公钥密码算法的困难问题。目前研究比较广泛的算法主要有如下几种：基于编码问题的公钥密码算法(McEliece，1978)、基于格问题的密码算法(NTRU，1996)、多变量密码系统(Multivariate PKC，1999)以及基于无限群理论的密码算法(辫子群， 2000)等。

3.2 基于身份的公钥密码
      基于身份的密码学是由Shamir[12]于1984年提出。其主要思想是，系统中可以直接使用用户的标识，如姓名、IP地址、电子邮件地址等作为用户的公钥。用户的私钥通过一个被称作私钥生成器(PKG)的可信任第三方计算分发给用户。Shamir在提出这一思想的同时设计了一个基于身份的数字签名方案。然而，直到2001年，Boneh等人[13]利用椭圆曲线的双线性对才得到一个真正有效的基于身份的加密体制(IBE)。目前，基于身份的方案(包括基于身份的加密算法、签名算法以及各种协议)不断涌现出来。现阶段，基于对的运算效率问题是亟需解决的问题，也是现在研究的热门问题。

3.3 密码协议
      所谓协议，就是两个或者两个以上的参与者为完成某项特定的任务而采取的一系列步骤。密码协议的参与者可能是可以信任的人，也可能是攻击者。在网络通信中最常用的基本的密码协议按照其完成的功能可以分成以下3类：

      (1)密钥交换协议
      参与协议的两个或者多个实体之间建立共享的秘密，例如在一次通信中所使用的会话密钥。协议可以采用对称密码体制，也可以采用非对称密码体制，例如Diffie-Hellman密钥交换协议。日本政府的密码研究与评估委员会推荐了3个密钥交换协议(DH、ECDH、PSEC-KEM)。

      (2)认证协议
      认证协议中包括实体认证(身份认证)协议、消息认证协议、数据源认证和数据目的认证协议等，用来防止假冒、篡改、否认等攻击。NESSIE工程中推荐了一个由法国的Ecole Normal Superieure大学和电信公司提交的鉴别方案GPS。

      (3)解决特殊问题的安全协议
      解决特殊问题的安全协议有电子选举协议、电子钱币协议、安全多方计算协议等。

      ECRYPT的PROVI实验室在密码协议研究方面又划分了3个研究小组：模型和定义小组，主要负责认证、密钥协商、零知识和身份认证的研究；安全计算小组，主要负责高效的多方计算协议、实用协议的可证明安全性和安全协议的无条件安全性研究；合理密码协议小组，主要负责密码协议模型的定义和合理参与者的多方计算问题研究。ECRYPT于2007年3月和7月分别举办了相关的主题研讨会。

      密码协议是许多分布式系统安全的基础，因此，对协议的安全性进行分析和研究是一个重要的课题。造成协议存在安全缺陷的原因主要有两个：一是协议设计者误解或者采用了不恰当的技术；二是协议设计者对环境的安全需求研究不足。目前，对密码协议进行分析的方法主要有两大类：一类是攻击检验方法；一类是形式化的分析方法。所谓攻击检验方法就是搜集使用目前的对协议的有效攻击方法，逐一对安全协议进行攻击，检验安全协议是否具有抵抗这些攻击的能力。这种分析方法是否奏效关键在于攻击方法的选择。形式化的分析方法是采用各种语言或者模型，为协议建立模型，并按照规定的假设和分析、验证方法证明协议的安全性。目前，形式化的分析方法是研究的热点，但是就其实用性来说，还没有什么突破性的进展。

4 参考文献
[1] SHANNON C E. Communication theory of secrecy systems [J]. Bell System Technical Journal, 1949, 28(4): 656-715.
[2] DIFFIE W, HELLMAN M. New irection in Cryptography [J]. IEEE Transactions on Information Theory, 1976,22(6):644-654.
[3] The RSA challenge numbers [EB/OL]. http://www.rsa.com/rsalabs/node.asp.
[4] AES Candidate algorithms [EB/OL]. http://cSRCnistgov/encryption/aes/aes-homehtm#candidates.
[5] Linear cryptan alysis of reduced-round SAFER++ [EB/OL]. http://www.cryptonessie. org.
[6] 王秋丽. 世界三次大规模密码算法评选活动介绍 [J]. 信息安全与通信保密, 2004(2):76-78.
[7] Network of excellence in cryptology [EB/OL]. http://www.ecrypt.eu.org.
[8] WANG Xiaoyun, FENG Dengguo, LAI Xuejia, et al. Collisions for Hash functions MD4, MD5, HAVAL-128 and RIPEMD [C]//Proceedings of Crypto'04, Aug 15-19,2004, Santa Barbara, CA,USA. Berlin,Germany: Springer-Verlag,2004.
[9] WANG Xiaoyun, YIN Yiqun, YU Hongbo. Finding collisions in the full SHA-1 [C]// Proceedings of Crypto'05, Aug 14-18,2005, Santa Barbara, CA,USA. Berlin, Germany: Springer-Verlag.2005.
[10] WANG Xiaoyun, YU Hongbo. How to break MD5 and other Hash functions [C]//Proceedings of  crypto’05, Aug 14-18,2005, Santa Barbara, CA,USA. Berlin, Germany: Springer-Verlag.2005.
[11] SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer [J]. SIAM Journal on Computing, 1997,26(5):1484-1509.
[12] SHAMIR A. Identity-based cryptosystems and signature schemes [C]//Proceedings of CRYPTO '84, Aug 19-22,1984,Santa Barbara, CA,USA. Berlin, Germany: Springer-Verlag, 1984:47-53.
[13] BONEH D, FRANKLIN M. Identity-based encryption from the weil pairing [C]//Proceedings of CRYPTO’01, Aug, 19-23, 2001, Santa Barbara, CA,USA. Berlin, Germany: Springer-Verlag, 2001:213-229.

收稿日期：2007-07-17

[摘要] 密码技术是信息安全的核心技术。密码技术主要包括对称密码算法和非对称密码算法及协议。对称加密算法加密密钥和解密密钥相互推导容易，加/解密速度非常快，适用于大批量数据加密的场合。非对称密钥密码体制从私有密钥推导公开密钥是计算不可行的，虽然公钥加密算法在运行速度方面无法和对称加密算法媲美，但很好地解决了对称密码学面临的密钥的分发与管理问题，同时对于数字签名问题也给出了完美的解答。

[关键词] 分组密码；流密码；Hash函数；非对称密码；密码协议

[Abstract] Technologies of cryptography are the core of information security. It mainly includes symmetric encryption algorithms and asymmetric cryptographic algorithms and protocols. For the symmetric encryption algorithm, it is easy to deduce decryption keys from the encryption keys and vice versa. Because this algorithm encrypts and decrypts data very quickly, it is applicable in situations where large numbers of data have to be protected. However, for the asymmetric algorithm, extracting the secret key from the public key is computationally infeasible. Although the performance speed of asymmetric encryption algorithm is much slower than that of the symmetric algorithm, the asymmetric algorithm has key management advantages over the symmetric one, and it generates signature of digital messages.

[Keywords] block cipher; stream cipher; Hash function; asymmetric cryptography; cryptographic protocol