密码学的发展.docx

《密码学的发展.docx》由会员分享，可在线阅读，更多相关《密码学的发展.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、献融7%姆学院课程论文题 目 密码学的发展院系计算机系专业网络工程学生姓名XXX学 号指导教师朱节中职 称 副教授二 0一二年五月二十四日密码学的发展XXX南京信息工程大学滨江学院网络工程专业，南京210044摘要：密码技术是信息安全的核心技术。如今，计算机网络环境下信息的保密性、完整性、可用性和抗抵赖性，都需要采用密码技术来解决。密码体制大体分为对称密码（又称为私钥密码）和非对称密码（又称为公钥密码）两 种。公钥密码在信息安全中担负起密钥商议、数字签名、消息认证等重要角色，已成为最核心的密码。关键词：密码；信息安全；密码学的发展；加密技术1引言密码学是一个即古老又新兴的学科。破译者一书说：“

2、人类使用密码的历史几乎与使用文字的时间 一样长。”因为自从有了文字以来，人们为了某种需要总是想法设法隐藏某些信息，以起到保证信息安全的 目的。人们最早为了确保通信的机密，通过一些图形或者象形文字相互传达信息。又如我国古代的烽火就是 一种传递军情的方法。古代的“兵符”就是用来传达信息的密令。连闯荡江湖的侠土和被压迫起义者都各 自有一套秘密的黑道行话和地下联络的暗语。2密码学的发展2.1古典密码学密码学发展的最初阶段称之为古典密码学。早期的密码体制创始人之一是朱丽叶斯凯撒。假设他要发送如下明文信息：gaul is divided into three parts。但他不想让布鲁吐斯（Brutus）

3、读到它，于是将每一个字母向后移三位，这样密文就成为:J D X OLVGLYLGHGLQWRWKUHHSDUW V。解密的过程就是将字母移回三位即可（尽量判断怎 样将空格还原）。通过这个例子看到移位密码不能很好地适应特殊环境，并且它的抗破译性也不强壮。对此 进行改进得到仿射密码，设两个整数。和B，及gcd（。，26）=1,考虑这样的函数x | -ox+B （mod 26）。假设 。=9和3=2,可得出9x+2,取一个明文字母如h（=7）,它加密成9*7+2三65三13 （mod 26）,就是字母N。使用 同样的函数我们得到affineCVVWPM。穷尽搜索覆盖所有312个密钥，显然该方法比同样

4、方法的移位密码花费的时间长，但在计算机中计算起来非常却容易。各种各样的移位密码是在16世纪发明的，但它们大多数 于自于Vigen3re方法,直到20世纪，这种加密体制在不少地方被认为是安全的,虽然19世纪，Babbage和 Kasiski就已展示了如何攻击它们。1920年Friedman开辟了此外一些加密方法，打破了VigenGre及其相关的密码方法。这个加密的密钥是 一个向量，按如下方式来选择。首先，确定一个密钥长度，如6,然后从025个整数中选择元素满足这个长度 的向量，如k=（21, 4, 2, 19, 14, 17）。通常情况下密钥所对应的单词是很容易记忆的，称这个单词为向量。系统 的

5、安全所在就是既不能知道密钥内容也不能知其长度。下面举的例子利用k来加密信息，首先，取明文的第1 个字母并将之移21位,然后将第2个字母移4位,第3个字母移2位等等，一旦到了密钥的末尾,又从头开始,这 样第7个字母又移21位,第8个字母移4位等等,加密过程的密码流程表如下：（明文）h erelsho wit works（密钥）21 4 2 19 14 17 21 4 7 2 19 14 17 21 4 2 19（密文）C T T X W J C S Y B H N J V M L世界上最早的一种密码产生于公元前两世纪。是由一位希腊人提出的，人们称之为棋盘密码，原因为该密码将26个字母放在5X5的

6、方格里，i, j放在一个格子里，具体情况如下表所示：123451abcde2fgh 1Jk31mn0P4qrstu5VwXyz这样，每一个字母就对应了由两个数构成的字符,。是该字母所 在行 的标号，B是列标号。如c对应13, s对应43等。如果接收到密文为：43 15 13 45 42 15 32 15 43 43 11 22 15 则对应的明文即为secure message。另一种具有代表性的密码是凯撒密码。它是将英文字母向前推移k位。如k=5,则密文字母与明文与如下对应关系：abode fghi jklmnopqrstuvwxyz FGHIJKLMNOPQRSTUVWXYZABCDE于是

