信息安全-三-信息安全密码学课件.pptx

1、密码学的基本概念密码学的基本概念是经过伪装后的明文是经过伪装后的明文c。全体可能出现的密文集合称。全体可能出现的密文集合称为为密文空间密文空间C密文密文未经过加密的原始信息称为明文未经过加密的原始信息称为明文m，明文的全体称，明文的全体称为为明文空间明文空间 M明文明文由明文空间、密文空间、密码方案和密钥空间组由明文空间、密文空间、密码方案和密钥空间组成成密码密码系统系统密码学的基本概念(2)加密和解密算法的操作在称为密钥（加密和解密算法的操作在称为密钥（k）的元素控）的元素控制下进行。密钥的全体称为制下进行。密钥的全体称为密钥空间（密钥空间（K）密钥密钥确切地描述了加密变换和解密变换的具体规

2、则确切地描述了加密变换和解密变换的具体规则密码密码方案方案加密算法加密算法对明文进行加密时所使用的规对明文进行加密时所使用的规则的描述则的描述(m)解密算法解密算法对密文进行还原时所使用的规对密文进行还原时所使用的规则则D(c)2022-12-114密码学的发展历程密码学密码学是一门古老而深奥的学科，是结合数学、计算机科学、电子与是一门古老而深奥的学科，是结合数学、计算机科学、电子与通信等诸多学科于一体的交叉学科，是研究信息系统安全保密的一门通信等诸多学科于一体的交叉学科，是研究信息系统安全保密的一门科学。密码学主要包括密码编码学和密码分析学两个分支，其中密码科学。密码学主要包括密码编码学和密

3、码分析学两个分支，其中密码编码学的主要目的是寻求保证信息保密性或仁整形的方法，密码分析编码学的主要目的是寻求保证信息保密性或仁整形的方法，密码分析学的主要目的是研究加密消息的破译或消息的伪造。密码学经历了从学的主要目的是研究加密消息的破译或消息的伪造。密码学经历了从古代密码学到现代密码学的演变。古代密码学到现代密码学的演变。2022-12-115最早将现代密码学概念运用于实际的是最早将现代密码学概念运用于实际的是CaesarCaesar大帝，他是古罗马帝国末期著名的统帅和政治大帝，他是古罗马帝国末期著名的统帅和政治家。家。CaesarCaesar发明了一种简单的加密算法把他的信息加密用于军队传

4、递，后来被称为发明了一种简单的加密算法把他的信息加密用于军队传递，后来被称为CaesarCaesar密密码。它是将字母按字母表的顺序排列，并且最后一个字母与第一个字母相连。加密方法是将码。它是将字母按字母表的顺序排列，并且最后一个字母与第一个字母相连。加密方法是将明文中的每个字母用其后边的第三个字母代替，就变成了密文。明文中的每个字母用其后边的第三个字母代替，就变成了密文。替代密码的基本思想，是将明文中的每个字母用此字符在字母表中后面第替代密码的基本思想，是将明文中的每个字母用此字符在字母表中后面第 k k个字母替代，加个字母替代，加密过程可以表示为函数密过程可以表示为函数E(m)=(m+k)

5、mod nE(m)=(m+k)mod n。其中：。其中：m m 为明文字母在字母表中的位置数，为明文字母在字母表中的位置数，n n 为为字母表中的字母个数，字母表中的字母个数，k k 为密钥，为密钥，E(m)E(m)为密文字母在字母表中对应的位置数。其解密过程可为密文字母在字母表中对应的位置数。其解密过程可以表示为函数以表示为函数E(m)=(m-k)mod nE(m)=(m-k)mod n。置换密码的基本思想，不改变明文字符，只是将字符在明文中的排列顺序改变，从而实现明置换密码的基本思想，不改变明文字符，只是将字符在明文中的排列顺序改变，从而实现明文信息的加密，又称为换位密码。矩阵换位法是实现

