管理信息学 第5章(3).ppt

《管理信息学 第5章(3).ppt》由会员分享，可在线阅读，更多相关《管理信息学 第5章(3).ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/175.5 5.5 公钥密码算法公钥密码算法公钥密码体制及其设计的基本原理公钥密码体制及其设计的基本原理RSARSA密码体制密码体制管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17 在私钥密码体制中，解密密钥与加密密钥相同或容易从加在私钥密码体制中，解密密钥与加密密钥相同或容易从加密密钥导出。存在的问题：密密钥导出。存在的问题：(1)加密密钥的暴露会使系统变得不安全；加密密钥的暴露会使系统变得不安全；(2)在传送密文前，发送者和接收者必须使用一个安全信道在传送密文前，发送者和接收者必须使用一个安

2、全信道预先通信密钥预先通信密钥 k，在实际通信中是很困难的。，在实际通信中是很困难的。私钥密码体制存在的问题私钥密码体制存在的问题管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17公钥密码体制及其设计的基本原理公钥密码体制及其设计的基本原理在公钥密码中，解密密钥和加密密钥不同，从一个难于推在公钥密码中，解密密钥和加密密钥不同，从一个难于推出另一个，解密和加密是可分离的，加密密钥是可以公开出另一个，解密和加密是可分离的，加密密钥是可以公开的。信息可通过编码被加密在一个的。信息可通过编码被加密在一个NP-完全问题之中，以完全问题之中，以普通方法破译该密码等价于解一个普通方

3、法破译该密码等价于解一个NP-完全问题。完全问题。管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17 如果函数如果函数 f(x)满足：满足：对对 f(x)的定义域中的任意的定义域中的任意 x，都容易，都容易计算函数值计算函数值 f(x)，而对于，而对于 f(x)的值域中的几乎所有的的值域中的几乎所有的 y，即，即使已知使已知 f 要计算要计算 f-1(y)也是不可行的，则称也是不可行的，则称 f(x)是单向函数。是单向函数。公钥密码体制：陷门单向函数(troop-door one-way function)若给定某些辅助信息时又容易计算单向函数若给定某些辅助信息时又容

4、易计算单向函数 f 的逆的逆 f-1，则称则称 f(x)是一个是一个陷门单向函数。陷门单向函数。这一辅助信息就是秘密的解密这一辅助信息就是秘密的解密密钥。公钥密码体制的安全性是指计算安全性，由求密钥。公钥密码体制的安全性是指计算安全性，由求 f-1 的复的复杂性决定。杂性决定。管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17单向函数举例单向函数举例例例1：y=anxn+an-1xn-1+a1x+a0例例2：设：设 n 是两个大素数是两个大素数 p 和和 q 的乘积，的乘积，b是一个正整数，是一个正整数，对对 xZn，令，令 f(x)xb(mod n)，即即 f(x)

5、等于被等于被n除所得的除所得的余数，人们认为余数，人们认为 f(x)是一个从是一个从 Zn 到到 Zn 的单向函数的单向函数管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17定义定义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密码体制：互素管理信息学 杨善林 胡笑旋编著第5章

6、信息安全与信息加密2022/12/17 设设 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，则对，则对 aZ*n，有，有 a(n)1(mod n)定理定理5.2 设设 p 与与 q 是两个不同的素数，是两个不同的素数，n=pq，则对任意的，则对任意的xZn=1，2，n-1 及任意的非负整数及任意的非负整数 k，有，有

7、xk(n)+1 x(mod n)RSA密码体制：欧拉函数密码体制：欧拉函数管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17 设设p，q是两个不同的奇素数，是两个不同的奇素数，n=pq，则，则(n)=(p-1)(q-1)，密钥密钥k=(n，p，q，a，b)|ab 1(mod (n)，a，bZ*n)对每对每一个一个k=(n，p，q，a，b)定义加密变换为：定义加密变换为：y=Ek(x)xb(mod n)，xZn 定义解密变换为：定义解密变换为：x=Dk(y)ya(mod n)，yZn RSA密码体制是公开加密密钥密码体制是公开加密密钥n与与b，保密解密密钥，保密解密密钥

