网络安全 第4章信息保密技术

1、信息保密技术信息保密技术 密码学中常见的两种体制: u对称密码体制(单钥密码体制) u 如果一个加密系统的加密密钥和解密密钥相 同，或者虽然不相同，但是由其中的任意一个可 以很容易地推导出另一个，即密钥是双方共享的, 则该系统所采用的就是对称密码体制。 u非对称密码体制(公钥密码体制) u 在公钥体制中，加密密钥不同于解密密钥。 将加密密钥公之于众，谁都可以使用；而解密密 钥只有解密人自己知道。 一、对称加密算法DES n美国数据加密标准美国数据加密标准DES（Data Encryption Standard） 美国制定数据加密标准简况美国制定数据加密标准简况 n目的目的 通信与计算机相结合是

2、人类步入信息社会的一个阶梯，通信与计算机相结合是人类步入信息社会的一个阶梯， 它始于六十年代末，完成于它始于六十年代末，完成于90年代初。计算机通信网的形年代初。计算机通信网的形 成与发展，要求信息作业标准化，安全保密亦不例外。成与发展，要求信息作业标准化，安全保密亦不例外。只只 有标准化，才能真正实现网络的安全，才能推广使用加密有标准化，才能真正实现网络的安全，才能推广使用加密 手段，以便于训练、生产和降低成本。手段，以便于训练、生产和降低成本。 背景背景 发明人发明人：美国：美国IBM公司公司 W. Tuchman 和和 C. Meyer 1971-1972年研制成功年研制成功 基础：基础

3、：1967年美国年美国Horst Feistel提出的理论提出的理论 产生：美国国家标准局（产生：美国国家标准局（NBS)1973年年5月到月到1974年年8月两次发布通告，月两次发布通告， 公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳 了了IBM的的LUCIFER方案方案 标准化：标准化：DES算法算法1975年年3月公开发表，月公开发表，1977年年1月月15日由美国国家标日由美国国家标 准局颁布为数据加密标准（准局颁布为数据加密标准（Data Encryption Standard），于），于 1977年年7月月15

4、日生效日生效 背景背景 美国国家安全局（美国国家安全局（NSA, National Security Agency)参与了美国国参与了美国国 家标准局制定数据加密标准的过程。家标准局制定数据加密标准的过程。NBS接受了接受了NSA的某些建议，的某些建议， 对算法做了修改，并将密钥长度从对算法做了修改，并将密钥长度从LUCIFER方案中的方案中的128位压缩到位压缩到 56位位 1979年，美国银行协会批准使用年，美国银行协会批准使用DES 1980年，年，DES成为美国标准化协会成为美国标准化协会(ANSI)标准标准 1984年年2月，月，ISO成立的数据加密技术委员会成立的数据加密技术委员会

5、(SC20)在在DES基础上基础上 制定数据加密的国际标准工作制定数据加密的国际标准工作 DES首次被批准使用五年，并规定每隔五年由美国国首次被批准使用五年，并规定每隔五年由美国国 家保密局作出评估，并重新批准它是否继续作为联邦加密家保密局作出评估，并重新批准它是否继续作为联邦加密 标准。最近的一次评估是在标准。最近的一次评估是在1994年年1月，美国已决定月，美国已决定1998年年 12月以后将不再使用月以后将不再使用DES。因为按照现有的技术水平，采。因为按照现有的技术水平，采 用不到几十万美元的设备，就可破开用不到几十万美元的设备，就可破开DES密码体制。目前密码体制。目前 的新标准是的

6、新标准是AES，它是由比利时的密码学家，它是由比利时的密码学家Joan Daemen和和 Vincent Rijmen设计的分组密码设计的分组密码Rijndael（荣代尔）。（荣代尔）。 美国制定数据加密标准简况美国制定数据加密标准简况 n1997年年DESCHALL小组经过近小组经过近4个月的努力，通过个月的努力，通过 Internet搜索了搜索了31016个密钥，找出了个密钥，找出了DES的密钥，恢的密钥，恢 复出了明文。复出了明文。 n1998年年5月美国月美国EFF(electronics frontier foundation) 宣布，他们以一台价值宣布，他们以一台价值20万美元的计

