网络与信息安全优秀PPT.ppt

《网络与信息安全优秀PPT.ppt》由会员分享，可在线阅读，更多相关《网络与信息安全优秀PPT.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、密码学基础（密码学基础（2）胡建斌胡建斌北京高校网络与信息平安探讨室北京高校网络与信息平安探讨室E-mail:hjbininfosec.pku.edu :/infosec.pku.edu/hjbin 目目 录录1.数据加密标准数据加密标准2.公开密钥算法公开密钥算法数据加密标准数据加密标准（Data Encryption Standard,DES)背景背景独创人：美国独创人：美国IBMIBM公司公司 W.Tuchman W.Tuchman 和和 C.Meyer C.Meyer 1971-1972 1971-1972年研制成功年研制成功基础：基础：19671967年美国年美国Horst Feis

2、telHorst Feistel提出的理论提出的理论产生：美国国家标准局（产生：美国国家标准局（NBS)1973NBS)1973年年5 5月到月到19741974年年8 8月两次发布通告，月两次发布通告，公开征求用于电子计算机的加密算法。经评比从一大批算公开征求用于电子计算机的加密算法。经评比从一大批算法中接受法中接受 了了IBMIBM的的LUCIFERLUCIFER方案方案标准化：标准化：DESDES算法算法19751975年年3 3月公开发表，月公开发表，19771977年年1 1月月1515日由美国国家标日由美国国家标 准局颁布为数据加密标准（准局颁布为数据加密标准（Data Encry

3、ption StandardData Encryption Standard），），于于 1977 1977年年7 7月月1515日生效日生效背景背景美国国家平安局（美国国家平安局（NSA,National Security Agency)参与了参与了美国国家标准局制定数据加密标准的过程。美国国家标准局制定数据加密标准的过程。NBS接受了接受了NSA的的某些建议，对算法做了修改，并将密钥长度从某些建议，对算法做了修改，并将密钥长度从LUCIFER方案方案中的中的128位压缩到位压缩到56位位1979年，美国银行协会批准运用年，美国银行协会批准运用DES1980年，年，DES成为美国标准化协会成

4、为美国标准化协会(ANSI)标准标准1984年年2月，月，ISO成立的数据加密技术委员会成立的数据加密技术委员会(SC20)在在DES基基础上制定数据加密的国际标准工作础上制定数据加密的国际标准工作DES概述概述分组加密算法：明文和密文为分组加密算法：明文和密文为64位分组长度位分组长度对称算法：加密和解密除密钥编排不同外，运用同一算法对称算法：加密和解密除密钥编排不同外，运用同一算法密钥长度：密钥长度：56位，但每个第位，但每个第8位为奇偶校验位，可忽视位为奇偶校验位，可忽视密钥可为随意的密钥可为随意的56位数，但存在弱密钥，简洁避开位数，但存在弱密钥，简洁避开接受混乱和扩散的组合，每个组合

5、先替代后置换，共接受混乱和扩散的组合，每个组合先替代后置换，共16轮轮只运用了标准的算术和逻辑运算，易于实现只运用了标准的算术和逻辑运算，易于实现DES加密算法的一般描述加密算法的一般描述输入输入64比特明文数据比特明文数据初始置换初始置换IP在密钥控制下在密钥控制下16轮迭代轮迭代初始逆置换初始逆置换IP-1输出输出64比特密文数据比特密文数据交换左右交换左右32比特比特 DES加密过程加密过程DES加密过程加密过程令令i表示迭代次数，表示迭代次数，表示逐位模表示逐位模2求和，求和，f为为加密函数加密函数DES解密过程解密过程令令i表示迭代次数，表示迭代次数，表示逐位模表示逐位模2求和，求和

6、，f为为加密函数加密函数DES中的各种置换、扩展和替代中的各种置换、扩展和替代初始置换初始置换IP和初始逆置换和初始逆置换IP1 IP和和IP1IPIP1Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1DES的的一轮迭代一轮迭代扩展置换扩展置换-盒盒32位扩展到位扩展到48位位扩展扩展压缩替代压缩替代S-盒盒48位压缩到位压缩到32位位共共8个个S盒盒S-盒1