8、a以及以及辅助信息辅助信息p与与qRSA密码体制：密钥密码体制：密钥管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17例例3：设用户：设用户A选择两个素数：选择两个素数：p=5，q=7，则：则：n=35，(n)=24。A 取取a=11Z*35，再由，再由Euclidean算法求出算法求出b=a-1(mod(n)。公开公开n=35和和b=11，保密，保密 p=5，q=7和和a=11。现现在在用用户户B想想把把明明文文 x=2Z35 发发送送给给A。B加加密密明明文文 x=2 得得密密文文：y=Ek(x)xb(mod 35)211(mod 35)=18；B在公开信道上将加

9、密后的密文在公开信道上将加密后的密文 y=18 发送给发送给A，当当A收收到到密密文文 y=18 时时，A解解密密可可得得：ya=18112(mod35)，从从而而A得得到到B发送的明文发送的明文 x=2。RSA密码体制：举例密码体制：举例管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17例例：设设a=11,n=35，(n)=24，计算，计算 b解解：ab 1(mod (n),即即 11b=24k+1，即，即b=(24k+1)/11=2k+(2k+1)/11 (1)令令(2k+1)/11=c,则则:2k+1=11c 那么那么 k=(11c-1)/2=5c+(c-1)/

10、2 (2)此时取此时取 c=1(取最小整数使其能够被整除取最小整数使其能够被整除),那么那么k=5+0=5 把把 k=5代入代入(1)式得到式得到:b=10+(10+1)/11=11 RSA密码体制：密码体制：b的求法的求法管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17RSA密码体制：举例密码体制：举例例例4：设用户：设用户A选择两个素数：选择两个素数：p=47，q=59，则；则；n=2773，(n)=46*58=2668。A取取a=157Z*2773，再求出，再求出b=a-1(mod (n)=17。A公开公开n=2773和和b=17，保密，保密p，q和和a。现现

11、在在用用户户B想想把把明明文文x=920Z2773发发送送给给A。B加加密密明明文文x=920得密文：得密文：y=Ek(x)xb(mod2773)92017(mod2773)=948；B在公开信道上将加密后的密文在公开信道上将加密后的密文y=948发送给发送给A，当当A收收到到密密文文y=948时时，A解解密密可可得得：ya=948157920(mod2773)，从而，从而A得到得到B发送的明文发送的明文x=920。管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17建立过程：建立过程：(1)找到两个大素数找到两个大素数 p与与 q(p与与q相差也很大相差也很大);(2

12、)计算计算 n 和和 (n);(3)随机选择一个数随机选择一个数b使得使得(b,n)=1,0b n;(4)利用利用Euclidean算法计算算法计算 a=b-1(mod (n);(5)将将n与与b作为他的公钥直接公开，以便让所有想给他发送想作为他的公钥直接公开，以便让所有想给他发送想 保密的信息加密。保密的信息加密。RSA密码体制：加密过程密码体制：加密过程管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/171：DES是一种广泛使用的（）A.非对称加密算法 B.流密码算法 C.分组密码算法 D.公钥密码算法 C练习题练习题管理信息学 杨善林 胡笑旋编著第5章 信息安全与

13、信息加密2022/12/172：密码学中的复杂性问题包括（）A.P或NP问题B.P和NP问题C.P问题D.NP问题 B练习题练习题管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/173：NP问题是指（）A.时间复杂度为指数函数的一类问题。B.空间复杂度为指数函数的一类问题。C.非确定性多项式时间可解问题。D.非确定性指数时间可解问题。C练习题练习题管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/174：所谓选择明文攻击是指（）A.仅知道一些密文。B.仅知道一些密文及其所对应的明文。C.可得到任何明文的密文。D.可得到任何密文的明文。C练习题练习题

14、管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/175：算法复杂性是指（）A.时间或空间复杂性。B.时间和空间复杂性。C.指数时间算法的复杂性。D.指数空间算法的复杂性。B练习题练习题管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/176：设n=527,则(n)为（）A.526 B.503 C.480 D.457 练习题练习题C管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/177：设n91，a17,则按RSA加密体制，收到密文2所对 应的明文是（）A.32 B.37 C.53 D.71 练习题练习题A管理信息学 杨善林

15、胡笑旋编著第5章 信息安全与信息加密2022/12/175.6 5.6 数字签名方案数字签名方案数字签名方案概述数字签名方案概述RSA签名方案签名方案数字签名的发展与挑战数字签名的发展与挑战管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17数字签名概述数字签名概述 简单地说简单地说,所谓数字签名就是附加在所谓数字签名就是附加在 数据单元上的一些数据数据单元上的一些数据,或是对数据单或是对数据单 元所作的密码变换。元所作的密码变换。这种数据或变换允许数据单元的接这种数据或变换允许数据单元的接收者用以确认数据单元的来源和数据单元的完整性并保收者用以确认数据单元的来源和数据

16、单元的完整性并保护数据护数据,防止被人进行伪造。防止被人进行伪造。管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17公钥签名方案：公钥签名方案：u 利用私钥生成签名利用私钥生成签名 u 利用公钥验证签名利用公钥验证签名 u 只有私钥的拥有者才能生成签名只有私钥的拥有者才能生成签名,所以能够用于证明谁所以能够用于证明谁生成的消息生成的消息 u 任何知道公钥的人可以验证消息任何知道公钥的人可以验证消息 u通常不对整个消息签名，因为这将会使交换信息长度增通常不对整个消息签名，因为这将会使交换信息长度增加一倍加一倍数字签名方案概述数字签名方案概述管理信息学 杨善林 胡笑旋编著

17、第5章 信息安全与信息加密2022/12/17一般地，一个数字签名方案主要由签名算法一般地，一个数字签名方案主要由签名算法S()和验证和验证算法算法V()组成。签名者使用一个只有本人知道的密钥签组成。签名者使用一个只有本人知道的密钥签一个消息一个消息 x 得得 S(x)，接受者使用公开的，接受者使用公开的V()验证其签名验证其签名的真伪。的真伪。数字签名方案概述数字签名方案概述管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17数字签名过程：数字签名过程：设厂长使用设厂长使用RSA密码体制，厂长的加密密钥密码体制，厂长的加密密钥为为b，是公开的，解密密钥为，是公开的，解

18、密密钥为a，只有厂长本人知道，则：，只有厂长本人知道，则：(1)将附上数据将附上数据 x 的合同发给厂长；的合同发给厂长；(2)厂长用解密密钥对数据厂长用解密密钥对数据 a 作运算作运算y=Dk(x)，结果为厂长的数，结果为厂长的数字签名；字签名；(3)用厂长的公开加密密钥用厂长的公开加密密钥b作运算作运算x=Ek(y)，如果如果x=x，则可，则可证实厂长的签名为真；否则为假。证实厂长的签名为真；否则为假。数字签名方案概述数字签名方案概述管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17 数字签名一般使用的都是公钥密码体制。要构造无条件数字签名一般使用的都是公钥密码体

19、制。要构造无条件安全的公钥密码体制几乎是不可能的。目前所用的公钥密码安全的公钥密码体制几乎是不可能的。目前所用的公钥密码体制都是基于以下三种数学疑难问题之一：体制都是基于以下三种数学疑难问题之一：(1)由由Diffie提提出出的的背背包包问问题题：给给定定一一个个互互不不相相同同的的数数组组成成的集合，如何找出一个子集，使其元素之和为的集合，如何找出一个子集，使其元素之和为N。(2)由由Gill提提出出的的离离散散对对数数问问题题：设设p是是素素数数，k与与m是是整整数数，如何找如何找x使下式成立：使下式成立：kx m(mod p)数字签名的发展与挑战数字签名的发展与挑战管理信息学 杨善林 胡

20、笑旋编著第5章 信息安全与信息加密2022/12/17 (3)由由Knuth提出的因子分解问题：设提出的因子分解问题：设 n 是两个不同的大素是两个不同的大素数乘积，如何分解数乘积，如何分解 n?一旦这些数学难题取得突破性进展，将使所有公开密钥体一旦这些数学难题取得突破性进展，将使所有公开密钥体制以及以公开密钥体制为基础的数字签名方案不安全。制以及以公开密钥体制为基础的数字签名方案不安全。数字签名的发展与挑战数字签名的发展与挑战管理信息学 杨善林 胡笑旋编著第5章 信息安全与信息加密2022/12/17数字签名的发展与挑战数字签名的发展与挑战-计算能力的发展计算能力的发展量子计算机：量子计算机：20122012年与传统计算机的性能相当。年与传统计算机的性能相当。20132013年相当于所有传统计年相当于所有传统计算机能力之和。算机能力之和。20142014年超过全宇宙：可以解决任何非量子计算机均无法解年超过全宇宙：可以解决任何非量子计算机均无法解决（哪怕整个宇宙的能量均供其支配）的特定问题决（哪怕整个宇宙的能量均供其支配）的特定问题