密码学--加密演算法

胜利是属于“公理正义”的一方。在历史长河中，取得战争胜利的一方，往往取得历史的“解释权”，他们的意识形态就理所当然地成为所谓的“主流价值观”，因此，胜利者会被“解释”成“公理正义”的一方，而失败者会被无情地“污名化”、“妖魔化”。一般而言，胜利是属于“掌握优势资源”的一方，这些优势资源包括了军事力量、先进科技、生产技术等等，同时也包括了为人讳言的“密码技术”。

二次世界大战中，日本海军联合舰队可以说是当时世界上最强的舰队，而美国在珍珠港战役之后，海军实力已处于劣势。然而，美国却能破译日本的密码，在一连串所破译的密电中，显示出了日本海军大将山本五十六的行踪以及联合舰队的动向，使美国能够在山本五十六飞往所罗门群岛途中将其狙杀，并以劣势兵力赢得中途岛海战，这是整个太平洋战役的转折点。

勿庸置疑，密码学的确是一门实用的科学；从以往王侯将相用来对他们所发布的信息加密，到今日的电子商务、“自然人认证”、网络安全等，其中所用的核心技术就是密码学。

谈到当代密码学的核心，我们就不可避免地要了解当代密码系统的运作机制；要想对其安全性评估，就不可避免地要了解密码系统的算法；如果只是将密码系统算法轻描淡写，或只是套用一些专业术语，充其量只能是“按图索骥”，对于使用密码学技术不会有实质性的帮助。因为任何密码学所能提供的安全保证，不是建立在“入侵者无知”的假设上，其所要面对的是精通各类信息技术、了解密码系统算法的超级骇客。

诚然，信息安全的漏洞，往往不是发生在所用的密码算法上，而主要是由系统管理员造成的；也许密码系统程序员能够遵循密码学算法，编写一份近乎“完美无缺”的系统，却可能忽略了运行系统随机产生的软硬件问题；有时甚至所使用的密码学产品本身就是泄密机。即使是以当代密码机RSA、DES、Triple DES为加密系统的“保健IC卡”或是“自然人认证”，都曾发生过资料保密上的纰漏，被人视为近乎“完美无缺”的系统，却无法保证非密码层面不出问题。

本书并不想对整个信息安全的大架构进行讨论，因为除了理论上的探讨外，必须很实际地，从管理层面探讨，这并非单从算法、协定中能解释清楚的，这是大师级的工作，绝非笔者所长，但是当代密码学各类算法，有精确的数学描述方式，可以将其程序化，并将这些内容列入教材，成效会丰常显著。

一个成熟耐用的密码系统，首先要有能经得起严谨理论考验的算法。综观当代密码系统，主要可分为公开密钥密码系统（Public Key Cryptosystem）以及对称密钥密码系统（Symmetric Key Cryptosystem）两类。以前者为代表的有RSA、ElGamal、椭圆曲线密码系统，而以后者为代表的有DES、AES等。这些密码系统，都要用到一些数学上的概念，而用到最多的数学相关知识，是被数学王子高斯誉为“数学女王”、被人们视为最冷门的“数论”（Number Theory）；由于真正“了解内情”的人实在不多，所以用当代密码技术为幌子行骗的空间很大，鉴于此，笔者特将相关的基础数论内容列入本书，其实就是大学“代数”以及部分“质数”理论，这些内容都是研究当代密码学的基础。

由于当代密码技术的应用已经不是只在“纸上谈兵”而已，必须依赖程序应用。所以在本书编排上，特别用类似C/C++/Java的语法，对部分已成熟的算法写成伪码，只需很少的修改，就可以执行运算。对于密码算法的学习，有相当的帮助。

尽管古典密码早已不符合当代信息安全的需求，但就其中所带来的益智性乐趣，笔者实在不想只是轻描淡写；就二次大战期间德国人所用的Enigma密码机而言，除了历史上的乐趣外，其中的加密解密运算，其实就是对称群的置换作用，就如同转动魔方一样，是绝佳的“群”作用范例，令人着迷不已。

记得1998、1999年冬天，曾与RSA的A合作过的黄明德在台湾大学讲述他的一系列工作，在那时笔者领略到高深的“数论”以及“代数几何”应用到密码学的研究是深邃而引人入胜的。

本书在撰写中，费时最久的是书中的每个例题，这些例题，除了少数参考了其他文献外，大多数都是程序执行的结果整理而成，部分也取自笔者的研究内容。

另外，本书部分内容，如RSA密码、非对称密钥密码与离散对数、数字签名以及部分古典密码的介绍，都是笔者在清云科技大学教授“密码学”、“公开钥密码系统”时讲授过的。笔者所指导的专题学生，也分别以“RSA电子投票研究”、“保健IC卡研究”、“RSA与PGP研究”当作专题研究方向，专题学生林俊余与黄明宗等人，也做出以Java撰写的RSA为基础的“电子投票系统”的半成品，虽然离成熟产品还有很大距离，但也属难能可贵。感谢这些专题学生林俊余、林罔永、许丰琳、杨贺杰、黄明宗、徐效群、林克儒、陈惠甄、陈华君、陈丽君、陈俞婷、李建志、潘丹尼、吴英绮的热心参与，使得笔者在密码学的授课以及学生研究会讨论过程中，增加不少互动。所谓“教学相长”，这对本书的撰写也有一定的帮助。

