信息加密与密码分析.ppt

信息加密与密码分析,内容提要 密码学的基本概念，加密类型，混合加密方法以及消息一致性 密码学应用，密码分析与攻击 加密领域中两种主流加密技术： des加密（data encryption standard） rsa加密（rivest-shamir-adleman） 加密工具pgp（pretty good privacy）,2.1密码学概述,密码学是一门古老而深奥的学科，对一般人来说是非常陌生的。长期以来，只在很小的范围内使用，如军事、外交、情报等部门。计算机密码学是研究计算机信息加密、解密及其变换的科学，是数学和计算机的交叉学科，也是一门新兴的学科。随着计算机网络和计算机通信技术的发展，计算机密码学得到前所未有的重视并迅速普及和发展起来。,2.1.1密码学的发展,密码学的历史比较悠久。在四千年前，古埃及人就开始使用密码来保密传递消息。两千多年前，罗马国王julius caesar（恺撒）就开始使用目前称为“恺撒密码”的密码系统。但是密码技术直到20世纪40年代以后才有重大突破和发展。特别是20世纪70年代后期，由于计算机、电子通信的广泛使用，现代密码学得到了空前的发展。 密码学相关科学大致可以分为3个方面：密码学（cryptology）是研究信息系统安全保密的科学，密码编码学（cryptography）主要研究对信息进行编码，实现对信息的隐藏。密码分析学（cryptanalytics）主要研究加密消息的破译或消息的伪造。,密码学的发展大致经过3个阶段（ 略 ） 第一阶段是1949年之前，密码学是一门艺术，这阶段的研究特点是： 1. 密码学还不是科学，而是艺术 2. 出现一些密码算法和加密设备 3. 密码算法的基本手段出现，主要针对字符 4. 简单的密码分析手段出现，数据的安全基于算法的保密。 该阶段具有代表性的事件是：1883年kerchoffs第一次明确的提出了编码的原则： 加密算法应建立在算法的公开且不影响明文和密钥的安全的基础上。这个原则得到广泛承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。 第二阶段是1949-1975年，密码学成为一门独立的科学，该阶段计算机的出现使基于复杂计算的密码成为可能。主要研究特点是：数据安全基于密钥而不是算法的保密。,第三阶段是1976年以后，密码学中公钥密码学成为主要研究方向，该阶段具有代表性的事件是： 1976年，diffie和hellman提出了不对称密钥。 1977年，rivest等提出了rsa公钥算法。 1977年，des算法出现。 80年代，出现idea和cast等算法。 90年代，对称密钥密码算法进一步成熟，rijndael，rc6等出现，逐步出现椭圆曲线等其他公钥算法。 2001年，rijndael成为des算法的替代者。 2004年8月，山东大学信息安全所所长王小云在国际会议上首次宣布了她及她的研究小组对md5、haval-128、md4和ripemd等四个著名密码算法的破译结果，引起世界轰动。这阶段的主要特点是：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能。,2.1.2 密码技术简介,计算机网络的广泛应用，产生了大量的电子数据，这些电子数据需要传输到网络的许多地方。有意的计算机犯罪和无意的数据破坏对这些数据产生了很大的威胁。国家机密、企业经济信息、银行网上业务等中的任何差错都会使国家安全、企业经营受到巨大的损害。原则上来说对电子数据的攻击有两种形式。 （1）被动攻击。非法从传输信道上截取信息，或从存储载体上偷窃信息。 （2）主动进攻。对传输或存储的数据进行恶意的删除、修改等。 虽然对这些行为已经建立相应的法律，但由于这种犯罪形式的特殊性，对于它的监督、甚至量刑都是很困难的。因此在不断完善相应法律和监督的同时，还需要加强自我保护，密码技术是一种有效而经济的方法。,经典的密码学是关于加密和解密，主要用于保密通信。目前，已经不再是单一的加解密技术，已被有效、系统地用于保证电子数据的保密性、完整性和真实性。 保密性就是对数据进行加密，使非法用户无法读懂数据信息，而合法用户可以应用密钥读取信息。 完整性是对数据完整性的鉴别，以确定数据是否被非法篡改，保证合法用户得到正确、完整的信息。 真实性是数据来源的真实性、数据本身真实性的鉴别，可以保证合法用户不被欺骗。 现代密码技术的应用已经深入到数据处理过程的各个环节，包括：数据加密、密码分析、数字签名、信息鉴别、零知识认证、秘密共享等。 密码学的数学工具也更加广泛，有概率统计、数论、代数、混沌和椭圆曲线等。 密码学专业术语包括：消息和加密、鉴别、完整性和抗抵赖性、算法和密钥、对称算法和非对称算法（公开密钥算法）等等。,2.1.3 消息和加密,加密：可翻译成“encipher” 或“ encrypt”，用某种方法伪装消息以隐藏它的内容的过程， 解密：可翻译成“decipher” 或“decrypt”，把密文转变为明文的过程。 明文：未加密消息， 密文：加了密的消息， 图2-1表明了加密和解密的过程。,明文用m（message,消息）或p（plaintext,明文）表示,它可能是比特流、文本文件、位图、数字化的语音流或者数字化的视频图像等。 密文用c（cipher）表示,也是二进制数据，有时c=m。通过压缩和加密的结合，c=m 。 加密函数e用于m得密文c,数学公式表示为：e（m）=c。 解密函数d用于c产生m,公式表示为：d（c）=m。先加密后再解密消息，原始的明文将恢复出来， d（e（m）=m。 简例 m：90（h）, e:前后换位， d :前后换位， c = e（m）= 09 （h）， d（ c ）= d（e（m）=m 。 ascii 131h ， a41h ， a61h,2.1.4 鉴别、完整性和抗抵赖性,密码学除了提供机密性外，需要提供三方面的功能：鉴别、完整性和抗抵赖性。这些功能是通过计算机进行社会交流至关重要的需求。 （1）鉴别：消息的接收者应该能够确认消息的来源；入侵者不可能伪装成他人。 （2）完整性：消息的接收者应该能够验证在传送过程中消息没有被修改；入侵者不可能用假消息代替合法消息。 （3）抗抵赖性：发送消息者事后不可能虚假地否认他发送的消息。,2.1.5算法和密钥,密码算法也叫密码函数，是用于加密和解密的数学函数。通常有两个相关的函数，分别用加密和解密。（什么情况可以是同一个？） 受限制的算法:算法本身是保密的. 受限制的密码算法不可能进行质量控制或标准化，每个用户组织必须有他们自己的唯一的算法，这样的组织不可能采用流行的硬件或软件产品。但窃听者却可以买到这些流行产品并学习算法，进而破解密码。尽管有这些主要缺陷，受限制的算法对低密级的应用来说还是很流行的。 简例：123434124321 123442314321 算法本身保密 123434122143 现代密码学里：算法公开，密钥不公开（如密码锁、）。,现代密码学用密钥解决了这个问题，密钥用k表示。k可以是很多数值里的任意值，密钥k的可能值的范围叫做密钥空间。加密和解密运算都使用这个密钥，即运算都依赖于密钥，并用k作为下标表示，加解密函数表达为： ek（m）=c, dk（c）=m, dk（ek（m）=m 例：交换是算法，交换对是密钥。 加密、解密过程如图2-2所示。,有些算法使用不同的加密密钥和解密密钥，也就是说加密密钥k1与相应的解密密钥k2不同，在这种情况下，加密和解密必须满足函数表达式为： ek1（m）=c, dk2（c）=m, dk2（ek1（m）=m. 例：mxxxx, k12, e*，则d *，k21/2 如图2-3所示。,2.1.6对称算法,基于密钥的算法通常有两类：对称算法和公开密钥算法。对称算法有时又称为传统密钥算法，加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加解密的密钥是相同的。对称算法要求发送者和接收者在安全通信之前，协商一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加解密。对称算法的加密和解密表示为： ek（m）=c，dk（c）=m 例：mxxxx, k2, e*，则d /，k2 对称算法可分为两类： 序列算法：一次只对明文中的单个比特或者字节进行运算的算法称为序列算法或序列密码。 分组算法或分组密码：对明文的一组比特或字节进行运算。现代计算机密码算法的典型分组长度为64位，这个长度已经足以防止被分析破译。,2.1.7公开密钥算法,公开密钥算法：加密的密钥和解密的密钥不同，而且解密密钥不能根据加密密钥计算出来，或者至少在可以计算的时间内不能计算出来。 加密密钥能够公开，陌生者能用加密密钥加密信息,但只有用相应的解密密钥才能解密信息.加密密钥叫做公开密钥（简称公钥）,解密密钥叫做私人密钥（简称私钥）。 公开密钥k1加密表示为：ek1（m）=c。公开密钥和私人密钥是不同的，用相应的私人密钥k2解密可表示为：dk2（c）=m。 简例：e：* ，k1：1/2，m：x ；则c= ek1（m）= x/2 d: * ， k2：2 ， c： x/2； 则m =dk2（c）= x,2.2 加密类型简介,从古到今有无数种加密方法，但归类起来，古代主要是代替密码、置换密码以及两者的结合. 计算机出现以后的现代密码则分为对称密码和非对称密码，以及分组密码和序列密码。 2.2.1 scytale密码 和 恺撒密码 scytale密码 最先有意识的使用一些技术的方法来加密信息的可能是公元前500年的古希腊人。他们使用的是一根叫scytale的棍子。送信人先绕棍子卷一张纸条，然后把要写的信息打纵写在上面，接着打开纸送给收信人。如果不知道棍子的粗细是不可能解密里面的内容的， 如图2-4所示。 缠棍子是算法， 棍子粗细是密 钥。,(省)曾有这样一件事，斯巴达是古希腊的一个城邦，里面的人以骁勇善战著称。有一天，距城很远的兵营中来了一个专程从斯巴达城赶来送信的奴隶，兵营中有位名叫莱桑德的将军读了信以后，感到很失望，因为信中毫无重要消息，就随手把它扔到一边去了。可是，刹那间，将军锐利的目光好像发现了什么，他立即命令侍卫人员暂时回避，然后对这个奴隶说：“把腰带给我。” 这是一条普通的腰带，只是与通常的略有不同，在腰带周围雕刻着一串字母，看上去毫无意义，大概只是做装饰之用罢了。但当将军把腰带螺旋式地绕在一根棍棒上时，奇迹出现了。显现在棍棒上的字母不再是无意义的了。它告诉将军一个极端重要的消息：斯巴达当时的同盟者波斯人正在搞阴谋，企图谋反夺权；于是将军立即带着他的队伍急速返回斯巴达城，粉碎了这起叛乱。,恺撒密码 公元前50年，恺撒大帝发明了一种密码叫做恺撒密码。在恺撒密码中，每个字母都与其后第三位的字母对应，然后进行替换，比如“a”对应于“d”，“b”对应于“e”，以此类推。如果到了字母表的末尾，就回到开始，例如“z”对应于“c”，“y”对应于“b”，“x”对应于“a”，如此形成一个循环。当时罗马的军队就用恺撒密码进行通信。 恺撒密码明文字母表：a b c d e f g x y z 恺撒密码密文字母表：d e f g h i j a b c 于是就可以从明文得到密文： 比如：明文为“veni，vidi，vici”得到的密文“yhal， ylgl，ylfl”，意思是“我来，我见，我征服”,曾经是恺撒征服本都王法那西斯后向罗马元老院宣告的名言。 26个字符代表字母表的26个字母，从一般意义上说，也可以使用其它字符表，一一对应的数字也不一定要是3，可以选其它数字。 算法和密钥？,2.2.2代替密码和置换密码,从古代密码出现一直到现代计算机诞生，密码学是由基于字符的密码算法构成的。不同的密码算法是字符之间互相代替或者是互相之间换位，好的密码算法是结合这两种方法，每次进行多次计算。 代替密码（substitution cipher)是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。 置换密码(permutation cipher)又称换位密码（transposition cipher)，加密过程中明文的字母保持相同，但顺序被打乱了。,代替密码,在经典密码学中，有4种类型的代替密码（介绍2种）： 1简单代替密码（simple substitution cipher)，又称单字母密码。明文的一个字符用相应的一个密文字符代替。恺撒密码就是一种简单的代替密码，它的每一个明文字母都由其右边第三个字母代替。rot13是建立在unix系统上的简单的加密程序，它也是简单代替密码。在这种密码中a被n代替，b被o代替，等等，每个字母是环移13所对应的字母。用rot13加密文件两遍便恢复出原始的文件：p=rot13（rot13（p） 简单代替密码很容易破解，因为它没有明文的不同字母的出现频率掩盖起来。 2多名码代替密码（homophonic substitution）：与简单代替密码相似，只是一对多映射，每个明文字母可以加密成多个密文字母。 例如，a可能对应于5、13、25; b可能对应于7、9、31、42 当对字母的赋值个数与字母出现频率成比例时，安全性将有所提高。这是因为密文符号的相关分布会近似于平的，可以挫败频率分析。多名码代替密码比简单代替密码难破译，但仍不能掩盖明文语言的所有统计特性，用已知明文攻击，较容易破解，但用唯密文攻击要困难些。,3(省)多字母代替密码（ploygram cipher)：字符块被成组加密. 例如，aba可能对应于rtq，abb可能对应于sll，等等。 playfair在1854年发明了playfair密码。在第一次世界大战中英国人就使用这种密码。 playfair将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。i与j视为同一字符，55变换矩阵为 c i p h e r a b d f g k l m n o q s t u v w x y z,加密规则是按成对字母加密，规则为“相同对中的字母加分隔符(如x)，同行取右边，同列取下边，其他取交叉”，例如下面的分组加密方法。 明文：balloon 单词中的ll为相同字符，所以分组为：ba lx lo on 明文：he，h和e在矩阵中同一行，都取右边的字符，密文为：ec 明文：dm，d和m在矩阵中同一列，都取下面的字符，密文为：mt 明文：kt，k和t在矩阵中不同行也不同列，取交叉顶点上的字符，密文为：mq 明文：od ，o和d在矩阵中不同行也不同列，取交叉顶点上的字符，密文为：tr 以这个55变换矩阵为例，可以对单词进行加密，加密结果如表2-1所示。,playfair密码算法有2626=676种字母对组合，字符出现几率一定程度上被均匀化，基于字母频率的攻击比较困难，但依然保留了相当的结构信息。 4(省)多表代替密码（polyalphabetic substitution cipher）由多个简单的代替密码构成，例如，可能使用5个不同的简单代替密码，单独一个字符用来改变明文的每个字符的位置。多表代替密码由loen battista在1568年发明，维吉尼亚（vigenre)密码、博福特（beaufort）密码、滚动密钥(running-key)密码、弗纳姆 (vernam)密码、转轮机(rotor machine)都属于多表代替密码。,置换密码,在简单的纵行置换密码中，把明文按列写入，按行读出，而密钥事实上由两方面信息组成：行宽、列高，读出顺序默认从左到右。一个简单纵行置换密码比如：明文：computer graphics may be slow，按照列宽10个字符的方式写出为： c o m p u t e r g r a p h i c s m a y b e s l o w 可以得到密文：caeopsmhlpioucwtsemragyrb， 下面是一个由密钥确定读出顺序的例子：如果再加上密钥： 密钥： 4 3 1 2 5 6 7 明文： a t t a c k p o s t p o n e d u n t i l t w o a m x y z 按照密钥大小的顺利，按照列的字符得到 密文：ttnaaptmtsuoaodwcoixpetz。,2.2.3 转轮机替换密码实例,上个世纪20年代，出现了转轮密码，而由德国发明家亚瑟谢尔比乌斯发明的enigma 密码机最为著名。它主要由经电线相连的键盘、转子和显示器组成，转子本身也集成了26条线路（在图2-5中显示了6条），把键盘的信号对应到显示器不同的小灯上去。在图2-5中可以看到，如果按下a键，那么灯b就会亮，这意味着a被加密成了b。同样地我们看到，b被加密成了a，c被加密成了d，d被加密成了f，e被加密成了e，f被加密成了c。于是如果我们在键盘上依次键入cafe（咖啡），显示器上就会依次显示dbce，这是最简单的加密方法之一简单替换密码。,(省)不仅仅如此，因为当键盘上一个键被按下时，相应的密文在显示器上显示，然后转子的方向就自动地转动一个字母的位置（在图中就是转动1/6圈，而在实际中转动1/26圈）。图2-6表示了连续键入3个b的情况。,(省)当第一次键入b时，信号通过转子中的连线，灯a亮起来，放开键后，转子转动一格，各字母所对应的密码就改变了；第二次键入b时，它所对应的字母就变成了c；同样地，第三次键入b时，灯e闪亮。 为使机器更安全，可以把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，n个转轮的机器的周期是26n。为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。,(省)德国人为了战时使用，大大加强了其基本设计，军用的enigma由3个转轮，从5个转轮中选取。转轮机中还有一块稍微改名明文序列的插板，有一个反射器导致每个转轮对每一个明文字母操作两次，结构如图2-7所示。,(省)于是转子自身的初始方向，转子之间的相互位置，以及连接板连线的状况就组成了所有可能的密钥：三个转子不同的方向组成了26*26*26=17576种不同可能性；三个转子间不同的相对位置为6种可能性；连接板上两两交换6对字母的可能性数目非常巨大，有100391791500种；于是一共有17576*6*100391791500，大约为10000000000000000，即一亿亿种可能性。 (省)但如此复杂的密码机在第二次世界大战中被破解了，首先是波兰人利用德军电报中前几个字母的重复出现，破解了早期的enigma密码机，而后又将破译的方法告诉了法国人和英国人。英国人在计算机理论之父图灵的带领下，通过寻找德国人在密钥选择上的失误，并成功夺取德军的部分密码本，获得密钥，以及进行选择明文攻击等等手段，破解出相当多非常重要的德军情报。,2.2.4 一次一密乱码本,如上所述的所有密码算法均被破解，那么是否存在无法破解的理想加密方案呢？香农证明了一种密码属于这种情况，它就是一次一密乱码本（one-time pad）。 一次一密乱码本就是一个大的不重复的真随机密钥字母集，发送者用乱码本中的每一个密钥准确地加密一个明文字符，加密是明文字符和密钥字符进行模26加法。比如： 明文：onetimepad 密钥：tbfrgfarfm 密文：ipklpsfhgq 因为：o+tmod26=i，n+bmod26=p，e+fmod26=k， (15+20)mod26=9 如果窃听者不能得到用来加密的一次一密乱码本，这个方案就是完全保密的。给出的密文消息相当于同样长度的任何可能的明文消息。,对于上面得到的密文，如果进行密码分析，其对应的密钥序列也可以是：poyyaeaazx，推出明文是salmoneggs，这是有意义的词汇。同样，密钥序列还可以是：bxfgbmimxm，推出的明文是greenfluid，也是有意义的词汇。由于明文消息是等概率的，所以密码分析者无法确定哪一个明文是正确的，由这样的一个随机密钥序列异或一个非随机的明文消息将产生一个完全随机的密文消息，再大的计算能力也无能为力。 这个方案需要注意两点：一是密钥字母必须是真正随机产生的；二是密钥不能重复使用。一次一密乱码本的缺点就是要求密钥序列的长度必须等于消息的长度，这使它非常不适于加密较长的消息，另外要保证发送者和接受者是完全同步的，因为哪怕传输中仅仅有1位的偏移，就会导致消息变成乱七八糟的东西，无法解密。,2.2.5 对称和非对称算法,早期的密钥算法是对称算法（加密密钥能够从解密密钥中推算出来，反之亦然）。多数对称算法中，加密和解密 由同一个 密钥来控 制，也叫 单钥算法， 如图2-8。,非对称算法/公钥算法/双钥算法：加密密钥不同于解密密钥，而且解密密钥不能根据加密密钥计算出来，反之亦然。 1976年，斯坦福大学的whitfield diffie等为解决密钥管理问题，发表论文“密码学研究的新方向”，奠基新体制，如图2-9。,公钥算法：加密密钥可以公开，即陌生人可以用加密密钥加密信息，但只有用相应的解密密钥才能解密信息。 加密密钥为公钥，解密密钥为私钥。 比较著名的公钥密码算法有：rsa、背包密码、mceliece密码、diffe-hellman、rabin、零知识证明的算法、椭圆曲线（elliptic curve）、elgamal算法等等。 rsa是最有影响的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击。现今世界上广为应用的pgp邮件加密软件就是基于rsa算法的。,2.2.6 分组密码和序列密码,如果按照加密时对明文的处理方法分类，密码算法可以分为两类：分组密码和序列密码。 分组密码将明文分成固定长度的组，典型分组长度是64位用同一密钥和算法对每一块加密，输出也是固定长度的密文，密钥的位数和这个固定的位数大致相等。 序列密码/流密码每次加密一位或一字节的明文，序列密码使用尽可能长的密钥，由于长的密钥的存储，分配都很困难，因此，采用一个较短的密钥来控制某种算法来产生出长的密钥。序列密码的加解密器采用较简单的模2加法器，这使它的实现相当简单，于是，它的关键就是产生密钥序列的算法。,这两种加密机制各有其特点（简）。 对于分组密码方式，如果每组的明文是n位，则n位密文的空间为2的n次方种情况，试想，在n很小的情况下（例如只有8位），其密文空间显然也很小（只有255种情况），这时只要强力攻击即穷举法就可很容易破解。这并不是由于它的加密的原理和结构的原因，而是因为它的分组大小太小，所以一般的分组都接近64位。攻击者也可以分析密文中字符分布的频率，将结果和已知的字符分布相比较，可以很容易的破解密文。这种方式还有一个缺点就是并不是所有的明文长度都是组长度的整数倍，于是就要进行合适的填充以解决这种不匹配，填充平均起来大概占组大小的一半，故在网络传输时会浪费宝贵的网络带宽。 分组密码的密钥可以在一定时间内固定，不必每次变换，因此给密钥配发带来了方便。但是，由于分组密码存在着密文传输错误在明文中扩散的问题，因此在信道质量较差的情况下无法使用。分组密码中最著名的两个分组密码：des(data encryption standard) 数据加密标准 idea(international data encryption algorithm)国际数据加密算法。,序列密码：最主要的优点是其对称性，它为加解密带来很大方便。另外一个优点是低错误扩散。这是因为明文和密码是逐比特对应加、解密的。因此，传输过程中的每比特错误只能影响该比特的明文。序列密码体制和其它密码体制相比较能做到更高速的加、解密(相对而言)。序列密码体制的密钥序列是随机变化的，而且每个密钥只使用一次。允许用户自己改变加密序列的大小，这样总可以找到一个分组大小使得不用填充明文，这样就可以充分的利用有限的网络带宽。典型的现代序列密码是由rsa公司发明的rc4，而在计算机出现之前，可以说所有的密码都是对称序列密码。,2.2.7 流密码简介（省）,流密码（序列密码）思想：利用密钥k产生一个密钥流z=z0z1，并对明文串x=x0x1x2使用规则为y=y0y1y2=ez0(x0)ez1(x1)ez2(x2)。密钥流由密钥流发生器f产生：zi=f(k, i)，这里i是加密器中的记忆元件在时刻i的状态，f是由密钥k和i产生的函数。 分组密码与流密码的区别是有无记忆性，如图2-10所示。流密码的滚动密钥z0=f(k,0)由函数f、密钥k和指定的初态0完全确定。由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态，因而i(i0)可能依赖于k，0，x0，x1，xi-1等参数。分组密码无记忆。,2.3常用加密算法,目前加密算法很多，具有代表性的加密算法： des算法、idea算法、aes算法、rc5算法、rc4序列算法、rsa算法与椭圆曲线算法。 2.3.1 idea 算法国际加密标准 idea是一个对称迭代分组密码，分组长度为64比特，密钥长度为128比特。idea的软件实现速度与des差不多。但硬件实现速度要比des快得多，快将近10倍。设计者们声称由eth zurich开发的一种芯片，采用idea算法的加密速率可达到177m比特/秒。 idea密码中使用了以下三种不同的运算： 1. 逐比特异或运算； 2. 模2加运算； 3. 模2+1乘运算，0与2对应。,idea算法是由8圈迭代和随后的一个输出变换组成。它将64比特的数据分成4个子块，每个16比特，令这四个子块作为迭代第一轮的输出，全部共8圈迭代。每圈迭代都是4个子块彼此间以及16比特的子密钥进行异或，mod2加运算，mod2+1乘运算。任何一轮迭代中，第三和第四子块互换。该算法所需要的“混淆”可通过连续使用三个“不相容”的群运算于两个16比特子块来获得，并且该算法所选择使用的ma-（乘加）结构可提供必要的“扩散”。 idea有多达2的51次方个弱密钥，这些弱密钥是否会威胁它的安全性还是一个迷。但毫无疑问，idea密码能够抵抗差分分析和线性分析。,2.3.2 aes 算法（略）,2000年10月，nist（美国国家标准和技术研究院）宣布通过从15种候选算法中选出的一项新的密钥加密标准。新的标准将会代替密钥长度变的太短的旧的des算法。rijndael被选中成为将来的aes(高级加密标准advanced encryption standard)。 aes有如下优点：可变的密钥长度、混合的运算、数据相关的圈数、密钥相关的圈数、密钥相关的s盒、长密钥调度算法、变量f、可变长明文/密文块长度、可变圈数、每圈操作作用于全部数据、 这个加密体系是一种对称分组加密方法，因为信息的内容是以128位长度的分组为加密单元的。加密密钥长度有128，192或256位多种选择。,2.3.3 rc5算法（省）,rc5是对称加密算法，由rsa公司的首席科学家r.rivest于1994年设计，1995年正式公开的一个很实用的加密算法。它主要通过数据循环来实现数据的扩散和混淆。每次循环的次数都依赖于输入数据，事先不可预测。 rc5实际上是由三个参数决定的一组加密算法，即分组长度w，密钥长度b和轮数r，见下表。,rc5加密明文块的长度为32，64，128 bits。并且对应同样长度的密文。密钥长度为从0到2040 bits。一个特定的rc5表示为： rc5-w/r/b。rivest建议使用的标注rc5为：rc5-32/12/16（明文分组长度64，加密轮数12，密钥长度128 bits)。rc5算法的特点是： 适用于软件或者硬件实现； 运算速度快； 能适应于不同字长的程序（一个字的bit数是rc5的一个参数；不同字长派生出相异的算法）； 加密的轮数可变（轮数是rc5的第二个参数，这个参数用来调整加密速度和安全性的程度）； 密钥长度是可变的（密钥长度是rc5的第三个参数）； rc5形式简单，易于实现，加密强度可调节； 对记忆度要求不高（使rc5可用于类似smart card这类的对记忆度有限定的器件）； 高保密性（适当选择好参数）； 对数据实行bit循环移位（增强抗攻击能力）；,2.3.4 rc4序列算法（省）,序列算法体制是：密钥馈送给一个算法，产生一个无穷序列(这种算法通常称为序列产生器或密钥流产生器)，但是，在实际应用中很难做到产生无穷序列(此时称one time pad),达到所谓的完全保密，所以现在实际应用的序列密码体制都产生伪随机密码序列。序列密码体制如图2-11所示。,rc4是目前使用较多，性能也较好的序列算法，它由ron rivest在1987年为rsa公司开发，是可变密钥长度的序列密码，该算法以ofb方式工作：密钥序列与明文互相独立。它有一个88的s盒：s0，s1，s255。所有项都是数字0到255的置换，并且这个置换是一个可变长度密钥的函数。它有两个计数器：i和j，初值为0。要产生一个随机字节，需要按下列步骤进行： i=(i+1)mod256 j=(j+si)mod256 交换si和sj t=(si+sj)mod 256 k=st 字节k与明文异或产生密文，或者与密文异或产生明文。rc4的加密速度很快，大约是des的10倍。rc4广泛应用于商业软件中，包括locus notes、苹果计算机的aoce、oracle的安全sql数据库以及adobe的acrobat中。,2.3.5 椭圆曲线算法（省）,在公钥密码算法中，1985年，n. koblitz和v. miller分别独立提出了椭圆曲线密码体制(ecc)，其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。他们并没有提出新的算法，只是把椭圆曲线运用到已存在的公钥密码算法中，比如说elgamal加密算法。 随后，koyama等在crypto91、demytko在eurocrypt93中分别提出了新的基于椭圆曲线的单项限门函数，生成了类似于rsa的公钥密码算法。椭圆曲线密码体制和rsa体制比较起来，所需要的密钥量小，安全程度高，比如rsa密码体制需要1024-bit的密钥才能达到的安全程度，利用椭圆曲线只需要160比特位的密钥就能够保证同样的安全，密钥长度的减少同时带来了计算速度的提高。即使是在剩余类环运用离散对数而构造的加密系统的安全程度也要低于椭圆曲线，因此椭圆曲线系统不愧为一个性质较好的密码系统。现在密码学界普遍认为它将替代rsa成为通用的公钥密码算法，set( secure electronic transactions )协议的制定者已把它作为下一代set协议中缺省的公钥密码算法。 在数字签名一节中详细地介绍的dsa算法，被广泛应用在椭圆曲线上的变化，称为椭圆曲线数字签名算法ecdsa，由ieee工作组和ansi（amercian national standards institute）x9组织开发。,应用椭圆曲线的数字签名同时可以很容易地使用到小的有限资源的设备中，例如智能卡。椭圆曲线上的密码算法速度很快，分别在32位的pc机上和16位微处理器上实现了快速的椭圆曲线密码算法，其中16位微处理器上的edsa数字签名不足500ms。图2-12为rsa算法和椭圆曲线密码算法的难度比较。,2.4 des对称加密技术,des（data encryption standard）算法于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。 2.4.1 des算法的历史 des加密算法要达到的目的有4点： （1）提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改； （2）具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握； （3）des密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础； （4）实现经济，运行有效，并且适用于多种完全不同的应用。 1977年1月，美国政府颁布采纳ibm公司设计的方案作为非机密数据的正式数据加密标准des。 国内随着三金工程尤其是金卡工程的启动，des算法在atm、磁卡及智能卡（ic卡）、加油站、高速公路收费站等领域被广泛应用，以此来实现关键数据的保密。如信用卡持卡人的pin的加密传输，ic卡与pos间的双向认证、金融交易数据包的mac校验等，均用到des算法。,2.4.2 des算法的安全性（略） des算法正式公开发表后，引起了一场激烈的争论。1977年diffie等人提出了制造一个每秒能测试106个密钥的大规模芯片，该芯片的机器大约一天可搜索des算法的整个密钥空间，制造这一机器需要2000万美元。 1993年r.session等人给出了一个非常详细的密钥搜索机器的设计方案，它基于并行的密钥搜索芯片，此芯片每秒测试5107个密钥，当时这种芯片的造价是10.5美元，5760个该芯片组成的系统需要10万美元，这一系统平均1.5天即可找到密钥，如果利用10个这样的系统，费用是100万美元，但搜索时间可降到2.5小时。可见这种机制是不安全的。 des的56位短密钥面临另外一个严峻问题是：国际互联网internet的超级计算能力。1997.1.28，美国的rsa数据安全公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56位密钥加密的des密文。计划公布后引起了网户的强烈响应。一位名叫rocke verser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为deshall的搜索行动，成千上万的志愿者加入到计划中，在计划实施的第96天，即挑战赛计划公布的第140天，1997.6.17晚上10:39，盐湖城inetz公司职员michael sanders成功地找到了密钥，在计算机上显示了明文：“the unknown message is: strong cryptography makes the world a safer place”。 世界在internet面前变得不安全了。internet仅应用闲散的资源，毫无代价地破解了des的密码，这是对密码方法的挑战，也是internet超级计算能力的显示。尽管des有些不足，但作为第一个公开密码算法的密码体制成功地完成了它的使命，它在密码学发展历史上具有重要的地位。,2.4.3 des算法的原理（*）,des算法的入口参数有3个： key、 data、 mode key为8个字节共64位，是des算法的工作密钥。 data也为8个字节64位，是要被加密或被解密的数据。 mode为des的工作方式有两种：加密或解密。 des算法的原理是： 如mode为加密，则用key把数据data进行加密，生成data的密码形式（64位）作为des的输出结果； 如mode为解密，则用key把密码形式的数据data解密，还原为data的明码形式（64位）作为des的输出结果。 在通信网络的两端，双方约定一致的key，在通信的源点用key对核心数据进行des加密，然后以密码形式在公共通信网（如电话网）中传输到通信网络的终点，数据到达目的地后，用同样的key对密码数据进行解密，便再现了明码形式的核心数据。这样，就保证了核心数据（如pin，mac等）在公共通信网中传输的安全性和可靠性。通过定期在通信网络的源端和目的端同时改用新的key，便能进一步提高数据的保密性，这是现在金融交易网络的流行做法。,2.4.4 des算法的实现步骤*,des算法实现加密需要3个步骤。 第1步：变换明文。对给定的64位的明文x，首先通过一个置换ip表来重新排列x，从而构造出64位的x0，x0=ip(x)=l0r0，其中l0表示x0的前32位，r0表示x0的后32位。 第2步：按规则迭代。规则为： li = ri-1 ，ri = lif(ri-1,ki) （i=1,2,3, ,16） 经过第1步变换已经得到l0和r0的值，其中符号表示数学运算“异或”，f表示一种置换，由s盒置换构成，ki是一些由密钥编排函数产生的比特块。f和ki将在后面介绍。 第3步：对l16r16利用ip-1作逆置换，就得到了密文y0加密过程如图2-13所示。 des加密需要4个关键点：ip置换表和ip-1逆置换表、函数f、子密钥ki、s盒 工作原理：,（1）ip置换表和ip-1逆置换表。 输入的64位数据按ip表置换进行重新组合，并把输出分为l0和r0两部分，每部分各32位 。（设计如此） 其ip表置换 16位*4,ip-1逆置换表,16位*4,将输入的64位明文的第58位换到第1位，第50位换到第2位，依此类推，最后一位是原来的第7位。l0和r0则是换位输出后的两部分，l0是输出的左32位，r0是右32位。比如：置换前的输入值为d1d2d3d64，则经过初始置换后的结果为：l0=d58d50d8，r0=d57d49d7。 经过16次迭代运算后。得到l16和r16，将此作为输入进行逆置换，即得到密文输出。 逆置换正好是初始置的逆运算，例如，第1位经过初始置换后，处于第40位，而通过逆置换ip-1，又将第40位换回到第1位，其逆置换ip-1规则表如2-4所示。,（2）函数f。它有两个输入：32位的ri-1和48位ki，f函数的处理流程如图2-14。,e变换的算法是从ri-1的32位中选取某些位，构成48位，即e将32位扩展为48位。变换规则根据e位选择表，如表2-5。 16位*3,ki是由密钥产生的48位比特串，具体的算法是：将e的选位结果与ki作异或操作，得到一个48位输出。分成8组，每组6位，作为8个s盒的输入。 每个s盒输出4位，共32位，s盒的工作原理将在第4步介绍。s盒的输出作为p变换的输入，p的功能是对输入进行置换，p换位表如表2-6所示。 16位*2 （3）子密钥 ki。设密钥为k，长度为64位，但是其中第8，16，24，32，40，48，56，64用做奇偶校验位，实际上密钥长度为56位。k的下标i的取值范围是1到16，用16轮来构造。构造过程如图2-15,首先，对于给定的密钥k，应用pc1变换进行选位，选定后的结果是56位，设其前28位为c0，后28位为d0。pc1选位如表2-7所示。 14位*4,第1轮：对c0作左移ls1得到c1，对d0作左移ls1得到d1，对c1d1应用pc2进行选位，得到k1。其中ls1是左移的位数，ls、 pc2如下。 第2轮：对c1和d1作左移ls2得到c2和d2，进一步对c2d2应用pc2进行选位，得到k2。如此继续，分别得到k3，k4，k16。,（4）s盒的工作原理。s盒以6位作为输入，而以4位作为输出，现在以s1为例说明其过程。假设输入为a=a1a2a3a4a5a6，则a2a3a4a5所代表的数是0到15之间的一个数，记为：k=a2a3a4a5；由a1a6所代表的数是0到3间的一个数，记为h=a1a6。在s1的h行，k列找到一个数b，b在0到15之间，它可以用4位二进制表示，为b=b1b2b3b4，这就是s1的输出。s盒由8张数据表组成，如表2-10所示。,2.4.5 des算法的应用误区（略）,des算法具有比较高的安全性，到目前为止，除了用穷举搜索法对des算法进行攻击外，还没有发现更有效的办法。而56位的密钥的穷举空间为2的56次方，这意味着如果一台计算机的速度是每秒钟检测一百万个密钥，则它搜索完全部密钥就需要将近2285年，可见难以实现。当然，随着科学技术的发展，当出现超高速计算机后，可考虑把des密钥的长度再增长一些，以此来达到更高的保密程度。 des算法中只用到64位密钥中的56位，而第8,16,24,64位8个位并未参与des运算，这一点提出了一个应用上的要求，即des的安全性是基于除了8，16，24，64位外的其余56位的组合变化2的56才得以保证的。因此，在实际应用中，应避开使用第8，16，24，64位作为有效数据位，而使用其他的56位作为有效数据位，才能保证des算法安全可靠地发挥作用。如果不了解这一点，把密钥key的8，16，24，64位作为有效数据使用，将不能保证des加密数据的安全性，对运用des来达到保密作用的系统产生数据被破译的危险，这正是des算法在应用上的误区，留下了被人攻击、破译的极大隐患。,2.4.6 des算法的程序实现,根据des算法的原理，可以方便地利用c语言实现其加密和解密算法。程序在vc+6.0环境下测试通过。 案例2-1 des加密算法研究,2.5 rsa公钥加密技术,1976年，diffie和hellman在“密码学新方向（new direction in cryptography）”文中首次提出了公开密钥密码体制的思想。 1977年，rivest，shamir和adleman三人(并以发明者的名字命名)实现了公开密钥密码体制，称为rsa公开密钥体制，它是第一个既能用于数据加密也能用于数字签名的算法。这种算法易于理解和操作。但rsa的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。 2.5.1 rsa算法的原理 rsa算法是一种基于大数不可能质因数分解假设的公钥体系。简单地说，就是找两个很大的质数/素数，一个公开给世界，称之为“公钥”，另一个不告诉任何人，称之为“私钥”。两把密钥互补用公钥加密的密文可以用私钥解密，反过来也一样。假设a寄信给b，他们知道对方的公钥。a可用b的公钥加密邮件寄出，b收到后用自己的私钥解出a的原文，这样就保证了邮件的安全性。,rsa体制可以简单描述如下： （1）生成两个大素数p和q； 11、7 （2）计算这两个素数的乘积n=pq； 77 （3）计算小于n并且与n互质的整数的个数， 即欧拉函数（n） =( p-1 ) ( q-1 )； 10 *6 = 60 （4）选择一个随机数b满足1b(n)，并且b和(n)互质， 即gcd（b,(n)）=1。 （5）计算ab=1 mod （n）； a=1/b （6）保密a，p和q， 公开n和b。 利用rsa加密时，明文以分组的方式加密，即每一个分组的比特数应该小于log2n。加密明文x时，利用公钥 （b, n）计算c=xb mod n就可以得到相应的密文c。解密时，通过计算c a mod n就可以恢复明文x。 选取的素数p和q要足够大，从而乘积n足够大，在事先不知道p和q的情况下分解n是计算上不可行的。常用的公钥加密算法包括：rsa密码体制、elgamal密码体制和散列函数密码体制（md4，md5等）。,2.5.2 rsa算法的安全性 rsa算法的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论证明，因为没有证明破解，rsa算法就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，rsa 算法的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。人们已能分解多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。 2.5.3 rsa算法的速度 由于进行的都是大数计算，使得rsa算法最快的情况也比des算法慢上数倍，无论是软件还是硬件实现，速度一直是rsa算法的缺陷，一般来说只用于少量数据加密。 rsa算法是第一个能同时用于加密和数字签名的算法