阅读时光

是的，最近在读书。在度过繁忙一学期，又经历了紧张的考试之后，总算有时间看点儿闲书。虽然有小学期的课程压着，但毕竟轻松很多。我是一个酷爱读书的人，尤其是长篇小说，各种各样的小说，沉浸在小说家为你构造的虚拟世界中简直太美妙了。

从初中开始就一直保留着读"闲书"的习惯，一直到大学二年级阅读量才出现明显的下降。促使这一事件发生的主要原因是我总结大学第一年的生活时发现最 主要的成绩居然是读了六十多本小说...所以我打定主意从那以后到图书馆尽量不借闲书。然后就是一堆一堆计算机书往宿舍抱（这类书基本都很厚），虽然没有 几本真正看完的，但在帮助我建立起对计算机科学的整体印象上还是起了很大帮助的。这段时间的闲书阅读基本上集中在杂志上：《科幻世界》、《新周刊》、《萌 芽》、《Newton 科学世界》、《走近科学》、《奥秘》等等。

聊聊最近买的这几本书吧。主题是科幻类：阿西莫夫的基地三部曲：《基地》、《基地与帝国》、《第二基地》，刘慈欣的《三体Ⅱ：黑暗森林》。我很爱看 科幻小说，尤其是儒勒·凡尔纳的小说读过非常多，从妇孺皆知的《海底两万里》、《环游世界八十天》、《神秘岛》、《格兰特船长的儿女》到《沙皇的邮件》、 《气球上的五星期》、《征服者罗比尔》，貌似还有本他儿子假托他出的书，怎么说也得有十几本。里面的"鹦鹉螺号"、"信天翁号"、"地球大炮"等机器形 象，都能让人看过后难以忘记，不敢相信这是一个 19 世纪的作家写的书。

我是从高中开始看《科幻世界》杂志的，我自己的感觉像是一步一步地看着中国科幻从落后走向繁荣。王晋康、刘慈欣（大刘）、何宏伟（何夕）、韩松、郭 威（星河）、柳文扬（07年因脑瘤去世），赵磊（七月，现在南大生科的研究生哦，就是小百合上的 SoulKnight），看着这些世纪之交崛起的科幻小说家的名头越来越响亮真是件让人开心的事情。这些作家的科幻小说中不再是完全对西方科幻的照搬和模 仿，融入了许多中国元素，看到时倍感亲切。我想《科幻世界》的主编的感触应该比我更深刻，所以他在《中国科幻基石丛书》的前言中写道：

仍然有人经常问及中国科幻与美国科幻的差距，但现在的答案已与十年前不同。在很多作品上，这种比较已经变成人家的牛排之于我们的土豆牛肉。差距是明显的——更准确地说，应该是"差别"——却已经无法再为它们排个名次。

刘慈欣的《三体》和《三体Ⅱ》，也被编入《中国科幻基石丛书》系列中。读这本《三体Ⅱ：黑暗森林》时，我仿佛又回到了当初在《科幻世界》上看到《三 体》连载时的感觉，都已经连载好几期了，作者的意图仍然难以摸透，下一期的内容总是自己预想的有万里之别。从科幻小说必须有的想象力方面来看，这两本书绝 对是值得一读的，但这次真正打动我的，并不是想象力，而是其中的一段心理描写：主人公罗辑创造自己梦中女孩的心理活动。看到这一段我就想，我应该在豆瓣上 给它五星！

阿西莫夫的《基地系列》是被称为科幻史诗的作品，《基地三部曲》则是这个系列中最关键的三册。对它的介绍我就不再赘述，豆瓣上能找到很多。我想说的 是，这本书对我来说，并没有太大的震撼（也许我不该读前言，或者对它的期望太高了），但并不是说我不认为它是一套好看的科幻小说，所以我在豆瓣上仍然给它 五星。

我在上一篇日志中就提到了《一个数学家的辩白》，这是哈代写的一本小书，C.P. 斯诺给它写的前言几乎和内容差不多长。虽然翻译有些晦涩，还是能大致领略到作者的意思。站在我们这个时代的视角上看这篇六十多年前的文章，发现他的很多论据都无法成立（我在《当数学遇上计算机：数论与密码学》说的就是一个例子），所以再去审视他的论证和思想，在某些地方就会觉得有些固执可笑。但是从中可以看到一个追求纯粹真理的人对数学的偏爱与维护，就像每个人在做一些事前总要给自己些理由或者信念，拥有这些才不至于在孤独的前行中感觉到灰心寂寞。

我原以为《丑陋的中国人》是一本书（这里书的意思是一个整体），后来才发现它原来是本杂文集。柏杨先生去世的时候，自己曾因为没有看过他对国民性的 批判文章感到很惶恐，所以特地买来准备拜读一番。如果让一个"一方面，另一方面"的人来看，柏杨先生的批判的确并不是像推理逻辑那样完美地无懈可击。幸好 我不是那样的人，从某种意义上来讲，一个人如果老是说"一方面，另一方面"，自然永立于不败之地，因而从信息论的角度来看，我们可以认为他说的话信息量为 零。起沉疴还需下猛药，对于麻木的人来说真的需要警示之钟在头顶轰鸣！

当数学遇上计算机：数论和公钥密码学

作者：杨文博 < http://blog.solrex.cn >
地址：http://blog.solrex.cn/articles/number-theory-and-public-key-cryptography.html

1940年，英国数学家哈代在他的一本小书《一个数学家的辩白》(A Mathematician's Apology)中说："如果有用的知识是这样的知识（我们暂时同意这样说）：它大概会在现在或相对不远的未来，为人类在物质上的享受方面作出贡献，因而，它是否在单纯的智力上满足人们乃是无关紧要的，那么，大量更高级的数学就是无用的。现代几何和代数、数论、集合论和函数论、相对论、量子力学——没有一种比其它的更经得住这种检验，也没有真正的数学家的生涯可以在这个基础上被证明是有价值的。"但是我们会看到，哈代这个断定在当时"不远的未来"几乎被一一证明是错误的，数论就是其中一个。

在 1970 年代以前，人们所知道的密码学都是对称密码学，就是在加密和解密过程中需要使用同一个密钥。在那个时代，一些密码算法已经能保证足够的安全性，比如数据加 密标准 DES。但是人类的需求是很难完全得到满足的，他们为每次密钥交换的复杂度而苦恼，比如在战时如果密码本被敌方获得，就必须重新向无线电收发员分发密码 本，这个工作量和代价是相当大的；还有一个需求就是数字签名，能不能用加密实现对数字文件的签名，像手写的签名一样，确保该文件出自谁人之手？

上述问题，就是 Whitfield Diffie 和 Martin Hellman 1976 年在他们那篇划时代的论文《密码学的新方向》(New Directions in Cryptography)中提出的，他们也给出了其中一个问题的解决办法，那就是 Deffie-Hellman 密钥交换算法（后来被改为 Deffie-Hellman-Merkle 密钥交换算法，里面还有一段小故事。）。但是 DH 没做完的功课，仅仅在一年后就被 RSA 解决了，那就是 Ron Rivest, Adi Shamir, 和 Leonard Adleman 的 "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"。RSA 的加密和解密使用的是不同的密钥，即公钥和私钥，你可以将你的公钥扔到世界上任何一个位置，我用你的公钥加密一段信息，除了你用自己的私钥解密，没有别的 人能从中得到原始消息。就相当于你把打开了的箱子扔的满世界都是，但箱子一旦锁上，就只有你能再打开。

RSA 算法自其诞生之日起就成为被广泛接受且被实现的通用公钥算法，但是 RSA 算法还带来一个另外的意义，那就是：数论知识从未像现在这样被广泛地使用着。RSA 程序的普及率要远远大于 Windows，因为每台 Windows 上都装配着 RSA 算法程序，但 RSA 并不仅仅装配 Windows。每当你登录邮箱、网上银行、聊天软件、安全终端，你都在使用着数论带来的好处。而且相比之前密码学的字母替换和置换，混淆和扩散，DH 和 RSA 使用的东西更有资格说自己是数学。

大概也是由于其基于数学的简洁性，RSA 和 DH 算法描述要比 DES, AES 简练许多，我在这篇小文中都能写完。

RSA

RSA 用到了数论中的三个基本定理：费马小定理、欧拉定理和中国剩余定理（几乎处处都在），和一个古典难题：大整数分解问题。如果你是数学系的学生，对这些概念一定不会陌生。

费马小定理：若 p 是素数，a 是正整数且不能被 p 整除，则： a^p-1 = 1(mod p)。或者另一种形式：a^p=a(mod p)，这种形式不要求 a 与 p 互素。

欧拉定理：对任意互素的 a 和 n，有 a^Φ(n) = 1(mod n)。其中，Φ(n)是欧拉函数，即小于 n 且与 n 互素的正整数的个数。

大整数分解问题：将两个整数乘起来是简单的，但是将一个整数分解为几个整数的乘积是困难的，尤其是当这个数比较大的时候。迄今为止没有有效的算法来解决这个问题，甚至我们连这个问题的计算复杂度量级是多少都不知道。

那么 RSA 算法是什么样的呢？

密钥的产生：
1. 选择两个素数 p 和 q.
2. 计算 n = p*q.
3. 计算 Φ(n) = (p-1)(q-1) （这是欧拉函数的性质）
4. 选择 e<Φ(n) 并使得其与 Φ(n) 互素。
5. 确定 d<Φ(n) 并使得 d*e = 1(mod Φ(n))。
6. 这时候，私钥就是{d, n}，公钥就是{e, n}。
加密算法：
假设 M 是明文（M<n），那么密文就是 C = M^emod n。（为什么明文是数字？在计算机科学里任何数据最终表示都是数字。）
解密算法：
假设 C 是密文，那么明文就是 M = C^d mod n。

我们来证明一下算法是否正确，由于 C^d = M^e*d = M^k*Φ(n)+1 (mod n)。

如果 M 和 n 是互素的，显然直接由欧拉定理我们就能得到：
C^d = M^k*Φ(n)*M¹ = M (mod n) = M
说明算法是正确的；
如果 M 和 n 不互素，由于 n 是两个素数 p 和 q 的乘积且 M<n，那么 M 要么是 p 的倍数，要么是 q 的倍数，由 e*d = 1(mod Φ(n)) = 1(mod (p-1)(q-1)) 我们可得：
e*d = 1(mod (p-1)) 且 e*d = 1(mod (q-1))
则 e*d 可以写成： e*d = k*(p-1)+1, e*d = h*(p-1)+1
由费马小定理，我们有：M^e*d = M^k*(p-1)+1 = M(mod p) 和 M^e*d = M^h*(q-1)+1 = M(mod q)。
由于 p 和 q 均为素数，且 p, q 均整除 M^e*d-M，所以我们有：
C^d = M^e*d = M (mod p*q) = M (mod n) = M

从上面我们可以看到 RSA 算法实现了加密和解密使用不同密钥，而且证明了这个算法的正确性。但 RSA 算法要想实用，光有正确性还不够，最重要的一点是安全性，即从公钥{e, n}无法推导出私钥{d, n}。在 RSA 算法中我们可以看到，关键要知道 Φ(n)，知道了 Φ(n)，使用欧几里德算法就能求出 e 的逆元，就得到了用户的私钥{d, n}。要求出 Φ(n)，就必须知道 p,q，但 p,q 是不公开的，仅仅知道 p,q 的乘积 n 去求 p,q，根据大整数分解古典难题，当 n 比较大时其分解在计算上是不可行的。这就保证了 RSA 算法的安全性。

而且 RSA 算法是可逆的，所以它就有能力同时实现加密和签名的功能。由于公钥是公开的，每个人都可以用你的公钥加密一段信息发给我，而私钥是保密的，所以只有你能看 到别人用你的公钥加密的消息；而也因为可逆性，如果你用私钥解密一段明文（实际是加密），所有人都可以用你的公钥加密它来得到明文（实际是解密），因为私 钥只有你一个人知道，这个消息只有可能是你发出的，就相当于你对这段明文做了一个签名。

DH 密钥交换算法

DH 密钥交换算法较 RSA 算法更为简单，它也是基于数论中的一个古典难题：离散对数问题。

离散对数问题：若 p 是素数，p 已知，考虑方程 y = g^x mod p，给定 g,x 求 y 是简单的，但给定 y,g 求 x，即求 x = log_g,py mod p，在计算上是不可行的。

DH 密钥交换算法的描述如下：
已知公开的素数 p 和 p 的本原根 α
1. 用户 A 选择秘密的 Xa<p，计算 Ya = α^Xa mod p，将其发送给 B。
2. 用户 B 选择秘密的 Xb<p，计算 Yb = α^Xb mod p，将其发送给 A。
3. A 和 B 分别计算 Ka = (Yb)^Xa mod p 和 Kb = (Ya)^Xb mod p，就同时得到了共享的密钥 K=Ka=Kb，然后就可以用 K 进行加密传输了。

DH 密钥交换算法的优点在于：双方在通信前不需要知道任何共享的密钥，而是通过公开的 p 和 α 协商出一个密钥来进行加密通信。

先看一下算法的正确性，Ka = Kb 是否成立：
Ka = (Yb)^Xa = (α^Xb)^Xa = α^Xa*Xb (mod p)
Kb = (Ya)^Xb = (α^Xa)^Xb = α^Xa*Xb (mod p)
Bingo! Ka 和 Kb 是相同的。

再来看一下算法的安全性，就是能否从公开的信息推导出 K 来：
由于密钥是 K = α^Xa*Xb，那么攻击者必须知道 Xa 和 Xb 才能得到共享的密钥 K，而公开的信息只有 Ya 和 Yb，由离散对数问题，从 Ya,Yb 求出 Xa,Xb 在计算上是不可行的，就保证了算法的安全性。

从上面两个算法我们可以看出，数论在公钥密码学中的重要地位，恐怕哈代当时怎么也想不到三十多年后人人都在使用他所认为在实际生活中毫无用处的数论吧！