1、第5章公钥密码算法 第第5章公钥密码算法章公钥密码算法5.1公钥密码技术公钥密码技术 5.2单向陷门函数单向陷门函数 5.3Diffie-Hellman密钥交换协议密钥交换协议 5.4RSA算法算法 5.5ElGamal算法算法 5.6Rabin算法和算法和Williams算法算法 5.7NTRU算法算法 5.8椭圆曲线密码体制椭圆曲线密码体制(ECC)5.91 n公钥体制公钥体制 5.10(t,n)秘密共享体制秘密共享体制 第5章公钥密码算法 5.1.1公钥密码算法的基本原理公钥密码算法的基本原理尽管对称密码技术有一些很好的特性,但它也存在着明显的缺陷,主要在于其密钥的管理。(1)进行安全通
2、信前需要以安全方式进行密钥交换。这一步骤在某些情况下是可行的,但在某些情况下会变得非常困难,甚至无法实现。5.1公钥密码技术公钥密码技术第5章公钥密码算法(2)密钥规模复杂。例如,A与B两人之间的密钥必须不同于A和C两人之间的密钥,否则A给B的消息的安全性就会受到威胁。在10000个用户的团体中,A需要保持至少9999个密钥(更确切地说是10000个,如果他需要留一个密钥给自己加密数据)。对于该团体中的其他用户,此种情况同样存在。这样,这个团体一共需要将近5000万个不同的密钥！推而广之,n个用户的团体需要n2/2个不同的密钥。第5章公钥密码算法 公钥密码算法是指加密和解密数据使用两个不同的密
3、钥,即加密和解密的密钥是不对称的,这种密码系统也称为公钥密码系统(PKC,PublicKeyCryptosystem)。公钥密码学的概念首先是由Diffie和Hellman两人在1976年发表的一篇著名论文密码学的新方向中提出的,并引起了很大的轰动。该论文曾获得IEEE信息论学会的最佳论文奖。与对称密码算法不同的是,公钥密码算法将随机产生两个密钥:一个用于加密明文,其密钥是公开的,称为公钥;另一个用来解密密文,其密钥是秘密的,称为私钥。图5.1.1表示了公钥密码算法的基本原理。第5章公钥密码算法 图5.1.1公钥密码算法的基本原理 第5章公钥密码算法 如果两个人使用公钥密码算法传输机密信息,则
4、发送者首先要获得接收者的公钥,并使用接收者的公钥加密原文,然后将密文传输给接收者。接收者使用自己的私钥才能解密密文。由于加密密钥是公开的,不需要建立额外的安全信道来分发密钥,而解密密钥是由用户自己保管的,与对方无关,因而避免了在对称密码系统中容易产生的任何一方单方面密钥泄露问题以及分发密钥时的不安全因素和额外的开销。公钥密码算法的特点是安全性高，密钥易于管理;缺点是计算量大,加密和解密速度慢。因此,公钥密码算法比较适合于加密短信息。在实际应用中,通常采用由公钥密码算法和对称密码算法构成的混合密码系统,以发挥各自的优势。使用对称密码算法来加密数据,加密速度快;使用公钥密码算法来加密对称密码算法的
5、密钥,可形成高安全性的密钥分发信道,同时还可以用来实现数字签名和身份验证机制。第5章公钥密码算法 5.1.2基本概念基本概念公钥密码算法要求从公钥很难推断出私钥。持有公钥的任何人都可以加密消息,但无法解密，只有持有私钥的人才能够解密。公钥加/解密的基本步骤如图5.1.2所示。第5章公钥密码算法 图5.1.2公钥加/解密的基本步骤 第5章公钥密码算法 一般情况下,网络中的用户约定一个共同的公开密钥密码系统,每个用户都有自己的公钥和私钥,并且所有的公钥都保存在某个公开的数据库中,任何用户都可以访问此数据库。因此,加密协议如下:(1)Alice从公开数据库中取出Bob的公开密钥;(2)Alice用B
6、ob的公开密钥加密她的消息,然后传送给Bob;(3)Bob用他的私钥解密Alice的消息。第5章公钥密码算法 5.1.3公钥的优点公钥的优点从以上介绍中可以看出,与对称密码技术相比较,利用非对称密码技术进行安全通信有以下优点:(1)通信双方事先不需要通过保密信道交换密钥。第5章公钥密码算法(2)密钥持有量大大减少。在n个用户的团体中进行通信时,每一用户只需要持有自己的私钥,而公钥可放置在公共数据库上,供其他用户取用。这样,整个团体仅需拥有n对密钥,就可以满足相互之间进行安全通信的需求。实际中,因安全方面的考虑,每一用户可能持有多个密钥,分别用于数字签名、加密等。事实上这也是必须的,对于同一个公
7、、私钥对,不能既用于签名,又用于加密,这也是目前本领域所公认的一个原则。此种情况下,整个团体拥有的密钥对数为n的倍数。但即使如此,与使用对称密码技术时需要n2/2个不同的密钥相比,需要管理的密钥数量仍有显著减少。(3)非对称密码技术还提供了对称密码技术无法或很难提供的服务。例如,与杂凑函数联合运用可生成数字签名。第5章公钥密码算法 5.1.4基本服务基本服务公钥算法的基本服务包括以下内容:(1)加密/解密:发送方可以用接收方的公钥加密消息。(2)数字签名:发送方用其私钥“签署”消息,通过对消息或作为消息函数的小块数据应用加密算法来进行签署。(3)密钥交换:两方通过互相合作可以进行会话密钥的交换
8、。第5章公钥密码算法 5.1.5理论基础理论基础一个公开密钥密码系统必须满足的条件如下:(1)通信双方A和B容易通过计算产生出一对密钥(公开密钥k1和私有密钥k2)。(2)在知道公钥k1和待加密报文m的情况下,对于发送方A,很容易通过计算产生对应的密文:c=Ek1(m)。(3)接收方B使用私钥能够很容易地对所接收到的密文进行解密计算以恢复原来的报文:。221kkkM=D(C)=D E(M)第5章公钥密码算法 5.2单向陷门函数单向陷门函数 5.2.1 单向函数单向函数 定义定义 5.2.1 令函数 f 是集A 到集 B的映射，以:fAB表示。若对任意12xx，12,x xA，有12()()f
9、xf x，则称 f 为单射单射，或1 1映射映射，或可逆的函数可逆的函数。f 为可逆的充要条件是，存在函数:g BA，使对所有xA有()g f xx。第5章公钥密码算法 第5章公钥密码算法 第5章公钥密码算法 第5章公钥密码算法 第5章公钥密码算法 5.2.2单向陷门函数的定义单向陷门函数的定义单向函数是求逆困难的函数,而单向陷门函数(TrapdoorOneWayFunction)是在不知陷门信息的情况下求逆困难的函数,当知道陷门信息后,求逆是易于实现的。这是Diffie和Hellman于1976年引入的有用概念。号码锁在不知预设号码时很难开启,但若知道所设号码则容易开启。太平门从里面向外出容
10、易,若无钥匙则反向难进。但如何给陷门单向函数下定义则很棘手,因为:第5章公钥密码算法(1)陷门函数其实就不是单向函数。这是因为单向函数在任何条件下求逆都是困难的。(2)陷门可能不止一个,通过试验,一个个陷门就可容易地找到逆。如果陷门信息的保密性不强,那么求逆也就不难。第5章公钥密码算法()()zzfxE x(5.2.3)()zzDfxx(5-2-4)而且在给定z后容易找到一种算法Fz(称其为可用消息集鉴别函数),对所有xA,易于检验是否 ,Az是可用的明文集。()zzxA AA第5章公钥密码算法 第5章公钥密码算法 第(2)条半精确地定义了陷门单向函数为一单向函数。它表明在给定算法zE，zD
11、时，对“几乎所有”zxA，至少对“大多数”zZ和“大多数”zxA，在“计算上”不可能求出逆。即使已知有限明密文对(,),1,2,iix yin，也难以轻易地从()zF x 算出 x，其中zxA但不在已知的明密文对中。第5章公钥密码算法(3)对任一z,集Az必须是保密系统的明文集中的一个“方便”集,即便于实现明文到它的映射(在PKC中是默认的条件)。Diffie和Hellman定义的陷门函数中,Az=A,对所有z成立,而实际中Az取决于Z。第5章公钥密码算法 5.2.3公钥系统公钥系统在一个公钥系统中,所有用户共同选定一个单向陷门函数、加密运算E及可用消息集鉴别函数F。用户i从陷门集中选定zi,
12、并公开Ezi和Fzi。任一向用户i发送机密消息者,可用Fzi检验消息x是否在许用明文之中,而后送y=Ezi(x)给用户x即可。在仅知y、Ezi和Fzi的情况下,任一用户都不能得到x。但用户i利用陷门信息zi,易于得到Dzi(y)=x。第5章公钥密码算法 定定义义5.2.4 对zZ和任意,()xX F xyYX。若()()jiijF F xF F x(5.2.5)成立，则称F为可换单向函数可换单向函数。第5章公钥密码算法 5.2.4 用于构造双钥密码的单向函数用于构造双钥密码的单向函数 1）多项式求根多项式求根 有限域()GF p 上的一个多项式 1110()mod nnnyf xxaxa xa
13、p 当给定011,na aa，p 及 x时，易于求 y，利用 Honers 法则，即 12310()()mod pnnnf xxaxaxaxa xa。(5-2-6)最多有 n 次乘法和 n1 次加法。反之，已知 y,011,na aa，要求解 x 需能对高次方程求根。这至少要22()n lb p次乘法，a 表示不大于 a 的最大整数，当n,p 大时很难。第5章公钥密码算法 第5章公钥密码算法 第5章公钥密码算法 RSA问题是FAC问题的一个特例。n是两个素数p和q之积,给定n后求素因子p和q的问题称为RSAP。求n=pq的分解问题有以下几种形式:(1)分解整数n为p和q;(2)给定整数M和C,
14、求d使CdM mod n;(3)给定整数e和C,求M使MeC mod n;(4)给定整数x和C,决定是否存在整数y使xy2 mod n(二次剩余问题)。第5章公钥密码算法 4.背包问题背包问题 背 包 问 题 是1972年Karp提 出 的。已 知 向 量12(,)NiAaaaa，为正整数 称 其 为 背 包 向 量背 包 向 量。给 定 向 量12(,)0,1Nixxxxx，求和式1()0,1NiiiiSf xxax，容易，只需N1 次加法。但已知 A和 S，求 x 则非常困难，称其为背包问题，又称作子集和(Subset-Sum)问题，是个 NP-C 问题。用穷举搜索法，有2N种可能。N 大
15、时，相当困难。第5章公钥密码算法 5.Diffie-Hellman 问题问题 给定素数 p，令为*pZ 的生成元，若已知a和b，求 a b的问题为 Diffie-Hellman 问题，简记为 DHP。若为循环群 G 的生成元，且已知a和b为 G 中的元素，求 a b的问题为广义 Diffie-Hellman 问题，简记为 GDHP。6.二次剩余问题二次剩余问题 给定一个奇合数 n 和整数 a，决定a 是否为 mod n 的平方剩余。第5章公钥密码算法 5.3DiffieHellman密钥交换协议密钥交换协议 5.3.1历史背景历史背景对于对称密码系统,在进行保密通信之前,必须向通信双方分别递送
16、一个密钥。在公钥密码体制出现之前,通信双方建立共享密钥一直是一个比较困难的问题,这是因为这个过程需要一条安全的信道,通常这样的信道意味着要由专门的信使以物理方式传送。与对称密码体制相比,公钥密码体制的一个显著优点就是远程通信各方无需安全信道就能实现相互交换密钥。第5章公钥密码算法 W.Diffie与M.Hellman在1976年提出了一个奇妙的密钥交换协议,称为DH密钥交换协议/算法(DHKeyExchange/AgreementAlgorithm)。这个机制的巧妙之处在于需要安全通信的双方可以用这个方法确定对称密钥,然后用这个密钥进行加密和解密。但需注意,这个密钥交换协议/算法只能用于密钥的
17、协商,而不能进行消息的加密和解密。双方确定要用的密钥后,要使用其他对称密钥操作加密算法来加密和解密消息。第5章公钥密码算法 此算法是最早的公钥算法。它实质上是一个通信双方进行密钥协定的协议:两个实体中的任何一个使用自己的私钥和另一实体的公钥,得到一个对称密钥,其他实体都计算不出这一对称密钥。DH算法的安全性基于有限域上计算离散对数的困难性。离散对数的研究现状表明,所使用的DH密钥至少需要1024位,才能保证有足够的中、长期安全。第5章公钥密码算法 5.3.2 协议描述协议描述 协议协议 5.3.1 DH 密钥交换协议密钥交换协议 共同输入 (p,q)：p 为大素数，g 为*pF 的生成元。输出
18、 Alice 和 Bob 共享*pF 中的一个元素。(1)Alice选择)1,1 paU；计算)(mod pggaa；发送ag 给 Bob；(2)Bob 选择)1,1 pbU；计算)(mod pggbb；发送bg 给 Alice；(3)Alice计算)(mod pgkab；(4)Bob 计算)(mod pgkba。第5章公钥密码算法 系统范围内的所有用户可以共用公开参数p和g。由协议5.3.1不难看出,对于Alice:(mod)bakgp对于Bob:(mod)abkgp我们注意到由于，这样双方计算得到的值是相同的。这就是DH密钥交换协议在通信双方之间实现了一个共享密钥的原因。第5章公钥密码算法
19、 5.3.3算法说明算法说明在执行和应用DH密钥交换协议的时候,我们应该注意如下细节:(1)共同的输入p应该为一个素数(或素数的幂),满足p-1有足够大的素因子p,这里“足够大”意味着p2160。(2)共同的输入g不必是F*p的生成元,但g应该是F*p中高阶子群的一个生成元。例如,阶为p的子群,则p也应该是这个协议共同输入的一部分。第5章公钥密码算法(3)Alice(Bob)应该验证gb1(mod p)(ga 1(modp)。对于他们各自取自(1,p)中的指数,这个验证将确保共享的密钥gab是Fp的p阶子群中的一个元素,也就是说,是一个高阶子群中的一个元素。(4)在这个协议结束之后,Alice
20、(Bob)应该立即删除她的指数a(他的指数b)。这样在通信结束后,如果他们都正确地处理了交换密钥gab,那么对于这个交换密钥,他们将会拥有前向保密的性质。第5章公钥密码算法 5.3.4安全性分析安全性分析应该注意,DH密钥交换协议不支持对协商密钥的认证功能。处于Alice和Bob通信中间的主动攻击者能够操纵这个协议的消息以实现成功攻击,称为中间人攻击(ManinthemiddleAttack)。攻击5.3.1说明了这种攻击。攻击攻击5.3.1对DH密钥交换协议的中间人攻击(见图5.3.1):共同输入:同协议5.3.1。第5章公钥密码算法 图5.3.1中间人攻击过程 第5章公钥密码算法(1)Al
21、ice 选择)1,1 paU，计算(mod)aaggp，发送ag 给 Malice（“Bob”）；1 Malice（“Alice”）对某个 mm1,1)p，计算(mod)mmggp，发送mg 给 Bob；(2)Bob 选择)1,1 pbU，计算(mod)bbggp，发送bg 给 Malice（“Alice”）；Malice（“Bob”）向 Alice 发送：mg；(3)Alice 计算 1(mod)amkgp；（*由于 Malice 能够计算1(mod)amkgp，这个密钥由 Alice 和 Malice 共享）(4)Bob 计算1(mod)amkgp。（*由于 Malice 能够计算2(mo
22、d)bmkgp，这个密钥由 Bob 和 Malice 共享）第5章公钥密码算法 在对协议运行的攻击当中，Malice（坏家伙）截获 Alice 发送给Bob 的第一条消息ag，并伪装成 Alice 向 Bob 发送消息 Malice(“Alice”)发送给 Bob：)(mod(pggmdefm；Bob 将按照协议的规则回复bg 给 Malice（“Alice”）。这意味着这个发送的数值再一次被 Malice 截获。现在 Malice 和 Bob 协商了一个密钥(mod)bmgp ，而Bob以为这个密钥就是他和Alice所共享的密钥。第5章公钥密码算法 类似地，Malice可以伪装成Bob，并同
23、Alice协商另一个密钥。以上两个过程完成之后，Malice用这两个密钥就可以在Alice和Bob之间阅读或转发“保密”通信，或者对于其中一方，伪装另一方。由于这个协议没有提供对协议消息源的认证服务，对Diffie-Hellman密钥交换协议的中间人攻击是可能的。为了协商一个仅由Alice和Bob专门共享的密钥，在协议的运行过程当中，参与者必须确定收到的消息的确来自目标参与者。关于参与者身份认证问题，我们在后面章节进行讲述。第5章公钥密码算法 5.3.5DH协议应用的典型案例协议应用的典型案例DH协议应用的典型实例是在中国无线局域网安全标准WAPI中采用DH密钥交换协议来实现接入点AP和终端S
24、TA之间的密钥协商,即在实现STA和AP认证的同时,产生它们共享的基密钥BK。BK可以用来进一步协商通信过程中的会话密钥等。图5.3.2为STA和AP的认证过程,其中AS表示后台认证服务器。第5章公钥密码算法 图5.3.2STA和AP的认证过程 第5章公钥密码算法 图5.3.3STA和AP认证过程的具体实现 第5章公钥密码算法 5.4RSA算法算法 5.4.1历史背景历史背景MIT三位年轻数学家R.L.Rivest、A.Shamir和L.Adleman于1978年和1979年发现了一种用数论构造双钥的方法,称做MIT算法,后来被广泛称为RSA算法。该算法既可用于加密,又可用于数字签字,易懂且易
25、于实现,是目前仍然安全并且逐步被广泛应用的一种算法。国际上一些标准化组织如ISO、ITU及SWIFT等均已接受RSA算法作为标准。在Internet中所采用的PGP(PrettyGoodPrivacy)中也将RSA作为传送会话密钥和数字签字的标准算法。第5章公钥密码算法 5.4.2算法描述算法描述系统参数:独立地选取两个大素数p1和p2(各为100200位十进制数字),计算:12npp(5.4.1)其欧拉函数值:12()(1)(-1)npp(5.4.2)随机选一整数e,1e(n),(n),e)=1。因而在模(n)下,e有逆元,即-1 mod()den(5.4.3)取公钥为n、e,秘密钥为d。(
26、p1、p2不再需要,可以销毁。)第5章公钥密码算法 加密:用x和y分别表示明文和密文,则 mod eyxn(5.4.4)解密解密:mod dxyn(5.4.5)第5章公钥密码算法 5.4.3算法说明算法说明RSA加密实质上是一种ZnZn上的单表代换,给定n=p1p2和合法明文xZn,其相应密文y=xemodnZn。对于xx,必有yy。Zn中的任一元素(0、p1、p2除外)是一个明文,但它也是与某个明文相对应的一个密文。因此,RSA是ZnZn的一种单表代换密码,其关键在于n极大且不知陷门信息的情况下极难确定这种对应关系,而用模指数算法又易于实现一种给定的代换。正是由于这种一一对应性使RSA不仅可
27、以用于加密,也可以用于数字签名。第5章公钥密码算法 5.4.4RSA实现方法实现方法RSA有硬件和软件两种实现方法。不论何种实现方法,RSA的速度总是比DES慢得多(其实任何公钥运算的复杂度都大于私钥运算)。因为RSA的计算量要大于DES,所以在加密和解密时需要做大量的模数乘法运算。例如,RSA在加密或解密一个200位十进制数时大约需要做1000次模数乘法运算,因此提高模数乘法运算的速度是解决RSA效率的关键所在。硬件实现方法采用专用的RSA芯片,以提高RSA的加密和解密速度。生产RSA芯片的公司有很多,如AT&T、Alpha、英国电信、CNET、Cylink等。同样使用硬件实现时,DES比R
28、SA快大约1000倍。第5章公钥密码算法 软件实现方法的速度要更慢一些,与计算机的处理能力和速度有关。同样使用软件实现时,DES比RSA快大约100倍。表5.4.1为多年前在SPARC工作站上测试RSA软件实现的处理速度实例,该数据现在可能已经没有参考价值,这里主要借用它来说明各种操作之间的运算速度快慢。第5章公钥密码算法 表5.4.1RSA软件实现的处理速度实例(在SPARC工作站上)第5章公钥密码算法 5.4.5RSA的安全性的安全性在RSA问世后的30多年中,有很多密码专家和研究机构对RSA进行了大量的研究和分析,迄今为止还未找到破译RSA的有效方法。这就是我们现在还可以放心使用RSA的
29、原因。对于破译RSA,穷举搜索法并不是有效的方法,通常主要采用分解因子的方法来分解n。因为破译者手中有公钥e和模数n,所以要找到解密密钥d,则必须分解n。分解因子问题是众所周知的数学难题,迄今为止还未找到分解因子的有效算法,这就是RSA算法的安全性基础。第5章公钥密码算法 然而,RSA在理论上还存在一定的空白点,也就是不能确切地证明它的安全性,破译RSA不会比分解因子问题更困难,并且不排除这种可能性:可以找到一种破译RSA密码的有效算法,但找不到相应分解因子的快速算法。另外,一些攻击者专门对RSA实现系统进行攻击,它们并不攻击RSA算法本身,而是设法攻击RSA实现上的弱点。根据一些成功的攻击经
30、验,RSA在使用上存在如下限制:(1)知道了对于一个给定模数的一个加/解密密钥指数对,攻击者就能分解这个模数。第5章公钥密码算法(2)知道了对于一个给定模数的一个加/解密密钥指数对,攻击者无需分解n就能计算出其他的加/解密密钥对。(3)在网络环境下应用时,基于RSA的网络协议不应当使用公共模数。(4)消息应当使用随机数填充,以避免对加密指数的攻击。(5)解密指数应当足够大。对于一个密码应用系统来说,密码算法、使用密码算法的协议以及使用协议的应用系统都必须是安全的,三者之中的任何一个环节出现弱点都会危及整个系统的安全。因此,RSA实现的细节也是很关键的,应当给予足够的重视。第5章公钥密码算法 5
31、.5ElGamal算法算法 5.5.1算法描述算法描述系统参数:令Zp是一个有p个元素的有限域,p是一个素数,令g是Z*p(Zp中除去0元素)中的一个本原元或其生成元。明文集M为Z*p,密文集C为Z*pZ*p。公钥:选定g(g p。这里我们记：1212,11,0L d dFRFdd；的 个系数为，个系数为余下系数为 则有如下多项式集合：第5章公钥密码算法 1,fffgggrrrLL ddLL ddLL d d121121:ppmRmLm的系数位于区间第5章公钥密码算法 表5.7.1 NTRU安全等级参数表 N p q df dg dr 一般安全 107 64 3 15 12 5 高安全 167
32、 128 3 61 20 18 最高安全 503 256 3 216 72 55 第5章公钥密码算法 第5章公钥密码算法 011modmod,mod,modNfpfp fpfp称为多项式模运算。第5章公钥密码算法 第5章公钥密码算法 第5章公钥密码算法 3.解密解密Bob计算计算:mod,mod1mod,mod1NNd xf x c xqxf x m xpr x g xqx注意到 f(x)、m(x)、r(x)和 g(x)的系数都很小，所以多项式 1mod,modNxqxgxprxmxf的系数以很大概率在区间 2/,2/(qq，即 1mod,modNxqxgxprxmxfxd。第5章公钥密码算法
33、 Bob继续计算:11mod,mod1mod,mod1NNd x fxpxfx fxm xpxm x第5章公钥密码算法 例例5.7.1：取参数N=11，P=32，q=3，df=4，dg=3，dr=3。根据df、dg 值随机选择满足互逆的两个多项式f、g：f=(1，l，1，0，-l，0，l，0，0，l，-1)g=(1，0，1，0，1，0，0，1，0，0，1)求出:h=(5，9，23，30，2 l，22，7，29，26，23，0)设Bob的公开密钥为h，一对私人密钥为(f，g)。Alice要发送信息给Bob时，先根据值随机选择一个多项式r：r=(1，0，1，1，0，1，0，-1，0，0，-1)设A
34、lice要发送的明文多项式m为：m=(1，0，1，1，l，0，0，l，l，0，1)第5章公钥密码算法 Alice使用Bob的公开密钥h对m进行加密得到密文e：e=(18，l6，8，0，24，22，28，2 l，8，3 l，23)Bob收到Alice的密文e后，用自己的私人密钥分别对e进行解密得：a=(6，-3，-4，5，-6，4，2，-1 5，4，7，-7)b=(0，0，-l，-l，0，l，-l，0，l，l，-1)c=(1，0，1，1，1，0，0，1，10，1)c就是Alice发送给Bob的明文m。第5章公钥密码算法 5.7.3安全性安全性NTRU算法的安全性是基于数论中在一个维数非常大的格中
35、寻找一个很短向量的数学难题。就目前来说,NTRU的安全性和目前最有影响的RSA算法、椭圆曲线密码体制ECC等是一样安全的。在相同安全级别的前提下,NTRU算法的速度要比其他公开密钥算法的速度快得多,用Tumbler软件工具包执行NTRU时的速度比RSA快100多倍。用NTRU算法产生密钥的速度也很快,其密钥的比特数较小。NTRU算法的优点意味着可以降低对带宽、处理器、存储器的性能要求,这也扩大了NTRU公开密钥算法的应用范围。第5章公钥密码算法 5.8.1基本原理基本原理1985年,N.Koblitz和V.Miller分别独立提出了椭圆曲线密码体制(ECC),其依据就是定义在椭圆曲线点群上的离
36、散对数问题的难解性。为了用椭圆曲线构造密码系统,首先需要找到一个单向陷门函数,椭圆曲线上的数量乘就是这样的单向陷门函数。椭圆曲线的数量乘是这样定义的:设WTBXE为域K上的椭圆曲线,G为E上的一点,这个点被一个正整数k相乘的乘法定义为k个G相加,因而有:kG=G+G+G(共有k个G)5.8椭圆曲线密码体制椭圆曲线密码体制(ECC)第5章公钥密码算法 若存在椭圆曲线上的另一点NG,满足方程kG=N,则容易看出,给定k和G,计算N相对容易,而给定N和G,计算k=logGN相对困难。这就是椭圆曲线离散对数问题。离散对数求解是非常困难的。椭圆曲线离散对数问题比有限域上的离散对数问题更难求解。对于当椭圆
37、曲线上的有理点的数目有大素数因子时的椭圆离散对数问题,目前还没有十分有效的攻击方法。下面我们详细介绍密码椭圆曲线的基本算法。第5章公钥密码算法 5.8.2基础知识基础知识1.平行线平行线我们很早就知道,平行线是永不相交的。不过到了近代这个结论遭到了质疑,平行线会不会在很远很远的地方相交了？事实上没有人见到过,所以“平行线永不相交”只是假设(大家想想初中学习的平行公理,是没有证明的)。既然可以假设平行线永不相交,就可以假设平行线在很远很远的地方相交了,即平行线相交于无穷远点P,如图5.8.1所示。第5章公钥密码算法 图5.8.1平行线在无穷远处相交 第5章公钥密码算法 直线上出现P点,所带来的好
38、处是所有的直线都相交了,且只有一个交点。这就把直线的平行与相交统一了。为与无穷远点相区别,把原来平面上的点叫做平常点。无穷远点具有如下性质。(1)直线L上的无穷远点只能有一个。(2)平面上一组相互平行的直线有公共的无穷远点。(3)平面上任何相交的两直线L1和L2有不同的无穷远点。(4)平面上的全体无穷远点构成一条无穷远直线。(5)平面上的全体无穷远点与全体平常点构成射影平面。第5章公钥密码算法 2.射影平面坐标系射影平面坐标系射影平面坐标系是普通平面直角坐标系(见图5.8.2)的扩展。我们知道,普通平面直角坐标系没有为无穷远点设计坐标,不能表示无穷远点。为了表示无穷远点,于是产生了射影平面坐标
39、系。当然,射影平面坐标系同样能很好地表示旧有的平常点(数学上也是“向下兼容”的)。第5章公钥密码算法 图5.8.2直角坐标系 第5章公钥密码算法 我们对普通平面直角坐标系上的点A的坐标（x,y）做如下改造：令x=X/Z，y=Y/Z（Z0）；则A点可以表示为（X:Y:Z）。变成了有三个参量的坐标点，这就对平面上的点建立了一个新的坐标体系。第5章公钥密码算法 例例5.8.1 求点（1,2）在新的坐标体系下的坐标。解解：X/Z=1，Y/Z=2（Z0）X=Z，Y=2Z 坐标为（Z:2Z:Z），Z0。即（1:2:1）（2:4:2）（1.2:2.4:1.2）等形如（Z:2Z:Z），Z0的坐标，都是（1,2
40、）在新的坐标体系下的坐标。我们也可以得到直线的方程aX+bY+cZ=0。新的坐标体系能够表示无穷远点么？那要让我们先想想无穷远点在哪里。根据平行线的知识，我们知道无穷远点是两条平行直线的交点。那么，如何求两条直线的交点坐标？设平行直线的方程是：aX+bY+c1Z=0；aX+bY+c2Z=0 (c1c2)。求交点的方法是：将两个方程联立，求解。有c2Z=c1Z=-（aX+bY），c1c2 Z=0 aX+bY=0；所以无穷远点就用这种形式（X：Y：0）表示。注意，平常点Z0，无穷远点Z=0，因此无穷远直线对应的方程是Z=0。第5章公钥密码算法 第5章公钥密码算法 5.8.3椭圆曲线椭圆曲线5.8.
41、2节建立了射影平面坐标系,本节将在这个坐标系下建立椭圆曲线方程。因为坐标中的曲线是可以用方程来表示的(比如单位圆方程是x2+y2=1),椭圆曲线是曲线,所以椭圆曲线也有方程。定义定义5.8.1一条椭圆曲线是在射影平面上满足方程:Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3 (5.8.1)的所有点的集合,且曲线上的每个点都是非奇异(或光滑)的。第5章公钥密码算法 说明说明:(1)式(5.8.1)是Weierstrass方程(该方程由KarlTheodorWilhelmWeierstrass提出),它是一个齐次方程。(2)椭圆曲线的形状并不是椭圆的。只是因为椭圆曲线的描述
42、方程类似于计算一个椭圆周长的方程,故得名。图5.8.3给出了椭圆曲线示意图。第5章公钥密码算法 图5.8.3椭圆曲线示意图 第5章公钥密码算法(3)所谓“非奇异”或“光滑”的,在数学中是指曲线上任意一点的偏导数Fx(x,y,z)、Fy(x,y,z)、Fz(x,y,z)不能同时为0,即满足方程的任意一点都存在切线。图5.8.4中的两个方程都不是椭圆曲线,尽管它们是方程式(5.8.1)的形式,因为它们在(0 0 1)点处(即原点)没有切线。第5章公钥密码算法 图5.8.4非椭圆曲线 第5章公钥密码算法(4)椭圆曲线上有一个无穷远点O(0 1 0),因为这个点满足方程式(5.8.1)。知道了椭圆曲线
43、上的无穷远点,我们就可以把椭圆曲线放到普通平面直角坐标系上。因为普通平面直角坐标系只比射影平面坐标系少无穷远点,所以在普通平面直角坐标系上,求出椭圆曲线上所有平常点组成的曲线方程,再加上无穷远点O(0 1 0),就构成了椭圆曲线。设x=X/Z,y=Y/Z,代入方程(5.8.1)得到:y2+a1xy+a3y=x3+a2x2+a4x+a6(5.8.2)也就是说,满足方程(5.8.2)的光滑曲线加上一个无穷远点O,就组成了椭圆曲线。第5章公钥密码算法 第5章公钥密码算法 5.8.4椭圆曲线上的加法椭圆曲线上的加法5.8.3节中,我们已经看到了椭圆曲线的图像,但点与点之间好像没有什么联系,那么能不能建
44、立一个类似于实数轴上加法的运算法则呢？天才的数学家找到了这一运算法则。自从近世纪代数学引入了群、环、域的概念,就使得代数运算达到了高度的统一。比如,数学家总结了普通加法的主要特征,提出了加群(也叫交换群或Abel(阿贝尔)群)。在加群的眼中,实数的加法和椭圆曲线上的加法没有什么区别。关于群以及加群的具体概念请参考第3章的内容。运算法则:任意取椭圆曲线上的两点P、Q作直线(若P、Q两点重合,则作P点的切线)交于椭圆曲线的另一点R,过R作y轴的平行线交于R。我们规定P+Q=R,如图5.8.5所示。第5章公钥密码算法 图5.8.5加法示意图 第5章公钥密码算法 说明说明:(1)这里的“+”不是实数中
45、普通的加法,而是从普通加法中抽象出来的加法,它具备普通加法的一些性质,但具体的运算法则显然与普通加法不同。(2)根据这个法则可以知道,椭圆曲线的无穷远点O与椭圆曲线上一点P的连线交于P,过P作y轴的平行线交于P,所以有O+P=P。这样,无穷远点O的作用与普通加法中零的作用相当(0+2=2),我们把无穷远点O称为零元,同时把P称为P的负元(简称为负P,记做-P),如图5.8.6所示。第5章公钥密码算法 图5.8.6负点示意图 第5章公钥密码算法(3)根据这个法则可以得到如下结论:如果椭圆曲线上的三个点A、B、C处于同一条直线上,那么它们的和等于零元,即A+B+C=O。(4)k个相同的点P相加,我
46、们记做kP,如图5.8.7中,P+P+P=2P+P=3P。(5)椭圆曲线不一定是关于x轴对称的,如图5.8.8中，y2-xy=x3+1。第5章公钥密码算法 图5.8.7多点相加示意图第5章公钥密码算法 图5.8.8 特殊曲线第5章公钥密码算法 5.8.5密码学中的椭圆曲线密码学中的椭圆曲线我们现在基本上对椭圆曲线有了初步的认识。但是,前面看到的椭圆曲线都是连续的,并不适合用于加密,所以我们必须把椭圆曲线变成离散的点。椭圆曲线都是连续的,这是因为椭圆曲线上点的坐标是实数,实数是连续的,从而导致了曲线的连续。因此,我们要把椭圆曲线定义在有限域上。第5章公钥密码算法 第5章公钥密码算法 第5章公钥密
47、码算法 图5.8.9y2=x3+x+1(mod23)的图像 第5章公钥密码算法 Fp上的椭圆曲线同样有加法，但已经不能给以几何意义的解释。不过，加法法则和实数域上的差不多，请读者自行对比。(1)无穷远点 O是零元，有O+O=O，O+P=P；(2)P(x,y)的负元是(x,-y)，有P+(-P)=O；(3)P(x1,y1),Q(x2,y2)的和R(x3,y3)有如下关系：x3k2-x1-x2(mod p)y3k(x1-x3)-y1(mod p)其中：若P=Q，则k=(3x2+a)/2y1；若PQ，则k=(y2-y1)/(x2-x1)。第5章公钥密码算法 例例5.8.4 已知E23(1,1)上两点
48、P(3,10)，Q(9,7)，求1)-P，2)P+Q，3)2P。解解(1)P的值为(3,-10)(2)k=(7-10)/(9-3)=-1/2，2的乘法逆元为12。因为2*121(mod 23)k-1*12(mod 23)故 k=11。x=112-3-9=10917(mod 23);y=113-(-6)-10=8920(mod 23)故P+Q的坐标为(17,20)第5章公钥密码算法(3)23(mod123410)73(6)23(mod2030336)23(mod64110213322yxk故2P的坐标为(7,12)第5章公钥密码算法 5.8.6简单的加密简单的加密/解密解密公开密钥算法总是基于一
49、个数学上的难题而提出的。比如RSA依据的是:给定两个素数p、q,很容易相乘得到n,而对n进行因式分解却相对困难。椭圆曲线上有什么难题呢？考虑如下等式:K=kG 其中,K、G为Ep(a,b)上的点,k为小于n(n是点G的阶)的整数。不难发现,给定k和G,根据加法法则,计算K很容易,但给定K和G,求k就相对困难了。这就是椭圆曲线密码体制依据的难题。我们把点G称为基点(BasePoint),k(kn,n为基点G的阶)称为私有密钥(PrivateKey),K称为公开密钥(PublicKey)。第5章公钥密码算法 现在我们描述一个利用椭圆曲线进行加密通信的过程：1、用户A选定一条椭圆曲线Ep(a,b)，
50、并取椭圆曲线上一点，作为基点G。2、用户A选择一个私有密钥k，并生成公开密钥K=kG。3、用户A将Ep(a,b)和点K，G传给用户B。4、用户B接到信息后，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r（rn）。5、用户B计算点C1=M+rK；C2=rG。6、用户B将C1、C2传给用户A。7、用户A接到信息后，计算C1-kC2，结果就是点M。因为 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M 再对点M进行解码就可以得到明文。第5章公钥密码算法 图5.8.10ECC加密通信模型 第5章公钥密码算法 密码学中,描述一条Fp上的椭圆曲线
