第4章公钥密码算法ppt课件

1、1,第4章 公钥密码算法,一、公钥密码体制概述 二、公钥加密算法 RSA、ElGamal、椭圆曲线密码、Diffie-Hellman 密钥交换算法,2,公钥密码体制概述,1976年Diffie和Hellman的“New directions in cryptography”导致了密码学上的一场革命，开创了公钥密码学的新纪元。他们首次证明了在发送端和接收端无密钥传输的保密通信是可能的。 1977年Rivest，Shamir和Adleman提出了RSA公钥密码算法。 90年代逐步出现椭圆曲线密码等其他公钥算法。 公钥密码体制，又称为双钥或非对称密码体制 密码系统有两个密钥，即加密密钥和解密密钥不同

2、，从一个难于推出另一个。这两个密钥一个是公开的，一个是秘密的，分别称为公开密钥和私有密钥，公开密钥是对外公开的，即所有的人都可知，私有密钥是只有特定的用户方能拥有,3,公钥密码体制概述,公钥密码体制与私钥密码体制的最大不同点就是：加密密钥和解密密钥不同，从一个难于推出另一个。在公钥密码体制中，将这两个不同的密钥区分为公开密钥PK(Public Key)和私有密钥SK(Secrete Key）。 六个组成部分： 明文、密文；公钥、私钥； 加密算法、解密算法,4,公钥密码体制模型,明文,明文,明文,密文,密文,加密模型,认证模型,B的公钥,B的私钥,A的私钥,A的公钥,明文,5,公钥密码体制的特点

3、,加密和解密能力分开。 可以实现多个用户加密的消息只能由一个用户解读（用于公共网络中实现保密通信）。 可实现只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。 无需事先分配密钥。 重要特点 仅根据密码算法和加密密钥来确定解密密钥在计算上不可行。 有些算法如RSA还具有：两个密钥中的任何一个都可用来加密，另一个用来解密。 优点：能很好解决私钥加密中由于密钥数量过多导致的管理难和费用高等问题，也不用担心传输中的私钥泄漏，保密性能优于私钥加密。 缺点：加密算法复杂，加密速度难以达到理想状态,6,公钥密码体制依赖的基础,传统的对称密码体制依赖的基础是替代和置换两种转换思

4、想。与对称密码体制不同的是，公钥密码体制依赖的基础是数学上的某类问题的求解困难。 经典的公钥密码算法RSA、椭圆曲线密码算法ECC等都是依赖某类数学问题的，它们共同的特点是基于某个单向陷门函数。单向陷门函数 y=fk(x) 是指同时满足下列条件的一类可逆函数,7,公钥密码体制依赖的基础,函数是一一映射关系，也就是说，对于每个函数值y，只有唯一的一个原象x与之对应； 给定x与关键参数k,函数y=fk(x)很容易计算； 给定y，存在某个关键参数k，在未知k时，由y计算出x非常困难，即在未知k的条件下，逆函数x=f-1k(y)的计算相当复杂，实际上是不可行的；在已知k时，对给定的任何y，则逆函数x=

5、f-1k(y)很容易计算； 给定y和参数k，无法从函数y=fk(x)推导出影响其逆函数f-1的关键参数k。 设计任何一种公钥密码方案，所要做的工作就是寻找这样的单向陷门函数，其中陷门信息就是私钥，也就是上面所列举的关键参数k,8,公钥密码系统的特征,根据密码系统的组成以及公钥密码体制自身的特点，一个公钥密码系统可以表示为：加密算法E、解密算法D、公钥/私钥(PK/SK)对、明文M、密文C六个元素，且各元素必须要满足以下条件,9,公钥密码系统的特征,密钥。要满足两点要求：公钥/私钥(PK/SK)对容易产生，且私钥除了生成密钥的用户自己知道之外，其他任何人都不可知；已知公钥PK，无法计算出私钥SK

6、，即公钥密码系统所要满足的基本条件之一是从公开密钥无法通过计算得到私有密钥,10,公钥密码系统的特征,加密算法E。要满足两点要求：已知公钥PK，对任何明文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。即由公钥、密文和解密算法 ，推导明文和解密密钥都是

7、计算不可行的。 一个设计良好的密码系统，加密算法E和解密算法D应该都是公开的，该原则同样适用于公钥密码系统，公钥密码系统中唯一需要保密的就是私钥SK,11,公钥密码体制加解密过程,假设网络上的两个用户Alice和Bob需要进行秘密通信，为了防止攻击者Eve窃听信息，Alice和Bob选择使用公钥密码体制加密传输的信息。Alice是信息的发送方；Bob是信息的接收方,12,公钥密码体制加解密过程,Alice与Bob产生公钥/私钥对：PKA/SKA，PKB/SKB。 Alice与Bob通过某种机制公布各自的公钥PKA与PKB，例如将公钥放到一个公共的服务器，供其他用户查询。 Alice通过查询公共

8、服务器获得Bob的公钥PKB。如果Alice欲给Bob发送报文M，他就用Bob的公钥PKB加密报文。已知待加密的明文M以及Bob的公钥PKB，Alice很容易通过加密算法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。

9、因此攻击者Eve无法得到Alice发给Bob的密码信息,13,公钥密码体制,公钥密码技术的主要价值是解决下列问题： 1）密钥分发； 2）大范围应用中，数据的保密性和完整性； 3）实体鉴别； 4）不可抵赖性； 公钥密码体制的应用可分为3类： a）加密/解密：发送方用接收方的公钥对消息加密。 b）数字签名：发送方用其私钥对消息签名。签名可以对整条消息加密或对消息的一个小的数据块加密来产生，其中该小的数据块是整条消息的函数。 c）密钥交换：通信双方交换会话密钥。有几种不同的方法可用于密钥交换，这些方法都使用了通信一方或双方的私钥,14,公钥密码体制,有些算法可用于上述三种应用，而其他一些算法则只适用

10、其中一种或两种应用,15,公钥密码体制,自1976年提出公钥密码系统以来，密码专家们已设计出多种公钥密码算法，这些算法的共同点都是基于某类数学难题，通过找到该类问题的某个单向陷门函数实现对数据的加密和解密。 依据所依赖的数学难题类别划分，主要有以下3类系统： 基于大整数因子分解问题的公钥系统，典型代表是RSA算法； 基于有限域椭圆曲线离散对数问题的公钥系统，典型代表是ECC算法； 基于有限域离散对数问题的公钥系统，典型算法是DSA,16,若干较有影响的公钥加密算法,RSA算法：基于大整数素因子分解问题，目前认为是安全的。 Merkle-Hellman背包体制：基于子集和问题，已证明不安全。 M

11、cEliece体制：基于余代数编码中的线性解码问题，目前认为是安全的。 ElGamal体制：基于有限域上的离散对数问题，目前认为有一定安全性。 Chor-Rivest背包体制：基于子集和问题，目前认为是安全的。 椭圆曲线密码：基于椭圆曲线上的离散对数问题，是对ElGamal体制的改进，目前认为是安全的。 有限自动机密码：基于有限自动机的求逆问题，目前认为有一定安全性,17,RSA算法,1976年Deffie和Hellman提出公钥密码系统思想之后，1977年麻省理工学院的Ron Rivest、Adi Shamir和Len Adleman三位学者研制了RSA(Rivest-Shamir-Adle

12、man)公钥密码方案，该方案于1978年首次发表，从那以后至今，RSA算法是被使用最多的公钥密码方案,18,RSA算法依赖的数学问题,RSA算法基于“大整数质因子分解”非常困难这一数学难题，这里大整数通常有几百位长。RSA算法依赖以下几个数论定理： 模运算的性质： 正整数n是素数，集合Zn = 0，1，2.，(n-1) 表示小于n的所有非负整数集合，则对于集合Zn 中的每一个非零整数wZn，均存在一个z，满足公式 w z = 1 mod n，我们称z是w的乘法逆元，且n是它们的模,19,RSA算法依赖的数学问题,费马定理： 如果p是素数，a是不能被p整除的正整数，则： ap-1 1 mod p

13、 例如： P=7， a=2， 则27-1 =26 = 64，64 mod 7 = 1,20,RSA算法依赖的数学问题,欧拉函数：正整数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) = (

14、3-1) (7-1) = 2 6 = 12，其中这12个整数是1，2，4，5，8，10，11，13，16，17，19，20,21,RSA算法依赖的数学问题,欧拉定理： 任何两个互素的整数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 n,22,RSA算法依赖的数学问题,欧几里德(Euclid)算法： 该算法主要的思想是：用一个简单的方法确定两个正整数的最大公因子，并且如果这两个整数互素，通过扩展该算法能确定它们各自的乘法逆元,23,欧几里德(Eucl

15、id)算法,设，求和的最大公因子（，）以及（，）中的与。 令r0=a, r1=n，利用辗转相除法可得： 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. 由上述关系式可以得到（，）中的与,24,欧几里德(Euclid)算法,25,欧几里德(Euclid)算法,26,欧几里德(Euclid)算法,27,欧几里德(E

16、uclid)算法,28,RSA算法密钥产生过程,随机选择两个秘密的大素数 p与q，且p q = n。 为了增强算法的安全性，避免攻击者通过数学攻击的方法找到n的欧拉函数(n)，从而攻破RSA密码方案，RSA算法的设计者建议： p与q长度应该只差几个数字，这样对于1024位的密钥来说，p与q都应该约位于区间1075 ,10100内； p-1 与 q-1 都应有一个大的素因子； gcd（p-1，q-1）应该较小。 另外，已经证明，若 en 且 dn1/4, 则d很容易被确定。 计算n的欧拉函数值： (n) = (p-1) (q-1,29,RSA算法密钥产生过程,随机选择一个大的正整数e，e满足小于

17、n且与(n)互素的条件，即e与(n)的最大公因子是1。 (4)根据e，(n)，计算另外一个值d，d是e的乘法逆元，且(n)是它们的模，由模运算及乘法逆元的性质，d e = 1 mod (n)。 则两个二元组(e,n)、(d,n) 构成RSA的密钥对，选择其中任意一个二元组作为公钥，则另外一个就为私钥，在此，我们定义(e,n)为公钥，(d,n)为私钥,30,RSA算法密钥产生过程,例如： 1) 令p = 7，q=11，则n=77； 2) 计算n的欧拉函数值(n) = (7-1) (11-1) = 60； 3) 选择e = 17，e符合小于77，且与欧拉函数值(n)（(n)=60）的最大公因子是1

