第十一章公钥密码学基础课件

第十一章

公钥密码学基础

2023/7/251计算机算法设计与分析密码、加密与解密密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照法则变明文为密文，称为加密变换；依照法则变密文为明文，称为解密变换。早期密码学仅对文字或数码进行加、解密变换。现代密码学还可以对语音、图像、数据等都可实施加、解密变换。

2023/7/252计算机算法设计与分析密码体制进行明密变换的法则，称为密码体制。密码体制可以分为四种基本类型：错乱：按照规定方式改变明文符号的位置；代替：用一个或多个代替表来代替明文符号；密本：用预先编定的字母或数字密码组来代替明文中一定的词组单词等；加乱：用有限元素组成的一串序列作为乱数，按规定的算法，同明文序列相结合变成密文。这四种体制，既可单独使用，也可混合使用。2023/7/253计算机算法设计与分析密钥和公钥密码的思想1976年美国斯坦福大学的Diffle和Hellman提出了公钥密码的思想：W.DiffieandM.E.Hellman:“NewDirectrionsinCryptography”,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654为密码系统分别设计一个加密密钥kc和一个解密密钥kd。把kc公开，而把kd保密，同时kc的公开不会影响kd的安全。这样：加密的过程为：c=Ekc(m)，解密的过程为：m=Dkd(c)。2023/7/254计算机算法设计与分析秘钥与公钥密码学分为秘钥密码学和公钥密码学。秘钥密码学在加密和解密所使用的密钥是相同的，又称为对称密码学。公钥密码学加密和解密所使用的密钥是不相同的，且前者(签字密钥)公开而后者(验证密钥)保密，又称为非对称密码学。

2023/7/255计算机算法设计与分析公钥密码学的各种技术及功能1、保密通信2、数字签名3、秘密共享4、认证功能2023/7/256计算机算法设计与分析单向函数加密的过程和解密的过程分别为：c=E

(m)和m=D(c)显然D是E的逆函数，即D=E–1。设f(x)是En上的一个变换，En={0,1,…,n–1}，f(x)是单向的，若由x计算y=f(x)是容易的，即P问题，而由y计算出x是困难的，即NPC问题。因此，公钥密码学的思想就是让加密函数是一个单向函数。加密容易解密难！2023/7/257计算机算法设计与分析单向陷门函数加密容易解密难。要难住别人，却不要难住自己。怎么办？f(x)说是单向陷门函数，如果有陷门信息K，当K未知时，f(x)是单向的，当K已知时，由y计算出x是容易的。公约密码学的思想就是将加密函数设计为一个单向陷门函数，而把陷门信息K作为解密密码。解密密码K是保密的。有了解密密码，就很容易解密，而不知道解密密码，就很难解密。2023/7/258计算机算法设计与分析单向陷门函数例如：取两个不相等的质数p和q，令n=pq，取函数f(x)=xkmodn，且(k,ф(n))=1，其中ф(n)是n的欧拉函数(即ф(n)=(p–1)*(q–1))，则f(x)是一个单向函数。如果有d使得kd≡1(modф(n))，已知d，由y计算出x是容易的，因为yd≡x(modn)。d就是它的陷门信息。如果我们不知道ф(n)，而仅知道k，要想求出d是很困难的，这是一个NPC问题。所以f(x)还是一个单向陷门函数。2023/7/259计算机算法设计与分析代表算法RSA(Rivest,Shamir,Adleman)椭圆曲线(ECC)(EillipticCurveCroptography)背包算法2023/7/2510计算机算法设计与分析RSA公钥密码体制2023/7/2511计算机算法设计与分析RSA公钥算法RSA公钥算法是由R.Rivest,A.Shamir和L.Adleman在1977年提出来的。该算法的数学基础是初等数论中的欧拉(Euler)定理并建立在大整数因子分解的困难性之上的2023/7/2512计算机算法设计与分析欧拉定理若整数a和m互素，则a(n)≡1(modn)其中(n)为比n小但与n互素的正整数个数,称为n的欧拉函数。比如：(10)=|{9，7，3，1}|=4，(15)=|{14,13,11,8,7,4,2,1}|=8。计算(n)很困难。但可以证明，若n=p*q(p、q均为素数)，(n)=(p–1)*(q–1)。

