The Code Book (Simon Singh) 读书笔记

操作系统课中讲安全的一节是代课老师上的，期间他推荐了 The Code Book (Simon Singh) 这本书，说是讲密码学历史的。我对密码学感兴趣，就读了一读，并照“不动笔墨不读书”的原则，记了读书笔记，发表出来以飨观众。看完这本书之后我还把它拍卖了，拍卖规则是：我公布保留价，买家秘密出价，一段时间后第一高价者成为最终买家，支付第二高价的货款和邮费。

弗朗西斯·培根著《谈读书》（王佐良译）中有：

书亦可请人代读，取其所作摘要，但只限题材较次或价值不高者，否则书经提炼犹如水经蒸馏，味同嚼蜡矣。

这本书算不上什么严肃的，所以只看读书笔记了解大概也未尝不可。本文基本上是我的纸质笔记的直接转录，且没有进行认真的排版，会有缩略语和不符合习惯的用法。此外，该笔记很可能具有科学性或事实性错误。本文适合具有一定密码学知识者阅读，可快速获得一些密码的历史小故事。

第一到第五章：直到二战结束

密写 stenography、加密 cryptography
密写的例子：写在头皮上用头发盖住、隐形墨水、microdot（微雕，把一页缩成一个句点 = 用缩印作弊）
小学生传纸条加密法：重拍字母，先写奇数位，再写偶数位
Scytale 加密：把纸条卷在圆柱上写明文再取下来（Beakman’s World《比克曼的科学世界》里面介绍过）
substitution cipher 的故事：B.C. 4 世纪 Vātsyāyana 著 Kāma-sūtra 教女人 64 艺，第 45 个是 mlecchita-vikalpā = stenography 用于隐瞒她们的苟合（liaisons）
subst. cipher 首次军事利用是 Caesar 加密（移三位只是一种，还有用 replace by Greek letters 的）

Auguste Kerckhoffs von Nieuwenhof, Dutch linguist

发明 cryptanalysis 的是 Arab scholars（约 750 年起，乃 Islam 鼎盛时代）

freq. analy. 不总是有效 e.g.

• 短句子
• 法国人 Georges Perec 著 La Disparition 一文不含字母 e
• Gilbert Adair 将其翻译为 A Void 且不含 e

freq. analy. 不但可分析字母频率，还可以利用拼写规律（vowel/consonant 出现位置）
如何反击？故意拼错、用同音拼写干扰
密文中加无意义字符、加单词缩写（nomenclators）

Girolamo Cardano, Italian, maths - 三次方程, crypto, 其他 - 发明盲文的前身

Mary（英女王）之死：Walsingham 在中间窃听并诱骗信息

Weak encryption that gives false illusion of security is worse than no encryption at all!

Vigenère cipher, Vigenère 总结三个前人工作所得 = n-time pad

homophonic subst. cipher 是 subst. cipher 加强版，每个字母有 k ∝ freq. 个可能的密文 （每次随机选）
example weakness: q ≤ 1%, u ≈ 3%, 英语里 q 后面只有 u，如果一个密文字母很少见且后面总是跟着某三个密文字母之一，则这个组合很可能是 qu

The Great Cipher (GC) & Man in the Iron Mask (MitIM)
GC 加密的是音节，有些密文符号表示“删除上一个音节”
突破口：频发的密文 pattern 124-22-125-46-345，其明文是 les ennemis
GC 的破译揭示了 MitIM 的真身

MitIM 的神秘引人遐想，Victor Hugo 和 Dumas 同时写了 conspiracy 风的 play，VH 听说 D 也在写的时候放弃了已写的 2 acts

Mr Babbage：发明单一邮资、制作科学数表、自动计算机器 Difference Engine No. 1
破了 Vigenère cipher
计划写破译学的书，每种 cipher 2 个例子（一个示例，一个读者习题），但没写成
轶事：Thwaites 写信给 journal 想发表他独立发现的 Vigenère cipher，Babbage 指出该设计早已有之，Thwaites 气不过要 Babbage 破了它，后者欣然接受～
方法：先找重复出现的长序列（假设为相同内容的加密），分析 key 可能的长度（见书 pg. 70）再对 key 的每个字母位置用 freq. analy.
该方法未发表，后来名归 Kasiski (Kasiski test)

