Categories
All 密碼學 技術

密碼學(1):古典密碼

前言:一點廢話

程序猿的博客好像都是用來寫技術文的,只有我一直在鍵政,所以心血來潮想寫技術文試一試。我對 WordPress 加上目前正在使用的前端主體的表現并沒有信心,像代碼高亮之類的操作也無法處理的很好,所以準備先談談比較理論少代碼的密碼學這個主題,這也是個人比較有興趣的一個領域。

古典密碼(Classical cipher),顧名思義,就是歷史上曾使用的一些加密方式,大多已不再使用。不過介紹它們有助於我們瞭解密碼學的發展歷史以及認識一些基本的加密思路。古典密碼主要有替換式密碼和移項式密碼兩大類。

替換式密碼

替換式密碼(Substitution ciphers),意指明文中的内容通過字母或字母群被系統性地替換爲其他内容,形成密文。

凱撒密碼

凱撒密碼(Caesar cipher)是最爲人熟知的一種替換式密碼,最早出現在 Gallic wars 中用於軍事目的。它還有另一個名字叫 Caesar shift,意思就很明顯了——通過移位(shift)來達成替換的目的。比如一串明文”ABC”,用”D”替代”A”、”E”替代”B”、”F”替代”C”,則會得到密文”DEF”,我們可以理解為,明文「右」移了三位得到了密文。

多説無益,直接看一個例子:

Plain: I like zttofficial
Cipher: L olnh cwwriilfldo

原文中的每個字母都向右移動了三位,從而產生了密文,替換過程遵循下表:

基於此,我們可以用數學方式表達明文與密文之間的關係:

C = E(k, p) = (p + k) mod 26
p = D(k, C) = (C - k) mod 26

凱撒密碼總共只有25種移位方法,很容易通過暴力(Brute Force)破解,簡簡單單枚舉所有可能的情況便能得到明文。

單表加密

單表加密(monoalphabetic cipher)嚴格定義上是凱撒密碼的母集,即凱撒密碼也是單表加密的一種。不過此處語境下的單表加密,是指對凱撒密碼的一種改良方式,它對整個明文進行替換,而不是替換逐個字母,這意味著單表加密需要一個與明文相同長度的密鑰。

Plain: if we wish to replace letters
Key: dkvqfibjwpescxhtmyauolrgznwi
Cipher: wi rf rwaj uh yftsdvf sfuufya

雖然排列組合的可能性變得非常多,但仍然是風險很高的一種加密方式,因爲在自然語言中一些詞的頻率必然會高於另外的詞,可以通過頻率分析(frequency analysis)進行破解。

維吉尼亞密碼

相較之下,維吉尼亞密碼(Vigenère Cipher)則是多表加密(polyalphabetic cipher)的一個典型例子,可以視之為多個凱撒密碼的組合,以下這個被稱爲維吉尼亞方格的表格被應用在這種加密方法中:

此處簡單引用一下維基中使用到的例子:

Plain: I LOVE CRYPTOGRAPHY
Key: W ORDW ORDWORDWORDW
Cipher: E ZFYA QIBLHFJNOGKU

波雷費密碼

波雷費密碼(Playfair cipher)是最爲著名的一種多字母加密方法。它將明文視爲單個整體的單元放在一幅圖中,并將整個單元轉換爲密文圖,此處的「圖」通常是指一個5×5的矩陣。

選擇密鑰之後,將密鑰的字母逐個填入該5×5的矩陣內,字母不能重複,若遇重複則跳過。填完密鑰之後講剩餘的英文字母依順序填入,因爲一共只有25個空間,一般會將Q去除或將I和J視作同一字(例子使用後者)。

加密時,應該把所有字母分爲兩個一組,如果最後有一個字母落單,則添上X作爲搭配。然後按以下規則,尋找每兩個字母對應的密文以實現加密:

  1. 如果兩個字母并非同行同列,將四個字母組成矩形,取明文對角處的字母作爲密文。
  2. 如果兩個字母在同一橫列,取這兩個字母右方的字母(若字母在最右方則取最左方的字母)。
  3. 如果兩個字母在同一直行,取這兩個字母下方的字母(若字母在最下方則取最上方的字母)。

現在假設明文是”Nice to meet you”,首先兩兩分組,得到”NI CE TO ME ET YO UX”。假設用 Monarchy 一詞作爲密鑰,按上述規則填入:

我們就能得到密文:AGELPRCLKLHNVZ。

移項式密碼

移項式密碼不改變明文本身,而是依照某種規則改變明文中的排列。

中國式密碼

中國式密碼(Chinese cipher)的規則是將明文按從右往左、上下交替寫出一段新的字母排列。例如明文是:THE DOG RAN FAR,則按此規則可以寫為:

 R R G T
 A A O H  
 F N D E  

密文則按照慣用的從左往右、從上往下的閲讀順序寫作:RRGT AAOH FNDE。

下一篇:密碼學(2): Modern Block Ciphers