公钥密码一

第6章：公钥密码一、公钥密码的基本概念二、公钥密码RSA三、背包公钥密码四、公钥密码Rabin学习要点–了解非对称密码体制的提出背景、基本思想–了解非对称密码体制的基本应用方向–了解三种典型的公钥密码体制DH密钥交换算法RSAECC§6－1概述问题的提出：密钥管理困难–传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。如:–n=100时C(100,2)=4,995–n=5000时C(5000,2)=12,497,500陌生人间的保密通信问题数字签名的问题–传统加密算法无法实现抗抵赖的需求020000400006000080000100000120000140000用户数密钥量50040030020010050图6－1　用户数与密钥量的对应关系公钥密码的基本概念双钥密码体制(公钥密码体制)于1976年由W.Diffie和M.Hellman[1976]提出，同时R.Merkle[1978]也独立提出了这一体制。可用于保密通信，也可用于数字签字。这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。公钥体制的基本原理是陷门单向函数。注：1*.仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，δ称为陷门信息。2*.当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开密钥，记为Pk。f函数的设计者将δ保密，用作解密密钥，此时δ称为秘密密钥，记为Sk。由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk，他自然可以解出x=f-1(y)。3*.单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。是满足下列条件的函数f：(1)给定x，计算y=f(x)是容易的(2)给定y,计算x使y=f(x)是困难的(3)存在δ，已知δ时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的陷门单向函数对公钥密码体制的要求（1）参与方B容易通过计算产生一对密钥（公开密钥KUb和私有密钥KRb）。（2）在知道公开密钥和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文：C＝EKUb（M）（3）接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文：M＝DKRb（C）＝DKRb（EKUb（M））（4）敌对方即使知道公开密钥KUb，要确定私有密钥KRb在计算上是不可行的。（5）敌对方即使知道公开密钥KUb和密文C，要想恢复原来的报文M在计算上也是不可行的。（6）加密和解密函数可以以两个次序中的任何一个来使用:M＝DKRb（EKUb（M））M=EKUb(DKRb(M))单向函数举例离散对数DL。给定一大素数p（比如，p在21024数量级），p－1含另一大素数因子。称log2p为素数p的长度。{1,2,…,p-1}关于modp乘法构成了一乘群Zp*，它是一个p－1阶循环群。该循环群的生成元一共有φ(p-1)个。设一个生成元为整数g，1gp－1。设一个整数x，1xp－1。设y满足y=gxmodp。单向函数举例已知x，g，p，求y=gxmodp容易。这是因为，采用折半相乘，只需要不超过2log2p次的modp乘法运算。（实际上只需要不超过2log2x次的modp乘法运算。如x=15=11112，g15modp=(((g)2g)2g)2gmodp，要用6次modp乘法）单向函数举例若已知y，g，p，求x满足y=gxmodp，称为求解离散对数问题。记为x=loggymodp。求解离散对数问题的“最笨的方法”当然就是穷举，对每一个x∈{0,1,2,…,p－1}检验是否y=gxmodp。穷举求解法的运算次数约为(p－1)/2。许多求解离散对数问题的算法比穷举快得多，比如Shanks算法，Pohlig-Hellman算法等。最快求解法的运算次数约为数量级)))ln)(ln(ln(exp(ppO单向函数举例这个计算量称为亚指数计算量。这是什么概念呢？我们知道p的长度是log2p。看以下的不等式。当log2p≈1024时，亚指数计算量不小于2100数量级。至少在在当前的计算水平之下是不能实现的。.log~ln))ln)(lnln(lnexp())ln)(ln(lnexp(;2)))(ln(lnexp())ln)(ln(lnexp(2log2pppppppppppp单向函数举例大整数分解FAC。设有二大素数p和q。设n=pq。若已知p和q，求n=pq只需一次乘法。但若已知n，求p和q满足n=pq，则称为大整数分解问题。迄今为止，已知的各种算法的渐近运行时间约为：试除法：n/2。二次筛(QS)：椭圆曲线(EC)：数域筛(NFS)：)lnlnln(expnnO)lnlnln2(expppO))ln(ln)(ln92.1(exp(3231nnO单向函数举例背包问题。已知向量A=(a1,a2,…,aN)，ai为正整数，称其为背包向量，称每个ai为物品重量。给定向量x=(x1,x2,…,xN)，xi{0,1}，求和式（称为背包重量）S=a1x1+a2x2+…+aNxN容易，只需要不超过N－1次加法。但已知A和S，求x则非常困难，称其为背包问题，又称作子集和(Subset-Sum)问题。一般只能用穷举搜索法，有2N种可能。N大时，相当困难。单向函数举例背包问题的特例：超递增背包问题。将物品重量从小到大排列：a1，a2，a3，…，aN。称该背包问题为超递增背包问题，如果：a1a2；a1+a2a3；a1+a2+a3a4；…a1+a2+a3+…+aN-1aN。（超递增背包问题是容易解决的。）单向函数举例定理设超递增背包重量为S。如果k满足akSak+1，则ak是背包中的最大物品重量。定理的证明首先，背包中没有大于ak的物品重量。其次，背包中确有等于ak的物品重量。证明完毕。注意到，寻找k满足akSak+1只需要对比N次。单向函数举例超递增背包问题的解决方法解决方法是可行的。设背包重量S，步骤如下。（1）穷举：找k满足akSak+1。（这说明背包中的最大物品重量是ak）（2）记忆：存储这个k。（3）卸载：如果S0，则令S:=S-ak，返回（1）。如果w=0，则到（4）。（4）输出前面存储的所有的k，停止。单向函数举例格的最小向量问题(SVP)。若干个N维向量组成的集合，如果满足“集合中任何若干个向量的整数线性组合仍是集合中的一个向量。”则该结合称为一个格。关于格有以下的性质和概念。如果格中存在这样的几个向量，满足①它们（实数）线性无关；②格中的任何其它向量都能唯一地表示为这几个向量的整数线性组合。则这几个向量构成的向量组称为基。基中的向量的个数称为格的维数。格的维数总是不超过N。单向函数举例给定一个格的一组基。寻找格中的“尺寸最小”的向量（即模最小的向量），称为格的最小向量问题（shortestvectorproblem；SVP）。又称为格归约。实际上，格归约的传统算法为LLL算法，以后又有各种改进的算法。当格的维数比较大时（比如，维数大于200），当前的所有格归约算法都不是有效算法。公开密钥密码系统的分析方法强行攻击(对密钥)。公开密钥算法本身可能被攻破。可能报文攻击(对报文本身的强行攻击)。公钥密码系统的应用类型加密/解密数字签名会话密钥交换例子：简单数字签名例子续：安全数字签名二、公钥密码RSA公钥密码RSA1977年由美国麻省理工学院的三位教授RonaldRivestAdiShamirLeonardAdleman联合发明二、公钥密码RSARSA的密钥生成选择两个大的素数p和q。选择两个正整数e和d，满足：ed是(p-1)(q-1)的倍数加1。计算n=pq。Bob的公钥是（n，e），对外公布。Bob的私钥是d，自己私藏。至于（p，q），可以是Bob的另一部分私钥，也可以是对所有人（包括Bob）都保密的。二、公钥密码RSA基本RSA的加密过程：Alice欲发送明文m给Bob，其中0mn。Alice用Bob的公钥（n，e），计算密文c为c=me(modn)。基本RSA的解密过程：Bob收到密文c后，用自己的公钥（n，e）和私钥d，计算cd(modn)=med(modn)=m。（因为ed是(p-1)(q-1)的倍数加1，所以med(modn)=m。这是数论中的一个基本结论）二、公钥密码RSA基本RSA的安全性攻击者Eve已经知道了Bob的公钥是（n，e）。如果Eve还知道（p，q），则他容易知道Bob的私钥d。此时Eve只需要用推广的辗转相除法寻找d，满足ed=1(mod(p-1)(q-1))。由n的值求解（p，q）的值，即求解n的大整数分解n=pq，是一个公认的数学难题（虽然至今并没有证明），暂时还没有有效的算法。二、公钥密码RSA目前普遍使用的参数范围是2511p2512，2511q2512。如果Eve欲穷举p的所有可能值，则穷举的次数约为(2512-2511)/2=2510（次）。（因此，基本RSA似乎是足够安全的）二、公钥密码RSA基本RSA的一个安全性漏洞设攻击者Eve获得了两组明文/密文对(m1，c1)，(m2，c2)。如果Bob新截获了一个密文c，并发现：（1）c=c1c2(modn)，则c所对应的明文一定是m=m1m2(modn)；（2）c=c1/c2(modn)，则c所对应的明文一定是m=m1/m2(modn)；（3）c=c2/c1(modn)，则c所对应的明文一定是m=m2/m1(modn)。（模除运算·/·(modn)是一个数论运算）二、公钥密码RSA基本RSA的这个安全性漏洞称为可传递性。这个漏洞使得攻击者Eve对某些新的密文能够轻而易举地找到其对应明文。这个漏洞还有更深刻的隐患，比如在消息认证过程中容易产生伪造。（将在后面介绍）为了克服基本RSA的这个安全性漏洞，人们将基本RSA进行改造，引入Hash函数。（将在后面介绍）要求：若使RSA安全，p与q必为足够大的素数，使分析者没有办法在有效时间内将n分解出来。建议选择p和q大约是100位的十进制素数。模n的长度要求至少是512比特。为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1)|p-q|很大，通常p和q的长度相同；(2)p-1和q-1分别含有大素因子p1和q1(3)gcd(p1-1,q1-1)应该很小。为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定e＝216＋1，ISO/IEC9796中甚至允许取e＝3。这时加密速度一般比解密速度快10倍以上。RSA密钥的生成例：p=47,q=61,(n)=(47-1)(61-1)=2760时，SK=167是否为秘密密钥的候选者？用欧氏算法计算：gcd(2760,167)=1即可证明。QX1X2X3Y1Y2Y3－1027600116716011671－168811－1688－117791－117792－33982－339－1728171－17281719－3142319－3142－7412231用RSA算法加密与解密的过程：例：明文=“RSAALGORITHM”(1)明文用数字表示空白=00，A=01,B=02,…,Z=26(两位十进制数表示)1819010001120715180920081300(2)利用加密变换公式C=mPKmodr,即C=18191223mod2867=2756PK=1223=10011000111=210+27+26+22+21+20=1024+128+64+4+2+1C=18191223(mod2867)=18191024·1819128·181964·18194·18192·18191(mod2867)=27562756200105420669234704081815选择两个大素数p和q，通常要求每个均大于1