公钥密码一课件

第6章：公钥密码一、公钥密码的基本概念二、公钥密码RSA三、背包公钥密码四、公钥密码Rabin第6章：公钥密码一、公钥密码的基本概念1学习要点了解非对称密码体制的提出背景、基本思想了解非对称密码体制的基本应用方向了解三种典型的公钥密码体制

DH密钥交换算法RSAECC学习要点2§6－1概述问题的提出：

密钥管理困难传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。如:n=100时C(100,2)=4,995n=5000时C(5000,2)=12,497,500陌生人间的保密通信问题

数字签名的问题传统加密算法无法实现抗抵赖的需求§6－1概述问题的提出：3公钥密码一课件4公钥密码的基本概念双钥密码体制(公钥密码体制)于1976年由W.Diffie和M.Hellman[1976]提出，同时R.Merkle[1978]也独立提出了这一体制。可用于保密通信，也可用于数字签字。这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。公钥体制的基本原理是陷门单向函数。公钥密码的基本概念双钥密码体制(公钥密码体制)于1976年5公钥密码一课件6注：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*.仅满足(1)、(2)两条的称为单向函数；第(3)7公钥密码一课件8对公钥密码体制的要求（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))对公钥密码体制的要求（1）参与方B容易通过计算产生一对密钥（9单向函数举例离散对数DL。给定一大素数p（比如，p在21024数量级），p－1含另一大素数因子。称log2p为素数p的长度。{1,

2,…,p-1}关于modp乘法构成了一乘群Zp*，它是一个p－1阶循环群。该循环群的生成元一共有φ(p-1)个。设一个生成元为整数g，1<g<p－1。设一个整数x，1<x<p－1。设y满足y=gxmodp。单向函数举例离散对数DL。给定一大素数p（比如，p在21010单向函数举例已知x，g，p，求y=gxmodp容易。这是因为，采用折半相乘，只需要不超过2log2p次的modp乘法运算。（实际上只需要不超过2log2x次的modp乘法运算。如x=15=11112，g15modp=(((g)2g)2g)2gmodp，要用6次modp乘法）单向函数举例已知x，g，p，求y=gxmodp容易。11单向函数举例若已知y，g，p，求x满足y=gxmodp，称为求解离散对数问题。记为x=loggymodp。求解离散对数问题的“最笨的方法”当然就是穷举，对每一个x∈{0,1,2,…,p－1}检验是否y=gxmodp。穷举求解法的运算次数约为(p－1)/2。许多求解离散对数问题的算法比穷举快得多，比如Shanks算法，Pohlig-Hellman算法等。最快求解法的运算次数约为数量级单向函数举例若已知y，g，p，求x满足y=gxmodp，称为12单向函数举例这个计算量称为亚指数计算量。这是什么概念呢？我们知道p的长度是log2p。看以下的不等式。当log2p≈1024时，亚指数计算量不小于2100数量级。至少在在当前的计算水平之下是不能实现的。单向函数举例这个计算量称为亚指数计算量。这是什么概念呢？我们13单向函数举例大整数分解FAC。设有二大素数p和q。设n=pq。若已知p和q，求n=pq只需一次乘法。但若已知n，求p和q满足n=pq，则称为大整数分解问题。迄今为止，已知的各种算法的渐近运行时间约为：试除法：n/2。二次筛(QS)：椭圆曲线(EC)：数域筛(NFS)：单向函数举例大整数分解FAC。设有二大素数p和q。设n=pq14单向函数举例背包问题。已知向量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大时，相当困难。单向函数举例背包问题。已知向量15单向函数举例背包问题的特例：超递增背包问题。将物品重量从小到大排列：a1，a2，a3，…，aN。称该背包问题为超递增背包问题，如果：a1<a2；a1+a2<a3；a1+a2+a3<a4；…a1+a2+a3+…+aN-1<aN。（超递增背包问题是容易解决的。）单向函数举例背包问题的特例：超递增背包问题。将物品重量从小到16（4个数的计算使用孙子定理（中国剩余定理）。执行概率素数判定测试,如果n未测试通过,则拒绝数值n,转向步骤1Alice用Bob的公钥n，计算：（4个数的计算使用孙子定理（中国剩余定理）。格的维数总是不超过N。务必要先签名后加密!x=15=11112，(3)K为有限密钥空间，是一些可能密钥的有限集合；Ua2>Ua1>M>Ua2(modM)=b2，了解三种典型的公钥密码体制C=18191223(mod2867)那么，4个不同的根怎样计算呢？如果仅仅知道n，而不知道分解式n=pq，则无法计算mp和mq，因而无法计算这4个不同的根。第(3)条称为陷门性，δ称为陷门信息。随机选一个奇数n(伪随机数发生器)四、公钥密码Rabin（因为ed是(p-1)(q-1)的倍数加1，所以med(modn)=m。（2）c=c1/c2(modn)，则c所对应的明文一定是m=m1/m2(modn)；如何判定一个给定的整数是素数？分析者没有办法在有效时间内将n分解出来。基本RSA的加密过程：Alice欲发送明文m给Bob，其中0<m<n。单向函数举例定理设超递增背包重量为S。如果k满足ak<S<ak+1，则ak是背包中的最大物品重量。定理的证明

