第3章信息加密技术

第3章信息加密技术本章内容3.1加密技术的相关概念和术语.3.2加密的基本思想3.3加密技术的分类3.4对称加密算法—DES算法3.5非对称加密算法--RSA算法3.6Diffie-Hellman密码体制3.7背包密码3.1加密的相关概念明文(plaintext)：也叫纯文本,明码密文(ciphertext)：也叫密码文本算法(algorithm):加密和解密过程基于的某种数学程序,数学

变换.密钥(Key):加解密过程中,某些只被通信双方所掌握的专门的、关键的信息加密(encryption)解密(decryption)利用加密技术存储、传输信息，可提供安全保护功能机密性完整性不可否认性密码学的发展阶段第1阶段：1949年以前——古典密码学密码学还不是科学，而是艺术；出现一些简单的密码算法,加密设备,简单的密码分析手段；主要特点：数据的安全基于算法的保密第2阶段：1949~1975年——现代密码学密码学成为科学计算机使得基于复杂计算的密码成为可能主要特点:数据的安全基于密钥而不是算法的保密第3阶段：1975年以后——公钥密码学密码学的新方向——公钥密码学公钥密码使得发送端和接收端无密钥传输的保密通信成为可能。Kerchoffs假设：如果密码系统的强度依赖于攻击者不知道算法的内部机理，则该密码系统注定会失败。密码系统的安全性应该完全依赖于密钥的安全性.密码算法的安全性如果不论截取者获得了多少密文，但在密文中都没有足够的信息来惟一地确定出对应的明文，则这一密码体制称为无条件安全的，或称为理论上是不可破的。在无任何限制的条件下，目前几乎所有实用的密码体制均是可破的。因此，人们关心的是要研制出在计算上(而不是在理论上)是不可破的密码体制。如果一个密码体制中的密码不能被可以使用的计算资源破译，则这一密码体制称为在计算上是安全的。破译的代价超出信息本身的价值破译的时间超出了信息的有效期.3.2基本加密思想-替换替换：按照一定的规则,将明文中每一个字符用不同的密文字符代替。(1)移位替换

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

ci=fi(mi)=(mi+ki)mod26,其中ki为密钥,

i=0,1,…,t-1举例说明：k=(6,14,15,7,4,17),t=6m=meetmeintheallyaftermidnightm=meetmeintheallyaftermidnightc=sstaqvobioirrznhjkkfbpheouwaabcdefghijklmnopqrstuvwxyz0123456789101112131415161718192021222324253.2基本加密思想—易位易位:把明文中的字符重新排列，本身不变，但位置变了。栅栏密码，就是把要加密的明文分成N个一组，然后把每组的第i个字连起来，形成一段无规律的话。举例1明文：THEREISACIPHER

去掉空格后变为：THEREISACIPHER

两个一组，得到：THEREISACIPHER

先取出第一个字母：TEESCPE

再取出第二个字母：HRIAIHR

连在一起就是：TEESCPEHRIAIHR举例2:明文:

STRIKEWHILETHEIRONISHOT密钥:PREDIC

密文:ETNE

ILRORIIH

KEOT

SWHIHTESSTRIKEWHILETHEIRONISHOTEPREDIC5632413.2基本加密思想--一次一密一次一密体制要求：密钥是真正的随机序列密钥长度至少等于明文长度一个密钥只用一次

满足上述三个条件的密码系统是绝对安全的，不会被破译(香农在1949年已证明)缺陷:

密钥的安全传送,安全存放网络状态下同步密钥2023/2/63.2基本加密思想–实例贴吧-神秘的摩斯密码最近和一个心仪的女生告白，谁知道她给了一个摩斯密码给我，说解出来了才答应和我约会。可是我用尽了所有方法都解不开这个密码。。好郁闷阿。只能求教你们了。

****-/*----/----*/****-/****-/*----/---**/*----/****-/*----/-****/***--/****-/*----/----*/**---/-****/**---/**---/***--/--***/****-/

她唯一给我的提示就是这个是5层加密的密码.

也就是说要破解5层密码才是答案.摩斯密码有两种“符号”用来表示字元：划（—）和点（·），或分别叫嗒（Dah）和滴（Dit）或长和短。点的长度决定了发报的速度，并且被当作发报时间参考。划一般是三个点的长度；点划之间的间隔是一个点的长度；字元之间的间隔是三个点的长度；单词之间的间隔是七个点的长度。Morsecode：——

/———/·—·/···/·

//—·—·/———/—··/·第一步摩尔斯解码：****-/*----/----*/****-/****-/*----/---**/*----/****-/*----/-****/***--/****-/*----/----*/**---/-****/**---/**---/***--/--***/****-/数字：4194418141634192622374