Pinprick encryption 实为 stenography（把真正的文本下面加小点）；Beakman’s World《比克曼的科学世界》里面也介绍过类似的“烤肉架加密法”；有些小说/漫画/影视作品的情节里面有人质被绑架犯要求打电话报平安时通过说奇怪的话 + 适时捂住 mic 实现 pinprick 传输 SOS 信号

Book cipher 里书是 key，页码 + 行号 + 序号 编码单词首字母；Sherlock Holmes Black Lotus Tong 里面有提到这个；历史故事 Beale ciphers，尚未破译（有疑点/破绽/阴谋论）

radio / 无线电 comm. 优点 - 到处可收，缺点 - 到处可收（易窃听），又 - 易 forge? 亟需 crypto. 一战时火热！

为何 Germany 不及时搞密码？Didn’t bother.
Germany 进攻法国时，法国人边撤边 destroy landlines，German 必须用 radio（易 intercept）但法国未失守处还有自己的 landlines，故 German 没有截获多少信息

法国 - traffic analy.

• Wilson = 美国总统
• Zimmerman = 德国外交大臣
• P.Mexico = 墨西哥总统
• G.A.Wash = 在 Washington 的德国大使 = von Bernstorff
• G.A.Mexico = 在 Mexico 的德国大使 = von Eckhardt
• Mr. H = 在 Mexico 的英国特务
• Admiral Hall = 英高官

One-Time Pad
约 1918 Major Joseph Mauborgne 完整提出 OTP
（注：不可用常用单词生成 key！）
问题：难以产生、分发 random keys

Cipher Machines
cipher discs 用于 modular addition（俩圆盘，可转）
Enigma 约 ${10}^{16}$ 个 keys，价格合现今的 £20 000，商用太贵；Germany 军方起初不用——他们以为 Zimmerman telegram 是在 Mexico 以明文泄露而不是被破译；后 Germany 军方采用（买了大概 3 万多台）

If necessity is the mother of invention, then perhaps adversity is the mother of cryptanalysis.

— pg. 144, The Code Book

Enigma in use

1. 每天有 day key（机器的 config）
2. 每条消息有 msg key（减少 key reusing），用 day key 加密 msg key 两次来传递之（冗余减少失误），然后用 msg key 加密 msg body

因为用词语选 key 已过时，language experts 效用不大，Polish cryptanalyst leader Biuro Szyrów 决定多用科学头脑
注意到 msg key 为了除错而重复加密了一次，该种重复降低了安全性——突破口
考虑 msg key 的密文 $A_1A_2A_3A_4A_5A_6$，14、25、36 为同一字母用不同位置同一密钥加密，对固定 day key 有 3 个双射关系，这 3 个双射的循环分解的型（所属 $S_n$ 的共轭类）只与 Enigma 配置的一部分有关，分析之可得 day key 的一部分
分析该部分后取消另一部分的 permutation 作用，再用 phrase-based analy. 等手段可破译消息（另一部分是很少的几个对换的积，相对容易）

Rejewsk 为破译者，Langer（其上级）其实有 day key，但是为了练兵所以没告诉他
1939，德国提高了 Enigma 的 ‘security parameter’，Rejewski 的破译方式被 budget 限制，Langer 的 key informant 也断了——惨！
Langer 在波兰被入侵前将成果全数交给 allies（英法），伟大！

二战中英法利用 Enigma usage 上的弱点：

1. 有规律的 msg key（被叫做 cillies），例如字母在打字机上临近、是女朋友的名字
2. scrambler position 每天都必须变化（看似安全，实则 key space 缩小）
3. plugboard 不得含有相邻字母的对换（看似安全，实则 key space 缩小）

