第3章 信息加密技术

1、第第3章章 信息加密技术信息加密技术 本章内容本章内容u3.1 加密技术的相关概念和术语.u3.2 加密的基本思想u3.3 加密技术的分类u3.4 对称加密算法DES算法u3.5 非对称加密算法-RSA算法u3.6 Diffie-Hellman密码体制u3.7 背包密码3.1 加密的相关概念加密的相关概念u明文(plaintext)：也叫纯文本,明码u密文(ciphertext)：也叫密码文本u算法(algorithm):加密和解密过程基于的某种数学程序,数学 变换.u密钥(Key):加解密过程中,某些只被通信双方所掌握的专门的、关键的信息u加密(encryption)u解密(decrypti

2、on)u利用加密技术存储、传输信息，可提供安全保护功能 机密性 完整性 不可否认性密码学的发展阶段u第第1阶段阶段：1949年以前古典密码学 密码学还不是科学，而是艺术； 出现一些简单的密码算法, 加密设备,简单的密码分析手段； 主要特点：数据的安全基于算法的保密u第第2阶段阶段：19491975年现代密码学 密码学成为科学 计算机使得基于复杂计算的密码成为可能 主要特点:数据的安全基于密钥而不是算法的保密u第第3阶段阶段：1975年以后公钥密码学 密码学的新方向公钥密码学 公钥密码使得发送端和接收端无密钥传输的保密通信成为可能。Kerchoffs假设：假设： 如果密码系统的强度依赖于攻击者不

3、知道算法的内部机理，则该密码系统注定会失败。密码系统的安全性应该完全依赖于密钥的安全性.密码算法的安全性u如果不论截取者获得了多少密文，但在密文中都没有足够的信息来惟一地确定出对应的明文，则这一密码体制称为，或称为。u在无任何限制的条件下，目前几乎所有实用的密码体制均是可破的。因此，人们关心的是要研制出()。u如果一个密码体制中的密码不能被可以使用的计算资源破译，则这一密码体制称为。 破译的代价超出信息本身的价值 破译的时间超出了信息的有效期.3.2 3.2 基本加密思想基本加密思想- -替换替换替换替换：按照一定的规则,将明文中每一个字符用不同的密文字符代替。(1)移位替换移位替换 缺点:很

4、容易通过穷举密钥方式破解,密钥的空间小.(2)单表替换单表替换:不规则将明文字母映射到密文字母空间.单表替换密钥空间为26！使用密钥穷举很难破解其密码随着统计学和概率的发展，破解单一字母替代编码非常容易。英文字母出现相对频率英文字母出现相对频率 密文语言统计规律密文语言统计规律 2021-7-16(3)多多表替代表替代密码密码:一一个字母在不同位置上被替换成不同的密文字母个字母在不同位置上被替换成不同的密文字母。 多表替换隐藏了字母的统计规律，比前两者具有更好的安全性。多表替换隐藏了字母的统计规律，比前两者具有更好的安全性。 Vigenere密码密码: t个密文本，加密为：个密文本，加密为：

5、ci=fi(mi)=(mi+ki) mod 26, 其中其中ki为密钥为密钥, i=0,1,t-1 举例说明：k=(6,14,15,7,4,17), t=6 m=meet me in the ally after midnight m=meetme inthea llyaft ermidn ight c=sstaqv obioir rznhjk kfbphe ouwaa b c d e f g h i j k l m n o p q r s t u v w x y za b c d e f g h i j k l m n o p q r s t u v w x y z0 1 2 3 4 5 6

6、 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 250 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 253.2 基本加密思想基本加密思想易位易位易位易位: 把明文中的字符重新排列，本身不变，但位置变了。 栅栏密码，就是把要加密的明文分成N个一组，然后把每组的第i个字连起来，形成一段无规律的话。 举例 1 明文：THERE IS A CIPHER 去掉空格后变为：THEREISACIPHER 两个一组，得到：TH ER EI SA CI PH ER 先取出第一

7、个字母：TEESCPE 再取出第二个字母：HRIAIHR 连在一起就是：TEESCPEHRIAIHR 举例举例2: 明文明文: STRIKE WHILE THE IRON IS HOT 密钥密钥: PREDIC 密文密文:ETNE ILRO RIIH KEOT SWHI HTESSTRIKEWHILETHEIRONISHOTEPREDIC5632413.2 基本加密思想基本加密思想-一次一密一次一密 一次一密体制要求：1. 密钥是真正的随机序列2. 密钥长度至少等于明文长度3. 一个密钥只用一次 满足上述三个条件的密码系统是绝对安全的，不会被破译(香农在1949年已证明) 缺陷: 密钥的安全传