7、S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的构造盒的构造S-盒的构造盒的构造DES中其它算法都是线性的，而中其它算法都是线性的，而S-盒运算则是非线性的盒运算则是非线性的S-盒不易于分析，它供应了更好的平安性盒不易于分析，它供应了更好的平安性所以所以S-盒是算法的关键所在盒是算法的关键所在S-盒的构造准则盒的构造准则S盒的每一行是整数盒的每一行是整数0，15的一个置换的一个置换没有一个没有一个S盒是它输入变量的线性函数盒是它输入变量的线性函数变更变更S盒的一个输入位至少要引起两位的输出变更盒的一个输入位至少要引起两位的输出变更对任何一个对任何一个S盒和任何一个输入盒和任何一

8、个输入X，S（X）和）和 S(X001100）至少有两个比特不同（这里）至少有两个比特不同（这里X是长度为是长度为6的比特串）的比特串）对任何一个对任何一个S盒，对任何一个输入对盒，对任何一个输入对e,f属于属于0,1,S(X)S(X11ef00)对任何一个对任何一个S盒，假如固定一个输入比特，来看一个固定输出比特的值，盒，假如固定一个输入比特，来看一个固定输出比特的值，这个输出比特为这个输出比特为0的输入数目将接近于这个输出比特为的输入数目将接近于这个输出比特为1的输入数目的输入数目S-盒的构造要求盒的构造要求S-盒是很多密码算法的唯一非线性部件盒是很多密码算法的唯一非线性部件,因此因此,它

9、的密码强度它的密码强度确定了整个算法的平安强度确定了整个算法的平安强度供应了密码算法所必需的混乱作用供应了密码算法所必需的混乱作用如何全面精确地度量如何全面精确地度量S-盒的密码强度和设计有效的盒的密码强度和设计有效的S-盒是分盒是分组密码设计和分析中的难题组密码设计和分析中的难题非线性度、差分匀整性、严格雪崩准则、可逆性、没有陷门非线性度、差分匀整性、严格雪崩准则、可逆性、没有陷门置换置换p-盒的构造盒的构造p-盒的构造准则盒的构造准则P置换的目的是供应雪崩效应置换的目的是供应雪崩效应明文或密钥的一点小的变动都引起密文的较大变更明文或密钥的一点小的变动都引起密文的较大变更DES中的子密钥的生

10、成中的子密钥的生成密钥置换算法的构造准则密钥置换算法的构造准则设计目标：子密钥的统计独立性和敏捷性设计目标：子密钥的统计独立性和敏捷性实现简洁实现简洁速度速度不存在简洁关系：不存在简洁关系：(给定两个有某种关系的种子密钥给定两个有某种关系的种子密钥,能预料它们轮子密能预料它们轮子密钥之间的关系钥之间的关系)种子密钥的全部比特对每个子密钥比特的影响大致相同种子密钥的全部比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥没有弱密钥Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）4

11、8比特寄存器比特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1DES的的一轮迭代一轮迭代DES加密算法的一般描述加密算法的一般描述DES的工作模式的工作模式电子密码本电子密码本 ECB(electronic codebook ECB(electronic codebook mode)mode)密码分组链接密码分组链接 CBC(cipher block chaining)CBC(cipher block chaining)密码反馈密码反馈 CFB(c

12、ipher feedback)CFB(cipher feedback)输出反馈输出反馈 OFB(output feedback)OFB(output feedback)电子密码本电子密码本ECBECB的特点的特点简洁和有效简洁和有效可以并行实现可以并行实现不能隐藏明文的模式信息不能隐藏明文的模式信息 相同明文生成相同密文，同样信息多次出现造成泄漏相同明文生成相同密文，同样信息多次出现造成泄漏对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放误差传递：密文块损坏误差传递：密文块损坏 仅对应明文块损坏仅对应明文块损坏适合于传输短信息适

13、合于传输短信息密码分组链接密码分组链接CBCCBC的特点的特点没有已知的并行实现算法没有已知的并行实现算法能隐藏明文的模式信息能隐藏明文的模式信息 须要共同的初始化向量须要共同的初始化向量IVIV 相同明文生成不同密文相同明文生成不同密文 初始化向量初始化向量IVIV可以用来变更第一块可以用来变更第一块对明文的主动攻击是不简洁的对明文的主动攻击是不简洁的 信息块不简洁被替换、重排、删除、重放信息块不简洁被替换、重排、删除、重放 误差传递：密文块损坏误差传递：密文块损坏 两明文块损坏两明文块损坏平安性好于平安性好于ECBECB适合于传输长度大于适合于传输长度大于6464位的报文，还可以进行用户鉴

14、别位的报文，还可以进行用户鉴别,是大多系统的标准如是大多系统的标准如 SSL SSL、IPSecIPSec密码反馈密码反馈CFB CFB:CFB:分组密码分组密码流密码流密码假定：假定：SiSi 为移位寄存器为移位寄存器,传输单位为传输单位为jbitbit 加密加密:C Ci i=P=Pi i(E EK K(S Si i)的高的高j j位位)S Si i+1+1=(=(S Si ij)|j)|C Ci i 解密解密:P Pi i=C Ci i(E EK K(S Si i)的高的高j j位位)S Si i+1+1=(=(S Si ij)|j)|C Ci i密码反馈密码反馈CFB加密加密Ci=Pi

15、(EK(Si)的高的高j位位);Si+1=(Sij)|Ci 密码反馈密码反馈CFB解密解密Pi=Ci(EK(Si)的高的高j位位);Si+1=(Sij)|Ci CFB的特点的特点分组密码分组密码 流密码流密码没有已知的并行实现算法没有已知的并行实现算法隐藏了明文模式隐藏了明文模式须要共同的移位寄存器初始值须要共同的移位寄存器初始值IVIV对于不同的消息，对于不同的消息，IVIV必需唯一必需唯一误差传递：一个单元损坏影响多个单元误差传递：一个单元损坏影响多个单元输出反馈输出反馈OFB O OFB:FB:分组密码分组密码流密码流密码假定：假定：SiSi 为移位寄存器为移位寄存器,传输单位为传输单位

16、为jbitbit 加密加密:C Ci i=P=Pi i(E EK K(S Si i)的高的高j j位位)S Si i+1+1=(=(S Si ij)|j)|(E EK K(S Si i)的高的高j j位位)解密解密:P Pi i=C Ci i(E EK K(S Si i)的高的高j j位位)S Si i+1+1=(=(S Si ij)|j)|(E EK K(S Si i)的高的高j j位位)输出反馈输出反馈OFB加密加密Ci=Pi(EK(Si)的高的高j位位);Si+1=(Sij)|(EK(Si)的高的高j位位)输出反馈输出反馈OFB解密解密Pi=Ci(EK(Si)的高的高j位位);Si+1=

17、(Sij)|(EK(Si)的高的高j位位)0FB的特点的特点分组密码分组密码 流密码流密码没有已知的并行实现算法没有已知的并行实现算法隐藏了明文模式隐藏了明文模式须要共同的移位寄存器初始值须要共同的移位寄存器初始值IVIV对于不同的消息，对于不同的消息，IVIV必需唯一必需唯一误差传递：一个单元损坏只影响对应单元误差传递：一个单元损坏只影响对应单元对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放平安性较平安性较CFBCFB差差多重多重DES两重两重DES三重三重DESDES的平安性的平安性 F F函数函数(S-Box)(S-Bo

18、x)设计原理设计原理未知未知 密钥长度的争论密钥长度的争论 DES DES的破译的破译 弱密钥与半弱密钥弱密钥与半弱密钥DES密钥长度密钥长度关于关于DESDES算法的另一个最有争议的问题就是担忧实际算法的另一个最有争议的问题就是担忧实际5656比特的密钥长度不足以抵挡穷举式攻击，因为密钥量只比特的密钥长度不足以抵挡穷举式攻击，因为密钥量只有有 个个 早在早在19771977年，年，DiffieDiffie和和HellmanHellman已建议制造一个每秒能已建议制造一个每秒能测试测试100100万个密钥的万个密钥的VLSIVLSI芯片。每秒测试芯片。每秒测试100100万个密钥的万个密钥的机

19、器大约须要一天就可以搜寻整个密钥空间。他们估计机器大约须要一天就可以搜寻整个密钥空间。他们估计制造这样的机器大约须要制造这样的机器大约须要20002000万美元万美元DES密钥长度密钥长度在在CRYPTO93CRYPTO93上，上，SessionSession和和WienerWiener给出了一个特别具体的给出了一个特别具体的密钥搜寻机器的设计方案，这个机器基于并行运算的密钥密钥搜寻机器的设计方案，这个机器基于并行运算的密钥搜寻芯片，所以搜寻芯片，所以1616次加密能同时完成。花费次加密能同时完成。花费1010万美元，平万美元，平均用均用1.51.5天左右就可找到天左右就可找到DESDES密钥

20、密钥美国克罗拉多洲的程序员美国克罗拉多洲的程序员VerserVerser从从19971997年年2 2月月1818日起，用了日起，用了9696天时间，在天时间，在InternetInternet上数万名志愿者的协同工作下，成上数万名志愿者的协同工作下，成功地找到了功地找到了DESDES的密钥，赢得了悬赏的的密钥，赢得了悬赏的1 1万美元万美元DES密钥长度密钥长度19981998年年7 7月电子前沿基金会（月电子前沿基金会（EFFEFF）运用一台）运用一台2525万美圆的电万美圆的电脑在脑在5656小时内破译了小时内破译了5656比特密钥的比特密钥的DESDES19991999年年1 1月月R

21、SARSA数据平安会议期间，电子前沿基金会用数据平安会议期间，电子前沿基金会用2222小小时时1515分钟就宣告破解了一个分钟就宣告破解了一个DESDES的密钥的密钥破译破译DES19901990年，以色列密码学家年，以色列密码学家EliEli Biham Biham和和Adi ShamirAdi Shamir提出了差提出了差分密码分析法，可对分密码分析法，可对DESDES进行选择明文攻击进行选择明文攻击线性密码分析比差分密码分析更有效线性密码分析比差分密码分析更有效 弱密钥与半弱密钥弱密钥与半弱密钥弱密钥弱密钥:E EK K E EK K=I=I ，DESDES存在存在4 4个弱密钥个弱密钥

22、 即：即：半弱密钥半弱密钥:E EK1K1=E=EK2K2 ，至少有至少有1212个半弱密钥个半弱密钥 即：即：其它常规分组加密算法其它常规分组加密算法Triple DES IDEA RC5 RC6 AES其他一些较好用的算法，如其他一些较好用的算法，如Blowfish，CAST，以及，以及RC2等等运用常规加密进行保密通信运用常规加密进行保密通信易受攻击的位置易受攻击的位置电话公司电话公司市话局市话局接线盒接线盒链路加密和端到端加密链路加密和端到端加密存储转发通信的加密覆盖范围存储转发通信的加密覆盖范围各种加密策略包含的内容各种加密策略包含的内容链路层加密链路层加密对于在两个网于在两个网络节

23、点点间的某一次通信的某一次通信链路路,链路加密能路加密能为网上网上传输的数据供的数据供应平安保平安保证全部消息在被全部消息在被传输之前之前进行加密行加密,在每一个在每一个节点点对接收接收到的消息到的消息进行解密行解密,然后先运用下一个然后先运用下一个链路的密路的密钥对消消息息进行加密行加密,再再进行行传输链路层加密的优点链路层加密的优点由于在每一个中由于在每一个中间传输节点消息均被解密后重新点消息均被解密后重新进行行加密加密,因此因此,包括路由信息在内的包括路由信息在内的链路上的全部数据均路上的全部数据均以密文形式出以密文形式出现。这样,链路加密就掩盖了被路加密就掩盖了被传输消息消息的源点与的

24、源点与终点点由于填充技由于填充技术的运用以及填充字符在不的运用以及填充字符在不须要要传输数据数据的状况下就可以的状况下就可以进行加密行加密,这使得消息的使得消息的频率和率和长度特度特性得以掩盖性得以掩盖,从而可以防止从而可以防止对通信通信业务进行分析行分析链路层加密的缺点链路层加密的缺点链路加密通常用在点路加密通常用在点对点的同步或异步点的同步或异步线路上路上,它要求先它要求先对在在链路两端路两端的加密的加密设备进行同步行同步,然后运用一种然后运用一种链模式模式对链路上路上传输的数据的数据进行加行加密。密。这就就给网网络的性能和可管理性的性能和可管理性带来了副作用来了副作用在一个网在一个网络节

25、点点,链路加密路加密仅在通信在通信链路上供路上供应平安性平安性,消息以明文形消息以明文形式存在式存在,因此全部因此全部节点在物理上必需是平安的点在物理上必需是平安的,否否则就会泄漏明文内容就会泄漏明文内容在在传统的加密算法中的加密算法中,用于解密消息的密用于解密消息的密钥与用于加密的密与用于加密的密钥是相同的是相同的,该密密钥必需被必需被隐私保存私保存,并按确定并按确定规则进行行变更。更。这样,密密钥安排在安排在链路加密系路加密系统中就成了一个中就成了一个问题,因因为每一个每一个节点必需存点必需存储与其相与其相连接的接的全部全部链路的加密密路的加密密钥,这就就须要要对密密钥进行物理行物理传送或

26、者建立送或者建立专用网用网络设施。而网施。而网络节点地理分布的广袤性使得点地理分布的广袤性使得这一一过程程变得困得困难,同同时增加增加了密了密钥连续安排安排时的的费用用节点加密节点加密节点在操作方式上与点在操作方式上与链路加密是路加密是类似的似的:两者均在通信两者均在通信链路上路上为传输的消息供的消息供应平安性平安性;都在中都在中间节点先点先对消息消息进行解密行解密,然后然后进行加密。因行加密。因为要要对全部全部传输的数据的数据进行加密行加密,所以加密所以加密过程程对用用户是透亮的是透亮的然而然而,与与链路加密不同路加密不同,节点加密不允点加密不允许消息在网消息在网络节点以明文点以明文形式存在

27、形式存在,它先把收到的消息它先把收到的消息进行解密行解密,然后接受另一个不同的然后接受另一个不同的密密钥进行加密行加密,这一一过程是在程是在节点上的一个平安模点上的一个平安模块中中进行行节点加密要求点加密要求报头和路由信息以明文形式和路由信息以明文形式传输,以便中以便中间节点能点能得到如何得到如何处理消息的信息。因此理消息的信息。因此这种方法种方法对于防止攻于防止攻击者分析者分析通信通信业务是脆弱的是脆弱的端到端加密端到端加密端到端加密允端到端加密允许数据在从源点到数据在从源点到终点的点的传输过程程中始中始终以密文形式存在以密文形式存在接受端到端加密接受端到端加密(又称脱又称脱线加密或包加密加

28、密或包加密),),消息在消息在被被传输时到达到达终点之前不点之前不进行解密行解密,因因为消息在整消息在整个个传输过程中均受到程中均受到爱护,所以即使有所以即使有节点被点被损坏坏也不会使消息泄露也不会使消息泄露端到端加密的优点端到端加密的优点端到端加密系端到端加密系统的价格便宜些的价格便宜些,与与链路加密和路加密和节点加密相点加密相比更牢靠比更牢靠,更更简洁设计、实现和和维护端到端加密避开了其它加密系端到端加密避开了其它加密系统所固有的同步所固有的同步问题,因因为每个每个报文包均是独立被加密的文包均是独立被加密的,所以一个所以一个报文包所文包所发生的生的传输错误不会影响后不会影响后续的的报文包文