首先，背包中没有大于ak的物品重量。其次，背包中确有等于ak的物品重量。证明完毕。注意到，寻找k满足ak<S<ak+1只需要对比N次。（4个数的计算使用孙子定理（中国剩余定理）。单向函数举例定理17单向函数举例超递增背包问题的解决方法解决方法是可行的。设背包重量S，步骤如下。（1）穷举：找k满足ak<S<ak+1。（这说明背包中的最大物品重量是ak）（2）记忆：存储这个k。（3）卸载：如果S>0，则令S:=S-ak，返回（1）。如果w=0，则到（4）。（4）输出前面存储的所有的k，停止。单向函数举例超递增背包问题的解决方法18单向函数举例格的最小向量问题(SVP)。若干个N维向量组成的集合，如果满足“集合中任何若干个向量的整数线性组合仍是集合中的一个向量。”则该结合称为一个格。关于格有以下的性质和概念。如果格中存在这样的几个向量，满足①它们（实数）线性无关；②格中的任何其它向量都能唯一地表示为这几个向量的整数线性组合。则这几个向量构成的向量组称为基。基中的向量的个数称为格的维数。格的维数总是不超过N。单向函数举例格的最小向量问题(SVP)。19单向函数举例给定一个格的一组基。寻找格中的“尺寸最小”的向量（即模最小的向量），称为格的最小向量问题（shortestvectorproblem；SVP）。又称为格归约。实际上，格归约的传统算法为LLL算法，以后又有各种改进的算法。当格的维数比较大时（比如，维数大于200），当前的所有格归约算法都不是有效算法。单向函数举例给定一个格的一组基。寻找格中的“尺寸最小”的向量20公开密钥密码系统的分析方法强行攻击(对密钥)。公开密钥算法本身可能被攻破。可能报文攻击(对报文本身的强行攻击)。公开密钥密码系统的分析方法强行攻击(对密钥)。21公钥密码系统的应用类型加密/解密数字签名会话密钥交换公钥密码系统的应用类型加密/解密22例子：简单数字签名例子：简单数字签名23例子续：安全数字签名例子续：安全数字签名24公钥密码一课件25公钥密码一课件26容易，只需要不超过N－1次加法。随机选择a<n,计算s次，n=5000时C(5000,2)=12,497,500陌生人间的保密通信问题d(d×a)modn找到一个e满足e×d＝1(modz)。TRUE:n一定不是素数n=5000时C(5000,2)=12,497,500基本RSA的这个安全性漏洞称为可传递性。如果每次都返回FALSE，doc2×c(2)给定y,计算x使y=f(x)是困难的单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。格归约的传统算法为LLL算法，以后又有各种改进的算法。在确定的范围内，加密和解密函数是互逆的。(3)K为有限密钥空间，是一些可能密钥的有限集合；格的维数总是不超过N。m(2,1)(modp)=p-mp；格归约的传统算法为LLL算法，以后又有各种改进的算法。执行概率素数判定测试,如果n未测试通过,则拒绝数值n,转向步骤1二、公钥密码RSA公钥密码RSA1977年由美国麻省理工学院的三位教授

RonaldRivestAdiShamirLeonardAdleman联合发明容易，只需要不超过N－1次加法。二、公钥密码RSA公钥密码R27二、公钥密码RSARSA的密钥生成选择两个大的素数p和q。选择两个正整数e和d，满足：ed是(p-1)(q-1)的倍数加1。计算n=pq。Bob的公钥是（n，e），对外公布。Bob的私钥是d，自己私藏。至于（p，q

），可以是Bob的另一部分私钥，也可以是对所有人（包括Bob）都保密的。二、公钥密码RSARSA的密钥生成28二、公钥密码RSA基本RSA的加密过程：Alice欲发送明文m给Bob，其中0<m<n