7、对应于明文secure message,可得密文为XJHZWJRJXXFLJo此时，k就是密钥。为了传送方便， 可以将26个字母一一对应于从0至IJ 25的26个整数。如a对1, b对2,，y对25, z对0。这样凯撒 加密变换实际就是一个同余式：c=m+k mod 26其中m是明文字母对应的数，c是与明文对应的密文的数。随后，为了提高凯撒密码的安全性，人们对凯撒密码进行了改进。选取k,b作为两个参数，其中要求 k与26互素，明文与密文的对应规则为：c = km+b mod 26可以看出，k=l就是前面提到的凯撒密码。于是这种加密变换是凯撒野加密变换的推广，并且其保密 程度也比凯撒密码高。以上

8、介绍的密码体制都属于单表置换。意思是一个明文字母对应的密文字母是确定的。根据这个特点， 利用频率分析可以对这样的密码体制进行有效的攻击。方法是在大量的书籍、报刊和文章中，统计各个字 母浮现的频率。例如，e浮现的次数最多，其次是t, a, o, I等等。破译者通过对密文中各字母浮现频率的 分析，结合自然语言的字母频率特征，就可以将该密码体制破译。鉴于单表置换密码体制具有这样的攻击弱点，人们自然就会想办法对其进行改进，来弥补这个弱点， 增加抗攻击能力。法国密码学家维吉尼亚于1586年提出一个种多表式密码，即一个明文字母可以表示成 多个密文字母。其原理是这样的：给出密钥K=klk2?-kLn,若明文

9、为则对应的 密文为 C=clc2-cn o 其中 Ci = (mi+ki) mod 26。例如,若明文 M 为 data security,密钥 k=best, 将明文分解为长为4的序列data security,对每4个字母，用k二best加密后得密文为：C=EELT TIUN SMLR从中可以看出，当K为一个字母时，就是凯撒密码。而且容易看出，K越长，保密程度就越高。显然 这样的密码体制比单表置换密码体制具有更强的抗攻击能力，而且其加密、解密均可用所谓的维吉尼亚方 阵来进行，从而在操作上简单易行。该密码可用所谓的维吉尼亚方阵来进行，从而在操作上简单易行。该 密码曾经被认为是三百年内破译不了

10、的密码，于是这种密码在今天仍被使用着。古典密码的发展已有悠久的历史了。尽管这些密码大都比较简单，但它在今天仍有其参考价值。最流行的密码体制之一是替换密码，国外时常使用在周末报纸的难题版块中。它的原理很简单：用置换 字母表来代替明文中的字母。大家都“知道”替换密码通过频率计算是可以被破解的，但是这个过程比人们 想象的要复杂的多。2. 2近代密码学1834年，伦敦大家的实验物理学教授惠斯顿发明了机电，这是通信向机械化、电气化跃进的开始，也 是密码通信能够采用在线加密技术提供了前提条件。前面已经讲过，密码技术的成果首先被用于战争，下 面的例子就是一个明证。1914年第一次世界大战爆发，德俄相互宣战。

11、在交战过程中，德军破译了俄军第 一军经给第二军的电文，从中得知，第一军的给养已经中断。根据这一重要情报，德军在这次战役中取得 了全胜。这说明当时交战双方已开展了密码战，又说明战争刺激了密码的发展。1920年，美国电报电话公司的弗纳姆发明了弗纳姆密码。共原理是利用电传打字机的五单位码与密钥字母进行模2相加。如若信息码(明文)为11010,密钥码为11101,则模2相加得00加1即为密文码。接收 时，将密文码再与密钥码模2相加得信息码(明文)HOlOo这种密码结构在今天看起来非常简单，但由于这种密码体制第一次使加密由原来的手工操作进入到由电子电路来实现，而月.加密和解密可以直接由机 器来实现，于是