29、包从用从用户对平安需求的直平安需求的直觉上上讲,端到端加密更自然些。端到端加密更自然些。单个用个用户可能会可能会选用用这种加密方法种加密方法,以便不影响网以便不影响网络上的其上的其他用他用户,此方法只此方法只须要源和目的要源和目的节点是保密的即可点是保密的即可端到端加密的缺点端到端加密的缺点通常不允通常不允许对消息的目的地址消息的目的地址进行加密行加密,这是因是因为每一个每一个消息所消息所经过的的节点都要用此地址来确定如何点都要用此地址来确定如何传输消息消息由于由于这种加密方法不能掩盖被种加密方法不能掩盖被传输消息的源点与消息的源点与终点点,因因此它此它对于防止攻于防止攻击者分析通信者分析通信

30、业务是脆弱的是脆弱的目目 录录1.数据加密标准数据加密标准2.公开密钥算法公开密钥算法公开密钥算法公开密钥算法 公公开开密密钥钥算算法法是是非非对对称称算算法法，即即密密钥钥分分为为公公钥钥和和私私钥钥，因因此称双密钥体制此称双密钥体制 双钥体制的公钥可以公开，因此也称公钥算法双钥体制的公钥可以公开，因此也称公钥算法 公公钥钥算算法法的的出出现现，给给密密码码的的发发绽绽开开拓拓了了新新的的方方向向。公公钥钥算算法法虽虽然然已已经经验验了了20多多年年的的发发展展，但但仍仍具具有有强强劲劲的的发发展展势势头头，在鉴别系统和密钥交换等平安技术领域起着关键的作用在鉴别系统和密钥交换等平安技术领域起