8、送,安全存放网络状态下同步密钥2021-7-163.2 基本加密思想基本加密思想 实例实例 贴吧-神秘的摩斯密码 最近和一个心仪的女生告白，谁知道她给了一个摩斯密码给我，说解出来了才答应和我约会。可是我用尽了所有方法都解不开这个密码。好郁闷阿。只能求教你们了。*-/*-/-*/*-/*-/*-/-*/*-/*-/*-/-*/*-/*-/*-/-*/*-/-*/*-/*-/*-/-*/*-/她唯一给我的提示就是这个是5层加密的密码.也就是说要破解5层密码才是答案.摩斯密码摩斯密码u 有两种“符号”用来表示字元：划（）和点（），或分别叫嗒（Dah）和滴（Dit）或长和短。u 点的长度决定了发报的速

9、度，并且被当作发报时间参考。u 划一般是三个点的长度；点划之间的间隔是一个点的长度；字元之间的间隔是三个点的长度；单词之间的间隔是七个点的长度。u Morse code： / / / / /第一步 摩尔斯解码：*-/*-/-*/*-/*-/*-/-*/*-/*-/*-/-*/*-/*-/*-/-*/*-/-*/*-/*-/*-/-*/*-/数字：4194418141634192622374 ： u第二步：手机按键码表 41 94 41 81 41 63 41 92 62 23 74 得到：G Z G T G O G X N C Su第三步：QWE键盘码表 QWERTYUIOPASDFGHJKL

10、ZXCVBNM ABCDEFGHIJKLMNOPQRSTUVWXYZ 得到：O T O E O I O U Y V Lu第四步：栅栏密码：（两排栅栏） O T O E O I O U Y V L 得到：O O T U O Y E V O L Iu第五步：倒序排列： 得到：I L O V E Y O U T O O （最终结果）3.3 加密算法的分类加密算法的分类1.对称加密算法l 加密密钥与解密密钥相同，又叫私有密钥算法。l 著名密码算法： DES/3DES数据加密标准 IDEA国际数据加密算法 RC系列(RC2, RC4, RC5) AES高级数据加密标准 等2.非对称加密算法l 加密密钥与

11、解密密钥不同 ，而且解密密钥不能根据加密密钥计算出来,又叫公有密钥算法l 著名密码算法： RSA加密算法 Diffie-Hellman加密算法 背包密码 椭圆曲线加密算法对称加密算法对称加密算法Strong cryptography makes the world a safer place!$#%$&*$#￥！#￥%*！#￥%&!$#%$&*$#￥！#￥%*！#￥%&Strong cryptography makes the world a safer place优点:加解密速度快缺点:密钥传送非常重要 密钥管理很复杂非对称加密算法原理非对称加密算法原理Str

12、ong cryptography makes the world a safer place!$#%$&*$#￥！#￥%*！#￥%&!$#%$&*$#￥！#￥%*！#￥%&Strong cryptography makes the world a safer placeu 又叫公钥密码算法。u 优点 安全性高 ,不需要安全信道来传送密钥u 缺点 算法复杂，加解密速度慢。非对称与对称加密算法相结合的加密方式非对称与对称加密算法相结合的加密方式 根据每次操作的数据单元是否分块划分 分组密码(block cipher):用一个固定的变换对等长分组进行处理 序列密码(s

13、tream cipher):用一个时变变换对明文进行逐个比特处理密钥源密钥源密钥序列 k0k1k2公开信道秘密信道密钥流产生器密钥流产生器密钥流产生器密钥流产生器KK密钥序列 k0k1k2明文序列m0m1m2明文序列m0m1m2密文序列 c0c1c2K为种子密钥，一般较短；密钥流发生器在K的控制下产生较长的密钥流 序列密码的优点： 1）处理速度快，实时性好； 2）错误传播小； 3）适用于军事、外交等保密信道。 序列密码的缺点： 1）明文扩散性差； 2）需要密钥同步。 序列密码的核心就是研究如何产生伪随机序列 真正的随机序列是很难得到的 伪随机序列的性质： 看起来是随机的 不可预测的 不能重复产

