密码算法

    陈道蓄

    

    

    

    自从人类进入阶级社会以来，军事与政治斗争催生了保密通信。对需要传递的信息加密，即使信件落入敌方手中，其内容也無法被理解。现在，随着网络渗透到每个普通人生活的方方面面，信息安全成了全社会的“刚性”需求。使用互联网的每个普通人恐怕每天都得有几次需要输入密码的时候，其实只要你在网上使用信息服务，不管你是否知道，总有加密解密算法在无声地为你服务，包括你进入各种服务的登录信息，往往也会被加密，避免他人很容易得到你的个人身份信息。

    凯撒密码

    一般教科书上都会将古罗马时代的凯撒密码称为我们能够确知的第一种密码系统。这种密码非常简单。

    假设我们通信时只使用26个英文字母（不区分大小写），加上空格符号，我们的“字母表”总共有27个符号。英文字母是有确定次序的，我们分别用0到25表示字母表中相应的字母，并令空格符的编号为26。

    凯撒密码的“密码机”如图1所示。大小不一的两个同心圆周上依次分布着26个字母。内圈的小圆盘可以旋转，如当前位置状态下小圆上的字母A对应大圆上的字母S，B对应T，以此类推。（注意：图中未包含空格符，但读者很容易理解，这个“密码机”工作原理不依赖于具体符号内容）

    我们将明文中的符号（小圆）替换为对应符号（大圆）即可得到密文。根据图1中标示的编号，如果用c（x），p（x）表示密文与明文中分别使用的符号在字母表中序号，则加密过程可以用以下公式表示：c（x）=p（x）+18 mod 26。这里使用模算术，即结果为简单加法和对26取余数，保证不会出现“字母表溢出”。

    18即在字母表中的“位移量”（大小两个圆对应字母在字母表中的距离），因此凯撒密码是一种简单位移码，这个例子中“密钥”是18，解码时只要按照公式p（x）=c（x）-18 mod 26即可。这个过程很简单，下面直接给出相应的Python代码段（如下页图2）。

    函数encode_decode既用于编码也用于解码。这里采用的“密钥”是5，并限定使用的字母表只包含小写英文字母、十进数字、最基本的标点符号以及空格符，一共40个。利用上述编码方式，报文“we will arrive at railway station 3 pm tomorrow afternoon.”将被加密为“1je1nqqefwwn0jefyewfnq1f3exyfyntse8eureytrtwwt1efkyjwsttsb”。

    由于凯撒密码中可选的密钥不大于字母表的长度（长了没意义），所以在计算机时代通过穷举法即刻可以破解。即使使用人工方法，这个密码也不难破解。注意，上述过程中空格符也同样移位，如果空格符不处理，那手工破解这样的密文只能作为小学生智力测试的题目。读者不妨自己编写一个程序破解凯撒密码。

    如果不是使用一个固定的移位量，显然可以使破解的难度增大。考虑不用一个数字做密钥，而是选择一个英语单词做密钥，如“algorithm”。这个单词由9个字符构成，用它们在英文字母表中的序号（从0开始）作为相应的“移位量”，则分别是“0，11，6，14，17，8，19，7，12”。现在加密是依次轮流使用这9个不同的位移量值，这只需对密钥字长度取模即可。读者很容易修改前面的过程，实现多位移量加密。即使是使用多位移量，密钥不是太长时，计算机仍然很容易破解。

    置换码

    显然，如果不是采用固定的“移位方式”，而是定义一个字母表上的一一对应的映射，由于长度为n的字母表中字母可能的排列方式有n！种，采用字母表上的置换方式定义密钥比凯撒密码安全得多，至少人工破解非常困难了。

    我们用随机方式生成字母表的任意一种排列。这样的排列共有n！种，尽管我们知道现在的计算机中不可能产生真正意义上的“随机”，但下面的算法可以保证得到任意一种排列的概率是相同的（如图3）。

    因为Python中的string不支持内容的修改，所以需要将原字母表转为list。新的排列相当于在字母表上定义了一个一一对应的函数，这就是“密钥”。读者应该很容易实现相应的加密与解密算法。

    表面上看n！虽然对计算机而言也是巨大的数，用穷尽方法破解很不现实，但自然语言中字符出现的频度有明显差异，只要积累足够的密文，通过频度分析就能找到解密的突破口。

    转置码

    小朋友可能玩过一种游戏。在一张硬纸板上画出包含4k个小方格的方阵，将其中k个挖空。将硬纸板放置在白纸上，如果挖的位置适当，可以按照特定方向旋转90度的方式依次在挖空位置上写字而不重叠。总共写完4k个字后就形成了含4k个字的密文。挖空的位置就相当于“密钥”。图4中是仅含16个空格的简单例子：利用左边的“密钥”，以逆时针方向旋转对中间的“明文”加密得到右侧的密文。（这里为了简单只用16个位置）

    这种加密方法与前面介绍的移位码与置换码不同。字母表中每个字符在密文中的对应字符不由字符本身决定，而是取决于该字符在原文中出现的位置（不是字母表中的位置）以及加密时采用的位置对应关系。这个例子中用的纸板上挖孔的方式当然不适合计算机实现（但让计算机帮我们决定合适的挖空位置是一个很好的编程练习）。计算机中基于同样思想的方法称为“转置码”。注意这种方法与字母表的字符表示无关。

    转置码的基本原理可以描述如下：假设明文包含n个字符。先确定一个“行宽”值，假设为w。可以理解明文是按行书写的。加密时通过转置使得原来的“行”变成“列”，但密文仍旧按照按行输出形式生成。如图5所示，左边为明文，右边为密文。

    这里假设密钥m=9（行宽），整个明文长度未必是m的整数倍，最后空格可以用任意字符填满至行宽。（为什么填任何字符都可以？）

    其实在计算机中并不需要“行列”的概念，只需适当控制输入与输出中字符相应index的关系就可以了。具体说，把左边的明文编码为右边的密文，明文中index从0开始顺序递增，右边密文中字符的index依次是km+i，其中m是密钥，k从0开始，每“行”加1，i=0，1，2，…，m。

    为了提高安全性，可以在应用转置码时除m外再加一个密钥，它可以是一个长度为m的字符串，如“algorithm”，按照英文字母表排序作為该字符串内元素序号，“algorithm”将对应（1，5，2，7，8，4，9，3，6）， 编码是用此序列作为“列”的顺序。见图5最右边。

    编码算法过程的Python实现如下页图6所示，读者可类似地自行实现解码过程。

    公钥密码与RSA算法

    前面提到转置码虽然可能的密钥数量巨大，但通过字符频度分析容易找到破解的入口。频度分析依赖样本数量，如果经常换密钥，显然安全性会提高。极端地说，如果每个密钥只用一次，可以认为这样的密码是无法破解的。

    可是，我们前面介绍的方法加密与解密必须使用相同的密钥，这称为“对称”密码。通信双方必须保有相同的密钥，经常更换代价很高。读者一定看过影视剧中关于传递“密码本”的情节，代价往往是牺牲许多人的生命。

    20世纪70年代以前人们一直确信对称对于加密和解密是铁定的规则。非对称密码的出现是一次重大的突破。相关的学者有5人为此得到计算机领域最高奖“图灵奖”。

    在讨论密码通信时，我们常用两个假想的人物Alice和Bob表示发件人和收件人。我们可以用一个形象的比喻解释“非对称”的含义。如果Bob在公众场所放置了多个信箱，上面挂了锁，但并不锁上，只有Bob本人有信箱的钥匙。当Alice打算发一封密信给Bob时，她只要将信放入Bob的信箱，随即将锁锁上（当然她自己也无法将信取出来了）。Bob只需用自己的钥匙开锁就可以拿到密信。

    基于非对称的思想可以开发“公钥”密码。密钥被分为两部分，Alice用Bob公开的密钥（称为公钥）对报文加密，但解密需要的部分（称为私钥）只有Bob本人掌控。计算机实现时，不是像前面那些方法那样逐个字符转换。我们将整个报文看作一个数（计算机中任意的字符串总可以看作一个二进制数），当然可能是非常大的数。我们需要的是一对函数与相应的反函数，其中一个方向计算容易，但逆运算却非常困难。

    这原理说起来似乎不难理解，但要在思想上突破传统观念的约束并能真正找到可行的实现方法是非常困难的。文献[1]有关于这段历史的详细描述。

    本文不打算涉及太多的相关数学概念，我们下面仅通过一个简化的例子描述公钥密码的使用过程。我们在算法园地栏目前面的文章中介绍过两个很大的整数相乘的算法，在计算机上很容易实现。反之，如果我们知道的是两个很大的质数的乘积，要想通过分解知道原来两个乘数究竟是什么就非常困难了。当数字很大时，现在的计算机也无法在可以容忍的时间内算出结果。这里强调“两个质数”的乘积，就是避免包含很小的因子，为分解提供突破口。

    公钥密码使用的RSA算法选择密钥的过程可简述如下：

    1.随机选择两个不同的大质数p，q，如1000位以上的。

    2.计算：n=p×q。

    3.计算 m=（p-1）×（q-1），选一个较小的奇数e，与m互质。

    4.计算d，满足ed=1（mod m）。

    5.将e，n公布，作为公钥;安全保存d，作为私钥。

    Alice将明文M加密为密文C，并将C发给Bob，按如下方式计算（前面说了，M可以看作一个数字）：

    P（M）=Me（mod n）， 这里只需要公钥，P是加密函数

    Bob将密文C还原为明文M，按如下方式计算：

    S（C）=Cd（mod n）， 可以证明：Cd=Med（mod n）

    为便于读者理解，这里举一个很小的例子。

    假设Alice要发给Bob的明文M=“88”：

    1.Bob已经选择两个质数11，17， 乘积为187;并选择了小奇数7（与160互质）。Bob将187和7公布，作为公钥;并计算出d=23，满足23×7=1（mod 160=（11-1）×（17-1）），23作为密钥保存。

    2.Alice将88加密为C=887（mod 187）=11，并发给Bob。

    3.Bob利用私钥23解密：原文=C23（mod 187）=1123（mod 187）=88

    这里会用到几个乘幂计算与质数算法，感兴趣的读者可参阅文献[2]，那里也给出了上述例子中用到的公式的正确性证明。

    本文开始时提到互联网的广泛应用使得每个普通人日常都需要使用加密解密功能，如果没有公钥密码，每个人去维护对称密钥是完全不可能的。但一方面，公钥密码并不能替代对称密码，因为更高要求的信息安全度公钥密码并不能保证满足，另一方面，从上面的介绍中大家也能看出它需要的计算量很大，效率受到影响。现在的对称密码的设计复杂度远不是我们前面介绍的那些方法可比的。密码涉及非常深的数学概念，尽管现在有关密码的书可谓“汗牛充栋”，但一般读者能理解的并不多。文献[3]介绍了用Python语言实现一些简单密码方法，不仅介绍加密解密，还介绍了一些破解密码的“黑客”算法。这本书对密码与Python程序设计的要求都是“零基础”，所以很适合中小学生用于课外活动。

    参考文献：

    [1]Simon Singh.The Code Book：the Secret History of Codes and Codebreaking， Fourth Estate，1999，中译本——码书：编码与解码的战争[M].南昌：江西人民出版社，2018.

    [2]Thomas Cormen， etc.： Introduction to Algorithms， 3rd ed.， MIT Press， 2009， 中译本——算法导论[M].北京：机械工业出版社，2012.

    [3]Al Sweigart： Cracking Codes with Python： An Introduction to Building and Breaking Cyphers， No Starch Press， 2018.

    注：作者系南京大学软件学院原院长，计算机系原系主任。