7、算机改装成的专用解万美元的计算机改装成的专用解 密机，用密机，用56小时破译了小时破译了56 比特密钥的比特密钥的DES。 美国制定数据加密标准简况美国制定数据加密标准简况 n尽管如此，尽管如此，DES对于推动密码理论的发展和应用毕竟起了对于推动密码理论的发展和应用毕竟起了 重大作用，对于掌握分组密码的基本理论、设计思想和实重大作用，对于掌握分组密码的基本理论、设计思想和实 际应用仍然有着重要的参考价值。际应用仍然有着重要的参考价值。 DES 算法算法 n分组长度为分组长度为64 bits (8 bytes) n密文分组长度也是密文分组长度也是64 bits。 n密钥长度为密钥长度为64 bi

8、ts，有，有8 bits奇偶校验，有效密钥长奇偶校验，有效密钥长 度为度为56 bits。 n算法主要包括：初始置换算法主要包括：初始置换IP、16轮迭代的乘积变换、轮迭代的乘积变换、 逆初始置换逆初始置换IP-1以及以及16个子密钥产生器。个子密钥产生器。 DES加密算法框图 子密钥产生器子密钥产生器 16轮迭代轮迭代 的乘积变换的乘积变换 DES算法框图算法框图 输入 64 bit明文数据 初始置换IP 乘积变换 （16轮迭代） 逆初始置换IP-1 64 bit密文数据 输出 标准数据加密算法 585042342618102 605244362820124 625446383022146

9、645648403224168 57494133251791 595143352719113 615345372921135 635547393123157 408481656246432 397471555236331 386461454226230 375451353216129 364441252206028 353431151195927 342421050185826 33141949175725 （a）初始置换）初始置换IP (b)逆初始置换逆初始置换IP -1 初始置换初始置换IPIP n将将64 bit明文的位置进行置换，得到一个乱明文的位置进行置换，得到一个乱 序的序的64

10、bit明文组，而后分成左右两段，每明文组，而后分成左右两段，每 段为段为32 bit，以，以L0和和R0表示，表示，IP中各列元素中各列元素 位置号数相差为位置号数相差为8。 n逆初始置换逆初始置换IPIP-1 -1 将 将16轮迭代后给出的轮迭代后给出的64 bit 组进行置换，得到输出的密文组。输出为组进行置换，得到输出的密文组。输出为 阵中元素按行读得的结果。阵中元素按行读得的结果。 nIP和和IPIP-1 -1在密码意义上作用不大，它们的作 在密码意义上作用不大，它们的作 用在于打乱原来输入用在于打乱原来输入x x的的ASCII码字划分的码字划分的 关系。关系。 DES加密算法的轮结构

11、加密算法的轮结构 密钥流生成器密钥流生成器 乘积变换乘积变换 n它是它是DES算法的核心部分。将经过算法的核心部分。将经过IP置换后的数据分成置换后的数据分成32 bit的左右两组，在迭代过程中彼此左右交换位置。的左右两组，在迭代过程中彼此左右交换位置。 n每次迭代时只对右边的每次迭代时只对右边的32 bit进行一系列的加密变换，在此进行一系列的加密变换，在此 轮迭代即将结束时，把左边的轮迭代即将结束时，把左边的32 bit与右边得到的与右边得到的32 bit逐位逐位 模模2相加，作为下一轮迭代时右边的段，并将原来右边未经相加，作为下一轮迭代时右边的段，并将原来右边未经 变换的段直接送到左边的