12、在近代密码学发展史上占有重要地位。随后，美国人摩波卡金在这种密码基础上设计出一 种一次一密体制。该体制当通信业务很大时，所需的密钥量太过庞大，给实际应用带来不少艰难。之后， 这种一次一密制又有了进一步改进，但历史事实证明，这种密码体制是不安全的，在太平洋战争中日本使 用的九七式机械密码就属于这一种。1940年，美国陆军通信机关破译了这种密码。在中途岛海战中，日本 海军大将山本五十六因密码电报被美国截获破译而被击毙在飞机上。2. 3现代密码学移位、仿射和替换密码，密文中给定的一个字母恰好都来自于明文中的同一个字母，这通过频率分析容 易发现密钥。而现代密码体制的不少方法都发源自分组密码的范畴，如D

13、ES方法是基于64比特的分组,AES 使用128比特的分组,RSA使用几百比特长的分组。所有这些分组的长度都足够长，能有效地防止类似频率 分析这样的攻击。分组密码的标准方法就是独立地、一次性地把明文中的一块分组转换成密文的一块分组, 这叫做电子电报密码本模式，有一种方式是使用后续明文分组的加密分组，从密文的分组中再使用反馈机 制,这就导致了密文分组的连锁模式和密文反馈操作模式。2. 3. 1 DES算法1973年美国国家标准局(NBS)发布了一个公开请求，寻觅一个加密算法使之成为国家标准。IBM在1974 年提出了一个算法叫LUCIFER, NBS后来将该算法提交给国家安全代理机构，它们重新审

14、阅并对算法做了一 些修改，提出来了一个版本，就是最初的数据加密标准(DES)算法。1975年公开了DES,即可以自由地使用它， 并于1977年将它作为政府数据加密标准。DES广泛地使用在电子商务中，它具有快速和安全的优点。DES持续 了相当长的时间才过时JES的一组密文由64位组成，密钥是56位但它是用64位的字串表示的。第8位，每16 位，第24位，是奇偶位，这样的安排是为了使每8位一组中都有一个奇数1,这是出于错误检测的目的，加密 的输出是64的密文。在DES算法中初始用64位的明文m表示,主要有三步：(l)m的各位置通过初始变换改变其罗列顺序得到m =IP(m),记为m二L R , L是

15、m的前32位,R是in的后32 000 00000位。对1 W i W 16,执行如下操作:L =R * R =L f(R ,K ),i i-1 i i-1i-1 iKi是来自于密钥K,称为“轮密钥”，它是56比特输入密钥的一个48比特的子串。f是函数，称为“S盒 函数”，是一个代换数码。这一步是代换密码和换位密码的结合，目的是获得很大程度的“信息扩散”。(3)摆布交换得到R L ,然后执行初始变换的逆变换，得到密文c=IPt (R L )。解密过程与加密过程彻底 16 1616 16相同，只是按密钥K，K相反的顺序而已。1 16DES的核心部份是在“S盒函数”里，在这里DES实现了明文消息在

16、密文消息空间上的随机非线性分布。2 . 3. 2 AES算法1997年，国际标准与技术研究机构寻觅DES的替代品，1998年加密委员会对15种候选算法进行评定，最终 Rijndael被选为高级加密标准。Ri jndael (AES)算法合用于128、192和256位的密钥长度。对于不同的密钥长 度循环加密的轮数不同。下面以128位密钥来讨论AES算法，它由10轮循环组成,每一轮循环都有一个循环密 钥，它来自于初始密钥。这里有一个第0轮循环密钥，这就是初始密钥。128比特的消息(明文，密文)分组被分 成16个字节(一个字节是8比特)，表示成一个4X4矩阵,称为状态矩阵。每一循环由4个基本步骤组成

17、，称为 层：(1)字节转换:这是一非线性的字节代替过程，它在状态矩阵的每一个分量(字节)上独立的进行运算。 目的是防止身份和线性密码体制的攻击。（2）行移位变换:状态矩阵中的每一行将以字节为单位循环右移不同的位移量。这一步是线性组合，多 轮循环可以导致各个位间的扩散。（3）列混合变换：把每列视作有限域GF（2。上的（四项）多项式。每一列所表示的多项式将乘以一个固定 的多项式a（x）并将所得的结果模x，+l0与行变换的目的是相同的。（4）循环密钥加法:用简单的比特异或者将循环密钥与状态进行模2加。AES的解密过程使用了四种变换的逆变换，以相反顺序对由密文映射得到状态矩阵进行变换完成。从目前来看,

