信號與編碼原理（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（數據加密標準）給破解了！其實，加密解密就是一個鬥智鬥勇的遊戲；說不定您一時腦洞大開，那個“陷門”就露出來了。