31、着关键的作用公开密钥算法的提出公开密钥算法的提出公公钥钥密密码码学学是是1976年年由由Diffie和和Hellman在在其其“密密码码学学新新方方向向”一文中提出的，见文献：一文中提出的，见文献：W.Diffie and M.E.Hellman,New Directrions in Cryptography，IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654公开密钥算法的提出公开密钥算法的提出RSA公公钥钥算算法法是是由由Rivest,Shamir和和Adleman在在1978年年提提出出来的来的参参

32、见见Communitions of the ACM.Vol.21.No.2.Feb.1978,PP.120-126该该算算法法的的数数学学基基础础是是初初等等数数论论中中的的Euler（欧欧拉拉)定定理理，并并建立在大整数因子的困难性之上建立在大整数因子的困难性之上加密与解密由不同的密钥完成加密与解密由不同的密钥完成 加密：加密：解密：解密：知知道道加加密密算算法法，从从加加密密密密钥钥得得到到解解密密密密钥钥在在计计算算上上是是不不行行行的行的两两个个密密钥钥中中任任何何一一个个都都可可以以作作为为加加密密而而另另一一个个用用作作解解密密（不是必需的）（不是必需的）公开密钥算法的基本要求公开

33、密钥算法的基本要求基于公开密钥的加密过程基于公开密钥的加密过程用公钥密码实现保密用公钥密码实现保密 用户拥有自己的密钥对用户拥有自己的密钥对(KU,KR)公钥公钥 KU公开，私钥公开，私钥KR保密保密 基于公开密钥的鉴别过程基于公开密钥的鉴别过程用公钥密码实现鉴别用公钥密码实现鉴别 条条件件：两两个个密密钥钥中中任任何何一一个个都都可可以以用用作作加加密密而而另另外外一一个个用作解密用作解密鉴别：鉴别：鉴别保密鉴别保密 公开密钥算法公开密钥算法公钥算法的种类很多，具有代表性的三种密码：公钥算法的种类很多，具有代表性的三种密码：基于整数分解难题（基于整数分解难题（IFP）的算法体制）的算法体制

