管理信息学 第5章(3)(精品)

*,*,管理信息学 杨善林 胡笑旋编著,第,5,章 信息安全与信息加密,管理信息学 杨善林 胡笑旋编著,第,5,章 信息安全与信息加密,*,*,2024/10/5,5.5,公钥密码算法,公钥密码体制及其设计的基本原理,RSA,密码体制,2024/10/5,在私钥密码体制中，解密密钥与加密密钥相同或容易从加密密钥导出。存在的问题：,(1),加密密钥的暴露会使系统变得不安全；,(2),在传送密文前，发送者和接收者必须使用一个安全信道预先通信密钥,k,，在实际通信中是很困难的。,私钥密码体制存在的问题,2024/10/5,公钥密码体制及其设计的基本原理,在公钥密码中，解密密钥和加密密钥不同，从一个难于推出另一个，解密和加密是可分离的，加密密钥是可以公开的。信息可通过编码被加密在一个,NP-,完全问题之中，以普通方法破译该密码等价于解一个,NP-,完全问题。,2024/10/5,如果函数,f,(,x,),满足：,对,f,(,x,),的定义域中的任意,x,，都容易计算函数值,f,(,x,),，而对于,f,(,x,),的值域中的几乎所有的,y,，即使已知,f,要计算,f,-,-1,(,y,),也是不可行的，则称,f,(,x,),是单向函数。,公钥密码体制：,陷门单向函数,(troop-door one-way function),若给定某些辅助信息时又容易计算单向函数,f,的逆,f,-1,，则称,f,(,x,),是一个,陷门单向函数。,这一辅助信息就是秘密的解密密钥。公钥密码体制的安全性是指计算安全性，由求,f,-1,的复杂性决定。,2024/10/5,单向函数举例,例,1,：,y,=,a,n,x,n,+,a,n,-1,x,n,-1,+,+,a,1,x,+,a,0,例,2,：设,n,是两个大素数,p,和,q,的乘积，,b,是一个正整数，对,x,Z,n,，令,f,(,x,),x,b,(mod,n,),，,即,f,(,x,),等于被,n,除所得的余数，人们认为,f,(,x,),是一个从,Z,n,到,Z,n,的单向函数,2024/10/5,定义,5.1,设,m,，,n,是两个整数，如果正整数,d,满足：,(1),d,整除,m,和,n,，即,d,|,m,，,d,|,n,;,(2),若,d,|,m,且,d,|,n,，则,d,|,d,。,则称,d,是,m,与,n,的最大公因数，记为,d,=,(m,，,n,),。若,(m,，,n),=1,，则称,m,与,n,互素。,RSA,密码体制：互素,2024/10/5,设,n,是任一自然数，记,1,，,2,，,，,n,-1,中与,n,互素的数的个数为,(,n,),，并称,(,n,),为欧拉,(Euler),函数。,若,n,=,pq,，其中,p,与,q,是不同的素数，则,(,n,)=(,p,-1)(,q,-1),定理,5.1,设,Z,*,n,=,m,|(,m,，,n,)=1,，,1,m,n,-1,，则对,a,Z,*,n,，有,a,(,n,),1(mod,n,),定理,5.2,设,p,与,q,是两个不同的素数，,n,=,pq,，则对任意的,x,Z,n,=1,，,2,，,，,n,-1,及任意的非负整数,k,，有,x,k,(,n,)+1,x,(mod,n,),RSA,密码体制：欧拉函数,2024/10/5,设,p,，,q,是两个不同的奇素数，,n=pq,，则,(,n,)=(,p,-1)(,q,-1),，密钥,k,=(,n,，,p,，,q,，,a,，,b,)|,ab,1(mod,(,n,),，,a,，,b,Z,*,n,),对每一个,k,=(,n,，,p,，,q,，,a,，,b,),定义加密变换为：,y=E,k,(,x,),x,b,(mod,n,),，,x,Z,n,定义解密变换为：,x=D,k,(,y,),y,a,(mod,n,),，,y,Z,n,RSA,密码体制是公开加密密钥,n,与,b,，保密解密密钥,a,以及辅助信息,p,与,q,RSA,密码体制：密钥,2024/10/5,例,3,：设用户,A,选择两个素数：,p,=5,，,q,=7,，,则：,n=,35,，,(,n,)=24,。,A,取,a,=11,Z,*,35,，再由,Euclidean,算法求出,b,=,a,-1,(mod,(,n,),。,公开,n,=35,和,b,=11,，保密,p,=5,，,q,=7,和,a,=11,。,现在用户,B,想把明文,x,=2,Z,35,发送给,A,。,B,加密明文,x,=2,得密文：,y,=,E,k,(x),x,b,(mod 35)2,11,(mod 35)=18,；,B,在公开信道上将加密后的密文,y,=18,发送给,A,，,当,A,收到密文,y,=18,时，,A,解密可得：,y,a,=18,11,2(mod35),，从而,A,得到,B,发送的明文,x,=2,。,RSA,密码体制：举例,2024/10/5,例,：,设,a,=11,n=,35,，,(,n,)=24,，计算,b,解,：,ab,1(mod,(,n,),即,11,b,=24,k,+1,，即,b,=(24,k,+1)/11=2,k,+(2,k,+1)/11 (1),令,(2,k,+1)/11=,c,则,:2,k,+1=11,c,那么,k,=(11,c,-1)/2=5,c,+(,c,-1)/2 (2),此时取,c,=1(,取最小整数使其能够被整除,),那么,k,=5+0=5,把,k,=5,代入,(1),式得到,:,b,=10+(10+1)/11=11,RSA,密码体制：,b,的求法,2024/10/5,RSA,密码体制：举例,例,4,：设用户,A,选择两个素数：,p,=47,，,q,=59,，,则；,n=2773,，,(,n,)=46*58=2668,。,A,取,a,=157,Z,*,2773,，再求出,b,=,a,-1,(mod,(,n,)=17,。,A,公开,n,=2773,和,b,=17,，保密,p,，,q,和,a,。,现在用户,B,想把明文,x,=920,Z,2773,发送给,A,。,B,加密明文,x,=920,得密文：,y,=,E,k,(x),x,b,(mod2773)920,17,(mod2773)=948,；,B,在公开信道上将加密后的密文,y,=948,发送给,A,，,当,A,收到密文,y,=948,时，,A,解密可得：,y,a,=948,157,920(mod2773),，从而,A,得到,B,发送的明文,x,=920,。,2024/10/5,建立过程：,(1),找到两个大素数,p,与,q,(,p,与,q,相差也很大,);,(2),计算,n,和,(,n,);,(3),随机选择一个数,b,使得,(,b,n,)=1,0,b,n;,(4),利用,Euclidean,算法计算,a,=,b,-1,(mod,(,n,);,(5),将,n,与,b,作为他的公钥直接公开，以便让所有想给他发送想,保密的信息加密。,RSA,密码体制：加密过程,2024/10/5,计算机分解大数的能力,RSA,算法的安全性是基于分解大整数,n,的困难性。,目前大整数分解算法能力：分解,512,位的十进制数,!,基于安全性考虑，用户选择的素数,p,和,q,大约都为,512,位的十进制数，那么,n=pq,将是,1024,位的十进制数。,每秒运算,1000000,次,:,n,的大小,(,十进制,),50,75,100,200,300,500,时间,3.9,小时,104,天,74,年,3.8*10,9,年,4.5*10,15,年,4.2*10,29,年,2024/10/5,1,：,DES,是一种广泛使用的（）,A.,非对称加密算法,B.,流密码算法,C.,分组密码算法,D.,公钥密码算法,C,练习题,2024/10/5,2,：,密码学中的复杂性问题包括（）,A.P,或,NP,问题,B.P,和,NP,问题,C.P,问题,D.NP,问题,B,练习题,2024/10/5,3,：,NP,问题是指（）,A.,时间复杂度为指数函数的一类问题。,B.,空间复杂度为指数函数的一类问题。,C.,非确定性多项式时间可解问题。,D.,非确定性指数时间可解问题。,C,练习题,2024/10/5,4,：,所谓选择明文攻击是指,（）,A.,仅知道一些密文。,B.,仅知道一些密文及其所对应的明文。,C.,可得到任何明文的密文。,D.,可得到任何密文的明文。,C,练习题,2024/10/5,5,：,算法复杂性是指,（）,A.,时间或空间复杂性。,B.,时间和空间复杂性。,C.,指数时间算法的复杂性。,D.,指数空间算法的复杂性。,B,练习题,2024/10/5,6,：,设,n,=527,则,(n),为,（）,A.526,B.503,C.480,D.457,练习题,C,2024/10/5,7,：设,n,91,，,a,17,则按,RSA,加密体制，收到密文,2,所对 应的明文是（）,A.32,B.37,C.53,D.71,练习题,A,2024/10/5,5.6,数字签名方案,数字签名方案概述,RSA,签名方案,数字签名的发展与挑战,2024/10/5,数字签名概述,简单地说,所谓数字签名就是附加在,数据单元上的一些数据,或是对数据单,元所作的密码变换。,这种数据或变换允许数据单元的接收者用以确认数据单元的来源和数据单元的完整性并保护数据,防止被人进行伪造。,2024/10/5,公钥签名方案：,利用私钥生成签名,利用公钥验证签名,只有私钥的拥有者才能生成签名,所以能够用于证明谁生成的消息,任何知道公钥的人可以验证消息,通常不对整个消息签名，因为这将会使交换信息长度增加一倍,数字签名方案概述,2024/10/5,一般地，一个数字签名方案主要由签名算法,S(),和验证算法,V(),组成。签名者使用一个只有本人知道的密钥签一个消息,x,得,S,(,x,),，接受者使用公开的,V(),验证其签名的真伪。,数字签名方案概述,2024/10/5,数字签名过程：,设厂长使用,RSA,密码体制，厂长的加密密钥为,b,，是公开的，解密密钥为,a,，只有厂长本人知道，则：,(1),将附上数据,x,的合同发给厂长；,(2),厂长用解密密钥对数据,a,作运算,y=D,k,(x),，结果为厂长的数字签名；,(3),用厂长的公开加密密钥,b,作运算,x=E,k,(y),，,如果,x=x,，则可证实厂长的签名为真；否则为假。,数字签名方案概述,2024/10/5,数字签名一般使用的都是公钥密码体制。要构造无条件安全的公钥密码体制几乎是不可能的。目前所用的公钥密码体制都是基于以下三种数学疑难问题之一：,(1),由,Diffie,提出的背包问题：给定一个互不相同的数组成的集合，如何找出一个子集，使其元素之和为,N,。,(2),由,Gill,提出的离散对数问题：设,p,是素数，,k,与,m,是整数，如何找,x,使下式成立：,k,x,m,(mod,p,),数字签名的发展与挑战,2024/10/5,(3),由,Knuth,提出的因子分解问题：设,n,是两个不同的大素数乘积，如何分解,n,?,一旦这些数学难题取得突破性进展，将使所有公开密钥体制以及以公开密钥体制为基础的数字签名方案不安全。,数字签名的发展与挑战,2024/10/5,数字签名的发展与挑战,-,计算能力的发展,量子计算机：,2012,年与传统计算机的性能相当。,2013,年相当于所有传统计算机能力之和。,2014,年超过全宇宙：可以解决任何非量子计算机均无法解决（哪怕整个宇宙的能量均供其支配）的特定问题,