公钥密码体制课件.pptVIP

5.1公钥密码体制的基本原理公钥密码体制采用了两个不同的密钥，这对在公开的网络上进行必威体育官网网址通信、密钥分配、数字签名和认证有着深远的影响。

5.1.1对称算法的不足密钥管理量的困难：两两分别用一个密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100时，共4,995个；n=5000时增加到12,497,500个。密钥建立问题：对协商密钥的信道的安全性的要求比正常的传送消息的信道的安全性要高。数字签名的问题：传统加密算法无法实现抗抵赖的需求。

5.1.2公钥密码体制的起源公钥密码又称为双钥密码和非对称密码，是1976年由qDiffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的,见CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-126q

5.1.3公开密钥密码的重要特性：加密与解密由不同的密钥完成q加密:X→Y:Y=E(X)KU解密:Y→X:X=D(Y)=D(E(X))KRKRKU知道加密算法,从加密密钥得到解密密钥在计算上是不可行的。（单向函数的性质）qq两个密钥中任何一个都可以用作加密而另一个用作解密(单向函数的交换性，不是必须的)X=D(E(X))=E(D(X))KRKUKUKR

基于公开密钥的加密过程图4.1公钥密码体制的通信必威体育官网网址过程

基于公开密钥的鉴别过程图4.2公钥密码体制的数字签名和验证签名过程

公钥密钥的应用范围加密/解密数字签名(身份鉴别)密钥交换

5.1.4公钥密码系统基本思想和要求1、涉及到各方：发送方、接收方、攻击者2、涉及到数据：公钥、私钥、明文、密文3、公钥算法的条件：–产生一对密钥是计算可行的；–已知公钥和明文，产生密文是计算可行的；–接收方利用私钥来解密密文是计算可行的；–对于攻击者，利用公钥来推断私钥是计算不可行的–已知公钥和密文，恢复明文是计算不可行的；–(可选)加密和解密的顺序可交换。

5.1.5部分数学基础涉及计算复杂性、近世代数等内容。严格单向函数q一个单射函数f:如果下述条件成立：存在一个有效的方法，对所有的x∈X可计算f（x），但不存在一个有效的办法由y=f（x）计算x,所有的y∈Y。则称X→Y称为是严格单向函数。

陷门单向函数q单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=f(x)是容易的；k(2)给定y,计算x使x=fk-1(y)是不可行的。(3)存在k，已知k时,对给定的任何y，若相应的x存在，则计算x使fk-1(x)是容易的。

5.1.6公钥密码基于的数学难题背包问题q大整数分解问题（TheIntegerFactorizationProblem,RSA体制）qq离散对数问题：有限域的乘法群上的离散对数问题(TheDiscreteLogarithmProblem,ElGamal体制）q椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem,类比的ElGamal体制）q?大整数分解问题和离散对数是构造RSA算法的重要基础

整数因子分解问题许多密码系统的安全性都依赖于整数因子分解的困难性。如RSA加密方案，RSA签名方案和Rabin公钥加密方案。定义：给定一个正整数n，找到它的素因子，即n=p1e1p2e2…pkek,这里p是不同的素数，并且e≥1。如：i×3i91=7×13;3600=242×52至今没有有效的求解方法。

指数函数及其性质指数函数y=amodp，已知x求y是一x个可解问题，但其逆过程：已知y求x称为离散对数问题，所以指数函数被认为是一个单向函数。Fermat定理：p素数，a是整数且不能被p整除，则:ap-1≡1modp

乘法逆元：n是整数qq当ax=1modn，x是a的乘法逆元。a的逆元记作a-1，根据Fermat定理，p是素数，若gcb(a,p)=1，ap-2modp是a的乘法逆元。Euclid计算公因数gcd(a，b)=gcd（b，amodb）;可以通过扩展的Euclid算法可以算:ed=kφ(n)+1知道e，d，φ(n)其中两个求另一个。因此：aed≡amodn

Euler定理:若a与n为互素的正整数,则: