信号与编码原理（3）：密码术

随着人类社会越来越开放，个人和小集体的某些信息的保密也变得越来越重要。其实，密码术自古就有之，只是到了计算机出现以后，才发展成为了一门科学。自古以来，隐藏信息的方法可分为两种：一是隐藏信息的载体，如密写术、隐身术；二是对表示信息的信号进行变化，使它不为非授权者所理解。密码学研究的是第二种方式。

给定一段信息源X，可以看成是一段声音、一组图片、或者一篇文章数字化、编码后的一串0及1的序列；我们需要寻找一个数学变换E，把集合X中的每一个比特，变换到另一个集合Y中；为了被授权接受者所理解，必须要E是可逆的。但是，非授权者也能解出逆变换啊，这就要在变换E中设置某个“陷门”或称“密钥”的东西，只有知道了密钥，逆变换才能容易地算出。

密钥的设计有两种方式：一是固定密钥k (就是一个或者一组数)。把信源分成等长的字符（0，1）串，每一串叫做一条明文m；对m在k的参与下进行数学变换E(k, m)，所得结果就是密文c。二是随机密钥，它与信源X一样长；对每个比特（或每个段）逐次运算（比如模2相加）。这种密码是不可破的，只是密钥的生成、分配、管理很困难。

所谓破译密码，就是在未知密钥的情况下，利用所得到的密文，和其它一切有用的信息，去求出明文、甚至是密钥。人类语言具有一些重要特征，比如，每个字母、字符串出现的频率几乎是固定的；字母的连接方式也有规律可循。如果能从此猜出一些对应明文的话，从c = E(k, m)，如果知道加密算法E，理论上是完全可以解出k的。

那就只有隐藏加密算法了？其实人类能够想到的数学变换是有限的，解密者可以逐个去试，如果值得的话（有足够的资源和成比例的时间）。这就要求增加变换的计算复杂性：计算时间是多项式级，还是指数级的？可另一方面，为了授权用户的使用方便，算法又不能太复杂，计算上最好是线性的，最多也只能是多项式级的布尔函数。

1976年，Whitfield Diffie和 Martin Hellman还提出了公开密钥系统：加密算法E和密钥k都公开，而E(k, *) 的逆变换中，存在某个参数h（解密密钥），当h已知时，逆变换容易求出；当h未知时，逆变换则难于求出（计算量至少是非多项式级的）。现有几个典型的公钥算法是，RSA系统（MIT的三位教授Rivest, Shamir, Adleman在1978年提出），按照 c = m^k (mod n) 加密，n是一个有两个差异较大的质数的乘积；n和k都公开。解密则是m = c^h (mod n)；其中的h是同余式 kh = 1 (mod t(n)) 的解，t(n)是欧拉函数。为了算出h或者t(n)，只有依靠n的质因数分解；目前的算法都是指数级的。

其次是Merkle和Hellman在1978年提出的背包系统：基于一个模M的线性运算，1983年被Shamir破译。还有McEliece基于线性纠错码（Goppa码）构造的体系，至今未有有效的破译方法；可惜密钥太长，难于加密。再有Goldwasser和Micali在1982年提出的二次剩余系统，基于平方剩余的Jacobi符号按照模n (同上)进行加、解密运算；其安全性也是基于质因数分解的复杂性。

最复杂的算法究竟是什么？人们已知的数学变换都有哪些？为了运算的方便，我们只能使用整数，这就只有模运算。即使把明文再分组、使用矩阵、张量，把它编码，变换上使用多重复合函数，我们永远只能在有限域上进行有限次运算。函数列的构造只有幂、指数、及其反函数—对数；一旦有人发明出离散对数的有效算法，目前所有的密码体系都将一夕被破。

在序列密码体制中，完全随机的密钥是不破的，可也是没有大众用途的，除了绝密的间谍。在商用上，为了生成密钥，采用的都是伪随机数列。这通常是用一个k元函数f(x1, x2, …, xk)产生一个递推数列：an = f(a(n—1), …, a(n-k)).在模运算下，任何递推数列都是周期性的; 在GF（q）中，最大的周期是q^k。Solomon Wolf Golomb 对二元伪随机周期数列提出了三条公设：（1）在一个周期内，0与1的个数相差不超过1，（2）连续的1串或0串的个数与其长度l的2^l成反比，（3）自相关函数只取两个值：1或-1/p，p为周期。能满足这三个条件的数列是很少的：哪些函数f能行呢？这是一个难题。

您要不要来一试身手：构造一个新的变换E，并且给出它的逆变换？最近听说中国某位女士，在坐月子期间闲得慌，就随手把美国的一个什么编码系统给破解了，得到了700万元的奖金。再以前还听说过，中国某大学的一个数学教授，把美国的DES（数据加密标准）给破解了！其实，加密解密就是一个斗智斗勇的游戏；说不定您一时脑洞大开，那个“陷门”就露出来了。