信息加密和鉴别ppt.ppt

第四章 信息加密与鉴别,内容提要,本章介绍密码学的基本概念。 介绍加密领域中两种主流的加密技术： DES加密（Data Encryption Standard） RSA加密（Rivest-Shamir-Adleman） 并用程序实现这两种加密技术的算法。最后介绍目前常用的加密工具PGP（Pretty Good Privacy），使用PGP产生密钥，加密文件和邮件。,4.1 信息加密基础,4.1.1 信息加密的发展 1、密码学概述 密码学是一门古老而深奥的学科，对一般人来说是非常陌生的。长期以来，只在很小的范围内使用，如军事、外交、情报等部门。计算机密码学是研究计算机信息加密、解密及其变换的科学，是数学和计算机的交叉学科，也是一门新兴的学科。,密码技术简介,密码学的历史比较悠久，在四千年前，古埃及人就开始使 用密码来保密传递消息。 两千多年前，罗马国王Julius Caesare（恺撒）就开始 使用目前称为“恺撒密码”的密码系统。但是密码技术直到 本20世纪40年代以后才有重大突破和发展。 特别是20世纪70年代后期，由于计算机、电子通信的广 泛使用，现代密码学得到了空前的发展。,中途岛之战,中途岛，陆地面积约 5.2平方公里，有三条 交叉的飞机跑道。该岛 距美国旧金山和日本横 宾均相距2800海里， 处于亚洲和北美之间的 太平洋航线的中途， 故名中途岛。,中途岛海战,日本海军联合舰队司令山本五十六,日本海军苍龙和飞龙号航空母舰,美舰载40毫米高炮向来袭日机猛烈开火,美国海军上将 尼米兹,约瑟夫罗谢福特少校， 美国密码专家，1940年， 他帮助破解了日本海军的 通讯密码JN-25，1942年 中途岛战役前破译日军攻 击目标。,1942年6月， 中途岛之战， 美国军队和日 本帝国海军作 战的场面。,偷袭珍珠港：,1941年12月7日清晨，日本皇家海军的飞机和微型潜艇突然袭击美国海军基地珍珠港以及美国陆军和海军在夏威夷欧胡岛上的飞机场的事件。这次袭击最终将美国卷入第二次世界大战 。,2、基本概念,（1）消息和加密 遵循国际命名标准，加密和解密可以翻译成：“Encipher（译成密 码）”和“（Decipher）（解译密码）”。也可以这样命名： “Encrypt（加密）”和“Decrypt（解密）”。 消息被称为明文。用某种方法伪装消息以隐藏它的内容的过程称为加 密，加了密的消息称为密文，而把密文转变为明文的过程称为解密，图 表明了加密和解密的过程。,明文 密文,明文用M（Message，消息）或P（Plaintext，明文） 表示，它可能是比特流、文本文件、位图、数字化的语音流 或者数字化的视频图像等。 密文用C（Cipher）表示，也是二进制数据。 加密函数E作用于M得到密文C：E（M）=C。 解密函数D作用于C产生明文M，D（C）=M。 先加密后再解密消息，原始的明文将恢复出来： D（E（M）=M必须成立。,鉴别、完整性和抗抵赖性,除了提供机密性外，密码学需要提供三方面的功能：鉴 别、完整性和抗抵赖性。 鉴别：消息的接收者应该能够确认消息的来源；入侵者 不可能伪装成他人。 完整性：消息的接收者应该能够验证在传送过程中消息 没有被修改；入侵者不可能用假消息代替合法消息。 抗抵赖性：发送消息者事后不可能虚假地否认他发送的 消息。,（2） 算法和密钥,密钥用K表示。密钥K的可能值的范围叫做密钥空间。加 密和解密运算都使用这个密钥，即运算都依赖于密钥，并用 K作为下标表示，加解密函数表达为： EK（M）=C DK（C）=M DK（EK（M）=M，如图所示。,有些算法使用不同的加密密钥和解密密钥，也就是说加密密钥K1与 相应的解密密钥K2不同，在这种情况下，加密和解密的函数表达式为： EK1（M）=C DK2（C）=M 函数必须具有的特性是，DK2（EK1（M）=M，如图所示。,4.2 传统加密技术,4.2.1 替代密码概述,替代密码是通过密钥字母表用一组密文字母来代替一组明文字母以隐藏明文，但保持明文字母的位置不变。如果密钥字母表由一个字母表构成替代密码，称为单表替代密码，如果由多个字母表构成替代密码，称为多表替代密码。,替代密码,单表替代密码,多表替代密码,20世纪早期密码机,1、 单表替代密码,单表替代密码的代表是凯撒密码，又叫循环移位密码。其加密方法是把明文中的所有字母都用它右边的第k个字母替代，并认为Z后面又是A。其映射关系函数为： F(a)=(a+k) mod n a明文字母；n字符集字母个数；k密钥,A B C D E F V W X Y Z （k=3）,D E F G H I Y Z A B C,1、 单表替代密码,单表替代密码的优点：密钥简单、易记； 单表替代密码的缺点：这种密码是很容易破译的，因为最多只需尝试25次即可轻松破译密码。凯撒密码的优点是密钥简单易记。但它的密码文与明码文的对应关系过于简单，故安全性很差,2、 多表替代密码,周期替代密码是一种常用的多表替代密码，又叫维吉尼亚密码。其加密表是以字母表移位为基础把26个英文字母进行循环移位，排列在一起，形成26*26方阵，称为维吉尼亚表。,2、多表替代密码,周期替代密码在实际使用时，往往把某个容易记忆的词或词组当作密钥，然后把密钥反复写在明文下方或上方。加密时，以明文字母选择列，以密钥字母选择行，两者的交点就是加密生成的密文字母；解密时做逆操作即可。,重点难点：多表替代密码,周期多表密码，每张表=caesar密码 密钥不断重复 密钥字母决定移位的次数 假设密钥为deceptive： key: de cep tivedecept ived eceptive plaintext: we are discovered save yourself ciphertext: ZI CVT WQNGRZGVTW AVZH CQYGLMGJ,Vigenre密码,3. 换位密码,（1）换位密码概述 （2）列换位法 （3）矩阵换位法,维吉尼亚密码的破解,维吉尼亚密码(Vigenere Cipher) 对字频信息的隐藏还 不够彻底。在19世纪50年代, 英国人查尔斯-巴贝奇对其的 破解. 其实其破解的基本思想如下:比如在密文中, 经常出现了同一个子串(比如UPK), 而且 每个字串之间的距离都是3的整数倍. 那么解密者就很容易推 测出秘匙的长度为3. 其原因也是十分简单的:当秘匙在重复了N次之后, 其还是用第一个字母去加密 UPK相应的明文. 尤其是对THE, YOU, WHAT 这类高频词 汇当使用了弱秘匙的话,更容易遭受破解.,换位密码概述,换位密码是采用移位法进行加密的。它把明文中的字母重新排列，本身不变，但位置变了。换位密码是靠重新安排字母的次序，而不是隐藏他们。换位加密方法有列换位法和矩阵换位法等。,换位密码 ,列换位法,矩阵换位法,1、 列换位法,列换位法是将明文字符分割成若干个（例如3个）一列的分组，并按一组后面跟着另一组的形式排好，不全的组用不常用的字符填满。最后取各列来产生密文。密钥为组中字符的个数。,明文,分组换位,C1 C2 C3 C4 C5 C6 C7 C8 C9 ,C1 C2 C3,C4 C5 C6,C7 C8 C9,C1 C2 C3,C4 C5 C6,C7 C8 C9,C1 C4 C7 ,C2 C5 C8 ,C3 C6 C9 ,C1 C4 C7,C2 C5 C8,C3 C6 C9,C1 C4 C7C2 C5 C8C3 C6 C9,密文,加密案例,列换位法将明文字符分割成为五个一列的分组并按一组后面跟着另一组的形式排好。如明文是： WHAT YOU CAN LEARN FROM THIS BOOK 分组排列为：,密文为：WOLF HOHUE RIKAC AOSXT ARMBX YNNTO X,解密案例,对下列54个密码进行解密。明文中可能会出现诸如perception(感觉)之类的词汇，明文只包含字母，没有空格。加密方法是列换位 (Transposition)法，为了阅读方便，密文被分成5个字母一组。 密文：IHADL HEIBD ATEEA ROLOV TPMVC NENEI RYEEP MOATO OAPRX TNUBU PTOY,密文是矩阵的形式，因此可以根据密文的长度来分组。密文长度为54，而54=2*27=3*18=6*9 分别对这三种形式进行分析，因为没有告知具体的密钥是多少，不能知道每一列具体的顺序，就先只是按照密文字母的顺序来排列每列。,（1）54=2*27 这种形式的举证比较容易观察，只需写出前面几列密文，若不能得到有意义的文字就可以排除。 列序 1 2 3 4 5 26 27 I A L E B P O H D H I D T Y 列序 1 2 I N H E A I D R N O E Y 这两种形式的排列都没有有意义文字perception出现，故排除。,（2）54=3*18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 I D E D E R O P C N R E O O P T B T H L I A E O V M N E Y P A O R N U O A H BT A L T V E I E M T A X U P Y 排列都没有有意义文字perception出现，故排除。,列序 1 2 3 I O O H V A A T T D P O L M O H V A E C P I N R B E X D N T A E N T I U E R B E Y U A E P R E T O P O L M Y,（3） 54=6*9 列序 1 2 3 4 5 6 I D O N O T H A V E A N A T T I T U D E P R O B L E M Y O U H A V E A P E R C E P T I O N P R O B L E M X Y 排列中可以找到有意义文字perception，将文字依次读下去，即是一段有意义的文字： I dont have an attitude problem. You have a perception problem. 后面多余的X、Y是明文分组后最后一部分的长度不足密钥长度时作为补齐字母的。,解密案例,对下列54个密码进行解密。明文只包含字母，没有空格。加密方法是列换位 (Transposition)法，为了阅读方便，密文被分成5个字母一组。 密文：ceyle stdco ,nofft ,htenc ,uiiee, osfer ,srprs , siist ,sooux, dneht ,nacx 明文：Confidence in yourself is the first step on the road to success,2、 矩阵换位法,矩阵换位法是将明文字符按给定的顺序排列在一矩阵中，然后用另一种顺序选出矩阵的字母来产生密文。密钥为矩阵的行数、列数以及给定的置换矩阵。,明文,矩阵换位,C1 C2 C3 C4 C5 C6 C7 C8 C9 ,C1 C2 C3,C4 C5 C6,C7 C8 C9,C1 C2 C3,C4 C5 C6,C7 C8 C9,C1 C4 C7 ,C2 C5 C8 ,C3 C6 C9 ,密文,C1 C4 C7 ,C2 C5 C8 ,C3 C6 C9 ,C3 C1 C2,C6 C4 C5,C9 C7 C8, ,C3 C1 C2,C6 C4 C5,C9 C7 C8,.,C3 C1 C2 C6 C4 C5 C9 C7 C8 .,4.3 对称算法,基于密钥的算法通常有两类：对称算法和公开密钥算法 （非对称算法）。对称算法有时又叫传统密码算法，加密密 钥能够从解密密钥中推算出来，反过来也成立。 在大多数对称算法中，加解密的密钥是相同的。对称算 法要求发送者和接收者在安全通信之前，协商一个密钥。对 称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能 对消息进行加解密。对称算法的加密和解密表示为： EK（M）=C DK（C）=M,4.3.1 DES对称加密技术,DES(Data Encryption Standard)算法 发明人： IBM公司 W.Tuchman和C.Meyer. 基础： 1967年美国Horst Feistel提出的理论； 产生： 美国国家标准局1973年开始研究除国防部外的其它部门的计算 机系统的数据加密标准，于1973年5月15日和1974年8月27日 先后两次向公众发出了征求加密算法的公告，最终选定DES。,2、 DES算法的原理,DES算法的入口参数有三个：Key、Data、Mode。 其中： Key为8个字节共64位，是DES算法的工作密钥； Data也为8个字节64位，是要被加密或被解密的数据； Mode为DES的工作方式有两种：加密或解密。,3、 DES算法的实现步骤,DES算法一般描述,64bits plain text 56bits key,初始置换IP,第1轮,置换选择1,循环左移,置换选择2,K1,第2轮,置换选择2,循环左移,K2,第16轮,K16,置换选择2,循环左移,32bits 对换,逆初始置换IP1,64bits cipher text,48bits,3、 DES算法的实现步骤,第一步：变换明文。 对给定的64位比特的明文X，首先通过一个置换IP表来重新排列X，从而构造出64位比特的X0，X0=IP(X)=L0R0，其中L0表示X0的前32比特，R0表示X0的后32位。 第二步：按照规则迭代。 Li = Ri-1 Ri = Lif(Ri-1,Ki) （i=1,2,316） 经过第一步变换已经得到L0和R0的值，其中符号表示的数学运算是异或，f表示一种置换，由S盒置换构成，Ki是一些由密钥编排函数产生的比特块。f和Ki将在后面介绍。 第三步：对L16R16利用IP-1作逆置换，就得到了密文y。加密过程如图所示。,3、 DES算法的实现步骤,DES加密需要四个关键点： 1、IP置换表和IP-1逆置换表。 2、函数f。 3、子密钥Ki。 4、S盒的工作原理。 DES对64位的明文分组进行操作，通过一个初始置换，将明文分组成左半部分和右半部分，各32位长。然后进行16轮完全相同的运算，这些运算被称为函数f，在运算过程中数据与密匙结合。经过16轮后，左，右半部分合在一起经过一个末置换，这样就完成了。,（1）IP置换表和IP-1逆置换表,58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7,40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25,IP与IP-1互逆,M=(m1 , m2 ,.),1 2 3 4 5 6 7 8,9 10 11 12 13 14 15 16,17 18 19 20 21 22 23 24,25 26 27 28 29 30 31 32,33 34 35 36 37 38 39 40,41 42 43 44 45 46 47 48,49 50 51 52 53 54 55 56,1 2 3 4 5 6 7 8,9 10 11 12 13 14 15 16,17 18 19 20 21 22 23 24,25 26 27 28 29 30 31 32,33 34 35 36 37 38 39 40,41 42 43 44 45 46 47 48,49 50 51 52 53 54 55 56,IP(M)=(m58 , m50 )=(m1 1 , m1 2 ,.),58 50 42 34 26 18 10 2,60 52 44 36 28 20 12 4,62 54 46 38 30 22 14 6,64 56 48 40 32 24 16 8,57 49 41 33 25 17 9 1,61 58 45 37 29 21 13 5,63 55 47 39 31 23 15 7,40 8 48 16 56 24 64 32,39 7 47 15 55 23 63 31,38 6 46 14 54 22 62 30,37 5 45 13 53 21 61 29,36 4 44 12 52 20 60 28,34 2 42 10 50 18 58 26,33 1 41 9 49 17 57 25,IP,IP-1,59 51 43 35 27 19 11 3,57 58 59 60 61 62 63 64,35 3 43 11 51 19 59 27,57 58 59 60 61 62 63 64,（1）IP置换表和IP-1逆置换表,输入的64位数据按置换IP表进行重新组合，并把输出分为L0、R0两部分，每部分各长32位。 比如：置换前的输入值为D1D2D3D64，则经过初始置换后的结果为：L0=D58D50.D8，R0=D57D49.D7。 经过16次迭代运算后。得到L16、R16，将此作为输入，进行逆置换，即得到密文输出。逆置换正好是初始值的逆运算，例如，第20位经过初始置换后，处于第14位，而通过逆置换IP-1，又将第14位换回到第20位。,DES的一轮迭代（F函数）,Li-1 （32 bit）,Ri-1 （32 bit）,选择扩展运算 E盒,48bit寄存器,48bit寄存器,选择压缩运算 S盒,32bit寄存器,置换运算 P,Ri =Li-1f(Ri-1,ki) （32 bit）,（32 bit）,Li =Ri-1,轮开始：64bit分成左右两半,子密钥Ki （48 bit）,扩展置换 E盒 (Expand Box),将输入的32bit块扩展到48bit的输出块； 48bit的输出块再分成8个6bit块；,01 02 03 04,05 06 07 08,09 10 11 12,13 14 15 16,17 18 19 20,21 22 23 24,25 26 27 28,29 30 31 32,01 02 03 04,05 06 07 08,09 10 11 12,13 14 15 16,17 18 19 20,21 22 23 24,25 26 27 28,29 30 31 32,32,04,08,12,16,20,24,28,05,09,13,17,21,25,29,01,扩展置换函数E,扩展位,扩展位,固定位,压缩替代 S盒 (Substitution Box),48bit块通过S盒压缩成32bit块,48bit寄存器,32bit寄存器,6bit,4bit,共8个S盒,将E的选位结果与Ki作异或操作，得到一个48位输出。分成8组，每组6位，作为8个S盒的输入。,S盒,作用：将6个输入位映射为4个输出位； 方法：若定义a1a2a3a4a5a6，将a1a6组成2位二进制数，对应S盒表中的行号；将a2a3a4a5组成一个4位的2进制数，对应S盒表中的列号；映射到交叉点的数据就是该S盒的输出。 S1输入为101011的输出是？A1a6=11 a2a3a4a5=0101 1001,S盒,S盒,表 选择函数S盒表,例 S盒应用实例：设B1=101100，求S1(B1) 则S1(B1)的值位于列号为2的列和行号为6的行，即等于2， 因此S1(B1)的输出是0010。,S盒,DES中其它算法都是线性的，而S盒运算则是非线性的， S盒不易于分析，它提供了更好的安全性；所以S盒是算法的 关键所在； 提供了密码算法所必需的混乱作用,置换函数P（Permutaion）,P置换的目的是：提供雪崩效应； 明文或密钥的一点小的变动都引起密文的较大变化； P的功能是对输入进行置换，P换位表如表所示:,DES中子密钥的生成,假设密钥为K，长度为64位，但是其中第8、16、24、32、40、48、64用作奇偶校验位，实际上密钥长度为56位。,DES中子密钥的生成,64bit密钥,C0（28bit）,D0（28bit）,循环左移,循环左移,C1（28bit）,D1（28bit）,循环左移,循环左移,置换选择2,Ci（28bit）,Di（28bit）,(56bit),(56bit),Ki,K0,(48bit),(48bit),(56bit),子密钥ki,由于不考虑每个字节的第8位，DES的密匙由64位减至56位，每个字 节第8位作为奇偶校验确保密匙不发生错误。 假设密钥为K，长度为64位，但是其中第8、16、24、32、40、48、64用作奇偶校验位，实际上密钥长度为56位。K的下标i的取值 范围是1到16，用16轮来构造。构造过程如图所示。,第一轮：对C0作左移LS1得到C1，对D0作左移LS1得到D1，对C1D1应用PC2进行选位，得到K1。其中LS1是左移的位数，如表所示 第二轮：对C1，D1作左移LS2得到C2和D2，进一步对C2D2应用PC2进行选位，得到K2。如此继续，分别得到K3，K4K16。,置换选择-1（7*8）置换选择-2（6*8）,57 49 41 33 25 17 9,1 58 50 42 34 26 18,10 2 59 51 43 25 27,19 11 3 60 52 44 36,63 55 47 39 31 23 15,7 62 54 46 38 30 22,14 6 61 53 45 37 29,21 13 5 28 20 12 4,14 17 11 24 1 5,3 28 15 6 21 10,23 19 12 4 26 8,16 7 27 20 13 2,41 52 31 37 47 55,30 40 51 45 33 48,44 49 39 56 34 53,46 42 50 36 29 32,假设密钥为K，长度为64位，但是其中第8、16、24、32、40、48、64用作奇偶校验位，实际上密钥长度为56位。对于给定的密钥K，应用PC1变换进行选位，选定后的结果是56位,子密钥换位表PC-2给出了选择及选择后的次序，可以看出去掉了第9、18、22、25、35、38、43、54位,函数f,函数f有两个输入：32位的Ri-1和48位Ki，f函数的处理流程 如图所示。,DES例题：,明文M=“SECURITY”，密钥K=“COMPUTER”。 SECURITY的ASCII码为：53 45 43 55 52 49 54 5916， 转换成二进制： M=(0101 0011 0100 0101 0100 0011 0101 0101 0101 0010 0100 1001 0101 0100 0101 1001)2； IP置换表：,经过IP置换后的排列结果： 11111111 11011001 01001010 10101111 L0 00000000 00000000 10100000 00010101 R0,DES例题：,K=“COMPUTER”的ASCII码用二进制表示： 43 4F 4D 50 55 54 45 5216 K=0100 0011 0100 1111 0100 1101 0101 0000 0101 0101 0101 0100 0100 0101 K加上第8、16、24、64位的奇同位检查码， 并去掉末8位结果如下： K=(0100 0011 1010 0111 1101 0011 1010 1011 0000 0100 1010 1011 0101 0001 1000 1010)2,密钥是64位，加入8个奇同校验位，为72位，去掉字母R，变成64位,密钥长度不是64的整数倍,一般右补0 x00；当然加密和解密应该实现同样的补位原则。即当加密是右补 0 x00，解密时要把补位的0 x00去掉就可以还原数据。在此，安全性肯定是不影响，但有一个问题就是要加密的数据中末尾有0 x00的问题如何解决，这是应考虑用别的补位数据，如0 xff等。,DES例题：,K经过PC-1置换后得到C0，D0 C0=1010 1110 0100 0101 0010 1010 0100 D0=1010 1111 0001 0010 1010 1000 0100 因为是第一次迭代，故左移1位C0D0得到C1D1为： C1=0101 1100 1000 1010 0101 0100 1001 D1=0101 1110 0010 0101 0101 0000 1001 C1D1在经过PC-2置换得48位子密钥K1： K1=0000 0101 1100 0001 0000 0111 0000 0010 0011 1011 1111 0001,DES例题：,将32位R0进行扩展置换后得48位： E(R0)=1000 0000 0000 0000 0000 0001 0101 0000 0000 0000 1010 1010 然后将E(R0)与K1进行异或得A： A= 1000 0101 1100 0001 0000 0110 0101 0010 0011 1011 0101 1011,将结果A分为8组， A1=100001，查S1盒坐标(3，0)得B1=15； A2=011100，查S2盒坐标(0，14)得B2=5； A3=000100，查S3盒坐标(0，2)得B3=9； A4=000110，查S4盒坐标(0，3)得B4=3； A5=010100，查S5盒坐标(0，10)得B5=3； A6=100011，查S6盒坐标(3，1)得B6=3； A7=101101，查S7盒坐标(3，6)得B7=10； A8=011011，查S8盒坐标(1，13)得B8=14,DES例题：,合并B1B2B8得数据B： B=1111 0101 1001 0011 0011 0011 1010 1110 进行置换P得： X0=1010 1100 1110 0010 1110 0111 1011 0011 将L0与X0按位异或，形成R1： R1=0101 0011 0011 1011 1000 1101 0001 1100 令L1=R0 至此，求出第一轮迭代结果L1R1，依次类推可求出L16R16，在经过逆初始置换即可获得密文。,DES 密钥的产生,K=science的ASCII码是： 73 63 69 65 6e 63 65 其二进制表示是： (01110011) (01100011) (01101001) (01100101) (01101110) (01100011) (01100101) 共56個位元 加入奇同位检查码结果如下： (01110011) (10110000) (11011010) (00101100) (01010111) (01110011) (10001100) (11001011) 共64位,按照置换选择1矩阵进行排列：,结果如下： (11000110) (10110101) (00101011) (00111011) (01010101) (10001100) (11000111),将结果分成KL0及KR0： KL0=11000110 10110101 00101011 0011 KR0=10110101 01011000 11001100 0111 按照循环移位表分别向左移动一位： KL1=10001101 01101010 01010110 0111 KR1=01101010 10110001 10011000 1111 经过置换选择2，生成K1： K1= 00101101 11011000 11001110 00110111 01111111 01000000,DES算法的安全性,DES算法具有比较高安全性，到目前为止，除了用穷举搜 索法对DES算法进行攻击外，还没有发现更有效的办法。 而56位长的密钥的穷举空间为256，如果一台计算机的速 度是每一秒种检测一百万个密钥，则它搜索完全部密钥就需 要将近228.5年的时间。 f函数（S盒）的设计原理未知；,DESCHALL,DES分组加密算法是美国政府于1977年公布的数据加密 标准，已在银行业和金融业使用了近二十年，自从其公布 起，DES就一直不断地被人们研究和攻击，它是世界上最知 名的、使用最广泛的分组密码算法。 目前攻击DES的最有效的办法是密钥穷举攻击，Verser 设计了一个密钥穷举攻击程序，用以穷举所有可能的DES密 钥，直至找到正确的那一个密钥，这个计算机程序可以从 Internet上分发和下载。他把这项计划命名为 DESCHALL，这项计划开始时只有几百人参与，最终吸引了 数万名志愿者参加。每有一名新的志愿者加入，DESCHALL 小组就为其分配一部分密钥空间让其测试，这样，正确的密 钥最终会在某一名志愿者的计算机中出现。,1997年1月28日，美国的RSA数据安全公司在RSA安全 年会上公布了一项“秘密密钥挑战”(Secret- KeyChallange)竞赛，分别悬赏$1000、$5000、 $10000用于攻破不同密钥长度的RC5密码算法，同时还悬 赏$10000破密钥长度为56bits的DES算法。 美国克罗拉多州的程序员RockeVerser从97年3月13日 起，在Internet上数万名志愿者的协同工作下，在RSA挑战 赛公布之后的第140天、DESCHALL计划实施的第96天，6 月17日的晚10点39分，盐湖城iNetZ公司的职员 MichaelSanders在他那台主频为奔腾90Hz、16M内存的 PC机上成功地解出了DES的明文，找到了正确的密钥。,密钥长度(bit)穷举时间 4078秒 485 小时 5659天 6441年 7210，696年 802，738，199年 88700，978，948年 96179，450，610，898年 11211，760，475，235，863，837年 128770，734，505，057，572，442，069年,DESCHALL搜索速度估算,4.4 非对称（公开）密钥算法,公开密钥算法（非对称算法）的加密的密钥和解密的密钥不同，而且 解密密钥不能根据加密密钥计算出来，或者至少在可以计算的时间内不 能计算出来。 之所以叫做公开密钥算法，是因为加密密钥能够公开，即陌生者能用 加密密钥加密信息，但只有用相应的解密密钥才能解密信息。加密密钥 叫做公开密钥（简称公钥），解密密钥叫做私人密钥（简称私钥）。 公开密钥K1加密表示为：EK1（M）=C。公开密钥和私人密钥是不 同的，用相应的私人密钥K2解密可表示为：DK2（C）=M。,4.4.2 RSA 公开密钥加密技术,公开密钥加密基本思想是利用求解某些数学难题的困难 性。用户的加密密钥与解密密钥不再相同，理论上通过加密 密钥求解解密密钥是不可能的。 RSA是由MIT的 Rivest, Shamir (3)计算(n)=(p-1)(q-1)=(7-1)(17-1)=96 (4)选择一个随机整数e=5，且1e(n)=96，满足gcd(b, (n)=1；则公钥Pk=5； (5)计算d，(d*e)mod(n)=1,即(d*5)mod 96=1，d=77；则私钥Sk=77； 设明文P=19； 加密：195 mod 119 = 66，传送密文C=66； 解密：6677mod 119 =19，获得明文P=19。,习题：,（1）取两个质数p=11, q=13； （2）得到 n=p*q=143 ； （3）算出另一个数 (n) = (p-1)*(q-1)=120 ； （4）再选取一个与(n) =120互质的数，如设e=7， 满足： e*d=1 mod (n) ，得到d=103； （5） 公开密钥（ 7 ，143） 秘密私钥（103， 143 ） （6）加密：设明文x=85，用公开密钥加密得到密文y： y=xe mod n = 857 mod 143 = 123 （7）解密：用秘密私钥计算： x=yd mod n = 123103 mod 143 = 85,4.4.3 RSA算法的安全性分析,密码分析者攻击RSA体制的关键点在于如何分解n； 若分解成功，使n=pq 则可以算出(n)=(p-1)(q-1)，然后由公开的e，解出秘密的d 若要RSA足够安全，p和q必须为足够大的素数，使分析者 做大数分解非常困难； 模数n必须选大一些；许多标准规定n至少为512比特位。,RSA算法的速度,由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无 论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量 数据加密。 RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和 操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年， 经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公 钥方案之一。,案例：PGP加密技术,PGP（Pretty Good Privacy）加密技术是一个基于RSA公钥加密体系的邮件加密软件，提出了公共钥匙或不对称文件的加密技术。,PGP简介,PGP加密技术的创始人是美国的Phil Zimmermann。他的创造性把把RSA公钥体系和传统加密体系的结合起来，并且在数字签名和密钥认证管理机制上有巧妙的设计，因此PGP成为目前几乎最流行的公钥加密软件包。 由于RSA算法计算量极大，在速度上不适合加密大量数据，所以PGP实际上用来加密的不是RSA本身，而是采用传统加密算法IDEA，IDEA加解密的速度比RSA快得多。PGP随机生成一个密钥，用IDEA算法对明文加密，然后用RSA算法对密钥加密。收件人同样是用RSA解出随机密钥，再用IEDA解出原文。这样的链式加密既有RSA算法的保密性（Privacy）和认证性（Authentication），又保持了IDEA算法速度快的优势。,PGP加密软件,PGP加密软件最新版本是8.0.2，使用PGP8.0.2i可以简洁而高效地实现邮件或者文件的加密、数字签名。 PGP8.0.2的安装界面如图所示。,下面的几步全面采用默认的安装设置，因为是第一次安装，所以在用户类型对话框中选择“No, I am a New User”，如图所示。,使用PGP产生密钥,因为在用户类型对话框中选择了“新用户”，在计算机启动以后，自动提示建立PGP密钥，如图所示。,点击按钮“下一步”，在用户信息对话框中输入相应的姓名和电子邮件地址，如图所示。,在PGP密码输入框中输入8位以上的密码并确认，如图所示。,然后PGP会自动产生PGP密钥，生成的密钥如图所示。,使用PGP加密文件,使用PGP可以加密本地文件，右击要加密的文件，选择PGP菜单项的菜单“Encrypt”，如图所示。,系统自动出现对话框，让用户选择要使用的加密密钥，选中一个密钥，点击按钮“OK”，如图所示。,目标文件被加密了，在当前目录下自动产生一个新的文件，如图所示。,打开加密后的文件时，程序自动要求输入密码，输入建立该密钥时的密码。如图所示。,使用PGP加密邮件,PGP的主要功能是加密邮件，安装完毕后，PGP自动和Outlook或者Outlook Express关联。和Outlook Express关联如图所示。,利用Outlook建立邮件，可以选择利用PGP进行加密和签名，如图所示。,4.7 数字签名,数字签名是一个加密的消息摘要，它是附加在被签名消息 之后或某一特定位置上的一段签名图样。数字签名建立在公 开密钥加密和单向安全哈希函数算法的组合基础之上。,数字签名的原理,1. 签名是可信的； 2. 其他任何人均不能伪造签名，也不能对接收或发送信息 进行篡改，伪造或冒充； 3. 签名不可重用； 4. 签名后的文件是不可变的； 5. 签名不可抵赖。 若当当事双方对签名真伪发生争执时，能够在公证的仲 裁者面前通过验证来确认其真伪。,报文分解函数,也称散列函数，是适应数字签名技术的需要而产生的一种 信息摘要技术。它是一个单向哈希函数，它能从任意长度的 输入信息中产生一个固定长度的输出（通常是128位）。,数据,散列函数,散列值（数据摘要）,数字签名流程,作业：,试编程根据给出的密钥，用列换位法对一段给出的文字进行加密。,