12、寄存器中作为下一轮迭代时左边变换的段直接送到左边的寄存器中作为下一轮迭代时左边 的段。的段。 n在每一轮迭代时，右边的段要经过在每一轮迭代时，右边的段要经过选择扩展运算选择扩展运算E E、密钥加、密钥加 密运算、选择压缩运算密运算、选择压缩运算S S、置换运算、置换运算P P和左右混合运算和左右混合运算。 选择扩展运算选择扩展运算E E 将输入的将输入的32 bit Ri-1扩展扩展 成成48 bit的输出，令的输出，令s表示表示E 原输入数据比特的原下标，原输入数据比特的原下标， 则则E的输出是将原下标的输出是将原下标s 0 或或1(mod 4)的各比特重复的各比特重复 一次得到的，即对原第

13、一次得到的，即对原第1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29，32各位都重各位都重 复一次复一次,实现数据扩展。将实现数据扩展。将 表中数据按行读出得到表中数据按行读出得到48 bit输出。输出。(表表c) 3212345 456789 8910111213 121314151617 161718192021 202122232425 242526272829 28293031321 密钥加密运算密钥加密运算 将子密钥产生器输出的将子密钥产生器输出的48 bit子子 密钥密钥ki与选择扩展运算与选择扩展运算E输出的输出的48 b

14、its数据按位模数据按位模2相加。相加。 选择压缩运算选择压缩运算S。将前面送来的将前面送来的48 bit数据自左至右分成数据自左至右分成 8组，每组为组，每组为6 bit。而后并行送入。而后并行送入8个个S盒，每个盒，每个S盒为一盒为一 非线性代换网络，有非线性代换网络，有4个输出，运算个输出，运算S的框图如下。的框图如下。 48 bit 寄存器 32 bit 寄存器 S1S2S3S4S5S6S7S8 DES的的S1-盒的输入和输出关系盒的输入和输出关系 nx5 x0 x5 x4 x3 x2 x1 x0 1 0 1 0 1 1 0 0 列号列号 0 1 2 3 4 5 6 7 8 9 10

15、11 12 13 14 15 行号行号 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13 (y3 , y2, y1 , y0)=(0,0,1,0) 置换运算置换运算P P 对对S1至至S8盒输出的盒输出的32 bit数据进行坐标置换，置换数据进行坐标置换，置换P输出的输出的 32 bit数据与左边数据与左边32 bit即即Li-

16、1逐位模逐位模2相加，所得到的相加，所得到的32 bit作作 为下一轮迭代用的右边的数字段为下一轮迭代用的右边的数字段Ri 。并将。并将Ri-1并行送到左边并行送到左边 的寄存器，作为下一轮迭代用的左边的数字段的寄存器，作为下一轮迭代用的左边的数字段Li 。（表。（表d） 167202129122817 11523265183110 282414322739 19133062211425 函数F(R,K)计算过程 R (32比特) K (48比特) 48比特 E + P 32比特 1 S 2 S 3 S 4 S 5 S 6 S 7 S 8 S 子密钥产生器子密钥产生器 n将将64 bit初始密

17、初始密 钥经过：钥经过： 置换选择置换选择PC-1PC-1 循环移位循环移位 置换选择置换选择PC-2PC-2 n给出每次迭代给出每次迭代 加密用的子密钥加密用的子密钥ki， 置换选择1 64比特 子密钥产生器框图子密钥产生器框图 密钥（64 bit ） 置换选择1，PC1 置换选择2，PC2 Ci(28 bit) Di(28 bit) 循环左移ti+1bit 循环左移ti+1bit 除去第8,16, ,64位(8个校验位) ki 5749413325179 1585042342618 1025951433527 1911360504436 63554739312315 76254463830

18、22 1466153453729 211352820124 1417112415328 15621102319124 2681672720132 4152313747553040 5145334844493956 3453464250362932 置换选择置换选择2（PC-2） 置换选择置换选择1（PC-1） 迭 代 次 数 12345678 循 环 左 移 位 数 11222222 迭 代 次 数 91 0 11121 3 141 5 1 6 循 环 左 移 位 数 12222221 左循环移位位数左循环移位位数 DES的安全性安全性 n穷举攻击分析穷举攻击分析 穷举攻击就是对所有可能的密钥