：

第二步：手机按键码表

4194418141634192622374得到：GZGTGOGXNCS第三步：QWE键盘码表

QWERTYUIOPASDFGHJKLZXCVBNM

ABCDEFGHIJKLMNOPQRSTUVWXYZ得到：OTOEOIOUYVL第四步：栅栏密码：（两排栅栏）

OTOEO

I

OUYVL得到：OOTUOYEVOLI第五步：倒序排列：得到：ILOVEYOUTOO（最终结果）3.3加密算法的分类对称加密算法加密密钥与解密密钥相同，又叫私有密钥算法。著名密码算法：DES/3DES数据加密标准IDEA国际数据加密算法RC系列(RC2,

RC4,

RC5)AES高级数据加密标准等非对称加密算法加密密钥与解密密钥不同，而且解密密钥不能根据加密密钥计算出来,又叫公有密钥算法著名密码算法：RSA加密算法Diffie-Hellman加密算法背包密码椭圆曲线加密算法对称加密算法Strongcryptographymakestheworldasaferplace!@$#^%$&*$#￥@！#￥%*！@#￥%&!@$#^%$&*$#￥@！#￥%*！@#￥%&Strongcryptographymakestheworldasaferplace优点:加解密速度快缺点:密钥传送非常重要密钥管理很复杂非对称加密算法原理Strongcryptographymakestheworldasaferplace!@$#^%$&*$#￥@！#￥%*！@#￥%&!@$#^%$&*$#￥@！#￥%*！@#￥%&Strongcryptographymakestheworldasaferplace又叫公钥密码算法。优点安全性高,不需要安全信道来传送密钥缺点算法复杂，加解密速度慢。非对称与对称加密算法相结合的加密方式根据每次操作的数据单元是否分块划分分组密码(blockcipher):用一个固定的变换对等长分组进行处理序列密码(streamcipher):用一个时变变换对明文进行逐个比特处理密钥源密钥序列k0k1k2…公开信道秘密信道密钥流产生器密钥流产生器KK密钥序列k0k1k2…明文序列m0m1m2…明文序列m0m1m2…密文序列c0c1c2…K为种子密钥，一般较短；密钥流发生器在K的控制下产生较长的密钥流序列密码的优点：1）处理速度快，实时性好；2）错误传播小；3）适用于军事、外交等保密信道。序列密码的缺点：1）明文扩散性差；2）需要密钥同步。序列密码的核心就是研究如何产生伪随机序列真正的随机序列是很难得到的伪随机序列的性质：看起来是随机的不可预测的不能重复产生

3.4对称加密算法--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的工作方式,有两种：加密或解密。DES算法是这样工作的：如Mode为加密，则用Key去把数据Data进行加密，生成Data的密码形式（64位）作为DES的输出结果如Mode为解密，则用Key去把密码形式的数据Data解密，还原为Data的明码形式（64位）作为DES的输出结果。DES算法的实现步骤加密过程如图所示。四个关键点：1、IP置换表和IP逆置换表。2、函数f。3、子密钥Ki。4、S盒的工作原理。(1)

IP置换表和IP逆置换表5850123426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725（2）函数f函数f有两个输入：32位的Ri-1和48位Ki。3212345456789891011121312131415161716171819202120212223242524252627282928293031321（3）子密钥ki。（4）S盒的工作原理首先回顾一下S盒变换在函数f中的位置：（4）S盒的工作原理S盒以6位作为输入，而以4位作为输出，现在以S1为例说明其过程。假设输入为A=a1a2a3a4a5a6，则a2a3a4a5所代表的数是0到15之间的一个数，记为：k=a2a3a4a5；由a1a6所代表的数是0到3间的一个数，记为h=a1a6。在S1的h行（范围0～3），k列（范围0～15）找到一个数B，B在0到15之间，用4位二进制表示，为B=b1b2b3b4，这就是S1的输出。练习：已知A＝101110求B012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613kh一次关于DES的攻击测试:

1997年1月，美国RSA公司公布了一个“秘密密钥挑战”竞赛项目：悬赏一万美元破解密钥长度为56比特的DES密码算法，以测试因特网上的分布式计算能力，并测试DES算法的相对安全程度。竞赛规则：明文开头是：“Theunknowmessageis:”

密钥是随机选取的；明文和密钥都严加保密；挑战者解出密钥后，用E-mail迅速向RSA公司报告，第一个解出者为胜利者。密钥穷举攻击程序：由参赛者RockeVerser设计，用于穷举所有可能的DES密钥。供其它参与者下载和使用。

