频率分析的一些实用技巧

本篇尝试将对西蒙·辛格 The Cook Book 附录部分进行翻译，中文版《密码故事》并未将其一并翻出。显示中英双语关闭中英双语

附录一 The Opening of A Void

作者：Georges Perec
翻译：Gilbert Adair

Today, by radio, and also on giant hoardings, a rabbi, an admiral notorious for his links to masonry, a trio of cardinals, a trio, too, of insignificant politicians (bought and paid for by a rich and corrupt Anglo-Canadian banking corporation), inform us all of how our country now risks dying of starvation. A rumour, that’s my initial thought as I switch off my radio, a rumour or possibly a hoax. Propaganda, I murmur anxiously—as though, just by saying so, I might allay my doubts—typical politicians’ propaganda. But public opinion gradually absorbs it as a fact. Individuals start strutting around with stout clubs. “Food, glorious food!” is a common cry (occasionally sung to Bart’s music), with ordinary hard-working folk harassing officials, both local and national, and cursing capitalists and captains of industry. Cops shrink from going out on night shift. In Mâcon a mob storms a municipal building. In Rocadamour ruffians rob a hangar full of foodstuffs, pillaging tons of tuna fish, milk and cocoa, as also a vast quantity of corn—all of it, alas, totally unfit for human consumption.

First published in France as La Disparition by Editions Denöel in 1969, and in Great Britain by Harvill in 1994. Copyright © by Editions Denöel 1969; in the English translation © Harvill 1994. Reproduced by permission of the Harvill Press.

附录二 频率分析的一些实用技巧

1. Begin by counting up the frequencies of all the letters in the ciphertext. About five of the letters should have a frequency of less than 1 percent, and these probably represent j,k,q,x and z. One of the letters should have a frequency greater than 10 percent, and it probably represents e. If the ciphertext does not obey this distribution of frequencies, then consider the possibility that the original message was not written in English. You can identify the language by analyzing the distribution of frequencies in the ciphertext. For example, typically in Italian there are three letters with a frequency greater than 10 percent, and nine letters have frequencies less than 1 percent. In German, the letter e has the extraordinarily high frequency of 19 percent, so any ciphertext containing one letter with such a high frequency is quite possibly German.Once you have identified the language you should use the appropriate table of frequencies for that language for your frequency analysis. It is often possible to unscramble ciphertexts in an unfamiliar language, as long as you have the appropriate frequency table.首先计算密文中所有字母出现的频率。约有5个字母的频率低于1%，它们可能表示 j， k，q， x 和 z。其中有一个字母的频率应该大于10%，它可能是 e。如果密文不遵从这条分布规律，那么应当考虑原始信息不是采用英文写作的可能性。你可以通过分析密文字母频率分布来确定一种语言。典型地是意大利语，它的三个字母出现频率高于10%，9个字母频率低于1%。德语中字母e的频率高达19%，因此密文中有如此高频率的字母很可能就是德语。一旦你确定了某种语言，你应该使用合适的频率表对这种语言进行频率分析。只要你使用了恰当的频率表，就很有可能解密以不熟悉语言写成的密文。
2. If the correlation is sympathetic with English but the plaintext does not reveal itself immediately, which is often the case, then focus on pairs of repeated letters. In English the most common repeated letters are ss, ee, tt, ff, ll, mm and oo. If the ciphertext contains any repeated characters, you can assume that they represent one of these.如果密文显示与英语有联系，但明文却没有立即显现出来——这很寻常——接下来关注几对重复字母。在英语中，最常见的重复字母是 ss，ee，tt，ff，ll，mm 和 oo。如果密文中包含重复字母，你可以假设他们是上面的其中一个。
3. If the ciphertext contains spaces between words, then try to identify words containing just one, two or three letters. The only one-letter words in English are a and i. The commonest two-letter words are of, to, in, it, is, be, as, at, so, we, he, by, or, on, do, if, me, my, up, an, go, no, us, am. The most common three-letter words are the and and.如果密文在单词之间包含空格，那么尝试确定一二或三字母的单词。单字母的词只有 a 和 i。最常见的两字母单词有 of, to, in, it, is, be, as, at, so, we, he, by, or, on, do, if, me, my, up, an, go, no, us, am。最常见的三字母单词有 the 和 and。
4. If possible, tailor the table of frequencies to the message you are trying to decipher. For example, military messages tend to omit pronouns and articles, and the loss of words such as l, he, a and the will reduce the frequency of some of the commonest letters. If you know you are tackling a military message, you should use a frequency table generated from other military messages.如果可能，对你正在尝试解密消息的频率表进行删减。比如，在军事消息中倾向于省略代词和介词，诸如 l, he, a 和 the 的缺失会降低某些最常见字母出现的频率。如果已经知道要处理的是军事消息，你应该使用由其他军事消息生成的频率表。
5. One of the most useful skills for a cyptanalyst is the ability to identify words, or even entire phrases, based on experience or sheer guesswork. Al-Khalı ̄l, an early Arabian cryptanalyst, demonstrated this talent when he cracked a Greek ciphertext. He guessed that the ciphertext began with the greeting “In the name of God.” Having established that these letters corresponded to a specific section of ciphertext, he could use them as a crowbar to pry open the rest of the ciphertext. This is known as a crib.对于密码破译师来说，最有用的技巧是根据经验或是知道不完全信息的基础上确定单词，甚至整个短语。海利勒（Al-Khalīl），这位阿拉伯早期的密码破译师，在破解希腊文密文时就展示了这种天赋。他猜测密文是以问候语“以上帝的名义”（In the name of God）开头的，在建立起这些字母与特定密文的关联后，他就可以拿它们用作撬棍，把剩余密文撬开了，就像剽窃他人著作一样。

