1、1公钥密码体制概述 1976年Diffie和Hellman的“New directions in cryptography”导致了密码学上的一场革命，开创了公钥密码学的新纪元。他们首次证明了在发送端和接收端无密钥传输的保密通信是可能的。 1977年Rivest，Shamir和Adleman提出了RSA公钥密码算法。 90年代逐步出现椭圆曲线密码等其他公钥算法。n公钥公钥密码体制，又称为双钥双钥或非对称非对称密码体制 密码系统有两个密钥，即加密密钥和解密密钥不同，从一个难于推出另一个。这两个密钥一个是公开的，一个是秘密的，分别称为公开密钥和私有密钥，公开密钥是对外公开的，即所有的人都可知，私有密
2、钥是只有特定的用户方能拥有。2公钥密码体制概述 公钥密码体制与私钥密码体制的最大不同点就是：加密密钥和解密密钥不同，从一个难于推出另一个。在公钥密码体制中，将这两个不同的密钥区分为公开密钥PK(Public Key)和私有密钥SK(Secrete Key）。 六个组成部分：明文、密文；公钥、私钥；加密算法、解密算法3公钥密码体制模型A加密B解密A加密B解密明文明文明文密文密文加密模型加密模型认证模型认证模型B的公钥B的私钥A的私钥A的公钥明文4公钥密码体制的特点 加密和解密能力分开。 可以实现多个用户加密的消息只能由一个用户解读（用于公共网络中实现保密通信）。 可实现只能由一个用户加密消息而使
3、多个用户可以解读（可用于认证系统中对消息进行数字签字）。 无需事先分配密钥。 重要特点仅根据密码算法和加密密钥来确定解密密钥在计算上不可行。 有些算法如RSA还具有：两个密钥中的任何一个都可用来加密，另一个用来解密。 优点：能很好解决私钥加密中由于密钥数量过多导致的管理难和费用高等问题，也不用担心传输中的私钥泄漏，保密性能优于私钥加密。 缺点：加密算法复杂，加密速度难以达到理想状态。5公钥密码体制依赖的基础 传统的对称密码体制依赖的基础是替代和置换两种转换思想。与对称密码体制不同的是，公钥密码体制依赖的基础是数学上的某类问题的求解困难。 经典的公钥密码算法RSA、椭圆曲线密码算法ECC等都是依
4、赖某类数学问题的，它们共同的特点是基于某个单向陷门函数。单向陷门函数 y=fk(x) 是指同时满足下列条件的一类可逆函数：6公钥密码体制依赖的基础 函数是一一映射关系，也就是说，对于每个函数值y，只有唯一的一个原象x与之对应； 给定x与关键参数k,函数y=fk(x)很容易计算； 给定y，存在某个关键参数k，在未知k时，由y计算出x非常困难，即在未知k的条件下，逆函数x=f-1k(y)的计算相当复杂，实际上是不可行的；在已知k时，对给定的任何y，则逆函数x=f-1k(y)很容易计算； 给定y和参数k，无法从函数y=fk(x)推导出影响其逆函数f-1的关键参数k。 设计任何一种公钥密码方案，所要做
5、的工作就是寻找这样的单向陷门函数，其中陷门信息就是私钥，也就是上面所列举的关键参数k。7公钥密码系统的特征 根据密码系统的组成以及公钥密码体制自身的特点，一个公钥密码系统可以表示为：加密算法E、解密算法D、公钥/私钥(PK/SK)对、明文M、密文C六个元素，且各元素必须要满足以下条件：8公钥密码系统的特征 密钥。要满足两点要求：公钥/私钥(PK/SK)对容易产生，且私钥除了生成密钥的用户自己知道之外，其他任何人都不可知；已知公钥PK，无法计算出私钥SK，即公钥密码系统所要满足的基本条件之一是从公开密钥无法通过计算得到私有密钥。9公钥密码系统的特征 加密算法E。要满足两点要求：已知公钥PK，对任
6、何明文M，由E计算出密文C非常容易，即C = EPK(M) 易计算，或者已知私钥SK，对任何信息M，由E计算数字签名也非常容易，即 C = ESK(M) 易计算。 解密算法D。要满足两点要求：已知私钥SK，对任何密文C，由D容易计算出明文M，或者已知公钥PK，对任何用SK所做的数字签名C，容易通过D计算，得到签名前的信息；但是已知公钥PK、密文C，以及解密算法D，无法由三者推导出明文M或者私钥SK。即由公钥、密文和解密算法 ，推导明文和解密密钥都是计算不可行的。 一个设计良好的密码系统，加密算法E和解密算法D应该都是公开的，该原则同样适用于公钥密码系统，公钥密码系统中唯一需要保密的就是私钥SK
7、。10公钥密码体制加解密过程 假设网络上的两个用户Alice和Bob需要进行秘密通信，为了防止攻击者Eve窃听信息，Alice和Bob选择使用公钥密码体制加密传输的信息。Alice是信息的发送方；Bob是信息的接收方。11公钥密码体制加解密过程 Alice与Bob产生公钥/私钥对：PKA/SKA，PKB/SKB。 Alice与Bob通过某种机制公布各自的公钥PKA与PKB，例如将公钥放到一个公共的服务器，供其他用户查询。 Alice通过查询公共服务器获得Bob的公钥PKB。如果Alice欲给Bob发送报文M，他就用Bob的公钥PKB加密报文。已知待加密的明文M以及Bob的公钥PKB，Alice
8、很容易通过加密算法E计算出密文，即 C = EPKB(M)。 （4）接收方Bob收到Alice发送的信息之后，使用自己的私钥SKB解密报文。已知密文C和私钥SKB，Bob很容易通过解密算法计算出明文M，即 M=DSKB(C)。 假设攻击者Eve窃听到Alice发送的报文，虽然Eve可查询获得Bob的公钥PKB，但从PKB确定Bob的私钥SKB 在计算上是不可行的，因此Eve无法获知Bob的私钥 SKB ；仅知道公开密钥和密文，无法计算出明文M。因此攻击者Eve无法得到Alice发给Bob的密码信息。12公钥密码体制 公钥密码技术的主要价值是解决下列问题： 1）密钥分发； 2）大范围应用中，数据
9、的保密性和完整性； 3）实体鉴别； 4）不可抵赖性； 公钥密码体制的应用可分为3类： a）加密/解密：发送方用接收方的公钥对消息加密。 b）数字签名：发送方用其私钥对消息签名。签名可以对整条消息加密或对消息的一个小的数据块加密来产生，其中该小的数据块是整条消息的函数。 c）密钥交换：通信双方交换会话密钥。有几种不同的方法可用于密钥交换，这些方法都使用了通信一方或双方的私钥。13公钥密码体制 有些算法可用于上述三种应用，而其他一些算法则只适用其中一种或两种应用。算法加密/解密 数字签名 密钥交换RSA是是是椭圆曲线密码是是是Diffie-Hellman否否是DSS否是否14公钥密码体制 自197
10、6年提出公钥密码系统以来，密码专家们已设计出多种公钥密码算法，这些算法的共同点都是基于某类数学难题，通过找到该类问题的某个单向陷门函数实现对数据的加密和解密。 依据所依赖的数学难题类别划分，主要有以下3类系统：基于大整数因子分解问题的公钥系统，典型代表是RSA算法；基于有限域椭圆曲线离散对数问题的公钥系统，典型代表是ECC算法；基于有限域离散对数问题的公钥系统，典型算法是DSA。15若干较有影响的公钥加密算法 RSA算法：基于大整数素因子分解问题，目前认为是安全的。 Merkle-Hellman背包体制：基于子集和问题，已证明不安全。 McEliece体制：基于余代数编码中的线性解码问题，目前
11、认为是安全的。 ElGamal体制：基于有限域上的离散对数问题，目前认为有一定安全性。 Chor-Rivest背包体制：基于子集和问题，目前认为是安全的。 椭圆曲线密码：基于椭圆曲线上的离散对数问题，是对ElGamal体制的改进，目前认为是安全的。 有限自动机密码：基于有限自动机的求逆问题，目前认为有一定安全性。16RSA算法1976年Deffie和Hellman提出公钥密码系统思想之后，1977年麻省理工学院的Ron Rivest、Adi Shamir和Len Adleman三位学者研制了RSA(Rivest-Shamir-Adleman)公钥密码方案，该方案于1978年首次发表，从那以后至
12、今，RSA算法是被使用最多的公钥密码方案。17RSA算法依赖的数学问题 RSA算法基于“大整数质因子分解”非常困难这一数学难题，这里大整数通常有几百位长。RSA算法依赖以下几个数论定理： 模运算的性质：正整数n是素数，集合Zn = 0，1，2.，(n-1) 表示小于n的所有非负整数集合，则对于集合Zn 中的每一个非零整数wZn，均存在一个z，满足公式 w z = 1 mod n，我们称z是w的乘法逆元，且n是它们的模。18RSA算法依赖的数学问题 费马定理：如果p是素数，a是不能被p整除的正整数，则： ap-1 1 mod p 例如：P=7， a=2，则27-1 =26 = 64，64 mod
13、 7 = 119RSA算法依赖的数学问题 欧拉函数：正整数n的欧拉函数是指小于n且与n互素的正整数个数，通常记为(n)。 对于任一素数p，显然有：(p) p 1， 例如：设p=3，小于3且与3互素的正整数为1，2，因此(3) = 2；类似地，当p=7时，小于7且与7互素的正整数为1，2，3，4，5，6，因此(7) = 6。 假定有两个不同的素数p和q，n是p与q之积，即 n = p q，则有如下公式关系：(n)=(pq)= (p)(q)=(p-1)(q-1) 例如：取n=21，(21) = (3) (7) = (3-1) (7-1) = 2 6 = 12，其中这12个整数是1，2，4，5，8，
14、10，11，13，16，17，19，20 。20RSA算法依赖的数学问题 欧拉定理： 任何两个互素的整数a和n，有如下关系： a(n) 1 mod n 例如：a = 3；n=8；由(3)欧拉函数的定义，(8) = 4；则a(n) = 34 = 81 =108 +1 1 mod 8 1 mod n21RSA算法依赖的数学问题 （）欧几里德(Euclid)算法：该算法主要的思想是：用一个简单的方法确定两个正整数的最大公因子，并且如果这两个整数互素，通过扩展该算法能确定它们各自的乘法逆元。 22欧几里德(Euclid)算法设，求和的最大公因子（，）以及（，）中的与。 令r0=a, r1=n，利用辗转
15、相除法可得： r0 = r1q1 + r2, 0 r2 r1 r1 = r2q2 + r3, 0 r3 r2 rm-2 = rm-1qm-1 + rm, 0 rm rm-1 rm-1 = rmqm + rm+1, rm+1 = 0 (a,n) = (r0, r1) = (r1, r2) = = (rm-1, rm) = (rm, 0) = rm. 由上述关系式可以得到（，）中的与23欧几里德(Euclid)算法24欧几里德(Euclid)算法25欧几里德(Euclid)算法26欧几里德(Euclid)算法27RSA算法密钥产生过程 随机选择两个秘密的大素数 p与q，且p q = n。 为了增强
16、算法的安全性，避免攻击者通过数学攻击的方法找到n的欧拉函数(n)，从而攻破RSA密码方案，RSA算法的设计者建议：1. p与q长度应该只差几个数字，这样对于1024位的密钥来说，p与q都应该约位于区间1075 ,10100内；2. p-1 与 q-1 都应有一个大的素因子；3. gcd（p-1，q-1）应该较小。另外，已经证明，若 en 且 d160 时受到青睐。47Zp上的椭圆曲线 不是所有的椭圆曲线都适合加密。 y2 = x3 + ax + b是一类可以用来加密的椭圆曲线，也是最简单的一类。把 y2 = x3 + ax + b 这条曲线定义在Zp上，x，y和系数都属于Zp 。这里p为大于3
17、的素数，a，b Zp，4a3 + 27b2 0 mod p。 记Zp上满足该方程的整数对（x，y）和无穷远点O组成的集合为Ep（a，b）。则基于该集合可定义一个有限阿贝尔群（ 4a3 + 27b2 0 mod p 等价于x3 + ax + b 无重复因子）。 Zp上的椭圆曲线就是由集合Ep（a，b）中的点组成。48Zp上的椭圆曲线49Zp上的椭圆曲线运算 Ep（a，b）上的加法运算与定义在实数域上的椭圆曲线中描述的代数方法是一致的。对任何点P，Q Ep（a，b）： P+O=P 若P=（xP，yP），则 P+（ xP，-yP）= O。点（ xP，-yP）是P的负元，记为-P。 例如，对 E23（
18、1，1）上的点P=（13，7），有-P=（13，-7），而-7 mod 23=16.因此，-P=（13，16），该点也在E23（1，1）上。50Zp上的椭圆曲线运算 若P=（xP，yP）和 Q=（xQ，yQ），且P-Q，则R=P+Q=（xR，yR）由下列规则确定： xR= （2 - xP xQ）mod p yR = （xP xR） - yP）mod p，其中 乘法定义为重复相加。如4P=P+P+P+P。 为确定各种椭圆曲线密码的安全性，需要知道定义在椭圆曲线上的有限阿贝尔群中点的个数。在有限群Ep（a，b）中，点的个数N的范围是：P+1-2pN P+1+2p 所以Ep（a，b）上点的个数约等于
19、Zp中元素的个数，即p个元素。QPpyaxQPpxxyyPPPQPQ，若，若mod)23(mod)(251有限域F2m上的椭圆曲线F2m上的椭圆曲线与Zp上的三次方程不同，可表示成 y2 + xy = x3 + ax2 + b这里a，b（0） F2m，或曲线方程 y2 + cy = x3 + ax + b这里a，b，c（0） F2m上述曲线上的所有有理点（x，y都在F2m上）和无穷远点组成的集合记为E F2m （a，b），有限域F2m上的椭圆曲线就是由该集合中的点组成。52有限域F2m上的椭圆曲线运算 对任何P E F2m （a，b），P+O=P。 若 P=（xP，yP），则P+ （xP， x
20、P +yP）=O。点（xP， xP +yP）是P的负元，记为-P。 1）方程为）方程为 y y2 2 + xy = x+ xy = x3 3 + ax+ ax2 2 + b + b 时时， 若P=（xP，yP）和 Q=（xQ，yQ）都属于F2m ，且P-Q， PQ，则R=P+Q=（xR，yR）由下列规则确定： xR= 2 + + a + xP + xQ yR = （xP + xR） + xR + yP其中， =（ yQ + yP）/（ xQ + xP） 若 P=（xP，yP），则R=2P= （xR，yR）由下列规则确定： xR= 2 + + a yR = （+1）xR + xP2 其中， =
21、xP + yP / xP53有限域F2m上的椭圆曲线运算 2）方程为）方程为 y y2 2 + cy = x+ cy = x3 3 + ax + b+ ax + b 时 对任何P=（xP，yP）和 Q=（xQ，yQ）都属于F2m ， 其中 ，否则，若)(,ORRPQPQ,yxcxyxxQPQPcaxQPxxxxyyxPQPQPQPR，若，若222QPcyxxcaxQPcyxxxxyyyPRPPPRPQPQPR，若，若)()(254椭圆曲线密码椭圆曲线密码ECCECC算法依赖的数学问题算法依赖的数学问题 椭圆曲线离散对数问题给定椭圆曲线E及该椭圆曲线上的一点P，kP 表示k个P相加，k为某整数，
22、如果椭圆曲线上存在一点Q，能够满足方程 Q = kP，那么椭圆曲线离散对数问题就是给定点P和点Q，求解k的问题，在数学上该问题是同时涉及整数因式分解和离散对数的难题。ECC算法就是基于“椭圆曲线离散对数问题”难以求解而设计的，给定P和k容易通过方程Q = kP计算Q；但是反过来，给定Q和P，求k在计算上是不可行的，因此我们可以设定k为私钥。55ECC算法密钥的选择 基于椭圆曲线密码体制的ECC算法在加解密之前，首先要给出椭圆曲线域的一些参数，如基点P，阶n ，以确定具体的椭圆曲线。 ECC算法密钥的产生是都是建立在某个有限域的椭圆曲线上，设给定一个具有q个元素有限域的椭圆曲线E，E 的基点是P
23、，P的阶为n。 下面介绍一种利用椭圆曲线实现加解密的方法，这种方法很简单。 密钥的选择： （1） 密钥的产生者在区间2，n-1随机选取某整数k； （2） 计算Q = kP。 则Q就是公钥，私钥是k。 56一种ECC算法加解密过程 假设网络上的用户Alice和Bob要进行保密通信，它们选择ECC算法加密通信的报文。Alice与Bob知道同一条椭圆曲线E，并已分别产生公钥/私钥对QA/kA，QB/kB，Alice欲发送明文m送给Bob，并且已获知Bob的公钥QB。Alice加密过程如下：（1）首先要将明文m编码成椭圆曲线上的点Pm，Pm为(Xm，Ym)；（2） Alice随机选择整数k2,n-1；
24、（3）计算 kP = R1 (X1，Y1)，kQB = R2 (X2，Y2）；如果X2 =0；则返回到（2）； (4) 则密文C由 R1，Pm + R2 组成； 57一种ECC算法的加解密过程 Bob收到密文C后，解密过程如下：（1）计算 kBR1 = kBkP = kkBP = kQB（2）Bob利用密文C的第二点的值R2 + Pm 减去由（1）计算得到的结果kQB，即 Pm + R2 kQB = Pm + kQB kQB = Pm；（3）Bob得到椭圆曲线上点Pm ，然后按照某种解码方法从点Pm获取明文m。举例：取 p=751，Ep(-1,188),即其椭圆曲线方程为y2 = x3 -x
25、+ 188，基点为（0，376）。假设A要将编码为椭圆曲线上点 Pm（562，201）的消息发给B，且A挑选的随机数为k=386，B的公钥为（201，5），那么有386（0，376）=（676，558）和（562，201）+386（201，5）=（385，328）。于是A发送的密文是（676，558），（385，328）。58Menezes-Vanstone 椭圆曲线密码体制 Menezes-Vanstone 椭圆曲线密码体制是ElGamal密码体制在椭圆曲线上的模拟，它是由A J Menezes与S A Vanstone 在1993年12月提出的。 ElGamal 公钥密码体制是1985年7
26、月由Taher ElGamal 发明的，它是建立在解有限乘法群上的离散对数问题的困难性基础之上的一种公钥密码体制。该密码体制至今仍被认为是一个安全性能较好的公钥密码体制，目前它被广泛用于许多密码协议中。59ElGamal 加密算法 ElGamal 算法既可用于加密，也可用于签名。加密算法描述如下： （1）公开参数：首先选取大素数p，并取是乘法群 Zp*=1，p-1的一个生成元。 （2）密钥生成：再随机选取整数d：0dp-1，并计算=d mod p。这里p与是公开参数，是公开的加密密钥（公钥），d是保密的解密密钥（私钥）。 （3）加密运算：对明文m Zp*，随机选取整数k：0k3是一个素数，E是
27、有限域Zp上的由方程y2 = x3 + ax + b 表示的椭圆曲线，E（Zp）是相应的阿贝尔群。G是该群中具有较大素数阶n的一个点。 （2）密钥生成：随机选取整数d：2dn-1，计算P=dG。d是保密的密钥，P是公开钥。 （3）加密运算：对任意明文m=（m1，m2） Zp* Zp*，随机选取一个秘密整数k：1kn-1,使得（x，y）=kP，满足x与y均为非零元素。并计算 C0=kG，c1= m1 x mod p，c2= m2 y mod p， 明文m=（ m1，m2）经加密后的密文为（C0，c1，c2）。密文空间为E（Zp） Zp* Zp* 。 （4）解密运算：对任意密文c=（C0，c1，c
28、2），计算标量乘 dC0 =（x，y），计算 m1 = c1 x-1 mod p，m2 = c2 y-1 mod p，即得c解密后的明文为（m1，m2）。63ECC 算法的安全性分析ECC算法的安全性依赖于椭圆曲线离散对数问题计算的困难性，如果离散对数问题容易计算，从用户的公钥能够推导出私钥，那么整个密码体制就会坍塌。除此之外，椭圆曲线E的选择也非常重要。为防止穷搜索攻击，有限域的阶应是一个较大的素数幂。解有限群离散对数问题的通用方法均可用来解椭圆曲线上阿贝尔群上的离散对数问题。但是关于解有限域乘法群上的指数演算法则对椭圆曲线离散对数问题(ECDLP)不适用，即目前还没有找到对ECDLP适用的
29、类似算法。已知的对ECDLP最好的算法是（并行）Pollard-算法。解 ECDLP 比解有限域上的离散对数问题 FFDLP 要困难得多，因而椭圆曲线密码体制比同等规模的Zp*上的 ElGamal 公钥密码体制安全性要强很多。64ECC算法的优点椭圆曲线加密算法ECC与其他公钥算法（如RSA）相比有很多优点： a)安全性能更高： 加密算法的安全性能一般通过该算法的抗攻击强度来反映。ECC和其他几种公钥系统相比，其抗攻击性具有绝对的优势。椭圆曲线的离散对数（ECDLP）计算困难性在计算复杂度上目前是完全指数级，而RSA是亚指数级的。这体现ECC比RSA的每bit安全性能更高。 b)计算量小和处理
30、速度快： 在一定的相同的计算资源条件下，在私钥 的处理速度上（解密和签名），ECC远比RSA、DSA 快得多。ECC总的速度比RSA、DSA要快得多。 同时ECC系统的密钥生成速度比RSA快百倍以上。 因此在相同条件下，ECC则有更高的加密性能。65ECC算法的优点 c)存储空间占用小： ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多。160位ECC与1024位RSA、DSA具有相同的安全强度，210位ECC则与2048位RSA、DSA具有相同的安全强度。意味着它所占的存贮空间要小得多。这对于加密算法在资源受限环境上（如智能卡等）的应用具有特别重要的意义。 d)带宽要求低： 当对长消息
31、进行加解密时， 三类密码系统有相同的带宽要求，但应用于短消息时ECC带宽要求却低得多。而公钥密码系统多用于短消息，例如用于数字签名和用于对对称系统的会话密钥传递。带宽要求低使ECC在无线网络领域具有广泛的应用前景。 6667ECC 算法的缺点 公开密钥加密系统是基于尖端的数学难题，计算非常复杂，实现难度大； 安全性高，但实现速度却远赶不上对称密钥加密系统。 随着计算能力的提高，从安全性角度考虑，对密钥长度的要求越来越高。相对于其他公钥密码算法，ECC逐渐体现出其优越性。但是自从使用公钥密码体制以来，实际应用中，RSA算法因为原理简单被广泛使用，ECC算法在实际应用中相对比较少。但是随着时间的推
32、移，ECC算法理论不断完善，相信它逐渐会被应用到实际系统中。68ECC算法应用与现状算法在标准化中应用 国内外软硬件中应用69ECC算法在标准化中应用 ECC的特点使它在某些领域（如手机、智能卡）的应用将取代RSA，并成为通用的公钥加密算法。 许多国际标准化组织（政府、工业界、金融界、商业界等）已将各种椭圆曲线密码体制作为其标准化文件向全球颁布。 ECC标准大体可以分为两种形式： 一类是技术标准，即描述以技术支撑为主的ECC体制，主要有 IEEEP1363、ANSIX9.62、ANSIX9.63、SEC1、SEC2、FIP1862、ISO/IEC148883。规范了ECC的各种参数的选择，并给
33、出了各级安全强度下的一组 ECC参数。 另一类是应用标准，即在具体的应用环境中建议使用 ECC技术，主要有ISO/IEC 15946、IETFPKIX、IETFTLS、WAPWTLS 等。70ECC在软硬件中应用 在标准化的同时，一些基于标准（或草案）的各种椭圆曲线加密、签名、密钥交换的软、硬件也相继问世。 美国RSA数据安全公司在1997年公布了包含ECC的密码引擎工具包BSAFE4.0。 以加拿大Certicom为首的安全公司和工业界联合也研制、生产了以椭圆曲线密码算法为核心的密码产品，还提出了各种安全条件下对椭圆曲线离散对数攻击的悬赏挑战。 德国、日本、法国、美国、加拿大等国的很多密码学
34、研究小组及一些公司实现了椭圆曲线密码体制。 我国也有一些密码学者做了这方面的工作。许多标准化组织已经或正在制定关于椭圆曲线的标准，同时也有许多的厂商已经或正在开发基于椭圆曲线的产品。71Diffie-Hellman 密钥交换 Diffie 和 Hellman 在1976年首次提出了公钥算法，这篇影响深远的论文给出了公钥密码学的定义，该算法通常被称为Diffie-Hellman 密钥交换。 由于该算法本身限于密钥交换（不能用于加密、解密）的用途，被许多商用产品用作密钥交换技术，因此该算法通常称之为Diffie-Hellman密钥交换。这种密钥交换技术的目的在于使得两个用户安全地交换一个秘密密钥以
35、便用于以后的报文加密。 Diffie-Hellman密钥交换算法的有效性依赖于计算一般有限域上离散对数的难度。 一个素数p的原根，是一个整数，且其幂可以产生1 到p-1之间的所有整数，也就是说，如果a是素数p的一个原根，那么数值 a mod p, a2 mod p, ., ap-1 mod p 是各不相同的整数，它是整数1到p-1的一个置换。72Diffie-Hellman 密钥交换算法73Diffie-Hellman 密钥交换算法74Diffie-Hellman 密钥交换算法75Diffie-Hellman 密钥交换协议下图给出了一个利用Diffie-Hellman计算的简单协议。 76Di
36、ffie-Hellman 密钥交换协议77Diffie-Hellman 算法优点 Diffie-Hellman算法具有两个吸引力的特征： 仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会。 除对全局参数的约定外，密钥交换不需要事先存在的基础结构。78Diffie-Hellman 算法缺点79Diffie-Hellman 算法的椭圆曲线版本利用椭圆曲线可如下实现密钥交换。 首先，挑选一个大整数q以及有限域上椭圆曲线方程中的参数a和b（见前面），这里q为素数p或是形式为2m的整数。由此可定义出点的椭圆群Eq（a，b）； 其次，在Eq（a，b）中挑选基点G=（x1，y1），G的阶为一个非常大的数n。 Eq（a，b）和G是该密码体制中通信各方均已知的参数。用户A和B之间完成密钥交换过程如下：80Diffie-Hellman 算法的椭圆曲线版本 1. A选择一个小于n的整数nA作为其私钥，然后产生其公钥PA= nAG；该公钥是Eq（a，b）中的一个点。 2. B可类似选择私钥 nB并计算公钥PB。8182精品课件精品课件！83精品课件精品课件！84作业 自选题目，要求与本课程相关，写一篇小论文。可以是自己原创性的，也可以是在查资料的基础上理解总结整理获得，也可以谈谈自己的想法，忌原原本本照搬照抄。最迟在2009年1月12日以前交打印版。