14、生 3.43.4 对称加密算法对称加密算法-DES-DES算法算法20世纪70年代, 由IBM公司发展出来1976年，DES被授权在美国政府非密级政府通信中使用1977年，DES作为美国联邦信息处理标准正式生效 ，是世界上一项最早被公认的实用的密码标准2000年10月2日，NIST公布了新的AES，DES作为标准正式结束密钥固定长度 ,只有56位以块模式对64bits的明文块进行操作DES算法的原理算法的原理 DES算法的入口参数有三个：Key、Data、ModeKey为8个字节共64位，是DES算法的工作密钥Data也为8个字节64位，是要被加密或被解密的数据Mode为DES的工作方式,有两

15、种：加密或解密。DES算法是这样工作的：如Mode为加密，则用Key去把数据Data进行加密，生成Data的密码形式（64位）作为DES的输出结果如Mode为解密，则用Key去把密码形式的数据Data解密，还原为Data的明码形式（64位）作为DES的输出结果。DES算法的实现步骤算法的实现步骤u加密过程如图所示。输入64位比特明文IP置换表L0R0Li = Ri-1 Ri = Lif(Ri-1,Ki)（i=1,2,16）迭代16次IP逆置换表输出64位比特密文四个关键点：1、IP置换表和IP逆置换表。2、函数f。3、子密钥Ki。4、S盒的工作原理。(1) IP置换表和置换表和IP逆逆置换表置

16、换表5850123426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725（2）函数）函数fu函数f有两个输入：32位的Ri-1和48位Ki。32位Ri-1E变换48位KiS1S7S6S5S4S

17、3S2S8P变换32位输出48位48位32位3212345456789891011121312131415161716171819202120212223242524252627282928293031321（3）子密钥kiu 。64位密钥字符串KPC1变换C0C16LS16D2LS2D0C2LS2D1C1LS1LS1D16LS16PC2变换PC2变换PC2变换48位K148位K1648位K256比特28比特28比特（4） S盒的工作原理盒的工作原理l 首先回顾一下S盒变换在函数f中的位置：32位Ri-1E变换48位KiS1S7S6S5S4S3S2S8P变换32位输出48位48位32位（4）S

18、盒的工作原理盒的工作原理 S盒以6位作为输入，而以4位作为输出，现在以S1为例说明其过程。 假设输入为A=a1 a2 a3 a4 a5 a6，则a2a3a4a5所代表的数是0到15之间的一个数，记为：k=a2a3a4a5； 由a1a6所代表的数是0到3间的一个数，记为h=a1a6。 在S1的h行（范围03），k列（范围015）找到一个数B，B在0到15之间，用4位二进制表示，为B=b1b2b3b4，这就是S1的输出。 练习：已知A101110 求 B0123456789101112131415014413121511831061259071015741421311061211953824114

19、81362111512973105031512824917511314100613kh一次关于DES的攻击测试: 1997年1月，美国RSA公司公布了一个“秘密密钥挑战” 竞赛项目：悬赏一万美元破解密钥长度为56比特的DES密码算法，以测试因特网上的分布式计算能力，并测试DES算法的相对安全程度。 竞赛规则： 明文开头是：“The unknow message is: ” 密钥是随机选取的； 明文和密钥都严加保密； 挑战者解出密钥后，用E-mail迅速向RSA公司报告，第一个解出者为胜利者。 密钥穷举攻击程序：由参赛者Rocke Verser设计，用于穷举所有可能的DES密钥。供其它参与者下载

20、和使用。 56位DES的全部密钥穷举量是：72,057,584,037,927,93672*1015 竞赛结果： 在RSA公布后的第140天，穷举攻击程序实施的第96天解出密钥和密文。 1997年6月17日晚10点39分，美国盐湖城iNet公司的职员Michael Sanders在其奔腾90Hz、16M内存的PC机上成功地解出了竞赛的密文。 密文：“The unknow message is: Strong Cryptography makes the world a safer place.” 密钥：85 58 89 la b0 c8 51 66 测试表明： 依靠因特网分布式计算能力，用密钥

21、穷举法破译DES成为可能。 随着计算能力的增长，必须增加密钥长度，才能更安全。密钥密钥长度长度密钥空间密钥空间穷举时间穷举时间401,099,511,627,77678秒秒485小时小时5672,057,594,037,927,93959天天6418,446,744,073,709,551,61641年年7210,696年年802,738,199年年88700,978,948年年96179,450,610,898年年11211,760,475,235,863,837年年128340,282,366,920,938,463,374,607,431,768,211,456770,734,505,0