34、基于离散对数难题（基于离散对数难题（DLP）算法体制）算法体制基于椭圆曲线离散对数难题（基于椭圆曲线离散对数难题（ECDLP）的算法体制）的算法体制Diffie-Hellman密钥交换算法密钥交换算法单向陷门函数函数单向陷门函数函数 满足下列条件的函数满足下列条件的函数f：(1)给定给定x，计算，计算y=f(x)是简洁的是简洁的 (2)给定给定y,计算计算x使使y=f(x)是困难的是困难的 (3)存在存在z，已知，已知z 时时,对给定的任何对给定的任何y，若相应的，若相应的x存存 在，则计算在，则计算x使使y=f(x)是简洁的是简洁的所谓计算所谓计算x=f-1(Y)困难是指计算上相当困难，已无

35、实际意义困难是指计算上相当困难，已无实际意义单向陷门函数说明单向陷门函数说明仅仅满满足足(1)、(2)两两条条的的称称为为单单向向函函数数；第第(3)条条称称为为陷陷门门性性，z 称为陷门信息称为陷门信息当当用用陷陷门门函函数数f作作为为加加密密函函数数时时，可可将将f公公开开，这这相相当当于于公公开加密密钥，此时加密密钥便称为公开钥，记为开加密密钥，此时加密密钥便称为公开钥，记为Pkf函函数数的的设设计计者者将将z保保密密，用用作作解解密密密密钥钥，此此时时z称称为为隐隐私私钥钥匙匙，记记为为Sk。由由于于设设计计者者拥拥有有Sk，他他自自然然可可以以解解出出x=f-1(y)单单向向陷陷门门

