第五章 公钥密码算法

1、n基本概念基本概念n基本原理基本原理n常见算法常见算法对称算法的缺陷对称算法的缺陷n尽管对称密码技术有一些很好的特性，但它也尽管对称密码技术有一些很好的特性，但它也存在着明显的缺陷，存在着明显的缺陷，主要在于其密钥的管理主要在于其密钥的管理： n 进行安全通信前需要以安全方式进行密钥交换进行安全通信前需要以安全方式进行密钥交换。这一步骤，在某种情况下是可行的，但在某些情况下会非常困难，甚至无法实现。n 密钥规模复杂密钥规模复杂。举例来说，A与B两人之间的密钥必须不同于A和C两人之间的密钥，否则A给B的消息的安全性就会受到威胁。 公钥算法的提出公钥算法的提出n公钥密码算法是指加密和解密数据使用两

2、个不同的密钥，即公钥密码算法是指加密和解密数据使用两个不同的密钥，即加密和解密的密钥是不对称的加密和解密的密钥是不对称的，这种密码系统也称为，这种密码系统也称为公钥密公钥密码系统码系统PKC (Public Key Cryptosystem) n公钥密码学的概念首先是由Diffie和Hellman两人在1976年发表的一篇著名论文：“密码学的新方向”中提出的，并引起很大的轰动。该论文曾获得该论文曾获得IEEE信息论学会的最佳论文奖信息论学会的最佳论文奖 n与对称密码算法不同的是，公钥密码算法将随机产生两个密钥：n 一个用于加密明文，其密钥是公开的，称为公钥n 另一个用来解密密文，其密钥是秘密的

3、，称为私钥 基本原理基本原理保密系统原理保密系统原理n发送者首先要发送者首先要获得接收者的公钥获得接收者的公钥，并，并使用接收使用接收者的公钥加密原文者的公钥加密原文，然后，然后将密文传输给接收者将密文传输给接收者 n接收者使用自己的私钥才能解密密文 优、缺点分析优、缺点分析n由于加密密钥是公开的，不需要建立额外的安全信道来分发由于加密密钥是公开的，不需要建立额外的安全信道来分发密钥，而解密密钥是由用户自己保管的，与对方无关，从而密钥，而解密密钥是由用户自己保管的，与对方无关，从而避免了在对称密码系统中容易产生的任何一方单方面密钥泄避免了在对称密码系统中容易产生的任何一方单方面密钥泄露问题以及

4、分发密钥时的不安全因素和额外的开销露问题以及分发密钥时的不安全因素和额外的开销 n公钥密码算法的特点是安全性高、密钥易于管理，公钥密码算法的特点是安全性高、密钥易于管理，缺点是计缺点是计算量大、加密和解密速度慢算量大、加密和解密速度慢 使用方式使用方式n公钥密码算法比较适合于公钥密码算法比较适合于加密短信息加密短信息 n通常采用由公钥密码算法和对称密码算法构成通常采用由公钥密码算法和对称密码算法构成的的混合密码系统混合密码系统，发挥各自的优势，发挥各自的优势 n使用对称密码算法来加密数据，加密速度快；使用对称密码算法来加密数据，加密速度快；使用公钥密码算法来加密对称密码算法的密钥使用公钥密码算

5、法来加密对称密码算法的密钥，形成高安全性的密钥分发信道，形成高安全性的密钥分发信道n还可以用来实现还可以用来实现数字签名数字签名和和身份验证身份验证机制机制通信过程通信过程n网络中的用户约定一个共同的公开密钥密码系网络中的用户约定一个共同的公开密钥密码系统，每个用户都有自己的公钥和私钥，并且所统，每个用户都有自己的公钥和私钥，并且所有的公钥都保存在有的公钥都保存在某个公开的数据库某个公开的数据库中，任何中，任何用户都可以访问此数据库用户都可以访问此数据库 优点总结优点总结n通信双方事先不需要通过保密信道交换密钥通信双方事先不需要通过保密信道交换密钥 n密钥持有量大大减少密钥持有量大大减少 n非

6、对称密码技术还提供了对称密码技术无法或非对称密码技术还提供了对称密码技术无法或很难提供的服务很难提供的服务 基本服务基本服务n加密加密/解密解密：发送方可以用接收方的公钥加密消：发送方可以用接收方的公钥加密消息息 n数字签名数字签名：发送方用其私钥：发送方用其私钥“签署签署”消息，通消息，通过对消息或作为消息函数的小块数据应用加密过对消息或作为消息函数的小块数据应用加密算法来进行签署算法来进行签署 n密钥交换密钥交换：两方互相合作可以进行会话密钥的：两方互相合作可以进行会话密钥的交换交换 公钥系统满足的条件公钥系统满足的条件n通讯双方通讯双方A和和B容易容易通过通过计算计算产生出产生出一对密钥