附录三 言过其实的“圣经密码”

In 1997 The Bible Code by Michael Drosnin caused headlines around the world. Drosnin claimed that the Bible contains hidden messages that could be discovered by searching for equidistant letter sequences (EDLSs). An EDLS is found by taking any text, picking a particular starting letter, then jumping forward a set number of letters at a time. So, for example, with this paragraph we could start with the M in Michael and jump, say, five spaces at a time. If we noted every fifth letter, we would generate the EDLS mesahirt…
1997年，迈克尔·德罗斯宁（Michael Drosnin）所著的《圣经密码》（The Bible Code）成为了世界各地的头版头条。德罗斯宁声称在圣经中含有隐藏信息，它可以通过搜索“等距字母序列”（equidistant letter sequences ，EDLSs）找到。 EDLSs 可以在任意文本中选取特定的起始字母，然后每次跳跃特定数目字母的方式找到。比如说，这个段落是以 Michael 的 M 开头，本例中每次跳五个位置。如果我们以每五个字母跳跃，得到了 EDLS 序列 mesahirt……

Although this particular EDLS does not contain any sensible words, Drosnin described the discovery of an astonishing number of biblical EDLSs that not only form sensible words, but result in complete sentences. Skeptics are not impressed because the Bible is so large: In a large enough text, it is hardly surprising that phrases can be made to appear by varying both the starting place and the size of the jump. Brendan McKay at the Australian National University tried to demonstrate the inevitability of Drosnin’s approach by searching for EDLSs in Moby Dick, and discovered thirteen statements pertaining to assassinations of famous people, including Trotsky, Gandhi and Robert Kennedy.
即使这个特别的 EDLS 并不含有意义的单词，但德罗斯宁发现了令人惊讶的一系列圣经 EDLSs，它不只是有意义的单词，甚至是完整的句子。由于圣经是如此之大，这不足以说服怀疑论者：在足够大的文本中，通过调整起始位置和跳跃距离而产生的短语不足为奇。澳大利亚国立大学的布兰登·麦凯（Brendan McKay）试图通过在《白鲸记》（Moby Dick）搜索 EDLSs 来证明德罗斯宁方法的必然性，结果发现了十三个有关名人暗杀的叙述，他们包括托洛茨基（Trotsky），甘地（Gandhi）以及罗伯特·肯尼迪（Robert Kennedy）。

附录四 猪圈密码

The monoalphabetic substitution cipher persisted through the centuries in various forms. For example, the pigpen cipher was used by Freemasons in the 1700s to keep their records private. The cipher does not substitute one letter for another; rather, it substitutes each letter for a symbol.
单字母替换密码（the monoalphabetic substitution cipher）以广泛的形式存在了数个世纪。比如，18世纪共济会成员（Freemasons）使用猪圈密码（the pigpen cipher）保护其记录的私密。这种密码不使用字母替换另一个字母，而使用符号进行替换。

To encrypt a letter, find its position in one of the grids, then skecth that portion of the grid to represent that letter. Hence:
要加密字母，首先找到它在方格中的位置，然后画出代表那个字母的方格部分。因此：