36、函函数数的的第第(2)条条性性质质表表明明窃窃听听者者由由截截获获的的密密文文y=f(x)推想推想x是不行行的是不行行的Diffie-Hellman密钥交换算法密钥交换算法Diffie和和Hellman在在其其里里程程碑碑意意义义的的文文章章中中，虽虽然然给给出出了了密密码码的的思思想想，但但是是没没有有给给出出真真正正意意义义上上的的公公钥钥密密码码实实例例，也也既没能找出一个真正带既没能找出一个真正带陷门陷门的单向函数的单向函数然然而而，他他们们给给出出单单向向函函数数的的实实例例，并并且且基基于于此此提提出出Diffie-Hellman密钥交换算法密钥交换算法Diffie-Hellman

37、密钥交换算法的原理密钥交换算法的原理基基于于有有限限域域中中计计算算离离散散对对数数的的困困难难性性问问题题之之上上：设设F为为有有限限域域，gF是是F的的乘乘法法群群 F*=F0=，并并且且对对随随意意正正整整数数x，计计算算gx是是简简洁洁的的；但但是是已已知知g和和y求求x使使y=gx，是是计计算算上上几几乎乎不行能的不行能的这这个个问问题题称称为为有有限限域域F上上的的离离散散对对数数问问题题。公公钥钥密密码码学学中中运运用用最广泛的有限域为素域最广泛的有限域为素域FPDiffie-Hellman密钥交换协议描述密钥交换协议描述Alice和和Bob协协商商好好一一个个大大素素数数p，和

