1、信息保密技术信息保密技术密码学中常见的两种体制:u对称密码体制(单钥密码体制) u 如果一个加密系统的加密密钥和解密密钥相同，或者虽然不相同，但是由其中的任意一个可以很容易地推导出另一个，即密钥是双方共享的,则该系统所采用的就是对称密码体制。 u非对称密码体制(公钥密码体制) u 在公钥体制中，加密密钥不同于解密密钥。将加密密钥公之于众，谁都可以使用；而解密密钥只有解密人自己知道。 一、对称加密算法DESn美国数据加密标准美国数据加密标准DES（Data Encryption Standard）美国制定数据加密标准简况美国制定数据加密标准简况n目的目的 通信与计算机相结合是人类步入信息社会的一
2、个阶梯，通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，完成于它始于六十年代末，完成于90年代初。计算机通信网的形年代初。计算机通信网的形成与发展，要求信息作业标准化，安全保密亦不例外。成与发展，要求信息作业标准化，安全保密亦不例外。只只有标准化，才能真正实现网络的安全，才能推广使用加密有标准化，才能真正实现网络的安全，才能推广使用加密手段，以便于训练、生产和降低成本。手段，以便于训练、生产和降低成本。 背景背景发明人发明人：美国：美国IBM公司公司 W. Tuchman 和和 C. Meyer 1971-1972年研制成功年研制成功基础：基础：1967年美国年美国Horst
3、 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年，美国银行协会批准使用年，美国银行协会批准使用DES1980年，年，DES成为美国标准化协会成为美国标准化协会(ANSI)标准标准1984年年2月，月，ISO成立的数据加密技术委员会成立的数据加密技术委员会(SC20)在在DES基础上基础上制定数据加密的国际
5、标准工作制定数据加密的国际标准工作 DES首次被批准使用五年，并规定每隔五年由美国国首次被批准使用五年，并规定每隔五年由美国国家保密局作出评估，并重新批准它是否继续作为联邦加密家保密局作出评估，并重新批准它是否继续作为联邦加密标准。最近的一次评估是在标准。最近的一次评估是在1994年年1月，美国已决定月，美国已决定1998年年12月以后将不再使用月以后将不再使用DES。因为按照现有的技术水平，采。因为按照现有的技术水平，采用不到几十万美元的设备，就可破开用不到几十万美元的设备，就可破开DES密码体制。目前密码体制。目前的新标准是的新标准是AES，它是由比利时的密码学家，它是由比利时的密码学家J
6、oan Daemen和和Vincent Rijmen设计的分组密码设计的分组密码Rijndael（荣代尔）。（荣代尔）。美国制定数据加密标准简况美国制定数据加密标准简况n1997年年DESCHALL小组经过近小组经过近4个月的努力，通过个月的努力，通过Internet搜索了搜索了31016个密钥，找出了个密钥，找出了DES的密钥，恢的密钥，恢复出了明文。复出了明文。n1998年年5月美国月美国EFF(electronics frontier foundation)宣布，他们以一台价值宣布，他们以一台价值20万美元的计算机改装成的专用解万美元的计算机改装成的专用解密机，用密机，用56小时破译了小
7、时破译了56 比特密钥的比特密钥的DES。美国制定数据加密标准简况美国制定数据加密标准简况n尽管如此，尽管如此，DES对于推动密码理论的发展和应用毕竟起了对于推动密码理论的发展和应用毕竟起了重大作用，对于掌握分组密码的基本理论、设计思想和实重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值。际应用仍然有着重要的参考价值。DES 算法算法n分组长度为分组长度为64 bits (8 bytes)n密文分组长度也是密文分组长度也是64 bits。n密钥长度为密钥长度为64 bits，有，有8 bits奇偶校验，有效密钥长奇偶校验，有效密钥长度为度为56 bits。n算法主
8、要包括：初始置换算法主要包括：初始置换IP、16轮迭代的乘积变换、轮迭代的乘积变换、逆初始置换逆初始置换IP-1以及以及16个子密钥产生器。个子密钥产生器。 DES加密算法框图子密钥产生器子密钥产生器16轮迭代轮迭代的乘积变换的乘积变换DES算法框图算法框图 输入 64 bit明文数据 初始置换IP 乘积变换 （16轮迭代） 逆初始置换IP-1 64 bit密文数据 输出 标准数据加密算法58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135
9、63554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725（a）初始置换）初始置换IP(b)逆初始置换逆初始置换IP -1初始置换初始置换IPIPn将将64 bit明文的位置进行置换，得到一个乱明文的位置进行置换，得到一个乱序的序的64 bit明文组，而后分成左右两段，每明文组，而后分成左右两段，每段为段为32 bit，以，以L0和和R0表示，表示，IP中各列元素中各列元素位置号数相差为
10、位置号数相差为8。n逆初始置换逆初始置换IPIP-1 -1 将将16轮迭代后给出的轮迭代后给出的64 bit组进行置换，得到输出的密文组。输出为组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。阵中元素按行读得的结果。nIP和和IPIP-1-1在密码意义上作用不大，它们的作在密码意义上作用不大，它们的作用在于打乱原来输入用在于打乱原来输入x x的的ASCII码字划分的码字划分的关系。关系。DES加密算法的轮结构加密算法的轮结构密钥流生成器密钥流生成器乘积变换乘积变换n它是它是DES算法的核心部分。将经过算法的核心部分。将经过IP置换后的数据分成置换后的数据分成32 bit的左右两组，
11、在迭代过程中彼此左右交换位置。的左右两组，在迭代过程中彼此左右交换位置。n每次迭代时只对右边的每次迭代时只对右边的32 bit进行一系列的加密变换，在此进行一系列的加密变换，在此轮迭代即将结束时，把左边的轮迭代即将结束时，把左边的32 bit与右边得到的与右边得到的32 bit逐位逐位模模2相加，作为下一轮迭代时右边的段，并将原来右边未经相加，作为下一轮迭代时右边的段，并将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段。的段。n在每一轮迭代时，右边的段要经过在每一轮迭代时，右边的段要经过选择扩展运算选择扩展运算E E、密钥加
12、、密钥加密运算、选择压缩运算密运算、选择压缩运算S S、置换运算、置换运算P P和左右混合运算和左右混合运算。选择扩展运算选择扩展运算E E 将输入的将输入的32 bit Ri-1扩展扩展成成48 bit的输出，令的输出，令s表示表示E原输入数据比特的原下标，原输入数据比特的原下标，则则E的输出是将原下标的输出是将原下标s 0或或1(mod 4)的各比特重复的各比特重复一次得到的，即对原第一次得到的，即对原第1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29，32各位都重各位都重复一次复一次,实现数据扩展。将实现数据扩展。将表中数据按行读
13、出得到表中数据按行读出得到48 bit输出。输出。(表表c)3212345456789891011121312131415161716171819202120212223242524252627282928293031321密钥加密运算密钥加密运算 将子密钥产生器输出的将子密钥产生器输出的48 bit子子密钥密钥ki与选择扩展运算与选择扩展运算E输出的输出的48 bits数据按位模数据按位模2相加。相加。 选择压缩运算选择压缩运算S。将前面送来的将前面送来的48 bit数据自左至右分成数据自左至右分成8组，每组为组，每组为6 bit。而后并行送入。而后并行送入8个个S盒，每个盒，每个S盒为一盒
14、为一非线性代换网络，有非线性代换网络，有4个输出，运算个输出，运算S的框图如下。的框图如下。48 bit 寄存器32 bit 寄存器S1S2S3S4S5S6S7S8DES的的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 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
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-1逐位模逐位模2相加，所得到的相加，所得到的32 bit作作为下一轮迭代用的右边的数字段为下一轮迭代用的右边的数字段Ri 。并将。并将Ri-1并行送到左边并行送到左边的寄存器，作为下一轮迭代用的左边的数字段的寄存器，作为下一轮迭代用的左边的数字段Li
16、 。（表。（表d） 1672021291228171152326518311028241432273919133062211425函数F(R,K)计算过程R (32比特)K (48比特)48比特E+P32比特1S2S3S4S5S6S7S8S子密钥产生器子密钥产生器n将将64 bit初始初始密钥经过：密钥经过：置换选择置换选择PC-PC-1 1循环移位循环移位置换选择置换选择PC-PC-2 2n给出每次迭给出每次迭代加密用的子密代加密用的子密钥钥ki，置换选择164比特子密钥产生器框图子密钥产生器框图 密钥（64 bit ）置换选择1，PC1置换选择2，PC2 Ci(28 bit) Di(28
17、bit) 循环左移ti+1bit 循环左移ti+1bit除去第8,16, ,64位(8个校验位)ki574941332517915850423426181025951433527191136050443663554739312315762544638302214661534537292113528201241417112415328156211023191242681672720132415231374755304051453348444939563453464250362932置换选择置换选择2（PC-2）置换选择置换选择1（PC-1）迭代次数12345678循环左移位数11222222迭代
18、次数910111213141516循环左移位数12222221左循环移位位数左循环移位位数 DES的安全性安全性n穷举攻击分析穷举攻击分析 穷举攻击就是对所有可能的密钥逐个进穷举攻击就是对所有可能的密钥逐个进行脱密测试，直到找到正确密钥为止的一种行脱密测试，直到找到正确密钥为止的一种攻击方法。攻击方法。 穷举攻击判断正确密钥的方法：穷举攻击判断正确密钥的方法： 将利用试验密钥解密得到的可能明文与将利用试验密钥解密得到的可能明文与已掌握的明文的信息相比较，并将最吻合的已掌握的明文的信息相比较，并将最吻合的那个试验密钥作为算法输出的正确密钥。那个试验密钥作为算法输出的正确密钥。 穷举攻击又称为穷尽
19、攻击、强力攻击、穷举攻击又称为穷尽攻击、强力攻击、蛮干攻击等。只要明文不是随机的，就蛮干攻击等。只要明文不是随机的，就可实施穷举攻击。可实施穷举攻击。二重二重DESn明文为明文为P，两个加密密钥，两个加密密钥k1和和k2，密文，密文为：为：C=Ek2Ek1Pn解密时，解密时，P=Dk1Dk2CXEEDDPCPXC k1 k1k2k2讨论：使用二重讨论：使用二重DES产生的映射是否等价于单产生的映射是否等价于单重重DES加密加密?二重二重DES 用用DES进行两次加密，但这是否就意味着进行两次加密，但这是否就意味着两重两重DES加密的强度等价于加密的强度等价于112 bit密钥的密密钥的密码的强
20、度？答案是否定的。码的强度？答案是否定的。 三重三重DES加密加密加密：加密：y=Ek1Dk2Ek1 x解密：解密：x=Dk1Ek2Dk1yn称其为加密称其为加密-解密解密-加密方案，简记为加密方案，简记为EDE(encrypt-decrypt-encrypt)。n此方案已在此方案已在ANSI X9.17和和ISO 8732标准中采用，并标准中采用，并在保密增强邮递在保密增强邮递(PEM)系统中得到利用。系统中得到利用。n破译它的穷举密钥搜索量为破译它的穷举密钥搜索量为2112 51035量级，而量级，而用差分分析破译也要超过用差分分析破译也要超过1052量级。此方案仍有足量级。此方案仍有足够
21、的安全性。够的安全性。 分组密码的运行模式分组密码在加密时，明文分组的长度固定。分组密码在加密时，明文分组的长度固定。实际应用中待加密消息的数据长度和格式各实际应用中待加密消息的数据长度和格式各有不同。有不同。为了能在各种应用场合使用为了能在各种应用场合使用DES，定义了，定义了DES的的4种运行模式，这些模式也可用于其他种运行模式，这些模式也可用于其他分组密码。分组密码。1 电码本（电码本（ECB）模式）模式消息分为长为消息分为长为64比特的分组，最后一个分组如果不比特的分组，最后一个分组如果不够够64比特，则需要比特，则需要填充填充。明文是由分组长为明文是由分组长为64比特的分组序列比特的
22、分组序列P1，P2，PN构成，相应的密文分组序列是构成，相应的密文分组序列是C1，C2，CN。 ECB的的最大特性最大特性是同一明文分组在消息中重复出现是同一明文分组在消息中重复出现的话，产生的密文分组也相同。的话，产生的密文分组也相同。ECB用于长消息时可能不够安全，如果消息有固定用于长消息时可能不够安全，如果消息有固定结构，密码分析者有可能找出这种关系。结构，密码分析者有可能找出这种关系。ECB在用于在用于短数据短数据（如加密密钥）时非常理想，因（如加密密钥）时非常理想，因此如果需要安全地传递此如果需要安全地传递DES密钥，密钥，ECB是最合适的模是最合适的模式。式。2 密码分组链接（密码
23、分组链接（CBC）模式）模式11111KnnKKnnnnnnnDCCDECPCCPCP1nKnnCECP解密时：每一个密文分解密时：每一个密文分组被解密后，再与前一组被解密后，再与前一个密文分组异或得明文个密文分组异或得明文解决解决ECB的安全缺陷的安全缺陷：可以让重复的明文分组可以让重复的明文分组产生不同的密文分组产生不同的密文分组加密时：输入是当前加密时：输入是当前明文分组和前一次密明文分组和前一次密文分组的异或文分组的异或初始向量初始向量IVIV应像密钥一样被保护，可使用应像密钥一样被保护，可使用ECB加密模式来发加密模式来发送送IV。保护保护IV的原因：如果敌手篡改的原因：如果敌手篡改
24、IV中的某些比特，则中的某些比特，则接收方收到的接收方收到的P1中相应的比特也发生了变化。中相应的比特也发生了变化。1111KKCEIVPPIVDC第一次加、解密需第一次加、解密需IV由于由于CBC 模式的链接机制，模式的链接机制，CBC模式对模式对加密长消息加密长消息非常合适。非常合适。CBC模式除能够获得保密性外，还能用于认证。模式除能够获得保密性外，还能用于认证。3 密码反馈（密码反馈（CFB）模式）模式加密算法的输入是加密算法的输入是64比特比特移位寄存器，其初值为某个移位寄存器，其初值为某个初始向量初始向量IV。加密算法输出的最左（最高加密算法输出的最左（最高有效位）有效位）j比特与
25、明文的第一比特与明文的第一个单元个单元P1进行异或，产生出进行异或，产生出密文的第密文的第1个单元个单元C1，并传送，并传送该单元。该单元。然后将移位寄存器的内容左然后将移位寄存器的内容左移移j位并将位并将C1送入移位寄存器送入移位寄存器最右边（最低有效位）最右边（最低有效位）j位。位。这一过程继续到明文的所有这一过程继续到明文的所有单元都被加密为止。单元都被加密为止。设设Sj(X)是是X的的j个最高有限个最高有限位，那么：位，那么：11jCPSE IV11jPCSE IV加密加密解密解密CFB特点特点nDES是分组长为是分组长为64比特的分组密码，但利比特的分组密码，但利用用CFB模式或模式
26、或OFB模式可将模式可将DES转换为流转换为流密码。密码。如果需要发送如果需要发送字符流字符流，每个字符长为，每个字符长为8比特比特,就应使用就应使用8比特密钥来加密每个字符比特密钥来加密每个字符.通常取通常取j=8流密码不需要对消息填充，而且运行是实时流密码不需要对消息填充，而且运行是实时的的图3.13 OFB模式示意图4 输出反馈输出反馈(OFB)模式模式OFB（output feedback）模式的结构类似于）模式的结构类似于CFB。不同之处不同之处OFB模式是将加密算法的输出反馈到移位寄存器，模式是将加密算法的输出反馈到移位寄存器，CFB模式中是将密文单元反馈到移位寄存器。模式中是将密
27、文单元反馈到移位寄存器。OFB优点：传输过程中的比特错误不会被传播。优点：传输过程中的比特错误不会被传播。OFB 中，中，C1中出现中出现1比特错误，在解密结果中只有比特错误，在解密结果中只有P1受到影响，以受到影响，以后各明文单元则不受影响。后各明文单元则不受影响。CFB中，中，C1也作为移位寄存器的输入，因此它的也作为移位寄存器的输入，因此它的1比特错误会影响比特错误会影响解密结果中各明文单元的值。解密结果中各明文单元的值。OFB的缺点：比的缺点：比CFB模式更易受到对消息流的篡改攻击。模式更易受到对消息流的篡改攻击。比较和选用比较和选用nECB模式，简单、高速，但最易受重发攻击。模式，简
28、单、高速，但最易受重发攻击。nCBC适用于文件加密，但较适用于文件加密，但较ECB慢。慢。nOFB和和CFB较较CBC慢许多。每次迭代只有少数慢许多。每次迭代只有少数bit完成加密。完成加密。nOFB用于高速同步系统，传输过程中的比特错误用于高速同步系统，传输过程中的比特错误不会被传播不会被传播.nCFB多用在字符为单元的流密码中多用在字符为单元的流密码中,有错误扩展有错误扩展分组密码的分析方法n解密与密码分析解密与密码分析u 解密是加密的逆过程，是指掌握密钥解密是加密的逆过程，是指掌握密钥和密码算法的合法人员从密文恢复出和密码算法的合法人员从密文恢复出明文的过程。明文的过程。u密码分析则是指
29、非法人员对密码的破密码分析则是指非法人员对密码的破译，而且破译以后不会告诉对方。译，而且破译以后不会告诉对方。分组密码的分析方法n根据攻击者掌握的信息，可将分组密码的攻击分为以下几类：u唯密文攻击：攻击者除了所截获的密文外，没有其他可利用的信息。u已知明文攻击： 攻击者仅知道当前密钥下的一些明密文对。u选择明文攻击：攻击者能获得当前密钥下的一些特定的明文所对应的密文。u选择密文攻击：攻击者能获得当前密钥下的一些特定的密文所对应的明文。分组密码的分析方法(续）u一种攻击的复杂度可以分为两部分：数据复杂度和处理复杂度。p数据复杂度是实施该攻击所需输入的数据量。p处理复杂度是处理这些数据所需的计算量
30、。 u对某一攻击通常是以这两个方面的某一方面为主要因素，来刻画攻击复杂度 。n 【例如】p穷举攻击的复杂度实际就是考虑处理复杂度；p差分密码分析其复杂度主要是由该攻击所需的明密文对的数量来确定。几种常见的攻击方法n1.强力攻击强力攻击n强力攻击可用于任何分组密码，且攻击的复杂度n只依赖于分组长度和密钥长度，严格地讲攻击所 n需的时间复杂度依赖于分组密码的工作效率（包n括加解密速度、密钥扩散速度以及存储空间等）。n强力攻击常见的有：穷举密钥搜索攻击穷举密钥搜索攻击、n字典攻击字典攻击、查表攻击和时间查表攻击和时间-存储权衡攻击存储权衡攻击等。几种常见的攻击方法（续）n2.差分密码分析差分密码分析
31、n基本思想基本思想n通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。n 若给定一个r轮的迭代密码，对已知n长明文对为 n 和 ，定义其差分为n 式中 表示集合中定义的群运算， 为 在群中的逆元。n密码分析者可随机选择具有固定差分的一对明文（只要求它们符合特定差分条件），然后使用输出密文中的差分，按照不同的概率分配给不同的密钥。随着分析的密文对越来越多，其中最可能的一个密钥就显现出来了。这就是正确的密钥。XX1XXX1XX几种常见的攻击方法（续）n3.线性密码分析线性密码分析u本质： 一种已知明文攻击方法。u基本思想 ：通过寻找一个给定密码算法的有效的n线性近似表达式来破译密码系统。
32、n对已知明文密文和特定密钥，寻求线性表示式n n式中， 是攻击参数。对所有可能密钥，此表n达式以概率 成立。对给定的密码算法，n使 极大化。为此对每一盒的输入和输n出构造统计线性路线，并最终扩展到整个算法。xdybxadba,2/1LP2/1LP二、公钥加密算法RSA二、公钥加密算法二、公钥加密算法RSARSA 公钥密码体制的基本原理公钥密码体制的基本原理公钥密码体制采用了两个不同的密钥，这公钥密码体制采用了两个不同的密钥，这对在公开的网络上进行对在公开的网络上进行保密通信保密通信、密钥密钥分配分配、数字签名和认证数字签名和认证有着深远的影响。有着深远的影响。 对称密码的不足对称密码的不足 密
33、钥管理量的困难：密钥管理量的困难：两两分别用一个密钥时，两两分别用一个密钥时，则则n n个用户需要个用户需要C(n,2)=n(n-1)/2C(n,2)=n(n-1)/2个密钥，当用户量个密钥，当用户量增大时，密钥空间急剧增大。如增大时，密钥空间急剧增大。如:n=100 :n=100 时，共时，共4,9954,995个；个；n=5000n=5000时增加到时增加到12,497,50012,497,500个。个。 密钥建立问题：密钥建立问题：对协商密钥的信道的安全性的对协商密钥的信道的安全性的要求比正常的传送消息的信道的安全性要高。要求比正常的传送消息的信道的安全性要高。 数字签名的问题：数字签名
34、的问题：传统加密算法无法实现抗抵传统加密算法无法实现抗抵赖的需求。赖的需求。 公钥密码体制的起源公钥密码体制的起源q公钥密码又称为双钥密码和非对称密码，是公钥密码又称为双钥密码和非对称密码，是19761976年由年由DiffieDiffie和和HellmanHellman在其在其“密码学新方向密码学新方向”一文中提出的，文献：一文中提出的，文献：W.Diffie and W.Diffie and M.E.Hellman, New DirectrionsM.E.Hellman, New Directrions in Cryptography, in Cryptography, IEEE Tran
35、saction 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-654qRSARSA公钥算法是由公钥算法是由Rivest,ShamirRivest,Shamir和和AdlemanAdleman在在19781978年提出来的年提出来的, , 见见CommunitionsCommunitions of the ACM. of the ACM. Vol.21.No.2. Feb.1978, PP.1
36、20-126Vol.21.No.2. Feb.1978, PP.120-126公钥密码体制加密框图公钥密码体制认证框图部分数学基础部分数学基础n乘法逆元乘法逆元n费尔玛（费尔玛（Fermat）定理）定理n欧拉函数欧拉函数n欧拉定理欧拉定理通过三个方面研究：通过三个方面研究： RSA算法描述算法描述 RSA实现中的问题实现中的问题 RSA的应用的应用RSARSA算法算法RSA算法算法 1977年由年由Ron Rivest、Adi Shamir和和Len Adleman发明，发明，1978年年公布是一种分组加密算法，明文和密文公布是一种分组加密算法，明文和密文在在0-（n-1）之间，）之间，n是一
37、个正整数；应是一个正整数；应用最广泛的公钥密码算法只在美国申请用最广泛的公钥密码算法只在美国申请专利，且已于专利，且已于2000年年9月到期。月到期。n RSA RSA体制的体制的安全性基于安全性基于数论中的数论中的EulerEuler定定理和计算复杂性理论中的下述论断：理和计算复杂性理论中的下述论断：求求两个大素数的乘积是很容易计算的，但两个大素数的乘积是很容易计算的，但要分解两个大素数的乘积，求出它们的要分解两个大素数的乘积，求出它们的素因子则是非常困难的素因子则是非常困难的。RSARSA算法描述算法描述 1 1、密钥生成、密钥生成（1 1）随机选取两个大素数）随机选取两个大素数p p 、
38、q q，令，令n=pqn=pq，随，随机选取两个整数机选取两个整数e e和和d d。使得。使得e,de,d与与 (n)(n)互素，互素，且且（2 2）公开）公开n,en,e，作为，作为E E，记为，记为E=(e,nE=(e,n) )（3 3）保密）保密p,q,dp,q,d与与 (n)(n)，作为，作为D D，记为，记为D=(d,nD=(d,n) )(mod1ned2 2、加密过程、加密过程（1 1）在公开密钥数据库中，查得用户）在公开密钥数据库中，查得用户U U的公的公钥：钥：E(n,e)；（2 2）将明文分组）将明文分组 ，使得每个，使得每个 n,in,i=1,2=1,2r r（3 3）对每
39、一组明文作加密变换）对每一组明文作加密变换 （4) 4)将密文将密文 传送给用户传送给用户U U。rxxxxx2ixryyyy21nxxEyeiiimod)( 3 3、解密过程解密过程（1 1）先对每一组明文做解密变换：）先对每一组明文做解密变换： （2 2）合并分组得到明文）合并分组得到明文 nyyDxdiiimod)(思考：思考：RSA算法中如何体现安全性？算法中如何体现安全性？证明解密过程的正确性：证明解密过程的正确性：ix)(mod1ned 存在某个整数存在某个整数k，使得，使得设设 与与n互素，即互素，即nyyDdiimod)(nxedimodnxnkimod1)(nxxnkiimo
40、d)(ix1),gcd(nxi1)(nked讨论讨论RSA算法的安全性：算法的安全性： 在算法中，在算法中，e和和n作为公开密钥，任何人都作为公开密钥，任何人都可以用来加密消息；而可以用来加密消息；而p、q、d和和 是保密是保密的，用来解密密文，只有私钥拥有者知道，也的，用来解密密文，只有私钥拥有者知道，也就是只有接收者知道。就是只有接收者知道。 由于由于n为两个大素数的乘积，又为两个大素数的乘积，又n=pq，那么，那么可以得到可以得到(n)=(p-1)(q-1)。发信者并不知道。发信者并不知道n的的两个素因子两个素因子p和和q，就无法计算，就无法计算(n)。 又由于又由于ed1 moded1
41、 mod(n)(n)，d d是通过此式计算是通过此式计算出来的，因此出来的，因此无法计算无法计算d，所以就无法进行解密。，所以就无法进行解密。 这样，只有秘密钥拥有者才可以进行密文这样，只有秘密钥拥有者才可以进行密文的解密，其他任何人都不能。的解密，其他任何人都不能。)(n因式分解的计算量因式分解的计算量RSARSA参数的选择参数的选择 RSARSA系统是一个将安全性植于因子分解的系统。很系统是一个将安全性植于因子分解的系统。很明显地，在公开密钥（明显地，在公开密钥（e e，n n）中，若）中，若n n能被因子分解，能被因子分解，则在模则在模n n中，中， (n)=(p-1)(q-1)(n)=
42、(p-1)(q-1)就无从隐藏，使得解密密钥就无从隐藏，使得解密密钥d d不再是秘密，进而整个系统不安全。不再是秘密，进而整个系统不安全。 因此，在使用因此，在使用RSARSA系统时，对于公开密钥系统时，对于公开密钥n n的选择非常的选择非常重要。必须使得重要。必须使得n n公开后，任何人无法从公开后，任何人无法从n n得到得到d d。此外，。此外，对于公钥对于公钥e e与解密密钥与解密密钥d d，也需要有所限制。否则在使用，也需要有所限制。否则在使用上可能会导致系统被破解上可能会导致系统被破解. .1、设设p=43，q=59，取，取e=13。 求公钥和私钥分别是多少？求公钥和私钥分别是多少？
43、RSA算法举例：算法举例：解：解：p=43,q=59,n=pqp=43,q=59,n=pq=43=4359=2539 59=2539 (n)=42(n)=4258=2436,58=2436, 取取e=13,e=13,解方程解方程d de1(mod2436) e1(mod2436) 2436=13 2436=13187+5,13=2187+5,13=25+3,5=3+2,3=2+15+3,5=3+2,3=2+1 1=3-2,2=5-3,3=13-2 1=3-2,2=5-3,3=13-25,5=2436-135,5=2436-13187187 1=3-2=3-(5-3)=2 1=3-2=3-(5-
44、3)=23-5=2(13-23-5=2(13-25)-5=25)-5=213-513-55 5 =2 =213-5(2436-1313-5(2436-13187)187) =937 =93713-513-524362436 即：即：937937131131（mod2436mod2436） 取取 e=13,d=937e=13,d=937 公钥公钥e,ne,n=13,2539,=13,2539,私钥私钥d,nd,n=937,2539=937,2539RSA算法举例算法举例：2、设设p=7，q=17，取，取e=5 求公钥和私钥分别是多少？求公钥和私钥分别是多少？ 设明文设明文m=19，加密的密文是多少？ 并进行解密验证？RSA算法举例：算法举例：RSA系统的应用系统的应用1、数据加密：数据加密：设设B欲秘密传递明文欲秘密传递明文m给给A，则，则B首先由公开档案找到首先由公开档案找到A的公开密钥的公开密钥 接着执行加密：接着执行加密： 将密文将密文c传送给传送给A。A收到后，利用私钥收到后，利用私钥 执行解密操作：执行解密操作： AdAenmcmEAmod)(AdncmcDAmod)()(,AAne
