非对称密码体制第四章网络09课件

第四章公开密钥密码体制一.基本要求与基本知识点（1）掌握公钥密码体制的基本概念；（2）掌握RSA的密钥产生、加密及解密过程；（3）理解ELGamal体制的密钥产生、加密及解密过程；（4）理解背包体制的密钥产生、加密及解密过程。二.教学重点与难点（1）公钥密码体制的基本概念；（2）RSA体制；（3）ELGamal体制；（4）背包体制。14.1公钥密码体制的基本概念公钥密码体制是为了解决对称密码体制中最难解决的两个问题而提出的。一是对称密码技术的密钥分配问题。在对称密码体制中，加密密钥和解密密钥是相同的，任何人只要获得加密密钥，才能对密文进行解密，获得明文。利用对称密码体制进行保密通信时，密钥不能公开，要通过安全信道传送给合法的接收者。若网络中有n个人要互相进行保密通信的话，每一个人就须保存另外n-1的密钥，因而网络中就会有n(n-1)／2个密钥，且为安全起见，密钥需要经常更换。因此当n较大时，大量密码的产生、分发和更换十分困难，即密钥管理变得十分复杂。二是对称密码不能实现数字签名，无法证实信息的真实性。24.1公钥密码体制的基本概念Diffie和Hellmna于1976年在《密码学的新方向》中首次提出了公钥密码的观点，即为每个用户分配两个相互匹配又相互独立的密钥，其中：一个密钥被公开，称为公开密钥（公钥），用于加密，另一个密钥被保密，称为私有密钥（私钥），用于解密。 所有用户的公钥均登记在类似电话号码簿的密钥本上。当要给用户A发送加密信息时，需要在密码本上查找A用户的公钥，然后加密信息，并发给用户A。用户A接收到密文之后，用自己的私钥进行解密即可得到明文。1977年由Rivest（李维斯特）、Shamir（沙米尔）和Adleman（埃德曼）共同提出了第一个公钥密码算法（即RSA密码体制），是公钥密码中最优秀的加密算法，被誉为密码学发展史上的里程碑之一。此后，人们基于不同的计算问题提出了大量的公钥密码算法。34.1.2加密模型和认证模型一个公钥密码体制由6个部分构成：明文，加密算法，公钥和私钥，密文，解密算法。可以构成两种基本的模型：加密模型和认证模型。1、加密模型---保密性在加密模型中，发送方用接收方的公钥作为加密密钥，接收方用自己的私钥作解密密钥，由于该私钥只有接收方拥有，因此即只有接收者才能解密密文得到明文。54.1.2加密模型和认证模型如图4-1所示，假设用户A向用户B发送消息M。在发送方，用户A首先用用户B的公钥PUB加密消息M，得到密文：；在接收方，用户B用自己的私钥PRB解密密文C，得到明文：。由于只有B知道PRB，所以其他人不能解密C。6图4-1公钥加密模型

7图4-2公钥认证模型

94.2RSA密码体制RSA密码体制是1977年由Rivest、Shamir、Adleman提出的非常著名的公钥密码算法。RSA算法的安全性基于：求两个大素数的乘积是容易的，但分解两个大素数的乘积，求出其素因子则是困难的，它属于NP完全类问题，至今没有有效的算法。RSA算法是一种分组密码，明文和密文是0到n-1之间的整数，通常n的大小为1024位二进制数或309位十进制数。104.2.1RSA算法1、密钥的产生（1）随机选择两个大素数（如100位十进制数）p和q，令n=p×q；（2）计算欧拉函数（见定理2.1.1） (n)=n(1-1/p)(1-1/q)=(p-1)(q-1)；（3）选择e使得1<e<(n)，且gcd(e,(n))=1；（4）计算d e∙d≡1mod(n)，且0≤d≤n（5）公开公钥：PU={e,n}；（6）保存私钥：PR={d,p,q}。11图4-3RSA算法13【例4-1】选择素数：p=47和q=71，求出RSA算法的公钥和私钥。【解】：（1）计算：n=pq=47×71=3337，

(n)=(p-1)(q-1)=46×70=3220。（2）选择e：使gcd(e,3220)=1，选取e=79；（3）求解d：de≡1mod3220， 即79d≡1mod3220辗转除法： 3220=40×79+60 79=1×60+19 60=3×19+3 19=6×3+1 14回代： 1=19-6×3=19-6×（60-3×19）=19×19-6×60 =19×(79-1×60)-6×60=19×79-25×60 =19×79-25×(3220-40×79)=19×79-25×(3220-40×79) =1019×79-25×3220两边同时对模3220进行求余运算得 1019×79≡1mod3220于是d=1019（4）公开公钥PU={79，3337} 保存私钥PR={1019，47，71}；15RSA密码体制的特点（1）运算速度慢 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，一般来说适用于少量数据的加密。（2）产生密钥烦琐 产生密钥很麻烦，受到素数产生技术的限制。174.2.2RSA算法的安全性