38、和大大的的整整数数g，1gp，g最好是最好是FP中的本原元，即中的本原元，即FP*p和和g无须保密，可为网络上的全部用户共享无须保密，可为网络上的全部用户共享Diffie-Hellman密钥交换协议描述密钥交换协议描述当当Alice和和Bob要进行保密通信时，他们可以按如下步骤来做：要进行保密通信时，他们可以按如下步骤来做：(1)Alice选取大的随机数选取大的随机数x，并计算，并计算 X=gx(mod P)(2)Bob选取大的随机数选取大的随机数x，并计算，并计算 X =gx (mod P)(3)Alice将将X传送给传送给Bob；Bob将将X 传送给传送给Alice (4)Alice计计算

39、算K=(X )X(mod P);Bob计计算算K =（X)X (mod P),易见，易见，K=K =g xx (mod P)由由(4)知，知，Alice和和Bob已获得了相同的隐私值已获得了相同的隐私值K双方以双方以K作为加解密钥以传统对称密钥算法进行保密通信作为加解密钥以传统对称密钥算法进行保密通信RSA 算法算法Euler 函数函数 全部模全部模m和和r同余的整数组成剩余类同余的整数组成剩余类r 剩余类剩余类r中的每一个数和中的每一个数和m互素的充要条件是互素的充要条件是r和和m互素互素 和和m互素的同余类数目用互素的同余类数目用(m)表示，称表示，称m的的Euler函数函数 当当m是是素