。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的加密过程：Alice欲发送明文29二、公钥密码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基本RSA的安全性30二、公钥密码RSA目前普遍使用的参数范围是2511<p<2512，2511<q<2512。如果Eve欲穷举p的所有可能值，则穷举的次数约为(2512-2511)/2=2510（次）。（因此，基本RSA似乎是足够安全的）二、公钥密码RSA目前普遍使用的参数范围是31二、公钥密码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的一个安全性漏洞32二、公钥密码RSA基本RSA的这个安全性漏洞称为可传递性。这个漏洞使得攻击者Eve对某些新的密文能够轻而易举地找到其对应明文。这个漏洞还有更深刻的隐患，比如在消息认证过程中容易产生伪造。（将在后面介绍）为了克服基本RSA的这个安全性漏洞，人们将基本RSA进行改造，引入Hash函数。（将在后面介绍）二、公钥密码RSA基本RSA的这个安全性漏洞称为可传递性。33要求：若使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与q必为足够大的素数，使34RSA密钥的生成RSA密钥的生成35公钥密码一课件36=[a(2i)modn]n=5000时C(5000,2)=12,497,500这是因为，采用折半相乘，只需要不超过2log2p次的modp乘法运算。(2)给定y,计算x使y=f(x)是困难的Bob的公钥是（n，e），对外公布。Ua1>M>Ua1(modM)=b1，设y满足y=gxmodp。定理设超递增背包重量为S。当log2p≈1024时，亚指数计算量不小于2100数量级。在确定的范围内，加密和解密函数是互逆的。务必要先签名后加密!如果n已通过足够的测试,则接受n,否则转向步骤2;WITNESS(a,n)判定n是否为素数，a是某个小于n的整数m(2,2)(modq)=q-mq。至于（p，q），可以是Bob的另一部分私钥，也可以是对所有人（包括Bob）都保密的。例：明文=“RSAALGORITHM”一个根的(modp)、(modq)值是p-mp、q-mq。m的二进制表示为bkbk-1…b0,则=18191024·1819128·181964·18194·18192·18191(mod2867)传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。例：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=[a(2i)modn]例：p=47,q=637用RSA算法加密与解密的过程：例：明文=“RSAALGORITHM”(1)明文用数字表示空白=00，A=01,B=02,…,Z=26(两位十进制数表示)

1819010001120715180920081300(2)利用加密变换公式C=mPKmodr,即C=18191223mod2867=2756 PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223(mod2867) =18191024·1819128·181964·18194·18192·18191(mod2867) =27562756200105420669234704081815用RSA算法加密与解密的过程：2756200105438选择两个大素数p和q，通常要求每个均大于10100。计算n＝pｘq和z＝(p－1)(q－1)。选择一与z互素的数、令其为d。找到一个e满足e×d＝1(modz)。选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0<m<n。加密P时，计算C＝Pe(modn)，解密C时计算P＝Cd(modn)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开(e,n)，为实现解密需要(d,n)。RSA算法归纳选择两个大素数p和q，通常要求每个均大于10100。RSA算39如何计算abmodn？如何判定一个给定的整数是素数？如何找到足够大的素数p和q?问题……如何计算abmodn？问题……40要点1：(axb)modn=[(amodn)x(bmodn)]modn]

要点2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的问题：am m的二进制表示为bkbk-1…b0,