If you know the key, then the pigpen cipher is easy to decipher. If not, then it can be broken by:
如果你知道密钥，解密猪圈密码很简单。否则，它会断裂成：

附录五 RSA 的数学原理

What follows is a straightforward mathematical description of the mechanics of RSA encryption and decryption.
以下是 RSA 加密和解密机制的简易数学描述。

1. Alice picks two giant prime numbers, $p$ and $q$. The primes should be enormous, but for simplicity we assume that Alice chooses $p = 17$, $q = 11$. She must keep these numbers secret.
   Alice 选取两个大的质数（prime numbers）$p$ 和 $q$. 质数应当尽可能的大，但为了简化说明，我们假设 Alice 取 $p=17$, $q=11$. 她必须对这两个数字保密。
2. Alice multiplies them together to get another number, $N$. In this case $N = 187$. She now picks another number $e$, and in this case she chooses $e = 7$ ($e$ and $(p-1) \times (q-1)$ should be , but this is a technicality).
   Alice 将它们相乘得到新数字 $N$. 在本例中 $N = 187$. 现在她选取新数字 $e$, 在本例中她取 $e = 7$（$e$ 和 $(p-1) \times (q-1)$ 应当互质（relatively prime），但这是技术性的）。
3. Alice can now publish $e$ and $N$ in something akin to a telephone directory. Since these two numbers are necessary for encryption, they must be available to anybody who might want to encrypt a message to Alice. Together these numbers are called the public key. (As well as being part of Alice’s public key, $e$ could also be part of everybody else’s public key. However, everybody must have a different value of $N$, which depends on their choice of $p$ and $q$.)
   现在 Alice 可以将 $e$ 和 $N$ 发表在类似电话簿的地方。由于这两个数字是加密的必要条件，它们必须能被想要给 Alice 发送加密消息的人获取到。这两个数字合称公钥（the public key）。（$e$ 也可以是其他人公钥的组成部分，就像它是 Alice 公钥组成部分一样。然而，其他人必须有着不同的 $N$ 值，它取决于 $p$ 和 $q$ 的取值。）
4. To encrypt a message, the message must first be converted into a number, $M$. For example, a word is changed into ASCII binary digits, and the binary digits can be considered as a decimal number. $M$ is then encrypted to give the ciphertext, $C$, according to the formula $C=M^{e}\ (mod\ N)$.
   加密的消息首先要转换成数字 $M$. 比如，一个单词可以转换成 ASCII 二进制数字，二进制数字可以被转换成十进制。根据公式 $C=M^{e}\ (mod\ N)$, $M$ 被加密成密文 $C$.
5. Imagine that Bob wants to send Alice a simple kiss: just the letter $X$. In ASCII this is represented by 1011000, which is equivalent to 88 in decimal. So, $M = 88$.
   假设 Bob 想要给 Alice 发送一个小玩意：字母 $X$. 在 ASCII 中它被表示为 1011000, 等于十进制 88. 因此 $M = 88$.
6. To encrypt this message, Bob looks up Alice’s public key, and discovers that $N = 187$ and $e = 7$. This provides him with the encryption formula required to encrypt messages to Alice. With $M = 88$, the formula gives $C=88^{7}\ (mod\ 187)$.
   要加密这条消息，Bob 查找了 Alice 的公钥，找到 $N = 187$, $e = 7$. 这提供了他给 Alice 发送加密消息的加密等式所需要的信息. 由 $M = 88$, 可知等式 $C=88^{7}\ (mod\ 187)$.
7. Working this out directly on a calculator is tough, because the display cannot cope with such large numbers. However, there is a trick for calculating exponentials in modular arithmetic. We know that since $7 = 4 + 2 + 1$,
   直接在计算器计算是很困难的，因为它无法显示如此大的数字。然而，幂模运算（exponentials in modular arithmetic）中有一个技巧，因为我们知道 $7 = 4 + 2 + 1$,

   $88^{7}\ (mod\ 187) = [88^{4}\ (mod\ 187) \times 88^{2}\ (mod\ 187) \times 88^{1}\ (mod\ 187)]\ (mod\ 187)$
   $88^{1} = 88 = 88\ (mod\ 187)$
   $88^{2} = 7744 = 77\ (mod\ 187)$
   $88^{4} = 59969536 = 132\ (mod\ 187)$
   $88^{7} = 88^{1} \times 88^{2} \times 88^{4} = 88 \times 77 \times 132 = 894432 = 11\ (mod\ 187)$

   Bob now sends the ciphertext, $C = 11$, to Alice.
   现在 Bob 可以发送密文 $C = 11$ 给 Alice。

