通证通研究院×FENBUSHIDIGITAL联合出品
文：宋双杰，CFA；孙含儒
特别顾问：沈波；Rin；JX
导读
密码学，是一门将信息进行加密处理与传递，以及分析加密信息的学科。根据以RSA为代表的公钥加密体系的出现，可以将密码学的发展过程分为古典密码学与现代密码学两部分。古典密码学以“置换法”与“替换法”为基础，多应用于军事与情报领域；现代密码学则建立在数学、计算机与通信科学的基础上，除了加密信息之外，数字签名、数据完整性、身份认证等也是现代密码学的研究课题。
摘要
置换法依照一定的规则，改变原始信息中的字母排列顺序；替换法将原始信息中的字母按照一定的规则替换成其他字母。置换法与替换法的安全性较差，古阿拉伯的学者们开创了破译加密信息的科学——密码分析学，通过频率分析的方法破解替换式加密法。
在长达一千多年的时间里，古典密码学以置换法与替换法为基础不断演进。以维吉尼亚密码为代表的多字母表替换式加密法轮流使用多个不同的替换式密码表，依次对明文中的字母进行加密。第二次世界大战时德军使用的“恩尼格玛”是一种基于复杂的多表替换加密原理的机械式密码机，但最终由于自身加密算法的缺陷，被图灵设计的“炸弹”攻克。
置换式与替换式加密法的弱点在于没能完全消除密文中有关明文的某些特征，保留了明文中的某些信息。奥古斯特·柯克霍夫在19世纪提出的柯克霍夫原则概括性地总结了加密算法应遵循的设计原则：即使加密系统的各个环节都是公开知识，只要密钥未被泄漏，加密系统都应该是安全的。
加密算法的安全性问题本质在于：如何降低攻击者在了解加密算法，并拥有足够长的密文片段的前提下，猜测出正确密钥的可能性？1948年，香农创立了信息论，并在次年的一篇论文中从数学的角度讨论了加密系统，人们开始从科学的角度探究密码学的奥秘。
风险提示：量子计算技术的潜在威胁
目录
1隐匿法
2加密法
3持续千年的智力竞赛：加密与解密
4古典密码学的圣杯
5攻克“恩尼格玛”
正文
密码学，是一门将信息进行加密处理与传递，以及分析加密信息的学科。“密码学”一词的词源来自古希腊语“隐藏”和“书写”，意为“秘密书写”，其历史几乎与人类有文字记载的文明一样悠久。古希伯来学者在公元前六世纪左右就掌握了“单字母表替换式加密法”，在之后的两千五百多年里，古典密码学在替换式加密法的基础之上不断发展演进。古典密码学多应用于军事与情报领域，而微型计算机与现代密码学的发展能够保护普通人的日常通信免受第三方的窥探。现代密码学建立在数学、计算机科学与通信科学的基础上，除了信息的加密与解密之外，数字签名、数据完整性、身份认证等也是现代密码学的研究课题。今天人们日常生活中的网络支付、电子商务、电子货币等都是密码学这一人类两千多年来智慧结晶的应用。
密码学的概念与人们平时登陆网站、使用银行账户的“密码”并不相同。这些用于身份认证的“密码”，更准确的翻译是“通行词”或“通行码”，它是现代密码学的诸多应用之一，请读者注意区分两者的区别。
受限于篇幅，有关密码学以及密码学在区块链中应用的内容将分两篇专题介绍。
1
隐匿法
隐匿法的历史非常久远，可以追溯到公元前5世纪古希腊与波斯帝国的战争年代。公元前480年，波斯舰队在“万王之王”薛西斯一世的率领下秘密集结，准备对希腊发起进攻，然而这一秘密行动被一位遭到流放、居住在波斯的希腊人狄马图拉斯发现了。他将波斯军队准备进攻希腊的消息写在木板上，并用一层蜡将文字遮住，成功过了路途中的波斯卫兵，将信息传回了希腊。希腊城邦联合起来，抵御住了波斯人的突袭。而遭遇挫败之后，曾经盛极一时的波斯阿契美尼德王朝也开始走向衰退。
尽管简单地“将信息隐藏起来”与我们今天熟知的密码学相差甚远，被称为“隐匿法”的秘密书写方式却标志着人们开始探索信息保密的方式。
2
加密法
隐匿法仅仅将信息藏匿起来，一旦藏匿的方式暴露，或是负责传达信息的信使叛变，信息安全也无从保证。加密法则注重隐藏信息本身的含义，信息的发出方与接收方事先约定，将信息按照一定的规则进行转译，接收方在收到后遵循约定的规则就可以还原原始信息，而即使信息被第三方截获，如果不知道转译规则，也无法还原出原始信息。
加密法的出现标志着古典密码学的开端。在上面的例子中，未经加密的原始信息称为明文，按照特定的规则对明文进行转译后得到的信息称为密文，这个规则称为加密算法。古典密码学的加密算法大多是以字母、单词或是短语为基本单位，又可分为置换法和替换法两大类。
置换法依照一定的规则，改变原始信息中的字母排列顺序。公元前5世纪，斯巴达军队采用一种名为“密码棒”的工具对信息进行加密。发信人将长条形的羊皮纸带缠绕在一根木棒上，将信息横向书写，最后将羊皮纸解下。收信人将信纸缠绕在同样直径的木棒上，就能够还原信息。而羊皮纸上的文字看起来是无意义的，并且用尺寸不相同的木棒也无法还原出原始信息。
但只要了解这种密码的加密方式，就能很容易地解读密文。从密文的第一个字母开始，每数到它之后的第N个字母，记下该字母。记录到密文结尾后，再从第二个字母开始重复这样的操作，以此类推，很快就可以还原明文信息。其中N取决于木棒的直径，写下N个字母后，纸带正好绕木棒一圈，选择不同的N，同样的明文经过加密得到的密文也不相同。发信人和收信人要事先约定好同样的N，收信人才能还原密文。同时N不能被第三方知晓，才能保证加密通信的安全。这里的N称为密钥，是加密通信的参与方共同享有的秘密知识，用于加密和解密信息。
替换法将原始信息中的字母按照一定的规则替换成其他字母。据传，凯撒大帝使用替换式加密法写作书信。凯撒大帝将信息中的每个字母后移三位，例如A替换成D，Y替换成B，这种加密法称为凯撒挪移式加密法。在这个例子中，密文相比明文，每个字母都被后移了3位，密钥可以用3表示。密钥可能的取值范围为1～25的自然数，称为密钥空间。明文里所有可能出现的字母的集合称为明文空间，密文里可能出现的字母集合称为密文空间，替换法中的密钥可以表示为明文空间到密文空间的一个映射，在古典密码学中又称为密码表。密文空间可以与明文空间相同，例如凯撒密码中，密文的字母仍然是26个拉丁字母。密文空间也可以是明文空间的超集，例如在密文中混入一些无效字符，以干扰试图破译密码的行动。密文空间还可以与明文空间完全不相关，例如在柯南道尔所著的福尔摩斯系列的《跳舞的人》中，罪犯用26种形态各异的跳舞的小人来替换英文字母。
公元8世纪，阿拉伯哈里发帝国的第二个世袭王朝——阿拔斯王朝在巴格达定都，其建立之初的一百年是伊斯兰文明的黄金时代。据记载，阿拔斯王朝的官员们使用替换式加密法保护机密的行政事务、税收数据，相信这能够帮助他们建立一个廉洁、高效的政府。巴士拉的语言学家卡里尔撰写了《加密信息手册》，使用排列组合对阿拉伯语单词的加密法进行分析。此外，阿拉伯的学者们还开创了破译加密信息的科学——密码分析学。
3
持续千年的智力竞赛：加密与解密
古典密码学多用于军事、、外交领域重要情报的传递，希望刺探这些秘密的人自然不在少数。阿拉伯学者们在统计语言学资料时发现，在样本容量较大，有意义的阿拉伯语文本中，每个字母出现的频率是不一样的。字母a和字母l在阿拉伯语中出现频率最高，因为“al”是阿拉伯语中的定冠词，相当于英语的“the”，此外，元音的出现频率也比较高。这些成果很快被运用到密文分析中。
之前介绍的替换式加密法中，明文中的所有字母都遵循同一套规则进行替换，这样的加密法称为单字母表替换式加密法。公元9世纪，阿拉伯科学家肯迪在《解译加密信息》一书中阐述了对这种加密法的解译方式。如果能确定原文所使用的语言，首先列举出密文中出现的所有字母，统计它们各自出现的频率并排序，对照该语言中字母出现的频率顺序，就可以开始尝试对密文进行分析，这种方法称为频率分析法。频率分析还可统计某种语言中特定的字母组合出现的频率，如英文中的“ee”，以及某个字母前后特定字母出现的频率，如英文中字母“q”之后一定跟随”u”等。直到数百年后，中世纪的欧洲学者才掌握这一方法，并且决定了两位女王的命运。
1586年，英格兰政府对天主教的迫害日益加剧，安东尼·贝平顿与几位同党密谋策反，计划救出被伊丽莎白女王软禁的苏格兰女王、伊丽莎白女王的表妹、信仰天主教的玛丽女王，并暗杀伊丽莎白女王。贝平顿通过密使传递使用替换式加密法加密的书信，与玛丽女王商讨暗杀计划。贝平顿设计的更加复杂的替换式加密法使用23个符号替换除j、v、w之外的英文字母，4个不具有任何意义的混淆符号，表示下一个字母连续出现两次的“dowbleth”符号，以及若干个符号替换常用的单词，以尽量减少遭到频率分析法破译的可能。
但可惜的是，贝平顿信任的密使其实是一位双面间谍，背地里将他与玛丽女王的密函交给伊丽莎白女王的国务大臣、间谍头子沃尔辛厄姆，后者先打开信封，抄写一份密文，再重新伪造封缄，并将密文交给密码学家托马斯·菲利普分析。菲利普通过频率分析法破译了密码，并在玛丽女王寄出的一封信件后附加了一段伪造的密文，诱使贝平顿说出参与计划的同伙的名字。暗杀计划暴露后，玛丽女王、贝平顿以及其密党都遭到处决。
以上是一个过于信任加密方法的安全性，以致造成悲剧结局的例子。如何衡量加密通信安全与否是一个重要的问题，加密通信的过程可以划分为选择加密方式、约定密钥、加密明文、传输加密信息、还原明文几个步骤。古典密码学中，绝大多数加密方式都是替换法、置换法或者两者的结合，因此加密方式几乎不是秘密，试图对密文进行分析的人可以通过尝试所有可能的密钥进行解译，当某个密钥还原出的明文出现了有意义的单词，就说明找到了正确密钥。因此，密钥空间越大，意味着破译者需要尝试的密钥数就越多，密码就越安全。凯撒挪移式加密法只有25个可能的密钥，安全性非常差。
奥古斯特·柯克霍夫在19世纪提出的柯克霍夫原则概括性地总结了加密算法应遵循的设计原则：即使加密系统的各个环节都是公开知识，只要密钥未被泄漏，加密系统都应该是安全的。换一个方式来说，加密系统的安全性应依赖于密钥的保密，而不是加密算法的保密。
除此之外，加密算法自身可能也存在安全性漏洞，虽然密钥空间非常庞大，但破译者也能够通过分析密文的某些特征，缩小可能的密钥范围。明文的目的一般是传递某些信息，因而是有意义的，存在某些语言学或统计学上的特征，而密文则一定程度地保留了这些特征，如单字母表替换式加密法保留了不同字母出现的频率特征。为了消除这些频率特征，一些增强的替换式加密法被发明出来，但仍未能解决替换式加密法的缺陷。例如同音替换式加密法将出现频率较高的字母对应多个不同的密文，从而使密文中各个字母出现的频率相近，但字母组合的频率信息仍然没有完全消除，仍存在被破译的可能。法国国王路易十四用来加密机密文件的“大密码”采用替换字母对的方式，两个世纪以来都没有遭到破译。19世纪末，人们发现大密码的密文中出现的数字数量接近676，即两个字母组成的字母对可能的数量，从而猜到了其加密方式，并用频率分析破译了它。
玛丽女王的例子还说明，信息传递的途径并非绝对安全。由于通信的双方需要事先约定同样的密钥，如果传递密钥的方式不安全，整个加密通信系统也形同虚设，信息安全保卫战就是“密钥保卫战”。
早在15世纪初，文艺复兴时期的佛罗伦萨艺术家阿尔伯蒂已经认识到了单字母表加密法在频率分析法面前不堪一击，他提出了一套新的加密方法，即轮流使用多张密码表，依次对明文中的字母进行加密。这一方法由法国外交官维吉尼亚所发扬光大，发明了“维吉尼亚加密法”。维吉尼亚加密法采用26套不同的密码表，对应密钥为0～25的凯撒挪移式密码表，并以从A～Z的英文字母表示。加密的过程是，选择一个密钥单词，例如KEY，然后按照密钥单词中的字母顺序，依次对明文字母按照相应的密码表进行加密，第一个字母使用“K”对应的密码表替换，第二个字母使用“E”，第三个用“Y”，第四个再回到“K”，以此循环直至加密结束。这一类加密法称为多字母表替换式加密法，同样的明文字母可能会被加密成不同的密文，相同的密文字母不一定对应相同的明文，给破译者带来很大的干扰。维吉尼亚加密法的密钥空间几乎是无限的，一度被视为不可破译的，是一千年以来古典密码学的重大突破。
但英国发明家查理`巴贝奇不认为破译维吉尼亚密码是一项不可能完成的任务。当人们开始了解维吉尼亚密码的加密算法，它的致命弱点也随之浮现。维吉尼亚密码用于加密的基础密码表只有26种，而且都是已知的凯撒密码表。维吉尼亚密码加密明文使用密码表的顺序是固定的，因此同一个明文单词，被加密成的密文仅有有限种可能。可能的密文种类数取决于密钥单词的长度。并且位置相差密钥单词长度的所有字母都是使用同一张密码表进行替换的。巴贝奇发现，维吉尼亚密码的密文每过一部分，就会出现重复的字母组合，这意味着两个可能：一，不同的明文片段被密钥单词的不同部分加密成了相同的密文；二、同样的明文片段恰好由密钥单词在同样的起始位置进行加密，形成了相同的密文。如果重复的字母组合足够长，第一种情形出现的可能性就远远小于第二种。第二种情况还揭露一个事实：密钥单词长度一定是重复的字母组合位置相差数的因子。巴贝奇记录下所有重复的密文字母组合位置之差，以及它们的所有因子，其中出现最多的因子就是密钥单词可能的长度。合位置之差，以及它们的所有因子，其中出现最多的因子就是密钥单词可能的长度。
知道了密钥单词长度这一重要信息，巴贝奇把密文分成N组分别由N个单字母表加密的片段。尽管这些零散的片段对应的明文是没有意义的，但只要这个片段出自完整的、有意义的信息，那么它的字母频率分布仍然遵守书写信息所使用语言的规律。使用频率分析法，维吉尼亚密码就可以被破译。加密者为了方便记忆，通常喜欢选取有意义的密钥单词，但这也使密码变得更加不安全。
4
古典密码学的圣杯
维吉尼亚密码法看起来拥有庞大的密钥空间，如果使用26个英文字母的排列组合作为密钥单词，仅长度为6的密钥单词就有超过3亿种可能，为什么还是能够被破解呢？维吉尼亚密码法的缺陷就是循环使用固定的密码表对明文加密，一旦循环长度被破译者分析出来，整个加密算法就变的和单密码表加密无异。为了增强维吉尼亚密码的安全性，可以选用非常长的密钥单词，这样一来，密文中出现重复字母组合的可能性就降低了很多，并且使用同一套密码表加密的字母个数也随之减少，猜测密钥单词长度和频率分析法就失效了。
将这个理论发挥到极致，就是著名的“一次一密”加密法，这种加密法广泛地运用在外交、军事等需要不计代价地保证通信秘密的场合。“一次一密”，即每发送一条信息，就更换一个新的密钥单词，密钥单词的长度和要发送信息的长度相当，而且是随机生成的，不包含任何有意义的单词。秘密通信的双方各持有一本密码本，每进行一次通信，就撕下密码本的一页，使用下一页的密钥。从理论上来说，只要密码本没有泄露，即使破译者截获了某次通信的明文和密文，仍然无法破译下次通信的密文，“一次一密”是真正安全的加密方式，被誉为古典密码学的圣杯。
第二次世界大战时，德军使用的“恩尼格玛”密码机是一种近似“一次一密”的加密机械。由于“一次一密“加密法需要对每一条信息使用随机的与明文等长度的密钥进行加密以保证安全性，因此就需要事先编纂一本密码本。而到了近代以后，战争期间情报部门每天需要处理海量的消息，使用这种密码本，不仅不容易查阅密钥，被敌人截获的可能性也高出不少。
1918年，德国发明家亚瑟·雪毕伍斯发明了一种使用转子密码盘和机械结构的密码机，并分为商用和军用的版本。恩尼格玛使用键盘输入明文字母，输入信号经过三个编码器经过一系列别换，最终会点亮另一个键盘相应密文字母上的灯泡。最先接收输入信号的编码器每输入一个字母，就会转动一次，当它转动完一周，下一个编码器就会转动一次，以此类推，三个安装好的编码器一共有26×26×26种不同的状态，每一种状态对应一个密码表，在开始加密时，可以选择任意一种状态作为初始状态，用来加密明文的“密钥单词”也随着改变。除此之外，编码器位置可以互换，输入键盘和第一个编码器之间还有一个称为接线板的装置，可以互换六对字母的输入信号，有大约一千亿种不同的互换方式。恩尼格玛是历史上最为可靠的机械式密码机之一，但在英国传奇数学家阿兰·图灵和布莱切利公园的盟军密码工作者的努力下，德国军队使用的部分型号恩尼格玛密码机未能免遭被破解的命运，德军也为过于信任恩尼格玛的安全性付出了惨重的代价，恩尼格玛，是古典密码学最后的辉煌。未能免遭被破解的命运，德军也为过于信任恩尼格玛的安全性付出了惨重的代价，恩尼格玛，是古典密码学最后的辉煌。
5
攻克“恩尼格玛”
阿兰·图灵，今天人们以他的名字命名计算机科学领域的最高荣誉奖项。图灵建立了计算机器的通用模型“图灵机”，提出了“算法”的概念，还是第一个利用计算机器破解加密算法的人。
恩尼格玛密码机能够由操作员设置的部分包括三个编码器的位置、编码器的起始位置、接线板互换的字母设置，密钥空间超过10^16。德军情报部门会事先编制一本密码本，每天更换一次密钥。由于恩尼格玛曾有商用的版本，盟军对它的构造原理与加密方式有一定的了解，加上盟军缴获的几台密码机，恩尼格玛的加密算法可谓无处可遁，但不知道密钥的话，破译德军的加密情报仍然无从谈起。
密码分析学中，破译方尝试破解加密系统的行为称为攻击。根据柯克霍夫原则，假设加密系统除了密钥之外的一切都是公开信息，攻击实际上就是猜测密钥的行为。根据攻击者掌握的有关加密系统的信息量的多少，有以下攻击类型：
惟密文攻击：攻击者只拥有关于密文的信息
已知明文攻击：攻击者拥有某些明文片段和对应的密文片段的信息
选择明文攻击：攻击者可以获得任意明文片段对应的密文信息
选择密文攻击：攻击者可以获得任意密文片段对应的明文信息
如果一个加密系统对已知明文攻击是安全的，那么即使攻击者截获了一些密文和对应的明文，仍然无法解译新的密文。单字母表和维吉尼亚加密法对于后三种攻击方式都不安全。如果明文是有意义的文本，它们对于惟密文攻击也是不安全的，通过频率分析法就能够轻松破解。“一次一密”，即密钥长度等于明文长度的多字母表替换式加密法是对所有攻击安全的。香农在“一次一密”法出现后30年创立了信息论，并从数学的角度证明了其安全性。而恩尼格玛的安全性介于一次一密和维吉尼亚加密法之间，下面将简要地说明图灵破解恩尼格玛的方法。
恩尼格玛的插线板最多可以对换六对字母的信号，一个对换过程可以表示为
三个编码器从左到右记为,,，相对初始状态的位置记为,,，则插线板与编码器对原始信号的共同作用可表示为
到这里为止，恩尼格玛的设计都还中规中矩。发报员在键盘上按下按键，字母会被转化为数字信号，经过处理后变成密文在密文键盘相应的位置点亮灯泡。那如果要解密怎么办呢？密码灯只能展示密文字母，而不能用做输入。收到加密信息的一方需要与加密使用相同的键盘输入密文解密，也就是要设计一种能够同时进行加密和解密的电路，对任意明文字母以及对应的密文=()满足：
雪比伍斯的方法是在三个编码器之后，再加上一块反射板，其作用是将最左边一块编码器的输出触点两两连接起来，将其输出信号反射回三个编码器，再穿过接线板，连接到密文灯泡。记反射板变换为，它由十三对不同字母的对换复合而成，满足
恩尼格玛在某个特定编码器状态下的加密过程就可以表示为
对于惟密文攻击，恩尼格玛几乎是牢不可破的。德军每天会更换密钥，每则密钥加密的明文数量有限。密钥的长度为17576，比大多数明文长度都要长，因而频率分析法对恩尼格玛也不起作用。但是对于已知明文攻击，反射板设计的危害就体现出来了。盟军缴获了德军的几台恩尼格玛密码机，并对一些已知的明文和密文进行对比，发现德军公文的格式较为固定，经常在固定的位置出现同样的单词。比如德军每天发送的天气预报中会出现wetter这一单词。图灵还发现，有时明文和密文之间会出现一种特殊的循环结构，这有助于识别编码器的状态信息。假设已知明文为wetter，对应的密文如下：
可以看出这样的循环是在的作用下产生的，与接线板设置无关。图灵利用这一点，便可以不考虑接线板的接法，他使用三台相同的恩尼格玛密码机，随意设置第一台的编码器位置，记这个位置为，将第二台设置为1，第三台设置为3，并同步改变三台密码机的编码器设置。将第一台密码机的输出连接到第二台的输入，第二台的输出连接到第三台的输入，以此类推，从而模拟出同样的加密过程。如果编码器设置正确，就可以形成相同的循环回路。现在还不知道字母被接线板替换成了哪个字母，图灵想到，连接两台密码机所有对应的字母触点，逐一尝试可能的编码器位置，只要有一个回路连通，就说明存在一个字母经过三台密码机被加密成它自身。这时的编码器位置虽然不一定是正确的，但只要使用筛选出的编码器位置还原明文，使用频率分析逐个检验就可以破解接线板的设置了。
图灵的设想成功地将搜寻密钥的工作简化了几个数量级，英国图表机械工厂根据图灵的设计建造出了拥有十二台密码机的解密机器“炸弹”，可以分析长度为十二的循环结构。到了1942年底，布莱切利公园一共拥有49台“炸弹”，最快在一小时内就可以找出德军的当日密钥，对盟军占据情报上的优势提供了极大的帮助。
要破解恩尼格玛，已知明文与密文的对应片段、三个编码器的内部线路都是不可缺少的。二战期间，英国皇家空军使用“栽培法”引诱德国海军发送包含特定信息的密文。英国空军在特定的地点布置水雷，故意让德军发送有关该地点坐标的情报，拦截下密文送往布莱切利公园，这也是一种选择明文攻击。
替换式加密算法与加密机械的弱点在于没能完全消除密文中有关明文的某些特征，保留了明文中的某些信息，例如单字母表替换式加密法保留了明文语言中字母的频率信息。有些则是设计上的缺陷，例如恩尼格玛。德军在二战后期增加了编码器的数量、接线板对换的字母对数量，却没意识到反射器才是根本缺陷。一些古典加密算法已经开始消除密文中反映的频率信息，如同音替换式加密法，但始终没能触及加密算法安全问题的本质：如何降低攻击者在了解加密算法，并拥有足够长的密文片段的前提下，猜测出正确密钥的可能性？
1948年，克劳德·香农发表了著名的论文《通信的数学理论》，开创了一门新的学科：信息论。隔年，香农发表了《加密系统的通信理论》(CommunicationTheoryofSecretarySystem)，首先使用数学工具对加密系统进行分析。香农的理论使密码学得以成为真正的科学，也标志着现代密码学的开端。
参考文献：
TheCodeBook,SimonSingh(1999)
TheCodeBreakers,DavidKahn(1996)
附注：
因一些原因，本文中的一些名词标注并不是十分精准，主要如：通证、数字通证、数字currency、货币、token、Crowdsale等，读者如有疑问，可来电来函共同探讨。
本文为通证通研究院原创。未经授权，禁止擅自转载。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。