椭圆曲线密码体制（ECC）是当前主流的公钥密码体制，该体制的安全核心是椭圆曲线离散对数问题（ECDLP）。本书首先对椭圆曲线离散对数及其相关问题，以及它们之间的相互关系进行了探讨，然后主要介绍了椭圆曲线离散对数问题的计算方法，包括通用的平方根算法及其改进、特殊椭圆曲线离散对数的计算方法、指标计算方法的努力、归约到NPC问题的方法和量子算法等，基本涵盖了ECDLP的所有求解算法。这些算法大都给出了实例验证，这为读者更好地理解它们提供了帮助。
样章试读
目录
- 目录
“密码理论与技术丛书” 序
前言
第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
京公网安备 11010102004214号