19、逐个进穷举攻击就是对所有可能的密钥逐个进 行脱密测试，直到找到正确密钥为止的一种行脱密测试，直到找到正确密钥为止的一种 攻击方法。攻击方法。 穷举攻击判断正确密钥的方法：穷举攻击判断正确密钥的方法： 将利用试验密钥解密得到的可能明文与将利用试验密钥解密得到的可能明文与 已掌握的明文的信息相比较，并将最吻合的已掌握的明文的信息相比较，并将最吻合的 那个试验密钥作为算法输出的正确密钥。那个试验密钥作为算法输出的正确密钥。 穷举攻击又称为穷尽攻击、强力攻击、穷举攻击又称为穷尽攻击、强力攻击、 蛮干攻击等。只要明文不是随机的，就蛮干攻击等。只要明文不是随机的，就 可实施穷举攻击。可实施穷举攻击。 二重

20、二重DES n明文为明文为P，两个加密密钥，两个加密密钥k1和和k2，密文，密文 为：为： C=Ek2Ek1P n解密时，解密时， P=Dk1Dk2C X EEDD P C P XC k1 k1k2k2 讨论：使用二重讨论：使用二重DES产生的映射是否等价于单产生的映射是否等价于单 重重DES加密加密? 二重二重DES 用用DES进行两次加密，但这是否就意味着进行两次加密，但这是否就意味着 两重两重DES加密的强度等价于加密的强度等价于112 bit密钥的密密钥的密 码的强度？答案是否定的。码的强度？答案是否定的。 三重三重DES加密加密 加密：加密：y=Ek1Dk2Ek1 x 解密：解密：x

21、=Dk1Ek2Dk1y n称其为加密称其为加密-解密解密-加密方案，简记为加密方案，简记为EDE(encrypt- decrypt-encrypt)。 n此方案已在此方案已在ANSI X9.17和和ISO 8732标准中采用，并标准中采用，并 在保密增强邮递在保密增强邮递(PEM)系统中得到利用。系统中得到利用。 n破译它的穷举密钥搜索量为破译它的穷举密钥搜索量为2112 51035量级，而量级，而 用差分分析破译也要超过用差分分析破译也要超过1052量级。此方案仍有足量级。此方案仍有足 够的安全性。够的安全性。 分组密码的运行模式 分组密码在加密时，明文分组的长度固定。分组密码在加密时，明文

22、分组的长度固定。 实际应用中待加密消息的数据长度和格式各实际应用中待加密消息的数据长度和格式各 有不同。有不同。 为了能在各种应用场合使用为了能在各种应用场合使用DES，定义了，定义了 DES的的4种运行模式，这些模式也可用于其他种运行模式，这些模式也可用于其他 分组密码。分组密码。 1 电码本（电码本（ECB）模式）模式 消息分为长为消息分为长为64比特的分组，最后一个分组如果不比特的分组，最后一个分组如果不 够够64比特，则需要比特，则需要填充填充。 明文是由分组长为明文是由分组长为64比特的分组序列比特的分组序列P1，P2， PN构成，相应的密文分组序列是构成，相应的密文分组序列是C1，

23、C2，CN。 ECB的的最大特性最大特性是同一明文分组在消息中重复出现是同一明文分组在消息中重复出现 的话，产生的密文分组也相同。的话，产生的密文分组也相同。 ECB用于长消息时可能不够安全，如果消息有固定用于长消息时可能不够安全，如果消息有固定 结构，密码分析者有可能找出这种关系。结构，密码分析者有可能找出这种关系。 ECB在用于在用于短数据短数据（如加密密钥）时非常理想，因（如加密密钥）时非常理想，因 此如果需要安全地传递此如果需要安全地传递DES密钥，密钥，ECB是最合适的模是最合适的模 式。式。 2 密码分组链接（密码分组链接（CBC）模式）模式 11111KnnKKnnnnnnn D

