第四章-公钥密码体制

密码学第四章公钥密码体制密码学公钥密码的基本原理RSA算法目录4.1公钥密码体制的基本原理•对称密码体制的特点及问题–建立在置换和代换的基础上–加密能力与解密能力是捆绑在一起的–密钥更换、传递和交换需要可靠信道–如有N用户，则需要C=N(N-1)/2个密钥，n=1000时，C(1000,2)≈500000,管理困难–无法满足不相识的人之间通信的保密要求–不能实现数字签名•公钥密码体制的基本特点–基于数学中的单向陷门函数–加密能力与解密能力是分开的–密钥分发简单–需要保存的密钥量大大减少，N个用户只需要N个–可满足不相识的人之间保密通信–可以实现数字签名NP复杂性理论•P问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，就是P问题。•NP问题：在多项式的时间内可以验证的问题。•NPC问题：特殊的NP问题，所有的NP问题在多项式时间内转化为它。如果NPC问题有多项式解，那么所有的NP问题均存在多项式解。–NPC问题可以通过穷举所有解的方案来求解。–目前已经发现3000多个NPC问题。NP复杂性理论•2000年初美国克雷数学研究所的科学顾问委员会选定了七个“千年大奖问题”。而NP=P?是世界七大数学难题之首•其中，庞加莱猜想已被俄罗斯人解决NP复杂性理论•1976年，Diffle-Hellman提出将NP完全理论应用在密码学中，即将信息通过编码加密在一个NP-完全问题中，使得普通的办法破译等同于解NP-完全问题。陷门单向函数•对于函数f定义域上的任一x,计算f(x)是容易的，而对于f值域上的任一y，计算f-1(y)是不可行的，那么f称为单向函数•若进一步给定某些信息，计算f-1(y)又变得很容易，则称f是陷门单向函数•可用陷门单向函数构造密码算法，其中陷门信息为解密密钥对称钥体制与公钥体制的特征运行要求：加解密的算法相同、密钥相同加密者与解密者必须共享算法和KEY运行要求：加解密需要不同的密钥加密者与解密者的密钥应该匹配安全要求：密钥必须是保密的没有必要信息时无法解密出明文给定算法和密文无法确定密钥安全要求：私钥必须保密没有必要信息时无法解密出明文给定算法、密文和其中一个密钥无法确定另外一个密钥对称钥体制公钥体制4.2RSA算法•概述–1977年，Rivest、Shamir、Adleman提出的非对称密码体制，是基于大合数的质因子分解问题的困难性。–目前人类已能分解十进制150位的特殊类型的大合数第9个费马数，1994年4月一个小组通过Internet合作，8个月时间成功分解129位的数，大约428比特，最新的记录是1996年分解130位合数。–RSA专利于2000年9月20日到期。费马数•费马数是以数学家费马命名一组自然数，具有形式：•1640年，费马提出了一个猜想，认为所有的费马数都是素数。这一猜想对最小的5个费马数成立，于是费马宣称他找到了表示素数的公式。然而，欧拉在1732年否定了这一猜想，他给出了分解式：–F5=232+1=4294967297=641×6700417最小的8个费马数–F0=21+1=3–F1=22+1=5–F2=24+1=17–F3=28+1=257–F4=216+1=65537–F5=232+1=4294967297=641×6700417–F6=264+1=18446744073709551617=274177×67280421310721–F7=2128+1=340282366920938463463374607431768211457=59649589127497217×5704689200685129054721费马只验证了最小的5个数，就认为找到了素数的表达公式QuadraticSieve二次筛法：用于大整数因子分解GeneralizedNumberFieldSieve:数域筛法费马•法国人，业余数学家之王•解析几何、微积分、概率论、数论、光学均有重要贡献•但其一生未受过专业数学教育，数学研究也是其业余爱好•17世纪法国最伟大的数学家之一数论基础•设a∈Zn,gcd(a,n)=1,则a在Zn中有乘法逆元–Zn为小于n的所有非负整数的集合–证：首先证明a与Zn中任意两个数的模n的乘积互不相同。否则设a×b≡a×cmodn，则存在两个整数k1,k2,使得ab=k1n+r，ac=k2n+r。可得a(b-c)=(k1-k2)n，所以a是(k1-k2)n的一个因子。又因为gcd(a,n)=1，所以a一定是(k1-k2)的因子。设(k1-k2)=k3a，所以a(b-c)=k3an，即b-c=k3n，与b和c属于Zn相矛盾。–所以a×Zn=Zn，由于1∈Zn,所以存在一个x，使得a×x=1modn，即x为a的逆元，记为x=a-1费马(Fermat)定理•若p是素数，a是正整数，且gcd(a,p)=1，则ap-1≡1modp•证明：考虑集合{1,2,…,p-1},对每个数乘以a,得到集合{amodp,2amodp,…,(p-1)amodp},对于p,后者两两不同且都在1与p-1之间,因此两个集合相同,于是:(p-1)!=12…(p-1)[(amodp)(2amodp)…((p-1)amodp)]modp[a2a…(p-1)a]modp[ap-1(p-1)!]modp注意到(p-1)!与p互素,因此定理成立.•推论:p素数,a是任意整数,则:apamodp欧拉数•Euler数(n)定义为小于n且与n互素的正整数个数•p是素数,(p)=p-1•若gcd(m,n)=1,则(mn)=(m)(n),特别地,若pq且都是素数,(pq)=(p-1)(q-1)•例21=37，则(21)=26=12•(21)：2，4，5，8，10，11，13，14，16，17，19，20•Euler定理:若a与n为互素的正整数,则:•a(n)1modn欧拉定理•证明：•R={x1,x2,…,x(n)}为所有小于n且与n互素的正整数,考虑集合•S={(ax1modn),(ax2modn),…,(ax(n)modn)}•(aximodn)与n互素•(aximodn)两两不等:•(aximodn)=(axjmodn)ximodn=xjmodn•S有(n)个元素•故S也是所有小于n且与n互素的正整数,因此S=R,从而xi=(aximodn)((axi))modn•(a(n)xi)modn•注意到xi与n互素,从而得到结论.RSA密码体制基本原理•随机选择两个秘密大质数p和q；•计算公开模数n=p*q；•计算秘密的欧拉指数函数φ(n)=(p-1)(q-1)•选择一个与φ(n)互素的数K，作为e或d；•用Euclid算法计算模φ(n)的K的乘法逆元素，即依edmodφ(n)=1,求d或e；•加密：C=Memodn•解密：M=Cdmodn=(Memodn)dmodn=M这里，φ(n)为EulerTotientFunction,欧拉数，即集合(1,2,...,n-1)中与n互素的数的个数。RSA原理解释•当M与n互素时，由Euler定理得–Mkφ(n)+1=Mmodn•当M与n不互素时，由于n=p.q，则M或者为p的倍数或者为q的倍数，设M为p的倍数(M=cp)，那么M与q互素,否则M=rp.wq=rwnn,这与RSA的假设不符。•那么gcd(M,q)=1，则Mφ(q)=1modq•推出Mkφ(q).φ(p)=1modq,即Mkφ(n)=1modq,推出：Mkφ(n)=1+rq,两边同乘以M，•Mkφ(n)+1=M+rcpq=M+rcn,所以•Mkφ(n)+1modn=MRSA算法举例（1）p=53，q=61，n=pq=3233，φ(n)＝52x60=3120令d=791，则e=71令m=RENAISSANCE即m=170413000818180013020426170471mod3233=3106，…，C=310601000931269119842927RSA算法举例（2）4.2.2平方-乘算法•1722mod21•22=（10110）2–1*17mod21=17–172mod21=16–162*17mod21=5–52*17mod21=5–52mod21=4•1722mod21=4密钥的选取•RSA的安全性在于p,q两个参数的保密性，为此，p,q应该是两个大素数。•费马没有解决素数的确定问题。目前的寻找素数的办法只能是通过素性检测法，即选找到一个数，然后判断其是不是素数。–思路：先找一个奇数，然后被小素数除，若被除尽，则+2。然后再用miller-rabin算法验证。许多次使用miller-rabin算法验证通过（其中a是随机数）。•2002年以前，素数判定是NP问题。2002年后，3位印度数学家给出了新的算法AKS，使得该问题变为P问题。RSA算法的安全性•大的密钥参数可以确保较高的安全性，但是这样效率低，因此需要在安全性和效率之间有个折中。•当p,q泄漏后，则可以计算ø(n)=(p-1)(q-1)，再根据公钥参数e就可以计算私钥参数d=e-1modø(n)了。•当解密参数d泄漏后，则会危及模n的安全性（会被分解），因此需重新选择新的p,q计算n公钥的保密体系公钥的鉴别体系密码学