Turing 的初恋是和他一起学习 science 的小伙伴！然而朋友四年，小伙伴肺结核死翘翘了。

Turing 破译 Enigma 的工作：
他发现消息内容的规律性（例如早上某时刻消息的某位置一定含有德语“天气”一词），并结合 Rejewski 的方法找一种不依赖重复 msg key 的破译方式
crib - 一个已知的明文—密文对应关系
同样利用了 permutation 的循环分解
Turing 要自动化破译，Rejewski 用的是机械的 bombes，Turing 用的是电路，也冠名 bombe（派上用场了！）

Fortunately the authorities did not know that Turing was a homosexual. Otherwise we might have lost the war.

— Jack Good

Turing 曾去看过 Snow White and the Seven Dwarfs 并对毒苹果情节念念有词，和他最终自杀方式有关吗？

二战中德军不同支部的 Enigma 使用是独立的，Naval Enigma 最难破译——连 crib 都很少，怎么办？

• Chosen Plaintext Attack：英国人埋雷，若德军踩中，则将发送带雷坐标的 telegram，以此获 crib——‘sowing mines for cribes’ = ‘gardening’
• Social Engineering：偷 key
  1. 在 English Channel 撞船
  2. 英军伪装为德军假意救援，顺走 codebook
  3. 在败露之前可解密通信
  4. 该方法乃 Ian Fleming 提出的，代号 Operation Ruthless（冷酷行动），我看应该叫“戏精行动”

Be cautious to not arouse suspicion（别把破译的信息用得太满，同之前 Zimmerman telegram 的手法）

Barrier of Language：用一种敌方不会的语言通信——高效且安全（类似一种 random encoding）
Problem：美军激战时来不及加密/解密，只能靠吼，然而日军的英语太好了
Solution：用 native American language（请 native American 负责通信）
附加好处：tamper-proof、unforgeable

古埃及文字是 phonograms，但一度被认为是 semagrams，法军（Napoléon Bonaparte）发现了 Rosetta stone，上有同一段文字的两种古埃及文字写法以及希腊语写法（= crib!）
那为什么 Rosetta stone 在 Br. museum 呢？
法国战败的时候签的协议把它交给英国了

Linear A & Linear B（得名于书写上有许多线条）
Sir Arthur 的考古发现
在 Plato/Aristotle 再往前 ~600 年的古希腊
Linear B 有 90 个 characters ⟹ syllabic

• alphabetic: 20-40 chars (e.g., Arabic, Russian, Latin)
• semantic: 一堆（e.g. 汉字）
• syllabic: 中间地带（e.g. 假名？）

Sir Arthur 认为 Linear B 不是 Greek 而是一种 native Cretan lang. 并打压异见者

后来希腊主岛出土 Linear B，那是不是 Greek 呢？
又或者 Linear B 语言是 lingua franca（类似 Latin 在 Europe 的地位）？

前 40 年解密 Linear B 毫无进展

Alice Kober：发现 Linear B 中的一些词可以三三分组，一个 triplet 中的 3 个词似乎是字尾改变（变位、性数格变化），但有一个位置的字母似乎既非 stem 也非 ending——为什么？她管这个叫 bridging syllable，因为一个字母代表一个音节，如果 stem 以辅音结尾而 ending 以元音开头，则连接处的字母会随两部分一起变化。

Michael Ventris：

1. 复辅音——插入虚拟元音
2. 元音开头词——一些符号表示元音音节，用分析符号出现位置的方法找到了 2 个这样的符号

Ventris shared 一系列 Work Notes，其中 WN20 总结了 35 个符号于 5 元音 × 15 辅音（外加无辅音）的表格
他又找到了 3 个常出现的词，认为是地名，通过一番分析可以得出大量符号的音值；此外账目表最下方的单词拟音和希腊语 ‘as much’ 相近（注：该单词理应是 ‘total’）
——所以 Linear B 是不是希腊语？
Ventris 发现了许多希腊语单词（他起初是 Sir Arthur 的非希腊语阵营的支持者）