7、一对密钥 n在知道公开密钥和待加密报文在知道公开密钥和待加密报文M的情况下，对于发送方的情况下，对于发送方A，很容易通过计算产生对应的密文很容易通过计算产生对应的密文 n接收方接收方B使用私有密钥能够很使用私有密钥能够很容易容易地对所接收到的密文地对所接收到的密文进行进行解密计算解密计算以恢复原来的报文以恢复原来的报文 n除A和B以外的其他人即使知道公钥，要确定私钥在计算上也是不可行的 n除A和B以外的其他人即使知道公钥和密文C，要想恢复原来的明文M在计算上也是不可行的 这些要求最终可以归结到设计一个单向陷门函数这些要求最终可以归结到设计一个单向陷门函数 单向函数相关定义单向函数相关定义n单射

8、函数单射函数：1 1对对1 1映射映射 n单向函数单向函数：一个可逆函数，算：一个可逆函数，算f(xf(x) )容易，但求容易，但求x x难难n陷门单向函数陷门单向函数：单向函数是求逆困难的函数，而单向函数是求逆困难的函数，而单向陷门函数单向陷门函数(Trapdoor one-way function)(Trapdoor one-way function)，是在不知陷门信息下求逆困难的函数，当知道是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的陷门信息后，求逆是易于实现的n这是这是Diffie和和Hellmam于于1976年引入的有用概念年引入的有用概念 关于关于陷门单向函

9、数陷门单向函数n生活实例生活实例：号码锁号码锁在不知预设号码时很难开，在不知预设号码时很难开，但若知道所设号码则容易开启；但若知道所设号码则容易开启；太平门太平门是另一是另一例，从里面向外出容易，若无钥匙者反向难进例，从里面向外出容易，若无钥匙者反向难进 n但如何给陷门单向函数下定义则很棘手，因为但如何给陷门单向函数下定义则很棘手，因为 n陷门函数其实就不是单向函数陷门函数其实就不是单向函数，因为单向函数是在任，因为单向函数是在任何条件下求逆都是困难的何条件下求逆都是困难的 n陷门可能不止一个陷门可能不止一个，通过试验，一个个陷门就可容易，通过试验，一个个陷门就可容易地找到逆。如果陷门信息的保

10、密性不强，求逆也就不地找到逆。如果陷门信息的保密性不强，求逆也就不难难 n定义定义3给出了公钥系统所要求的条件给出了公钥系统所要求的条件 密码算法中用到的陷门单向函数密码算法中用到的陷门单向函数 n多项式求根多项式求根n离散对数离散对数 n大整数分解大整数分解 n背包问题背包问题nDiffie-Hellman问题问题 n二次剩余问题二次剩余问题 目前多数双钥体制是基于这些问题构造的目前多数双钥体制是基于这些问题构造的 DHDH密钥交换协议密钥交换协议nDiffie-Hellman(DH)密钥交换协议主要用于通信双方密钥交换协议主要用于通信双方的的密钥交换密钥交换或称或称密钥协商密钥协商过程过程

11、 n使用该协议进行密钥交换需要在该协议的基础上使用该协议进行密钥交换需要在该协议的基础上增加消增加消息认证性以抵抗中间人攻击息认证性以抵抗中间人攻击即可即可 n应用非常简单应用非常简单，而且，而且具有前向保密性的安全特性具有前向保密性的安全特性，能够，能够满足当前本领域对信息安全系统的最新安全要求满足当前本领域对信息安全系统的最新安全要求 n中国无线局域网安全标准WAPI就是采用DH密钥交换协议来实现接入点AP和终端STA之间的密钥协商 协议内容协议内容协议内容协议内容1212(,)KKM C K KEd1212(,)KKM C K KEd中间人攻击中间人攻击man-in-the-middle