则计算ammodnammodn=[

a(2i)]modn =[a(2i)modn]bi0bi0如何计算abmodn？要点1：(axb)modn=[(amod41快速取模指数算法计算abmodn

c0;d1forikdownto0doc2×cd(d×d)modnifbi=1thencc+1d(d×a)modnreturnd快速取模指数算法计算abmodnc0;d42快速取模指数算法：例子i9876543210bi1000110000c=01248173570140280560d=17491575261602412981666717560mod561=1快速取模指数算法：例子i9876543210bi10001143MillerandRabin,WITNESS算法

WITNESS(a,n)判定n是否为素数，a是某个小于n的整数1.令bkbk-1…b0

为(n-1)的二进制表示，2.d13.forikdownto04. doxd5. d(dd)modn6. ifd=1andx1andxn-17. thenreturnTRUE8. ifbi=19. thend(da)modn10.ifd111.thenreturnTRUE12.returnFALSE

返回值：TRUE:n一定不是素数FALSE:n可能是素数应用：随机选择a<n,计算s次，如果每次都返回FALSE，则这时n是素数的概率为

(1-1/2s)如何判定一个给定的整数是素数？MillerandRabin,WITNESS算法1.441.随机选一个奇数n(伪随机数发生器)2.随机选择一个整数a<n3.执行概率素数判定测试,如果n未测试通过,则拒绝数值n,转向步骤14.如果n已通过足够的测试,则接受n,否则转向步骤2;说明：①随机选取大约用

ln(N)/2的次数，如ln(2200)/2=70②好在生成密钥对时才用到，慢一点还可忍受。

③确定素数p和q以后，只需选取e,满足gcd(e,(n))=1,计算d=e-1mod(n)（扩展的欧拉算法）如何找到足够大的素数p和q?如何找到足够大的素数p和q?45p和q在长度上应仅差几个数位，即p和q应是1075

到10100（p-1）和（q-1）都应包含一个较大的素数因子gcd(p-1,q-1)应比较小如果e<n且d<n1/4,则d可以很容易确定建议－p和q在长度上应仅差几个数位，即p和q应是1075到10146（3）c=c2/c1(modn)，则c所对应的明文一定是m=m2/m1(modn)。如果n已通过足够的测试,则接受n,否则转向步骤2;f函数的设计者将δ保密，用作解密密钥，此时δ称为秘密密钥，记为Sk。至少在在当前的计算水平之下是不能实现的。至于（p，q），可以是Bob的另一部分私钥，也可以是对所有人（包括Bob）都保密的。这个漏洞还有更深刻的隐患，比如在消息认证过程中容易产生伪造。p,q,d为保密的（私钥）d(d×a)modn（3）c=c2/c1(modn)，则c所对应的明文一定是m=m2/m1(modn)。③确定素数p和q以后，只需选取e,满足gcd(e,(n))=1,计算d=e-1mod(n)（扩展的欧拉算法）找到一个e满足e×d＝1(modz)。例：p=47,q=61,(n)=(47-1)(61-1)=2760时，SK=167是否为秘密密钥的候选者？

用欧氏算法计算：gcd(2760,167)=1即可证明。由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；使用公钥{b1，b2，b3，…，bn}计算密文c：c=m1b1+m2b2+m3b3+…+mnbn。0<m(2,1)<n；分析者没有办法在有效时间内将n分解出来。(2)给定y,计算x使y=f(x)是困难的a1+a2+a3+…+aN-1<aN。计算n＝pｘq和z＝(p－1)(q－1)。四、公钥密码Rabin数字签名方案：一个签名方案是由签署算法与验证算法两部分构成。可由五元关系组（M,A,K,S,V）来描述：(1)M是由一切可能消息所构成的有限集合；(2)A是一切可能的签名的有限集合；(3)K为有限密钥空间，是一些可能密钥的有限集合；(4)任意k∈K，有签署算法Sigk∈S且有对应的验证算法Verk∈V,对每一个Sigk和Verk满足条件：任意一个签名：Ver(x,y)=｛

RSA的数字签名应用真若y=sig(x)假若ySig(x)（3）c=c2/c1(modn)，则c所对应的明文一定是47选取整数n=pq,

M=A=Zn定义密钥集合K={(n,e,p,q,d)}|n=pq,d*e1(mod(n))}n和e为公钥；p,q,d为保密的（私钥）对x∈M,Bob要对x签名，取k∈K：Sigk(x)xd(modn)y(modn)

Verk(x,y)=真xye(modn)RSA的数字签名方案选取整数n=pq,M=A=ZnRSA的数字签名方案48假设Alice想把签了名的消息加密送给Bob：对明文x，Alice计算对x的签名y=SigAlice(x)，然后用Bob的公钥加密函数eBob,算出z=eBob(x,y),Alice将z传给BobBob收到z后，先解密：dBob(z)=dBobeBob(x,y)=(x,y)后检验：

VerAlice(x,y)=真？问题：若Alice首先对消息x进行加密,z=eBob(x),然后再签名，y=SigAlice(eBob(x)),结果如何呢？Alice将（z,y)传给Bob，Bob先将z解密，获取x;然后用VerAlice检验关于x的加密签名y一个潜在问题：如果Oscar获得了这对（z,y)，他能用自己的签名来替代Alice的签名

y=SigOscar(eBob(x))签名消息的加密传递问题务必要先签名后加密!

假设Alice想把签了名的消息加密送给Bob：对明文x，Al49公钥密码一课件50公钥密码一课件51公钥密码一课件52公钥密码一课件53DES和RSA性能比较（同等强度）DES和RSA性能比较（同等强度）54三、背包公钥密码背包公钥密码早已经被攻破，然而背包公钥密码的设计思想是公认的人类设计思想精华，其设计和攻击已成为公钥密码攻防的一个样板。三、背包公钥密码背包公钥密码早已经被攻破，然而背包公钥密码的55三、背包公钥密码背包公钥密码的密钥生成取n个具有超递增性的物品重量：a1，a2，a3，…，an。取正整数M，U，满足M>a1+a2+a3+…+an；M>U；Ua1>M；M与U互素，因此可以用辗转相除法计算出U关于(modM)的逆元U-1。三、背包公钥密码背包公钥密码的密钥生成56计算n＝pｘq和z＝(p－1)(q－1)。C=18191223(mod2867)7560mod561=1C=18191223(mod2867)选择两个大的素数p和q，要求p和q都是4的倍数加3。由n的值求解（p，q）的值，即求解n的大整数分解n=pq，是一个公认的数学难题（虽然至今并没有证明），暂时还没有有效的算法。定义密钥集合K={(n,e,p,q,d)}|n=pq,d*e1(mod(n))}一个根的(modp)、(modq)值是p-mp、q-mq。了解非对称密码体制的基本应用方向数字签名方案：一个签名方案是由签署算法与验证算法两部分构成。a1+a2+a3+…+aN-1<aN。当格的维数比较大时（比如，维数大于200），当前的所有格归约算法都不是有效算法。如果每次都返回FALSE，最快求解法的运算次数约为数量级计算n＝pｘq和z＝(p－1)(q－1)。=U-1(m1b1+m2b2+m3b3+…+mnbn)(modM)（4个数的计算使用孙子定理（中国剩余定理）。传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。其次，背包中确有等于ak的物品重量。这个漏洞还有更深刻的隐患，比如在消息认证过程中容易产生伪造。三、背包公钥密码计算：b1=Ua1(modM)，b2=Ua2(modM)

