3_公钥密码

公钥密码13：公钥密码PublicKeyCryptography公钥密码2公钥密码PublicKey公钥密码也被称为”非对称“密码，或“双匙”密码公钥密码体系是近代密码学的产物，由英国政府通信总局(GCHQ(类似于NSA))的密码学者在20世纪60年代末和民间学者在70年代初分别独立提出政府开始没有足够重视，直至民间学者公开研究成果，最终导致密码学的革命公钥密码体制比对称匙密码相对少很多基于特殊的数学结构对称匙密码则可以有很多新思路公钥密码3公钥密码PublicKey两个密钥发送者用接收者的公钥进行加密接收者用自己的私钥来解密基于单向陷门函数(trapdoor,onewayfunction)从一个方向容易计算从反方向很难计算运用“陷门”创建密钥例如:给定p和q,积N=p*q很容易计算；但给定积N,很难找到因子p和q公钥密码4公钥密码学加密假设我们用Bob的公钥对信息M加密解密只有通过Bob的私钥才能解密得到信息MBob还可以使用私钥对信息进行签名任何人可以通过公钥解密这个信息只要私钥拥有者能进行签名如同手工签名公钥密码5背包密码(Knapsack)最早提出的公钥密码体制公钥密码6背包(Knapsack)密码给定一组n个重量W0,W1,...,Wn-1和一个总重量S,能否找到一组系数ai{0,1}满足S=a0W0+a1W1+...+an-1Wn-1(也称其为“子集-和”问题)实例重量(62,93,26,52,166,48,91,141)问题：找到系数满足S=302答案:62+26+166+48=302此处系数为（10101100）已证明一般knapsack问题是NP-完全问题(非常难解)公钥密码7背包(Knapsack)问题一般背包问题(GK)很难解决但超递增背包问题(super-increasingknapsack)(SIK)很容易解决SIK要求重量递增排列且每个重量比前面所有重量和还大实例重量(2,3,7,14,30,57,120,251)问题:找出子集满足和=186从大到小逐步推算…答案:120+57+7+2=186系数为(1,0,1,0,0,1,1,0)公钥密码8背包密码系统1.创建一个超级递增背包(SIK)2.将超级背包转换成“普通”背包(GK)3.公钥:普通背包问题4.私钥:超级递增背包加转换因子很容易用普通背包(GK)加密很容易用私钥解密(将密文转换成SIK)在没有私钥的情况下,必须解决普通背包问题?(非常困难)公钥密码9背包密码系统实例假设(2,3,7,14,30,57,120,251)是超级递增背包选择m=41、n=491。这里m,n互素并且n大于背包各元素之和则普通背包产生方式：241mod491=82341mod491=123741mod491=2871441mod491=833041mod491=2485741mod491=37312041mod491=1025141mod491=471普通背包:(82,123,287,83,248,373,10,471)公钥密码10背包密码系统实例私钥:(2,3,7,14,30,57,120,251)及12（m1modn称为m的模逆）m1modn=411mod491=12（491+1=492/12=41）公钥:(82,123,287,83,248,373,10,471),n=491实例:加密明文1001011082+83+373+10=548（密文）解密,(548·12)mod491=6576%491=1936576=491*13+193用私钥(2,3,7,14,30,57,120,251)解193得到明文10010110(2+14+57+120=193)公钥密码11背包密码系统实例分析如果没有私钥[(2,3,7,14,30,57,120,251),12]攻击者必须找到公钥(82,123,287,83,248,373,10,471)里的某个子集满足元素之和为491变成了普通背包问题，非常难解将超递增背包通过模运算转换为普通背包就是陷门，没有私钥的情况下将很难解密公钥密码12背包密码系统分析陷门:通过模运算将超级超递增背包转换为一般递增背包单向:一般背包容易用来加密，难解密;超递增则容易解密这种背包密码系统是不安全的在1983被苹果II电脑破解攻击采用的是格约简(latticereduction)技术“普通背包”并不够‘简单’!这种特殊的背包很容易破解!现在很多背包密码的变形是安全的，但已很少应用公钥密码13RSA密码技术公钥密码14RSA密码最早由CliffCocks提出,后来被Rivest,ShamirandAdleman(MIT)独立发明其设计原理是基于因子分解的困难性虽不如“货担郎”问题困难虽未被证明是NP完全问题仍然是一种数学上非常难解的问题公钥密码15RSA密码设p和q是两个大素数设N=p*q选择e与(p1)(q1)互为素数找到合适的d满足(e*d)%(p1)(q1)=1公钥是(N,e)私钥是d公钥密码16RSA密码对信息M加密C=Me％N对密文C解密M=Cd％N回忆e和N是公开的如果攻击者能找到N,那么他很容易用e找到d因为e＊d％(p1)(q1)=1因子分解可以破解RSA密码目前尚未明确是否只有因子分解可以破解RSA公钥密码17简单RSA密码实例RSA实例选择两个素数p=11,q=3那么N=p*q=33并且(p1)*(q1)=20选择e=3(与20互为素数)选择满足(e*d)%20=1,找到d=7满足公钥:(N,e)=(33,3)私钥:d=7公钥密码18简单RSA密码实例公钥:(N,e)=(33,3)私钥:d=7假设需加密信息M=8密文C的计算方法如下C=Me%N=83%33=512%33=17将C解密恢复明文的算法如下M=Cd%N=177%33=410,338,673%33=(12,434,50533+8)%33=8公钥密码19Diffie-Hellman算法公钥密码20Diffie-Hellman算法被D(Diffie)andH(Hellman)提出“密钥交换”算法用来创建一套‘共享’的对称密钥它并不用来加密或者签名算法的难度建立在离散对数问题(discretelog)上:给定g,p,以及x=gk%p很难找到k公钥密码21Diffie-Hellman算法算法的难度建立在离散对数问题(discretelog)上:给定g,p,以及x=gk%p很难找到k于对数问题相似，不同的是进行离散对数运算为被证实是NP完全问题，但与因子分解一样非常困难公钥密码22Diffie-Hellman算法设p是素数,g是生成元(generator)对任意x{1,2,…,p-1}我们能找到n满足x=gn%pAlice选择一个秘密的a值Bob选择一个秘密的b值Alice将ga%p发送给BobBob将gb%p发送给Alice两人的电脑共享秘密的gab%p共享的秘密可被用作对称密钥(公钥)公钥密码23Diffie-Hellman算法假设Bob和Alice使用gab%p作为对称密钥Trudy可以获得ga%p和gb%p注意(ga*gb)%p=ga+b%pgab%p如果Trudy能找到a或b,整个系统就被破译了如果Trudy能解离散对数问题，那么她能够找到a或b公钥密码24Diffie-Hellman算法公钥:gandp密钥:Alice的指数a,Bob的指数bAlice,aBob,bga%pgb%pAlice计算(gb)a=gb*a=ga*b%pBob计算(ga)b=ga*b%p可以利用K=gab%p作为共有(对称)密钥公钥密码25Diffie-Hellman算法弱点会遭受中级人(MiM)攻击（一种主动攻击）Alice,aBob,bgamodpgbmodpTrudy,tgtmodpgtmodpTrudy和Alice共享密钥gat%pTrudy和Bob共享密钥gbt%pAlice和Bob不知道Trudy的存在!公钥密码26Diffie-Hellman算法分析如何防止‘中间人’攻击?用对称密钥加密DH交换用公钥加密DH交换使用私钥签名DH交换使用Diffie-Hellman时必须重视‘中间人’攻击公钥密码27作业假设Bob的背包密码私钥是(3,5,10,23)和m-1=6,模数n=47。对密文C=20求出明文，以二进制表示。对密文C=29求出明文，以二进制表示。求出m和公钥。Alice的RSA公钥是(N,e)=(33,3),私钥d=7.如果Bob加密消息M=19发送给Alice,密文C是什么，展示Alice如何将密文解密。