笔记分享｜组队学习密码学（4）— 密码：从艺术到科学

9月2日，OpenMPC组队学习·密码学 第四期 <密码：从艺术到科学>，我们邀请到了来自原语科技的密码学专家 应用数学博士刘仁章老师，带领大家一起学习密码学从艺术到科学，密码的发展史和小故事！我们整理了第四期的分享内容方便大家学习，感兴趣的同学们可以点击视频，观看完整版分享。

首先我们来看一下什么叫做密码，密码是指采⽤特定变换的⽅法对信息等进⾏加密保护、安全认证的技术、产品和服务。这个定义是我国的密码法给出的定义。

这里需要做一个区分：“密码不是口令”，在生活中我们提到的银行卡密码、登陆密码等等实际上只是一种口令。密码学有两大分支——密码编码学（设计）和密码译码学（分析）。

1

几种古典的密码算法

接下来我们来看几种古典的密码算法。第一个是Atbash算法，它是一种代换（Substitution）密码，即通过将每一个字母按照上图右边的对应关系得到新的字母。比如要加密“CRYPTOGRAPHY”，那么C对应X，R对应I，Y对应B，P对应K，T对应G，O对应L，G对应T，A对应Z，H对应S，最终得到“XIBKGLTIZKSB”，解密过程同理。

我们不难发现，它的加密过程和解密过程是一样的，是一种“对合变换”。“对合变换”与其他变换相比有什么优势呢？因为对合变换它的正变换（加密）和逆变换（解密）是一样的，所以在软件实现的过程中，无论是加密还是解密，只需要调用一次整个过程；在硬件实现的过程中，可以有效减少芯片资源；在机械实现的过程中，可以有效节省空间。大家今后如果研究对称加密的话，不难发现，在扩散层中选用对合变换有一些特殊的优势。

第二个是Scytale算法，我们拿一个如上图右边所示的棒子，然后拿一张纸带，在上面横向书写明文，接着将纸带展开即得到对应的密文。大家可以自己动手尝试，将明文“scytale is a permutation cipher”加密为密文“serihcimoeysunrtatcapailetp”，解密的过程和加密是同样的。这种算法是一种置换（Permutation）密码，即明文和密文中出现的字母是相同的，但是他们的位置发生了变化。

说到密码，有几个名词和它比较像，容易混淆。

第一个名词是加密，即隐藏信息的含义，通俗来说就是“让人看不懂”；

第二个名词常出现在信息安全领域，叫做隐写术，它隐藏了信息的存在，简单来说就是“看不见”，如果与加密技术结合起来，它的安全性会更高；

第三个名词是编码，编码分两种，一种是信源编码，解决信息的表示问题，比如一个系统的信息如何在另一个系统中表示，常用的有摩斯“密”码（摩斯电码）、哈夫曼编码，另一种是信道编码，解决在有噪声的信道里如果进行可靠传输的问题，常用的有汉明码、极化码等。

此外，同态加密中也会用到编码技术。实际上我们在每一个加密过程中都隐含着编码的过程：将一段消息变换为一段明文，这个过程就是利用了编码技术，将信息从消息空间编码到明文空间。比如如果有一封英文的信件，怎样将这些英文转换为明文（数字）呢？

接下来再来看一些不太常见的密码算法：猪圈密码、当铺密码、培根密码（它们都是代换密码）、栅栏密码（是一种置换密码）、方言等等。

2

密码学小故事

很多战争的失败都是密码被破译导致的。今天这里的第一个故事是巴宾顿阴谋。首先介绍一下主要人物：苏格兰女王玛丽、英格兰女王伊丽莎白、英格兰情报⼤⾂沃尔⾟厄姆、破译专家菲利普斯、故事主角巴宾顿、双⾯间谍吉福德。