18、的条件； 4）计算e的逆元d，因为 53 17 = 15 60 +1 1 mod 60，所以当e=17时，d=53（利用欧式算法求）。 因此(17，77)/(53，77)构成一个RSA的公钥/私钥对. 实际应用中，RSA算法的密钥长度至少是比特（指的二进制比特数），即的大小相当于约位十进制数,31,RSA算法加解密过程,RSA算法属于分组加密方案，也就是说明文以分组为单位加密，分组的大小取决于所选的模n的值，明文块每个分组的长度可以相同也可以不同.已知明文的某块分组报文M，公钥(e，n)，私钥(d，n)，则加密过程如下： 对M的e次方幂指数运算结果再做模n运算，所得结果即为密文C，即由M计算C

19、用公式表示为： C = EPK(M) = Me mod n RSA算法加密和解密过程是等价的，解密过程如下： 对C的d次方幂运算结果再做模n运算，所得结果即为明文M，即由C推导M可用公式表示为： M = DSK(C) = Cd mod n,32,RSA算法加解密过程,33,RSA算法加解密过程,34,RSA算法安全性及性能分析,RSA算法的安全性基于大整数因子分解的困难性，即给定大整数n，将n分解为两个素数因子p与q，在数学上已证明是难题，至今没有有效的方法予以解决。 对于一个公钥密码系统的攻击，主要是利用公钥信息来获取私钥信息。对RSA的攻击一般有3种方式： 分解模数n；确定欧拉函数(n)