John Chadwick 得知 Ventris 的工作后 review 他的 notes 想要挑刺儿，却成了支持者，并用他的希腊语知识一同破译了 Linear B 之谜

冷知识：一个 informal test on 破译准确性是看“神祇的名字”个数——一般 nonsense words 会被认为是一个未知的神的名字。Ventris & Chadwick 的破一种只有 4 个神的名字，且都是 well-established Gods

第六章：Alice and Bob Go Public

二战时德国另一个 cipher 是 Lorenz，比 Enigma 更难破。Max Newman（Bletchley 数学家）用 universal Turing machine 的 idea 设计了 programmable computer，但 Bletchley 高层搁置（shelve）了该 project。
Tommy Flowers 实现了它并交给了 Bletchley，该机器名为 Clossus，乃现代电子计算机之先驱；当然，由于保密，ENIAC 长久以来被认为是第一台计算机。

战后计算机发展，cryptographer—cryptanalyst 之战也愈加火热，加密也走进商业界。

第一个标准化的 enc. scheme 是 Feistel 发明的 Lucifer 的一个版本，又叫 DES。在标准化之前，NSA 干预它的 key 数目 s.t. 民间无法解密但 NSA（因具有庞大算力而）可以。

又一个问题：key distribution？用快递？快递不 scale——‘horrendous logistical nightmare’, ‘the cost is prohibitive’.

吐槽：接下来的历史应该是我熟悉的密码学知识了…

果不其然，Diffie-Hellman! Diffie 在 ARPANet 还在 infancy 的时候就在想 key distr. 的问题了
Hellman: professor at Stanford Univ.
Diffie 和 Hellman 认识后在 research 上一拍即合，Diffie 以研究生身份入学，在研究过程中 Ralph Merkle 加入。当时大家都不看好他们研究 crypto

真实世界里的 Diffie-Hellman 类比：

1. Alice 锁上有秘密的盒子并发给 Bob
2. Bob 用他的锁再锁上，还给 Alice
3. Alice 拆掉她的锁并发给 Bob
4. Bob 可以打开盒子查看秘密

But in general, 加密是不交换的，D-H 更贴切的比喻是“颜料混合”。Mathematically, we use $Y^x\mathrm{\ mod\ }P$.

该 scheme 也叫 Diffie-Hellman-Merkle key exchange, 突破是 Hellman 深夜做出的
此外 Diffie 和他妻子谈及他对 asymmetric encryption 的想法，但他未有一个具体的例子（受 DH 交换之启发？）

若有 PKE，则 KE 是 trivial 的（至少 DH KE 是 trivially achievable 的）；此外 DH KE 要求双方交互的需求也将降低——you just look up someone’s public key!

PKE 的比喻：无需钥匙即可扣上的锁头必须要钥匙才能打开。钥匙 = trapdoor function

DHM KE 生于西海岸，而 PKE (RSA) 生于东海岸：

• 1977.4 Ron Rivest 夜间想出了 RSA
• 1977.8 Scientific American 提出 RSA 挑战——分解一个 $\sim{10}^{129}$ 的数
• 1994.6 分解出来了

Alternative History of PKC

There was no theorem that said you had to have a shared secret.

— James Ellis

他受一篇匿名文章启发，文章提到一种安全电话通信：

• 听者在电话线上叠加 random noise
• 说者在电话线上叠加 message
• 听者自己可以减去 random noise
• 窃听者只能听见 message + random noise
• 重点：recipient takes part in encryption

1969 Ellis 已经发明了 public/private key 的概念，且走在寻找 trapdoor function 的路上

Clifford Cocks 加入了 GCHQ 后听说了该问题并找到了 RSA trapdoor function (1973)，据他回忆，他从听说问题到想出来用了半小时。Hardy 曾说 “Real mathematics has no effect on war” 其中 real 指 pure，例如数论就是“纯数学”，然而 Cocks proved him wrong.