8. We know that exponentials in modular arithmetic are one-way functions, so it is very difficult to work backward from $C = 11$ and recover the original message, $M$. Hence, Eve cannot decipher the message.
   我们已经知道幂模运算是一种单向函数（one-way functions），因此从 $C = 11$ 反过来恢复到原始消息 $M$ 是很困难的，Eve 无法解密消息。
9. However, Alice can decipher the message because she has some special information: she knows the values of $p$ and $q$. She calculates a special number, $d$, the decryption key, otherwise known as her private key. The number $d$ is calculated according to the following formula:
   但 Alice 可以，因为她得到了某个特别的消息：她知道 $p$ 和 $q$ 的取值。她计算一个特别的数字，解密密钥 $d$, 它也被称为私钥。数字 $d$ 的计算遵从以下等式：

   $e \times d = 1\ (mod\ (p – 1) \times (q – 1))$
   $7 \times d = 1\ (mod\ 16 \times 10)$
   $7 \times d = 1\ (mod\ 160)$
   $d = 23$

   (Deducing the value of $d$ is not straightforward, but a technique known as Euclid’s algorithm allows Alice to find $d$ quickly and easily.)
   （计算 $d$ 的值并不容易，但是辗转相除法（Euclid’s algorithm）能够让 Alice 又快又准地找到 $d$.）

10. To decrypt the message, Alice uses this formula:
    要解密消息，Alice 使用这个等式：

    $M = C^{d}\ (mod\ 187)$
    $M = 11^{23}\ (mod\ 187)$
    $M = [11^{1}\ (mod\ 187) \times 11^{2}\ (mod\ 187) \times 11^{4}\ (mod\ 187) \times 11^{16}\ (mod\ 187)]\ (mod\ 187)$
    $M = 11 \times 121 \times 55 \times 154\ (mod\ 187)$
    $M = 88 = X$ in ASCII

Rivest, Shamir and Adleman had created a special one-way function, one that could be reversed only by somebody with access to privileged information, namely, the values of p and q. Each function can be personalized by choosing $p$ and $q$, which multiply together to give $N$.
Rivest, Shamir 和 Adleman 创造了一种特殊的单向函数，只有拥有特殊信息（即 $p$ 和 $q$ 值）的人才能执行其逆运算。通过选取 $p$ 和 $q$，他们相乘等于 $N$，得到特定的函数。

Having described RSA in terms of encrypting a message letter by letter, it is necessary to clarify one particular point. In the previous example, RSA is effectively reduced to monoalphabetic substitution without key distribution. In practice, encryption would proceed according to much larger blocks of binary digits, thus making frequency analysis impossible.
为了清楚地阐明要点，我们已经逐字逐句地解释了 RSA 加密消息的过程。在前面的例子中，RSA 有效地解决了单字母替换密码的密钥分发问题。在实际中，加密会使用巨大的二进制数字块进行计算，这使得频率分析成为不可能。

—The Code Book by Simon Singh 青少版 附录补译，原作所使用许可证 Attribution-Noncommercial-No Derivative Works 3.0。
———–

后记 到底谁在公交车上

《密码故事》第68页中译者将 The Sun and the Man in the Moon 翻译成“在月亮中的太阳与人”，这引出了一个有意思的话题。为了说明这个问题，我引用《英语常见问题解答大词典》的例子：

I saw him on a bus.
我在公交车上看到他。
我看到他在公交车上。

哪种理解是正确的，到底谁在公交车上，还是都在公交车上？事实上我们无从知晓答案，在英文中它无法表达出这一种状况。你只能通过上下文去推测谁在哪里。例如：I saw him on the airplane. 双方要得看到对方必须都在飞机上。回到《密码故事》，根据常识可以知道 The Sun and the Man in the Moon 表达的是“太阳和月亮中的人”而不是“在月亮中的太阳与人”，因为很显然月亮的大小是装不下太阳的。这里我引用解答大词典的一段话作为结尾：

在英语中，有时候我们只能根据逻辑分析来确定句子的语法结构，而无法用语法分析加以证明。这说明英语的语法结构的严密性是有很大缺陷的，所以人们常常把英语称为含糊的语言（ambiguous language）。

相关参考链接：
https://www.englishforums.com/English/WhatExactlyDoesMean/qnhqw/post.htm