20、；直接确定d。 可证明，第2种和第3种方式攻击RSA均等价于用第一种方式攻击RSA，即等价于大整数素数分解的困难性。 RSA密码方案的优点在于原理简单，易于使用. 因此，许多使用公钥密码方案的系统都会选用RSA算法,35,RSA算法安全性及性能分析,缺点： RSA的性能比较低。因为算法中使用的模数n以及p与q都是大整数，因此无论是用硬件实现还是软件实现效率都比较低，其中硬件实现的效率是DES的1/1000，软件实现的效率是DES的1/100，由此可见，RSA不适用于对长的明文信息加密，它常常与对称密码体制结合使用，RSA用来加密通信双方的会话密钥，对称密码体制如DES用来加密传输的报文。 实际

21、中，在不影响安全性的条件下，为提高加解密的运算速度，通常选择的公钥比较小,36,RSA算法安全性及性能分析,为了安全起见，RSA方案中要求模数n越来越大。当前，RSA密钥长度要求在1024比特到2048比特之间才有安全保障，在安全要求比较高的政府等部门，需要采用2048比特长的密钥。密钥长度的增加提高了安全性，但是进一步影响了算法的性能，RSA算法加解密的速度会越来越慢，对系统的要求较高，因此，在选择RSA密钥时，不能只考虑安全性，单纯的扩大RSA密钥长度，在系统的安全性和性能之间需要找到一个平衡点。 鉴于RSA存在的问题，人们一直致力于寻找新的、有效的公钥密码体制，椭圆曲线密码算法ECC以其