2023/7/2513计算机算法设计与分析用欧拉函数构造单向陷门函数选取大整数n和一个与(n)互质的整数e，将n和e公开。若要对明文m加密，则令c=me(modn)。显然，这是一个单向函数。若已知一个整数d满足e*d(mod(n))=1，则cd=(me)d(modn)=(med)(modn)=(m(n)+1)(modn)=(m*m(n))(modn)=m。这里，整数d就是陷门。2023/7/2514计算机算法设计与分析RSA密码体制描述A.密钥的生成：1、选择两个素数p、q，计算n=p*q和(n)=(p–1)*(q–1)。2、选取整数b，使其满足gcd(b,(n))=1，1<b<(n)，3、计算a，满足a*b≡1mod(n)。

4、将n和b作为加密秘钥公开，将p、q和a作为解密秘钥保密。2023/7/2515计算机算法设计与分析RSA密码体制描述B.加密的过程：1、将明文数字化，并选取长度小于logn位的数字作为明文信息块。2、加密明文m，令c=E(m)=mbmodn。C.解密的过程：对密文c计算，m=D(c)=camodn，得到明文m。2023/7/2516计算机算法设计与分析RSA算法的举例A.密钥的生成1、取素数43和59，则n=43*59=2537，(n)=42*58=2436。2、选取b为13，显然满足gcd(b,(n))=1，1<b<(n)。3、解方程ab≡1mod2436，a=937。4、将2537和13作为加密公钥，937和2436保密。2023/7/2517计算机算法设计与分析RSA算法的举例B.加密过程：现有明文“publickeyencryptions”要加密。首先将其以两个字符为一组进行分组为：publickeyencryptions令00表示a，01表示b，…，将其数字化编码为：15200111080210042404130217421519081414182023/7/2518计算机算法设计与分析RSA算法的举例先讨论对第一个明文数字m1=1520的加密：E(m1)=m1bmodn=152013mod2537=(15202)6*1520mod2537∵

15202

1730mod2537=(1730)6*1520mod2537=(17302)3*1520mod2537∵

17302

1777mod2537=(1777)3*1520mod2537=(1777)2*(1777*1520)mod2537∵

17772

1701mod25371777*1520

1672mod2537=1701*1672mod2537=00952023/7/2519计算机算法设计与分析RSA算法的举例类似地，对其它数字加密后得到密文序列为：0095164814101299136513792333213217511289C.解密过程：解密运算的过程与加密过程类似，只不过将b换成a。例如：m1=D(0095)=0095937mod2537=(952)468*95mod2537=……=15202023/7/2520计算机算法设计与分析RSA算法的讨论若使RSA安全，p与q必为足够大的素数。建议选择p和q为100位以上的十进制素数。模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC9796中规定n的长度位512比特位。2023/7/2521计算机算法设计与分析RSA算法的讨论为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：1、|p–q|很大，通常p和q的长度相同；2、p–1和q–1分别含有大素因子p1和q1；3、P1–1和q1–1分别含有大素因子p2和q2；4、p+1和q+1分别含有大素因子p3和q3。2023/7/2522计算机算法设计与分析RSA算法的讨论为了提高加密速度通常取b为特定的小整数。如EDI国际标准中规定b=216+1,ISO/IEC9796中甚至允许取b=3。这时加密速度一般比解密速度快10倍以上。加密和解密算术运算主要是模n的求幂运算。著名的“平方-和-乘法”方法将计算xcmodn的模乘法的数目缩小到至多为2l。这里的l是指数a的二进制表示的比特数。若设n以二进制形式表示有k比特即k=[log2n]+1由lk这样xcmodn能在o(k3)时间内完成。2023/7/2523计算机算法设计与分析椭圆曲线密码体制2023/7/2524计算机算法设计与分析椭圆曲线实数域上的一个椭圆曲线是指满足方程：y2=x3+ax+b(x,y,a,bR)的所有点(x,y)所形成的平面曲线。有限域上模p，p为素数，的一个椭圆曲线是指满足方程：y2=x3+ax+bmodp(x,y,a,bZ)的所有点(x,y)所形成的平面曲线。2023/7/2525计算机算法设计与分析椭圆曲线群若椭圆曲线y2=x3+ax+b满足4a3+27b2

