《S.》中使用的加密法

S.》中使用到了四种经典的加密法:

本文介绍这四种加密法的加解密方法、在书中的应用和解密过程。

波雷费加密法

波雷费加密法(Playfair cipher)由 Charles Wheatstone 于 1854 年发明,由 Lord Playfair 大力推广并以后者的名字命名。此加密法在第二次波尔战争和两次世界大战中都有应用,主要用于短时间内保护重要但非致命的信息。现代电子计算机的出现使得波雷费加密法在几秒钟内就会被破解,而不再被军方使用。

波雷费加密法首先需要生成一个 \(5 \times 5\) 的矩阵,使用关键字或短语(去掉重复的字母)及剩下的英文字母按顺序填充这个矩阵。填充顺序可以是从左到右、从上到下填充,也可以是从最左上角开始、顺时针方向螺旋向内填充。由于英文字母有 26 个,而矩阵只有 25 个位置,因此可以去掉字母 J 或 Q,或者字母 I 和字母 J 使用同一格等。

加密时,将明文每两个字母作为一个二元组,对照上面生成的矩阵,对每个二元组依以下四条规则处理:

  • 如果二元组中两个字母相同,则将第二个字母替换为 X 再继续加密;如果只剩一个字母(即明文长度为奇数),则加上字母 X 再继续加密。也可以使用字母 Q 或其它任意不常用的字母。
  • 如果二元组中的两个字母在矩阵中位于同一行,则分别使用右边的字母替换(矩阵中最右边的字母则翻转到最左边的字母替换)。
  • 如果二元组中的两个字母在矩阵中位于同一列,则分别使用下面的字母替换(矩阵中最下面的字母则翻转到最上面的字母替换)。
  • 如果二元组中的两个字母在矩阵中既不在同一行,也不在同一列,则分别使用各自同一行且与对方同一列的字母替换(也就是对角上的两个字母,注意替换后二元组中两个字母的顺序)。

解密时,对密文两两组成的二元组使用上述后三条规则相反的操作处理(同行左移,同列上移,其余对角),并根据第一条规则去掉末尾不合理的字母 X 或 Q,或将字母 X 或 Q 替换为其前面的字母,即可得到明文。

在《S.》中第二章注解 2 中,出现了以下几个人名:

  • Oskar Heilemann
  • Herbert Uhler
  • Bolingbroke Wadkins
  • Helmer Aasen
  • Martin Gonçalves
  • Sydney Youngblood

将各个姓名首字母提取得到如下密文(二元组):

OH HU BW HA MG SY

英文原版第二章标题为 The Drifting Twins,而文中内容是在说双子星座(Gemini)。将 GEMINI 作为关键字,采用从左到右、从上到下的顺序并忽略字母 Q 的方法,构造出如下加解密矩阵:

使用上文介绍的方法对每个二元组解密过程如下:

O 和 H 在矩阵中同行,替换为各自左边的一个字母(H 的左边翻转到 O),得到 L 和 O:

H 和 U 在矩阵中既不同行也不同列,替换为各自同一行并与对方同列的字母,得到 O 和 P:

B 和 W 在矩阵中同列,替换为各自上面的一个字母,得到 E 和 R:

H 和 A 在矩阵中同列,替换为各自上面的一个字母,得到 A 和 G:

M 和 G 在矩阵中同行,替换为各自左边的一个字母(G 的左边翻转到 N),得到 E 和 N:

S 和 Y 在矩阵中既不同行也不同列,替换为各自同一行并与对方同列的字母,得到 T 和 X:

最后,将解密后的字母串起并根据语义加入空格,得到如下明文:

Looper Agent X

去掉最后一个用于填充的字母 X (第一条规则)即得到「鲁柏是特务」的信息。

虚无加密法

虚无加密法(Nihilist cipher)最初在 19 世纪 80 年代由俄罗斯虚无主义者用于组织对抗沙皇政权的恐怖行动中。

与波雷费加密法一样,虚无加密法也需要先使用关键字构造一个 \(5 \times 5\) 的矩阵,所不同的是,此矩阵中的字母以所在行号和列号作为该字母的坐标(两位十进制数),这样的矩阵称为波力比阿矩阵(Polybius square)。另外,波力比阿矩阵中通常将字母 I 和 字母 J 放在同一格,或字母 C 和字母 K 同一格,而不采用去掉字母 Q 的方法。

除了波力比阿矩阵,虚无加密法还需要选取一个密钥用于加解密。

加密时,将明文各个字母对应的坐标,依次加上密钥各个字母对应的坐标,就得到密文。密钥长度小于明文长度时,将密钥循环使用。各个字母坐标相加后的数值可能不止两位数,但不做取模等其它额外处理。

而解密时,将密文各个数值减去密钥各个字母对应的坐标,得到的数值作为坐标在波力比阿矩阵中对应的字母,即可得到明文。

在《S.》第六章中,注释中出现的所有年份的后两个数字组成了密文:

66 64 47 83 64 33 46 86 53 54 52 43 72 85 66 46 64 44 72

第六章的英文标题为 Sleeping Dog,其中 sleeping 作为构造波力比阿矩阵的关键字,dog 作为密钥。

构造出的矩阵如下所示:

密钥 dog 对应的坐标为 31 41 22,解密过程就是循环使用 31 41 22 去减密文的数字,得到的数值再对应到矩阵中,如下所示:

