科普也需严谨---对《数学之美》密码部分的评论
《数学之美》是一本备受推崇的书，今天在搭乘高铁回广州的时候翻看了一下。我觉得这本书的名字改为《数学应用之美》甚至《信息论应用之美》更为合适。对于希望体验数学之美的同学，我推荐 S. Lang 的 《做数学之美妙》，见 http://book.douban.com/subject/1327048/ 。
这本书开始看时感觉挺好的，扼要地介绍了中文分词，自然语言处理的一些基本想法，以及自然语言发展史上的一些传闻。我对上述领域完全陌生，读完后感觉获益良多。当我读到章节“谈谈密码学的数学原理”时，因为对这部分内容比较熟悉，本想直接跳过去的，但不小心看到章末的话：
"不管怎么样,我们今天用的所谓最可靠的加密方法的数学原理其实就这么简单,一点也不神秘,无非是找几个大素数做一些乘除和乘方运算就可以了。"
这句话太扯了，所以我又翻回去，决定把这章仔细看一遍。一看之下，发觉这章充满了 Bug, 作者显然对密码这个领域了解得不够。下面列出本章的一些软伤和硬伤。
1. 作者把公钥密码等同于 RSA 了，虽然他几乎没有提到 RSA 这个术语。这显然不符合事实。公钥密码体制是一个大类，常见的公钥密码体制有 RSA, EIgamal, 椭圆曲线，Rabbin 等。作者讲的其实只是 RSA, 难怪他会觉得“找几个大素数做一些乘除和乘方运算就可以了” 。事实上椭圆曲线公钥体制很常见，其背后的数学知识可深得很。
2. 作者说："我们今天用的所谓最可靠的加密方法的数学原理其实就这么简单"。
看了这句话，读者会认为 RSA 就是当前最可靠的加密方法了。这句话错得离谱，我并不是说 RSA 不安全，而是说我们无法作出这种比较。目前实践中使用的密码算法大致分为三类：a. 公钥密码; b. 分组密码，典型的如 DES, AES; c. 流密码，典型的如 RC4, HC-128, Rabbit 等。后两类又常合并归入对称密码体制。这三类密码分别用于不同场合。与对称加密算法比较，公钥密码的加解密速度慢很多，所以在处理大量数据时，应使用前者。在使用对称密码进行通信时，通信双方要约定一个 session key, 即会话密钥，这个密钥通常是用公钥密码体制来保护的。公钥密码和对称密码是协同工作而不是相互排斥的，所以并不能说 RSA 是最安全的加密算法。
3. 作者说：“要破公开密钥的加密方式,至今的研究结果表明最好的办法还是对大字 N 进行因数分解,即通过 N 反过来找到 P 和 Q,这样密码就被破了。”
如前文所述，作者这里的公开密钥加密方式指的是 RSA。通过分解 N 来破解 RSA, 当然很彻底，但由于技术上的困难，直接分解很难成功。作者这样写，会给读者一种错觉，即对 RSA 的攻击首选是分解，但事实并非如此。RSA 在使用上有很多讲究，稍不小心就会中招，很多攻击是针对使用不当展开的。关于这方面，有一篇综述“Twenty Years of Attacks on the RSA Cryptosystem”， 很容易查到。
4. 作者说：“对大字 N 进行因数分解,即通过 N 反过来找到 P 和 Q,这样密码就被破了。而找 P 和 Q 目前只有用计算机把所有的数字试一遍这种笨办法。”
因子分解是计算数论上的永恒主题之一，很多数学家对此作出了贡献。虽然困难重重，但情况远没有作者所讲的那么糟。目前最有效的分解方法是 GNFS, 即一般数域筛法。关于因子分解的历史，可以参考这本书：《计算代数数论》, 见 http://book.douban.com/subject/1165572/ 。
5. 作者说：“RSA-158 密码是这样因数分解的......”
RSA-*** 被称为 RSA (挑战)数。RSA 为演示其公钥体制的安全性，给出了一系列的大整数，悬赏求分解。右面的链接给出了全部 RSA 数的列表，仔细看一下，就会发现并没有一个叫做 RSA-158 的。其实这个 158 位 10 进制数的分解跟 RSA 数没有任何关系。这个分解纪录是 2002 年创造的，起源于对 2^953+1 的分解，当时已经有部分素因子被找到了，剩下一个 158 位的合数因子。这个纪录就是分解了这个合数因子，从而最终宣告 2^953+1 的彻底分解，详情见 http://www.crypto-world.com/announcements/c158.txt 。从该文档的内容看，对这个合数因子的分解使用的是数域筛法，而不是作者所说的“用计算机把所有的数字试一遍”。
6. 作者说：“好了,现在没有密钥 D,神仙也无法从 Y 中恢复 X。如果知道 D,根据费尔马小定理,则只要按下面的公式就可以轻而易举地从 Y 中得到 X。”
如果非要绕一个大圈子，用费马小定理来证，当然也可以做到。不过从书中所写的公式，我认为这里使用了欧拉定理而不是费马小定理。
7. 作者说："让我们回到《暗算》中,黄依依第一次找的结果经过一系列计算发现无 法归零,也就是说除不尽,我猜她可能试图将一个大数 N 做分解,没成功。第 二次计算的结果是归零了,说明她找到的 N=P×Q 的分解方法。"
作者在这里让自己的思想飞......当然没有问题，因为这段明显是《故事会》。不过.......穿越了，RSA 算法是 1977 年才出现的。
好了，现在我高度怀疑这本书其它部分的质量。不过由于我对那些领域的把握远不如密码，无从判断，只能希望作者在自己熟悉的部分不会乱来。
嗯，如果要作个总结的话，那就是：科普也要严谨，避免选择不熟悉的领域作为主题。同时高度推荐作者读一下方舟子以及科学松鼠会李清晨，桔子帮主等人的科普文。
附录 1
昨天看到了该书纸质版本的目录，密码学这章主要分成了两部分，1 密码学的自发时代，2 信息论时代的密码学，还有一个小结我们可以忽略掉。这个目录在我上次看的版本里是没有的，它体现了作者的一个想法：公钥密码是信息论时代的密码，文章中也说:
“有了信息论后，密码的设计就有了理论基础，现在通用的公开密钥的方法，包括《暗算》里的“光复一号”密码，就是基于这个理论。”
这个想法是似是而非的。一般认为香农的理论是个分界线，区分了古典密码和现代密码。自此以后，密码学的研究有了科学基础。但信息论对密码的影响主要体现在对称密码上，比如流密码和分组密码。香农给出的不可破密码就是流密码，分组密码设计中的扩散，混淆都来自香农的理论。如果要谈信息论时代的密码，应该举对称密码为例子。
那么香农的理论对公钥密码设计有什么影响呢？基本没有。公钥密码都是基于数学难题的，而且是带陷门的难题。有个相关术语叫陷门单向，意思是，加密函数在计算上是不可逆的，除非你知道陷门。文章中的 “有了信息论后，密码的设计就有了理论基础，现在通用的公开密钥的方法，包括《暗算》里的“光复一号”密码，就是基于这个理论。” 在第二个逗号之前是正确的，之后的是错误的，整体看来是似是而非的。
就加解密发展而言，有两个重要的里程碑。一个是 1949 年香农的 “Communication Theory of Secrecy Systems” ，另一个是 1976 年 Diffie, Hellman 的 “New Directions in Cryptography”。前者对流密码和分组密码产生重大影响，后者则开创了公钥密码的新方向。作者在一个名为“信息论时代的密码”的子章节中大讲与信息论关联不大的公钥密码，是文不对题的。
2012. 8. 23
附录2
有些朋友把作者的不严谨解释成为通俗而作出的妥协，同时表示如果按书评的写法，会很难理解。在这里我解释一下。首先，那个是书评而不是科普文；其次，通俗不等于传播错误观点。比如讲到大整数分解，可以说当 N 足够大时，按当前最先进的分解算法，也无法在合理时间内分解 N。当然不必提数域筛法。我提数域筛法只不过为了举证作者的谬误。其它地方类推。
应该区分两种情况：1、精通者对某领域深入浅出的介绍；2、一知半解者对某领域乱入错出的介绍。对这两种情况，外行人一般很难作出准确判断，如果碰上了后者，你可能会看得很爽，但得到的是一堆错误的信息。
2012.8.29
这本书开始看时感觉挺好的，扼要地介绍了中文分词，自然语言处理的一些基本想法，以及自然语言发展史上的一些传闻。我对上述领域完全陌生，读完后感觉获益良多。当我读到章节“谈谈密码学的数学原理”时，因为对这部分内容比较熟悉，本想直接跳过去的，但不小心看到章末的话：
"不管怎么样,我们今天用的所谓最可靠的加密方法的数学原理其实就这么简单,一点也不神秘,无非是找几个大素数做一些乘除和乘方运算就可以了。"
这句话太扯了，所以我又翻回去，决定把这章仔细看一遍。一看之下，发觉这章充满了 Bug, 作者显然对密码这个领域了解得不够。下面列出本章的一些软伤和硬伤。
1. 作者把公钥密码等同于 RSA 了，虽然他几乎没有提到 RSA 这个术语。这显然不符合事实。公钥密码体制是一个大类，常见的公钥密码体制有 RSA, EIgamal, 椭圆曲线，Rabbin 等。作者讲的其实只是 RSA, 难怪他会觉得“找几个大素数做一些乘除和乘方运算就可以了” 。事实上椭圆曲线公钥体制很常见，其背后的数学知识可深得很。
2. 作者说："我们今天用的所谓最可靠的加密方法的数学原理其实就这么简单"。
看了这句话，读者会认为 RSA 就是当前最可靠的加密方法了。这句话错得离谱，我并不是说 RSA 不安全，而是说我们无法作出这种比较。目前实践中使用的密码算法大致分为三类：a. 公钥密码; b. 分组密码，典型的如 DES, AES; c. 流密码，典型的如 RC4, HC-128, Rabbit 等。后两类又常合并归入对称密码体制。这三类密码分别用于不同场合。与对称加密算法比较，公钥密码的加解密速度慢很多，所以在处理大量数据时，应使用前者。在使用对称密码进行通信时，通信双方要约定一个 session key, 即会话密钥，这个密钥通常是用公钥密码体制来保护的。公钥密码和对称密码是协同工作而不是相互排斥的，所以并不能说 RSA 是最安全的加密算法。
3. 作者说：“要破公开密钥的加密方式,至今的研究结果表明最好的办法还是对大字 N 进行因数分解,即通过 N 反过来找到 P 和 Q,这样密码就被破了。”
如前文所述，作者这里的公开密钥加密方式指的是 RSA。通过分解 N 来破解 RSA, 当然很彻底，但由于技术上的困难，直接分解很难成功。作者这样写，会给读者一种错觉，即对 RSA 的攻击首选是分解，但事实并非如此。RSA 在使用上有很多讲究，稍不小心就会中招，很多攻击是针对使用不当展开的。关于这方面，有一篇综述“Twenty Years of Attacks on the RSA Cryptosystem”， 很容易查到。
4. 作者说：“对大字 N 进行因数分解,即通过 N 反过来找到 P 和 Q,这样密码就被破了。而找 P 和 Q 目前只有用计算机把所有的数字试一遍这种笨办法。”
因子分解是计算数论上的永恒主题之一，很多数学家对此作出了贡献。虽然困难重重，但情况远没有作者所讲的那么糟。目前最有效的分解方法是 GNFS, 即一般数域筛法。关于因子分解的历史，可以参考这本书：《计算代数数论》, 见 http://book.douban.com/subject/1165572/ 。
5. 作者说：“RSA-158 密码是这样因数分解的......”
RSA-*** 被称为 RSA (挑战)数。RSA 为演示其公钥体制的安全性，给出了一系列的大整数，悬赏求分解。右面的链接给出了全部 RSA 数的列表，仔细看一下，就会发现并没有一个叫做 RSA-158 的。其实这个 158 位 10 进制数的分解跟 RSA 数没有任何关系。这个分解纪录是 2002 年创造的，起源于对 2^953+1 的分解，当时已经有部分素因子被找到了，剩下一个 158 位的合数因子。这个纪录就是分解了这个合数因子，从而最终宣告 2^953+1 的彻底分解，详情见 http://www.crypto-world.com/announcements/c158.txt 。从该文档的内容看，对这个合数因子的分解使用的是数域筛法，而不是作者所说的“用计算机把所有的数字试一遍”。
6. 作者说：“好了,现在没有密钥 D,神仙也无法从 Y 中恢复 X。如果知道 D,根据费尔马小定理,则只要按下面的公式就可以轻而易举地从 Y 中得到 X。”
如果非要绕一个大圈子，用费马小定理来证，当然也可以做到。不过从书中所写的公式，我认为这里使用了欧拉定理而不是费马小定理。
7. 作者说："让我们回到《暗算》中,黄依依第一次找的结果经过一系列计算发现无 法归零,也就是说除不尽,我猜她可能试图将一个大数 N 做分解,没成功。第 二次计算的结果是归零了,说明她找到的 N=P×Q 的分解方法。"
作者在这里让自己的思想飞......当然没有问题，因为这段明显是《故事会》。不过.......穿越了，RSA 算法是 1977 年才出现的。
好了，现在我高度怀疑这本书其它部分的质量。不过由于我对那些领域的把握远不如密码，无从判断，只能希望作者在自己熟悉的部分不会乱来。
嗯，如果要作个总结的话，那就是：科普也要严谨，避免选择不熟悉的领域作为主题。同时高度推荐作者读一下方舟子以及科学松鼠会李清晨，桔子帮主等人的科普文。
附录 1
昨天看到了该书纸质版本的目录，密码学这章主要分成了两部分，1 密码学的自发时代，2 信息论时代的密码学，还有一个小结我们可以忽略掉。这个目录在我上次看的版本里是没有的，它体现了作者的一个想法：公钥密码是信息论时代的密码，文章中也说:
“有了信息论后，密码的设计就有了理论基础，现在通用的公开密钥的方法，包括《暗算》里的“光复一号”密码，就是基于这个理论。”
这个想法是似是而非的。一般认为香农的理论是个分界线，区分了古典密码和现代密码。自此以后，密码学的研究有了科学基础。但信息论对密码的影响主要体现在对称密码上，比如流密码和分组密码。香农给出的不可破密码就是流密码，分组密码设计中的扩散，混淆都来自香农的理论。如果要谈信息论时代的密码，应该举对称密码为例子。
那么香农的理论对公钥密码设计有什么影响呢？基本没有。公钥密码都是基于数学难题的，而且是带陷门的难题。有个相关术语叫陷门单向，意思是，加密函数在计算上是不可逆的，除非你知道陷门。文章中的 “有了信息论后，密码的设计就有了理论基础，现在通用的公开密钥的方法，包括《暗算》里的“光复一号”密码，就是基于这个理论。” 在第二个逗号之前是正确的，之后的是错误的，整体看来是似是而非的。
就加解密发展而言，有两个重要的里程碑。一个是 1949 年香农的 “Communication Theory of Secrecy Systems” ，另一个是 1976 年 Diffie, Hellman 的 “New Directions in Cryptography”。前者对流密码和分组密码产生重大影响，后者则开创了公钥密码的新方向。作者在一个名为“信息论时代的密码”的子章节中大讲与信息论关联不大的公钥密码，是文不对题的。
2012. 8. 23
附录2
有些朋友把作者的不严谨解释成为通俗而作出的妥协，同时表示如果按书评的写法，会很难理解。在这里我解释一下。首先，那个是书评而不是科普文；其次，通俗不等于传播错误观点。比如讲到大整数分解，可以说当 N 足够大时，按当前最先进的分解算法，也无法在合理时间内分解 N。当然不必提数域筛法。我提数域筛法只不过为了举证作者的谬误。其它地方类推。
应该区分两种情况：1、精通者对某领域深入浅出的介绍；2、一知半解者对某领域乱入错出的介绍。对这两种情况，外行人一般很难作出准确判断，如果碰上了后者，你可能会看得很爽，但得到的是一堆错误的信息。
2012.8.29
有关键情节透露