0modp则由该椭圆曲线上的点再加上一个无穷远点，可以形成一个Abel群。这里无穷远点是一个抽象的点，可以想象为平行线的交点。有限域上模p的椭圆曲线群记为Ep(a,b)。2023/7/2526计算机算法设计与分析一个有限域上的椭圆曲线群设p=23，令y2=x3+x+1，即a=1,b=1。∵4a3+27b2

0modp∴该曲线在F23上的点：(0,1)(0,22)(1,7)(1,16)(3,10)(3,13)(4,0)(5,4)(5,19)(6,4)(6,19)(7,11)(7,12)(9,7)(9,16)(11,3)(11,20)(12,4)(12,19)(13,7)(13,16)(17,3)(17,20)(18,3)(18,20)(19,5)(19,18)，再加上无穷远点构成椭圆曲线群E23(1,1)。群E23(1,1)包括无穷远点在内有28个点。2023/7/2527计算机算法设计与分析椭圆曲线群的加法定义Ep(a,b)上点的加法为：⑴

为单位元素；⑵(x,y)(x,–y)=，即点(x,y)的逆为(x,–y)。⑶

令P=(x1,y1),Q=(x2,y2)且非互逆，则PQ=(x1,y1)(x2,y2)=(x3,y3),其中，x3=k2–x1–x2modp，y3=k(x1–x3)–y1modp，k=(y2–y1)/(x2–x1)。易证Ep(a,b)对加法构成Abel群。2023/7/2528计算机算法设计与分析椭圆曲线群的点加运算PQ在几何上的定义是P、Q两点的连线与椭圆曲线E的交点的对称点。而当P=Q，PQ在几何上的定义就成了椭圆曲线E在P点的切线与E的交点的对称点。因此，倍点运算，即2P=PP的计算，有别于PQ。2023/7/2529计算机算法设计与分析椭圆曲线群的倍点运算令P=(x1,y1)，y10，则2P=2(x1,y1)=(x3,y3),其中，x3=k2–2x1modp，

y3=k(x1–x3)–y1modp，

k=(3x12+a)/2y1。注意，虽然x3和y3的计算公式与点加公式中的形式仍然完全是一样的，但是k的计算却完全不一样了。2023/7/2530计算机算法设计与分析椭圆曲线点群的离散对数问题1985年N.Koblitz和V.Miller分别独立提出了椭圆曲线密码体制(ECC)，其依据就是椭圆曲线点群的离散对数问题的难解性。设G=(x,y)是椭圆曲线点群Ep(a,b)的一个生成元，且G的周期n是一个很大素数。所谓G的周期n就是使得nP=的最小正整数n。设Q是Ep(a,b)中的点，则必有正整数m使得Q=m

G于是，定义m=log

GQ。已知m和G求Q的计算是很容易的，但是已知Q和G，要求m却是非常困难的。这就是椭圆曲线点群上的离散对数问题。2023/7/2531计算机算法设计与分析椭圆曲线密码体制A.密钥的生成：1、选择素数p构造椭圆曲线群Ep(a,b)。2、选择Ep(a,b)的一个点G，使得G的阶n是一个大素数。3、秘密选择整数d<n，计算Q=dG。4、将(p,a,b,G,Q)作为加密公钥公开，把整数d作为解密思钥保密。2023/7/2532计算机算法设计与分析椭圆曲线密码体制B.加密过程：1、将明文m编码为Ep(a,b)的点Pm。2、随机选择k，计算kG和kP。(若kG或kP为，则要重新选择k。)3、将c=(kG,Pm

kP)作为密文。C.解密过程：1、计算Pm

kP–dkG=Pm。∵

P=dG∴

kP=dkG。2、将Pm解码为m。2023/7/2533计算机算法设计与分析椭圆曲线密码的举例A.密钥的生成：1、取y2=x3+ax+bmodp中的a、b和p分别为–1、188和751，得到E751(–1,188)。2、选G为(0,376)，阶为769(即769G=)。3、选d=85，计算P=85G=(671,558)4、将(751,–1,188,(671,558))作为公钥公开。将85作为私钥。2023/7/2534计算机算法设计与分析椭圆曲线密码的举例B.加密过程：1、设明文m编码为E751(–1,188)的点(443,253)。2、随机选取k=113，计算：kG=113(0,376)=(34,633)；kP=113(671,558)=(47,416)PmkP=(443,253)(47,416)=(217,606)3、最后将((34,633),(217,606))作为密文。2023/7/2535计算机算法设计与分析椭圆曲线密码的举例C.解密过程：1、收到密文((34,633),(217,606))，利用私钥85计算：85(34,633)=(47,416)；2、计算：(217,606)–(47,416)=(217,606)