Malcom Williamson 于 1974 加入 GCHQ，乃 Cocks 老朋友，听闻 RSA 后不敢相信，研究之（想挑刺儿），在违反保密条例在家狂算 5 小时之后，发现了 Diffie-Hellman-Merkle KE

1997.12.18 Cocks 在 GCHQ 允许下进行关于这段研究的 presentation，可惜 Ellis 于 1997.11.25 去世了

第七章：Pretty Good Privacy

RSA 公司只和 business/gov. 合作，Phil Zimmerman 认为应在大众中推广加密，于是开发 PGP，他想到了用 RSA 保护对称 key、用对称 key 加密消息的 scheme（因为 RSA 慢而对称快），且他让 PGP user-friendly，支持：

• 自动 2-phase 加密
• 用鼠标移动的 entropy 生成 RSA key-pair
• 数字签名

有 2 个问题：

1. RSA 有专利保护（但 PGP 和 RSA Inc. 的 market niche 不重合，P.Z. 认为可以有免费 licence）
2. 法律要求一切电信业务提供明文以备 discovery（民权组织和 RSA Inc. 成功说服法条废止，然而会不会死灰复燃呢？）

发布后，广受好评，但也有问题：

1. RSA Inc. 不给予免费许可，诉其专利侵权
2. 非法出口武器（encryption was [is?] a weapon!）

NSA 相关电影：Mercury Rising (1998), Enemy of the State (1998)

pro/anti-enc. 阵营：libertarians + corporations v.s. law enforcement
中间派：key escrow scheme

AEES 将 key 分成两半，存在 2 个机构中，只有 gov. 同时说服 2 个机构才可监听。该标准是 optional，民权组织不买账，AEES 没起色。
未来会有 compulsory escrow 吗？

Kenneth Neil Cukier: intelligent, honourable and pro-escrow, 人们不可能同时有这三种品质。

虽然 crypto policy 一直变，但 CA 的存在一直不变
CA 认证 entity 与 public key 之间的对应关系 e.g. Verisign
另一类公司 TTP 提供 key recovery — controversial

• 正方：TTP is a necessary part of sensible PKI
• 反方：TTP is a reincarnation of key escrow

回到 Phil Zimmerman，当时法律对网上分发软件算不算“出口密码设备”定义很模糊，FBI 调查了 3 年之后放了 P.Z.：

1. MIT Press 把 PGP 源码印成书出版了——要起诉 MIT Press 吗？
2. 覆水难收
3. 不一定能定罪——很难定罪！

此外 Zimmerman 和 RSA Inc. 也谈妥了（我怀疑：RSA Inc. 牺牲专利费换取人们好感）

第八章：A Quantum Leap into the Future

警告 这一章可能包含大量由我造成的科学错误，如果您能指出我将十分感谢。然而，如果您指出的错误是该书所产生的，将不予更正。读者应当注意这本科普读物里面可能包含不严谨的内容。

Tempest attack：通过监视电磁场来还原事件（相当于透视眼）。可用电磁屏蔽材料防护，但该类防护罩的购买需要 gov. 许可，说明 FBI 有利用该 attack

Traffic analy., virus/trojan horse, backdoor is a special kind of trojan horse.

Thomas Young：破译埃及文字（见笔记本 pg. 38 处的故事，但笔记没记），也是“杨氏双缝干涉实验”的“杨”。此人下午喜欢坐在鸭塘旁边歇着，从鸭子扑腾的水波的干涉想到双缝实验里面的光是一种波。

Young 的双缝干涉实验可以用“光是由光子组成的波”（我：光子之于光，相当于绳段之于振动的绳、水分子之于水波？）
后人又做了个实验：若降低光子的发射速率 s.t. 一分钟发射一个光子，那么依次观点，将不会有干涉——但实际上还是有干涉，为什么？

Quantum theory 的两派：

1. superpositionists：未被观察的光子可以同时穿过两个孔并和自己干涉
2. many-world interpretation：一个光子可以通过两个孔之一，这会导致宇宙分叉成有两个，这两个宇宙可以互相干涉

Consequences of qntm theory

