73第四章公钥密码体制

背景对称密钥编码所面临的难题密钥分配。通信密钥太多，管理和分发困难。数字签名和认证。密码体制上的突破Diffie&Hellman,“NewDirectioninCryptography”,1976。首次公开提出了“公开密钥密码编码学”的概念。这是一个与对称密码编码截然不同的方案。提出公开密钥的理论时，其实用性并没有又得到证明：当时还未发现满足公开密钥编码理论的算法；直到1978年，RSA算法的提出。1976年，W.Diffie和M.E.Hellman发表了“密码学的新方向（NewDirectionsinCryptography)”一文，提出了公钥密码学（Public-keycryptography）的思想，在公钥密码体制（Public-keycryptosystem）中加密密钥和解密密钥是不同的，加密密钥可以公开传播而不会危及密码体制的安全性。通信的一方利用某种数学方法可以产生一个密钥对，一个称为公钥（Public-key)，另外一个称为私钥（Private-key)。该密钥对中的公钥与私钥是不同的，但又是相互对应的，并且由公钥不能推导出对应的私钥。选择某种算法（可以公开）能做到：用公钥加密的数据只有使用与该公钥配对的私钥才能解密。基本特征两个密钥：使用一个密钥进行加密，用另一个相关的密钥进行解密用加密密钥生成的密文只有使用其对应的解密密钥才能解密。两个密钥的关系满足：两个密钥是不相同；且在仅知道密码算法和加密密钥的情况下，要推断解密密钥在计算上是不可行的。优点密钥管理加密密钥是公开的；解密密钥需要妥善保存；在当今具有用户量大、消息发送方与接收方具有明显的信息不对称特点的应用环境中表现出了令人乐观的前景。数字签名和认证只有解密密钥能解密，只有正确的接收者才拥有解密密钥。公钥密码算法基础单向函数对于一个函数，如果对于其定义域上的任意x，都容易计算，同时，对于其值域中几乎所有的取值y，计算其逆函数都是不可行的，则函数被称为单向函数。可以提供单向函数的三大数学难题大整数分解问题（简称IFP）；离散对数问题（简称DLP）；椭圆曲线离散对数问题（简称ECDLP）。)(xf)(xf)(1yf)(xf公钥密码算法基础单向陷门函数对于一个单向函数，如果其逆函数在已知某些辅助信息的情况下容易求解得出，则称该单向函数为单向陷门函数。构造公钥密码系统的关键是如何在求解某个单向函数的逆函数的NP完全问题中设置合理的“陷门”)(xf)(1yf)(xf公钥密码算法基于因子分解问题的Rabin算法；椭圆曲线公钥算法；基于有限域中离散对数难题的ElGamal公钥密码算法基于代数编码系统的McEliece公钥密码算法；基于“子集和”难题的Merkle-HellmanKnapsack公钥密码算法；目前被认为安全的Knapsack型公钥密码算法Chor-Rivest。RSA公钥密码算法RSA是Rivet，Shamir和Adleman于1978年在美国麻省理工学院研制出来的，它是一种比较典型的公开密钥加密算法。基础大数分解和素性检测——将两个大素数相乘在计算上很容易实现，但将该乘积分解为两个大素数因子的计算量是相当巨大的，以至于在实际计算中是不能实现的。RSA公钥密码算法（续）算法内容(1)公钥选择两个互异的大质数和，使，，是欧拉函数，选择一个正数，使其满足，则将作为公钥。(2)私钥求出正数使其满足，则将作为私钥。(3)加密变换将明文作变换,使，从而得到密文。(4)解密变换将密文作变换,使，从而得到明文。pqpqn11qpn)(ne1,1,nneenKp,d1,mod1nndeqpdKs,,MnMMEKCepmodCCnCCDKMdsmodMRSA公钥密码算法（续）如果A要发送信息M给B，A和B之间用以下方式进行通信：计算密文→发送C给B→从A接收C→计算明文.一般要求p，q为安全质数，现在商用的安全要求为n的长度不少于1024位。)(MEKCBpCDKMBsRSA公钥密码算法（续）算法的安全性分析1.如果密码分析者能分解的因子和，他就可以求出和解密的密钥，从而能破译RSA，因此破译RSA不可能比因子分解难题更困难。2.如果密码分析者能够不对进行因子分解而求得，则可以根据求得解密密钥，从而破译RSA。因为所以知道和就可以容易地求得和，从而成功分解，因此，不对进行因子分解而直接计算并不比对进行因子分解更容易。npqndnndemod1d1nnqpnqpqp42nnpqnnnnRSA公钥密码算法（续）3.如果密码分析者既不能对n进行因子分解,也不能求而直接求得解密密钥，则他就可以计算是的倍数。而且利用的倍数可以容易地分解出n的因子。因此直接计算解密密钥并不比对n进行因子分解更容易。注意问题p和q的长度相差不能太多.p-1和q-1都应该包含大的素因子。p-1和q-1的最大公因子要尽可能小。ndd1,1edednnRSA安全性分析影响RSA算法安全性的因素主要有：密码分析者若能计算，由定义知的两个根为p和q，即能分解n。实际上知道就可以依据Euclidean算法从公钥e计算得出私钥d。在构造n时应选择p和q，使得p-1和q-1有大的素因子。一般选择p和(p-1)/2均是素数的p。通过截获来自不同用户的密文，密码分析者能够有机会计算出密文，因此，不同用户之间不要共享整数n。RSA算法具有同态的特点，在具体应用中，经常在加密之前对明文进行杂凑处理或者单向变换，以此破坏RSA算法的同态性质。)(n0)1)((2npnnp)(nRSA的性能同等强度的DES与RSA比较硬件实现：比DES慢1000倍。软件实现：比DES慢100倍。安全强度：RSA的缺点RSA的缺点主要有：产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。分组长度太大，为保证安全性，n至少也要600比特以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(SecureElectronicTransaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。ElGamal算法该体制是由ElGamal在1985年提出的，其安全性是基于有限域上计算离散对数的困难性。ElGamal提出了加密模型和认证模型两种体制，加密模型没有被充分应用，而其认证模型是美国数字签名标准（DSS）的基础。ElGamal算法算法内容1.选取大素数，是一个本原元，和公开。2.随机选取整数计算是公开的加密密钥，是保密的解密密钥。3.明文空间为，密文空间为4.加密变换为：对任意明文，秘密随机选取一个整数，则密文为其中5.解密变换：对任意密文，明文为p*pZp21,pddpdmodd*pZ**ppZZ*pZmk21pk21,ccc.mod,mod21pmcpckk**21,ppZZcccpccmdmod112ElGamal算法的安全性分析有限域上的离散对数问题定义设是素数，，是一个本原元，已知和，求满足的唯一整数，称为有限域上的离散对数问题。现在要求在ElGamal密码算法的应用中，素数p按十进制表示至少应该有150位数字，并且p-1至少应该有一个大的素因子。ppZpZpnmodn20pn椭圆曲线算法1985年Koblitz和Miller提出在密码学中应用椭圆曲线的思想，使其成为构造公开密钥密码系统的一个有利工具。其安全性是基于椭圆曲线上的离散对数计算的困难性。优点：椭圆曲线上离散对数的计算要比有限域上离散对数的计算更困难。与RSA相比，椭圆曲线密码体制能用较短的密钥达到较强的安全性，这样实现上能节省系统资源。椭圆曲线算法（续）1.有限域上的椭圆曲线设表示一个有限域，是域上的椭圆曲线，则是一个点的集合，表示为：其中表示无穷远点。在上定义’+’运算，是过的直线与曲线的另一交点关于x轴的对称点，当时，是点的切线与曲线的另一交点关于轴的对称点。这样，构成可换群(Abel群)，O是加法单位元(零元)。KEKEERRQP,QP,QPRPx,EO,,,,,,,/,6423164223312KyxaaaaaaxaxaxyaxyayyxKEO椭圆曲线算法（续）椭圆曲线离散对数问题（ECDLP）：给定义在上的椭圆曲线，一个阶的点和点，如果存在1，确定整数1,01n-1,。RSA是基于因子分解，其算法的核心就是如何寻找大数的因子分解，但ECDLP是比因子分解难得多的问题。KEnKEP/KEQ/PQ1椭圆曲线中两种运算示意图椭圆曲线上的加法：P＋Q＝R椭圆曲线上一点的2倍：P＋P＝R椭圆曲线算法（续）2.椭圆曲线上的密码算法1985年N.Koblitz和Miller提出将椭圆曲线用于密码算法，分别利用有限域上椭圆曲线的点构成的群，实现了离散对数密码算法。椭圆曲线数字签名算法ECDSA，由IEEE工作组和ANSI（AmercianNationalStandardsInstitute）X9组织开发。椭圆曲线算法（续）3.椭圆曲线密码算法的发展RSA的长密钥带来了运算速度慢和密钥存储与管理的问题。由于其自身的优点，椭圆曲线密码学被普遍认为将替代RSA成为通用的密码算法。应用：数字签名，智能卡研究：陶仁骥，陈世华－基于有限自动机的公开密钥加密方法:FAPKC0，FAPKC1，FAPKC2，FAPKC3。单钥体制密钥长度短运算速度快密钥个数一个加、解密算法相同密钥分配困难可用于数据加密和消息的认证无法满足互不相识的人之间进行私人谈话时的保密性需求双钥体制密钥长度长运算速度慢密钥个数两个加、解密算法不同密钥分配简单可以完成数字签名和实现保密通信可满足互不相识的人之间进行私人谈话时的保密性需求单钥体制和双钥体制比较作业习题1.a)、1.e)习题2习题3比较单钥体制和双钥体制