RSA体制的安全性是基于大数的因子分解问题，大数的因子分解在数学上是一个难解问题，即无法从公钥参数n中计算出素数因子（大于100个十进制位）p和q，于是无法计算出(n)=(p-1)(q-1)，也就无法计算出私钥d，从而保证非法者不能对密文进行解密。RSA的安全性依赖于大数分解困难，即从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。显然，分解n是最常遇到的攻击方法。在算法中要求p和q均大于100位十进制数，这样的话n至少200位十进制数，目前人们已能分解140多位的十进制数的大素数。最新记录是129位十进制数的因数分解，在网络通过分布计算被成功分解。估计对200位十进制数的因数分解，在亿次计算机上也要进行55万年。184.3EIGamal密码体制该体制是1985年由EIGamal提出的一个著名的公钥密码算法。该算法既能用于数据加密也能用于数字签名，其安全性依赖于离散对数这一难题。【离散对数问题：设g，x，p是正整数。已知g，x和p，可以容易地求出y，使得： y≡gx(modp)反之，如果已知y，g和p，求x，这就是离散对数问题，属NP完全类问题，是难解的。】1.密钥产生（1）任选一个大素数p（300位十进制数），使得p-1有大素因子，g是模p的一个本原根（即g是{0，1，2，…，p-1}中与p互素的数），公开p与g；（2）任选一私钥x，x∈[0,p-1]；（3）计算y≡gx(modp)；（4）公开公钥：y；（5）保密私钥：x；194.3EIGamal密码体制 与RSA方法比较，ElGamal方法具有以下优点：（1）系统不需要保存秘密参数，所有的系统参数均可公开；（2）密文依赖于加密过程所选择的随机数r，加密相同的明文可能会产生不同的密文；（3）ElGamal方法的计算复杂度比RSA方法要大。21【例4-2】

假设Alice想要加密消息m=1299后传送给Bob。（1）密钥产生Alice任选一个大素数p为2579，g是模p的一个本原根，取g为2，公开参数p，g。任选私钥x为765， 计算公钥y≡gx(modp)≡2765(mod2579)≡949(mod2579)，公开：PU=949，保密：PR=765。22（2）加密Alice在[0,p-1]=[0,2578]内任选r为853，计算： c1≡gr(modp)≡2853(mod2579)≡435(mod2579) c2≡m∙yr(modp)≡1299*949853(mod2579)≡2396(mod2579)Alice将（c1，c2）=（435，2396）作为密文发给Bob。（3）解密Bob计算： m≡c2∙w(modp)≡c2*(c1x)-1(modp) ≡(c2*c1p-1-x)(modp)≡(2396*4352579-1-765)(mod2579)≡(2396*4351813)(mod2579)≡1299(mod2579)234.4背包密码体制定理4.3.1由超递增序列a1，a2，…，an及k确定的超递增背包问题是容易求解的。（即对于背包问题： 其中已知超递增序列a1，a2，…，an及k，容易求出X=(x1,x2,……,xn)）254.4背包密码体制1.密钥产生（1）随机选取一个超递增序列（e1，e2，…，en），作为用户的私钥加以保存，记为PR；（2）选取一对大的互素的数w和N，把序列（e1，e2，…，en）变换为： T(ei)≡w∙ei(modN)即做MH变换，将一个超递增序列转换为一个普通序列后作为公钥，记为PU；（3）将公钥PU=（T(e1)，T(e2)，…，T(en)）加以公布。264.4背包密码体制【以下说明如何按超递增序列（e1，e2，…，en）从c’中还原mi？ 因为c=E(m)=m1T(e1)+m2T(e2)+…+nT(en)=,而T(ei)≡w∙ei(modN) 所以c≡,c∙w-1≡

于是c’≡ 由已知w和N互素，则有w∙w-1≡1(modN)， 因此c’≡ 其中，已知c’和ei，求mi，即按超递增序列（e1，e2，…，en）从c’中还原mi，就变成求解特殊的背包问题，是容易求解的，因此解密是容易进行的。】294.4背包密码体制关于背包密码体制的安全问题说明如下。由于 c=

是个普通背包问题，由公开信息c和T(ei)求出明文是难解问题，所以破译是困难的。而解密时，是按超递增序列（e1，e2，…，en）从c’中还原mi，即由私钥ei和c’求解超递增背包 问题c’≡，这是个易解问题，因此解密容易进行的。Merkle和Hellman的背包密码体制提出后，悬赏以求破译者，两年后被RSA的发明者之一沙米尔攻破。尽管二人又做了改进，但最终出现了一种新的破译方法，彻底结束了背包公钥密码体制的历史使命。304.5本章总结（1）公开密钥密码体制的基本概念；（2）RSA的密钥产生、加密及解密过程；（3）背包体制的密钥产生、加密及解密过程；（4）ELGamal体制的密钥产生、加密及解密过程；课堂练习： 如果选择素数p=101和q=113，选取e=3533，计算RSA的公钥和私钥。314.6思考及作业题1、在使用RSA公钥体制中，已截获发给某用户的密文为c=10，该用户的公钥为e=5，n=35，那么明文是多少？为