根据语义及上下文,加入空格和标点,得到如下明文:

Mac was Judas, not Tiago.

也就是说,「犹大(叛徒)是麦(金内),而不是狄亚哥(·贾西亚·费拉拉)」。

连续金钥加密法

连续金钥加密法(Running key cipher)是多字母替换加密法的一种,通常使用书中某一段开始的文字作为密钥。所使用的书通常是事先约定的,而采用书中哪一段作为密钥应该是随机的,并通过密文中的某个特殊标记或其它方法暗示消息接收者。

加密时,对照多字母替换加密法常用的维吉尼亚表(Vigenère table / Tabula recta),将明文的每个字母作为行号,密钥的每个字母作为列号,一一替换为表中对应行列的字母,即得到密文。

维吉尼亚表如下所示(来自维基百科):

解密时,将密钥的每个字母作为列号,查看此列对应密文字母所在的行号,即是对应的明文字母。对所有密文一一替换后得到完整的明文。

在《S.》第七章中,密文来自注解 5,直白地列出了一串字母:

L B Q T A H M A K
A F P F A P G O J M
U P B A N G R N J L

而 Eric 和 Jen 根据注解 1 提到的「讣闻」,和注解 1 及讣闻中都出现的「猜不透(impenetrable)」,猜出了密钥来自讣闻中的这一句话:

the impenetrable CORIOLIS and the saccharine WINGED SHOES

密钥的第一个字母为 T,查看维吉尼亚表的 T 列,找到密文的第一个字母 L,位于 S 行,因此对应的明文字母为 S,依此类推,解密过程如下图所示:

根据语义加上空格和标点后,得到明文:

Sum losing hope. Please get in touch.

意指「沙默思(Summerby)渐渐失去希望,请联系」。

栅栏加密法

栅栏加密法(Rail fence cipher)属于换位加密法的一种,即明文本身的字母不变,只是相互之间变换位置。

顾名思义,栅栏加密法在加密时,将明文以蛇形依次错位写在一个假想的栅栏的每一行(rail)上,到达栅栏底部后折返向上,到达栅栏顶部后折返向下,如此反复直到所有明文结束。最后,将栅栏上的文字逐行依次取出即得到密文。

而解密时,可以像维基百科上介绍的那样,根据栅栏高度计算出第一行栅栏的字母间隔,再将密文按此间隔及错位依次在每行上写下来,最后以蛇形重组即是明文。但更简单的方法,是直接根据栅栏高度及密文长度,画出明文的蛇形表格(栅栏高度为表格行数,密文长度为表格列数),再将密文逐行逐个填入蛇形的空格中。

比如,在《S.》的第八章中,将本章所有注解中排版错位的字提取出来后得到如下密文:

这走么想出长着来时试给间有其以没他来有任你又何有你人没伊一有想个忘再机记不会过念她思你过有止没停有

密文长度为 49,而栅栏高度正是本书中最重要的数字:19。绘制如下 19 行 49 列的表格并以灰色阴影标出蛇形:

再将密文逐行逐个填入蛇形的空格,即「这」填入第一行第一个带阴影的空格,「走」填入第一行第二个带阴影的空格,「么」填入第二行第一个带阴影的空格,依此类推,全部填入后的蛇形如下:

根据语义加入标点后,得到如下明文:

这么长时间以来,你有没有忘记过她?你有没有停止过思念,不再想伊?你又有没有试着想走出来,给其他任何人一个机会?

由上述解密过程可以看出,对于中文来说,栅栏加密法的加密强度大大减弱。即使不解密,从密文中也能看出大概意思。那再看看英文原版书中的密文是怎样的呢?

HVAAEVHYEROYEUOHEUTVEEUECVORNEBGARAIHSGVCTNEAOINEPKASPNNLEIYEDHOETN

密文共有 67 个字符,而栅栏高度同样为 19,因此是一个 19 行 67 列的表格。同样方法绘制蛇形并填入后如下:

所以解密后的明文根据语义插入空格和标点后如下所示:

Have you ever stopped thinking about her? Have you ever given anyone else a chance?

小结

从上述对这四种经典加密法的分析可知:

  • 作为换位加密法的一种,栅栏加密法的强度最低。攻击者只需遍历从 2 到密文长度减 1 的栅栏高度,很快就能译出明文。尤其不适合中文。
  • 虚无加密法本质上仍是维吉尼亚加密法,且明文与密钥简单相加之后没有取模运算,这使得密文可能大于 100。而大于 100 的密文对应的明文和密钥一定来自 \(5 \times 5\) 矩阵的第 5 行,这为破解提供了额外的信息。
  • 波雷费加密法虽然将单字母替换改进为双字母(二元组)替换,但仍然可以通过对密文中二元组的频度分析得到对应的明文二元组,从而译出明文,加密强度仅比单字母替换方法稍好一些。
  • 连续金钥加密法在这四种加密法中的强度最高,不仅采用了多字母替换,而且所使用的密钥可能来自任何文本材料的任何一段,这使得密钥数量浩如烟海。但假如用于暗示密钥位置的信息泄漏或被破译,连续金钥加密法同样非常脆弱。

上述的加密强度分析仅是在这四种加密法之间做相对的比较,毕竟都是经典的加密法,在现代的实际应用中,都已不满足高强度加密的要求。

以上。

comments powered by Disqus