《[精选]网络与信息安全32940.pptx》由会员分享，可在线阅读，更多相关《[精选]网络与信息安全32940.pptx（93页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、密码学基础（密码学基础（2）胡建斌胡建斌北京大学网络与信息安全研究室北京大学网络与信息安全研究室E-mail: http:/ 目目 录录1.数据加密标准数据加密标准2.公开密钥算法公开密钥算法数据加密标准数据加密标准（Data Encryption Standard,DES)背景背景发明人发明人：美国：美国IBM公司公司 W.Tuchman 和和 C.Meyer 1971-1972年研制成功年研制成功基础：基础：1967年美国年美国Horst Feistel提出的理论提出的理论产生：美国国家标准局（产生：美国国家标准局（NBS)1973年年5月到月到1974年年8月两次发布通告，月两次发布通告
2、，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳 了了IBM的的LUCIFER方案方案标准化：标准化：DES算法算法1975年年3月公开发表，月公开发表，1977年年1月月15日由美国国家标日由美国国家标 准局颁布为数据加密标准（准局颁布为数据加密标准（Data Encryption Standard），于），于 1977年年7月月15日生效日生效背景背景美国国家安全局（美国国家安全局（NSA,National Security Agency)参与了参与了美国国家标准局制定数据加密标准的过程。美国国家标准局制定数据加密标准的
3、过程。NBS接受了接受了NSA的的某些建议，对算法做了修改，并将密钥长度从某些建议，对算法做了修改，并将密钥长度从LUCIFER方案方案中的中的128位压缩到位压缩到56位位1979年，美国银行协会批准使用年，美国银行协会批准使用DES1980年，年，DES成为美国标准化协会成为美国标准化协会(ANSI)标准标准1984年年2月，月，ISO成立的数据加密技术委员会成立的数据加密技术委员会(SC20)在在DES基基础上制定数据加密的国际标准工作础上制定数据加密的国际标准工作DES概述概述分组加密算法：明文和密文为分组加密算法：明文和密文为64位分组长度位分组长度对称算法：加密和解密除密钥编排不同
4、外，使用同一算法对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：密钥长度：56位，但每个第位，但每个第8位为奇偶校验位，可忽略位为奇偶校验位，可忽略密钥可为任意的密钥可为任意的56位数，但存在弱密钥，容易避开位数，但存在弱密钥，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共采用混乱和扩散的组合，每个组合先替代后置换，共16轮轮只使用了标准的算术和逻辑运算，易于实现只使用了标准的算术和逻辑运算，易于实现DES加密算法的一般描述加密算法的一般描述输入输入64比特明文数据比特明文数据初始置换初始置换IP在密钥控制下在密钥控制下16轮迭代轮迭代初始逆置换初始逆置换IP-1输出输出6
5、4比特密文数据比特密文数据交换左右交换左右32比特比特 DES加密过程加密过程DES加密过程加密过程令令i表示迭代次数，表示迭代次数，表示逐位模表示逐位模2求和，求和，f为为加密函数加密函数DES解密过程解密过程令令i表示迭代次数，表示迭代次数，表示逐位模表示逐位模2求和，求和，f为为加密函数加密函数DES中的各种置换、扩展和替代中的各种置换、扩展和替代初始置换初始置换IP和初始逆置换和初始逆置换IP1 IP和和IP1IPIP1Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（4
6、8比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1DES的的一轮迭代一轮迭代扩展置换扩展置换-盒盒32位扩展到位扩展到48位位扩展扩展压缩替代压缩替代S-盒盒48位压缩到位压缩到32位位共共8个个S盒盒S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的构造盒的构造S-盒的构造盒的构造DES中其它算法都是线性的，而中其它算法都是线性的，而S-盒运算则是非线性的盒运算则是非线性的S-盒不易于分析，它提供了更好的安全性盒不易于分析，它提供了更好的安全性所以所以S-盒是算法的关键所在盒是算法的关键所在S-盒的构造
7、准则盒的构造准则S盒的每一行是整数盒的每一行是整数0，15的一个置换的一个置换没有一个没有一个S盒是它输入变量的线性函数盒是它输入变量的线性函数改变改变S盒的一个输入位至少要引起两位的输出改变盒的一个输入位至少要引起两位的输出改变对任何一个对任何一个S盒和任何一个输入盒和任何一个输入X，S（X）和）和 S(X 001100）至少有两个比特不同（这里）至少有两个比特不同（这里X是长度为是长度为6的比特串）的比特串）对任何一个对任何一个S盒，对任何一个输入对盒，对任何一个输入对e,f属于属于0,1,S(X)S(X 11ef00)对任何一个对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的
8、值，盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为这个输出比特为0的输入数目将接近于这个输出比特为的输入数目将接近于这个输出比特为1的输入数目的输入数目S-盒的构造要求盒的构造要求S-盒是许多密码算法的唯一非线性部件盒是许多密码算法的唯一非线性部件,因此因此,它的密码强度它的密码强度决定了整个算法的安全强度决定了整个算法的安全强度提供了密码算法所必须的混乱作用提供了密码算法所必须的混乱作用如何全面准确地度量如何全面准确地度量S-盒的密码强度和设计有效的盒的密码强度和设计有效的S-盒是分盒是分组密码设计和分析中的难题组密码设计和分析中的难题非线性度、差分均匀性、严格雪崩准则、
9、可逆性、没有陷门非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门置换置换p-盒的构造盒的构造p-盒的构造准则盒的构造准则P置换的目的是提供雪崩效应置换的目的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化明文或密钥的一点小的变动都引起密文的较大变化DES中的子密钥的生成中的子密钥的生成密钥置换算法的构造准则密钥置换算法的构造准则设计目标：子密钥的统计独立性和灵活性设计目标：子密钥的统计独立性和灵活性实现简单实现简单速度速度不存在简单关系：不存在简单关系：(给定两个有某种关系的种子密钥给定两个有某种关系的种子密钥,能预测它们轮子密能预测它们轮子密钥之间的关系钥之间的关系)种子密钥的
10、所有比特对每个子密钥比特的影响大致相同种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥没有弱密钥Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1DES的的一轮迭代一轮迭代DES加密算法的一般描述加密算法的一般描述DES的工作模式的工作模式电子密码本电子
11、密码本 ECB(electronic codebook ECB(electronic codebook mode)mode)密码分组链接密码分组链接 CBC(cipher block chaining)CBC(cipher block chaining)密码反馈密码反馈 CFB(cipher feedback)CFB(cipher feedback)输出反馈输出反馈 OFB(output feedback)OFB(output feedback)电子密码本电子密码本ECBECB的特点的特点简单和有效简单和有效可以并行实现可以并行实现不能隐藏明文的模式信息不能隐藏明文的模式信息 相同明文相同明文
12、生成生成相同密文，相同密文，同样信息多次出现造成泄漏同样信息多次出现造成泄漏对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放误差传递：密文块损坏误差传递：密文块损坏仅仅对应明文块损坏对应明文块损坏适合于传输短信息适合于传输短信息密码分组链接密码分组链接CBCCBC的特点的特点没有已知的并行实现算法没有已知的并行实现算法能隐藏明文的模式信息能隐藏明文的模式信息 需要共同的初始化向量需要共同的初始化向量IVIV 相同明文相同明文生成生成不同密文不同密文 初始化向量初始化向量IVIV可以用来改变第一块可以用来改变第一块对明文的主动攻击
13、是不容易的对明文的主动攻击是不容易的 信息块不容易被替换、重排、删除、重放信息块不容易被替换、重排、删除、重放 误差传递：密文块损坏误差传递：密文块损坏两两明文明文块块损坏损坏安全性好于安全性好于ECBECB适合于传输长度大于适合于传输长度大于6464位的报文，还可以进行用户鉴别位的报文，还可以进行用户鉴别,是大多系统的标准如是大多系统的标准如 SSL SSL、IPSecIPSec密码反馈密码反馈CFB CFB:CFB:分组密码分组密码流密码流密码假定：假定：Si Si 为移位寄存器为移位寄存器,传输单位为传输单位为jbitbit 加密加密:C:Ci i=P=Pi i(E EK K(S(Si
14、i)的高的高j j位位)S Si+1i+1=(S=(Si ij)|Cj)|Ci i 解密解密:P:Pi i=C=Ci i(E EK K(S(Si i)的高的高j j位位)S Si+1i+1=(S=(Si ij)|Cj)|Ci i密码反馈密码反馈CFB加密加密Ci=Pi(EK(Si)的高的高j位位);Si+1=(Sij)|Ci 密码反馈密码反馈CFB解密解密Pi=Ci(EK(Si)的高的高j位位);Si+1=(Sij)|Ci CFB的特点的特点分组密码分组密码流密码流密码没有已知的并行实现算法没有已知的并行实现算法隐藏了明文模式隐藏了明文模式需要共同的移位寄存器初始值需要共同的移位寄存器初始值I
15、VIV对于不同的消息，对于不同的消息，IVIV必须唯一必须唯一误差传递：一个单元损坏影响多个单元误差传递：一个单元损坏影响多个单元输出反馈输出反馈OFB O OFB:FB:分组密码分组密码流密码流密码假定：假定：Si Si 为移位寄存器为移位寄存器,传输单位为传输单位为jbitbit 加密加密:C:Ci i=P=Pi i(E EK K(S(Si i)的高的高j j位位)S Si+1i+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+1i+1=(S=(Si ij)|j
16、)|(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=(Sij)|(EK(Si)的高的高j位位)0FB的特点的特点分组密码分组密码流密码流密码没有已知的并行实现算法没有已知的并行实现算法隐藏了明文模式隐藏了明文模式需要共同的移位寄存器初始值需要共同的移位寄存器初始值IVIV对于不同的消息，对于不同的消息，IVIV必须唯一必须唯一误差传递：一个单元损坏只影响对应单元误差传递：一个单元损坏只影响
17、对应单元对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放安全性较安全性较CFBCFB差差多重多重DES两重两重DES三重三重DESDES的安全性的安全性 F F函数函数(S-Box)(S-Box)设计原理未知设计原理未知 密钥长度的争论密钥长度的争论 DES DES的的破译破译 弱密钥与半弱密钥弱密钥与半弱密钥DES密钥长度密钥长度关于关于DES算法的另一个最有争议的问题就是担心实际算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有有 个个
18、 早在早在1977年，年，Diffie和和Hellman已建议制造一个每秒能测已建议制造一个每秒能测试试100100万个密钥的万个密钥的VLSI芯片。每秒测试芯片。每秒测试100100万个密钥的万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要制造这样的机器大约需要2000万万美元美元DES密钥长度密钥长度在在CRYPTO93上，上，Session和和Wiener给出了一个非常详细给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以钥搜
19、索芯片，所以16次加密能同时完成。花费次加密能同时完成。花费10万万美元，美元，平均用平均用1.5天左右就可找到天左右就可找到DES密钥密钥美国克罗拉多洲的程序员美国克罗拉多洲的程序员Verser从从1997年年2 2月月18日起，用了日起，用了96天时间，在天时间，在Internet上数万名志愿者的协同工作下，成功上数万名志愿者的协同工作下，成功地找到了地找到了DES的密钥，赢得了悬赏的的密钥，赢得了悬赏的1万美元万美元DES密钥长度密钥长度19981998年年7 7月电子前沿基金会（月电子前沿基金会（EFFEFF）使用一台）使用一台2525万美圆的电万美圆的电脑在脑在5656小时内破译了小
20、时内破译了5656比特密钥的比特密钥的DESDES19991999年年1 1月月RSARSA数据安全会议期间，电子前沿基金会用数据安全会议期间，电子前沿基金会用2222小小时时1515分钟就宣告破解了一个分钟就宣告破解了一个DESDES的密钥的密钥破译破译DES19901990年，以色列密码学家年，以色列密码学家Eli BihamEli Biham和和Adi ShamirAdi Shamir提出了差提出了差分密码分析法，可对分密码分析法，可对DESDES进行选择明文攻击进行选择明文攻击线性密码分析比差分密码分析更有效线性密码分析比差分密码分析更有效 弱密钥与半弱密钥弱密钥与半弱密钥弱密钥弱密钥
21、:E EK K E EK K=I=I ，DESDES存在存在4 4个弱密钥个弱密钥 即：即：半弱密钥半弱密钥:E EK1K1=E=EK2K2 ，至少有，至少有1212个半弱密钥个半弱密钥 即：即：其它常规分组加密算法其它常规分组加密算法Triple DES IDEA RC5 RC6 AES其他一些较实用的算法，如其他一些较实用的算法，如Blowfish，CAST，以及，以及RC2等等使用常规加密进行保密通信使用常规加密进行保密通信易受攻击的位置易受攻击的位置电话公司电话公司市话局市话局接线盒接线盒链路加密和端到端加密链路加密和端到端加密存储转发通信的加密覆盖范围存储转发通信的加密覆盖范围各种加
22、密策略包含的内容各种加密策略包含的内容链路层加密链路层加密对于在两个网于在两个网络节点点间的某一次通信的某一次通信链路路,链路加密能路加密能为网上网上传输的数据提供安全保的数据提供安全保证所有消息在被所有消息在被传输之前之前进行加密行加密,在每一个在每一个节点点对接收接收到的消息到的消息进行解密行解密,然后先使用下一个然后先使用下一个链路的密路的密钥对消消息息进行加密行加密,再再进行行传输链路层加密的优点链路层加密的优点由于在每一个中由于在每一个中间传输节点消息均被解密后重新点消息均被解密后重新进行行加密加密,因此因此,包括路由信息在内的包括路由信息在内的链路上的所有数据均路上的所有数据均以密
23、文形式出以密文形式出现。这样,链路加密就掩盖了被路加密就掩盖了被传输消息消息的源点与的源点与终点点由于填充技由于填充技术的使用以及填充字符在不需要的使用以及填充字符在不需要传输数据数据的情况下就可以的情况下就可以进行加密行加密,这使得消息的使得消息的频率和率和长度特度特性得以掩盖性得以掩盖,从而可以防止从而可以防止对通信通信业务进行分析行分析链路层加密的缺点链路层加密的缺点链路加密通常用在点路加密通常用在点对点的同步或异步点的同步或异步线路上路上,它要求先它要求先对在在链路两端路两端的加密的加密设备进行同步行同步,然后使用一种然后使用一种链模式模式对链路上路上传输的数据的数据进行加行加密。密。
24、这就就给网网络的性能和可管理性的性能和可管理性带来了副作用来了副作用在一个网在一个网络节点点,链路加密路加密仅在通信在通信链路上提供安全性路上提供安全性,消息以明文形消息以明文形式存在式存在,因此所有因此所有节点在物理上必点在物理上必须是安全的是安全的,否否则就会泄漏明文内容就会泄漏明文内容在在传统的加密算法中的加密算法中,用于解密消息的密用于解密消息的密钥与用于加密的密与用于加密的密钥是相同的是相同的,该密密钥必必须被秘密保存被秘密保存,并按一定并按一定规则进行行变化。化。这样,密密钥分配在分配在链路加密系路加密系统中就成了一个中就成了一个问题,因因为每一个每一个节点必点必须存存储与其相与其
25、相连接的接的所有所有链路的加密密路的加密密钥,这就需要就需要对密密钥进行物理行物理传送或者建立送或者建立专用网用网络设施。而网施。而网络节点地理分布的广点地理分布的广阔性使得性使得这一一过程程变得复得复杂,同同时增加增加了密了密钥连续分配分配时的的费用用节点加密节点加密节点在操作方式上与点在操作方式上与链路加密是路加密是类似的似的:两者均在通信两者均在通信链路上路上为传输的消息提供安全性的消息提供安全性;都在中都在中间节点先点先对消息消息进行解密行解密,然后然后进行加密。因行加密。因为要要对所有所有传输的数据的数据进行加密行加密,所以加密所以加密过程程对用用户是透明的是透明的然而然而,与与链路
26、加密不同路加密不同,节点加密不允点加密不允许消息在网消息在网络节点以明文点以明文形式存在形式存在,它先把收到的消息它先把收到的消息进行解密行解密,然后采用另一个不同的然后采用另一个不同的密密钥进行加密行加密,这一一过程是在程是在节点上的一个安全模点上的一个安全模块中中进行行节点加密要求点加密要求报头和路由信息以明文形式和路由信息以明文形式传输,以便中以便中间节点能点能得到如何得到如何处理消息的信息。因此理消息的信息。因此这种方法种方法对于防止攻于防止攻击者分析者分析通信通信业务是脆弱的是脆弱的端到端加密端到端加密端到端加密允端到端加密允许数据在从源点到数据在从源点到终点的点的传输过程程中始中始
27、终以密文形式存在以密文形式存在采用端到端加密采用端到端加密(又称脱又称脱线加密或包加密加密或包加密),),消息在消息在被被传输时到达到达终点之前不点之前不进行解密行解密,因因为消息在整消息在整个个传输过程中均受到保程中均受到保护,所以即使有所以即使有节点被点被损坏坏也不会使消息泄露也不会使消息泄露端到端加密的优点端到端加密的优点端到端加密系端到端加密系统的价格便宜些的价格便宜些,与与链路加密和路加密和节点加密相点加密相比更可靠比更可靠,更容易更容易设计、实现和和维护端到端加密避免了其它加密系端到端加密避免了其它加密系统所固有的同步所固有的同步问题,因因为每个每个报文包均是独立被加密的文包均是独
28、立被加密的,所以一个所以一个报文包所文包所发生的生的传输错误不会影响后不会影响后续的的报文包文包从用从用户对安全需求的直安全需求的直觉上上讲,端到端加密更自然些。端到端加密更自然些。单个用个用户可能会可能会选用用这种加密方法种加密方法,以便不影响网以便不影响网络上的其上的其他用他用户,此方法只需要源和目的此方法只需要源和目的节点是保密的即可点是保密的即可端到端加密的缺点端到端加密的缺点通常不允通常不允许对消息的目的地址消息的目的地址进行加密行加密,这是因是因为每一个每一个消息所消息所经过的的节点都要用此地址来确定如何点都要用此地址来确定如何传输消息消息由于由于这种加密方法不能掩盖被种加密方法不
29、能掩盖被传输消息的源点与消息的源点与终点点,因因此它此它对于防止攻于防止攻击者分析通信者分析通信业务是脆弱的是脆弱的目目 录录1.数据加密标准数据加密标准2.公开密钥算法公开密钥算法公开密钥算法公开密钥算法 公公开开密密钥钥算算法法是是非非对对称称算算法法，即即密密钥钥分分为为公公钥钥和和私私钥钥，因因此称双密钥体制此称双密钥体制 双钥体制的公钥可以公开，因此也称公钥算法双钥体制的公钥可以公开，因此也称公钥算法 公公钥钥算算法法的的出出现现，给给密密码码的的发发展展开开辟辟了了新新的的方方向向。公公钥钥算算法法虽虽然然已已经经历历了了2020多多年年的的发发展展，但但仍仍具具有有强强劲劲的的发
30、发展展势势头头，在鉴别系统和密钥交换等安全技术领域起着关键的作用在鉴别系统和密钥交换等安全技术领域起着关键的作用公开密钥算法的提出公开密钥算法的提出公公钥钥密密码码学学是是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公公
31、钥钥算算法法是是由由Rivest,Shamir和和Adleman在在1978年年提提出出来的来的参参见见Communitions of the ACM.Vol.21.No.2.Feb.1978,PP.120-126该该算算法法的的数数学学基基础础是是初初等等数数论论中中的的Euler（欧欧拉拉)定定理理，并并建立在大整数因子的困难性之上建立在大整数因子的困难性之上加密与解密由不同的密钥完成加密与解密由不同的密钥完成 加密：加密：解密：解密：知知道道加加密密算算法法，从从加加密密密密钥钥得得到到解解密密密密钥钥在在计计算算上上是是不不可可行的行的两两个个密密钥钥中中任任何何一一个个都都可可以以作
32、作为为加加密密而而另另一一个个用用作作解解密密（不是必须的）（不是必须的）公开密钥算法的基本要求公开密钥算法的基本要求基于公开密钥的加密过程基于公开密钥的加密过程用公钥密码实现保密用公钥密码实现保密 用户拥有自己的密钥对用户拥有自己的密钥对(KU,KR)公钥公钥 KU公开，私钥公开，私钥KR保密保密 基于公开密钥的鉴别过程基于公开密钥的鉴别过程用公钥密码实现鉴别用公钥密码实现鉴别 条条件件：两两个个密密钥钥中中任任何何一一个个都都可可以以用用作作加加密密而而另另外外一一个个用作解密用作解密鉴别：鉴别：鉴别保密鉴别保密 公开密钥算法公开密钥算法公钥算法的种类很多，具有代表性的三种密码：公钥算法的
33、种类很多，具有代表性的三种密码：基于整数分解难题（基于整数分解难题（IFPIFP）的算法体制）的算法体制 基于离散对数难题（基于离散对数难题（DLPDLP）算法体制）算法体制基于椭圆曲线离散对数难题（基于椭圆曲线离散对数难题（ECDLPECDLP）的算法体制）的算法体制Diffie-Hellman密钥交换算法密钥交换算法单向陷门函数函数单向陷门函数函数 满足下列条件的函数满足下列条件的函数f f：(1)给定给定x，计算，计算y=f(x)是容易的是容易的 (2)给定给定y,计算计算x使使y=f(x)是困难的是困难的 (3)存在存在z，已知，已知z 时时,对给定的任何对给定的任何y，若相应的，若相
34、应的x存存 在，则计算在，则计算x使使y=f(x)是容易的是容易的所谓计算所谓计算x=x=f-1(Y)(Y)困难是指计算上相当复杂，已无实际意困难是指计算上相当复杂，已无实际意义义单向陷门函数说明单向陷门函数说明仅仅满满足足(1)、(2)两两条条的的称称为为单单向向函函数数；第第(3)条条称称为为陷陷门门性性，z 称为陷门信息称为陷门信息当当用用陷陷门门函函数数f作作为为加加密密函函数数时时，可可将将f公公开开，这这相相当当于于公公开加密密钥，此时加密密钥便称为公开钥，记为开加密密钥，此时加密密钥便称为公开钥，记为Pkf函函数数的的设设计计者者将将z保保密密，用用作作解解密密密密钥钥，此此时时
35、z称称为为秘秘密密钥钥匙匙，记记为为Sk。由由于于设设计计者者拥拥有有Sk，他他自自然然可可以以解解出出x=f-1(y)单单向向陷陷门门函函数数的的第第(2)条条性性质质表表明明窃窃听听者者由由截截获获的的密密文文y=f(x)推测推测x是不可行的是不可行的Diffie-Hellman密钥交换算法密钥交换算法Diffie和和Hellman在在其其里里程程碑碑意意义义的的文文章章中中，虽虽然然给给出出了了密密码码的的思思想想，但但是是没没有有给给出出真真正正意意义义上上的的公公钥钥密密码码实实例例，也也既没能找出一个真正带既没能找出一个真正带陷门陷门的单向函数的单向函数然然而而，他他们们给给出出单
36、单向向函函数数的的实实例例，并并且且基基于于此此提提出出Diffie-Hellman密钥交换算法密钥交换算法Diffie-Hellman密钥交换算法的原理密钥交换算法的原理基基于于有有限限域域中中计计算算离离散散对对数数的的困困难难性性问问题题之之上上：设设F为为有有限限域域，gF是是F的的乘乘法法群群 F*=F0=，并并且且对对任任意意正正整整数数x，计计算算gx是是容容易易的的；但但是是已已知知g和和y求求x使使y=gx，是是计计算算上几乎不可能的上几乎不可能的这这个个问问题题称称为为有有限限域域F上上的的离离散散对对数数问问题题。公公钥钥密密码码学学中中使用最广泛的有限域为素域使用最广泛
37、的有限域为素域FPDiffie-Hellman密钥交换协议描述密钥交换协议描述Alice和和Bob协协商商好好一一个个大大素素数数p，和和大大的的整整数数g，1gp，g最好是最好是FP中的本原元，即中的本原元，即FP*p和和g无须保密，可为网络上的所有用户共享无须保密，可为网络上的所有用户共享Diffie-Hellman密钥交换协议描述密钥交换协议描述当当Alice和和Bob要进行保密通信时，他们可以按如下步骤来做：要进行保密通信时，他们可以按如下步骤来做：(1)Alice选取大的随机数选取大的随机数x，并计算，并计算 X=gx(mod P)(2)Bob选取大的随机数选取大的随机数x，并计算，
38、并计算 X =gx (mod P)(3)Alice将将X传送给传送给Bob；Bob将将X 传送给传送给Alice (4)Alice计算计算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互互素素的的充充
39、要要条条件件是是r和和m互互素素 和和m互素的同余类数目用互素的同余类数目用(m)表示，称表示，称m的的Euler函数函数 当当m是是素素数数时时，小小于于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寻找出两个大素数寻找出两个
40、大素数p和和q (2)Bob计算出计算出n=pq 和和(n)=(p-1)(q-1)(3)Bob选择一个随机数选择一个随机数e(0e(n)，满足，满足(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；公钥
41、公钥PK=EPK=E；设：明文设：明文M M，密文，密文C C，那么：，那么：用公钥作业：用公钥作业：M ME E mod N=C mod 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,gcd(5,96)=1;e=5,gcd(5,96)=1;公钥公钥pk=5;pk=5;计算计算d,(d*e)mod 96=1;d=77;d,(d*
42、e)mod 96=1;d=77;私钥私钥sk=77;sk=77;设设:明文明文m=19m=19 加密：（加密：（1919）5 5 mod 119=66 mod 119=66 脱密：（脱密：（6666）7777 mod 119=19 mod 119=19RSA算法的安全性分析算法的安全性分析密码分析者攻击密码分析者攻击RSA体制的关键点在于如何分解体制的关键点在于如何分解n若若分分解解成成功功使使n=pq，则则可可以以算算出出(n)（p-1)(q-1)，然然后由公开的后由公开的e，解出秘密的，解出秘密的d若若使使RSA安安全全，p与与q必必为为足足够够大大的的素素数数，使使分分析析者者没没有有办
43、法在多项式时间内将办法在多项式时间内将n分解出来分解出来RSA算法的安全性分析算法的安全性分析建议选择建议选择p和和q大约是大约是100位的十进制素数位的十进制素数模模n的长度要求至少是的长度要求至少是512比特比特EDI攻攻击击标标准准使使用用的的RSA算算法法中中规规定定n的的长长度度为为512至至1024比比特特位之间，但必须是位之间，但必须是128的倍数的倍数国际数字签名标准国际数字签名标准ISO/IEC 9796中规定中规定n的长度位的长度位512比特位比特位RSA算法的安全性分析算法的安全性分析 为为了了抵抵抗抗现现有有的的整整数数分分解解算算法法，对对RSA模模n的的素素因因子子
44、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倍以上倍以上演讲完毕，谢谢观看！