密码编码学与网络安全课件.pptVIP

公钥加密的出现?1976年由WhitfieldDiffieMartinHellman在StanfordUniversity所发明–加密密钥P是公开的，称为公钥K–解密密钥S是保密的，称为私钥K?公钥技术是二十世纪最伟大的思想之一–改变了密钥分发的方式–可以广泛用于数字签名和身份认证服务

公钥编码模型-1

公钥编码模型-2

公钥加密的特点?公开密钥密码体制–能够有效计算公钥PK和私钥SK。–从已知的公钥PK不能推导出私钥SK。–发送方用公钥PK进行加密，而接收方用私钥SK进行解密,还原出明文，即：D(E(P))=PSKPK–两个密钥中的任何一个都能进行加密，而另一个则进行解密。

公钥算法应用：保密

公钥算法应用：鉴别

保密和鉴别

RSA?RSA方法由三位MIT科学家Rivest、Shamir和Adleman于1977年提出?最著名和使用最广泛的公钥加密方法?基于整数的有限幂次对素数的取模?使用大整数作为密钥?安全性依赖于大数的因子分解

RSA-密钥选择?1．随机选择两个大素数p和q。?2．计算公开的模n=p*q。?3．计算欧拉函数Φ(n)=(p-1)*(q-1)。?4．随机选一整数e，1≤eΦ(n)，?(Φ（n）,e)=1。即Φ（n）和e互素。?5．计算d，满足edmodΦ(n)=1。?得到公钥和密钥，公钥为(e,n)，密钥为d。

RSA-加密与解密1．将明文划分为一个个数据块P，其中0≤Pn。2．C为P对应的密文。则：加密：C=P解密：P=Ced(modn)(modn)

RSA-证明?解密：X=D(C)=CdmodnSK??=(Xemodn)dmodn=Xmodned?由于de≡1modφ(n)，故de=kφ(n)+1，则?Cmodn=Xkφ(n)+1modnd??=(X)Xmodnkφ(n)=X(根据欧拉定理的变化形式)

RSA-举例?1．选择p=7,q=17。?2．计算n=p*q=119，Φ(n）=(p-1)*(q-1)=96。?3．选e=5，因为5和96互素。?4．根据5dmod96=1，得d=77。?5．公钥为(5,117),密钥为77。?如：明文为P=6。?密文:C=Pemodn=65mod119=41。?解密：P=Cmodn=41mod119=6。d77

RSA的计算技巧?模运算的性质计算Mmodne–[(amodn)(bmodn)=(ab)modn–e=bb…b,则e=∑2,其中b=1ikk-10i=M∑2i=(((…((M–Mebk)2Mbk-1)2Mbk-2)2…)2Mbk)2Mb1)2Mb0.2.6=362.–如：65=6=((6))10126=77766=46656?计算算法–d=1–Fori=kto0do?d=d2modn?Ifb=1thend=(d*M)modni

RSA的计算技巧?计算7560mod561–560=230h=001000110000b–d=1,k=9,?i=9,d=d?i=8,d=d?i=7,d=d?i=6,d=d?i=5,d=d?i=4,d=d?i=3,d=d?i=2,d=d?i=1,d=d222222222mod561=1,b=1,d=(d*7)mod561=79mod561=49,b=08mod561=157,b=07mod561=526,b=06mod561=103,b=1,d=(d*7)mod561=1605mod561=355,b=1,d=(d*7)mod561=2414mod561=298,b=03mod561=166,b=02mod561=67,b=01?i=0,d=d2mod561=1,b=00

RSA-安全性?蛮力攻击?数学攻击?定时攻击

RSA-蛮力攻击整数N的因子分解：从2开始试验每一个小于等于√N的素数整数n的十进制位数因子分解的运算次数所需计算时间（次/微秒）50751002003005001.4x10109.0x10122.3x10151.2x10231.5x10291.3x10393.9小时104天74年3.8x10年94.0x1015年4.2x1025年

RSA-数学攻击?三种形式:–因子分解N=p.q,从而发现?(N)和d–直接确定?(N)，然后