18、AES尚无已知的安全性方面的攻击AES的密钥长度为可变的，当进行穷举密钥攻击时，穷 举密钥的期望尝试次数与密码密钥的长度有关，相比之下AES算法比DES算法保密强度更高。2. 3. 3公钥密码体制前面讨论的密码系统称之为私钥密码系统，它是以通信双方在进行保密通信之前需要通过安全通道传 送密钥为前提的，而这在实际中是非常艰难的，公钥密码系统可使通信双方无须事先传送密钥就可以建立 保密通信，解决了私钥密码系统的密钥分配问题。公钥密码的观点是Diffie和Hellman于1976年在“密码学 的新方向”一文中首次提出的。指明了某些已知的数学难解问题上建立密码的具体途径。随后 Rivest, Sham

19、ir和Adleman于1977年提出了第一个比较完善的RSA公钥密码系统。这三位科学家荣获2002年 度图灵奖，以表彰他们在算法方面的突出贡献。比较著名的公钥密码原型有Diffie-Hellman密钥交换协议、 Rabin密码体制、ElGamal密码体制等。与对称密钥密码体制相比，公开密钥密码体制具有以下几个特点：密 钥分发简单、每一个用户秘密保存的密钥量减少、能够满足互不相识的用户之间进行保密通信的要求、能够 完 成数字签名。在公钥密码系统中每一个实体都有自己的公钥和相应的私钥。在安全系统中已知公钥推 算出私 钥在计算上是艰难的。2. 3. 3.1 RSA公钥加密算法RSA公钥加密算法是19

20、77年由RonRivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开辟的。 RSA取名来自开辟他们三者的名字RSA是旦蓟最有影响力的公钥加密算法，它能够反抗到目前为止已知的 所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数 相乘十分容易，但那时想要对其乘积进行因式分解却极其艰难，因此可以将乘积公开作为加密密钥。RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由 已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而

21、解密密钥（即秘密密钥）SK是需 要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据 PK计算出SK。正是基于这种理论，1978年浮现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之 一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密 强度，RSA密钥至少为500位长，普通推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送 信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或者IDEA对话密 钥 加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息

22、后，用不同的密钥解密并可核对信 息摘要。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公 钥算法，从提出到现在的三十多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀 的公钥方案之一。RSA是基于大整数分解的公开密钥密码体制，大整数分解是计算上艰难的问题，目前还不存在普通有效 解决算法。目前较好的大整数分解算法包括：二次筛选法、椭圆曲线法、Pollard的蒙特卡罗算法、数域筛选 法等。最好的分解算法是数域筛选法，假设大整数为一个200位十进制数，即使以每秒107次运算的高速电子 计算机进行因子分解，也要IO年。简单描述一下RSA的工