22、较短的密钥，但能保证与RSA相当程度的安全性，被广大学者关注和研究,37,有限域上椭圆曲线密码算法ECC,将椭圆曲线用于公钥密码学的思想是1985年由Neal Kobiltz和Victor Miller提出。 其理论基础是：定义在有限域上的某一椭圆曲线上的有理点可构成有限交换群。如果该群的阶包含一个较大的素因子，则其上的离散对数问题是计算上难解的数学问题。 业已证明，除了某些特殊椭圆曲线外，目前已知的最好的攻击算法（Pollard-算法）也是完全指数级的。就安全强度而言，密钥长为163比特的椭圆曲线密码体制ECC（Elliptic Curve Cryptosystem）相当于1024比特的RS

23、A。即在相同安全强度下，ECC使用的密钥比RSA要短约。这使得ECC对存储空间、传输带宽、处理器的速度要求较低。这一优势对于资源环境有限的移动用户终端，具有极其重要的意义,38,有限域上椭圆曲线密码算法ECC,椭圆曲线密码学使用椭圆曲线上称之为加法的运算，乘法被定义为重复相加。例如 为个相加，其中加法是椭圆曲线上的加法。密码分析者需要从给定的和来确定。 椭圆曲线是一个具有两个变元及系数的方程。对于密码学而言，变元和系数均限制于有限域上（即在实际的密码学研究中，主要应用的是基于有限域上的椭圆曲线），这导致了有限阿贝尔群（交换群）的定义,39,阿贝尔（Abel）群,阿贝尔群G由元素的集合及其上的二

24、元运算 组成，有时记为G，。将G中元素的序偶（a，b）与G中元素（a b）对应，使得下述公理成立： A1）封闭性：若a和b属于G，则a b也属于G。 A2）结合性：对G中任意a ，b和c，（ a b） c = a （b c） A3）单位元：G中存在元素e，使得对G中所有的a， e a = a e = a。 A4）逆元：对G中任何a，存在G中元素a，使得 a a = a a = e。 A5）交换性：对G中任何a和b，都有 b a = a b。 许多公钥密码都使用了阿贝尔群。例如，Diffie-Hellman 密钥交换包含若干非零整数对素数q的取模运算，通过幂运算来产生密钥，其中幂运算定义为重复相