56位DES的全部密钥穷举量是：72,057,584,037,927,936≈72*1015竞赛结果：在RSA公布后的第140天，穷举攻击程序实施的第96天解出密钥和密文。1997年6月17日晚10点39分，美国盐湖城iNet公司的职员Michael

Sanders在其奔腾90Hz、16M内存的PC机上成功地解出了竞赛的密文。密文：“Theunknowmessageis:StrongCryptographymakestheworldasaferplace.”密钥：855889lab0c85166测试表明：①依靠因特网分布式计算能力，用密钥穷举法破译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,057,572,442,069年3.5非对称加密算法--RSA算法由MIT的Rivest,Shamir&Adleman在1978提出.分组加密算法RSA的安全性依赖于大数因子分解问题:

计算n=pq，公钥{e，n}，私钥{d，n}RSA算法密钥生成过程选取两个不同的素数p和q公钥{7,187}，私钥{23,187}已知公钥e和n，能够破解出私钥d吗？分组对应数字值设为m,加密将明文内容进行分组,分组长度k满足RSA算法加解密过程解密将密文内容进行分组,分组长度为k加密过程解密过程明文明文密文加密过程解密过程公钥私钥相等吗？分组长度k为什么要小于RSA安全性讨论RSA算法总结密钥生成过程加密过程:

c=memodn解密过程:

m=cdmodn程序演示计算n=pq，公钥{e，n}，私钥{d，n}选取两个不同的素数p和q2023/2/6413.6

Diffie-Hellman密码体制Diffie-Hellman

公钥密码系统出现在RSA之前，它实际是仍在使用的最古老的公钥系统。由于该算法本身限于密钥交换的用途，被许多商用产品用作密钥交换技术，因此又称之为Diffie-Hellman密钥交换。这种密钥交换技术的目的在于使得两个用户安全地交换一个秘密密钥以便用于以后的报文加密。DH密钥交换的安全性依赖于计算有限域中的离散对数问题。离散对数问题本原元(primitiveelement)：给定素数p，如果a是素数p的一个本原元，那么数值

amodp,a2modp,...,ap-1modp是各不相同的整数，并且以某种排列方式组成了从1到p-1的所有整数。离散对数：对于一个整数β和素数p的一个本原元a，可以找到惟一的指数d，使得

β=admodp，其中0≤d≤(p-1)，指数d称为β的以a为基数的模p的离散对数或者指数。2023/2/6451.基本原理Diffie-Hellman密钥交换XAXBYAYBKA计算KB计算用户A用户B

公开公开秘密秘密会话秘密会话秘密

密钥交换过程

举例例：为了计算简单，使用很小数字。设P=47,以及47的一个本原元a=3，A选择秘密密钥XA=8，B选择秘密密钥XB=10。（1）双方各自计算其公开密钥用户A计算：YA=38mod47=6561mod47=28mod47用户B计算：YB=310mod47=59049mod47=17mod47（2）交换YA和YB；（3）交换密钥后，A、B分别计算共享的秘密会话密钥KA、KB：用户A计算：KA=YBXAmod47=178mod47=4

mod47用户B计算：KB=YAXBmod47=2810mod47=4

mod47A和B双方独立地决定采用4作为会话密钥。2023/2/647Diffie-Hellman密钥交换Diffie-Hellman算法具有两个吸引力的特征：对共享密钥提供的保护，能够抵抗来自于被动敌手（窃听者）的攻击仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会。除对全局参数的约定外，密钥交换不需要事先存在的基础结构。存在不足：没有提供双方身份的任何信息。它是计算密集性的，因此容易遭受阻塞性攻击，即对手请求大量的密钥。受攻击者花费了相对多的计算资源来求解无用的幂系数而不是在做真正的工作。没办法防止重放攻击。容易遭受中间人的攻击。2023/2/648中间人攻击BobAliceEve3.7背包(Knapsack)密码给定一组n个重量W0,W1,...,Wn-1和一个总重量S,能否找到一组系数ai

{0,1}满足

S=a0W0+a1W1+...+an-1Wn-1实例

重量(62,93,26,52,166,48,91,141)问题：找到系数满足S=302答案:62+26+166+48=302此处系数为（10101100）已证明一般knapsack问题是NP-完全问题(非常难解)公钥密码49背包(Knapsack)问题一般背包问题(GK)很难解决但超递增背包问题(super-increasingknapsack)

(SIK)很容易解决SIK要求重量递增排列且每个重量比前面所有重量和还大实例重量(2,3,7,14,30,57,120,251)

问题:找出子集满足和=186从大到小逐步推算…