40、素数数时时，小小于于m的的全全部部整整数数均均与与m互互素素，因因此此(m)=m-1对对n=pq,p和和q 是素数，是素数，(n)=(p)(q)=(p-1)(q-1)Euler 函数函数举例举例 设设p=3,q=5,那么那么 （15）=（3-1）*（5-1）=8 这这8个模个模15的剩余类是的剩余类是：1，2，4，7，8，11，13，14 RSA算法的实现算法的实现 实现的步骤如下：实现的步骤如下：Bob为实现者为实现者 (1)Bob找寻出两个大素数找寻出两个大素数p和和q (2)Bob计算出计算出n=pq 和和(n)=(p-1)(q-1)(3)Bob选择一个随机数选择一个随机数e(0e(n)

41、，满足，满足(e,(n)=1 (4)Bob运用辗转相除法计算运用辗转相除法计算d=e-1(mod(n)(5)Bob在书目中公开在书目中公开n和和e作为公钥作为公钥密码分析者攻击密码分析者攻击RSA体制的关键点在于如何分解体制的关键点在于如何分解n。若分。若分解成功使解成功使n=pq，则可以算出，则可以算出(n)（p-1)(q-1)，然后由公，然后由公开的开的e，解出隐私的，解出隐私的dRSA算法编制算法编制 参数参数T=NT=N；私钥私钥SK=DSK=D；公钥公钥PK=EPK=E；设：明文设：明文M M，密文密文C C，那么：那么：用公钥作业：用公钥作业：M ME E mod N=C mod

42、N=C 用私钥作业：用私钥作业：M MD D mod N=M mod N=MRSA算法举例算法举例设设 p=7,q=17,n=7*17=119;p=7,q=17,n=7*17=119;参数参数T=n=119;T=n=119;(n)=(7-1)(17-1)=96;(n)=(7-1)(17-1)=96;选择选择e=5,e=5,gcd gcd(5,96)=1;(5,96)=1;公钥公钥pkpk=5;=5;计算计算d,(d*e)mod 96=1;d=77;d,(d*e)mod 96=1;d=77;私钥私钥sksk=77;=77;设设:明文明文m=19m=19 加密：（加密：（1919）5 5 mod

43、119=66mod 119=66 脱密：（脱密：（6666）7777 mod 119=19mod 119=19RSA算法的平安性分析算法的平安性分析密码分析者攻击密码分析者攻击RSA体制的关键点在于如何分解体制的关键点在于如何分解n若若分分解解成成功功使使n=pq，则则可可以以算算出出(n)（p-1)(q-1)，然然后由公开的后由公开的e，解出隐私的，解出隐私的d若若使使RSA平平安安，p与与q必必为为足足够够大大的的素素数数，使使分分析析者者没没有有方法在多项式时间内将方法在多项式时间内将n分解出来分解出来RSA算法的平安性分析算法的平安性分析建议选择建议选择p和和q大约是大约是100位的十

44、进制素数位的十进制素数模模n的长度要求至少是的长度要求至少是512比特比特EDI攻攻击击标标准准运运用用的的RSA算算法法中中规规定定n的的长长度度为为512至至1024比比特特位之间，但必需是位之间，但必需是128的倍数的倍数国际数字签名标准国际数字签名标准ISO/IEC 9796中规定中规定n的长度位的长度位512比特位比特位RSA算法的平安性分析算法的平安性分析 为为了了反反抗抗现现有有的的整整数数分分解解算算法法，对对RSA模模n的的素素因因子子p和和q还还有有如下要求：如下要求：(1)|p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同；(2)p-1 和和q-1分别含有大素因子分别含有大素因子p1和和q1 (3)P1-1和和q1-1分别含有大素因子分别含有大素因子p2和和q2 (4)p+1和和q+1分别含有大素因子分别含有大素因子p3和和q3RSA算法的平安性分析算法的平安性分析为了提高加密速度，通常取为了提高加密速度，通常取e为特定的小整数为特定的小整数如如EDI国际标准中规定国际标准中规定 e2161ISO/IEC9796中甚至允许取中甚至允许取e3这时加密速度一般比解密速度快这时加密速度一般比解密速度快10倍以上倍以上