椭圆曲线离散对数问题

目录 “密码理论与技术丛书” 序 前言 第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