25、乘。如ak mod q，要攻击Diffie-Hellman，攻击者必须对给定a和ak确定k，这就是求离散对数问题,40,椭圆曲线,椭圆曲线指的是由韦尔斯特拉斯（Weierstrass）方程： y2 + axy + by = x3 + cx2 + dx + e， 所确定的平面曲线和一个称为无穷远点或零点(y轴方向上）的特殊元素（记为O） ，将椭圆曲线记为E。 其中系数a,b,c,d,e 定义在某个域F上，可以是有理数域、实数域、复数域，还可以是有限域GF（pr），x，y属于F或F的代数闭包。 椭圆曲线E上的所有有理点（E中两坐标都属于F）加上无穷远点构成的集合连同一个定义的加法运算构成一个Abe

26、l群。 椭圆曲线并不是椭圆，之所以称为椭圆曲线是因为它们与计算椭圆周长的方程相似，也是用3次方程来表示,41,实数域上的椭圆曲线,此时，韦尔斯特拉斯方程中的系数以及变元x和y都属于实数集。将方程限制为下述形式 y2 = x3 + ax + b， 此曲线中每一曲线关于y=0对称。记满足上述方程的所有点（x，y）和无穷远点O所组成的点集为E（a，b）。 加法的几何描述 上述式子里的参数a和b，如果满足条件 4a3 + 27b2 0 则可基于集合E（a，b）定义一个群。因此必须定义一个运算，称为加法，用+表示。若椭圆曲线上的三个点同在一条线上，则它们的和为O。从这个定义可以定义椭圆曲线加法的运算规则

27、,42,实数域上椭圆曲线加法的运算规则,1. O是加法的单位元。这样有O=-O；对椭圆曲线上的任何一点P，有P+O=P。下面假定PQ且QO。 2. 点P的负元是具有相同x坐标和相反的y坐标的点，即若P=（x，y），则-P=（x，-y）。注意这两个点可以用一条垂直x轴的线连接起来，并且P+（-P）= P-P = O。 3. 要计算x坐标不相同的两点P和Q之和，则在P和Q间画一条直线并找出第三个交点，显然存在唯一的交点（除非这条直线在P或Q处与该椭圆曲线相切，此时分别取=P或=Q）。关于x轴的对称点R=- 即为P与Q的和，即。 .上述术语的几何解释也适用于具有相同坐标的两个点和-P。用一条垂直的线

28、连接这两点，这也可看做是在无穷远点处与曲线相交，因此有P+（-P）= O,43,实数域上椭圆曲线加法的运算规则,如果P和Q相同，即P与Q是椭圆曲线的某一点，如图2-7所示，则过P做椭圆的切线，该切线同E相交点为M，M关于X轴的对称点MM就是P+P的点加和，即M MP +P，我们将P + P记做M = 2P，以此类推，n个P相加 P + P + P .+ P 记做 nP ，nP 也称为倍乘。根据椭圆曲线的性质，2P、3P.nP都是E上的点。 椭圆曲线上点的阶：满足公式nP（无穷远点）的最小正整数称为点的阶（若存在）。若不存在，则说P是无限阶的,44,实数域上椭圆曲线加法的运算规则,45,实数域上

29、椭圆曲线加法的运算规则,46,实数域上椭圆曲线加法的代数描述,对不是互为负元的两个不同的点P=（xP，yP）和Q=（xQ，yQ），连接它们的曲线的斜率（yQ yP）/（xQ xP）。恰与椭圆曲线相交于另一点，即P与Q之和的负元。 利用某些代数运算，可如下表示和 R=P+Q： xR= 2 - xP - xQ yR = - yP + （xP xR） 当P与Q相同时，即 P+P=2P=R，当yP 0时，该表达式为： xR= (3xP2 +a)/2yP)2 - 2xP ， yR = (3xP2 +a)/2yP)2 (xP xR) - yP,47,有限域上的椭圆曲线,有限域上的椭圆曲线是由韦尔斯特拉斯（