22、57,572,442,069年年 3.5 3.5 非对称加密算法非对称加密算法-RSARSA算法算法u由MIT的 Rivest, Shamir & Adleman 在1978提出.u分组加密算法uRSA的安全性依赖于大数因子分解问题: a bn 容易na b 困难RSARSA算法密钥生成过程算法密钥生成过程( )(1)(1)npq( )een选取 ，且 与互素 mod ( )1dden寻找 ，满足17,11pq187,( )160npqn7e ( ) 1,123deknkd 公钥7, 187，私钥23, 1872,5, ()(10)(2 1)(5 1)4;pqpq1,3,7,94(10

23、)( )nnn欧拉函数：比 小且与 互素的正整数个数。pq(pq)(1)(1)pq若 和 是素数，那么已知公钥已知公钥e和和n，能够，能够破解出私钥破解出私钥d吗？吗？分组对应数字值设为分组对应数字值设为m, 加密加密将明文内容进行分组将明文内容进行分组,分分组长度组长度k满足满足RSARSA算法加解密过程算法加解密过程20logknmodecmn将密文将密文内容进行分组内容进行分组,分分组长度为组长度为kmoddcnm加加密密过过程程解解密密过过程程明文明文明文明文密文密文加密过程加密过程解密过程解密过程88m 788 mod18711c 11c 公钥公钥2311 mod 1878888m

24、私钥私钥相等吗？相等吗？分组长度分组长度k为什为什么要小于么要小于 2log nRSARSA安全性讨论安全性讨论2222409,401,164009405240516422405242pqnpqnpqpqnnpqpqRSARSA算法总结算法总结l 密钥生成过程l 加密过程:l 解密过程:l 程序演示( )(1)(1)npq( )een公选与钥取，且互素 mod ( )1d den寻找私钥 ，2021-7-16413.6 Diffie-Hellman密码体制密码体制 Diffie-Hellman 公钥密码系统出现在 RSA 之前，它实际是仍在使用的最古老的公钥系统。 由于该算法本身限于密钥交换的

25、用途，被许多商用产品用作密钥交换技术，因此又称之为Diffie-Hellman密钥交换。 这种密钥交换技术的目的在于使得两个用户安全地交换一个秘密密钥以便用于以后的报文加密。 DH密钥交换的安全性依赖于计算有限域中的离散对数问题。离散对数问题离散对数问题本原元(primitive element)：给定素数p，如果a是素数p的一个本原元，那么数值 a mod p, a2 mod p, ., ap-1 mod p 是各不相同的整数，并且以某种排列方式组成了从1到p-1的所有整数。离散对数：对于一个整数和素数p的一个本原元a，可以找到惟一的指数d，使得 = ad mod p，其中0 d (p-1)

26、，指数d称为的以a为基数的模p的离散对数或者指数。moddp2021-7-1645Diffie-HellmanDiffie-Hellman密钥交换密钥交换XAXBYAYBKA计计算算KB计计算算用户用户A用户用户B 公开公开公开公开秘密秘密秘密秘密会话秘密会话秘密会话秘密会话秘密 举例举例2021-7-1647Diffie-Hellman密钥交换密钥交换 Diffie-Hellman算法具有两个吸引力的特征： 对共享密钥提供的保护，能够抵抗来自于被动敌手（窃听者）的攻击 仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会。 除对全局参数的约定外，密钥交换不需要事先存在的基础

27、结构。 存在不足： 没有提供双方身份的任何信息。 它是计算密集性的，因此容易遭受阻塞性攻击，即对手请求大量的密钥。受攻击者花费了相对多的计算资源来求解无用的幂系数而不是在做真正的工作。 没办法防止重放攻击。 容易遭受中间人的攻击。2021-7-1648中间人攻击modBEX XBEK pBXBY = mod pBobAliceEveEXEY = mod pAXAY = mod pAlicemodAEX X p与协商的密钥：modAEX XAEK pEXEY =mod pBobmodBEX X p与协商的密钥：3.7 背包背包(Knapsack)密码密码u给定一组n个重量W0,W1,.,Wn-1

28、和一个总重量S,能否找到一组系数ai 0,1满足 S = a0W0+a1W1 +.+ an-1Wn-1u实例 重量(62,93,26,52,166,48,91,141) 问题：找到系数满足S=302 答案: 62+26+166+48=302 此处系数为（10101100）u已证明一般knapsack问题是NP-完全问题(非常难解)公钥密码49背包背包(Knapsack)问题问题u一般背包问题(GK)很难解决u但超递增背包问题(super-increasing knapsack) (SIK)很容易解决uSIK要求重量递增排列且每个重量比前面所有重量和还大u实例 重量(2,3,7,14,30,57,120,251) 问题: 找出子集满足和=186 从大到小逐步推算 答