(47,–416)=(217,606)

(47,335)=(443,253)；3、将(443,253)解码便得到明文m。两者互逆335=–416mod7512023/7/2536计算机算法设计与分析椭圆曲线密码体制的安全性自从椭圆曲线密码体制提出来以后，它一直受到数学界和密码学界的关注。但是迄今为止，还未见相当有效的攻击算法的报道。如果有1000MIPS的计算机10000台，取长约160比特的素数，则计算椭圆曲线的离散对数问题需要96000年。因此椭圆曲线密码体制被认为是安全的。2023/7/2537计算机算法设计与分析背包公钥密码体制2023/7/2538计算机算法设计与分析0-1背包问题已知一容积为b的背包及体积分别为a1,a2,…an的n个物品，从这些物品中选出若干个正好装满这个背包，那么究竟是那些物品？即求解:

naixi=b，xi{0,1}，i=1,…,n,

i=1其中ai和b都是正整数。2023/7/2539计算机算法设计与分析背包公钥密码选取正整数a1,a2,…,an作为公钥，设明文位串为m=m1m2…mn，mi{0,1}

。利用公钥将明文加密为密文c=a1m1+a2m2+…+anmn。这样，如果要将其解密，即从密文c求得明文m等价于求解一个背包问题。2023/7/2540计算机算法设计与分析超递增序列简单的说，序列{a1,a2,…,an}是超递增的，就是该序列中的每个元素都大于序列中位于它之前的所有元素之和。

i–1

aj<ai,i=2，3，……，n

j=1序列{a1,a2,…,an}是超递增的，如果满足的序列{a1，a2，……，an}。

2023/7/2541计算机算法设计与分析超递增序列的背包问题易解背包问题难解，但是超递增序列{a1,…,an–1,an}构成的背包问题却不难解。设序列{a1,…,an–1,an}是超递增的。求背包问题a1x1+…+an–1xn–1+anxn=c

。显然，若c>an，则xn为1，否则xn为0。确定了xn之后，将c减去an或不变，就得到一个新的m–1个变量的背包问题。用同样方法确定xn–1。重复进行，求出所有xi。2023/7/2542计算机算法设计与分析MH背包公钥密码显然，不能将超递增序列{a1,a2,…,an}直接作为公钥使用，而应将其超递增性掩盖起来，转换为一个非超递增序列作为公钥使用。这就是由Merkle和MartinHelman合作设计的一个基于0-1背包问题的公钥密码算法的思想。这个算法简称为MH背包密码算法。2023/7/2543计算机算法设计与分析将超递增性隐藏起来选取一个超递增序列：a1，a2，…，an。选取正整数m和w，m>a1+a2+…+an且(w，m)=1，作变换：bi=waimodm，于是得到新序列：b1,b2,…,bn。将新序列作为加密的公钥。{b1,b2,…,bn}不再是超递增序列。2023/7/2544计算机算法设计与分析将超递增性隐藏起来例如：超递增序列为{1,2,5,9,20,41,83,164}，选取m=353，w=233。做变换：b1=233*1mod353=233，b2=233*2mod353=113，……得到新序列(233,113,106,332,71,22,277,88)。这个序列不再是超递增序列，将它作为公钥。这样，用新序列加密就成了一般的背包问题。2023/7/2545计算机算法设计与分析MH背包密码的陷门若知道w，由于(w，m)=1，故存在w–1满足：ww–1

≡1(modm)w–1就是MH背包密码的陷门。应用w–1，解密就变得很容易了：w–1c≡w–1b1m1+w–1b2m2+…+w–1bnmn(modm)由于w–1bi≡w–1wai≡ai(modm)i=1,2,…,n所以有m1a1+m2a2+…+mnan≡w–1c(modm)。这样，就还原为超递增序列的背包问题。2023/7/2546计算机算法设计与分析背包公钥密码的例子A.密钥的生成选取超递增序列为{1,2,5,9,20,41,83,164}，m=353，w=233，计算得w–1=50。做变换：b1=233*1mod353=233，b2=233*2mod353=113，……得到新序列(2