故事的大意是：伊丽莎白女王将玛丽女王囚禁，巴宾顿等人希望暗杀伊丽莎白女王以此营救玛丽女王，他们买通了一位送酒的马车夫，将加密的情报放入中空的酒桶木塞中，这个传递的过程相当于我们前面提到的隐写术。双面间谍吉福德知晓了此事并将这一情况告知了沃尔⾟厄姆，沃尔⾟厄姆找到了菲利普斯破译密信，他们发现破译后的信中没有他们想要的情报。

随后，菲利普斯模仿玛丽女王的笔迹，按照原有的加密方式在密信中额外加入了一些信息，成功地从来往信件中套出了想要的情报。

我们可以简单看一下网上的资料，这里是一个改造的单表代换加密，除了常见的字母表代换外，还有一些特殊的单词、短语代换，因此破解起来会更复杂一些。菲利普斯能够在密信中额外加入一些信息并不被发现的这一特性被称为密码的可延展性。在《福尔摩斯探案集》之“跳舞的小人”这一故事中也体现了该性质。除此之外，密码学还有一性质被称为认证性，它确定了发送方的身份。

这段历史上还有几位著名人物，其中一位是沃尔特·罗利爵士，他提出了格理论中的堆球问题。堆球问题是指，在空间中放一些大小相同的球，球不重叠，怎样使得球的堆积密度最大。

关于这个问题，我国的宗传明老师做出了一系列重要的工作。目前，球堆积问题只解决了1维、2维、3维、8维和24维，其他维度的问题我们还知之甚少。另一位著名人物是大名鼎鼎的哲学家弗朗西斯·培根，他发明了培根密码。

第二个故事是一战期间的⻬默尔曼电报事件，它使得美国举国震怒，结束中⽴，最终加⼊到对德作战的⾏列中。第三个故事是我国的破译天才池步洲破译了⽇军偷袭珍珠港的密电。他破译了⽇本外务省与海军之间的密电，掌握了⼭本五⼗六视察部队的⾏程。最后介绍一个我国在抗战时期设计的密码——豪密，它是由周总理设计的，该密码直到国⺠党倒台也未被破译。

3

近代密码学

前面我们介绍的都属于古典密码学的范畴，和数学的联系较为松散。我们都知道香农是信息学之父，他发表了两篇具有划时代意义的论文：一篇是《通信的数学原理》，开启了信息论的研究；另一篇是于1948年发表的《保密系统的通信原理》，在密码中引入了统计学和信息论，使得密码学从一门艺术转变成了科学。

在《保密系统的通信原理》一文中，香农提出了对称密码设计的两个主要原则：扩散（Diffusion）和混淆（Confusion），扩散是指让明文和密文之间的关系变得复杂；混淆是指让密文和密钥之间的关系变得复杂。

此外，他还在该文中提出了“完善保密性”的概念，即“绝对安全”（Perfect Secrecy）或“信息论安全”。虽然一次一密（One-time pad）在理论上可以达到绝对安全，但在实际中，这非常低效，极为不实用。我们后面会接触到的流密码可以被看作一次一密的近似，它将周期足够大的伪随机序列作为密钥流。此外，简单地将“每次加密都更换一次密钥”当作一次一密是不正确的，因为一次一密要求每次使用的密钥也是随机的。

另一个概念是Kerckhoffs原则：密码系统仍应是安全的，即使系统（除密钥外）的所有内容都是公开的。即密码系统的安全性仅仅依赖于密钥（⽽不是算法）的保密性。这和香农提出的“敌⼈知道系统”是一脉相承的。

接下来看看对称密码的发展历程。现代密码学中有一个里程碑式的事件，即数据加密标准DES的提出，它是第⼀个标准化的加密算法，标志着密码从军事、外交领域⾛向民用。DES的算法流程如上右图所示，它是一个Feistel结构的算法，分组长度64比特、密钥长度64比特，其中8比特做校验位（因此密钥长度实际上是56比特）。

一般来说密钥长度越长，设计安全强度越高，所以DES的安全性相对来说并不高，这也是该算法被广为诟病的一点。虽然现在来看DES算法已经不安全，但是DES算法对于后续分组密码的设计和分析具有重要意义，比如对DES算法提出的线性分析和差分分析等已经成为了对称密码算法的标准分析方法。

