第1章 数学背景 1
1.1 数论 1
1.1.1 模运算 1
1.1.2 素数 3
1.1.3 最大公因子 3
1.2 域表示 4
1.2.1 有限域 Fp 4
1.2.2 有限域 F2m 5
1.2.3 用 ONB 表示的 F2m 中元素的乘积 7
1.3 不可约多项式和本原多项式的判定 11
1.4 复杂性理论 13
1.4.1 算法与问题 13
1.4.2 算法复杂性 14
1.4.3 问题复杂性 15
第2章 RSA 公钥密码 18
2.1 RSA 加密算法 18
2.2 RSA 签名算法 20
2.3 RSA 公钥密码的安全性及攻击 RSA 公钥密码的一些典型方法 21
2.3.1 RSA 公钥密码的安全性 21
2.3.2 攻击 RSA 公钥密码的一些典型方法 22
2.4 素性检测 26
2.4.1 Fermat 素数 28
2.4.2 Solovay-Strassen 素性检测 29
2.4.3 Miller-Rabin 素性检测 30
2.4.4 Mensenne 数的素性检测 32
2.4.5 利用 n-1的因子分解进行素性检测 34
2.4.6 Jacobi 和检测 36
2.4.7 椭圆曲线素性证明 36
2.4.8 强素数 36
2.5 因子分解算法 38
2.5.1 试除法 39
2.5.2 Pollard-ρ 因子分解算法 40
2.5.3 Pollard p-1因子分解算法 42
2.5.4 椭圆曲线因子分解算法 44
2.5.5 随机平方因子分解算法 44
2.5.6 连分式因子分解算法 46
2.5.7 二次筛法 49
2.5.8 数域筛法 51
2.6 RSA 公钥密码的实现 52
2.6.1 RSA 公钥密码的建立 52
2.6.2 模算术运算 54
2.7 参考与注记 65
3.1 离散对数问题 68
第3章 ElGamal 公钥算法 68
3.2 ElGamal 加密算法 69
3.3 ElGamal 签名算法 72
3.4 离散对数算法 73
3.4.1 穷尽搜索 73
3.4.2 baby-step giant-step 算法 73
3.4.3 Pollard-ρ因子分解算法 75
3.4.4 Pohlig-Hellman 算法 78
3.4.5 index-calculus 算法 80
3.5.1 选取素数 p 和 Z*p 的生成元 85
3.5 ElGamal 密码算法的实现 85
3.5.2 模运算 86
3.6 参考与注记 86
第4章 椭圆曲线公钥密码 88
4.1 椭圆曲线上的基本运算 88
4.1.1 Fp 上的椭圆曲线 88
4.1.2 F2m 上的椭圆曲线 91
4.2 椭圆曲线公钥密码简介 94
4.2.1 椭圆曲线上的离散对数问题 94
4.2.2 椭圆曲线公钥密码的攻击现状 95
4.2.3 椭圆曲线公钥密码算法 96
4.3.1 系统的参数选取 102
4.3 椭圆曲线公钥密码的实现 102
4.3.2 椭圆曲线上的快速算法 108
4.4 参考与注记 116
第5章 背包加密算法和其他公钥密码 117
5.1 Merkle-Hellman 背包加密算法 117
5.1.1 多重迭代 Merkle-Hellman 背包加密算法 120
5.1.2 Merkle-Hellman 背包加密算法的不安全性 120
5.2 Chor-Rivest 背包加密算法 121
5.2.1 Chor-Rivest 公钥加密算法的实现 125
5.2.2 Chor-Rivest 公钥加密算法的安全性 125
5.3.1 L3-格基约简算法 126
5.3 背包公钥加密算法的破译 126
5.3.2 子集和问题的解 129
5.4 Diffie-Hellman 公钥算法 131
5.4.1 三方或多方情况下的 Diffie-Hellman 密钥交换协议 132
5.4.2 算法的实现 133
5.5 Rabin 公钥加密算法 133
5.5.1 Rabin 公钥加密算法的安全性 135
5.5.2 Rabin 公钥加密算法的实现 136
5.6 McEliece 公钥加密算法 136
5.7 LUC 公钥算法 138
5.8 参考与注记 139
参考文献 140