23、作原理：每一个实体有自己的公钥（n,e）及私钥p, q, d,其中p, q是两个大 素数,n邛 q, e d = lmod (p (n),显然e应该满足gcd(e, (p (n)二1。实体助口密消息m,将密文在公开信道上传送 给实体A。实体A接到密文后对其解密。实体的加密算法操作：(1)得到实体A的真实公钥(n,e);(2)把消息表示成整数叫0 W m W n-l;(3)使用平方一乘积算法，计算OEk (m)二叫mod n;(4)将密文C发送给实体A。实体A的解密算法操作：实体A接收到密文C,使用自己的私钥d计算m=D (C)=C mod n, me Zn0 kd2. 3. 3. 2 ElGa

24、mal 算法El Gamal为目前著名的公钥密码系统之一，是由ElGamal于1985年提出的。ElGamal密码系统可用于 加解密、数字签名等，其安全性是建立于离散数学问题，即给定g, P与尸gHiod p,求x为计算上不可行。密钥对产生办法，首先选择一个素数P，两个随机数，g和X, g, X p,计算y = gx ( mod p ), 则其公钥为y、g和p,私钥是x, g和p可由一组用户共享。ElGamal用于数字签名。被签信息为M,首先选择一个随机数k, k与p - 1互质，计算：a = gk ( mod p )再用扩展Euclidean算法对下面方程求解b： M=xa + kb ( m

25、od p - 1 )签名就是(a, b )o随机数k须丢弃。验证时要验证下式：ya * ab ( mod p ) = gM ( mod p )同时一定要检验是否满足a po否则签名容易伪造。ElGamal用于加密。被加密信息为M,首先选择一个随机数k, k与p -1互质，计算：a二gk ( mod p ) b=yk M ( mod p )( a, b )为密文，是明文的两倍长。解密时计算：M = b / ax ( mod p )ElGamal签名的安全性依赖于乘法群(IFp)*上的离散对数计算。素数p必须足够大，且pT至少包含 一个大素数。因子以反抗Pohlig & Hellman算法的攻击。

26、M普通都应采用信息的HASH值(如SHA算法)。ElGamal 的安全性主要依赖于P和g,若选取不当则签名容易伪造，应保证g对于pT的大素数因子不可约。 D. Bleichenbache uGeneratingElGamal Signatures Without Knowing the Secret Key” 中提至U了些攻 击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。2. 3. 3. 3锥曲线密码学圆锥曲线密码学是1998年由曹珍富教授首次提出。C. Schnorr认为,除椭圆曲线密码以外这是人们最 感兴趣的密码算法。在圆锥曲线群上的各项计算比椭圆曲线群上的更简单，特别是在

27、其上的编码和解码都 很容易被执行。同时,还可以建立模n的圆锥曲线群，构造等价于大整数分解的密码。 本文首先分别介绍了 基于有限域Fp上的圆锥曲线C p(a,b)和基于环Z n上的圆锥曲线C n( a , b )的定义和性质。重点对基于 环Z n上的圆锥曲线的性质进行了较为深入的讨论,证明了C n( a , b )对于其上定义的运算构成有限交 换群，并给出了一种计算C n( a , b )上某些圆锥曲线基点的算法。 在深入研究的基础上，将公钥密码的 一些加密和签名算法应用于环Z n上的圆锥曲线，提出了基于环Z n上圆锥曲线的Diffie-Hellman密钥交换 算法、ElGamal数字签名方案和

28、多重数字签名方案。这些方案的安全性都是基于大数分解的艰难性和有限 群上计算离散对数的艰难性。 最后，从明文嵌入和阶的运算两方面比较了椭圆曲线密码和圆锥曲线密码, 说明圆锥曲线密码具有明文嵌入方便、阶的运算容易的优点。2. 3.4新的研究领域虽然公钥密码体制具有私钥密码体制不可比拟的优点，但因其运算量太大,加解密迅速远远落后于私 钥密码体制，因此公钥密码体制多用于传递密钥、签名等少量信息的加密上，大量信息的加密还是使用私钥 密码体制。为扩展公钥密码体制的应用范围，现在所做的研究一方面是修改当前密码算法，提高运算速度。 笔者在这方面也做了一些研究，改进了典型的RSA的基于椭圆曲线离散对数点乘的算法

29、，使其运算速度提 高了40%,但仍与私钥加密速度有很大差距。另一方面是量子密码学的引入，现在光纤电缆上创建密钥已有 了实验室模型。量子计算机的构想从根本改革传统计算机的处理信息方式，大幅度地提高了运算能力，现还 未能实现。虽量子密码是一种绝对安全的密码技术，但走向实用还有许多难题要解决。这些都将是未来密码 技术研究的重要内容。3总结密码学作为保护信息的手段，它最早应用在军事和外交领域，随着科技的发展逐渐进入人们的生活中。 现在世界各国对密码的研究高度重视，已发展到了现代密码学时期。密码学成为结合物理、量子力学、电 子学、语言学等多个专业的综合科学，浮现了如“量子密码”、“混沌密码”等先进理论，

30、在信息安全中起 着十分重要的角色。当前，密码学发展面临着挑战和机遇。计算机网络通信技术的发展和信息时代的到来， 给密码学提供了前所未有的发展机遇。在密码理论、密码技术、密码保障、密码管理等方面进行创造性思 维，去开辟密码学发展的新纪元才是我们的追求！参考文献：1王继林，伍前红等译,现代密码学理论与实践.电子工业出版社.2004.2冯登国译.密码学原理与实践.电子工业出版社.2003.3W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. Info. Theory. 1976.4王衍波，薛通.应用密码学.机械工业出版社.2003.