，b3=Ua3(modM)

，…，bn=Uan(modM)

。（此时a1=U-1b1(modM)，a2=U-1b2(modM)，a3=U-1b3(modM)，…，an=U-1bn(modM)

。）计算n＝pｘq和z＝(p－1)(q－1)。三、背包公钥密码计57三、背包公钥密码b1，b2，b3，…，bn是n个物品重量。因为Ua1>M>Ua1(modM)=b1，Ua2>Ua1>M>Ua2(modM)=b2，Ua3>Ua1>M>Ua3(modM)=b3，…，Uan>Ua1>M>Uan(modM)=bn，所以通常b1，b2，b3，…，bn不具有超递增性。{b1，b2，b3，…，bn}是公钥。{a1，a2，a3，…，an}

，M，U都是私钥。三、背包公钥密码b1，b2，b3，…，bn是n个物品重量。因58三、背包公钥密码背包公钥密码的加密设明文m=(m1,m2,m3,…,mn)是长度为n的比特串。使用公钥{b1，b2，b3，…，bn}计算密文c

：c=m1b1+m2b2+m3b3+…+mnbn。密文c是一个正整数。（密文c是背包重量，由n个物品重量b1，b2，b3，…，bn中的某些物品重量相加而成。若截获了密文c，又知道n个物品重量b1，b2，b3，…，bn，求解明文m就是背包问题。）三、背包公钥密码背包公钥密码的加密59三、背包公钥密码背包公钥密码的解密使用私钥{a1，a2，a3，…，an}

，M，U，计算变换课文C：C=U-1c(modM)=U-1(m1b1+m2b2+m3b3+…+mnbn

)(modM)=m1a1+m2a2+m3a3+…+mnan(modM)=m1a1+m2a2+m3a3+…+mnan。根据定理中的方法，容易解出明文m。三、背包公钥密码背包公钥密码的解密60三、背包公钥密码变换课文C是背包重量，由n个物品重量a1，a2，a3，…，an中的某些物品重量相加而成。若已知变换课文C，又知道n个物品重量a1，a2，a3，…，an，求解明文m就是超递增背包问题。三、背包公钥密码变换课文C是背包重量，由n个物品重量a1，a61四、公钥密码RabinRabin的密钥生成选择两个大的素数p和q，要求p和q都是4的倍数加3。计算n=pq。Bob的公钥是n，对外公布。Bob的私钥是（p，q），自己私藏。四、公钥密码RabinRabin的密钥生成62四、公钥密码RabinRabin的加密过程Alice欲发送明文m给Bob，其中0<m<n

