日报标题：不管是保护自己的隐私，还是写一封浪漫情书，你都用得上 谢钧，尼古拉谢·奥斯特洛夫斯钧 长文慎入！多图杀猫！ 在上一篇中，@Banana9 学长对密码学做了一个很好的介绍概括。那么在这一篇中，就由我来给大家介绍一些具体的信息加密与密码破解的方式。看完这一篇，大家也能变成密码学的小能手，不仅可以巧妙地保护自己的隐私，还可以给钟意的妹纸 / 汉纸写一封浪漫的 without wax 的密码情书（误）。本文将由浅而深，最难只要求大家掌握高中数学基础，请各位放心阅读！ 本篇内容： 一、古典密码学 1.1 斯巴达将军的腰带——变位字谜 1.2 经久耐用的“数字、字母替换” 1.3 凯撒密码 1.4 凯撒平方 1.5 如何破译古典密码 二、现代密码学 2.1 对称加密 异或运算 流密码与块密码 电子密码本（ECB） 加密块链（CBC） 数据加密标准（DES） 高级加密标准（AES） 下一篇内容（敬请期待）： 2.2 非对称加密（更多未知惊喜） 在密码学发展的历史中，主要分为两个阶段，一个是古典密码学，另一个则是现代密码学。我们就先从较为简单的古典密码学开始： - 古典密码学 - 1. 在公元前 405 年，Lysander，一位古希腊的斯巴达将军，便将一份加密后的信息写在了腰带的背后。解码时，将腰带缠绕在特制的木棍上，便能读出正确的信息。 这种通过改变字母顺序的加密方式，被称为变位字谜（Anagram），常常被用于许多密码学相关的文学与影视作品当中。例如在丹·布朗的处女作《数字城堡》中，远诚友加所编造出来的同伙诺斯·达科塔（NDakota）即是友加本名（Tankado）的替换。而在其成名作《达芬奇密码》中，Anagram 的应用更是丧心病狂，例如卢浮宫馆长死前留下的遗言，“O, Draconian devil. Oh, lame saint. （严峻的魔鬼，跛足的圣人）”代表着“Leonardo da Vinci. The Mona Lisa.（莱昂纳多·达芬奇，蒙娜丽莎）”； “So dark the con of man（男人的骗局是如此阴暗）”代表着“Madonna of the Rocks（岩中圣母）”。而最为人熟知的 Anagram，应当还要属 J·K·罗琳所著《哈利波特》系列小说中的伏地魔：其原名为 Tom Marvolo Riddle，替换后变为“I am Lord Voldemort”. 2. 古希腊人还发明过另一种用数字替换字母的加密方式： 这种加密方式简单快捷，而且可以衍生出许多变体，因此一直沿用至第一次世界大战。 3. 在古典密码中，最为著名的，便是在上一篇中所提到的“凯撒密码”。它的加密方式在上一篇中也有讲到，因此在这里就不再赘述了。类似的加密还有 Alberti 密码盘： 4. 另一个与凯撒有关的，则是“凯撒平方”。虽然名称与“凯撒密码”相近，但是实际原理却完全不同，反倒是与 Lysander 相似。其基本原理，是将长度为完全平方数 n2（例如 9、16、64 等）的明文写依次在 n*n 的正方形中（如从左到右），然后改变顺序（如从上到下）将正方形中的字母抄下，即为密文。 5. 那么，当我们遇到古典密码时，要怎么破译他们呢？ 第二种与第三种加密方式，是逐字替换，即明文单位与密文单位一一对应。这个概念在高中数学（基本在高一）中的集合与映射中就有提到，相信大家不会陌生。如果是喜欢看福尔摩斯的童鞋们，大概这时候已经猜到了答案。当然，这里还要照顾一下没看过的孩纸们，我们还是从头开始。 密文单位与明文单位一一对应，导致了一个很明显的问题：密文中每个信息单位（一般情况下为字母）出现的频率，也会等于明文中某个特定信息单位出现的频率。可是，无论在何种自然语言体系当中，不同的文字单位都有其特定的出现频率。尤其在长篇幅、有意义的文字序列中，这个现象表现的尤为明显。以最典型的英语为例，26 个字母的使用频率分别为（数据来源：Letter frequency (English)）： 我们可以很明显地看到，字母 E 的使用频率远高于其他字母，另外字母 T、A 也都有较高的使用频率；而字母 J、Q、X、Z 的使用频率则相对较低。利用这一点，让我们可以在没有计算机的帮助下，也有极大的机率在短时间内破解出古典加密方式的密码。在福尔摩斯探案集约翰·特纳的故事中，对于密文“dv mvvw blfi svok”，便是将密文中出现次数最多的字母“v”认定为日常使用频率最高的字母“e”，然后顺藤摸瓜破解出明文为“we need your help”。 而随着科学技术的进步，古典密码受到了越来越严峻的挑战。因为需要加密的情报越来越多，而敌人监听的情报越多，结果就越符合基本分布频率，密码也就越容易被破译；加上计算机的出现，在计算机强大的枚举能力面前，古典密码那简单的字母代换已经不再是一个难题。因此，二战中的德军，专门为此发明了加密机 Enigma。Enigma 类似一台老式打字机（见下图左），每个按键上标写的是明文字母；而在每个按键下面，则是印满字母的圆盘，按下按键后自动打出对应的密文字母（见下图右）。通过旋转按键下面的圆盘，即可轻易改变字母的替换方式。二战时德军利用 Enigma，至少每天改变一次加密方式，以此来应对盟军情报部门的监听。饶是如此，德军仍然有不少重要情报被破译。 而第一种与第四种加密方式，是变位替换。而变位替换之所以一直没被作为主流的加密方式，在于其过于容易被识别。由于变位替换并不改变字母本身，而是改变其排列顺序，因此密文的字母频率会遵循自然语言的字母频率。尤其当密文越长，该现象也越为明显，越容易被识别；而如果密文过短，一来严重限制了能够传输的信息量，二来被破解的可能性也越大。但是变位替换是最富有艺术性的古典加密方式之一，尤其是当明文与密文都有意义的时候，常能令人啧啧称奇，回味无穷。 - 现代密码学 - 随着计算机技术的发展，古典加密方式越来越不能够满足信息加密与传输的作用。因此，以计算机技术为基础的现代密码学应运而生。与古典密码学相比，现代密码学的内容更为艰深，艺术性也更低。虽然我仍然能够保证将难度限制在高中数学范围内，但该部分将不再同古典密码一样拥有丰富而有趣的例子了。若各位看官到这里知难而退，不必为此感到羞愧；若有兴趣的读者愿意进一步深究，下面便为你们敞开现代密码学的大门： 由于现代密码学是建立在计算机技术的基础之上，因此在接下来的内容中，明文、密文以及其他所有的编码方式，都将以二进制来表示。至于自然语言与二进制之间的转换，一般按照 ASCII（美国信息交换标准代码）作为规范。 在现代密码学中，信息的加密与解密，都要依靠一把“钥匙”。这把“钥匙”的本质，是一串数据，或者说是一条信息。而根据“钥匙”种类的不同，我们将现代密码学分为两大类，对称加密与非对称加密。 1. 对称加密，指的是将明文加密，以及破解密文所使用的“钥匙”，是同一把“钥匙”。在介绍加密算法之前，我们得先了解一下数学逻辑中的“异或”运算。 异或运算，它的符号为“⊕”。真值表如下： 异或运算有这样一种性质，(X⊕Y)⊕Y=X。即对于 X 而言，使用相同的数字对其做两次异或运算，将仍然获得原来的 X。因此对称加密的最基本方式，便是将明文与同等长度的“钥匙”，按位依次做异或运算，即得到密文；而解密时，将密文再与“钥匙”按位异或，便得到明文，如图。 然而这种简易的加密方式有个致命的缺点，就是每个钥匙在使用一次之后就必须丢弃，不能重复使用。一旦重复使用，密文就会轻易地被破解。至于原因么，我就吊一吊大家的胃口，放到后面来说。 而在密码的加密与传输过程中，又分为流密码（Stream Cipher）与块密码（Block Cipher）两种。流密码的思想很简单：按位加密、按位传输。而块密码，则将明文与钥匙分成许多等长的小块（Block），每次按块加密再按块传输，如图： 由于块密码将钥匙也分成了等长的小块，所以钥匙的每个小块既可以用单块重复，也可以不重复。若小块不重复，则与流密码相似，钥匙长度与明文长度相同，其安全性较高，但是需要处理的数据量也较大。若小块重复，则大大缩短了钥匙长度，加密解密的速度更快，但是安全性较低。其典型代表为 ECB（Electronic Code Book，电子密码本），基本原理如图。 钥匙的重复使用容易导致安全问题，这在前面提到过，每个钥匙在使用一次之后就应当丢弃。而在 ECB 中，同一个钥匙被多次使用，更增加了其危险性。具体原因如下： 假设我们有 n 条信息 Mi(i=1,2,...,n)，对它们使用同一个钥匙 K 进行加密，则密文 Ci=Mi⊕K。当有人获取了两条或以上的密文 Ci、Cj(i≠j)时，将 Ci⊕Cj，便可以得到 Mi⊕Mj（证明：Ci⊕Cj=(Mi⊕K)⊕(Mj⊕K)=Mi⊕Mj）。那么只要有任意一条信息被破解，其他所有信息也都将被破解。而即使在改进加密方式，不再使用异或运算加密，相同的明文块在加密后，其密文块也仍然相同。如此，对方便可以使用类似破解古典密码学的方式，使用频率分析来破解 ECB 加密后的密文。 为了解决 ECB 的安全问题，同时仍然保证其钥匙长度短、加密速度快等优点，CBC（Cipher Block Chaining，加密块链）等方式依次被研发出来。由于篇幅限制（我好像已经写了好多的样子(*/ω╲*)……），这里仅简要介绍 CBC 的加密方式。 CBC 的加密方式，简要来说，就是将前一段的密文，作为后一段明文加密的钥匙；而接收到密文后，也如此依次解密。基本原理如图： 与 ECB 相比，CBC 较好地提高了安全性。只要被窃听的密文不连续，对方便很难破解出明文。 而目前使用最为广泛的块密码，则是 DES（Data Encryption Standard，数据加密标准）。但是在讲 DES 之前，需要先介绍 DES 的基础，Feistel 加密法。 Feistel 加密法，是将明文块拆解成长度相等的左右两块，将右半部用钥匙加密后，再用左半部进行二次加密，得到密文的右半部；而密文的左半部，则直接等同于明文的右半部。如图： 听上去挺简单，感觉要破解好像也没什么难度。但是这并不是 Feistel 的核心，它的思路是，一次加密不够？那就把密文当成明文，多来几次……注意到图中的“F”了吗？它代表的是轮函数，即在每一轮（每一次加密）中，它所使用的钥匙 K 是不一样的。于是，下面才是 Feistel 的正常画风： 而 DES 的算法加密，主要就是建立在 Feistel 的基础之上。DES 将输入的明文分割成 64 位长的块，先对每个明文块中的位子重新进行组合变换，置换方式如图 看不清楚是吗？没事，我也看不清楚……反正不是重点，你们记住在 DES 中顺序是换过了的就行了…… 在将明文块内的位置顺序变换之后，DES 会对变换后的明文块进行连续 16 轮的 Feistel 加密。每一轮中进行加密使用的钥匙，都是由 56 位的主钥匙所导出的不同的子钥匙。关于子钥匙的导出，以及利用子钥匙加密过程中的排列扩张、S-Box 替换、P-Box 排列等，感兴趣的童鞋可以私信我，这里就不再多说了（我觉着可能已经有好多童鞋看不下去了……）。 童鞋们，坚持住！我就讲最后一题，最后一题！！讲完就下课！！！ 啊，历史的车轮滚滚向前，长江后浪推前浪。作为 1977 年提出的“前浪”DES，虽然目前的使用仍然比较广泛，但是也快要被 2002 年提出的 AES（Advanced Encryption Standard，高级加密标准）给拍死在沙滩上了。在 RSA lab 举办的 DES Challenge II-2 比赛中，EFF（Electronic Frontier Foundation）在 56 个小时内便破解出了一个 DES 钥匙（RSA 又是一个大坑，我们将在下节课与这位可爱的大坑见面）。 于是乎，更流弊的加密算法应运而生，那就是由 Joan Daemen 和 Vincent Rijmen 所设计的 Rijndael 加密法稍加修改而成的 AES。要明白 AES 到底咋回事，我们得先了解 AES 中的四种基本操作：轮函数加密、字节替换、移行与混列。其中轮函数加密与 DES 中的轮函数加密相同，这里不再赘述。 与 DES 不同的是，在 AES 当中，明文被分割成 128 位长的块，即每个明文块长 16 字节（1 字节=8 位；1byte=8bit）；然后将每个明文块写成 4*4 的矩阵（矩阵，高中数学选修 4-2，一般高二就教了；没学过的童鞋，简单来说这就像最开头古典密码中的方法 2，看下图）。 首先，是字节替换。其本质与古典加密中的替换相同。只是在计算机的实现过程中，人们开发了一个神器，叫 S-Box。它是一个替换表，通过查表即可获得该字节所对应的替换字节。一般 AES 中的 S-Box 长这样： 可能有些童鞋有点看不懂，我稍微解释一下。AES 中每个明文块长度是 128 位，在写成 4*4 矩阵之后，每个矩阵单位的长度是 8 位。所以对于每个矩阵单位而言，总共有 2^8=256 种可能性，正好为 16^2。即两位 16 进制数刚好能够完全表示单个明文块的所有可能性。而表中的横纵坐标，对应的正是转换成 16 进制后的明文块的第 1 位与第 2 位。其中 A~F 代表 16 进制数中的 10~15。另外相应地，还有一个逆 S-Box，标注有替换字节所对应的原字节，用于解码时的逆字节替换。 然后，是移行。移行是怎样一个操作呢？我不说话，就上个图，相信大家都能看得懂： 啊不好意思，上面的图是逆向移行。正向移行么，把中间那一步反过来就行了。 最后是混列。正向混列为左乘一个矩阵 A，逆向混列为左乘一个矩阵 B： 可计算得 A·B=I，即 A、B 两个矩阵互逆。注意在混列的矩阵运算当中，加法是通过转化成二进制后进行异或运算来实现的。 好的，我们终于讲到了 AES 的结构了。不好意思我也觉得有点累了，还是直接上个图吧（说的好像我画个图更轻松一样~~~~(>_<)~~~~）。 说实话 AES 与 DES 都是一个德性，NIST（National Institute of Standards and Technology，美国国家标准与技术研究院）的想法就是，没有什么问题是一遍算法加密解决不了的；如果有，就多加几遍……不过要注意的是，加密的最终轮与其他不同，不再进行混列操作；因此解密时也相应地略去这一步。 好了，今天就上到这里，童鞋们辛苦啦！有什么问题呢可以课后找老湿@谢钧 讨论。下节课呢，将由何老师@何钦尧来给大家讲现代密码学中剩下的内容：非对称加密。请大家掌声欢迎！同时也请做好相应的预习工作（非对称加密涉及到较多的数论知识）与心理准备…… P.S. 若大家对于密码学的专业书籍感觉阅读有困难的话，也支持大家看一些密码学相关的文学与影视作品。例如著名的《福尔摩斯探案集》，丹·布朗的《数字城堡》（《天使与魔鬼》、《达芬奇密码》、《失落的符号》及《地狱》也比较推荐，但是这几部涉及的则更多是符号学而非密码学）。至于电影么，我看的不多，不敢妄言 P.P.S. 码字辛苦，绘图更辛苦。未经允许，严禁转载！ P.P.P.S. 本人是在南洋理工大学进行的密码学学习，因此文中的名词翻译可能与国内中文教材有异，请见谅。另外还要感谢@何钦尧学弟对本文的审阅与批改。 参考文献： [1] Buonafalce, Augusto, “An Exercise in Solving the Alberti Disk”. The Cryptogram LIV, 5, ACA, Plano 1999. [2] Alberti, Leon Battista, A Treatise on Ciphers, trans. A. Zaccagnini. Foreword by David Kahn, Galimberti, Torino 1997. [3] Carroll, Christine M., BSN, RN, MBA, Cryptology and Cryptography. Salem Press Encyclopedia of Science, January, 2015. 4p. [4] Lek, Kamol, Rajapakse, Naruemol, Cryptography: protocols, design, and applications. Hauppauge, N.Y. : Nova Science Publishers, c2012. [5] Piper, F. C., Cryptography: a very short introduction. Oxford ; New York : Oxford University Press, 2002. [6] Meyer, Carl H. Cryptography: a new dimension in computer data security: a guide for the design and implementation of secure systems. New York : Wiley, 1982. [7] Alhamdani, Wasim A. Teaching Cryptography Using Design Thinking Approach. Journal of Applied Security Research; Jan-Mar2016, Vol. 11 Issue 1, p78-89, 12p. 阅读原文
