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

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