1. 解释 Young 的实验
2. 计算核反应
3. 解释 DNA
4. 解释太阳的燃烧
5. 设计激光 CD 读头
6. 量子计算

David Deutsch：1985 年 paper 提出 qntm computer
一种理解 quantum computing 的方式是它可以计算 particle states in superposition（我：类似并行？）
hurdle to qntm cmpting: maintaining superposition state thruout computation. 这要求必须不 observe（预防意外的 observation）

两个有名的 qntm algorithms

• Shor 分解质因数
• Grover 在 list 中搜索

Qntm crypto

late 1960s: 研究生 Wiesner 提出 qntm money (hard to counterfeit)
too ahead of time 没人 took it seriously
qntm money 利用光子偏振
光子有偏振，通过偏振片的光子的偏振永远和偏振片方向平行
两个正交的偏振方向可以看成是 qubit state 的一组标准正交基
既不平行也不正交于 polaroid filter 方向偏振的光子以一定概率通过 filter，且通过后改变为平行方向的
（我：偏振片 = 一个 measurement device？）

考虑 4 种偏振的光子：$\left|0\right>,\left|1\right>,\left|{+}\right>,\left|{-}\right>$（原文是水平、垂直、斜线、反斜线，这里用四个常见的态表示）
每张流通货币有序列号 SN（字符串）和密码 PW（四进制数），SN 到 PW 是一个映射，存在银行
SN 印在货币上，PW 的每一位代表一个偏振方向，纸币上安置位数那么多的 light-trap 储存正确偏振的光子

to verify a note:

1. 通过 SN 查询正确的 PW
2. 用偏振片验证纸币上存储的光子具有正确的偏振
3. 若通过，银行自己知道正确的偏振方向，所以很容易 refill light-traps

to forge a note 要么要量子克隆一张纸币上的光子偏振态（熟知这是不可能的），要么要分辨一张纸币上的光子偏振态（熟知不能完美区分非正交的态）

Currently impractical because

1. 未找到可以持久保存 specific 偏振态的 device
2. 即使有，也太贵，不值得用来保护纸币

Wiesner 四次提交论文，被拒四次。只有 Charles Benett 赏识该 idea，并在十年间多次重读他的 manuscript。之后 C.B. 和 Gukkes Brassard 讨论该论文，两人最终想到可用于 crypto.

第一个想法：Alice 有一个二进制串，每一位她随机选择用 $\left|0\right>,\left|1\right>$ 或 $\left|{+}\right>,\left|{-}\right>$ 来编码，并发送给 Bob
问题：Bob 必须事先知道每一位是哪种编码的才能正确解码——回 key distr. 老问题

breakthru:

1. Alice 产生一堆 random bits 每一位随机用两种编码之一发送
2. Bob 对每一位随机用两种编码之一解码
3. Alice（明文）告诉 Bob 每一位的编码
4. Bob（明文）告诉 Alice 他们每一位的测量方式有没有 coincide

然后 Alice 和 Bob 扔掉所有没 coincide 测量方式的 bits，这大概扔掉了一半 bits

对于 Eve，她不知道正确结果；此外，如果 Eve 中途测量 qubit 就会导致 qubit 坍缩到她的测量结果，只要 Eve 没猜对就会导致数据损坏。Alice 和 Bob 随机拿一些 bits 检查就可以发现此事（类似 garbled circuits 里面的 cut-and-choose 方法），把用于检查的 bits 也扔掉，剩下的部分用作 shared secret (e.g., one-time pad)

• 1988-1989: Brenett 首次完成 qntm crypto 实战（两个电脑间隔 30 cm）
• 1995: U of Geneva 完成了 23 km 距离的量子密码实战

该量子密码方案非常安全——窃听 = tamper ⟹ 被察觉。Open questions:

• 我们能造出来能大量应用的量子密码设备吗？
• Gov. 会管制之吗？

The Code Book (Simon Singh) 正文完。感谢 Jinzheng Tu 和 Shan Zhou 对笔记内容的指正。