在本书即将完成之际，笔者仍发现密码学实在涉略广大，许多内容只好忍痛割舍，限于各种因素，无法面面俱到，作为教材不免有遗珠之憾。

特别感谢（台湾）中央研究院数学所谢春忠教授对本书算法及算式逐一检查校阅。感谢中央研究院数学所提供笔者短期访问的机会，不少研究密码学的相关文献资料，都是在此取得。更感谢清云科技大学的系主任李振焘教授及系同事的支持与协助。另外在Lilie的协助下，本书也加上了“福尔摩斯密码”一节，替本书增色不少。

本书部分函数图形由数学软件Mathematica产生，部分精美的图案由全华科技图书绘制而成。感谢Bletchley Park Trust所提供的珍贵照片及Sue May的协助，也感谢Brian Smith的居中联络。

邓安文

序
前言
第1章 绪论 1
1.1 通信安全 1
1.2 公开密钥密码系统与对称密钥密码系统 5
第2章 古典密码 7
2.1 凯撒挪移码 8
2.2 仿射密码 9
2.3 单套字母替代法以及频率分析 10
2.4 福尔摩斯密码 13
2.5 Vigenère密码 15
2.6 Hill密码 20
2.7 单次密码本 21
2.8 Enigma密码机 22
2.9 破译Enigma与对称群 27
第3章 基础数论 31
3.1 模运算与辗转相除法 31
3.2 中国余式子定理（Chinese Remainder Theorem） 36
3.3 Lagrange定理与费马小定理 38
3.4 原根 39
3.5 二次剩余（Quadratic Residue） 41
3.6 Galois域 45
3.7 质数理论 48
3.8 连分数 51
3.9 密码安全伪随机数生成器 54
第4章 信息理论 57
4.1 概率 57
4.2 完美秘密 58
4.3 熵 60
4.4 自然语言之熵 62
第5章 对称密钥密码系统 66
5.1 DES与Feistel密码 66
5.2 Triple DES挑战DES 73
5.3 AES 75
5.4 IDEA 79
5.5 区块密码加密模式 83
第6章 RSA密码 87
6.1 公开密钥密码系统 87
6.2 RSA算法 89
6.3 RSA的数论背景 92
6.4 RSA数字签名 96
6.5 同时进行RSA加密和RSA数字签名 98
6.6 RSA-129挑战与因数分解 100
6.7 二次筛法Pollard的p－1法 103
6.7.1 二次筛法 104
6.7.2 Pollard的p-1法 107
6.8 利用RSA私钥因数分解 108
6.9 RSA密码系统使用的注意事项 110
6.10 Wiener低幂次d攻击 112
6.11 Rabin密码 115
第7章 非对称密钥密码系统与离散对数 119
7.1 Pohlig-Hellman密码与离散对数 120
7.2 Diffie-Hellman密钥交换 123
7.3 ElGamal密码 126
7.4 Pohlig-Hellman算法 127
7.5 Index Calculus 129
第8章 数字签名 131
8.1 数字签名方案 131
8.2 RSA盲签名 133
8.3 Hash函数简介 135
8.4 生日攻击 136
8.5 ElGamal数字签名 137
8.6 DSA数字签名 140
8.7 Schnorr数字签名 143
8.8 Nyberg-Rueppel数字签名 144
8.9 MD5 Hash函数 147
8.10 SHA-1 Hash函数 150
8.11 信息校验码MAC 152
第9章 质数与大整数算术 154
9.1 大整数的加减乘法 154
9.2 大整数的除法 157
9.3 Montgomery算术 159
9.4 Miller-Rabin质数测试 161
9.5 Agrawal-Kayal-Saxena算法 163
9.6 公开密钥密码的质数 165
9.6.1 强质数 165
9.6.2 DSA质数 166
9.7 Java的BigInteger Class 167
9.8 大整数算术与数论套件及软件 171
第10章 椭圆曲线密码 173
10.1 椭圆曲线 174
10.2 椭圆曲线（mod p） 179
10.3 加权投影坐标 183
10.4 定义在Galois域 的椭圆曲线 185
10.5 密码安全曲线 188
10.6 将信息转化为椭圆曲线代码 189
10.7 椭圆曲线公开密钥密码算法 190
10.8 椭圆曲线因数分解 196
10.9 ECCp-109挑战 199
10.10 并行Pollard Rho法 201
第11章 公开密钥基础建设 204
11.1 认证机构CA 204
11.2 X.509 206
11.3 认证机构CA 207
第12章 量子密码 208
12.1 量子实验 208
12.2 量子密钥分配 210
12.3 浅谈Shor之量子算法 212
参考文献 214