24、CCDECPCCPCP 1nKnn CECP 解密时：每一个密文分解密时：每一个密文分 组被解密后，再与前一组被解密后，再与前一 个密文分组异或得明文个密文分组异或得明文 解决解决ECB的安全缺陷的安全缺陷： 可以让重复的明文分组可以让重复的明文分组 产生不同的密文分组产生不同的密文分组 加密时：输入是当前加密时：输入是当前 明文分组和前一次密明文分组和前一次密 文分组的异或文分组的异或 初始向量初始向量IV IV应像密钥一样被保护，可使用应像密钥一样被保护，可使用ECB加密模式来发加密模式来发 送送IV。 保护保护IV的原因：如果敌手篡改的原因：如果敌手篡改IV中的某些比特，则中的某些比特，

25、则 接收方收到的接收方收到的P1中相应的比特也发生了变化。中相应的比特也发生了变化。 11 11 K K CEIVP PIVDC 第一次加、解密需第一次加、解密需IV 由于由于CBC 模式的链接机制，模式的链接机制，CBC模式对模式对加密长消息加密长消息非常合适。非常合适。 CBC模式除能够获得保密性外，还能用于认证。模式除能够获得保密性外，还能用于认证。 3 密码反馈（ 密码反馈（CFB）模式）模式 加密算法的输入是加密算法的输入是64比特比特 移位寄存器，其初值为某个移位寄存器，其初值为某个 初始向量初始向量IV。 加密算法输出的最左（最高加密算法输出的最左（最高 有效位）有效位）j比特与

26、明文的第一比特与明文的第一 个单元个单元P1进行异或，产生出进行异或，产生出 密文的第密文的第1个单元个单元C1，并传送，并传送 该单元。该单元。 然后将移位寄存器的内容左然后将移位寄存器的内容左 移移j位并将位并将C1送入移位寄存器送入移位寄存器 最右边（最低有效位）最右边（最低有效位）j位。位。 这一过程继续到明文的所有这一过程继续到明文的所有 单元都被加密为止。单元都被加密为止。 设设Sj(X)是是X的的j个最高有限个最高有限 位，那么：位，那么： 11j CPSE IV 11j PCSE IV 加密加密 解密解密 CFB特点特点 nDES是分组长为是分组长为64比特的分组密码，但利比特

27、的分组密码，但利 用用CFB模式或模式或OFB模式可将模式可将DES转换为流转换为流 密码。密码。 如果需要发送如果需要发送字符流字符流，每个字符长为，每个字符长为8比特比特, 就应使用就应使用8比特密钥来加密每个字符比特密钥来加密每个字符.通常取通常取 j=8 流密码不需要对消息填充，而且运行是实时流密码不需要对消息填充，而且运行是实时 的的 图3.13 OFB模式示意图 4 输出反馈 输出反馈(OFB)模式模式 OFB（output feedback）模式的结构类似于）模式的结构类似于 CFB。 不同之处不同之处 OFB模式是将加密算法的输出反馈到移位寄存器，模式是将加密算法的输出反馈到移

28、位寄存器， CFB模式中是将密文单元反馈到移位寄存器。模式中是将密文单元反馈到移位寄存器。 OFB优点：传输过程中的比特错误不会被传播。优点：传输过程中的比特错误不会被传播。 OFB 中，中，C1中出现中出现1比特错误，在解密结果中只有比特错误，在解密结果中只有P1受到影响，以受到影响，以 后各明文单元则不受影响。后各明文单元则不受影响。 CFB中，中，C1也作为移位寄存器的输入，因此它的也作为移位寄存器的输入，因此它的1比特错误会影响比特错误会影响 解密结果中各明文单元的值。解密结果中各明文单元的值。 OFB的缺点：比的缺点：比CFB模式更易受到对消息流的篡改攻击。模式更易受到对消息流的篡改

