實用密碼學工具——編碼與解碼

02-02

編碼(encode)和解碼(decode)是個相當廣泛的話題，因為它涉及到了計算機對信息處理的根本方式。

別看AlphaGo那麼牛，它根本不懂圍棋，它懂的是按照既定的程序把人類圍棋對局編碼成兩個卷積神經網路節點間的參數，以此作為評價系統，不斷左右手互搏，生成新的對局……

計算機並不懂信息的意義，對它來說，信息只有兩種：一種是最終可以通過電路撥動CPU裡面「微小開關」的信息，統稱程序；令一種則是程序處理的對象，工地上工人搬動的磚。這兩種信息都需要變成計算機可以處理的形式，也就是所謂的編碼。前者由CPU內的電路負責解碼，指揮CPU進行計算；後者則是由前者進行解碼、計算和再編碼。

我們最常用到的編碼(code)，是對基本字元的編碼，在計算機上當屬ASCII (American Standard Code for Information Interchange)，它包括了英文的26個字母的大小寫、十個阿拉伯數字和各種符號，還有一堆早期系統中用到的控制符號（題圖）。這套編碼作為絕大多數程序語言的默認支持的編碼，說它是互聯網的通用語言一點也不過分。

另一套對基本字元編碼則是大名鼎鼎的Morse code，它是有三種符號構成：dash、dot、space。其中dash、dot用來編碼字元，而space用來同步，用來區分單詞邊界、片語邊界。很難想像，這套編碼(code)的編碼(encode)和解碼(decode)工作竟然都是由人直接完成，而且在二十一世紀的今天，依然有人去訓練自己掌握腦內編碼和解碼Morse code的能力。

如果去掉space，Morse code其實是二進位的編碼，如果dot是0，dash是1，則Morse code的編碼空間是2^5，最多可以表示64種不同的符號；而實際上，Morse code只表示了36種不同的符號。這是由於Morse code是經過壓縮的編碼，很多符號並不需要5個二進位就能表示。

另一個比較有名的例子是Flag semaphore。想當年軍訓的時候，還專門學習過這個編碼。旗手左右手各有8個旗位，但又不能同一個旗位放兩個旗（默認動作外），一個動作即可以傳達C(8, 2)=28種不同的信息，加上默認動作和「錯誤/注意」這個需要搖動旗的動作，一共有30種動作。

除了基本字元外，我們還需要處理沒有編碼的二進位信息。一個典型的例子就是Email的附件。我們知道Email的傳輸協議SMTP早期是只有基本字元的純文本，而附件中可能包括未知編碼的內容。這類叫做binary-to-text encoding的編碼方式其實有很多。最常見的也就是Email使用的，是一種叫做MIMEs Base64的編碼，將8bit的位元組拼接起來，依次讀取其中的6-bit（2^6=64），從而編碼到64個基本字元。（參考RFC 1421 - Privacy Enhancement for Internet Electronic Mail: Part I: Message Encryption and Authentication Procedures）

類似地，還有BASE32、ASCII85等常用的binary-to-text encoding編碼，基本思想都是一樣的。

當然，現在的很多SMTP伺服器已經支持了RFC3030，可以直接傳二進位文件了。

密碼(cipher)也是一種編碼，但它相對於上面所說的這些編碼，其編碼的具體方式是對一部分人保密的。自然，需要解碼用密碼編碼過的密文，需要知道其具體的的編碼方式才行。

一類很早就有的密碼構建方式是對基本字元進行替換。最簡單而著名的當屬Caesar cipher，簡單地挪動一下字母表的開始位置，就能起到迷惑對方的目的。

ROT13演算法就是一種Caesar cipher的特例。因為英文的26個字母的緣故，ROT13得到的密文只需要再進行一次ROT13就可以得到明文，加密和解密的方式相同。

$ echo Hello, World! | tr A-Za-z N-ZA-Mn-za-mnUryyb, Jbeyq!n$ echo Uryyb, Jbeyq! | tr A-Za-z N-ZA-Mn-za-mnHello, World!n

然而，簡單的替換密碼只能迷惑人類。通過對一定量的密文中出現的字母頻率的分析，就可以反推出密碼。人類製造的複雜而最有名替換密碼，應當歸屬納粹德國Enigma。當年Alan Turing破解Enigma的故事已經被搬上了銀幕（《模仿遊戲》）。Enigma採用了多重替換密碼錶，隨輸入更改的密碼錶，可配置的密碼錶等多種手段，彌補了替換密碼容易被字母頻率分析的缺陷，將替換密碼幾乎用到了極致。（參考《模仿遊戲》中艾倫·圖靈是如何破譯英格瑪的？ - 電影）當然，在目前計算機的計算能力下，破解Enigma並不困難，比走圍棋要容易得多了。

所以說，密碼學真正意義上開始改變信息傳輸和儲存，是二戰以後的事情了。我們現在輕而易舉就能接觸到的工具，其安全性遠遠超過了二戰時期的工具。

編碼解碼的本質上是兩個空間的映射關係，映射前後的信息相同（無損，有損編碼則是看起來幾乎相同），只是包裝的格式不同。ASCII是將常用字元映射到大小為2^7的空間，flag semaphore是將26個字元與符號（重用一部分表示數字）映射到大小30的空間。base64是把2^8的序列拼接起來，按2^6取出後映射到大小為64的空間。而所有的替換密碼，其映射前後的空間大小都是相等的。為了避免被頻率分析，一個好的替換密碼，應該做到映射時每個元素映射到另一個元素的概率是相等的。Enigma有一個致命缺陷，就是它編碼的字元不會映射到自身，這個缺陷在破譯時被利用，大大降低了破譯難度。

P.S. 因為和大標題關係不大，這裡有意避開了結構化數據的編碼（序列號）和解碼（反序列化），日後有機會再談。

P.P.S. 嚴格地說，編碼和解碼前後的信息不一定是相同的，有時候編碼後信息會增加，解碼後會減少，因為我們需要一些額外的信息起到錯誤檢測、錯誤修復、混淆等作用；有時候編碼後的信息會減少，比較說音頻和視頻的有損壓縮方式，就是減少了一些對人耳、人眼來說不那麼有用的信息。所以這裡所說的信息相同，特指原始的、有用的信息。