。Alice用Bob的公钥n，计算：c=m2(modn)。c为密文。四、公钥密码RabinRabin的加密过程63四、公钥密码RabinRabin的解密过程Bob收到密文c后，用自己的私钥（p，q）计算四、公钥密码RabinRabin的解密过程64四、公钥密码Rabin计算4个数m(1,1)，m(1,2)，m(2,1)，m(2,2)，满足：0<m(1,1)<n；0<m(1,2)<n；0<m(2,1)<n；0<m(2,2)<n；m(1,1)(modp)=mp；m(1,1)(modq)=mq；m(1,2)(modp)=mp；m(1,2)(modq)=q-mq；m(2,1)(modp)=p-mp；m(2,1)(modq)=mq；m(2,2)(modp)=p-mp；m(2,2)(modq)=q-mq。四、公钥密码Rabin计算4个数m(1,1)，m(1,2)65四、公钥密码Rabin（4个数的计算使用孙子定理（中国剩余定理）。）于是，真正的明文m一定就是4个数m(1,1)，m(1,2)，m(2,1)，m(2,2)之中的一个。观察4个数，排除那些没有意义的“乱码课文”。哪个是有意义的课文，哪个就是真正的明文m。解密完毕。四、公钥密码Rabin（4个数的计算使用孙子定理（中国剩余定66四、公钥密码RabinRabin的解密原理因为n=pq是两个不同的素数的乘积，所以，关于未知数x的二次方程c=x2(modn)恰好有4个不同的根x，分别有以下形状：一个根的(modp)、(modq)值是mp、mq；一个根的(modp)、(modq)值是mp、q-mq；一个根的(modp)、(modq)值是p-mp、mq；一个根的(modp)、(modq)值是p-mp、q-mq。四、公钥密码RabinRabin的解密原理67四、公钥密码Rabin4个根中有一个是明文m。如果把(modp)、(modq)值为mp、mq的根叫做m’，则(modp)、(modq)值为p-mp、q-mq的根就是n-m’。另外两个根的和也等于n。即如果把一个叫做m’’，则另一个就是n-m’’。那么，4个不同的根怎样计算呢？如果仅仅知道n，而不知道分解式n=pq，则无法计算mp和mq，因而无法计算这4个不同的根。四、公钥密码Rabin4个根中有一个是明文m。68四、公钥密码Rabin如果知道了n的分解式n=pq，则能够计算mp和mq。再由mp和mq计算4个根，使用的是著名的孙子定理（中国剩余定理）（略）。最后，要判断哪一个根是真正的明文。一般，真正的明文都具有语言含义，而其它的根则是没有语言含义的“乱码课文”。当然也有例外，比如当明文是一副图象的编码时，明文也是没有语言含义的“乱码课文”。四、公钥密码Rabin如果知道了n的分解式n=pq，则能够计69四、公钥密码RabinRabin的安全性原理攻击者Eve截获了密文c。Eve还知道Bob的公钥n，也知道明文m满足方程c=m2(modn)。但是他不知道n的分解式n=pq，无法计算mp和mq，进一步无法计算4个根。求n的分解式n=pq是大数分解问题。四、公钥密码RabinRabin的安全性原理70如果每次都返回FALSE，LeonardAdleman(3)K为有限密钥空间，是一些可能密钥的有限集合；设明文m=(m1,m2,m3,…,mn)是长度为n的比特串。(3)K为有限密钥空间，是一些可能密钥的有限集合；a1+a2+a3<a4；容易，只需要不超过N－1次加法。四、公钥密码RabinBob的公钥是n，对外公布。p,q,d为保密的（私钥）使用公钥{b1，b2，b3，…，bn}计算密文c：c=m1b1+m2b2+m3b3+…+mnbn。n=100时C(100,2)=4,995于是，真正的明文m一定就是4个数(2)p-1和q-1分别含有大素因子p1和q1背包公钥密码的密钥生成若干个N维向量组成的集合，如果满足一般，真正的明文都具有语言含义，而其它的根则是没有语言含义的“乱码课文”。许多求解离散对数问题的算法比穷举快得多，比如Shanks算法，Pohlig-Hellman算法等。变换课文C是背包重量，由n个物品重量a1，a2，a3，…，an中的某些物品重量相加而成。m(1,1)(modq)=mq；四、公钥密码RabinRSA与Rabin比较比较项目RSARabin公钥(n,e)n私钥d(p,q)加密算法c=me(modn)c=m2(modn)解密算法m=cd(modn)若干步安全基础大数分解问题的困难性大数分解问题的困难性如果每次都返回FALSE，四、公钥密码RabinRSA与Ra71第6章：公钥密码一、公钥密码的基本概念二、公钥密码RSA三、背包公钥密码四、公钥密码Rabin第6章：公钥密码一、公钥密码的基本概念72学习要点了解非对称密码体制的提出背景、基本思想了解非对称密码体制的基本应用方向了解三种典型的公钥密码体制

DH密钥交换算法RSAECC学习要点73§6－1概述问题的提出：

密钥管理困难传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。如:n=100时C(100,2)=4,995n=5000时C(5000,2)=12,497,500陌生人间的保密通信问题