6、置换密码的一种常用方法，它将明文中文信息的加密，又称为换位密码。矩阵换位法是实现置换密码的一种常用方法，它将明文中的字母按照给的顺序安排在一个矩阵中，然后根据密钥提供的顺序重新组合矩阵中字母，从的字母按照给的顺序安排在一个矩阵中，然后根据密钥提供的顺序重新组合矩阵中字母，从而形成密文。而形成密文。明文abcdefghijklm密文DEFGHIJKLMNOP明文nopqrstuvwxyz密文QRSTUVWXYZABC2022-12-116第一阶段：古代第一阶段：古代19491949年年这阶段的密码技术可以说是一种艺术，而不是一种科学，密码学专家常常是凭知觉和这阶段的密码技术可以说是一种艺术，而不

7、是一种科学，密码学专家常常是凭知觉和信念来进行密码设计和分析，而不是推理和证明，没有形成密码学的系统理论。这一信念来进行密码设计和分析，而不是推理和证明，没有形成密码学的系统理论。这一阶段设计的密码称为经典密码或古典密码，并且密码算法在现代计算机技术条件下都阶段设计的密码称为经典密码或古典密码，并且密码算法在现代计算机技术条件下都是不安全的。是不安全的。第二阶段：第二阶段：1949197519491975年年19491949年年C.E.ShannonC.E.Shannon（香农）发表在（香农）发表在贝尔实验室技术杂志贝尔实验室技术杂志上的上的保密系统的信息保密系统的信息理论（理论（Commun

8、ication Theory of Secrecy SystemCommunication Theory of Secrecy System）为私钥密码体系（对称加密）为私钥密码体系（对称加密）建立了理论基础，从此密码学成为一门科学。图建立了理论基础，从此密码学成为一门科学。图3-33-3为为ShannonShannon提出的保密通信模型。提出的保密通信模型。密码学直到今天仍具有艺术性，是具有艺术性的一门科学。这段时期密码学理论的研密码学直到今天仍具有艺术性，是具有艺术性的一门科学。这段时期密码学理论的研究工作进展不大。究工作进展不大。19671967年年David KahnDavid Kah

