密码学理论概述

hwj3

1．引言
目前，密码已经从外交和军事领域走向公开，且已发展成为一门结合数学、计算机科学、电子与通信、微电子等技术的交叉学科。使用密码技术不仅可以保证信息的机密性，而且可以保证信息的完整性和确定性，防止信息被篡改、伪造和假冒。密码技术是信息安全技术的核心，它主要由密码编码技术和密码分析技术两个分支组成。密码编码技术的主要任务是寻求产生安全性高的有效密码算法和协议 ,以满足对数据和信息进行加密或认证的要求。密码分析技术的主要任务是破译密码或伪造认证信息 ,实现窃取机密信息或进行诈骗破坏活动。这两个分支既相互对立又相互依存 ,正是由于这种对立统一关系 ,才推动了密码学自身的发展密码理论与技术目前主要有两大体制 ,即公钥密码与单钥密码（对称密码）。其中，单钥密码又可以分为分组密码和序列密码。





2．公钥密码
1976年，Whitfield Diffie和Martin Hellman发表了“New directions in cryptography”，这篇划时代的文章奠定了公钥密码系统的基础。公钥密码系统的概念在密码学的发展史上具有划时代意义。公钥密码算法又称非对称密钥算法、双钥密码算法。在公钥密码算法中，Kp≠Ks，Kp可以公开，简称公钥；Ks必须保密，简称私钥。从Ks可以很容易推出Kp，但从Kp很难推出Ks。公钥密码算法的这种单向特性是基于陷门单向函数实现的。我们说一个函数ｆ是单向函数 ,若对它的定义域中的任意ｘ都易于计算ｆ(ｘ)，而对ｆ的值域中的几乎所有的ｙ，即使当ｆ为已知时，要计算f (ｙ)在计算上也是不可行的。若当给定某些辅助信息(陷门信息 )时易于计算f (ｙ)，就称单向函数ｆ是一个陷门单向函数。目前只有两种类型的公钥系统是安全实用的，即基于大整数困难分解问题的密码体制和基于离散对数困难问题的密码体制。还有一些其它公开的密钥密码体制，如Goldwasser-Micali概率公开密钥系统，Mekle-Hellman背包公钥密码体制，有限自动机公钥密码体制，基于纠错码的公钥体制，基于辫群的密码体制、NTRU、量子密码体制等。

2.1基于大整数困难分解问题的密码体制
自1976年提出公钥密码体制思想后，基于大整数困难分解问题的公钥密码体制有RSA, Rabin体制，LUC体制及其推广，二次剩余体制等。
RSA体制最初是由美国麻理工的Riverst，Shamir和Adleman于1978年提出的。它基于一个非常简单的数论思想，但能抵抗所有的密码攻击。其思想是对如下事实的应用：很容易将两个素数乘起来，但分解该乘积却非常困难。从而，该乘积可以公开而且可以作为加密公钥。不能从该乘积恢复这两个素数。另一方面，解密需要这些素数。RSA的具体算法可参考相关文献。目前，由于分解大整数的能力增强，建议使用1024的模长，未来十几年里可能要选择2048模长。但由此带来的是系统更复杂，速度更慢。对于RSA密码体制，n被分解成功，该体制便被破译。即破译RSA的难度不超过大整数的分解。但不能证明破译RSA和分解大整数是等价的。这样作为对RSA体制的一种修正，M.O.Rabin于1979年提出了一种变形的RSA算法，称之为Rabin算法，可证明它的安全性等价于大整数因子分解问题。
目前RSA体制已经作为一种标准被广泛使用，比如现流行的PGP就是将RSA作为传送会话密钥和数字签名的标准算法。由于RSA体制比较简单和成熟，很多公司和研究团的都对此做了实现。如RSA公司的RsAref，IBM公司的CCA等。

