.网络与信息安全 数据加密标准

1、网络与信息平安网络与信息平安DES加密算法的一般描述加密算法的一般描述输入输入64比特明文数据比特明文数据初始置换初始置换IP在密钥控制下在密钥控制下16轮迭代轮迭代初始逆置换初始逆置换IP-1输出输出64比特密文数据比特密文数据交换左右交换左右32比特比特 DES加密过程加密过程DES加密过程加密过程)(6416, 2 , 1),(16, 2 , 1)64(1616111100LRIPbitikRfLRiRLbitIPRLiiiiii密文输入码令令i表示迭代次数，表示迭代次数， 表示逐位模表示逐位模2求和，求和，f为为加密函数加密函数DES解密过程解密过程令令i表示迭代次数，表示迭代次数，

2、表示逐位模表示逐位模2求和，求和，f为为加密函数加密函数)(641 ,15,16),(1 ,15,16)64(0011111616LRIPbitikRfRLiLRbitIPLRiiiiii明文密文DES中的各种置换、扩展和替代中的各种置换、扩展和替代初始置换初始置换IP和初始逆置换和初始逆置换IP1 IP和和IP12014MM1420MMIPIP1Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算P

3、Ri（32比特）比特）Li=Ri-1DES的的一轮迭代一轮迭代扩展置换扩展置换-盒盒32位扩展到位扩展到48位位扩展扩展压缩替代压缩替代S-盒盒48位压缩到位压缩到32位位共共8个个S盒盒S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的构造盒的构造1 2 3 4 5 61 6262 3 4 521133 911001110019bbbbbbbbSbbbb行：-盒子 行 列列：值：14=1100S-盒的构造盒的构造DES中其它算法都是线性的，而中其它算法都是线性的，而S-盒运算那么是非线性盒运算那么是非线性的的S-盒不易于分析，它提供了更好的平安性盒不易于分析，它提供了更

4、好的平安性所以所以S-盒是算法的关键所在盒是算法的关键所在S-盒的构造准那盒的构造准那么么S盒的每一行是整数盒的每一行是整数0，15的一个置换的一个置换没有一个没有一个S盒是它输入变量的线性函数盒是它输入变量的线性函数改变改变S盒的一个输入位至少要引起两位的输出改变盒的一个输入位至少要引起两位的输出改变对任何一个对任何一个S盒和任何一个输入盒和任何一个输入X，SX和和 S(X001100至少有两个比特不同这里至少有两个比特不同这里X是长度为是长度为6的比特串的比特串对任何一个对任何一个S盒，对任何一个输入对盒，对任何一个输入对e,f属于属于0,1,S(X) S(X11ef00) 对任何一个对任

5、何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为这个输出比特为0的输入数目将接近于这个输出比特为的输入数目将接近于这个输出比特为1的输入数目的输入数目S-盒的构造要求盒的构造要求S-盒是许多密码算法的唯一非线性部件盒是许多密码算法的唯一非线性部件,因此因此,它的密码强度它的密码强度决定了整个算法的平安强度决定了整个算法的平安强度提供了密码算法所必须的混乱作用提供了密码算法所必须的混乱作用如何全面准确地度量如何全面准确地度量S-盒的密码强度和设计有效的盒的密码强度和设计有效的S-盒是分盒是分组密码设计和分析中的难题组密

6、码设计和分析中的难题非线性度、差分均匀性、严格雪崩准那么、可逆性、没有陷非线性度、差分均匀性、严格雪崩准那么、可逆性、没有陷门门置换置换p-盒的构造盒的构造p-盒的构造准那盒的构造准那么么P置换的目的是提供雪崩效应置换的目的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化明文或密钥的一点小的变动都引起密文的较大变化 k1 （ 56 位 ） (48 位 ) ki （ 56 位 ） （ 48 位 ） 64 位 密 钥置 换 选 择 1 C0（ 28 位 ） D0（ 28 位 ） 循 环 左 移循 环 左 移 C1（ 28 位 ） D1（ 28 位 ） 循 环 左 移循 环 左 移 Ci（

7、 28 位 ） Di（ 28 位 ）置 换 选 择 2置 换 选 择 2密 钥 表 的 计 算 逻 辑循 环 左 移 ：1 1 9 12 1 10 23 2 11 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 1DES中的子密钥的生成中的子密钥的生成密钥置换算法的构造准那么密钥置换算法的构造准那么设计目标：子密钥的统计独立性和灵活性设计目标：子密钥的统计独立性和灵活性实现简单实现简单速度速度不存在简单关系：不存在简单关系：( 给定两个有某种关系的种子密钥给定两个有某种关系的种子密钥,能预测它们轮子密能预测它们轮子密钥之间的关系钥之间的关系)种子密钥的所有比特对

8、每个子密钥比特的影响大致相同种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥没有弱密钥Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1DES的的一轮迭代一轮迭代DES加密算法的一般描述加密算法的一般描述DES的工作模式的工作模式电子密码本电子密码本 E

9、CB (electronic codebook mode)ECB (electronic codebook mode)密码分组链接密码分组链接 CBC (cipher block chaining)CBC (cipher block chaining)密码反响密码反响 CFB (cipher feedback)CFB (cipher feedback)输出反响输出反响 OFB (output feedback)OFB (output feedback)iKiiKiC = E (P) P = D (C) 电子密码本电子密码本ECBECB的特点的特点简单和有效简单和有效可以并行实现可以并行实现不能

10、隐藏明文的模式信息不能隐藏明文的模式信息 相同明文生成相同密文，同样信息屡次出现造成泄漏相同明文生成相同密文，同样信息屡次出现造成泄漏对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放误差传递：密文块损坏误差传递：密文块损坏仅对应明文块损坏仅对应明文块损坏适合于传输短信息适合于传输短信息密码分组链接密码分组链接CBCiKii-1iKii-1C = E (PC ) P = D (C ) CCBC的特点的特点没有的并行实现算法没有的并行实现算法能隐藏明文的模式信息能隐藏明文的模式信息 需要共同的初始化向量需要共同的初始化向量IVIV

11、相同明文生成不同密文相同明文生成不同密文 初始化向量初始化向量IVIV可以用来改变第一块可以用来改变第一块对明文的主动攻击是不容易的对明文的主动攻击是不容易的 信息块不容易被替换、重排、删除、重放信息块不容易被替换、重排、删除、重放 误差传递：密文块损坏误差传递：密文块损坏两明文块损坏两明文块损坏平安性好于平安性好于ECBECB适合于传输长度大于适合于传输长度大于6464位的报文，还可以进行用户鉴别位的报文，还可以进行用户鉴别, ,是大多系统的标准如是大多系统的标准如 SSLSSL、IPSecIPSec密码反响密码反响CFB CFB:CFB:分组密码分组密码流密码流密码假定：假定：Si Si

12、为移位存放器为移位存放器, ,传输单位为传输单位为jbitjbit 加密加密: Ci =Pi: Ci =Pi(EK(Si)(EK(Si)的高的高j j位位) ) Si+1=(Sij)|Ci Si+1=(Sij)|Ci 解密解密: Pi=Ci: Pi=Ci(EK(Si)(EK(Si)的高的高j j位位) ) Si+1=(Sij)|Ci Si+1=(Sij)|Ci密码反响密码反响CFB加密加密Ci =Pi (EK(Si)的高的高j位位) ; Si+1=(Sij)|Ci 密码反响密码反响CFB解密解密Pi=Ci (EK(Si)的高的高j位位); Si+1=(Sij)|Ci CFB的特点的特点分组密码

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

14、的高j j位位) ) 解密解密: Pi=Ci: Pi=Ci(EK(Si)(EK(Si)的高的高j j位位) ) Si+1=(Sij)|(EK(Si) Si+1=(Sij)|(EK(Si)的高的高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的特点的特点分组密码分组密码流密码流密码没有的并行实现算法没有的并行实现算法隐藏了明文模式隐藏了明文模式需要共同的移位存放器初始

15、值需要共同的移位存放器初始值IVIV对于不同的消息，对于不同的消息，IVIV必须唯一必须唯一误差传递：一个单元损坏只影响对应单元误差传递：一个单元损坏只影响对应单元对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放平安性较平安性较CFBCFB差差多重多重DES两重两重DES三重三重DESDES的平安性的平安性 F F函数函数(S-Box)(S-Box)设计原理未知设计原理未知 密钥长度的争论密钥长度的争论 DESDES的的破译破译 弱密钥与半弱密钥弱密钥与半弱密钥DES密钥长度密钥长度关于关于DESDES算法的另一个最有争议的问题

16、就是担忧实际算法的另一个最有争议的问题就是担忧实际5656比特的密钥长度缺乏以抵御穷举式攻击，因为密钥量只比特的密钥长度缺乏以抵御穷举式攻击，因为密钥量只有有 个个 早在早在19771977年，年，DiffieDiffie和和HellmanHellman已建议制造一个每秒能已建议制造一个每秒能测试测试100100万个密钥的万个密钥的VLSIVLSI芯片。每秒测试芯片。每秒测试100100万个密钥的万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要制造这样的机器大约需要20002000万美元万美元1756102DES密

17、钥长度密钥长度在在CRYPTO93上，上，Session和和Wiener给出了一个非常详细给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以钥搜索芯片，所以16次加密能同时完成。花费次加密能同时完成。花费10万万美元，美元，平均用平均用1.5天左右就可找到天左右就可找到DES密钥密钥美国克罗拉多洲的程序员美国克罗拉多洲的程序员Verser从从1997年年2 2月月18日起，用了日起，用了96天时间，在天时间，在Internet上数万名志愿者的协同工作下，成上数万名志愿者的协同工作下，成功地找到了功地找到了DES

18、的密钥，赢得了悬赏的的密钥，赢得了悬赏的1万美元万美元DES密钥长度密钥长度19981998年年7 7月电子前沿基金会月电子前沿基金会EFFEFF使用一台使用一台2525万美圆的电万美圆的电脑在脑在5656小时内破译了小时内破译了5656比特密钥的比特密钥的DESDES19991999年年1 1月月RSARSA数据平安会议期间，电子前沿基金会用数据平安会议期间，电子前沿基金会用2222小小时时1515分钟就宣告破解了一个分钟就宣告破解了一个DESDES的密钥的密钥破译破译DES19901990年，以色列密码学家年，以色列密码学家Eli BihamEli Biham和和Adi ShamirAdi

19、 Shamir提出了提出了差分密码分析法，可对差分密码分析法，可对DESDES进行选择明文攻击进行选择明文攻击线性密码分析比差分密码分析更有效线性密码分析比差分密码分析更有效 弱密钥与半弱密钥弱密钥与半弱密钥弱密钥弱密钥: : E EK K E EK K = I = I ，DESDES存在存在4 4个弱密钥个弱密钥 即：即：半弱密钥半弱密钥: : E EK1K1 = E = EK2K2 ，至少有，至少有1212个半弱密钥个半弱密钥 即：即：( )kkpE E P12( )( )kkC E PE P其它常规分组加密算法其它常规分组加密算法Triple DES IDEA RC5 RC6 AES其他

20、一些较实用的算法，如其他一些较实用的算法，如Blowfish，CAST，以及，以及RC2等等使用常规加密进行保密通信使用常规加密进行保密通信易受攻击的位置易受攻击的位置 公司公司市话局市话局接线盒接线盒链路加密和端到端加密链路加密和端到端加密存储转发通信的加密覆盖范围存储转发通信的加密覆盖范围各种加密策略包含的内容各种加密策略包含的内容链路层加密链路层加密对于在两个网络节点间的某一次通信链路对于在两个网络节点间的某一次通信链路, ,链路加密能链路加密能为网上传输的数据提供平安保证为网上传输的数据提供平安保证所有消息在被传输之前进行加密所有消息在被传输之前进行加密, ,在每一个节点对接收在每一个

21、节点对接收到的消息进行解密到的消息进行解密, ,然后先使用下一个链路的密钥对消然后先使用下一个链路的密钥对消息进行加密息进行加密, ,再进行传输再进行传输链路层加密的优点链路层加密的优点由于在每一个中间传输节点消息均被解密后重新进行由于在每一个中间传输节点消息均被解密后重新进行加密加密, ,因此因此, ,包括路由信息在内的链路上的所有数据均包括路由信息在内的链路上的所有数据均以密文形式出现。这样以密文形式出现。这样, ,链路加密就掩盖了被传输消息链路加密就掩盖了被传输消息的源点与终点的源点与终点由于填充技术的使用以及填充字符在不需要传输数据由于填充技术的使用以及填充字符在不需要传输数据的情况下

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

23、提供平安性链路加密仅在通信链路上提供平安性, ,消息以明文形消息以明文形式存在式存在, ,因此所有节点在物理上必须是平安的因此所有节点在物理上必须是平安的, ,否那么就会泄漏明文内否那么就会泄漏明文内容容在传统的加密算法中在传统的加密算法中, ,用于解密消息的密钥与用于加密的密钥是相同的用于解密消息的密钥与用于加密的密钥是相同的, ,该密钥必须被秘密保存该密钥必须被秘密保存, ,并按一定规那么进行变化。这样并按一定规那么进行变化。这样, ,密钥分配在密钥分配在链路加密系统中就成了一个问题链路加密系统中就成了一个问题, ,因为每一个节点必须存储与其相连接因为每一个节点必须存储与其相连接的所有链路

24、的加密密钥的所有链路的加密密钥, ,这就需要对密钥进行物理传送或者建立专用网这就需要对密钥进行物理传送或者建立专用网络设施。而网络节点地理分布的广阔性使得这一过程变得复杂络设施。而网络节点地理分布的广阔性使得这一过程变得复杂, ,同时增同时增加了密钥连续分配时的费用加了密钥连续分配时的费用节点加密节点加密节点在操作方式上与链路加密是类似的节点在操作方式上与链路加密是类似的: :两者均在通信链路上为两者均在通信链路上为传输的消息提供平安性传输的消息提供平安性; ;都在中间节点先对消息进行解密都在中间节点先对消息进行解密, ,然后然后进行加密。因为要对所有传输的数据进行加密进行加密。因为要对所有传

25、输的数据进行加密, ,所以加密过程对所以加密过程对用户是透明的用户是透明的然而然而, ,与链路加密不同与链路加密不同, ,节点加密不允许消息在网络节点以明文节点加密不允许消息在网络节点以明文形式存在形式存在, ,它先把收到的消息进行解密它先把收到的消息进行解密, ,然后采用另一个不同的然后采用另一个不同的密钥进行加密密钥进行加密, ,这一过程是在节点上的一个平安模块中进行这一过程是在节点上的一个平安模块中进行节点加密要求报头和路由信息以明文形式传输节点加密要求报头和路由信息以明文形式传输, ,以便中间节点能以便中间节点能得到如何处理消息的信息。因此这种方法对于防止攻击者分析得到如何处理消息的信

26、息。因此这种方法对于防止攻击者分析通信业务是脆弱的通信业务是脆弱的端到端加密端到端加密端到端加密允许数据在从源点到终点的传输过程端到端加密允许数据在从源点到终点的传输过程中始终以密文形式存在中始终以密文形式存在采用端到端加密采用端到端加密( (又称脱线加密或包加密又称脱线加密或包加密),),消息在消息在被传输时到达终点之前不进行解密被传输时到达终点之前不进行解密, ,因为消息在整因为消息在整个传输过程中均受到保护个传输过程中均受到保护, ,所以即使有节点被损坏所以即使有节点被损坏也不会使消息泄露也不会使消息泄露端到端加密的优点端到端加密的优点端到端加密系统的价格廉价些端到端加密系统的价格廉价些

27、, ,与链路加密和节点加密相与链路加密和节点加密相比更可靠比更可靠, ,更容易设计、实现和维护更容易设计、实现和维护端到端加密防止了其它加密系统所固有的同步问题端到端加密防止了其它加密系统所固有的同步问题, ,因为因为每个报文包均是独立被加密的每个报文包均是独立被加密的, ,所以一个报文包所发生的所以一个报文包所发生的传输错误不会影响后续的报文包传输错误不会影响后续的报文包从用户对平安需求的直觉上讲从用户对平安需求的直觉上讲, ,端到端加密更自然些。单端到端加密更自然些。单个用户可能会选用这种加密方法个用户可能会选用这种加密方法, ,以便不影响网络上的其以便不影响网络上的其他用户他用户, ,此

28、方法只需要源和目的节点是保密的即可此方法只需要源和目的节点是保密的即可端到端加密的缺点端到端加密的缺点通常不允许对消息的目的地址进行加密通常不允许对消息的目的地址进行加密, ,这是因为每一个这是因为每一个消息所经过的节点都要用此地址来确定如何传输消息消息所经过的节点都要用此地址来确定如何传输消息由于这种加密方法不能掩盖被传输消息的源点与终点由于这种加密方法不能掩盖被传输消息的源点与终点, ,因因此它对于防止攻击者分析通信业务是脆弱的此它对于防止攻击者分析通信业务是脆弱的目目 录录数据加密标准数据加密标准1.公开密钥算法公开密钥算法公开密钥算法公开密钥算法 公开密钥算法是非对称算法，即密钥分为公

29、钥和私钥，公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制因此称双密钥体制 双钥体制的公钥可以公开，因此也称公钥算法双钥体制的公钥可以公开，因此也称公钥算法 公钥算法的出现，给密码的开展开辟了新的方向。公钥公钥算法的出现，给密码的开展开辟了新的方向。公钥算法虽然已经历了算法虽然已经历了20多年的开展，但仍具有强劲的开展势多年的开展，但仍具有强劲的开展势头，在鉴别系统和密钥交换等平安技术领域起着关键的作头，在鉴别系统和密钥交换等平安技术领域起着关键的作用用公开密钥算法的提出公开密钥算法的提出公钥密码学是公钥密码学是1976年由年由Diffie和和Hellman在其在其“密码学新方

30、密码学新方向一文中提出的，见文献：向一文中提出的，见文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography， IEEE Transaction on Information Theory, 公开密钥算法的提出公开密钥算法的提出RSA公钥算法是由公钥算法是由Rivest,Shamir和和Adleman在在1978年提出年提出来的来的参见参见Communitions该算法的数学根底是初等数论中的该算法的数学根底是初等数论中的Euler欧拉欧拉)定理，并定理，并建立在大整数因子的困难性之上建立在大整数因子的困难性之上加密与解密由不同

31、的密钥完成加密与解密由不同的密钥完成 加密：加密： 解密：解密：知道加密算法，从加密密钥得到解密密钥在计算上是不可知道加密算法，从加密密钥得到解密密钥在计算上是不可行的行的两个密钥中任何一个都可以作为加密而另一个用作解密两个密钥中任何一个都可以作为加密而另一个用作解密不是必须的不是必须的公开密钥算法的根本要求公开密钥算法的根本要求:( )KUXY YEX:( )( )KRKRKUYX XDYDEX基于公开密钥的加密过程基于公开密钥的加密过程用公钥密码实现保密用公钥密码实现保密 用户拥有自己的密钥对用户拥有自己的密钥对(KU,KR) 公钥公钥 KU公开，私钥公开，私钥KR保密保密 :( )bKU

32、AB YEX:( )( )bbbKRKRKUB DYDEXX基于公开密钥的鉴别过程基于公开密钥的鉴别过程用公钥密码实现鉴别用公钥密码实现鉴别 条件：两个密钥中任何一个都可以用作加密而另外一个条件：两个密钥中任何一个都可以用作加密而另外一个用作解密用作解密鉴别：鉴别： 鉴别保密鉴别保密 :():( )()aabaKRKUKUKRAALL YEXALL DYDEXX:():( )baabKUKRKUKRAB ZEDXB EDZX公开密钥算法公开密钥算法公钥算法的种类很多，具有代表性的三种密码：公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题基于整数分解难题IFP的算法体制的算法体制 基

33、于离散对数难题基于离散对数难题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)困难是指计算上相当复杂，已无实际意

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

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

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

37、个大素数协商好一个大素数p，和大的整数，和大的整数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将将

38、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互素的充要条件是互素的充要条件是r和和m互素互素 和和m互素的同余类数目用互素的同余类数目

39、用(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, p=3, q=5, 那么那么 1515= =3-13-1* *5-15-1=8=8 这这8 8个模个模1515的剩余类是：的剩余类是： 11，2 2，4 4，7 7，8 8，1111，1313，14 14 RSA算法的实现算法的实现 实现的步骤如下：实现的步骤如下：Bob为实现者为实现者 (1) Bob寻找出两个大素数寻找出两个大素数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