信息安全原理与技术第2章密码学基础课件

本章主要内容本章主要内容 密码学基本概念密码学基本概念密码学基本概念密码学基本概念 对称密码体制对称密码体制对称密码体制对称密码体制 公钥密码体制公钥密码体制公钥密码体制公钥密码体制 散列函数散列函数散列函数散列函数 数字签名数字签名数字签名数字签名 信息隐藏与数字水印信息隐藏与数字水印信息隐藏与数字水印信息隐藏与数字水印 6/17/20241信息安全原理与技术本章主要内容8/9/20231信息安全原理与技术2.1 概概 述述经典密码：经典密码：经典密码：经典密码：古埃及人用以保密传递的消息；古埃及人用以保密传递的消息；古埃及人用以保密传递的消息；古埃及人用以保密传递的消息；单表置换密码，凯撒密码，单表置换密码，凯撒密码，单表置换密码，凯撒密码，单表置换密码，凯撒密码，多表置换密码，多表置换密码，多表置换密码，多表置换密码，VigenereVigenere密码等等密码等等密码等等密码等等近代密码：近代密码：近代密码：近代密码：DESDES数据加密标准，数据加密标准，数据加密标准，数据加密标准，7070年代年代年代年代Diffie,HellmanDiffie,Hellman 的开创性工作的开创性工作的开创性工作的开创性工作公钥体制的提出公钥体制的提出公钥体制的提出公钥体制的提出密码应用：密码应用：密码应用：密码应用：电子数据，军事目的，经济目的。电子数据，军事目的，经济目的。电子数据，军事目的，经济目的。电子数据，军事目的，经济目的。应用形式：应用形式：应用形式：应用形式：数据的保密性、真实性、完整性。数据的保密性、真实性、完整性。数据的保密性、真实性、完整性。数据的保密性、真实性、完整性。主要内容：主要内容：主要内容：主要内容：数据加密，密码分析，数字签名，信息数据加密，密码分析，数字签名，信息数据加密，密码分析，数字签名，信息数据加密，密码分析，数字签名，信息 鉴别，零泄密认证，秘密共享等等。鉴别，零泄密认证，秘密共享等等。鉴别，零泄密认证，秘密共享等等。鉴别，零泄密认证，秘密共享等等。信息攻击：信息攻击：信息攻击：信息攻击：主动攻击主动攻击主动攻击主动攻击对数据的恶意删除、篡改等对数据的恶意删除、篡改等对数据的恶意删除、篡改等对数据的恶意删除、篡改等 被动攻击被动攻击被动攻击被动攻击从信道上截取、偷窃、拷贝从信道上截取、偷窃、拷贝从信道上截取、偷窃、拷贝从信道上截取、偷窃、拷贝 信息。信息。信息。信息。无意攻击无意攻击无意攻击无意攻击错误操作、机器故障等。错误操作、机器故障等。错误操作、机器故障等。错误操作、机器故障等。6/17/20242信息安全原理与技术2.1 概 述经典密码：古埃及人用以保密传递的消息；2.2 密码学基本概念密码学基本概念现代密码系统的组成现代密码系统的组成现代密码系统的组成现代密码系统的组成 现代密码系统现代密码系统现代密码系统现代密码系统(通常简称为密码体制通常简称为密码体制通常简称为密码体制通常简称为密码体制)一般由五一般由五一般由五一般由五个部分组成：个部分组成：个部分组成：个部分组成：明文空间明文空间明文空间明文空间MM 密文空间密文空间密文空间密文空间C C 密钥空间密钥空间密钥空间密钥空间K K 加密算法加密算法加密算法加密算法E E 解密算法解密算法解密算法解密算法D D 则五元组（则五元组（则五元组（则五元组（MM，C C，KK，E E，D D）称为一个密码体制。）称为一个密码体制。）称为一个密码体制。）称为一个密码体制。6/17/20243信息安全原理与技术2.2 密码学基本概念现代密码系统的组成 现密码体制密码体制密码体制密码体制 对称密钥体制对称密钥体制对称密钥体制对称密钥体制 非对称密钥体制非对称密钥体制非对称密钥体制非对称密钥体制 6/17/20244信息安全原理与技术密码体制8/9/20234信息安全原理与技术 根据密码算法对明文信息的加密方式，根据密码算法对明文信息的加密方式，根据密码算法对明文信息的加密方式，根据密码算法对明文信息的加密方式，对称密码体制常分为两类：对称密码体制常分为两类：对称密码体制常分为两类：对称密码体制常分为两类：分组密码分组密码分组密码分组密码(Block cipher(Block cipher，也叫块密码，也叫块密码，也叫块密码，也叫块密码)DES DES DES DES、IDEA IDEA IDEA IDEA、BLOWFISH BLOWFISH BLOWFISH BLOWFISH 序列密码序列密码序列密码序列密码(Stream cipher(Stream cipher，也叫流密码，也叫流密码，也叫流密码，也叫流密码)。A5 A5、FISH FISH、PIKEPIKE 6/17/20245信息安全原理与技术 根据密码算法对明文信息的加密方式，对称密码体制常分为两密码分析学密码分析学穷举攻击：穷举攻击：又称作蛮力攻击，是指密码分析者用试遍所有又称作蛮力攻击，是指密码分析者用试遍所有又称作蛮力攻击，是指密码分析者用试遍所有又称作蛮力攻击，是指密码分析者用试遍所有密钥的方法来破译密码密钥的方法来破译密码密钥的方法来破译密码密钥的方法来破译密码对可能的密钥或明文的穷举对可能的密钥或明文的穷举对可能的密钥或明文的穷举对可能的密钥或明文的穷举统计分析攻击统计分析攻击：指密码分析者通过分析密文和明文的统指密码分析者通过分析密文和明文的统指密码分析者通过分析密文和明文的统指密码分析者通过分析密文和明文的统计规律来破译密码。计规律来破译密码。计规律来破译密码。计规律来破译密码。数学分析攻击：数学分析攻击：指密码分析者针对加密算法的数学依据，指密码分析者针对加密算法的数学依据，指密码分析者针对加密算法的数学依据，指密码分析者针对加密算法的数学依据，通过数学求解的方法来破译密码。通过数学求解的方法来破译密码。通过数学求解的方法来破译密码。通过数学求解的方法来破译密码。6/17/20246信息安全原理与技术密码分析学8/9/20236信息安全原理与技术1 1、唯密文攻击：、唯密文攻击：、唯密文攻击：、唯密文攻击：仅根据密文进行的密码攻击；仅根据密文进行的密码攻击；仅根据密文进行的密码攻击；仅根据密文进行的密码攻击；2 2、已知明文攻击：、已知明文攻击：、已知明文攻击：、已知明文攻击：根据一些相应的明、密文对进行的密码攻根据一些相应的明、密文对进行的密码攻根据一些相应的明、密文对进行的密码攻根据一些相应的明、密文对进行的密码攻击。击。击。击。3 3、选择明文攻击：、选择明文攻击：、选择明文攻击：、选择明文攻击：可以选择一些明文，并获取相应的密文，可以选择一些明文，并获取相应的密文，可以选择一些明文，并获取相应的密文，可以选择一些明文，并获取相应的密文，这是密码分析者最理想的情形。例如，在公钥体制中。这是密码分析者最理想的情形。例如，在公钥体制中。这是密码分析者最理想的情形。例如，在公钥体制中。这是密码分析者最理想的情形。例如，在公钥体制中。4 4、选择密文攻击：、选择密文攻击：、选择密文攻击：、选择密文攻击：密码分析者能选择不同的被加密的密文，密码分析者能选择不同的被加密的密文，密码分析者能选择不同的被加密的密文，密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，密码分析者的任务是推出密钥。并可得到对应的解密的明文，密码分析者的任务是推出密钥。并可得到对应的解密的明文，密码分析者的任务是推出密钥。并可得到对应的解密的明文，密码分析者的任务是推出密钥。5 5 5 5、选择密钥攻击、选择密钥攻击、选择密钥攻击、选择密钥攻击 ：这种攻击并不表示密码分析者能够选择这种攻击并不表示密码分析者能够选择这种攻击并不表示密码分析者能够选择这种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间关系的有关知密钥，它只表示密码分析者具有不同密钥之间关系的有关知密钥，它只表示密码分析者具有不同密钥之间关系的有关知密钥，它只表示密码分析者具有不同密钥之间关系的有关知识。识。识。识。6 6 6 6、软磨硬泡攻击、软磨硬泡攻击、软磨硬泡攻击、软磨硬泡攻击 ：密码分析者威胁、勒索，或者折磨某人，密码分析者威胁、勒索，或者折磨某人，密码分析者威胁、勒索，或者折磨某人，密码分析者威胁、勒索，或者折磨某人，直到他给出密钥为止。直到他给出密钥为止。直到他给出密钥为止。直到他给出密钥为止。根据密码分析者掌握明、根据密码分析者掌握明、根据密码分析者掌握明、根据密码分析者掌握明、密文的程度密码分析可分类为：密文的程度密码分析可分类为：密文的程度密码分析可分类为：密文的程度密码分析可分类为：6/17/20247信息安全原理与技术1、唯密文攻击：仅根据密文进行的密码攻击；根据密码分析者掌握密码算法的安全性：密码算法的安全性：密码算法的安全性：密码算法的安全性：理论上，除一文一密外，没有绝对安全理论上，除一文一密外，没有绝对安全理论上，除一文一密外，没有绝对安全理论上，除一文一密外，没有绝对安全的密码体制，通常，称一个密码体制是安全的的密码体制，通常，称一个密码体制是安全的的密码体制，通常，称一个密码体制是安全的的密码体制，通常，称一个密码体制是安全的是指是指是指是指计算上安全的计算上安全的计算上安全的计算上安全的，即：密码分析者为了破译，即：密码分析者为了破译，即：密码分析者为了破译，即：密码分析者为了破译密码，穷尽其时间、存储资源仍不可得，或破密码，穷尽其时间、存储资源仍不可得，或破密码，穷尽其时间、存储资源仍不可得，或破密码，穷尽其时间、存储资源仍不可得，或破译所耗资材已超出因破译而获得的获益。译所耗资材已超出因破译而获得的获益。译所耗资材已超出因破译而获得的获益。译所耗资材已超出因破译而获得的获益。6/17/20248信息安全原理与技术密码算法的安全性：8/9/20238信息安全原理与技术2.3 对称密码体制对称密码体制经典的密码体制中，加密密钥与解密密钥是相经典的密码体制中，加密密钥与解密密钥是相经典的密码体制中，加密密钥与解密密钥是相经典的密码体制中，加密密钥与解密密钥是相同的，或者可以简单相互推导，也就是说：知同的，或者可以简单相互推导，也就是说：知同的，或者可以简单相互推导，也就是说：知同的，或者可以简单相互推导，也就是说：知道了加密密钥，也就知道了解密密钥；知道了道了加密密钥，也就知道了解密密钥；知道了道了加密密钥，也就知道了解密密钥；知道了道了加密密钥，也就知道了解密密钥；知道了解密密钥，也就知道了加密密钥。所以，加、解密密钥，也就知道了加密密钥。所以，加、解密密钥，也就知道了加密密钥。所以，加、解密密钥，也就知道了加密密钥。所以，加、解密密钥必须同时保密。这种密码体制称为解密密钥必须同时保密。这种密码体制称为解密密钥必须同时保密。这种密码体制称为解密密钥必须同时保密。这种密码体制称为对对对对称（也称单钥）密码体制。称（也称单钥）密码体制。称（也称单钥）密码体制。称（也称单钥）密码体制。最典型的是最典型的是最典型的是最典型的是DESDES数数数数据加密标准，应该说数据加密标准据加密标准，应该说数据加密标准据加密标准，应该说数据加密标准据加密标准，应该说数据加密标准DESDES是单钥是单钥是单钥是单钥体制的最成功的例子。体制的最成功的例子。体制的最成功的例子。体制的最成功的例子。6/17/20249信息安全原理与技术2.3 对称密码体制经典的密码体制中，加密密钥与解密密钥是 1973.5.15：美国国家标准局（美国国家标准局（NSA）公开征）公开征求密码体制的联邦注册；求密码体制的联邦注册；1975.3.17：DES首次在联邦记事公开，它首次在联邦记事公开，它由由IBM开发，它是开发，它是LUCIFER的改进；的改进；1977.2.15：DES被采用作为非国家机关使用的被采用作为非国家机关使用的数据加密标准，此后，大约每五年对数据加密标准，此后，大约每五年对DES进行依进行依次审查，次审查，1992年是最后一次审查，美国政府已年是最后一次审查，美国政府已声明，声明，1998年后对年后对DES不再审查了；不再审查了；1977.2.15：联邦信息处理标准版联邦信息处理标准版46（FIPS PUB46）给出了）给出了DES的完整描述。的完整描述。6/17/202410信息安全原理与技术1973.5.15：美国国家标准局（NSA）公开征求密码体2.3.1 DES分组密码系统分组密码系统 DES密码体制：它是应用密码体制：它是应用56位密钥，加密位密钥，加密64比比特明文分组的分组秘钥密码体制特明文分组的分组秘钥密码体制 DES加密算法：加密算法：（一）初始置换：（一）初始置换：x0=L0R0=IP(x)；（二）（二）16次迭代：次迭代：xi-1=Li-1Ri-1，Li=Ri，Ri=Li f(Ri-1,ki)i=1,2,16；（三）逆置换：（三）逆置换：x16=L16R16，y=IP-1(x16)。密钥生成器：密钥密钥生成器：密钥ki是由是由56位系统密钥位系统密钥k生成的生成的32位子密钥。位子密钥。函数函数f及及S盒：盒：f(Ri-1,ki)=P(S(E(Ri-1)ki)6/17/202411信息安全原理与技术2.3.1 DES分组密码系统DES密码体制：它是应用 其中其中E，P是两个置换，是两个置换，表示比特的表示比特的“异或异或”，S是一组八个变换是一组八个变换S1，S2，S3，S8，称为，称为S盒，每个盒以盒，每个盒以6位输入，位输入，4位输出，位输出，S盒构成了盒构成了DES 安全的核心。安全的核心。DES算法流程图算法流程图6/17/202412信息安全原理与技术 其中E，P是两个置换，表示比特的“异或”，S是一组 函数函数f及及S盒的示意图盒的示意图DESDES解密：解密：解密：解密：DESDES的解密过程与加密过程相同，只不过的解密过程与加密过程相同，只不过的解密过程与加密过程相同，只不过的解密过程与加密过程相同，只不过子密钥的使用相反，即，首先使用子密钥的使用相反，即，首先使用子密钥的使用相反，即，首先使用子密钥的使用相反，即，首先使用k k1616，再使用，再使用，再使用，再使用k k1515，最后使用，最后使用，最后使用，最后使用k k1 1。6/17/202413信息安全原理与技术函数f及S盒的示意图DES解密：DES的解密过程与加密过程相2.3.2 关于关于DES的讨论的讨论 S盒是唯一非线性组件：有人认为其中可能含有盒是唯一非线性组件：有人认为其中可能含有某种某种“陷门陷门”，国家安全机关可以解密。，国家安全机关可以解密。DES的密钥量太小：密钥量为的密钥量太小：密钥量为256 1977年：年：Diffie.Hellman提出制造一个每秒测提出制造一个每秒测试试106的的VLSI芯片，则一天就可以搜索完整个密芯片，则一天就可以搜索完整个密钥空间，当时造价钥空间，当时造价2千万美圆。千万美圆。CRYPTO93：R.Session，M.Wiener提出并提出并行密钥搜索芯片，每秒测试行密钥搜索芯片，每秒测试5x107个密钥，个密钥，5760片这种芯片，造价片这种芯片，造价10万美圆，平均一天即万美圆，平均一天即可找到密钥。可找到密钥。6/17/202414信息安全原理与技术2.3.2 关于DES的讨论S盒是唯一非线性组件：有人 Internet的超级计算能力：的超级计算能力：1997年年1月月28日，美国日，美国RSA数据安全公司在数据安全公司在Internet上上开展了一项开展了一项“秘密密钥挑战秘密密钥挑战”的竞赛，悬赏一的竞赛，悬赏一万美圆，破解一段万美圆，破解一段DES密文。计划公布后，密文。计划公布后，得到了许多网络用户的强力相应。科罗拉州得到了许多网络用户的强力相应。科罗拉州的程序员的程序员R.Verser设计了一个可以通过互设计了一个可以通过互联网分段运行的密钥搜索程序，组织了一个联网分段运行的密钥搜索程序，组织了一个称为称为DESCHALL的搜索行动，成千上万的的搜索行动，成千上万的的志愿者加入到计划中。的志愿者加入到计划中。6/17/202415信息安全原理与技术Internet的超级计算能力：1997年1月28日，美国R第第96天，即竞赛公布后的第天，即竞赛公布后的第140天，天，1997年年6月月17日晚上日晚上10点点39分，美国盐湖城分，美国盐湖城Inetz公司公司职员职员M.Sanders成功地找到了密钥，解密出明成功地找到了密钥，解密出明文：文：The unknown Message is：“Stronge cryptography makes the word a safer place”(高强度密码技术使世界更安全高强度密码技术使世界更安全)。Internet仅仅利用闲散资源，毫无代价就破译仅仅利用闲散资源，毫无代价就破译了了DES密码，这是对密码方法的挑战，是密码，这是对密码方法的挑战，是Internet超级计算能力的显示超级计算能力的显示.6/17/202416信息安全原理与技术第96天，即竞赛公布后的第140天，1997年6月17日晚上差分分析法：除去穷举搜索密钥外，还有其他差分分析法：除去穷举搜索密钥外，还有其他形式的攻击方法，最著名的有形式的攻击方法，最著名的有Biham，Shamir的差分分析法。这是一个选择明文攻击的差分分析法。这是一个选择明文攻击方法。虽然对方法。虽然对16轮轮DES没有攻破，但是，如果没有攻破，但是，如果迭代的轮数降低，则它可成功地被攻破。例如，迭代的轮数降低，则它可成功地被攻破。例如，8轮轮DES在一个个人计算机上只需要在一个个人计算机上只需要2分钟即可分钟即可被攻破。被攻破。6/17/202417信息安全原理与技术差分分析法：除去穷举搜索密钥外，还有其他形式的攻击方法，最著2.3.3 DES扩展形式扩展形式多重多重DES S盒可选择的盒可选择的DES 具有独立子密钥的具有独立子密钥的DES G-DES 6/17/202418信息安全原理与技术2.3.3 DES扩展形式多重DES 8/9/202318信2.4 公钥密码体制公钥密码体制 一个安全的对称密钥密码系统，可以达到下列功能：一个安全的对称密钥密码系统，可以达到下列功能：一个安全的对称密钥密码系统，可以达到下列功能：一个安全的对称密钥密码系统，可以达到下列功能：保护信息机密保护信息机密保护信息机密保护信息机密 认证发送方之身份认证发送方之身份认证发送方之身份认证发送方之身份 确保信息完整性确保信息完整性确保信息完整性确保信息完整性 对称密钥密码系统具有下列缺点：对称密钥密码系统具有下列缺点：对称密钥密码系统具有下列缺点：对称密钥密码系统具有下列缺点：收发双方如何获得其加密密钥及解密密钥？收发双方如何获得其加密密钥及解密密钥？收发双方如何获得其加密密钥及解密密钥？收发双方如何获得其加密密钥及解密密钥？密钥的数目太大密钥的数目太大密钥的数目太大密钥的数目太大 无法达到不可否认服务无法达到不可否认服务无法达到不可否认服务无法达到不可否认服务 2.4.1 传统密码体制的缺陷与公钥密码体制的产生传统密码体制的缺陷与公钥密码体制的产生传统密码体制的缺陷与公钥密码体制的产生传统密码体制的缺陷与公钥密码体制的产生 6/17/202419信息安全原理与技术2.4 公钥密码体制 一个安全的对称密钥密码系统，可以达到下 现代密码学修正了密钥的对称性，现代密码学修正了密钥的对称性，现代密码学修正了密钥的对称性，现代密码学修正了密钥的对称性，19761976年，年，年，年，DiffieDiffie，HellmannHellmann提出了公开密钥密码体制提出了公开密钥密码体制提出了公开密钥密码体制提出了公开密钥密码体制（简称公钥体制）（简称公钥体制）（简称公钥体制）（简称公钥体制），它的加密、解密密钥是不，它的加密、解密密钥是不，它的加密、解密密钥是不，它的加密、解密密钥是不同的，也是不能（在有效的时间内）相互推导。同的，也是不能（在有效的时间内）相互推导。同的，也是不能（在有效的时间内）相互推导。同的，也是不能（在有效的时间内）相互推导。所以，它可称为所以，它可称为所以，它可称为所以，它可称为双钥密码体制双钥密码体制双钥密码体制双钥密码体制。它的产生，是。它的产生，是。它的产生，是。它的产生，是密码学革命性的发展，它一方面，为数据的保密码学革命性的发展，它一方面，为数据的保密码学革命性的发展，它一方面，为数据的保密码学革命性的发展，它一方面，为数据的保密性、完整性、真实性提供了有效方便的技术。密性、完整性、真实性提供了有效方便的技术。密性、完整性、真实性提供了有效方便的技术。密性、完整性、真实性提供了有效方便的技术。另一方面，科学地解决了密码技术的瓶颈另一方面，科学地解决了密码技术的瓶颈另一方面，科学地解决了密码技术的瓶颈另一方面，科学地解决了密码技术的瓶颈密钥的分配问题。密钥的分配问题。密钥的分配问题。密钥的分配问题。6/17/202420信息安全原理与技术现代密码学修正了密钥的对称性，1976年，Diffie，He 第一个公钥体制是第一个公钥体制是第一个公钥体制是第一个公钥体制是19771977年由年由年由年由RivestRivest，ShamirShamir，AdlemanAdleman提出的，称为提出的，称为提出的，称为提出的，称为RSARSA公钥体制，其公钥体制，其公钥体制，其公钥体制，其安全性是基于整数的因子分解的困难性。安全性是基于整数的因子分解的困难性。安全性是基于整数的因子分解的困难性。安全性是基于整数的因子分解的困难性。RSARSA公钥体制已得到了广泛的应用。其后，诸如基公钥体制已得到了广泛的应用。其后，诸如基公钥体制已得到了广泛的应用。其后，诸如基公钥体制已得到了广泛的应用。其后，诸如基于背包问题的于背包问题的于背包问题的于背包问题的Merkle-HellmanMerkle-Hellman背包公钥体制，背包公钥体制，背包公钥体制，背包公钥体制，基于有限域上离散对数问题的基于有限域上离散对数问题的基于有限域上离散对数问题的基于有限域上离散对数问题的EIGamalEIGamal公钥体公钥体公钥体公钥体制，基于椭圆曲线的密码体制等等公钥体制不制，基于椭圆曲线的密码体制等等公钥体制不制，基于椭圆曲线的密码体制等等公钥体制不制，基于椭圆曲线的密码体制等等公钥体制不断出现，使密码学得到了蓬勃的发展，断出现，使密码学得到了蓬勃的发展，断出现，使密码学得到了蓬勃的发展，断出现，使密码学得到了蓬勃的发展，6/17/202421信息安全原理与技术第一个公钥体制是1977年由Rivest，Shamir，Ad2.4.2 公钥密码体制介绍公钥密码体制介绍 公钥密码体制加解密过程主要有以下几步公钥密码体制加解密过程主要有以下几步：6/17/202422信息安全原理与技术2.4.2 公钥密码体制介绍 公钥密码体制加解密过程主要安全的公开密钥密码可以达到下列功能：安全的公开密钥密码可以达到下列功能：（1 1 1 1）简化密钥分配及管理问题）简化密钥分配及管理问题）简化密钥分配及管理问题）简化密钥分配及管理问题 公钥体制用于数据加密时：公钥体制用于数据加密时：公钥体制用于数据加密时：公钥体制用于数据加密时：用户将自己的公开（加密）密钥登记在一个公开密用户将自己的公开（加密）密钥登记在一个公开密用户将自己的公开（加密）密钥登记在一个公开密用户将自己的公开（加密）密钥登记在一个公开密钥库或实时公开，秘密密钥则被严格保密。信源为钥库或实时公开，秘密密钥则被严格保密。信源为钥库或实时公开，秘密密钥则被严格保密。信源为钥库或实时公开，秘密密钥则被严格保密。信源为了向信宿发送信息，去公开密钥库查找对方的公开了向信宿发送信息，去公开密钥库查找对方的公开了向信宿发送信息，去公开密钥库查找对方的公开了向信宿发送信息，去公开密钥库查找对方的公开密钥，或临时向对方索取公钥，将要发送的信息用密钥，或临时向对方索取公钥，将要发送的信息用密钥，或临时向对方索取公钥，将要发送的信息用密钥，或临时向对方索取公钥，将要发送的信息用这个公钥加密后在公开信道上发送给对方，对方收这个公钥加密后在公开信道上发送给对方，对方收这个公钥加密后在公开信道上发送给对方，对方收这个公钥加密后在公开信道上发送给对方，对方收到信息（密文）后，则用自己的秘密（解密）密钥到信息（密文）后，则用自己的秘密（解密）密钥到信息（密文）后，则用自己的秘密（解密）密钥到信息（密文）后，则用自己的秘密（解密）密钥解密密文，从而，读取信息。可见，这里省去了从解密密文，从而，读取信息。可见，这里省去了从解密密文，从而，读取信息。可见，这里省去了从解密密文，从而，读取信息。可见，这里省去了从秘密信道传递密钥的过程。这是公钥体制的一大优秘密信道传递密钥的过程。这是公钥体制的一大优秘密信道传递密钥的过程。这是公钥体制的一大优秘密信道传递密钥的过程。这是公钥体制的一大优点。点。点。点。6/17/202423信息安全原理与技术安全的公开密钥密码可以达到下列功能：8/9/202323信息（2 2 2 2）保护信息机密）保护信息机密）保护信息机密）保护信息机密 任任任任何何何何人人人人均均均均可可可可将将将将明明明明文文文文加加加加密密密密成成成成密密密密文文文文，此此此此后后后后只只只只有有有有拥拥拥拥有有有有解密密钥的人才能解密。解密密钥的人才能解密。解密密钥的人才能解密。解密密钥的人才能解密。6/17/202424信息安全原理与技术（2）保护信息机密 8/9/202324信息安全原理与技术（3 3 3 3）实现不可否认功能）实现不可否认功能）实现不可否认功能）实现不可否认功能 公钥体制用于数字签名时：公钥体制用于数字签名时：公钥体制用于数字签名时：公钥体制用于数字签名时：信源为了他人能够验证自己发送的消息确实来自本人，信源为了他人能够验证自己发送的消息确实来自本人，信源为了他人能够验证自己发送的消息确实来自本人，信源为了他人能够验证自己发送的消息确实来自本人，他将自己的秘密（解密）密钥公布，而将公开（加他将自己的秘密（解密）密钥公布，而将公开（加他将自己的秘密（解密）密钥公布，而将公开（加他将自己的秘密（解密）密钥公布，而将公开（加密）密钥严格保密。与别人通信时，则用自己的加密）密钥严格保密。与别人通信时，则用自己的加密）密钥严格保密。与别人通信时，则用自己的加密）密钥严格保密。与别人通信时，则用自己的加密密钥对消息加密密密钥对消息加密密密钥对消息加密密密钥对消息加密称为称为称为称为签名签名签名签名，将原消息与签名后，将原消息与签名后，将原消息与签名后，将原消息与签名后的消息一起发送的消息一起发送的消息一起发送的消息一起发送.对方收到消息后，为了确定信源的真实性，用对方的对方收到消息后，为了确定信源的真实性，用对方的对方收到消息后，为了确定信源的真实性，用对方的对方收到消息后，为了确定信源的真实性，用对方的解密密钥解密签名消息解密密钥解密签名消息解密密钥解密签名消息解密密钥解密签名消息称为称为称为称为（签名）验证（签名）验证（签名）验证（签名）验证，如果，如果，如果，如果解密后的消息与原消息一致，则说明信源是真实的，解密后的消息与原消息一致，则说明信源是真实的，解密后的消息与原消息一致，则说明信源是真实的，解密后的消息与原消息一致，则说明信源是真实的，可以接受，否则，拒绝接受。可以接受，否则，拒绝接受。可以接受，否则，拒绝接受。可以接受，否则，拒绝接受。6/17/202425信息安全原理与技术（3）实现不可否认功能 8/9/202325信息安全原理与技2.4.3 基本数学概念基本数学概念群群模逆元模逆元费尔马小定理费尔马小定理 Euler函数函数 生成元生成元 6/17/202426信息安全原理与技术2.4.3 基本数学概念群8/9/202326信息安全原2.4.4 RSA算法算法1976年：年：Diffie，Hellman在在“New Direction in Cryptography”(密码学新方密码学新方向向)一文中首次提出公开密钥密码体制的思想。一文中首次提出公开密钥密码体制的思想。1977年：年：Rivest,Shamir,Adleman第一次第一次实现了公开密钥密码体制，现称为实现了公开密钥密码体制，现称为RSA公钥公钥体制。体制。6/17/202427信息安全原理与技术2.4.4 RSA算法1976年：Diffie，Hell基本算法：基本算法：生成两个大素数生成两个大素数p和和q（保密）；（保密）；计算这两个素数的乘积计算这两个素数的乘积n=pq（公开）；（公开）；计计算算小小于于n并并且且与与n互互素素的的整整数数的的个个数数，即即欧欧拉函数拉函数(n)=(p1)(q1)（保密）；（保密）；选选取取一一个个随随机机整整数数e满满足足1e (n)，并并且且e和和(n)互素，即互素，即gcd(e,(n)=1（公开）；（公开）；计算计算d，满足满足de=1 mod (n)（保密）；（保密）；6/17/202428信息安全原理与技术8/9/202328信息安全原理与技术E(m)Kb1AKa1BD(E(m)Kb2mmRSA的加解密过程公开信道6/17/202429信息安全原理与技术E(m)Kb1AKa1BD(E(m)Kb2mmRSA的加解一个利用一个利用一个利用一个利用RSARSA算法的加密实例算法的加密实例算法的加密实例算法的加密实例 设设p=101，q=113，n=pq=11413，(n)=(p-1)(q-1)=100112=11200，a=6597，b=3533，x=9726。加密：加密：y=xb=97263533=5761 mod 11413；解密：解密：x=ya=57616597=9726 mod 11413。6/17/202430信息安全原理与技术一个利用RSA算法的加密实例 设p=101，q=113，n=算法分析：算法分析：该体制的数学依据是该体制的数学依据是Euler定理及大数分解定理及大数分解的困难性，体制中使用的是的困难性，体制中使用的是Zn中的计算。中的计算。设是两个不同奇素数设是两个不同奇素数p,q的乘积，对于这样的乘积，对于这样的正整数，其的正整数，其Euler函数值是容易计算的，函数值是容易计算的，它是它是(n)=(p-1)(q-1)。对于给定的明文。对于给定的明文xn，选定一个正整数，选定一个正整数b，称为加密密钥。，称为加密密钥。6/17/202431信息安全原理与技术算法分析：8/9/202331信息安全原理与技术作作Zn中的指数运算，将明文以指数形式中的指数运算，将明文以指数形式xb表示出来，即以指数形式将明文隐藏表示出来，即以指数形式将明文隐藏起来。即使知道一个明、密文对起来。即使知道一个明、密文对(x,y)，y=xb mod n,要得到密钥要得到密钥b，必须求解，必须求解离散对数问题：离散对数问题：b=logxy，在，在Zn中这也中这也是一个困难问题。可见这种加密思想是是一个困难问题。可见这种加密思想是简单、明确的。简单、明确的。6/17/202432信息安全原理与技术作Zn中的指数运算，将明文以指数形式xb表示出来，即以指数形RSA RSA 安全性分析安全性分析安全性分析安全性分析 加密密钥加密密钥b b是公开的，从而，要求从是公开的，从而，要求从b b不不能有效地推导出能有效地推导出a a，解已知解已知b b，求解求解ab1 mod ab1 mod (n)(n)是计算上不可能的。是计算上不可能的。(n)(n)是是n n的的EulerEuler函数，如果已知函数，如果已知(n)(n)，则，则可以应用展转相除法求得可以应用展转相除法求得b b的逆元的逆元a a，从而，从而(n)(n)的保密是安全的关键，而的保密是安全的关键，而(n)(n)的有效计的有效计算则依赖于算则依赖于n n的素因子分解，从而，的素因子分解，从而，RSARSA的安的安全性与全性与n n的素因子分解等价。的素因子分解等价。体制的安全性机理是大数分解的困难性。体制的安全性机理是大数分解的困难性。6/17/202433信息安全原理与技术RSA 安全性分析8/9/202333信息安全原理与技术 大数分解是一个大数分解是一个大数分解是一个大数分解是一个NPNP问题问题问题问题，目前已知的最好的算法，目前已知的最好的算法，目前已知的最好的算法，目前已知的最好的算法需要进行需要进行需要进行需要进行e e e ex x x x次算术运算。假设我们用一台每秒运算次算术运算。假设我们用一台每秒运算次算术运算。假设我们用一台每秒运算次算术运算。假设我们用一台每秒运算（即：一亿）次的计算机来分解一个（即：一亿）次的计算机来分解一个（即：一亿）次的计算机来分解一个（即：一亿）次的计算机来分解一个200200位十进位十进位十进位十进制的数制的数制的数制的数 要分解一个要分解一个要分解一个要分解一个200200位十进制的数，需要位十进制的数，需要位十进制的数，需要位十进制的数，需要3.83.810107 7年，年，年，年，类似地，可算出要分解一个类似地，可算出要分解一个类似地，可算出要分解一个类似地，可算出要分解一个300300位的十进制整数，位的十进制整数，位的十进制整数，位的十进制整数，则需要年则需要年则需要年则需要年4.86 4.86 10 101313。可见，增加的位数，将大。可见，增加的位数，将大。可见，增加的位数，将大。可见，增加的位数，将大大地提高体制的安全性。大地提高体制的安全性。大地提高体制的安全性。大地提高体制的安全性。由以上分析可见，从直接分解大数来破译由以上分析可见，从直接分解大数来破译由以上分析可见，从直接分解大数来破译由以上分析可见，从直接分解大数来破译RSARSA是是是是计算上不可能的，那么是否存在一种破译方法不计算上不可能的，那么是否存在一种破译方法不计算上不可能的，那么是否存在一种破译方法不计算上不可能的，那么是否存在一种破译方法不依赖于的分解呢？虽然现在还没有发现，但是也依赖于的分解呢？虽然现在还没有发现，但是也依赖于的分解呢？虽然现在还没有发现，但是也依赖于的分解呢？虽然现在还没有发现，但是也没有严格的论证。没有严格的论证。没有严格的论证。没有严格的论证。6/17/202434信息安全原理与技术大数分解是一个NP问题，目前已知的最好的算法需要进行ex次算 直接分解一个大素数的强力攻击的一个实例是：直接分解一个大素数的强力攻击的一个实例是：直接分解一个大素数的强力攻击的一个实例是：直接分解一个大素数的强力攻击的一个实例是：19941994年年年年4 4月分解的月分解的月分解的月分解的RSARSA密钥密钥密钥密钥RSA-129RSA-129，即分，即分，即分，即分解了一个解了一个解了一个解了一个129129位十进制，位十进制，位十进制，位十进制，425425比特的大素数。比特的大素数。比特的大素数。比特的大素数。分解时启用了分解时启用了分解时启用了分解时启用了16001600台计算机，耗时台计算机，耗时台计算机，耗时台计算机，耗时8 8个月，处个月，处个月，处个月，处理了理了理了理了4600MIPS4600MIPS年的数据。年的数据。年的数据。年的数据。1MIPS1MIPS年是年是年是年是1MIPS1MIPS的机器一年所能处理数据量。的机器一年所能处理数据量。的机器一年所能处理数据量。的机器一年所能处理数据量。Pentium100Pentium100大约是大约是大约是大约是125MIPS125MIPS，它分解，它分解，它分解，它分解RSA-RSA-129129需要需要需要需要3737年。年。年。年。100100台台台台Pentium100Pentium100需要需要需要需要4 4个个个个月。月。月。月。6/17/202435信息安全原理与技术直接分解一个大素数的强力攻击的一个实例是：1994年4月分解 硬件实现时，硬件实现时，硬件实现时，硬件实现时，RSARSA比比比比DESDES要慢大约要慢大约要慢大约要慢大约10001000倍，倍，倍，倍，软件实现时，软件实现时，软件实现时，软件实现时，RSARSA比比比比DESDES要慢大约要慢大约要慢大约要慢大约100100倍。可倍。可倍。可倍。可见，用见，用见，用见，用RSARSA直接加密信息有诸多不便，所以，直接加密信息有诸多不便，所以，直接加密信息有诸多不便，所以，直接加密信息有诸多不便，所以，很多实际系统中，只用很多实际系统中，只用很多实际系统中，只用很多实际系统中，只用RSARSA来交换来交换来交换来交换DESDES的密钥，的密钥，的密钥，的密钥，而用而用而用而用DESDES来加密主体信息。来加密主体信息。来加密主体信息。来加密主体信息。6/17/202436信息安全原理与技术硬件实现时，RSA比DES要慢大约1000倍，软件实现时，R2.5 散列函数散列函数 2.5.1 2.5.1 散列函数的概念散列函数的概念散列函数的概念散列函数的概念 散散散散列列列列函函函函数数数数又又又又可可可可称称称称为为为为压压压压缩缩缩缩函函函函数数数数、杂杂杂杂凑凑凑凑函函函函数数数数、消消消消息息息息摘摘摘摘要要要要、指指指指纹纹纹纹、密密密密码码码码校校校校验验验验和和和和、信信信信息息息息完完完完整整整整性性性性检检检检验验验验(DIC)(DIC)、操作检验码、操作检验码、操作检验码、操作检验码(MDC)(MDC)。散列函数有散列函数有散列函数有散列函数有4 4个主要特点：个主要特点：个主要特点：个主要特点：它能处理任意大小的信息它能处理任意大小的信息它能处理任意大小的信息它能处理任意大小的信息它是不可预见的。它是不可预见的。它是不可预见的。它是不可预见的。它是完全不可逆的，即散列函数是单向的它是完全不可逆的，即散列函数是单向的它是完全不可逆的，即散列函数是单向的它是完全不可逆的，即散列函数是单向的它是抗碰撞的它是抗碰撞的它是抗碰撞的它是抗碰撞的6/17/202437信息安全原理与技术2.5 散列函数 2.5.1 散列函数的概念 8/9/20单向散列函数的工作原理单向散列函数的工作原理单向散列函数的工作原理单向散列函数的工作原理 常用的消息摘要算法有：常用的消息摘要算法有：常用的消息摘要算法有：常用的消息摘要算法有：（1 1）MD2MD2算法算法算法算法 （2 2）MD4MD4和和和和MD5MD5算法算法算法算法（3 3）SHASHA算法算法算法算法6/17/202438信息安全原理与技术单向散列函数的工作原理 8/9/202338信息安全原理与技 2.5.2 MD52.5.2 MD5算法算法算法算法 算法算法算法算法MDMD5 5首先填充消息成首先填充消息成首先填充消息成首先填充消息成512512比特的整数比特的整数比特的整数比特的整数倍，但最后倍，但最后倍，但最后倍，但最后6464比特是由文件长度填充的；其次，比特是由文件长度填充的；其次，比特是由文件长度填充的；其次，比特是由文件长度填充的；其次，将个将个将个将个512512比特分割成比特分割成比特分割成比特分割成1616个个个个3232比特子块；取比特子块；取比特子块；取比特子块；取4 4个初个初个初个初始向量，从其及第一个子块出发，作始向量，从其及第一个子块出发，作始向量，从其及第一个子块出发，作始向量，从其及第一个子块出发，作4 4轮（轮（轮（轮（MDMD4 4只有只有只有只有3 3轮）轮）轮）轮）16 16次迭代。得次迭代。得次迭代。得次迭代。得128128比特输出；以比特输出；以比特输出；以比特输出；以此作为初始向量，对下一个此作为初始向量，对下一个此作为初始向量，对下一个此作为初始向量，对下一个512512比特执行同样比特执行同样比特执行同样比特执行同样的操作；的操作；的操作；的操作；依次下去，直到所有的依次下去，直到所有的依次下去，直到所有的依次下去，直到所有的512512比特都处理完毕，比特都处理完毕，比特都处理完毕，比特都处理完毕，输出输出输出输出128128比特，此即比特，此即比特，此即比特，此即MDMD5 5的输出。的输出。的输出。的输出。6/17/202439信息安全原理与技术2.5.2 MD5算法 8/9/202339信息安全原理与2.6 数字签名数字签名数字签名最早被建议用来对禁止核试验数字签名最早被建议用来对禁止核试验条律的验证。禁止核试验条律的缔约国条律的验证。禁止核试验条律的缔约国为了检测对方的核试验，需要把地震测为了检测对方的核试验，需要把地震测试仪放在对方的地下，而把测试的数据试仪放在对方的地下，而把测试的数据送回，自然这里有一个矛盾：东道主需送回，自然这里有一个矛盾：东道主需要检查发送的数据是否仅为所需测试的要检查发送的数据是否仅为所需测试的数据；检测方需要送回的数据是真实的数据；检测方需要送回的数据是真实的检测数据，东道主没有篡改检测数据，东道主没有篡改。6/17/202440信息安全原理与技术2.6 数字签名数字签名最早被建议用来对禁止核试验条律的基本要求：基本要求：1.签名不能伪造：签名不能伪造：签名是签名者对文件内容合法签名是签名者对文件内容合法签名是签名者对文件内容合法签名是签名者对文件内容合法性的认同、证明、和标记，其他人的签名无效性的认同、证明、和标记，其他人的签名无效性的认同、证明、和标记，其他人的签名无效性的认同、证明、和标记，其他人的签名无效；2.签名不可抵赖：签名不可抵赖：这是对签名者的约束，签名者这是对签名者的约束，签名者这是对签名者的约束，签名者这是对签名者的约束，签名者的认同、证明、标记是不可否认的；的认同、证明、标记是不可否认的；的认同、证明、标记是不可否认的；的认同、证明、标记是不可否认的；3.签名不可改变：签名不可改变：文件签名后是不可改变的，这文件签名后是不可改变的，这文件签名后是不可改变的，这文件签名后是不可改变的，这保证了签名的真实性、可靠性；保证了签名的真实性、可靠性；保证了签名的真实性、可靠性；保证了签名的真实性、可靠性；4.签名不可重复使用：签名不可重复使用：签名需要时间标记，这签名需要时间标记，这签名需要时间标记，这签名需要时间标记，这样可以保证签名不可重复使用。样可以保证签名不可重复使用。样可以保证签名不可重复使用。样可以保证签名不可重复使用。5.签名容易验证：签名容易验证：对于签名的文件，一旦发生纠对于签名的文件，一旦发生纠对于签名的文件，一旦发生纠对于签名的文件，一旦发生纠纷，任何第三方都可以准确、有效地进行验证。纷，任何第三方都可以准确、有效地进行验证。纷，任何第三方都可以准确、有效地进行验证。纷，任何第三方都可以准确、有效地进行验证。6/17/202441信息安全原理与技术基本要求：8/9/202341信息安全原理与技术数字签名的基本原理：数字签名的基本原理：应用一对不可互相应用一对不可互相推导的密钥，推导的密钥，一个用于签名（加密），一一个用于签名（加密），一个用于验证（解密），颠倒使用加解密过个用于验证（解密），颠倒使用加解密过程。程。公钥签名原理：公钥签名原理：这种签名就是加密过程的这种签名就是加密过程的简单颠倒使用，签名者用加密密钥（保密）简单颠倒使用，签名者用加密密钥（保密）签名（加密）文件，验证者用（公开的）签名（加密）文件，验证者用（公开的）解密密钥解密文件，确定文件的真伪。解密密钥解密文件，确定文件的真伪。6/17/202442信息安全原理与技术数字签名的基本原理：应用一对不可互相推导的密钥，一个用于签散列函数：散列函数：散列函数：散列函数：散列函数是数字签名的一个重要散列函数是数字签名的一个重要散列函数是数字签名的一个重要散列函数是数字签名的一个重要辅助工具，辅助工具，辅助工具，辅助工具，应用散列函数可以生成一个文件应用散列函数可以生成一个文件应用散列函数可以生成一个文件应用散列函数可以生成一个文件的，具有固定长度的文件摘要，从而使数字的，具有固定长度的文件摘要，从而使数字的，具有固定长度的文件摘要，从而使数字的，具有固定长度的文件摘要，从而使数字签名可以迅速有效地签名一个任意长度的文签名可以迅速有效地签名一个任意长度的文签名可以迅速有效地签名一个任意长度的文签名可以迅速有效地签名一个任意长度的文件。一般地，对文件的任意小改动，都会改件。一般地，对文件的任意小改动，都会改件。一般地，对文件的任意小改动，都会改件。一般地，对文件的任意小改动，都会改变文件的散列值，从而，秘密的散列函数可变文件的散列值，从而，秘密的散列函数可变文件的散列值，从而，秘密的散列函数可变文件的散列值，从而，秘密的散列函数可以用来检测病毒等对文件的破坏。以用来检测病毒等对文件的破坏。以用来检测病毒等对文件的破坏。以用来检测病毒等对文件的破坏。对签名的攻击：对签名的攻击：对签名的攻击：对签名的攻击：对数字签名有各种各样的欺对数字签名有各种各样的欺对数字签名有各种各样的欺对数字签名有各种各样的欺骗存在，重复使用是一个典型欺骗，如电子骗存在，重复使用是一个典型欺骗，如电子骗存在，重复使用是一个典型欺骗，如电子骗存在，重复使用是一个典型欺骗，如电子支票，重复的使用具有可怕后果，阻止这种支票，重复的使用具有可怕后果，阻止这种支票，重复的使用具有可怕后果，阻止这种支票，重复的使用具有可怕后果，阻止这种欺骗的有效方法是签名中包含时间日期标志。欺骗的有效方法是签名中包含时间日期标志。欺骗的有效方法是签名中包含时间日期标志。欺骗的有效方法是签名中包含时间日期标志。6/17/202443信息安全原理与技术散列函数：散列函数是数字签名的一个重要辅助工具，应用散列函常用算法介绍常用算法介绍1 1、ElgamalElgamal算算算算法法法法：ElGamalElGamal签签签签名名名名方方方方案案案案基基基基于于于于离离离离散散散散对数问题对数问题对数问题对数问题离散对数问题：设离散对数问题：设离散对数问题：设离散对数问题：设p p是一个素数，是一个素数，是一个素数，是一个素数，b b Z Z*p p，寻找，寻找，寻找，寻找整数整数整数整数 d d，0dp0dp，满足：，满足：，满足：，满足：a ad db mod b mod p p。这样的。这样的。这样的。这样的问题称为离散对数问题。问题称为离散对数问题。问题称为离散对数问题。问题称为离散对数问题。选取选取选取选取p p至少至少至少至少150150位十进制数，位十进制数，位十进制数，位十进制数，p-1p-1至少有一个至少有一个至少有一个至少有一个“大大大大”素因子，则离散对数问题称为困难问题，困素因子，则离散对数问题称为困难问题，困素因子，则离散对数问题称为困难问题，困素因子，则离散对数问题称为困难问题，困难问题不存在多项式时间算法难问题不存在多项式时间算法难问题不存在多项式时间算法难问题不存在多项式时间算法6/17/202444信息安全原理与技术常用算法介绍8/9/202344信息安全原理与技术ElGamal签名方案于签名方案于1985年提出，改进后，年提出，改进后，被美国国家标准和技术研究所（被美国国家标准和技术研究所（NIST）采纳）采纳为数字签名标准。为数字签名标准。ElGamal签名方案是一个签名方案是一个非确定性的方案，也就是说，验证算法可以非确定性的方案，也就是说，验证算法可以接受的合法签名不止一个。接受的合法签名不止一个。6/17/202445信息安全原理与技术ElGamal签名方案于1985年提出，改进后，被美国国家标ElGamal签名方案的定义：签名方案的定义：设设p是一个素数，是一个素数，Zp中的离散对数是困难问题，中的离散对数是困难问题，a Z*p是一个生成元，是一个生成元，bad mod p，则定义：，则定义：签名算法：签名算法：Sigk(x,t)=(,)，at mod p，(x-a)t-1 mod p-1，t是一保密的随机数。是一保密的随机数。验证算法：对给定的消息及签名验证算法：对给定的消息及签名(x,(,)，x,Z*p,Zp-1，验证算法为验证算法为6/17/202446信息安全原理