2.2基于离散对数困难问题的密码体制
基于离散对数困难问题的密码体制主要包括基于有限域的乘法群上的离散对数问题的ElGamal体制和基于椭圆曲线离散对数的椭圆曲线密码体制（ECC），以及近来Lenstra等人提出的XTR群的离散对数问题的XTR公钥体制。
ElGamal公钥密码系统是T.ElGam于1984年提出的，它的安全性主要基于离散对数问题的困难性。离散对数问题：p是素数， 是Z 的本原元素， ，求唯一的整数 ，0 ，使得 。记整数 为log  .。小心地选择素数p，对于离散对数问题目前还没有多项式时间算法。因此，人们认为离散对数问题是困难问题。目前该公钥密钥系统使用在许多协议之中。
前文已经说过，为保证RSA算法的安全性，RSA的密钥长度需要一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制（ECC）可用短得多密钥获得同样的安全性。该体制，由Koblitz和Miller于20世纪80年代中期分别提出。ECC的安全性只与椭圆曲线本身有关系，基于椭圆的离散对数问题比一般的基于整数的离散对数问题和整数分解问题更加困难。ECC由于其自身的安全性高，密钥量小，较好的灵活性，得以广泛应用。目前，ECC已经被IEEE公钥密码标准P1363采用。
作为椭圆曲线的一个推广，Neal Koblitz在1989年提出了超椭圆曲线密码体制（HCC），它是基于有限域上超椭圆曲线的Jacobian群上的离散对数问题的计算困难性。HCC具有与ECC相似的密码特性，但HCC具有在比较小的基域上提高与ECC同级别的安全性的优势。从已有的HCC实现来看，HCC实现速度要比ECC要慢。由于HCC的实现的复杂度较大，因此它还不实用。
XTR公钥体制，即有效的紧致子群迹表示，由Lenstra在Crypto2000提出。它是一种传统的基于子群离散对数问题的密码体系。XTR是一种非常具有吸引力的公钥密码体制，与目前实用的RSA,ECC相比，同等安全程度的XTR的体制实现在计算、密钥存储和通信方面的要求和ECC基本相同，但XTR的密钥生成要比ECC快得多。当然，如何进一步改善XTR算法,优化参数选取，使XTR走向实用需要进一步的工作。

2.3其它一些公钥密码体制
纠错码和密码学是两门不同的学科。但是公钥密码体制思想是建立在一个难解的数学问题之上，即NPC问题。1978年，Berlekamp等人证明了纠错码中的一些译码问题属于NPC问题。这两项成果建立起纠错码和密码学相结合的理论基础。同年， McEliece设计出第一个基于纠错码的公钥密码体制。被称作McEliece公钥密码体制。目前，关于该密码体制的破解尚未有公开证据进行证明。
有限自动机公钥密码体制是由我国学者陶仁骥发明的，它的思想与RSA体制类似。此类体制是基于分解两个有限自动机的合成也是困难的而构造的，尤其是当其中的一个或两个为非线性时，难度更大。目前，陶仁骥已经公开了三个算法。分别为FAPKC0，FAPKC1和FAPKC2，后者比较复杂，研究出来用以支持基于身份鉴别的操作。
此外，还有基于辫群的密码体制、NTRU、量子密码体制，格密码等。




3．分组密码
所谓分组密码，通俗地说就是数据在密钥的作用下，一组一组、等长地被处理，且通常情况下是明、密文等长。这样做的好处是处理速度快，节约了存储，避免了浪费带宽。分组密码是许多密码组件的基础，比如很容易转化为流密码（序列密码）、Hash函数。分组密码的另一个特点是容易标准化，由于其固有的特点（高强度、高速率、便于软硬件实现）而成为标准化进程的首先体制。但该算法存在一个比较大的缺陷是安全性很难被证明。尽管“可证明安全性”的研究发展很快，目前的分组密码大多看起来也安全，可是还没有一个著名分组密码是真正被证明安全的，至多证明了局部安全性。有人为了统一安全性的概念，引入了伪随机性和超伪随机性，它是用概率图灵机来描述的，但在实际设计和分析中很难应用。关于分组密码的算法，有早期的DES密码到现在的AES(目前选定为Rijndael算法),还有其它一些分组密码算法，如IDEA,RC5,RC6,Camellia算法等。

3.1典型的分组密码算法——DES算法
美国国家标准局（NBS）于1977年公布了由IBM公司研制的一种DES算法，该算法是早期的称作Lucifer密码的一种发展和修改。它的分组长度为64比特，密钥长度为56比特。由于其密钥太短，其安全性受到严重挑战。事实上，通过穷尽密钥搜索攻击和差分攻击，已经造成DES算法的安全性不再受到信任。因此，产生了许多DES的变形算法，比如二重DES和三重DES，其相应的复杂性也高了许多。2000年，AES算法的最终确定使DES基本上完成了自己的历史使命。

