第1章绪论
密码学是保障信息安全的核心工具.密码学的英文是Cryptography，是由古希腊语（罗马化为krypt6s）“隐藏的”和YPcpeiv（罗马化为grSphein）“书写”派生而来的，是研究如何隐秘地传递信息的学科.密码学已经有数千年的历史，从古埃及金字塔中的加密象形文字和中国古代周朝兵书《六韬 龙韬》记载的《阴符》和《阴书》的远古密码，到近代第二次世界大战时期德军使用的恩尼格玛（ENGMA）和日军使用的紫密的电子机械密码，现在广泛应用的高级加密标准（AES）、RSA和椭圆曲线密码体制（ECC），以及正在研究中的后（抗）量子公钥密码等现代密码体制.密码学的研究从时间上来分的话，分为古典密码学和现代密码学.这种分类的时间分水岭是1976年，因为这一年密码学研究历史上发生了两个非常重要的事件：公钥密码学的提出和美国数据加密标准（DES）的颁布.这两大事件标志着现代密码学的开始，密码学的研究从军事和外交走向了公开.Whitfield Diffie和Martin Heilman在1976年发表的论文“New Directions in Cryptography”，标志着公钥密码学的诞生，这一体制不仅可以用来加密，还可以用来实现数字签名，从而实现认证性、完整性以及不可否认性.
信息化和网络化的发展是公钥密码学诞生的历史背景和社会需求.迅速发展的互联网给人们的生活、工作带来了极大的方便，人们可以坐在家里通过互联网进行收发电子邮件、视频通话、网上购物、银行转账等活动.在利用像互联网这样的公开性网络进行通信或商业活动时，一个非常大的现实问题是如何同不认识的人进行安全的或秘密的通信，或确认对方发来的信息是否正确.在公钥密码体制未出现之前，不借助安全通道或密钥共享来解决这个问题几乎是不可能的.而有了公钥密码体制，这个问题就可以很容易解决了.在公钥密码出现以前的密码体制的主要功能就是加密，从而确保信息的机密性.有了公钥密码，密码不仅具有加密的功能，还具有了认证的功能.在今天的信息安全中，特别是在数字签名、身份认证和密钥管理中，公钥密码学是必不可少的.
公钥密码体制又称非对称密码或双钥密码体制，通信的接收方和发送方使用的密钥不同，而且几乎不可能从加密密钥推导出解密密钥.公钥密码系统的每个用户U选择一对密钥（PK^SKd，分别称为公钥和私钥，并构造出自己的加密算法EPKu和解密算法DSK[7.每个用户将他的加密密钥和加密算法公开，可以像电话号码簿一样公开让其他用户来查找，而解密密钥则由用户自己保密管理.如果用户A要给用户B传送秘密信息m，A最先从公开信息上查到B的公钥PKb，用B的加密算法和公钥对明文m加密得密文，并将c发送给B.B接收到密文c后，用自己的私钥和一个确定的解密算法来恢复明文消息mDSKB（c）.这就是一般的公钥密码系统的加密、解密过程.由此可见，公钥密码系统使得任何一个用户都可用某一用户U公开的加密密钥给该用户发送经公开加密算法加密的消息，用户不必事先分配和保管传统密码系统丨即对称密码系统）所需的大量密钥.另外，如果用户U用自己的私钥SK；对消息m作用，作用结果只有借助U的公钥PKy才可以验证的话，则该公钥系统就给用户U提供了对消息进行签名和身份认证的功能.
Diffie和Heilman在提出公钥密码系统的薪新概念时，自己还未能解决实现这种系统的具体方法，但他们的思想很快引发了RSA和背包公钥密码系统的诞生.实际上，公钥密码体制可以看成是单向陷门函数.非形式化地讲，单向函数就是那些容易计算但难于求逆的函数（关于单向函数的形式化定义和性质，可以参见Goldreich的书[108]关于单向函数的描述构造公钥加密方案，仅靠一个单向函数是不够的，还得需要存在某个陷门使得这个函数能够有效求逆.如果有这样的单向陷门函数就可以构造公钥加密方案:单向函数的描述就是公钥，函数计算就是加密算法；而陷门就是私钥，借助陷门有效求逆过程就是解密算法.所以，只要构造出单向陷门函数，就可以构造公钥加密方案.尽管有很多函数被认为是单向的，例如整数分解问题、离散对数问题、背包问题等，但至今还没有一个函数能被严格证明是单向的.也就是说，单向函数是否存在至今还没有被证明.根据计算复杂性理论我们知道，如果单向函数存在，那么任何NP问题都有零知识证明协议.然后，借助Fiat-Shamir变换可以将交互式零知识证明转换为非交互式的，从而可以构造出数字签名方案.也就是说，基于任何单向函数都可以构造数字签名方案（当然效率高低取决于具体函数的性质但是，构造公钥加密方案不只是需要单向函数，还得是单向陷门函数.从这一点上说，数字签名方案比公钥加密方案更容易构造.
自从公钥密码的概念被提出以来，相继出现了许多公钥密码方案.在不断的研究和实践中，有些方案被攻破了，有些方案不太实用.在四十多年的公钥密码研究中，我们发现基本上十多年就出现一个研究热点.在公钥密码学提出的第一个十年（1976-1986）的研究中，主要是基于初等数论的公钥密码学，集中在整数分解密码体制（如RSA，Rabin等）和有限域乘法群的离散对数密码体制（如Diffie-Hellman密钥协商协议、ElGamal加密方案和数字签名方案等）.这两类密码体制成了公钥密码学的第一个研究热点.尽管在这一时期也有一些其他的非常有趣的方案被提出，例如Merkle和Heilman[173]提出的基于背包问题的公钥密码系统、McElieCe提出利用纠错码构造的公钥密码体制等，但由于这些方案要么被证明不安全了，要么被认为不实用，所以在当时并没有形成主流研究方向.第二个研究热点是1985年提出的椭圆曲线密码体制，这一体制的数学基础比之前的公钥密码体制更高深和丰富些.由于这种体制与当时存在的一些公钥密码体制（特别是与当时已经占主导地位的RSA体制）相比，无论在安全性上还是性能上都有着非常大的优势，所以该体制一经提出，就被广泛关注，甚至成了当前应用最广泛的公钥密码体制.公钥密码学的第三个研究热点是2000年左右开始的基于双线性对的密码体制.双线性对在密码中的最早应用是1993年，Menezes，Okamoto和Vanstone[168]给出的超奇异椭圆曲线离散对数问题的MOV攻击.在2000年，双线性对被发现在密码中有正面的应用--能够用来构造密码体制，如基于身份的密码体制（IBE）、三方一轮密钥协商、一些带有特殊性质的签名等，这使得双线性对密码体制的研究一度成为一个热点，并持续了十多年.所取得的研究成果丨特别是发表的文章数量）在密码学研究领域创造了一个不小的奇迹.量子计算理论和量子计算机的研究与发展，对已经广泛应用的ECC和RSA等公钥密码体制产生了严重的安全威胁.为抗击量子计算机的挑战，近十多年来国内外掀起了后量子密码体制的研究热潮.基于一些NP困难问题的后量子公钥密码研究是当前的一个研究热点，特别是基于格的密码体制、多变量多项式的密码体制、纠错码的密码体制等.
密码学是一个理论和实践相结合的学科，密码体制的研究最终要为实际应用服务.评价一个公钥密码体制好不好，有没有使用价值，除了安全性以外，还有以下几个因素：密钥尺寸不能太大；加、解密的实现比较容易，用硬件实现电路规模不大，用软件实现速度较快;密文没有太大的扩展；能够方便地产生大量的新密钥;能够进行数字签名等.目前，第一的广泛应用于实际中的只有三种类型的公钥系统是有效的和安全的，即基于大整数分解的RSA公钥密码、基于有限域乘法群上的离散对数问题的数字签名算法（DSA）或ElGamal加密体制和基于椭圆曲线离散对数的ECC.这三类实用的公钥密码体制相比较的话，最主流的公钥密码体制当属ECC.
椭圆曲线密码体制是由华盛顿大学的Neal Koblitz[143]和当时在IBM工作的Victor Miller于1985年相互最立地提出的，这使得被数学家在数学领域研究了150多年的椭圆曲线在密码领域中得以发挥重要作用.椭圆曲线密码体制的数学基础是有限域上椭圆曲线有理点群中的离散对数问题（ECDLP）的计算困难性.所以说ECC属于离散对数密码系统.
一般来说，如果一个群G（x，l）满足如下三个性质时，就可用于构造基于离散对数的密码体制：
（1）群元素可以（用计算机）紧致地表示；
（2）群运算可以有效地执行；
（3）离散对数问题（给定g，h=ga&G，计算a）是困难的.
有限域的非零元素全体构成一个循环群，显然这个循环群满足前两个条件.而这个群的离散对数问题具有亚指数时间算法，所以选择合适的参数，可以利用有限域上的乘法群构造密码体制，例如ElGamal加密方案和DSA数字签名方案就是利用素域Fp的乘法群来构造的.从体制上说，ECC并没有给出任何新的方案，它只是提供了一个实现传统离散对数密码体制的新的载体，就是将原来基于有限域的乘法循环子群的密码方案平移到有限域的椭圆曲线群上来，如Diffie-Hellman密钥协商协议变成ECDH、DSA变成ECDSA等.由于椭圆曲线所具有的特性，ECC可以在相同安全级别下使用比其他一些密码体制更短的密钥，例如在128比特的对称密码体制的安全级别下，ECC只需要256比特的密钥，而RSA密码体制则需要2048比特的密钥.所以利用ECC不但可以实现髙度安全性，而且在同等安全强度下，可以只需要较小的开销（所需的计算量、存储量、带宽、软件和硬件实现的规模等）和时延（加密和签名速度髙）.因此，ECC特别适用于计算能力和集成电路空间受限（如Smart卡）、带宽受限（如无线通信和某些计算机网络）、要求高速实现的情况.由于ECC比其他的公钥体制有着无法替代的优点，所以ECC从一提出就被得到广泛关注.经过这几十年的研究，ECC的理论已经比较成熟，并在实际中得到了广泛应用.当前流行的公钥密码产品多数是用ECC实现的.以比特币为代表的一些密码货币的实现也是基于ECC的.作为ECC的一个推广，Neal Koblitz在1989年提出了超椭圆曲线密码体制（HCC）它是基于有限域上超椭圆曲线的Jacobian上的离散对数问题，所以也属于离散对数密码系统.Cantor的算法-为实现超椭圆曲线的Jacobian中的群运算提供了一个有效的算法.在同等安全水平下，超椭圆曲线密码体制所用的基域要比椭圆曲线密码的小，且可以模拟基于一般乘法群上的如DSA，ElGamal等几乎所有协议，所以对超椭圆曲线密码体制的研究也被大家重视.
椭圆曲线理论的研究本来属于数学领域，从20世纪80年代初才开始进入到密码学研究领域.关于椭圆曲线应用在密码中的一个介绍，可以参看文献[7].椭圆曲线在密码中的最早应用是荷兰数学家Hendrik Lenstra在1984年[153]提出的利用椭圆曲线性质分解整数的精妙算法.之后，Shafi Goldwasser和JoeKi-lian在1986年提出一个利用椭圆曲线做素性检测的想法[11Q]，该想法由Oliver Atkin在同年转化成一个算法，后来该算法被许多研究者改进I19!，变成了现在常用的素性检测算法ECPP.1985年，Koblitz和Miller提出的ECC实际上是利用椭圆曲线群代替了有限域上的乘法群，只是提出了一个实现传统离散对数密码体制的新载体.真正利用椭圆曲线构造出新的密码体制的是双线性对密码体制.双线性对具有非常有趣的特性，利用双线性对可以构造出一些其他数学问题所不能或很难设计的密码方案，如基于身份的密码体制、形形色色的签名方案等.基于双线性对的密码体制在工业界已经有了许多应用实例.随着应用的日趋广泛，国际上许多标准组织也制定了这一密码体制的一些标准，如国际标准化组织（ISO）在ISO/IEC14888-3中给出了两个利用双线性对设计的基于身份的签名体制的标准，电气电子工程师学会（IEEE）也组织了专门的基于身份的密码体制的工作组（IEEEP1363.3）.我国也推出了商用密码标准SM9基于标识的密码（IBC）等.
不管是椭圆曲线密码体制还是双线性对密码体制，如果定

目录
“密码理论与技术丛书” 序
前言
第1章 绪论 1
第2章 椭圆*线 6
2.1 椭圆*线及其群运算 6
2.2 椭圆*线的其他方程形式及其运算 13
2.2.1 三次方程(Hessian *线) 13
2.2.2 四次方程 14
2.2.3 二次*面的交 14
2.2.4 Huff*线 16
2.2.5 Edwards*线 17
2.3 有理数域上的椭圆*线.19
2.3.1 Mordell定理 19
2.3.2 标准高度 19
2.3.3 除多项式与椭圆除序列 21
2.4 自同态与自同构 22
2.5 有限域上的椭圆*线 25
2.5.1 有限域上的椭圆*线的群结构 25
2.5.2 F2m上的椭圆*线及其群运算 28
2.5.3 标量乘运算 29
2.6 除子和双线性对 30
2.6.1 除子 30
2.6.2 双线性对 32
2.6.3 Miller算法 35
第3章 椭圆*线密码体制介绍 39
3.1 椭圆*线密码体制 39
3.1.1 椭圆*线密钥协商方案 40
3.1.2 椭圆*线加密方案 40
3.1.3 椭圆*线数字签名方案 43
3.2 椭圆*线密码体制的标准 44
3.2.1 国外标准简介 44
3.2.2 中国椭圆*线密码标准 SM2 46
3.3 双线性对密码体制 50
3.3.1 密钥协商 51
3.3.2 基于身份的加密体制及其推广 51
3.3.3 基于双线性对的签名 53
3.3.4 双线性对密码的标准化 55
第4章 椭圆*线离散对数及其相关问题 57
4.1 ECDLP 57
4.1.1 ECDLP的定义 57
4.1.2 ECDLP的比特安全性 58
4.1.3 ECDLP的通用算法 60
4.1.4 ECDLP的其他形式 62
4.2 CDHP及其变形 64
4.2.1 EC-CDHP 64
4.2.2 平方CDHP 65
4.2.3 逆CDHP 66
4.2.4 平方根CDHP 67
4.3 ECDLP与ECDHP的等价证明 72
4.3.1 Maurer的证明.72
4.3.2 一个实践中的例子 76
4.3.3 进一步的讨论 77
第5章 特殊椭圆*线的离散对数问题.78
5.1 光滑阶的椭圆*线 78
5.2 MOV攻击和FR攻击 80
5.3 非常规*线算法 84
5.3.1 代数数论方法 84
5.3.2 代数几何方法 90
5.4 扩域*线 94
5.4.1 Weil下降方法 95
5.4.2 F2ln上椭圆*线：GHS算法 96
5.4.3 GHS 算法的推广 102
5.5 新的陷门 104
第6章 ECDLP的平方根攻击.107
6.1 小步大步法及其改进108
6.1.1 小步大步法 108
6.1.2 小步大步法的改进方法 109
6.2 Pollard 算法 118
6.2.1 生日悖论 118
6.2.2 原始的Pollard rho算法 120
6.2.3 改进的Pollard rho算法 123
6.2.4 Pollard lambda 算法 128
6.2.5 借助负映射提速Pollard rho 算法 130
6.2.6 平方根算法总结 132
6.3 特征2域上改进的迭代算法 133
6.3.1 利用半分设计迭代函数 134
6.3.2 优化配置.138
6.3.3 借助同时逆实现并行Pollard rho算法 141
6.4 实际攻击 145
6.4.1 Certicom挑战 145
6.4.2 ECC2-131的相关运算实现 147
6.4.3 ECC2-131求解评估与分析 153
第7章 指标计算方法的努力.157
7.1 指标计算方法与实例157
7.1.1 指标计算方法的基本思想 157
7.1.2 两类成功应用指标计算的群 158
7.2 提升方法 167
7.2.1 提升的基本思路 167
7.2.2 提升到p-adic非挠点 168
7.2.3 提升到p-adic挠点 170
7.2.4 提升到全局挠点 172
7.2.5 提升全局非挠点 173
7.3 加和多项式方法 177
7.3.1 加和多项式定义 177
7.3.2 Semaev算法 179
7.3.3 特征2域上ECDLP的指标计算 183
第8章 归约到NPC问题 186
8.1 NPC 问题 186
8.2 ECDLP 到子集和问题 189
8.2.1 子集和问题 189
8.2.2 ECDLP转化成子集和的实例 191
8.3 ECDLP到多变量多项式方程组求解问题 193
8.3.1 多变量多项式方程组求解问题 193
8.3.2 利用多变量多项式方程组计算 ECDLP 194
8.3.3 多变量多项式方程组的新归约 199
8.4 利用 SAT计算ECDLP 201
8.4.1 SAT 201
8.4.2 SAT 在计算ECDLP中的应用 203
8.5 椭圆码的列表译码与ECDLP 206
8.5.1 纠错码与代数几何码 207
8.5.2 列表译码 209
8.5.3 列表译码与计算*小重量码字 210
8.5.4 利用列表译码计算ECDLP 214
第9章 量子算法 219
9.1 量子比特和量子门 219
9.1.1 量子比特 219
9.1.2 量子门 220
9.2 离散对数的Shor算法 222
9.2.1 量子傅里叶变换 222
9.2.2 Shor算法 222
9.3 ECDLP的量子算法 224
9.3.1 有限域基本运算的量子门实现 224
9.3.2 椭圆*线运算的量子门实现 226
9.3.3 ECDLP的量子计算评估 229
参考文献 233
索引 248
后记 250