数字签名的问题传统加密算法无法实现抗抵赖的需求§6－1概述问题的提出：74公钥密码一课件75公钥密码的基本概念双钥密码体制(公钥密码体制)于1976年由W.Diffie和M.Hellman[1976]提出，同时R.Merkle[1978]也独立提出了这一体制。可用于保密通信，也可用于数字签字。这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。公钥体制的基本原理是陷门单向函数。公钥密码的基本概念双钥密码体制(公钥密码体制)于1976年76公钥密码一课件77注：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*.仅满足(1)、(2)两条的称为单向函数；第(3)78公钥密码一课件79对公钥密码体制的要求（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))对公钥密码体制的要求（1）参与方B容易通过计算产生一对密钥（80单向函数举例离散对数DL。给定一大素数p（比如，p在21024数量级），p－1含另一大素数因子。称log2p为素数p的长度。{1,

2,…,p-1}关于modp乘法构成了一乘群Zp*，它是一个p－1阶循环群。该循环群的生成元一共有φ(p-1)个。设一个生成元为整数g，1<g<p－1。设一个整数x，1<x<p－1。设y满足y=gxmodp。单向函数举例离散对数DL。给定一大素数p（比如，p在21081单向函数举例已知x，g，p，求y=gxmodp容易。这是因为，采用折半相乘，只需要不超过2log2p次的modp乘法运算。（实际上只需要不超过2log2x次的modp乘法运算。如x=15=11112，g15modp=(((g)2g)2g)2gmodp，要用6次modp乘法）单向函数举例已知x，g，p，求y=gxmodp容易。82单向函数举例若已知y，g，p，求x满足y=gxmodp，称为求解离散对数问题。记为x=loggymodp。求解离散对数问题的“最笨的方法”当然就是穷举，对每一个x∈{0,1,2,…,p－1}检验是否y=gxmodp。穷举求解法的运算次数约为(p－1)/2。许多求解离散对数问题的算法比穷举快得多，比如Shanks算法，Pohlig-Hellman算法等。最快求解法的运算次数约为数量级单向函数举例若已知y，g，p，求x满足y=gxmodp，称为83单向函数举例这个计算量称为亚指数计算量。这是什么概念呢？我们知道p的长度是log2p。看以下的不等式。当log2p≈1024时，亚指数计算量不小于2100数量级。至少在在当前的计算水平之下是不能实现的。单向函数举例这个计算量称为亚指数计算量。这是什么概念呢？我们84单向函数举例大整数分解FAC。设有二大素数p和q。设n=pq。若已知p和q，求n=pq只需一次乘法。但若已知n，求p和q满足n=pq，则称为大整数分解问题。迄今为止，已知的各种算法的渐近运行时间约为：试除法：n/2。二次筛(QS)：椭圆曲线(EC)：数域筛(NFS)：单向函数举例大整数分解FAC。设有二大素数p和q。设n=pq85单向函数举例背包问题。已知向量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大时，相当困难。单向函数举例背包问题。已知向量86单向函数举例背包问题的特例：超递增背包问题。将物品重量从小到大排列：a1，a2，a3，…，aN。称该背包问题为超递增背包问题，如果：a1<a2；a1+a2<a3；a1+a2+a3<a4；…a1+a2+a3+…+aN-1<aN。（超递增背包问题是容易解决的。）单向函数举例背包问题的特例：超递增背包问题。将物品重量从小到87（4个数的计算使用孙子定理（中国剩余定理）。执行概率素数判定测试,如果n未测试通过,则拒绝数值n,转向步骤1Alice用Bob的公钥n，计算：（4个数的计算使用孙子定理（中国剩余定理）。格的维数总是不超过N。务必要先签名后加密!x=15=11112，(3)K为有限密钥空间，是一些可能密钥的有限集合；Ua2>Ua1>M>Ua2(modM)=b2，了解三种典型的公钥密码体制C=18191223(mod2867)那么，4个不同的根怎样计算呢？如果仅仅知道n，而不知道分解式n=pq，则无法计算mp和mq，因而无法计算这4个不同的根。第(3)条称为陷门性，δ称为陷门信息。随机选一个奇数n(伪随机数发生器)四、公钥密码Rabin（因为ed是(p-1)(q-1)的倍数加1，所以med(modn)=m。（2）c=c1/c2(modn)，则c所对应的明文一定是m=m1/m2(modn)；如何判定一个给定的整数是素数？分析者没有办法在有效时间内将n分解出来。基本RSA的加密过程：Alice欲发送明文m给Bob，其中0<m<n。单向函数举例定理设超递增背包重量为S。如果k满足ak<S<ak+1，则ak是背包中的最大物品重量。定理的证明

首先，背包中没有大于ak的物品重量。其次，背包中确有等于ak的物品重量。证明完毕。注意到，寻找k满足ak<S<ak+1只需要对比N次。（4个数的计算使用孙子定理（中国剩余定理）。单向函数举例定理88单向函数举例超递增背包问题的解决方法解决方法是可行的。设背包重量S，步骤如下。（1）穷举：找k满足ak<S<ak+1。（这说明背包中的最大物品重量是ak）（2）记忆：存储这个k。（3）卸载：如果S>0，则令S:=S-ak，返回（1）。如果w=0，则到（4）。（4）输出前面存储的所有的k，停止。单向函数举例超递增背包问题的解决方法89单向函数举例格的最小向量问题(SVP)。若干个N维向量组成的集合，如果满足“集合中任何若干个向量的整数线性组合仍是集合中的一个向量。”则该结合称为一个格。关于格有以下的性质和概念。如果格中存在这样的几个向量，满足①它们（实数）线性无关；②格中的任何其它向量都能唯一地表示为这几个向量的整数线性组合。则这几个向量构成的向量组称为基。基中的向量的个数称为格的维数。格的维数总是不超过N。单向函数举例格的最小向量问题(SVP)。90单向函数举例给定一个格的一组基。寻找格中的“尺寸最小”的向量（即模最小的向量），称为格的最小向量问题（shortestvectorproblem；SVP）。又称为格归约。实际上，格归约的传统算法为LLL算法，以后又有各种改进的算法。当格的维数比较大时（比如，维数大于200），当前的所有格归约算法都不是有效算法。单向函数举例给定一个格的一组基。寻找格中的“尺寸最小”的向量91公开密钥密码系统的分析方法强行攻击(对密钥)。公开密钥算法本身可能被攻破。可能报文攻击(对报文本身的强行攻击)。公开密钥密码系统的分析方法强行攻击(对密钥)。92公钥密码系统的应用类型加密/解密数字签名会话密钥交换公钥密码系统的应用类型加密/解密93例子：简单数字签名例子：简单数字签名94例子续：安全数字签名例子续：安全数字签名95公钥密码一课件96公钥密码一课件97容易，只需要不超过N－1次加法。随机选择a<n,计算s次，n=5000时C(5000,2)=12,497,500陌生人间的保密通信问题d(d×a)modn找到一个e满足e×d＝1(modz)。TRUE:n一定不是素数n=5000时C(5000,2)=12,497,500基本RSA的这个安全性漏洞称为可传递性。如果每次都返回FALSE，doc2×c(2)给定y,计算x使y=f(x)是困难的单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。格归约的传统算法为LLL算法，以后又有各种改进的算法。在确定的范围内，加密和解密函数是互逆的。(3)K为有限密钥空间，是一些可能密钥的有限集合；格的维数总是不超过N。m(2,1)(modp)=p-mp；格归约的传统算法为LLL算法，以后又有各种改进的算法。执行概率素数判定测试,如果n未测试通过,则拒绝数值n,转向步骤1二、公钥密码RSA公钥密码RSA1977年由美国麻省理工学院的三位教授