3.2高级加密标准（AES）——Rijndael算法
等鉴于DES得没落，美国政界和商界一直在寻求高强度、高效率的替代算法。1997年，美国国家标准技术研究所（NIST）为了履行其法定职责，发起了一场推选用于保护敏感的联邦信息的对称密钥算法的活动。1998年，NIST宣布接受了15个候选算法并提请全世界密码学界协助分析这些候选算法。NIST通过初步考察，1999年选定MARS、RC6、Rijndael、Serpent、Twofish五个算法作为决赛的算法。最终由比利时的密码专家Joan Danmen和Vincent Rijmen开发的Rijndael算法决出胜利。
当前的大多数分组密码，其轮函数有Feistel结构或准Feistel结构，即将中间状态的部分比特不加改变地简单转置到其它地位置。Rijndael没有这种结构，其轮函数是由三个不同的可逆一致变换组成的，称它们为三个“层”。不同层的特定选择大部分是建立在宽轨迹策略的应用基础上，而该策略就是提供抗线性密码分析和差分密码分析能力的一种设计。

3.3其它一些分组密码算法
国际上目前公开的分组密码不下100种。比如DES的变形（包括New DES、多重DES、白化了的DES、S-盒可变的DES、广义DES等），IDEA算法，RC系列分组密码（包括RC2,RC5,RC6等），Lucifer，Madeyga，Feal-N，LOKI系列分组密码（包括LOKI89，LOKI91，LOKI97等），CAST系列算法，Khufu，Safe系列，3-WAY、TEA、MacGuffin、SHARK、BEAR、LION、Blowfish、GOST、SQUARE、MISTY，以及日本电报电话公司和三菱电子公司联合设计的Camellia密码等等。






4．序列密码
序列密码虽然主要用于政府、军方等国家要害部门，而且用于这些部门的理论和技术都是保密的，但由于一些数学工具（比如代数、数论、概率等）可用于研究序列密码，其理论和技术相对而言比较成熟。序列密码的基本思想：加密的过程是明文数据与密钥流进行叠加，同时解密过程就是密钥流与密文的叠加。该理论的核心就是就是对密钥流的构造与分析。因此，序列密码学在一些文献中被称做流密码。流密码与分组密码的区别就在于有无记忆性。对于流密码来说，内部存在记忆元件（存储器）。根据加密器中记忆元件的存储状态是否依赖于输入的明文序列，又分为同步流密码和自同步流密码。目前大多数的研究成果都是关于同步流密码的。
同步流密码的关键是密钥流产生器，要求密钥流具有良好的随机性。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样地序列是不可能做到随机的，只能要求截获比周期段地密钥流不会泄漏更多信息，这样的序列叫伪随机序列。伪随机序列的生成通常是将m-序列作为驱动序列进行适当的变换或组合，即保留m-序列的良好伪随机性，又大幅提高线性复杂度。
在序列密码的设计方法方面，人们将设计序列密码的方法归纳为四种，即系统论方法、复杂性理论方法、信息论方法和随机化方法；将同步流密码的密钥流生成器分解成驱动部分和非线性组合部分，驱动部分负责生成器的状态转移，并未非线性组合部分提供统计性能良好的序列，而非线性部分要利用这些序列组合出满足要求的密钥流序列，这样做不仅结构简单，而且便于从理论上分析这类生成器；提出了非线性组合生成器、非线性滤波生成器和钟控生成器等多种具体设计方法。在研究方法方面，将谱技术、概率统计方法、纠错编码技术、并元理论，有限域理论等均可有效地用于序列密码的研究。

序列密码不象分组密码那样有公开的国际标准，虽然世界各国都在研究和应用序列密码，但大多数设计、分析成果还都是保密的。下面介绍几种序列密码，如由法国人设计，在欧洲GSM中广泛使用的A5算法，该算法主要用于从用户手机到基站（CS）的连接加密；英国的Rambutan；1987年 RonRivest为RSA数据安全公司设计的RC4序列密码，该算法广泛用于商业密码产品中；IBM公司Phil Rogaway和Don Coppersmith设计的SEAL密码。

lwx1982

很不错谢谢

hwj3

谢谢
这是我去年写的论文手稿中的部分内容，希望对大家有益，对所谓的密码这块有个了解。