30、Weierstrass）方程： y2 + axy + by = x3 + cx2 + dx + e， 所确定的平面曲线和无穷远点或零点(y轴方向上）的特殊元素（记为O） ，将椭圆曲线记为E。 其中系数a,b,c,d,e 定义在有限域GF（pr）上，x，y属于该域的代数闭包(若K是F的代数扩域且K无真代数扩张，则称K是F的代数闭包）。 一般在实际密码应用中，使用的两类椭圆曲线是定义在有限域 Zp（或Fp）上的素曲线和在F2m上的椭圆曲线，这里p是素数，尤其是当p为大于2160的素数和 m160 时受到青睐,48,Zp上的椭圆曲线,不是所有的椭圆曲线都适合加密。 y2 = x3 + ax + b是

31、一类可以用来加密的椭圆曲线，也是最简单的一类。把 y2 = x3 + ax + b 这条曲线定义在Zp上，x，y和系数都属于Zp 。这里p为大于3的素数，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）中的点组成,49,Zp上的椭圆曲线,50,Zp上的椭圆曲线运算,Ep（a，b）上的加法运算与定义在实数域上的椭圆曲线中描述的代数方法是一致的。对任何点P，

32、Q Ep（a，b）： P+O=P 若P=（xP，yP），则 P+（ xP，-yP）= O。点（ xP，-yP）是P的负元，记为-P。 例如，对 E23（1，1）上的点P=（13，7），有-P=（13，-7），而-7 mod 23=16.因此，-P=（13，16），该点也在E23（1，1）上,51,Zp上的椭圆曲线运算,若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。 为确定各种椭圆曲线密码的安全性，需要知

33、道定义在椭圆曲线上的有限阿贝尔群中点的个数。在有限群Ep（a，b）中，点的个数N的范围是：P+1-2pN P+1+2p 所以Ep（a，b）上点的个数约等于Zp中元素的个数，即p个元素,52,有限域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上的椭圆曲线就是由该集合中的点组成,53,有限域F2m上的椭圆曲线运算

34、,对任何P E F2m （a，b），P+O=P。 若 P=（xP，yP），则P+ （xP， xP +yP）=O。点（xP， xP +yP）是P的负元，记为-P。 1）方程为 y2 + xy = x3 + ax2 + 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 =

35、（+1）xR + xP2 其中， = xP + yP / xP,54,有限域F2m上的椭圆曲线运算,2）方程为 y2 + cy = x3 + ax + b 时 对任何P=（xP，yP）和 Q=（xQ，yQ）都属于F2m ， 其中,55,椭圆曲线密码ECC算法依赖的数学问题,椭圆曲线离散对数问题 给定椭圆曲线E及该椭圆曲线上的一点P，kP 表示k个P相加，k为某整数，如果椭圆曲线上存在一点Q，能够满足方程 Q = kP，那么椭圆曲线离散对数问题就是给定点P和点Q，求解k的问题，在数学上该问题是同时涉及整数因式分解和离散对数的难题。 ECC算法就是基于“椭圆曲线离散对数问题”难以求解而设计的，给定

36、P和k容易通过方程Q = kP计算Q；但是反过来，给定Q和P，求k在计算上是不可行的，因此我们可以设定k为私钥,56,ECC算法密钥的选择,基于椭圆曲线密码体制的ECC算法在加解密之前，首先要给出椭圆曲线域的一些参数，如基点P，阶n ，以确定具体的椭圆曲线。 ECC算法密钥的产生是都是建立在某个有限域的椭圆曲线上，设给定一个具有q个元素有限域的椭圆曲线E，E 的基点是P，P的阶为n。 下面介绍一种利用椭圆曲线实现加解密的方法，这种方法很简单。 密钥的选择： （1） 密钥的产生者在区间2，n-1随机选取某整数k； （2） 计算Q = kP。 则Q就是公钥，私钥是k,57,一种ECC算法加解密过程

37、,假设网络上的用户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； （3）计算 kP = R1 (X1，Y1)，kQB = R2 (X2，Y2）；如果X2 =0；则返回到（2）； (4) 则密文C由 R1，Pm + R2 组成,58,一种ECC算法的加解密过程,Bob收到密文C后，解密过程

38、如下： （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 + 188，基点为（0，376）。假设A要将编码为椭圆曲线上点 Pm（562，201）的消息发给B，且A挑选的随机数为k=386，B的公钥为（201，5），那么有386（0，376）=（676，558）和（562，

39、201）+386（201，5）=（385，328）。于是A发送的密文是（676，558），（385，328,59,Menezes-Vanstone 椭圆曲线密码体制,Menezes-Vanstone 椭圆曲线密码体制是ElGamal密码体制在椭圆曲线上的模拟，它是由A J Menezes与S A Vanstone 在1993年12月提出的。 ElGamal 公钥密码体制是1985年7月由Taher ElGamal 发明的，它是建立在解有限乘法群上的离散对数问题的困难性基础之上的一种公钥密码体制。该密码体制至今仍被认为是一个安全性能较好的公钥密码体制，目前它被广泛用于许多密码协议中,60,ElG

40、amal 加密算法,ElGamal 算法既可用于加密，也可用于签名。加密算法描述如下： （1）公开参数：首先选取大素数p，并取是乘法群 Zp*=1，p-1的一个生成元。 （2）密钥生成：再随机选取整数d：0dp-1，并计算=d mod p。这里p与是公开参数，是公开的加密密钥（公钥），d是保密的解密密钥（私钥）。 （3）加密运算：对明文m Zp*，随机选取整数k：0kp-1,计算 c1=k mod p，c2= mk mod p， 得到密文c=（c1，c2）。 （4）解密运算：对密文c Zp* Zp*，用私钥d解密为 m= c2(c1d)-1 mod p,61,离散对数问题与ElGamal密码体

41、制的安全性,设p是大素数，是乘法群 Zp*=1，p-1的一个生成元， Zp*。求满足同余方程 x = mod p 的整数解x：0 xp-2。显然，该方程存在唯一解。求解该同余方程的解问题称为有限乘法群Zp*上的离散对数问题。若x=l 是该方程的解，则称l是Zp*上的以为底的的离散对数，记为log。 如果能求出上述同余方程的解，那么就可破解ElGamal密码体制。方程的解可通过计算1，2，3， 直到找到某个正整数k使得k = mod p 为止。这是穷搜索法，需要的运行时间是O（p）。运行时间指运行算法需要的群运算次数,62,离散对数问题与ElGamal密码体制的安全性,关于Zp*上的离散对数问题

42、的研究取得了许多重要的研究成果，已设计出了各种计算离散对数的算法，主要的有关算法有： Shanks 算法、小步大步算法、Pohlig-Hellman 算法、指数演算法、并行Pollard-算法。 并行Pollard-算法和指数演算法是其中比较有效的算法，但它们都至少是lnp的亚指数时间算法，而非多项式时间算法,63,Menezes-Vanstone 椭圆曲线密码体制,1）公开参数：设p3是一个素数，E是有限域Zp上的由方程y2 = x3 + ax + b 表示的椭圆曲线，E（Zp）是相应的阿贝尔群。G是该群中具有较大素数阶n的一个点。 （2）密钥生成：随机选取整数d：2dn-1，计算P=dG。

43、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，c2），计算标量乘 dC0 =（x，y），计算 m1 = c1 x-1 mod p，m2 = c2 y-1 mod p，即得c解密后的明文为（m1，m2,64,ECC 算法的安全性分析,ECC算法

44、的安全性依赖于椭圆曲线离散对数问题计算的困难性，如果离散对数问题容易计算，从用户的公钥能够推导出私钥，那么整个密码体制就会坍塌。除此之外，椭圆曲线E的选择也非常重要。为防止穷搜索攻击，有限域的阶应是一个较大的素数幂。 解有限群离散对数问题的通用方法均可用来解椭圆曲线上阿贝尔群上的离散对数问题。但是关于解有限域乘法群上的指数演算法则对椭圆曲线离散对数问题(ECDLP)不适用，即目前还没有找到对ECDLP适用的类似算法。 已知的对ECDLP最好的算法是（并行）Pollard-算法。解 ECDLP 比解有限域上的离散对数问题 FFDLP 要困难得多，因而椭圆曲线密码体制比同等规模的Zp*上的 ElG

45、amal 公钥密码体制安全性要强很多,65,ECC算法的优点,椭圆曲线加密算法ECC与其他公钥算法（如RSA）相比有很多优点： a)安全性能更高： 加密算法的安全性能一般通过该算法的抗攻击强度来反映。ECC和其他几种公钥系统相比，其抗攻击性具有绝对的优势。椭圆曲线的离散对数（ECDLP）计算困难性在计算复杂度上目前是完全指数级，而RSA是亚指数级的。这体现ECC比RSA的每bit安全性能更高。 b)计算量小和处理速度快： 在一定的相同的计算资源条件下，在私钥 的处理速度上（解密和签名），ECC远比RSA、DSA 快得多。ECC总的速度比RSA、DSA要快得多。 同时ECC系统的密钥生成速度比R

46、SA快百倍以上。 因此在相同条件下，ECC则有更高的加密性能,66,ECC算法的优点,c)存储空间占用小： ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多。160位ECC与1024位RSA、DSA具有相同的安全强度，210位ECC则与2048位RSA、DSA具有相同的安全强度。意味着它所占的存贮空间要小得多。这对于加密算法在资源受限环境上（如智能卡等）的应用具有特别重要的意义。 d)带宽要求低： 当对长消息进行加解密时， 三类密码系统有相同的带宽要求，但应用于短消息时ECC带宽要求却低得多。而公钥密码系统多用于短消息，例如用于数字签名和用于对对称系统的会话密钥传递。带宽要求低使ECC在

47、无线网络领域具有广泛的应用前景,67,68,ECC 算法的缺点,公开密钥加密系统是基于尖端的数学难题，计算非常复杂，实现难度大； 安全性高，但实现速度却远赶不上对称密钥加密系统。 随着计算能力的提高，从安全性角度考虑，对密钥长度的要求越来越高。相对于其他公钥密码算法，ECC逐渐体现出其优越性。但是自从使用公钥密码体制以来，实际应用中，RSA算法因为原理简单被广泛使用，ECC算法在实际应用中相对比较少。但是随着时间的推移，ECC算法理论不断完善，相信它逐渐会被应用到实际系统中,69,ECC算法应用与现状,算法在标准化中应用 国内外软硬件中应用,70,ECC算法在标准化中应用,ECC的特点使它在某些领域（如手机、智能卡）的应用将取代RSA，并成为通用的公钥加密算法。 许多国际标准化组织（政府、工业界、金融界、商业界等）已将各种椭圆曲线密码体制作为其标准化文件向全球颁布。 ECC标准大体可以分为两种形式： 一类是技术标准，即