公钥密码学基础

2020/5/5,计算机算法设计与分析,1,第十一章公钥密码学基础,2020/5/5,计算机算法设计与分析,2,密码、加密与解密,密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照法则变明文为密文，称为加密变换；依照法则变密文为明文，称为解密变换。早期密码学仅对文字或数码进行加、解密变换。现代密码学还可以对语音、图像、数据等都可实施加、解密变换。,2020/5/5,计算机算法设计与分析,3,密码体制,进行明密变换的法则，称为密码体制。,密码体制可以分为四种基本类型：错乱：按照规定方式改变明文符号的位置；代替：用一个或多个代替表来代替明文符号；密本：用预先编定的字母或数字密码组来代替明文中一定的词组单词等；加乱：用有限元素组成的一串序列作为乱数，按规定的算法，同明文序列相结合变成密文。这四种体制，既可单独使用，也可混合使用。,2020/5/5,计算机算法设计与分析,4,密钥和公钥密码的思想,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)。,2020/5/5,计算机算法设计与分析,5,秘钥与公钥,密码学分为秘钥密码学和公钥密码学。秘钥密码学在加密和解密所使用的密钥是相同的，又称为对称密码学。公钥密码学加密和解密所使用的密钥是不相同的，且前者(签字密钥)公开而后者(验证密钥)保密，又称为非对称密码学。,2020/5/5,计算机算法设计与分析,6,公钥密码学的各种技术及功能,1、保密通信2、数字签名3、秘密共享4、认证功能,2020/5/5,计算机算法设计与分析,7,单向函数,加密的过程和解密的过程分别为：c=E(m)和m=D(c)显然D是E的逆函数，即D=E1。,设f(x)是En上的一个变换，En=0,1,n1，f(x)是单向的，若由x计算y=f(x)是容易的，即P问题，而由y计算出x是困难的，即NPC问题。因此，公钥密码学的思想就是让加密函数是一个单向函数。加密容易解密难！,2020/5/5,计算机算法设计与分析,8,单向陷门函数,加密容易解密难。要难住别人，却不要难住自己。怎么办？,f(x)说是单向陷门函数，如果有陷门信息K，当K未知时，f(x)是单向的，当K已知时，由y计算出x是容易的。,公约密码学的思想就是将加密函数设计为一个单向陷门函数，而把陷门信息K作为解密密码。解密密码K是保密的。有了解密密码，就很容易解密，而不知道解密密码，就很难解密。,2020/5/5,计算机算法设计与分析,9,单向陷门函数,例如：取两个不相等的质数p和q，令n=pq，取函数f(x)=xkmodn，且(k,(n)=1，其中(n)是n的欧拉函数(即(n)=(p1)*(q1)，则f(x)是一个单向函数。如果有d使得kd1(mod(n)，已知d，由y计算出x是容易的，因为ydx(modn)。d就是它的陷门信息。如果我们不知道(n)，而仅知道k，要想求出d是很困难的，这是一个NPC问题。所以f(x)还是一个单向陷门函数。,2020/5/5,计算机算法设计与分析,10,代表算法,RSA(Rivest,Shamir,Adleman)椭圆曲线(ECC)(EillipticCurveCroptography)背包算法,2020/5/5,计算机算法设计与分析,11,RSA公钥密码体制,2020/5/5,计算机算法设计与分析,12,RSA公钥算法,RSA公钥算法是由R.Rivest,A.Shamir和L.Adleman在1977年提出来的。该算法的数学基础是初等数论中的欧拉(Euler)定理并建立在大整数因子分解的困难性之上的,2020/5/5,计算机算法设计与分析,13,欧拉定理,若整数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)=(p1)*(q1)。,2020/5/5,计算机算法设计与分析,14,用欧拉函数构造单向陷门函数,选取大整数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就是陷门。,2020/5/5,计算机算法设计与分析,15,RSA密码体制描述,A.密钥的生成：,1、选择两个素数p、q，计算n=p*q和(n)=(p1)*(q1)。2、选取整数b，使其满足gcd(b,(n)=1，1b(n)，3、计算a，满足a*b1mod(n)。4、将n和b作为加密秘钥公开，将p、q和a作为解密秘钥保密。,2020/5/5,计算机算法设计与分析,16,RSA密码体制描述,B.加密的过程：1、将明文数字化，并选取长度小于logn位的数字作为明文信息块。2、加密明文m，令c=E(m)=mbmodn。,C.解密的过程：对密文c计算，m=D(c)=camodn，得到明文m。,2020/5/5,计算机算法设计与分析,17,RSA算法的举例,A.密钥的生成1、取素数43和59，则n=43*59=2537，(n)=42*58=2436。2、选取b为13，显然满足gcd(b,(n)=1，1ba1+a2+an且(w，m)=1，作变换：bi=waimodm，于是得到新序列：b1,b2,bn。,将新序列作为加密的公钥。b1,b2,bn不再是超递增序列。,2020/5/5,计算机算法设计与分析,45,将超递增性隐藏起来,例如：超递增序列为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)。这个序列不再是超递增序列，将它作为公钥。这样，用新序列加密就成了一般的背包问题。,2020/5/5,计算机算法设计与分析,46,MH背包密码的陷门,若知道w，由于(w，m)=1，故存在w1满足：ww11(modm)w1就是MH背包密码的陷门。,应用w1，解密就变得很容易了：w1cw1b1m1+w1b2m2+w1bnmn(modm)由于w1biw1waiai(modm)i=1,2,n所以有m1a1+m2a2+mnanw1c(modm)。这样，就还原为超递增序列的背包问题。,2020/5/5,计算机算法设计与分析,47,背包公钥密码的例子,A.密钥的生成选取超递增序列为1,2,5,9,20,41,83,164，m=353，w=233，计算得w1=50。做变换：b1=233*1mod353=233，b2=233*2mod353=113，得到新序列(233,113,106,332,71,22,277,88)。将新序列作为公钥，原超递增序列为私钥。,2020/5/5,计算机算法设计与分析,48,背包公钥密码的例子,B.加密过程：设发送的明文为：010110011100101010001001。,先将明文分块为：010110011100101010001001,01011001对应的密文为：a2+a4+a5+a8,公钥序列：(233,113,106,332,71,22,277,88),=113+332+71+88=604,604,11001010对应的密文为：a1+a2+a5+a7,=233+113+71+277=694,694,同样方法的出10001001对应的密文为：392。这样，密文为：604，694，392。,2020/5/5,计算机算法设计与分析,49,背包公钥密码的例子,C.解密过程：收到密文后，分别先计算50乘以密文值模353，然后再解超递增序列(私钥)背包问题。比如，对604，先计算50*604mod353=195然后解超递增序列1,2,5,9,20,41,83,164的背包问题，易得2+9+20+164=195，于是对应的明文为：01011001。同样的方法求得，694和392的明文。,2020/5/5,计算机算法设计与分析,50,背包公钥密码的安全性,Merkle悬赏$100请人破译背包密码。1