再看看公钥密码的发展历程。在实际应用中，要解决的一个最大的问题是密钥分发和分配的问题，因为如果双方想要利用对称密码进行保密通信，他们就需要获得相同的密钥。另外一个问题是密钥管理，即，如果一个人想要和一方通信，那么他需要具有一个密钥，而如果他想要和其他方通信，那么他又要换一个密钥……由此可见，这个人需要保存很多密钥。

针对这些问题，Diffie和Hellman在1976年《密码学新方向》（New Directions in Cryptography）一文中提出了公钥密码的思想并提出了一个密钥交换协议，但是未给出公钥加密方案。提到公钥密码，不得不提的另一个人是Merkle，他利用Merkle Puzzles在Diffie和Hellman之前提出了一个较为低效的密钥交换协议，而Diffie和Hellman的密钥交换协议正是受到了这一启发而提出的。

随后，Rivest，Shamir和Adleman在1978年提出了广为人知的RSA加密方案，他们也因此获得了图灵奖。

以上就是公钥密码学在学术界诞生的历程。

此外，1977年，Malcolm Williamson和Hellman提出了背包加密体制，但其被证明是不安全的；根据后世的解密资料，早在1970年，英国GCHQ实验室的密码学家James Henry Ellis起草了一份《非秘密的数字加密的可能性研究》报告，被普遍认为是最早提出公钥加密思想的论文。

前面提到的故事可以从上面这两本非常有名的书中找到。近年来较为热门的量子密码实际是利用量子力学原理去做密钥分发。量子密码中最为主要的是BB84协议。

Shor提出了一种量子算法，利用量子傅里叶变换进行周期查找，导致经典设定中的困难问题在量子计算机下是多项式时间可解的，由此对基于整数分解和离散对数问题等设计的公钥密码体系造成了致命打击。

Grover搜索算法可以将经典状态下N/2的时间复杂度降低到根号N，将对称密码算法的安全强度降低了至少一半。后量子密码实际上是基于“量⼦困难”的数学难题（目前没有找到有效量子算法的问题）构建的密码，有基于格、多变量、编码、哈希、同源等，可以关注NIST发布的后量子密码标准。

4

我国密码的一些概况

我国密码实⾏分类管理。密码分为核⼼密码（核密）、普通密码（普密）和商⽤密码（商密）。核⼼密码、普通密码⽤于保护国家秘密信息。核⼼密码保护信息的最⾼密级为绝密级，普通密码保护信息的最⾼密级为机密级。国家秘密的密级分为绝密、机密、秘密级。商⽤密码⽤于保护不属于国家秘密的信息。

我国商⽤密码标准体系主要包括商⽤密码国家标准、⾏业标准。商⽤密码国家标准由国家标准化管理委员会（全国信息安全标准化技术委员会，信安标委）组织制定，代号为GB，如GB/T 32918（SM2）。商⽤密码⾏业标准由国家密码管理局（国密局）组织制定，报国家标准化管理委员会备案，代号为GM。

我国的商密算法有：SM1/2/3/4/7/9，ZUC。其中SM1/7算法不公开，是以IP核的形式提供，有需要可以调用；SM3是密码哈希函数；SM4（分组密码）和ZUC（流密码）是对称加密算法；SM2/9（都是基于椭圆曲线设计的）是公钥密码算法，提供了密钥封装、数字签名、公钥加密等功能。

“密评”是商⽤密码应⽤安全性评估的简称，在GB/T 39786的指导下进行的。关键信息基础设施、政务信息系统、等保三级以上信息系统建设，都要“过密评”。目前有一些第三方密评机构，具体名单可以去国家密码管理局网站搜索。

中国密码学会是成立于2007年的学术性组织，主办期刊《密码学报》。

此外，相关比赛、课程与培训、网站、工具、课后题网站有：

作者: 裴君翎

END

热文推荐