29、攻击。 比较和选用比较和选用 nECB模式，简单、高速，但最易受重发攻击。模式，简单、高速，但最易受重发攻击。 nCBC适用于文件加密，但较适用于文件加密，但较ECB慢。慢。 nOFB和和CFB较较CBC慢许多。每次迭代只有少数慢许多。每次迭代只有少数bit 完成加密。完成加密。 nOFB用于高速同步系统，传输过程中的比特错误用于高速同步系统，传输过程中的比特错误 不会被传播不会被传播. nCFB多用在字符为单元的流密码中多用在字符为单元的流密码中,有错误扩展有错误扩展 分组密码的分析方法 n解密与密码分析解密与密码分析 u 解密是加密的逆过程，是指掌握密钥解密是加密的逆过程，是指掌握密钥 和

30、密码算法的合法人员从密文恢复出和密码算法的合法人员从密文恢复出 明文的过程。明文的过程。 u密码分析则是指非法人员对密码的破密码分析则是指非法人员对密码的破 译，而且破译以后不会告诉对方。译，而且破译以后不会告诉对方。 分组密码的分析方法 n根据攻击者掌握的信息，可将分组密码的攻击分为 以下几类： u唯密文攻击：攻击者除了所截获的密文外，没有其他可 利用的信息。 u已知明文攻击： 攻击者仅知道当前密钥下的一些明密 文对。 u选择明文攻击：攻击者能获得当前密钥下的一些特定 的明文所对应的密文。 u选择密文攻击：攻击者能获得当前密钥下的一些特定 的密文所对应的明文。 分组密码的分析方法(续） u一

31、种攻击的复杂度可以分为两部分：数据复杂 度和处理复杂度。 p数据复杂度是实施该攻击所需输入的数据量。 p处理复杂度是处理这些数据所需的计算量。 u对某一攻击通常是以这两个方面的某一方面为 主要因素，来刻画攻击复杂度 。 n 【例如】 p穷举攻击的复杂度实际就是考虑处理复杂度； p差分密码分析其复杂度主要是由该攻击所需的明密 文对的数量来确定。 几种常见的攻击方法 n1.强力攻击强力攻击 n强力攻击可用于任何分组密码，且攻击的复杂度 n只依赖于分组长度和密钥长度，严格地讲攻击所 n需的时间复杂度依赖于分组密码的工作效率（包 n括加解密速度、密钥扩散速度以及存储空间等）。 n强力攻击常见的有：穷举

32、密钥搜索攻击穷举密钥搜索攻击、 n字典攻击字典攻击、查表攻击和时间查表攻击和时间-存储权衡攻击存储权衡攻击等。 几种常见的攻击方法（续） n2.差分密码分析差分密码分析 n基本思想基本思想 n通过分析明文对的差值对密文对的差值的影响 来恢复某些密钥比特。 n 若给定一个r轮的迭代密码，对已知n长明文对 为 n 和 ，定义其差分为 n 式中 表示集合中定义的群运算， 为 在 群中的逆元。 n密码分析者可随机选择具有固定差分的一对明 文（只要求它们符合特定差分条件），然后使用输出 密文中的差分，按照不同的概率分配给不同的密钥。 随着分析的密文对越来越多，其中最可能的一个密钥 就显现出来了。这就是正

33、确的密钥。 X X 1 XXX 1 X X 几种常见的攻击方法（续） n3.线性密码分析线性密码分析 u本质： 一种已知明文攻击方法。 u基本思想 ：通过寻找一个给定密码算法的有效的 n线性近似表达式来破译密码系统。 n对已知明文密文和特定密钥，寻求线性表示式 n n式中， 是攻击参数。对所有可能密钥，此表 n达式以概率 成立。对给定的密码算法， n使 极大化。为此对每一盒的输入和输 n出构造统计线性路线，并最终扩展到整个算法。 xdybxa dba, 2/1 L P 2/1 L P 二、公钥加密算法RSA 二、公钥加密算法二、公钥加密算法RSARSA 公钥密码体制的基本原理公钥密码体制的基本

34、原理 公钥密码体制采用了两个不同的密钥，这公钥密码体制采用了两个不同的密钥，这 对在公开的网络上进行对在公开的网络上进行保密通信保密通信、密钥密钥 分配分配、数字签名和认证数字签名和认证有着深远的影响。有着深远的影响。 对称密码的不足对称密码的不足 密钥管理量的困难：密钥管理量的困难：两两分别用一个密钥时，两两分别用一个密钥时， 则则n n个用户需要个用户需要C(n,2)=n(n-1)/2C(n,2)=n(n-1)/2个密钥，当用户量个密钥，当用户量 增大时，密钥空间急剧增大。如增大时，密钥空间急剧增大。如:n=100 :n=100 时，共时，共 4,9954,995个；个；n=5000n=5

35、000时增加到时增加到12,497,50012,497,500个。个。 密钥建立问题：密钥建立问题：对协商密钥的信道的安全性的对协商密钥的信道的安全性的 要求比正常的传送消息的信道的安全性要高。要求比正常的传送消息的信道的安全性要高。 数字签名的问题：数字签名的问题：传统加密算法无法实现抗抵传统加密算法无法实现抗抵 赖的需求。赖的需求。 公钥密码体制的起源公钥密码体制的起源 q公钥密码又称为双钥密码和非对称密码，是公钥密码又称为双钥密码和非对称密码，是 19761976年由年由DiffieDiffie和和HellmanHellman在其在其“密码学新方向密码学新方向” 一文中提出的，文献：一文

36、中提出的，文献：W.Diffie and W.Diffie and M.E.Hellman, New Directrions in Cryptography, M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-IEEE Transaction on Information Theory, V.IT- 22.No.6, Nov 1976,PP.644-65422.No.6, Nov 1976,PP.644-654 qRSARSA公钥算法是由公钥算法是由Rivest,

37、ShamirRivest,Shamir和和AdlemanAdleman在在 19781978年提出来的年提出来的, , 见见Communitions of the ACM. Communitions of the ACM. Vol.21.No.2. Feb.1978, PP.120-126Vol.21.No.2. Feb.1978, PP.120-126 公钥密码体制加密框图 公钥密码体制认证框图 部分数学基础部分数学基础 n乘法逆元乘法逆元 n费尔玛（费尔玛（Fermat）定理）定理 n欧拉函数欧拉函数 n欧拉定理欧拉定理 通过三个方面研究：通过三个方面研究： RSA算法描述算法描述 RSA

38、实现中的问题实现中的问题 RSA的应用的应用 RSARSA算法算法 RSA算法算法 1977年由年由Ron Rivest、Adi Shamir和和Len Adleman发明，发明，1978年年 公布是一种分组加密算法，明文和密文公布是一种分组加密算法，明文和密文 在在0-（n-1）之间，）之间，n是一个正整数；应是一个正整数；应 用最广泛的公钥密码算法只在美国申请用最广泛的公钥密码算法只在美国申请 专利，且已于专利，且已于2000年年9月到期。月到期。 n RSA RSA体制的体制的安全性基于安全性基于数论中的数论中的EulerEuler定定 理和计算复杂性理论中的下述论断：理和计算复杂性理论

39、中的下述论断：求求 两个大素数的乘积是很容易计算的，但两个大素数的乘积是很容易计算的，但 要分解两个大素数的乘积，求出它们的要分解两个大素数的乘积，求出它们的 素因子则是非常困难的素因子则是非常困难的。 RSARSA算法描述算法描述 1 1、密钥生成、密钥生成 （1 1）随机选取两个大素数）随机选取两个大素数p p 、q q，令，令n=pqn=pq，随，随 机选取两个整数机选取两个整数e e和和d d。使得。使得e,de,d与与 (n)(n)互素，互素， 且且 （2 2）公开）公开n,en,e，作为，作为E E，记为，记为E=(e,n)E=(e,n) （3 3）保密）保密p,q,dp,q,d与

40、与 (n)(n)，作为，作为D D，记为，记为D=(d,n)D=(d,n) )(mod1ned 2 2、加密过程、加密过程 （1 1）在公开密钥数据库中，查得用户）在公开密钥数据库中，查得用户U U的公的公 钥：钥：E(n,e)； （2 2）将明文分组）将明文分组 ，使得每个，使得每个 n,i=1,2rn,i=1,2r （3 3）对每一组明文作加密变换）对每一组明文作加密变换 （4) 4)将密文将密文 传送给用户传送给用户U U。 rx xxxx 2 i x r yyyy 21 nxxEy e iii mod)( 3 3、解密过程解密过程 （1 1）先对每一组明文做解密变换：）先对每一组明文做

41、解密变换： （2 2）合并分组得到明文）合并分组得到明文 nyyDx d iii mod)( 思考：思考：RSA算法中如何体现安全性？算法中如何体现安全性？ 证明解密过程的正确性：证明解密过程的正确性： i x )(mod1ned 存在某个整数存在某个整数k，使得，使得 设设 与与n互素，即互素，即 nyyD d ii mod)( nx ed i mod nx nk i mod 1)( nxx nk ii mod )( i x 1),gcd(nxi 1)(nked 讨论讨论RSA算法的安全性：算法的安全性： 在算法中，在算法中，e和和n作为公开密钥，任何人都作为公开密钥，任何人都 可以用来加密

42、消息；而可以用来加密消息；而p、q、d和和 是保密是保密 的，用来解密密文，只有私钥拥有者知道，也的，用来解密密文，只有私钥拥有者知道，也 就是只有接收者知道。就是只有接收者知道。 由于由于n为两个大素数的乘积，又为两个大素数的乘积，又n=pq，那么，那么 可以得到可以得到(n)=(p-1)(q-1)。发信者并不知道。发信者并不知道n的的 两个素因子两个素因子p和和q，就无法计算，就无法计算(n)。 又由于又由于ed1 moded1 mod(n)(n)，d d是通过此式计算是通过此式计算 出来的，因此出来的，因此无法计算无法计算d，所以就无法进行解密。，所以就无法进行解密。 这样，只有秘密钥拥

43、有者才可以进行密文这样，只有秘密钥拥有者才可以进行密文 的解密，其他任何人都不能。的解密，其他任何人都不能。 )(n 因式分解的计算量因式分解的计算量 RSARSA参数的选择参数的选择 RSARSA系统是一个将安全性植于因子分解的系统。很系统是一个将安全性植于因子分解的系统。很 明显地，在公开密钥（明显地，在公开密钥（e e，n n）中，若）中，若n n能被因子分解，能被因子分解， 则在模则在模n n中，中，(n)=(p-1)(q-1)(n)=(p-1)(q-1)就无从隐藏，使得解密密钥就无从隐藏，使得解密密钥d d 不再是秘密，进而整个系统不安全。不再是秘密，进而整个系统不安全。 因此，在使

44、用因此，在使用RSARSA系统时，对于公开密钥系统时，对于公开密钥n n的选择非常的选择非常 重要。必须使得重要。必须使得n n公开后，任何人无法从公开后，任何人无法从n n得到得到d d。此外，。此外， 对于公钥对于公钥e e与解密密钥与解密密钥d d，也需要有所限制。否则在使用，也需要有所限制。否则在使用 上可能会导致系统被破解上可能会导致系统被破解. . 1、设设p=43，q=59，取，取e=13。 求公钥和私钥分别是多少？求公钥和私钥分别是多少？ RSA算法举例：算法举例： 解：解：p=43,q=59,n=pq=43p=43,q=59,n=pq=4359=2539 59=2539 (n)=42(n)=4258=2436,58=2436, 取