12、man-in-the-middleRSARSA加密算法加密算法nRSA是是第一个比较完善第一个比较完善的公钥密码算法的公钥密码算法 n既可用于既可用于加密数据加密数据，又可用于，又可用于数字签名数字签名，并且，并且比较比较容易理解和实现容易理解和实现 nRSA算法经受住了多年的密码分析的攻击，具算法经受住了多年的密码分析的攻击，具有较高的安全性和可信度有较高的安全性和可信度 nRSA简单实用，几乎可以满足任何应用场合简单实用，几乎可以满足任何应用场合 关于关于RSARSAnMIT三位年青数学家三位年青数学家R.L.Rivest，A.Shamir和和L.Adleman于于1978年和年和1979

13、年发现了一种用年发现了一种用数论构造双钥的方法，称作数论构造双钥的方法，称作MIT算法算法，后来被，后来被广泛称之为广泛称之为RSA算法算法 n国际上一些标准化组织国际上一些标准化组织ISO、ITU、及、及SWIFT等均已接受等均已接受RSA算法作为标准算法作为标准n在在Internet中所采用的中所采用的PGP(Pretty Good Privacy)中也将中也将RSA作为传送会话密钥和数字作为传送会话密钥和数字签字的标准算法签字的标准算法 RSARSA算法算法 RSARSA算法算法 问题问题n怎么产生怎么产生大素数大素数？ n需要多大素数？需要多大素数？n软件实现常碰到哪些问题？软件实现常

14、碰到哪些问题？n加密的特点加密的特点? ?确定性加密确定性加密 ElGamalElGamal算法算法 n一般来说，一个工程问题需要使用公钥加密算法时，我们印一般来说，一个工程问题需要使用公钥加密算法时，我们印象中的不二选择一定会是象中的不二选择一定会是RSA加密算法加密算法 n这没有什么问题，因为这没有什么问题，因为RSA不仅安全，而且容易实现不仅安全，而且容易实现 n但是，众所周知，但是，众所周知，RSA算法是一个确定性算法算法是一个确定性算法，对同一明文，对同一明文加密多次，其密文都是相同的，这本身没有什么安全漏洞加密多次，其密文都是相同的，这本身没有什么安全漏洞 n但是，如果工程应用的安

15、全性很高，为了避免攻击者搜集明为了避免攻击者搜集明密文对进行攻击，我们就必需选取一些随机加密算法密文对进行攻击，我们就必需选取一些随机加密算法 nElGamal于于1984和和1985年提出，是一种基于离散对数问题年提出，是一种基于离散对数问题的双钥密码算法，的双钥密码算法，既可用于加密，又可用于签字，是一种随既可用于加密，又可用于签字，是一种随机加密算法机加密算法 ElGamalElGamal算法算法 ElGamalElGamal算法算法 椭圆曲线密码体制椭圆曲线密码体制(ECC) n椭圆曲线密码体制椭圆曲线密码体制ECC是目前公钥体制中是目前公钥体制中每比每比特密钥安全强度最高特密钥安全强

16、度最高的一种密码体制的一种密码体制 n在相同安全强度条件下，椭圆曲线密码体制在相同安全强度条件下，椭圆曲线密码体制具具有较短的密钥长度，较少的计算量、存储量、有较短的密钥长度，较少的计算量、存储量、带宽等优点带宽等优点，而且椭圆曲线密码体制已经得到，而且椭圆曲线密码体制已经得到非常广泛的应用，非常广泛的应用，主要用于如智能卡等性能较主要用于如智能卡等性能较低的设备低的设备 n在中国无线局域网安全标准WAPI中，ECC已被采用 ECC与与RSA具体比较具体比较 nECC和和RSA相比，在许多方面都有绝对的优势，主要体现在以下方相比，在许多方面都有绝对的优势，主要体现在以下方面面n抗攻击性强抗攻击

17、性强。相同的密钥长度，其抗攻击性要强很多倍。相同的密钥长度，其抗攻击性要强很多倍 n计算量小，处理速度快。ECC总的速度比RSA、DSA要快得多 n存储空间占用小。ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多，意味着它所占的存贮空间要小得多 n带宽要求低。当对长消息进行加解密时，RSA、DSA和ECC有相同的带宽要求，但应用于短消息时ECC带宽要求却低得多 nECC的这些特点使它必将能够取代RSA，成为通用的公钥加密算法。比如SET协议的制定者已把它作为下一代SET协议中缺省的公钥密码算法 RSA和和ECC安全模长的比较安全模长的比较 攻破时间攻破时间(MIPS年年)RSA/DSA(密钥长度密钥长度)ECC密钥长度密钥长度RSA/ECC密钥长度比密钥长度比1045121065：11087681326：1101110241607：11020204821