密码学历史悠久，它的重要性在二战中显露无遗，受到一般人关注。进入电脑化的资讯时代
讯息传递更需要加密。今天网上银行服务，自动取款机运作，
以至所有的电子商务信息都无一不经过加密处理。如果你家里有个无线网络路由器（Router，或称宽频分享器），从路由器输出的Wi - Fi
(无线电脑网路) 讯息通常也会经过加密处理。
我不打算详细去谈现今加密法的分类，我只想谈 “重新排列加密法”和“数学运算加密法”两种。前者可以用 Advanced Encryption Standard (AES)为代表，後者的典型是RSA 加密法。
重新排列加密法
重新排列加密法
这是把要加密的讯息在电脑里重新排列。任何的讯息在电脑里最终还是以二进制的方式储存。
比方现在有 11000110 10100110 那样的两组数据。 你可用以下的办法加密：
(1) 每一组里面第1和第5对换， 第3和第2对换， 第7和第8对换， 别的不动：
00101101 01001101
(2) 每一组里往右移2个位置，第1移到第3， 第2移到第4，第7移到第1，第8移到第2。
(1) 的结果 00101101 经过右移2后就变成 01001011
(3) 进行所谓“异或”运算 (XOR)。 这是"异或"的真值表：
Input A Input B Output of XOR
0 0 0
0 1 1
1 0 1
1 1 0
比如说我们已经有了一个预先固定的 Input A 11010111 (下面谈到的钥就可以充当这角色)。
现在把 (2) 的结果 01001011 当作 Input B 01001011
XOR 的结果就是 XOR 10011100
这个XOR结果 10011100 就用来取代原先的 01001011 来加密。请留意如果你知道XOR 和 Input A， 你可以还原 Input B 。
通常像这几种加密都要做很多次才可以输出。这些加密都是可逆的，只要你记得做过什么你就可以一步步的把它还原。因此收件的那一方得知你加密的步骤就可以解密了。以上都是简化了的例子，美国的 Da
数学运算加密法
另
一种加密法是直接把要加密的数据化成十进制的整数，然后进行数学运算来加密。 如果你要加密的是一个英文文件，你可以对每一个字母去加密，
也可以把整个句子甚至更多的篇章化成一个十进制的整数来加密，那当然是一个相当大的数目， 不过现今的电脑和软件应用
Arbitrary-precision arithmetic 会允许我们对这种大数目来进行运算。最简单的数学运算加密法是用可逆函数来加密。
比如说你把数据 x 用函数 F 加密变成 F(x)，收件人就用 F 的逆函数把 F(x) 还原到
x。剩下来的问题就是怎样去找一个不容易被人破解的函数 F，和怎样去使收件人得到(或创造出) F 的逆函而不为人知。数学运算加密法的代表是 RSA
加密法。
加密用的“钥”
就算你设计出一种复杂的加密法，用久以后难免会被人侦破，所以人们开始要求每次通讯加密法都要更换，这样做立刻产生了一个新命题：你怎样令你的收件人知道你这次是怎样去加密呢？ 这里的解决办法是用“钥” (用繁体字的朋友: 这就是"鑰")。
这里我们先谈重新排列加密法的钥。 现在假设你的软件随机地搞出 01110101 这把钥来 (这样短的钥只可以作例子，实际上用的钥起码有128 bits)。
作为重新排列加密法的简化例子你的软件可以把前三位数目 011 拿出来化为十进，那就是3，然后再拿第四位来作左右位移的指标(0左1右)。现在第四位是1， 那我们就向右移3位。 请参考(2)。
你的软件也可以把 01110101 这个钥当作 XOR 的 Input A 来对你要加密的数据进行运算。请参考(3)。
上面我提到重新排列加密法要对原来数据做很多次才可以输出，这是用钥来驱动的。比如你已经写了一个按一个钥来加密的程序A，现在要你按不同的钥同样做五遍，那你只需在一个 loop 里面把这钥重新排列五次，每次都调用程序A来再加密。当然，这个将钥重新排列五次的方法是要告诉给对方的，这可以是预定，比如把原来的钥分开五段再加上一些东西，更高明的办法是根据原来钥某一段的排列来决定怎样去把钥重新排列若干次。
加密钥還分成兩种：对称钥和非对称钥。对称钥可以用来加密和解密，也就是说通讯的两方都用同一条钥匙。如果这个对称钥是通讯的A方搞出来的(或者是A方的软件搞出来的)，怎样把它交到通讯的B方是一个重要的命题，我们会在後面的章节详细去谈。
上面我提到重新排列加密法要对原来数据做很多次才可以输出，这是用钥来驱动的。比如你已经写了一个按一个钥来加密的程序A，现在要你按不同的钥同样做五遍，那你只需在一个 loop 里面把这钥重新排列五次，每次都调用程序A来再加密。当然，这个将钥重新排列五次的方法是要告诉给对方的，这可以是预定，比如把原来的钥分开五段再加上一些东西，更高明的办法是根据原来钥某一段的排列来决定怎样去把钥重新排列若干次。
加密钥還分成兩种：对称钥和非对称钥。对称钥可以用来加密和解密，也就是说通讯的两方都用同一条钥匙。如果这个对称钥是通讯的A方搞出来的(或者是A方的软件搞出来的)，怎样把它交到通讯的B方是一个重要的命题，我们会在後面的章节详细去谈。
另一种钥就是非对称钥， 也就是公钥/私钥加密法。公钥用来加密而私钥用来解密。通讯的每一方都有自己的私钥，这私钥是保密的， 只留给自己作解密之用。而公钥是交给其他人发信给这一方时加密之用，把公钥交给对方时通常不加密，换言之给黑客拿到公钥也无所谓。
假如 A 君要发信给B，A先要得到 B 的公钥，这公钥是相对于B 的私钥而言的。A 得到公钥后就可以用它把要发的讯息加密，然后送去给 B。B 接到 A 加密的讯息后就用准备好的私钥解密。 如果黑客截获公钥对他来讲是没多大用处的，因为那不能用来解密。当然黑客可以冒用A 的身份给 B 发出加密的假信，这方面就涉及身份验证，对身份验证有兴趣的朋友可以查看 Digital Signature 和 Digital Certificate 有关的资料，不过最好是等到读完RSA加密法之后。
至于这两条钥是由谁造出来的要看具体情况而定。如果 A 要和 B 通讯，B 的公钥和私钥可能是 B 接到 A 要通讯的意愿后由 B 的通讯软件即时所产生的，然后经通常途径把 B 的公钥交给 A 作加密之用。你可以看出来用公钥加密私钥解密的办法不必担心怎样把钥交到对方。
有人就把公私钥办法应用来将对称钥交到对方去。我就用 https 作为例子吧。当你用浏览器上网到你的银行处理账目时，你会看到银行互联网地址是以 https 开头而不是 http。
这表示通讯是加密的。首先银行的网站会给你那一方发一条公钥，然后https 所调用的软件就会在你方随机地搞出一个新的钥，再用所收到的公钥把这个新钥加密送到银行的网站，
银行的一方就可以用它的私钥来解密得到这个新钥，那通讯双方就可以用这个新钥(对称钥)加密和解密了。如果你再输入你的ID和密码，这些数据都会经过加密後才送出。
以上这个例子是一次性的用公私钥办法把对称钥递交过去。为什么不直接用公私钥通讯呢？
一般来讲那会慢得多。我还得指出这里是把 https 所用的加密法简化了来介绍公私钥的一个应用。当银行网站给你方发公钥的时候，它还会发出它的“数字证书”去证明那的确是这银行的网站，这也涉及身份验证。
这里我好像把公钥私钥的应用说得头头是道，但如果你要我举一个具体的例子，我只好说那要等到我们谈 El-Gamal 或 RSA 加密法才行。监于博客的篇幅限制，我只能在另一个篇章去谈。
我们已经谈过一种把对称钥交到对方的方法。第二种是和数学有关的 Diffie
Hellman 对称钥交递法。
陶哲轩有趣的比喻
A 君想把一封信托邮差C交给B君。
为了保密, A 把这封信放在一个小盒子，加上锁，才交给邮差C。
B 君从邮差手里接过小盒子后，他没有A 的钥，打不开。怎办呢？他索性加多一个锁，请邮差C拿回去给A君。
当C把这个有两个锁的盒子交给A 时，A 打开了他自己的锁，再叫C拿这盒子回去给B。
B 君从邮差手里再接过小盒子时只剩下他自己的那个锁，他可以用自己的钥开这盒子了。
请注意邮差C自始到终都没机会偷看这封信。
这是很有趣的比喻。我想请读者留意这件事：在 B 加上他的锁后，A 还能先打开他自己原先加上的锁。这对小盒子和真锁钥是显然的，但对对数学加密法就有很大的启发性。
如果加锁等于加密，对数学运算加密法而言就等于把原来的讯息用一个函数F变为加密后的讯息F(x)， 那A君
和 B君
所用的函数必须具有“可换”这一特性。
如果说原来的讯息是x，A 上 F 这把锁后就变为 F(x)。
B 再加另一把锁 G 就变为
G(F(x))。
如果 G(F(x)) = F(G(x))，
也就是说F和G在复合函数的意义下可换，那样 A 就可以用 F 的逆函数开锁，A开锁后剩下的是G(x)， 当然B 可以用 G 的逆函数开锁还原 x 了。当然这两个函数的可换性只是其中一个要求，这些函数取值的范围要大，取值形态要不规则，这样构成的加密法才不容易被人侦破。此外，这些函数还要有逆函数来解密。 这种加密法的一个特例是 G(F(x)) = F(G(x)) = x , 这样的话 G 就是 F的逆函数， F也是G的逆函数。 后来的 RSA 加密法基本上是遵循这个思路。
两个有逆函数的可换函数可以用来加密，而没有逆函数的可换函数却可以用在加密钥的交递, 具体步骤是这样的：
发件一方 (A君) 确定一个函数F， 收件一方(B君) 确定一函数G。
F 和 G都是把整数投射到整数的函数， 而且它们是在复合函数的意义下可换的。
A 挑一个常数 r， 然后用自己的函数算出 F(r)， 再把 r 和 F(r) 交给 B。
B 收到 A 的数据以后就用自己的函数 G 算出G(r) 再把它交给 A。 然后再用函数G算出 G(F(r))，最后这个数字就是B君要用的钥了。
A 收到 B 的发过来的 G(r) 以后就用自己的函数F 算出F(G(r))。 那就是A君要用的钥了。
因为 F 和 G是可换的， 那 B 的钥 G(F(r)) 就等于 A 的钥 F(G(r))。到此这个钥交递过程就完成了。
其实说钥交递是不对的， A 和 B 事先都不知道这钥是什么。他们一来一往的几次交流中把一些资料交换去各自去打造一条钥匙。而这些网络上传送未加密的资料就算被截获也不足以让别人制造出同一条钥 。一旦收发双方的钥都打造成功，以后的传送就可以加密了。根据以上的讨论我们没必要对这条钥里的内容有什么要求，只希望这个方法打造出来的钥取值范围大， 那就不容易被人抓到痛脚了。
如果黑客截获未加密的 r 和 F(r)的两个数字时 (那是A交与 B的)， 他能否猜到 F是那一个函数呢？要知道现在流行的加密函数都是有固定型式的，只是参数不同而已，所以这是一个现实问题。一个方案的成败就在於从 r 和 F(r)找出 F 的难度。
所以说 F(x) = a + x,
G(x)=b + x; F(x) = ax, G(x)= bx; F(x) = x^a, G(x) = x^b 等等都不行的，太容易被破解。这里a 和 b 都是一个整数，所有以下提到的常数都是整数。
在进一步讨论以前我先介绍一些符号：a ^b 是 a 的 b 次方，比如 3^2 = 9， 2^3 = 8。 mod(a,b) 是a 除以b后的余数 。 比如 mod(10，5) = 0， mod(11，4) = 3 。 ***** 注1
F( x ) =
mod( x^a, p)
G( x )
= mod( x^b, p)
这里 p, a 和 b 是三个常数(整数)，
而 p 是质数 (也叫素数)。
这样的函数是够复杂了，对整数x 而言我们可以证明
G(F(x ))= F(G(x ))。
这个交递的具体做法是由A君找来质数p,
和 a , r 两个整数，
算出 F( r ) = mod( r^a, p) ， 然后把 p, r, 和 F(r) = mod( r^a, p) 送交给B。
B君收到後自己找一个整数 b, 算出 G(r) = mod( r^b, p) 後再将之送交给A。自己再算出 G(F(r))
= mod(F(r)^b,p) = mod(mod(r^a,p)^b,p) 那就是B自己的钥了。
A君收到B 送来的G(r)以后也就可以算出 F(G(r)) = mod(G(r)^a,p) = mod(mod(r^b,p)^a,p), 那就是A自己的钥了。
请留意A是把未加密的 p, r, 和
F(r) = mod( r^a, p) 送交给B。如果黑客得到这几个数後他能否把 a 找出来呢？不要忘记 Diffie
Hellman 的钥交递法已经规定了函数F的形式，他所不知道的只是 a 的数值而已。
我要指出 r 是 p 的原根不是Diffie Hellman 的钥交递法必需具備的，只不過那是最佳的选择。在实际应用上因为大的质数的原根不是那样容易找，r 的选取只是去保证 mod(r, p), mod(r^2, p), ... mod(r^(p-1), p) 取值的范围够大而已。
实际上用的质数p是很大的，这里为了让读者验证，我们用小数值的 p 为例：
( 下面 c = mod(r^a,p), d = mod(r^b,p) )
最后的两个纵行(columns) 就是B君的钥 和 A君的钥。
实际用的质数 p 又有多大呢？
我想借用William Stein 在 Elementary Number Theory 一书中的列子：
( 下面 c = mod(r^a,p), d = mod(r^b,p) )
| p | r | a | b | r^a | c | r^b | d | mod(c^b,p) | mod(d^a,p) | |
| 13 | 5 | 3 | 2 | 125 | 8 | 25 | 12 | 12 | 12 | |
| 11 | 7 | 2 | 6 | 49 | 5 | 117649 | 4 | 5 | 5 | |
| 17 | 5 | 6 | 7 | 15625 | 2 | 78125 | 10 | 9 | 9 | |
| 19 | 3 | 4 | 7 | 81 | 5 | 2187 | 2 | 16 | 16 | |
| 13 | 7 | 3 | 7 | 343 | 5 | 823543 | 6 | 8 | 8 | |
| 17 | 3 | 5 | 7 | 243 | 5 | 2187 | 11 | 10 | 10 |
最后的两个纵行(columns) 就是B君的钥 和 A君的钥。
p = 93450983094850938450983409611
r = -2
a = 18319922375531859171613379181
b = 82335836243866695680141440300
c = mod(r^a,p) = 45416776270485369791375944998
d = mod(r^b,p) = 15048074151770884271824225393
A 和 B的钥都等于 mod(mod(r^b, p)^a,p) = 85771409470770521212346739540
为什么r 会是负数呢？事实上在这里 -2 和 p - 2 是一样的 ( -2 和 p - 2 同余: mod(-2,p) = mod(p -2, p) ).
同样这里 r^a 也可以是负数，但 mod(r^a,p)是应该取 0 到 p - 1 之间与 r^a 同余那个数为代表。
当p 是这样大的时候，黑客只截获 p, r, c, d 又怎样能猜到钥 = 85771409470770521212346739540 ？
严格说来 Diffie Hellman 对称钥交递法并不是一个加密法，而是令通讯两方安全地共同创造出同一个加密钥的方法。至于有了同一个加密钥后怎样去加密就有很多既有的方法可以挑了。比方说你可以把要加密的数据与加密钥进行异或(XOR)运算，把结果传送到对方，收件的一方把加密后的数据再与加密钥多作一次异或运算，那就能还原到原来的数据了。上面是假设你已经把数据分成与加密钥同样的长度。
如果原来的数据是 M，加密钥是 K， 那么 (M XOR K) XOR K = M
比如 M = 11010111， K = 01001011，
(11010111 XOR 01001011) XOR 01001011 = 10011100 XOR 01001011 = 11010111
这不算是一个安全的办法，因为用同一个钥作那么多次的异或运算会容易给人破解的。如果你在通讯过程中不停更换你的加密钥那就不同。
和 Diffie Hellman 对称钥交递法只差一步之遥的公私钥加密法是 El-Gamal 加密法。我们会在以后的章节谈到。
我们剩下的工作是证明 mod(mod(r ^ b, p) ^ a,p) = mod(mod(r ^ a, p) ^ b,p).
上面提到r 的挑选最好是p的原根，这里我们举一个例子。现在挑 p = 23，当 r 分别等于 2， 3，5， 6，7，8 时看mod(r^n,p) 取值的范围如何？
如 果mod(r^n,p)来来回回都是取那几个数，那个钥就容易被破。最好的 r 会使
mod(r,p), mod(r^2,p), ... mod(r^(p-1),p) 走遍了1， 2，3，.... p -1 这些数值。这样的r 叫 p 的原根。从下面的表我们可以看到 r = 7 就是 23 的原根。如果你挑r = 2 的话2，4，8，16，9 等的数字都出现两次，mod(2^n,p)
取值的范围只有 mod(7^n,p) 的一半。所以p = 23 的话挑 r = 7 最好。
p =
23
| r |
2
|
3
|
5
|
6
|
7
|
8
|
| mod(r, p) |
2
|
3
|
5
|
6
|
7
|
8
|
| mod(r^2, p) |
4
|
9
|
2
|
13
|
3
|
18
|
| mod(r^3, p) |
8
|
4
|
10
|
9
|
21
|
6
|
| mod(r^4, p) |
16
|
12
|
4
|
8
|
9
|
2
|
| mod(r^5, p) |
9
|
13
|
20
|
2
|
17
|
16
|
| mod(r^6, p) |
18
|
16
|
8
|
12
|
4
|
13
|
| mod(r^7, p) |
13
|
2
|
17
|
3
|
5
|
12
|
| mod(r^8, p) |
3
|
6
|
16
|
18
|
12
|
4
|
| mod(r^9, p) |
6
|
18
|
11
|
16
|
15
|
9
|
| mod(r^10, p) |
12
|
8
|
9
|
4
|
13
|
3
|
| mod(r^11, p) |
1
|
1
|
22
|
1
|
22
|
1
|
| mod(r^12, p) |
2
|
3
|
18
|
6
|
16
|
8
|
| mod(r^13, p) |
4
|
9
|
21
|
13
|
20
|
18
|
| mod(r^14, p) |
8
|
4
|
13
|
9
|
2
|
6
|
| mod(r^15, p) |
16
|
12
|
19
|
8
|
14
|
2
|
| mod(r^16, p) |
9
|
13
|
3
|
2
|
6
|
16
|
| mod(r^17, p) |
18
|
16
|
15
|
12
|
19
|
13
|
| mod(r^18, p) |
13
|
2
|
6
|
3
|
18
|
12
|
| mod(r^19, p) |
3
|
6
|
7
|
18
|
11
|
4
|
| mod(r^20, p) |
6
|
18
|
12
|
16
|
8
|
9
|
| mod(r^21, p) |
12
|
8
|
14
|
4
|
10
|
3
|
| mod(r^22, p) |
1
|
1
|
1
|
1
|
1
|
1
|
严格说来 Diffie Hellman 对称钥交递法并不是一个加密法，而是令通讯两方安全地共同创造出同一个加密钥的方法。至于有了同一个加密钥后怎样去加密就有很多既有的方法可以挑了。比方说你可以把要加密的数据与加密钥进行异或(XOR)运算，把结果传送到对方，收件的一方把加密后的数据再与加密钥多作一次异或运算，那就能还原到原来的数据了。上面是假设你已经把数据分成与加密钥同样的长度。
如果原来的数据是 M，加密钥是 K， 那么 (M XOR K) XOR K = M
比如 M = 11010111， K = 01001011，
(11010111 XOR 01001011) XOR 01001011 = 10011100 XOR 01001011 = 11010111
这不算是一个安全的办法，因为用同一个钥作那么多次的异或运算会容易给人破解的。如果你在通讯过程中不停更换你的加密钥那就不同。
和 Diffie Hellman 对称钥交递法只差一步之遥的公私钥加密法是 El-Gamal 加密法。我们会在以后的章节谈到。
我们剩下的工作是证明 mod(mod(r ^ b, p) ^ a,p) = mod(mod(r ^ a, p) ^ b,p).
对整数 x，y， p 我们先证明这个引理： mod(mod(x,p) ^ y, p) = mod(x ^ y, p) ....(a)
首先我们证明 mod(mod(x,p) mod(y,p), p) = mod(xy, p) ..... (b)
让 m = mod(x,p)， n = mod(y, p)
我们会有整数 k, s 使 x = kp + m, y = sp + n
那么 xy = (kp + m) (sp + n) = mn + p 乘一个整数
所以 mod(xy,p) = mod(mn,p) = mod(mod(x,p) mod(y,p), p) (b)证毕
从(b)得到 mod(x^2, p) = mod(mod(x,p)^2, p)
应用归纳法不难证明 mod(x^y,p) = mod(mod(x,p) ^ y, p)
好，现在我们可以证明 mod(mod(r ^ b, p) ^ a, p) = mod(mod(r ^ a, p) ^ b, p)：
根据 ( a ) mod(mod(r ^ b, p) ^ a, p) = mod((r ^ b)^a, p) = mod(r ^ (ba), p) = mod(r ^ (ab), p)
= mod((r ^ a) ^ b, p) = mod(mod(r ^ a, p) ^ b, p) QED.
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * *
注1： 除了电脑软件以外现在很少用 mod(x,p) 这种表示法了，现在大部分是用 ≡ 这个符号的。
这两种表示法各有好处，≡
这个符号是用来表示两个数目同余的关系，而 mod(x,p) 就直指 x 除以 p 的余数。
初学者可以把mod当作一个“算子”(operator)，虽然麻烦一点，但不容易错。而且mod這個符號在很多電腦軟件都代表同余函數，用來驗證很方
便。你用≡这个符号说这个和那个同余，那个也和别一个同余，有時中間推理的步驟都省略了，所以初学者照样来推理容易会弄错。不过，当你掌握同余的基本运算
后用≡那个符号也有它的好处，论证会简约得多。 