作者：丁勇(著)
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
椭圆曲线密码快速算法理论试读：
前言
自从W.Hellman和M.E.Hellman于1976年提出公钥密码思想以来，由于其良好的性质以及现代通信网络的发展对信息安全技术需求的强烈增长，公钥密码体系得到了广泛的应用和发展。目前使用较为广泛的公钥密码体系是RSA，但是它也有其局限性，由于存在着亚指数攻击，随着计算能力的不断增强，RSA不得不提高密钥长度来保证其安全强度。1985年提出的椭圆曲线密码体系（ECC，Elliptic Curve Crypto System）是一种基于椭圆曲线群上的新的公钥体系，相对 RSA 而言，它具有安全强度高、密钥长度短、计算速度快、节约通信带宽、节省存储空间等优点，逐渐成为理论研究的热点和实际应用的首选。而对于ECC的快速实现来说，最为关键的因素就是标量乘法kP的计算，因此研究标量乘法的快速算法具有很好的应用前景和迫切的实际需求。[1]
1948年 Shannon发表了划时代的“通信的数学理论”，宣告了信息论的诞生。60多年后的今天，通信、计算机和网络技术的发展已将人类社会推进了一个崭新的信息时代。随着计算机及通信技术的快速发展，数字化、信息化、网络化正冲击、影响并改变着我们生活的方方面面。
自古以来，通信安全保密就成为各国军队和政府高度关注和把持的领域。孙子兵法云：“知己知彼，百战不殆”。因此，如何保证己方信息不被敌方知道就成了战场上的一个决定胜负的因素。历史上的战争，特别是在两次世界大战中，谁能在通信保密、密码分析上占据优势，往往就能在战争中取得主动，有些时候甚至成为扭转战局的关键。因此，早期密码的主要应用就是使用对称加密体制对通信的信息进行加密，以保证自己的情报不被敌方获悉。
在信息社会中，信息是一种重要的战略资源，因特网已经成为世界各国获取经济、军事和科技情报的极其重要的战场。信息高速公路为跨国搜集各种战略信息提供了新的机会，国际上围绕信息的获取、使用及控制的斗争亦愈演愈烈。“谁掌握了信息，控制了网络，谁就将拥有整个世界”（托夫勒）。一个国家的信息获取能力及在社会生产生活领域中“制信息权”的大小，成为了这个国家在生存与发展的竞争中能否占据主动的关键。信息安全已成为信息社会亟需解决的重要问题之一。在 21 世纪，保障信息安全是综合国力、经济竞争能力和生存能力的重要组成部分，是当前世界各国奋力攀登的制高点。
自从20世纪70年代中期Diffie和Hellman提出了公钥密码体系的思[2]想以来，密码学中爆发了一场革命。从那时起，密码学理论和技术已不再是被少数人掌握并服务于政府、军事、外交等神秘领域，而是“飞入寻常百姓家”。基于文献[2]思想的公钥密码体系以及1977年美[3]国NBS制定的公开的数据加密标准DES（Data Encrypt Standard）成为了现代密码学诞生的两个标志。公钥体制的最大特点就是采用两个密钥将加密和解密功能分开：一个公开作为公钥（它的名称由此而来）；一个为用户专用，作为私钥。通信双方无需事先交换密钥就可以进行保密通信，而要从用户公开的公钥以及可得的明文和密文中分析出私钥在计算上是不可行的。若以公钥作为加密密钥，以私钥作为解密密钥，可实现多个用户加密的消息只能由一个用户解读。反之，如果使用私钥作为加密密钥而将公钥作为解密密钥，则可实现一个用户加密，多个用户解读。公钥体制的出现，标志着保密学理论与技术划时代的革命的爆发，主要体现在以下几方面：第一，传统的对称加密体制主要功能是信息保密，而公钥体制则还可以实现消息的认证；第二，公钥体制无需实现交换密钥，大大简化了密钥分配的工作量，尤其适用于当前的大型动态网络；第三，公钥体制实现了密码学和数学（如数论、抽象代数、复杂性理论、组合数学、概率论等）、信息论、计算机科学以及微电子、量子理论等学科的交叉，大大丰富了密码学的内容，为密码学的研究提供了强有力的理论工具和应用领域。
基于 Diffie-Hellman 的思想，公钥密码算法的设计成为了密码学家研究的重点。许多密码学家提出了各种不同的公钥密码算法，有的[4～7][8，是成功的，而有的是失败的。包括背包体制、Willamas体制9][10，11][12～14][15，16]、ELGamal体制、RSA体制、椭圆曲线密码以及新[17～20][21]兴的辫群公钥密码体系和NTRU等。
由于公钥密码体系良好而特殊的性质，当前信息技术的高度发达导致的信息安全需求的多样性和爆发性，它被广泛地应用于信息安全的各个领域，用于构造各种密码应用和安全保护，如消息加密、认证和密钥协商、身份认证、数字签名、数据完整性保护、特殊数字签名、电子选举、电子商务等，特别是以CA和证书为支撑的PKI更是成为构建大型动态安全网络必需的基础设施。
在公开密码体制中，密钥对的选择要保证从公钥求出私钥等价于要求解一个困难的计算问题。公开密钥方案要求参与通信的双方知道一对密钥：私钥不能被其他参与方知道；公钥则以公开的方式保存起来，以便在同一安全方案下的参与方都知道。私钥和公钥通过单项函数联系起来：知道私钥可以很容易地得到公钥，但是知道公钥却很难得到私钥。通常情况下，公钥连同公钥算法一起保存在软件中，而私钥则以硬件的形式保存起来，避免对私钥的截取和篡改。对于N个通信方的网络来说，一方若需要跟网络中任何一方进行安全通信，则只需要保存自身的一个私钥，与其他参与方通信的时候查找相应的公钥即可。很明显，这种方案很好地解决了对称密钥方案的密钥管理问题，更主要的是，有些公开密钥算法可进行数字签名。构成常用公钥密码基础的困难问题是如下的数论问题。
1.整数的因子分解问题，其困难性是RSA公钥密码安全性的基础。
2.离散对数问题，其困难性是 EIGamal 公钥密码及其变体（如数字签名算法）安全性的基础。
3.椭圆曲线离散对数问题，其困难性是椭圆曲线公钥密码安全性的基础。
目前广泛应用于实际系统的公钥密码算法是RSA体制。它的困难性问题是基于大整数的因式分解问题，而大整数的因式分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。该体制简述如下：独立地选取两个大素数p、q，计算n=pq，其欧拉函数φ(n)=(p−1)(q−1)；随机选择一个整数1≤e＜φ(n)，−1计算d=e(mod φ(n))，取公钥为n、e，私钥为d。对于明文m，加密x算法为c=m mod n，其中x为e（公钥加密）或者d（私钥加密）。
椭圆曲线作为代数几何中的一个重要问题，已经有100多年的研究历史，积累了大量的研究文献。直到 1985 年，Kolitz 以及 Miller 才分别独立将其引入密码学领域，构造了ECC（椭圆曲线密码体系）。相对RSA而言，椭圆曲线密码的优势和好处为：第一，安全强度更高。RSA中存在着一般数域筛（NFS）方法攻击，使得其安全强度为亚指[22]数级，而ECC 的安全强度为指数级，即使使用目前国际上公认的有效攻击方法——Pollard orhd方法也很难将其破解。第二，密钥短。在同等安全强度下，椭圆曲线密码的密钥尺寸比RSA体制和ElGamal类体制要小得多，椭圆曲线密码所具有的短密钥这一优势，将适合在存储受限的条件下（如 IC 卡技术等）使用。第三，椭圆曲线密码所需的存储空间小，宽带要求低。由于其存储少、宽带要求低的特点，使得椭圆曲线密码在许多条件受限的领域内具有很优越的发展前景。第四，椭圆曲线密码的计算速度快。在现代分布式网络中，由于服务器的瓶颈效应，使得快速的认证成为了一种迫切的需求。比如一个Web服务器，如果认证速度太慢，就会影响用户访问的热情，导致服务效率降低。由于 ECC 最底层的有限域规模较小，以及相关研究的不断深入，已使得其计算速度大大高于RSA的计算速度。而相对后来的辫群公钥系统以及 NTRU 的新兴公钥系统，ECC 已经得到了广泛而长期的研究和攻击，能提供更可靠的安全性。
推动ECC实际应用的一个里程碑事件就是椭圆曲线数字签名标准[23（]（ECDSA） ANSI X9.62）的公布。之后其他国际组织也纷纷将其[24]标准化，例如 IEEE P1363、ISO、IEC CD14888-3等，而相应的各[25，26][27]种协议也将ECC应用到其中，如IPSec/IKE、WAPI等。其中，由Visa和Mastercard两大信用卡公司于1997年推出的SET（安全电子交易）协议更是将其默认的公钥密码算法置为 ECC。ECC 的加密技术产品已经被广泛应用到各种安全产品中，如VPN网关、防火墙，安全网关、安全路由器、Web服务器、基于ECC的移动终端、SIM卡数字签名模块、无线POS机、CA以及基于ECC的企业级安全解决方案等。可以说ECC已经逐步并将最终取代RSA的主流应用公钥密码算法的地位，将拥有非常广阔的市场。
尽管现有的ECC的计算速度已经比RSA快了很多，但是由于信息技术飞速发展造成的信息膨胀，因此对ECC的计算速度也提出了更高的要求。ECC的快速实现算法将在很长一段时间内成为安全专家研究的重点。
在对椭圆曲线密码的研究中，椭圆曲线密码的构造、分析和快速实现是目前研究的 3个主要方向。由于椭圆曲线密码快速实现直接影响了整个椭圆曲线密码体系的性能，所以快速计算的实现已成为椭圆曲线密码体制能否快速实现的关键，本书主要对椭圆曲线密码快速算法进行了较深入的研究。
经过10多年来的努力研究，密码学家们在ECC标量乘法的快速计算方面取得了令人瞩目的成就。Knuth提出了标量k从右到左的二进制方法。1997年，J.Solinas在二进制方法的基础上，提出了k的非邻接形式（NAF）和窗口 NAF 方法，此后不久又有学者在此基础上提出了滑动窗口方法，这种方法利用额外的存储器，扩大了可能的系数集，降低了标量k的非零密度。目前基于 NAF 的研究有很多，其中主要的研究是与底层域上的快速算法相结合提出新算法。
目前研究最热的是由V.S.Dimitrov等人率先提出的双基数字系统（DBNS，Double-base Number System），此系统的思想是将标量k分解成2与3的幂指数和的形式，减少点加操作的次数。在双基数字系统的基础上，C.Doche和L.Imbert提出了Extended DBNS方法，这种方法扩大了可能的系数集，有效地降低了椭圆曲线密码系统的计算复杂度。K.W.Wong等人在双基表示的基础上，结合半点运算提出了一种新的双基表示，进一步提高了标量乘法的运算效率。近年来，Dimitrov等人对双基数字系统进行了扩展，提出了多基的思想，基于多基思想的研究也是最近几年的研究热点。不少专著和文献对标量k的表示形式进行了更加深入的研究，在标量k的表示方面技术已愈趋成熟。基于双基系统的快速算法的相关研究可参考文献[28～30]。
近年来底层运算有了新的发展，Guajardo等人应用中间变量，用乘法运算来代换求逆运算，提出了二进制域上4P、8P、16P的直接计k算方法，减少了算法的运算量。目前底层运算已经发展到了3P、2P等。
二进制域上的特殊曲线——Koblitz曲线上的标量乘法由于可以不用使用倍点算法，而且其计算相对比较容易，所以，Koblitz曲线的研究也是目前标量乘法研究的主要内容。
另外，Sakai等人于2000年提出了基于双线性对的身份认证协议，最近几年，双线性对获得了广泛的密码应用，涌现出了各种基于双线性对的密码协议。实现这些应用的效率，取决于双线性对的计算速度，而实现这些协议的瓶颈在于能否快速计算双线性对，Miller算法成功地运用倍点—加和切—割线组合来完成这一计算过程。
在ECC的标量乘法的快速计算方面的理论已愈趋成熟，而在ECC的快速实现中，最关键的因素就是标量乘法kP的快速算法研究问题。因此，研究这个问题有着较深的理论意义，更具有迫切的实际意义和广阔的市场前景。
本书的内容安排如下。第1章介绍椭圆曲线密码的基本概念和研究椭圆曲线密码所需的基础知识。第2章介绍椭圆曲线上重要的点的计算公式。第3章讲述了基于NAF分解，提出几种新的标量乘快速算法，如w-NNAF方法、RTSNAF方法等。这些方法使得标量乘的计算复杂性可以进一步降低，最后定量分析了这些方法降低的计算复杂度。第3章是本书的重点。第4章讲述了联合稀疏形（JSF）与Frobenius映射结合的快速算法，该方法以少量的存储为代价获得了一定的运算加速。第5章介绍基于最大公约数（GCD）的高速带模除法，主要对常规 GCD 算法进行了深入分析，改进了算法的判断标准和体系结构，从根本上加快了GCD算法的效率。第6章扩展了基于半点与双基表示的ECC快速标量算法，分析并比较了提出的快速算法的计算复杂度相比于其他算法的优势。第7章提出了一种优化算法，将双基数链与Miller算法相结合，从而缩短了链长，减少了算法中的迭代次数，并将“倍点—加”的过程进行优化，提出新的除子表达式，在迭代过程中优化了除子计算，提高了运算速度。 第1章椭圆曲线密码简介
椭圆曲线是代数几何中一类重要的曲线，至今已有 100 多年的研究历史。而应用于密码学中的椭圆曲线是基于有限域上的，通过引入无穷远点，将椭圆曲线上的所有点和无穷远点组成一个集合，并在该集合上定义一个运算，从而该集合和运算构成了群。在有限域上的m椭圆曲线群有两种，分别基于GF(p)以及GF(2)，它们各自有不同的群元素和群运算，然而对于群上的 ECDLP 问题，都认为是一个指数级的困难问题。基于这个困难问题，构建了ECC算法，包括公钥加密、私钥解密、数字签名、签名验证、DH交换等。1.1 无穷远点
在平面上，任意两条不同的直线只有相交和平行两种关系，为了将这两种关系统一，引入了无穷远点的概念，无穷远点就是两条平行直线的交点。有了这个概念，我们就认为平面任意两条不同的直线都是相交的，对于平行的直线，它们的交点为无穷远点。任何一条直线有且只有一个无穷远点，平面上不平行的两条直线有不同的无穷远点。平面上所有的无穷远点组成一条直线，成为无穷远直线。
为了从坐标上把普通点和无穷远点表示出来，我们使用齐次坐标（X，Y，Z）（X，Y，Z不能全为0）来表示平面上普通坐标为（x，y）的点。二者之间的转化关系为x=X/Z，y=Y/Z，之所以称为齐次坐标，是因为（pX，pY，pZ）表示同一个点。而无穷远点的齐次坐标表示形式为（X，Y，0），无穷远直线的方程为Z＝0。假设在普通的坐标系下一条直线L的方程为：ax+by=c，则在齐次坐标下L的方程为aX+bY=cZ。任何曲线都可以实现方程之间的转化，而且任何曲线都包括无穷远点。1.2 数论相关概念1.2.1 同余和剩余类的概念
这一节我们将给出同余系统的一些结果。
定理 1.2.1 对整数n＞1，同余关系（模n）具有自反性、对称性和传递性，即对任意的a,b,c ∈Z有
1.a ≡ a(mod n)；
2.如果a≡b(modn)，则b≡a(modn)；
3.如果a≡b(modn)，b≡c(modn)，则a≡c(modn)。
满足定理1.2.1中3条性质的关系被称为等价关系。
大家都知道，一个集合上的等价关系把这个集合分为若干个等价n类。令“≡”表示模n同余的等价关系。这个关系定义在集合Z上，因此它把Z恰好分成n个等价类，每个类包含于某整数模n同余的所有整数。把这n个类表示成
其中，={x∈Z|x(modn)≡a}。
我们将上面每一个集合均称为一个模 n 剩余类，显然，我们可以将 Z 看做是。
定理1.2.2 对任意的a,b∈Z定义剩余类和之间的加法和乘法运算为nn
则对任意的n＞1，由“(modn)”定义的映射f:Z→Z是从Z到Z的一个同态映射。
定理1.2.3 对任意整数n＞1，如果a≡b(modn)和c≡d(modn)，则a±c≡b±d(modn)，ac≡bd(modn)。1.2.2 Euler定理和中国剩余定理
定义1.2.1 Euler函数。q
在有限域F上，q≥1，在{1,2,…,n}中与n互素的元素的个数叫做Euler函数，记作φ(n)。
引理1.2.1 设φ(n)是定义1.2.1中定义了的欧拉φ函数。则
1.φ(1)=1；
2.如果p是素数，则φ(p)=p − 1；
3.欧拉φ函数是积性函数。即如果gcd(m,n)=1，则φ(m,n)=φ(m)φ(n)。
4.如果是n的素分解，则
定理1.2.4 对于整数n≥0，有。d
证明 假设S={x|1≤x≤n,gcd(x,n)=d}，显然，对于每个d|n，集合dS={1,2,…,n}被分割成不相交的子集S，所以
注意到对任意的d|n，有，于是
然而，对任意的d|n，我们有φ(d/n)|n，所以
证毕。
例1.1 对于n=12，d |12可能的值是1，2，3，4，6和12。我们有
φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12)=1+1+2+2+2+4=12。
定理1.2.5 Fermat定理。
若p是素数，a是正整数且不能被p整除，则p−1
a≡1mod p
Fermat定理的另一种有用的表示形式是若p是素数且a是正整数，则p
a≡p mod p。
定理1.2.6 Euler定理。q
令={a|a∈F,gcd(a,q)=1}，则(q≥2)中元素a满足φ(q)
a≡1modq
其中，表示有限域中所有的非零元素的集合。
定理1.2.7 中国剩余定理（CRT)。12r12r
令r个整数m,m,…,m两两互素，a,a,…,a是任意r个整数，则同余方程ii
x≡a mod m，1≤i≤r （1-1）
有如下唯一解ii12rii
其中，M=M/m，M=mm…m，y=modm，1≤i≤r。
算法1.1 中国剩余算法12r
输入：整数多元组(m,m,…,m)两两互素；1122rr
整数多元组(a(modm),a(modm),…,a(modm))12r
输出：整数x＜M=m,m,…,m满足方程（1-1）12r
1.M←mm…m
2.对于i=1,2,…,r重复执行−1iii（1）y←(M/m)(modm)ii（2）←yM/m
3.返回
中国剩余定理是数论中最有用的定理之一，它说明了某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构。1.3 有限域简介
有限域的具体相关知识请参看文献[31]。我们这里仅列出一些重要的概念和定理。
定义1.3.1 任意给定一非空集合G和其上的二元运算“∗”，如果满足：
1.封闭性：对任意a,b∈G，存在c∈G，使得a∗b=c；
2.结合律：对于任意a,,bc∈G，都有(a∗b)∗c=a∗(b∗c)；
3.单位元e存在：即存在e∈G，对于任意a∈G，都有e∗a=a∗e；
4.逆元存在：对于任意a∈G，存在b∈G，使得b∗a=a∗b=e，b称为a的逆元。则称集合G关于二元运算“∗”构成群，记为：
在群
定义1.3.2 设“+”，“∗”是G上的二元运算，集合的基数|G|>1，如果满足：
1.
2.
3.运算“*”对“+”可分配，即对任意a,b,c∈G，都有
a∗(b+c)=(a∗b)+(a∗c)
(a+b)∗c=(a∗c)+(b∗c)
则称
例如：
定义1.3.3 有限域，又称伽罗华（Galois)域，顾名思义，就是指域G元素个数为有限的域。其中，G中的元素个数称为有限域G的阶，记为|G|。
定义1.3.4 设G是任意域，1是G的单位元。
如果对于任何正整数n，有
则称域G的特征为0；
如果存在正整数n，满足
则称满足上式的最小正整数n为G的特征，记为ChG=n。
定理1.3.1 若G是域，则G的特征为0或者是一个素数p。
定理1.3.2 从同构意义上来说，则只存在两种有限域。一种有限m域元素个数为p（p为正素数），记做GF(p)；另一种元素个数为p（pm为正素数，m为正整数），记做GF(p)。
定义1.3.5 有限域的全体非零元素都可以用域中某一个元素的幂次来表示，我们称这个元素为域的本原元。l
定义1.3.6 对于有限域上的一个元素x，满足x＝1的最小的正整数l称作元素x的阶。
有限域GF(p)可以用区间[0，p−1]上的全体整数来表示，并且满足如下条件。
1.乘法中的幺元为整数1。
2.加法中的零元为整数0。
3.域中的加法为模p加法，即任取a,b∈GF(p)，有a⊕b=(a+b)mod p。
4.域中的乘法为模p乘法，即任取a,b∈GF(p)，有a⊗b=(a×b)mod p。mm
对于有限域 GF(p)，由于主流的 ECC 算法中只用到 GF(2)，mmm因此我们这里只介绍GF(2)，GF(p)的表示方式也和GF(2)类似。mGF(2)可以看做是GF(2)上的一个m维向量空间，只要确定了空间上m的基，GF(2)上的任何一个元素都可以用这些基的线性组合来表示。若用多项式基表示，首先确定一个 GF(2)上的 m 次不可约多项imm式 f(x)，则多项式x(0≤i 因此，GF(2)对应所有次数小于m的GF(2)上多项式，也对应于长度为m的所有比特串，并且有如下法则。 1.乘法幺元为1，用(0,0,…,0,1)表示。 2.加法的零元为0，用(0,0,…,0,0)表示。 3.域上的加法为两个元素对应比特串的异或（XOR）运算。 4.令a的多项式表示为a(x)，b的多项式表示为b(x)，r(x)=a(x)b(x)mod f(x)，则ab=r。mm 对于有限域GF(2)，总存在元素β∈GF(2)，使得{,,…,m}为GF(2)的一组基，我们把这种形式的基称为正规基。任取i一个元素α，都可以唯一地表示为(a∈GF(2))，因此可用mm−1m−210长度的比特串(a,a,…,a,a)来表示。在正规基表示下，有如下的运算法则。 1.加法的零元为全0比特串。 2.乘法的单位元为全1比特串。 3.两个元素的加法为异或（XOR）运算。 4.乘法的运算可看做是关于β的两个多项式的乘积，再将其转化为标准形式。 使用正规基的一个最大的好处就是使得乘方运算非常简单，只需要一个右循环移位，尽管这样会使得不同的两个元素的乘积运算比较复杂，但是幸运的是对于不能被8整除的m，总存在一种特殊的高斯正规基（GNB），在这种正规基下，乘法同样也能快速地计算。1.4 椭圆曲线简介1.4.1 椭圆曲线的概念 这里所说的椭圆曲线并不是通常意义的椭圆，它是一类特殊的曲线，有限域K上椭圆曲线的方程形式为12346 其中，a,a,a,a,a∈K且满足E的判别式Δ≠0，则具体定义为 如果L为有限域K的扩域，则，这里符号O表示无穷远点。12346 上式即为著名的Weierstrass方程，由于a,a,a,a,a∈K，所以称E为K上的椭圆曲线，一般记为E/F。需要注意的是，如果E定义在K上，则E必然定义在K的扩域上。 条件Δ≠0确保了椭圆曲线的光滑性，也就是说曲线上没有一个点有两个或者更多的不同切线。 无穷远点O在曲线上是唯一存在的，它满足Weierstrass方程的投影形式。 定义1.4.1[32] 定义在有限域K上的下列椭圆曲线232113246 E:y+axy+ay=x+ax+ax+a
试读结束[说明：试读内容隐藏了图片]