RonaldRivestAdiShamirLeonardAdleman联合发明容易，只需要不超过N－1次加法。二、公钥密码RSA公钥密码R98二、公钥密码RSARSA的密钥生成选择两个大的素数p和q。选择两个正整数e和d，满足：ed是(p-1)(q-1)的倍数加1。计算n=pq。Bob的公钥是（n，e），对外公布。Bob的私钥是d，自己私藏。至于（p，q

），可以是Bob的另一部分私钥，也可以是对所有人（包括Bob）都保密的。二、公钥密码RSARSA的密钥生成99二、公钥密码RSA基本RSA的加密过程：Alice欲发送明文m给Bob，其中0<m<n

。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的加密过程：Alice欲发送明文100二、公钥密码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基本RSA的安全性101二、公钥密码RSA目前普遍使用的参数范围是2511<p<2512，2511<q<2512。如果Eve欲穷举p的所有可能值，则穷举的次数约为(2512-2511)/2=2510（次）。（因此，基本RSA似乎是足够安全的）二、公钥密码RSA目前普遍使用的参数范围是102二、公钥密码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的一个安全性漏洞103二、公钥密码RSA基本RSA的这个安全性漏洞称为可传递性。这个漏洞使得攻击者Eve对某些新的密文能够轻而易举地找到其对应明文。这个漏洞还有更深刻的隐患，比如在消息认证过程中容易产生伪造。（将在后面介绍）为了克服基本RSA的这个安全性漏洞，人们将基本RSA进行改造，引入Hash函数。（将在后面介绍）二、公钥密码RSA基本RSA的这个安全性漏洞称为可传递性。104要求：若使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与q必为足够大的素数，使105RSA密钥的生成RSA密钥的生成106公钥密码一课件107=[a(2i)modn]n=5000时C(5000,2)=12,497,500这是因为，采用折半相乘，只需要不超过2log2p次的modp乘法运算。(2)给定y,计算x使y=f(x)是困难的Bob的公钥是（n，e），对外公布。Ua1>M>Ua1(modM)=b1，设y满足y=gxmodp。定理设超递增背包重量为S。当log2p≈1024时，亚指数计算量不小于2100数量级。在确定的范围内，加密和解密函数是互逆的。务必要先签名后加密!如果n已通过足够的测试,则接受n,否则转向步骤2;WITNESS(a,n)判定n是否为素数，a是某个小于n的整数m(2,2)(modq)=q-mq。至于（p，q），可以是Bob的另一部分私钥，也可以是对所有人（包括Bob）都保密的。例：明文=“RSAALGORITHM”一个根的(modp)、(modq)值是p-mp、q-mq。m的二进制表示为bkbk-1…b0,则=18191024·1819128·181964·18194·18192·18191(mod2867)传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。例：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=[a(2i)modn]例：p=47,q=6108用RSA算法加密与解密的过程：例：明文=“RSAALGORITHM”(1)明文用数字表示空白=00，A=01,B=02,…,Z=26(两位十进制数表示)

1819010001120715180920081300(2)利用加密变换公式C=mPKmodr,即C=18191223mod2867=2756 PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223(mod2867) =18191024·1819128·181964·18194·18192·18191(mod2867) =27562756200105420669234704081815用RSA算法加密与解密的过程：27562001054109选择两个大素数p和q，通常要求每个均大于10100。计算n＝pｘq和z＝(p－1)(q－1)。选择一与z互素的数、令其为d。找到一个e满足e×d＝1(modz)。选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0<m<n。加密P时，计算C＝Pe(modn)，解密C时计算P＝Cd(modn)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开(e,n)，为实现解密需要(d,n)。RSA算法归纳选择两个大素数p和q，通常要求每个均大于10100。RSA算110如何计算abmodn？如何判定一个给定的整数是素数？如何找到足够大的素数p和q?问题……如何计算abmodn？问题……111要点1：(axb)modn=[(amodn)x(bmodn)]modn]

要点2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的问题：am m的二进制表示为bkbk-1…b0,

则计算ammodnammodn=[

a(2i)]modn =[a(2i)modn]bi0bi0