9、n发表了发表了The Code Breakers(The Code Breakers(破译者破译者)一书，一书，详尽地阐述了密码学的发展和历史，使人们开始了解和接触密码。详尽地阐述了密码学的发展和历史，使人们开始了解和接触密码。19761976年，年，PfisterPfister（菲斯特）和美国国家安全局（菲斯特）和美国国家安全局NSANSA（National Security AgencyNational Security Agency）一起制定了数据加）一起制定了数据加密标准（密标准（Data Encryption StandardData Encryption Standard，DESD

10、ES），这是一个具有深远影响的分组密码算），这是一个具有深远影响的分组密码算法。法。2022-12-117第三阶段：第三阶段：19761976年到年到 19761976年年DiffieDiffie和和HellmanHellman发表的文章发表的文章“密码学发展的新方向密码学发展的新方向”导致了导致了密码学上的一场革命，他们首先证明了在发送端和接收端无密钥传输密码学上的一场革命，他们首先证明了在发送端和接收端无密钥传输的保密通信是可能的，从而开创了公钥密码学的新纪元。从此，密码的保密通信是可能的，从而开创了公钥密码学的新纪元。从此，密码开始充分发挥它的商用价值和社会价值。开始充分发挥它的商用价值

11、和社会价值。19781978年，在年，在ACMACM通信中，通信中，RivestRivest、ShamirShamir和和AdlemanAdleman公布了公布了RSARSA密码体系，这是第一个真正实用密码体系，这是第一个真正实用的公钥密码体系，可以用于公钥加密和数字签名。由于的公钥密码体系，可以用于公钥加密和数字签名。由于RSARSA算法对计算法对计算机安全和通信的巨大贡献，该算法的算机安全和通信的巨大贡献，该算法的3 3个发明人因此获得计算机界个发明人因此获得计算机界的诺贝尔奖的诺贝尔奖图灵奖（图灵奖（A.M.Turing AwardA.M.Turing Award）。在）。在EuroCr

12、ypt91EuroCrypt91年会年会上，中国旅居瑞士学者来学嘉（上，中国旅居瑞士学者来学嘉（X.J.LaiX.J.Lai）和）和James L.MasseyJames L.Massey提出了提出了IDEAIDEA，成为分组密码发展史上的又一个里程碑，成为分组密码发展史上的又一个里程碑。保密通信系统的基本模型加密算法加密算法解密算法解密算法密码分析者密码分析者加密密钥加密密钥Ke解密密钥解密密钥Kd窃听窃听干扰干扰明文明文m明文明文m密文密文c有了密钥的概念后，加密的过程：有了密钥的概念后，加密的过程：c=EKe(m)，解密的过程，解密的过程:m=DKd(c)，其中，其中mM，cC密码体制的

13、分类 1.按照密码的发展历史分类密码可分为古典密码和近现代密码 2.按照需要保密的内容分类 根据密码体制的密码算法是否需要保密，可分为受限制的算法（算法的保密基于保持算法的秘密）和基于密钥的算法（算法的保密性仅仅基于对密钥的保密）1883年Kerchoffs第一次明确提出了编码的原则，即加密算法应建立在算法的公开不影响明文和密钥的安全的基础上 密码体制的分类 3.根据加密算法和解密算法所使用的密钥是否相同分类 对称密码体制 公钥密码体制：也称为非对称密码体制 4.根据对明文的处理方式 分组密码算法和流密码算法 5.根据是否能进行可逆的加密变换分为单向函数密码体制和双向变换密码体制 对称密码体制

14、对称密码体制 对称密码体制对称密码体制Symmetric Key Cryptosystem加密密钥加密密钥=解密密钥解密密钥密钥必须保密密钥必须保密公钥密码体制公钥密码体制公钥密码体制公钥密码体制Public Key Cryptosystem加密密钥加密密钥解密密钥解密密钥 加密密钥为公钥（加密密钥为公钥（Public Key），公钥无需保密），公钥无需保密 解密密钥为私钥（解密密钥为私钥（Private Key）密码分析与密码系统的安全性密码系统的安全性取决于密码系统的安全性取决于(1)所使用的密码算法的保密强度所使用的密码算法的保密强度(2)密码算法以外不安全的因素密码算法以外不安全的因素

15、因此必须同时完善技术与管理上的要求，才能保证整个密码因此必须同时完善技术与管理上的要求，才能保证整个密码系统的安全系统的安全密码分析研究如何分析和破解密码密码分析研究如何分析和破解密码密码分析-穷举 拦截了密文 UVACLYFZLJBYL K=1 明文=tuzbkxeykiaxk K=2 明文=styajwdxjhzwj K=3 明文=rsxzivcwigyvi K=4 明文=qrwyhubvhfxuh K=5 明文=pqvxgtaugewtg K=6 明文=opuwfsztfdvsf K=7 明文=notverysecure 则密钥为7密码分析-统计 密文 XLILSYWIMWRSAJSVW

16、EPIJSVJSYVQMPPMSRHSPPEVWMXMWASVX-LQSVLY-VVCFIJSVIXLIWIPPIVVIGIMZIWQSVISJJIVW 频率分析：I 14 V 13 S 12,推测i为英文中统计频率最高的e,则k=4,解密后明文：The house is now for sale for million dollars it is worth more hurry before the seller receives more offers模运算 A=q*n+r n正数,r非负，则a mod n=r 求模：27 mod 5 36 mod 12-18 mod 14-7 mod

17、10逆元 A+b0(mod n)a,b 为加法逆 A*b 1(mod n)a,b为乘法逆 A,b为0-n之间的整数求解过程 Gcd(a,b)R1=a,r2=b;s1=1,s2=0;t1=0;t2=1;While(r20)Q=r1/r2;R=r1-q*r2;r1=r2;r2=r;S=s1-q*s2;s1=s2;s2=s;T=t1-q*t2;t1=t2;t2=t;gcd(a,b)=r1;s=s1;t=t1 s*a+t*b=r1;表格帮助理解算法QR1R2RS1S2ST1T2T5161282110101-512821701-11-56321701-14-562370-14623线性丢番图方程 Ax+

18、by=c 设d=gcd(a,b),c%d!=0则无解，c%d=0则无穷个解 有解，求出s,t 1 特解x0=(c/d)*s,y0=(c/d)*t 2 通解 x=x0+k(b/d)y=y0-k(a/d)k为整数 解决问题：100元换成20元和5元的组合，用本方法求解扩展欧几里得算法求逆元 Gcd(n,a)=1，则存在逆元 N=26 a=11 则存在逆元。找寻11对26中的乘法逆元：N=100 a=23求解过程 12对26的乘法逆qr1r2rt1t2T22611401-2211431-251431-25-733105-72610726单变量线性方程 ax b(mod n)设d=gcd(a,n)如果

19、d mod b=0 有d个解，d mod b!=0 无解 1 方程两边同除以d 简化方程 2 简化后的方程两边同乘以a的乘法逆，求得特解x0 3 x=x0+k(n/d)k=0,1,(d-1)练习：10 x 2(mod 15)14x 12(mod 18)仿射密码示例仿射密码示例Alice与与Bob事先协定一把密钥事先协定一把密钥K=(3,8)其中其中gcd(3,26)=1E(.)maffine(0,5,5,8,13,4)(8,23,23,6,21,20)IXXGVUc E(m)3m8(mod26)1D(c)3(c8)9(c8)(mod26)D(.)cIXXGVU(8,23,23,6,21,20)

20、(0,5,5,8,13,4)affinem 仿射密码的选择明文攻击 截获密文：PWUFFOGWCHFDWIWEJOUUNJORSMDWRHVCMWJUPVCCG 1明文et-WC 2明文et-WF 对于4-22 19-2 带入方程，4*k1+k2 22(mod 26)19*k1+k2 2(mod 26)求得k1=16 k2=10 k1=16乘法不可逆，因此不是合理答案 对于04-22 19-5 带入 4*k1+k2 22(mod 26)19*k1+k2 2(mod 26)k1对26乘法可逆，进行解密得到 Best time of the year is spring when flowers

21、bloom对单表加密算法的统计分析对单表加密算法的统计分析字母百分比字母百分比a8.2n6.8b1.5o7.5c2.8p1.9d4.2q0.1e12.7r6.0f2.2s6.3g2.0t9.0h6.1u2.8i7.0v1.0j0.1w2.4k0.8x2.0l4.0y0.1m2.4z0.1另外最常出现的双字母组合为：另外最常出现的双字母组合为：th(3.15%)，he(2.51%)，an(1.72)，in(1.69%)，er(1.54%)，re(1.48%)，es(1.45%)，on(1.45%)，ea(1.31%)，ti(1.28)，at(1.24%)，st(a.21%)，en(1.20%)，

22、nd(1.18%)等。等。最常出现的三字母组合（最常出现的三字母组合（Trigram）为：为：the，ing，and，her，ere，ent，tha，。维吉尼亚（Vigenere）密码 维吉尼亚密码：一种典型的多表替代密码，该密码体制有一个参数n，表示采用n位长度的字符串（例如一个英文单词）作为密钥。设密钥k=k1k2kn，明文M=m1m2mn，则加密变换为：Ek(m1,m2,mn)=(m1+k1mod 26,m2+k2mod 26,mn+knmod 26)维吉尼亚密码举例 例 设明文为“killthem”密钥为“gun”，试用维吉尼亚密码对明文进行加密。加密密钥：k=gun=(6,20,13

23、)明文对应的数字为明文对应的数字为 1081111197412密钥对应的数字密钥对应的数字6201362013620相加取余变换后：相加取余变换后：16224171320106对应的密文是：对应的密文是：qcyrnvkg因因 密文为：密文为：qcyrvkg维吉尼亚密码分析 不保存频率，需要先求出密钥长度，再求出密钥 http:/ 1 求密钥长度,密文：LIONWGFGEGGDVWGHHCQUCRHRWAGWIOWQLKZETKKMEVLWPCZVGTHVTSGXQOVGCSVETQLTJSUMVWVEUVLXEWSLGFZMVVWLGYHCUSWXQHKVGSHEEVFLCFDGVSUMPHK

24、IRZDMPHHBVWVWJWIXGFWLTSHGJOUEEHHVUCFVGOWICQLTJSUXGLW 找到串索引位置，求出差：JSU 68 168 差100 SUM 69 117 差48 VWV 72 132 60 MPH 119 127 8 差的最大公约数为4，密钥为4的倍数，首先尝试一下4，获得几个子串，c1由1,5,9组成,c2由2,6,10,组成，每个片段分别用统计攻击,以便得到明文片段。如果明文还不清楚，尝试8,12HILL希尔密码 密钥为一个矩阵 解密密钥为矩阵的逆矩阵希尔密码 希尔密码：利用矩阵变换来对信息实现加密。数学定义：设m是一个正整数，令M=E=(Z26)m，密钥Km

25、m=定义在Z26上的mm矩阵，其中K的行列式值必须和26互素，否则不存在K的逆矩阵K-1。对任意的密钥Kmm，定义加密/解密变换为Ek(x)=Kmmx mod 26Dk(y)=K-1mmy mod 26希尔（希尔（HillHill）密码举例）密码举例首先决定所用矩阵的大小，譬如是首先决定所用矩阵的大小，譬如是2211E34其中其中E的行列式值的行列式值detE必须与必须与26互质，否则不存在互质，否则不存在E的反矩阵。的反矩阵。m=Hillhl711Mil81111711EM3 481115 2253 7715 22(mod 26)12515 22pwC125bzc=pbwzHill密码解密过

26、程密码解密过程计算加密矩阵的反矩阵，再进行模运算（计算加密矩阵的反矩阵，再进行模运算（mod 26），），得解密矩阵得解密矩阵41D(mod 26)314115 22EM3112559534441711(mod 26)811hlil 希尔密码分析 假定知道m，并且有m个分组的明文密文对，就可以对密码进行已知明文攻击 创建两个mXm的矩阵明文P和密文C，C=PK K=CP-1.如果不知道m，m不大，也可以进行尝试.假设m=3，已知三个明文密文对 05 07 10-03 06 00 13 17 07-14 16 09 00 05 04-03 17 11 K=p-1C 先求得P的逆矩阵，然后乘积得到

27、K 21 14 01 03 06 00 02 03 07 00 08 25 X 14 16 09 =05 07 09 13 03 08 03 17 11 01 02 11通俗解释：离散对数 欧拉定理指出如果gcd(a,n)=1，则a(n)1 mod n。现在考虑如下的一般形式：am1 mod n 如果a与n互素，则至少会有一整数m（比如m=(n)）满足这一方程。称满足方程的最小正整数m为模n下a的阶。例如：a=7，n=19，则易求出717 mod 19，7211 mod 19，731 mod 19，即7在模19下的阶为3。本原根 定理 设a的阶为m，则ak1 mod n的充要条件是k为m的倍数

28、。推论：a的阶m整除(n)。如果a的阶m等于(n)，则称a为n的本原根。如果a是n的本原根，则a,a2,a(n)在mod n下互不相同且都与n互素。特别地，如果a是素数p的本原根，则a,a2,ap-1在 mod p下都不相同。N=8 求阶ai x123456711111111331313135515151577171717i=（8）=4，ai mod 8 的结果表。的结果表。Ord(1)=1,ord(3)=ord(5)=ord(7)=2本原根 n=7ai x123456111111122412413326451442142155462316616161本本原根为原根为3，5推论：存在本原根，则

29、本源根的数目为推论：存在本原根，则本源根的数目为(n)本原根举例 例如：n=9，则(n)=6，考虑2在mod 9下的幂21 mod 92，22 mod 94，23 mod 98，24 mod 97，25 mod 95，26 mod 91。即2的阶为6，正好等于(9)，所以2为9的本原根。离散对数 计算bak mod p p=19 本原根前提下，对于任意b1,p-1，都有且仅有唯一的正整数k与b对应，使得bak mod p，也就是说b和k之间是一一对应的关系。称k为模p下以a为底b的离散对数，记为klogab(mod p)3133293383453515367372386391831016311

30、10312113131431443151231617317133181离散对数的这一特点保证了任意一个明文（密文）字符都有且仅有唯一的密文离散对数的这一特点保证了任意一个明文（密文）字符都有且仅有唯一的密文（明文）字符与之对应（明文）字符与之对应离散对数举例 如p=7,存在本原根3，5 取3，则存在b，k对：3-1 2-2 6-3 4-4 5-5 1-6离散对数难题 当a、k、p已知时，可有快速算法比较容易地求出b的值；但如果已知b、a和p时，要求k的值，对于小心选择的p将至少需要p1/2次以上的运算，如果p足够大，求解离散对数问题是相当困难的，这就是著名的离散对数难题。由于离散对数问题具有较

31、好的单向性，所以离散对数问题在公钥密码学中得到广泛应用。像EIGamal、Diffie-Hellman、DSA等密码算法都是建立在离散对数问题之上的 中国电建昆明院RSA算法的过程：密钥产生 找素数 选取两个大的随机的素数p，q 计算模n和Euler函数(n)npq(n)=(p-1)(q-1)找ed1 mod(n)随机取一个数e(与(n)互素)，用扩展Euclid算法求d即可 发布 d保密，(d,n)是私钥 Ks 发布(e,n)，这是公钥Kp 销毁p、qRSA的简单例子任选两个素数任选两个素数 p7，q17 npq(n)请练习请练习任务：对明文任务：对明文 M=19 加密加密 npq119(n

32、)(p-1)(q-1)61696选取整数选取整数1e(n)与与(n)互素：互素：e5求求e的逆元的逆元d：ed1 mod(n)请练习请练习计算计算 C=Me(mod n)=?其中其中M=19 请练习请练习 计算计算 M=Cd(mod n)=?请练习请练习 d=77c=66练习 p=3，q=11 对bnuz进行加密 2 14 21 26 如果Alice和Bob想在不安全的信道上交换密钥，他们可以采用如下步骤：(1)Alice和Bob协商一个大素数p及p的本原根a，a和p可以公开；(2)Alice秘密产生一个随机数x，计算X=ax mod p，然后把X发送给Bob；(3)Bob秘密产生一个随机数y

33、，计算Y=ay mod p，然后把Y发送给Alice；(4)Alice计算k=Yx mod p；(5)Bob计算k=Xy mod p。k和k是恒等的，因为k=Yx mod p=(ay)x mod p=(ax)y mod p=Xy mod p=k 线路上的搭线窃听者只能得到a、p、X和Y的值，除非能计算离散对数，恢复出x和y，否则就无法得到k，因此，k为Alice和Bob独立计算的秘密密钥。下面用一个例子来说明上述过程。Alice和Bob需进行密钥交换，则：两人协商后决定采用素数p=353及其本原根a=3。Alice选择随机数x=97，计算X=397 mod 35340，并发送给Bob。Bob选

34、择随机数y=233，计算Y=3233 mod 353248，并发送给Alice。Alice计算k=Yx mod p24897 mod 353=160。Bob计算k=Xy mod p40233 mod 353=160。k和k(160)即为秘密密钥。Diffie-Hellman密钥交换 Bob和Alice都不关心最终的密钥到底是什么 Bob和Alice相互之间都不分享他们各自的保密数 攻击者能够得到g、p以及值ga mod p和gb mod p，而得到k的唯一办法是计算出a和b，这等价于求解离散对数问题Dh密钥交换密钥交换Diffie-Hellman的参数选择(1)素数p必须要非常大(多于300个

35、十进制数位)。(2)素数p的选择必须要使得p1具有至少一个大的素因子(多于60个十进制数位)。(3)生成元必须要从群中选择。(4)Alice和Bob算出对称密钥后，必须立即销毁x 和 y。x 和 y的值只能使用一次2 中间人攻击 Diffie-Hellman密钥交换容易遭受中间人攻击：(1)Alice发送公开值(a和p)给Bob，攻击者Carol截获这些值并把自己产生的公开值发送给Bob。(2)Bob发送公开值给Alice，Carol截获它然后把自己的公开值发送给Alice。(3)Alice和Carol计算出二人之间的共享密钥k1。(4)Bob和Carol计算出另外一对共享密钥k2。造 成 中

36、 间 人 攻 击 的 原 因 是 D i f f i e-Hellman密钥交换不认证对方，没有对公钥的合法性进行验证，利用数字签名可以挫败中间人攻击。公钥密码算法解决的问题 为什么需要公钥密码算法呢，它可解决以下问题w 密钥分配 w 密码系统密钥管理问题 w 数字签名问题不可逆加密体制 不可逆加密体制又称为单向密码体制，它是一种从明文到密文的不可逆变换，通常在明文到密文的转换中存在信息的损失，因此密文无法恢复成明文，实现不可逆密码体制的方法是通过单向散列函数。单向散列函数用于某些只需要加密、不需要解密的特殊场合，例如:文件完整性保证 口令存储单向散列函数的性质 函数的输入（明文）可以是任意长

37、度；函数的输出（密文）是固定长度的；已知明文m，求H(m)较为容易，可用硬件或软件实现；已知散列值h，求使得H(m)=h的明文m在计算上是不可行的，这一性质称为函数的单向性，称H(m)为单向散列函数；散列函数具有防伪造性（又称弱抗冲突性），即已知m，找出m(mm)使得H(m)=H(m)在计算上是不可行的；散列函数具有很好的抵抗攻击的能力（又称强抗冲突性），即找出任意两个不同的输入x、y，使得H(y)=H(x)在计算上是不可行的。单向散列函数的性质和种类 提示：强抗冲突性自然包含弱抗冲突性。第和第个条件给出了散列函数无碰撞性的概念，如果散列函数对不同的输入可产生相同的输出，则称该函数具有碰撞性c

38、ollision。常见的单向散列函数有MD5和SHA-1，散列函数的安全性主要来源于它的单向性。散列函数算法被破解的含义 MD5的散列码长度是128比特，而SHA-1的散列码长度是160比特。近年来有报道称已可以在24小时内找到MD5的一个冲突，使得MD5对于不同的输入有相同的输出结果，因此说MD5算法已经被破解。注意：说MD5算法被破解，只是说可以通过密文找到与明文有相同散列值的一个碰撞，而绝不是说可以将MD5算法加密的密文还原成明文。2 对散列函数的攻击 由于单向散列函数接受的输入长度是任意的，而它的输出长度是固定值，因此单向散列函数将带来数据的压缩，单向散列函数肯定会存在碰撞的可能。如果

39、用单向散列函数对消息求散列值，是不希望发生碰撞的，否则攻击者可以把消息修改成特定的模式，使其和原始消息具有相同的散列值，而用户却无法通过计算散列值发现数据已经被修改 因此散列函数又被称为数字指纹，就是说一般每个不同的消息都有其独特的散列值。两类生日攻击 对单向散列函数的攻击是指找到散列函数对不同输入的碰撞，这称为生日攻击，它包括两类，分别对应攻击散列函数的弱抗冲突性和强抗冲突性 1.第类生日攻击 2.第类生日攻击（基于生日悖论）第类生日攻击 已知一散列函数H有n个可能的输出，H(x)是一个特定的输出，如果对H随机取k个输入，则至少有一个输入y使得H(y)=H(x)的概率为0.5时，k有多大？由

40、(1+x)k1+kx，其中|x|1，可得1-1-1/nk1-1-k/n=k/n 若使上述概率等于0.5，则k=n/2。特别地，如果H的输出为m比特长，即可能的输出个数n=2m，则k=2m-1 第类生日攻击（基于生日悖论）生日悖论是指：任意找23个人，则他们中有两个人生日相同的概率会大于50%，如果有30人，则此概率大约为70%，这比我们凭感觉认为的概率要大得多，因此称为生日悖论。设散列函数H有2m个可能的输出（即输出长为m比特），如果H的k个随机输入中至少有两个产生相同输出的概率大于0.5，则k=2m/2。称寻找函数H的具有相同输出的两个任意输入的攻击方式为第类生日攻击。两类生日攻击的难度比较

41、 可看出第类生日攻击比第类生日攻击容易，因为它只需要寻找2m/2个输入。因此抵抗第类生日攻击（对应强抗冲突性）比抵抗第类生日攻击（对应弱抗冲突性）要难。例子：针对散列函数的第类生日攻击的方法 散列函数的设计及MD5算法 一个好的散列函数的设计有一些基本原则：1）对不同的输入，要尽量不产生相同的散列值（抗冲突性）。2）两个明文即使只有微小的差别（如只有一位不同），它们的散列值也会有很多位都发生变化（扩散性），这样根本不能从散列值看出两个明文的相似性。3）将明文的长度信息记录在散列值中，这样可以更好的防止冲突 MD5散列算法散列函数的分类 1）带秘密密钥的Hash函数：消息的散列值由只有通信双方知

42、道的秘密密钥K来控制。此时，散列码称作MAC（Message Authentication Code，消息认证码）原文原文消息摘要消息摘要MACHash函数函数密钥密钥k消息认证码的实现 MAC的实现的一个简单方法是先对消息求散列值，再用一个对称密钥加密该散列值，这样，接收方必须知道该对称密钥才能够提取这个散列值，并将该散列值与对消息求出的散列值进行比较。由于散列函数并不是专为MAC而设计的，它不使用密钥，并不能直接构造MAC。于是人们想出了将密钥直接加到原文中再求hash值方法构造MAC，传输前把密钥K移去。这种方案的一种实现叫做HMAC HMACHash密钥密钥K原文原文MAC原文原文MA

43、C原文原文密钥密钥KHashMAC比较比较MDC 2）不带秘密密钥的散列函数：消息散列值的产生无需使用密钥，任何人都可以使用公开的散列函数算法对散列值进行验证，这就是普通的散列函数。此时，散列值称作MDC（Manipulation detection code，篡改检验码）。MDC通常用来检测文件或报文的完整性。根据散列函数使用的算法 根据散列函数使用的算法，目前的散列函数主要分为两类，MD5 128位散列值 SHA-1 160位散列值 问题 散列函数的要求是什么？什么是HMAC，MDC对称加密法使用方式 ECB电子密码本 CBC密码分组链接模式 CFB密码反馈模式 OFC输出反馈模式 CTR

44、计数器模式 分组密码和流密码密码学应用 数字信封 数字签名 数字证书。要求掌握RSA算法过程，给定n,p,q,能够算出e,n d,n,加密和解密 EIGAMAL算法，给定n,a,选定x，能够计算y，并能够加密和解密 给定n,a,双方选定x,y，能够交换秘钥DH数字信封技术：1 A B各自产生自己的公私钥对 2 公布自己的公钥，保密自己的私钥 3 A待加密信息M，产生对称加密法的秘钥k，对称加密法加密M得到C 4 A使用B的公钥，加密k,传送到B 5 A将密文C传送给B B 1 使用自己的私钥解密，得到k 对应4 2 使用k，解密C得到M 对应5,3任务 Java加密库函数 http:/www.

45、open- 12-1 mod 77 77=7X11 16-1 mod 323 323=17X19 20-1 mod 403 403=31X13 44-1 mod 667 667=23X29求值值(29)(32)(80)(100)（101）(pe)=pe-pe-1 p为素数为素数练习1 在RSA中，给出n=221,e=5,求d 给出n=3937,e=17,求d 给出p=19,q=23,e=3,求n,(n)，d。加密信息加密信息 this is laugh，编码值为字母，编码值为字母顺序顺序练习2 在eigamal中，给出素数p=31,选择适当的本原根a,私钥x,计算g。a,g,p为公钥，x为私钥 运用字母表顺序编码hello，加密并解密他们练习3 DH密钥分配：本原根g=7,p=23 A选择x=3 B选择y=6 描述它们交换密钥的过程