密碼學是CTF中經常出現的題型，除了經典的各種加密之外，還時常會出現出題者自定義的加密法，要求攻擊者以各種方式來進行解密，因此通常在密碼學中，數學推導與邏輯是非常被強調的一個部分，此外，如何利用程式語言寫出合適且效率好的解密方法也是不可或缺，以下我們就來介紹密碼學的各種類型與解法吧!歡迎各位來訊說明或補充筆者不足的部分喔!😄

Encode or Encrypt?

一開始先來討論時常被一般大眾搞混的兩個詞彙，Encode(編碼)與Encrypt(加密)。Encode的內容單純，甚至一般被認為無安全性，主要是以各種定義的函數來對資料進行處理，諸如Ascii、Base64、Base58、UTF-8、Big5等，以數學上的定義來說，假設$f(x)$為編碼函數，那麼利用其之反函數$f^{-1}(x)$對已編碼資料進行處理，便能回到原先的資料型態，無須多餘處理。

而Encrypt的內容相對複雜一些，單純使用反函數的概念是無法將加密資料返回原先狀態的，需要經過一些額外的處理與變換，有時利用正面的方法是無法解決的，需要旁敲側擊，其中又分為古典密碼(Classical Cipher)與現代密碼(Modern Cipher)，根據不同的演算法又存在不同的處理方式，以下將逐一介紹。

Encode

Encode的方式千奇百怪，尤其是因為只要符合反函數定義者都能被廣義的稱為編碼，因此自定義的編碼也不在少數。以下會介紹幾個最為常見的編碼模式。

Morse Code

摩斯密碼，是一種時通時斷的訊號代碼，通過不同的排列順序來表達不同的英文字母、數字和標點符號。由美國發明家薩繆爾·摩斯及其助手艾爾菲德·維爾在2009年發明，也是經常在談論密碼學時提及的古典密碼經典。詳情可參見此頁面

透過以上這張對應表，能夠從文檔或音檔中獲取到對方所欲傳達的訊息。當然，現今也有發展出對應的工具來處理這方面的解碼(Decode)。

Decode Tools

CyberChef：幾乎可以解出所有密碼(前提為條件足夠)
morse-sound-receiver：可處理音檔摩斯密碼

Base-X

Base編碼基於各種不同的編碼字元數與字元，能夠產生出各種不同的加密形式。最常見的型態為Base64，它基於64個可列印字元來表示二進位資料($2^6=64$，$6$ $bit$)，一個ASCII字元為8bit，由最小公倍數得，3個文字能夠被Base64轉換成4個字元，範例如下：

Base64在進行轉換時，由上面所述，資料字元數須為三的倍數，不足三位以0x0補足。接著根據二進位值一一取出6bit，並從64個字元中找出其對應字元，直到所有資料轉換完成。若資料位數為$3n+2,n\in N$，會在轉換資料後補上==；若資料位數為$3n+1,n\in N$，則會在轉換資料後補上=。

輕鬆一下：Base1024會是以🥳等表情符號作為編碼喔!

Decode Tools

CyberChef
base-x：能夠處理各種base為基底的加解碼(包含自訂字元)

當然，我們也能夠透過Python來處理這方面的解碼工作，如下所示：

import base64
raw = "M3t30r loves cryptography."
data = base64.b64encode(raw) # encode
assert raw == base64.b64decode(data) # decode
chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" # Base64 64bit string

uuencode

uuencode採用的方法基本上與Base64相同，在分為三位元的資料轉換為6bit一組時，每組的10進位資料會落於0～63之間，此時將所有資料加上32之後，剛好會落在ASCII可列印的字元範圍，以此做為資料輸出。如下例所示：

Tips：uuencode辨識方法為特殊字元非常多(因範圍為32至95，多為特殊字元)

Decode Tools

xxencode

基本上與Base64相同，但使用的轉換字元串不同，它使用的是+-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz，且資料位數不足時補的是+，其餘皆同。

Decode Tools

base-x

URL Encode

通常會在瀏覽器中使用，基於一些保留字元會有相異的解讀，會先將每個字元轉換為2位16進位表示值後(以UTF-8標準)，再在前方加入%符號作為URL統一標準，稱為URL encode。

Decode Tools

URL Encoder/Decoder

BrainFuck

Brainfuck是一種極小化的程式語言，由Urban Müller在1993年創造。其目標是建立一種簡單的、可以用最小的編譯器來實現的、符合圖靈完全思想的程式語言。這個語言由八種運算子構成，它的名字也意味著想要直接讀懂它是極度困難的，即使它是一個圖靈完備的語言。八種運算子意義如下所示：

但在同時也有些題目會將其他語言的程式包裝成BrainFuck來讓解題者解，因此將它歸類在此處，通常只要編譯它產生輸出即可。

Compile Tools

Brainfuck Compiler

JSFuck

JSFuck是一種深奧的JavaScript程式設計風格，靈感來自於BrainFuck，使用六種字元完成程式。基本上不需要另外的編譯器或直譯器來執行，無論瀏覽器或JavaScript引擎中的原生JavaScript直譯器皆可直接執行。鑑於JavaScript是弱型別語言，編寫者可以用數量有限的字元重寫JavaScript中的所有功能，且可以用這種方式執行任何類型的表達式。詳見此頁面

Compile Tools

基本上不需要，瀏覽器的Console即可執行。

aaencode/jjencode

這兩種encode都是針對JavaScript的轉換方式，與JSFuck相近。aaencode會將JavaScript轉換為表情符號，而jjencode會將它轉換成類似 $_$ 等風格的字串。兩者皆可轉為JavaScript，但JavaScript無法轉回。

Compile Tools

統整

編碼的內容其實五花八門，要完全認識世界上每一種編碼幾乎是不可能的，但比賽時只要能夠有通靈+查詢能力就不太需要擔心解不出來囉～

Classical Cipher

進入了古典密碼學的部分，就必須談到密碼學的兩大分類：對稱式加密(Symmetric Encryption)與非對稱式加密(Asymmetric Encryption)。對稱式加密意味著在加密與解密時所使用的密鑰(key)完全相同，無須經過任何轉換即可用以解密。

而非對稱式加密則是分為公鑰(public key)與私鑰(private key)，加密者使用公鑰加密後，傳遞到另一方必須以私鑰才能解密，且有一個重要前提：私鑰可以推導出公鑰，但公鑰推導出私鑰極度困難。古典密碼的部分大多為對稱式加密，以下舉出常見的幾個密碼。

Caesar Cipher

凱撒密碼利用了線性映射(linear transformation)的原理，是一種替換加密技術，明文中的所有字母都在字母表上向後或向前，依照一個固定數目(offset)進行偏移後被替換成密文。這個加密方法是以羅馬共和時期凱撒大帝的名字命名的，據稱當年凱撒曾用此方法與其將軍們進行聯繫。現代的ROT13也以凱撒密碼作為實作基礎。

以下為凱撒密碼以數學式表示的加解密方法，$x$為資料內容，$n$為偏移量(offset)：

$E_n(x)=(x+n)$ $mod$ $26$
$D_n(x)=(x-n)$ $mod$ $26$

攻擊手法

暴力窮舉(brute force)

基於英文子母僅有26個字元，利用0~25間的offset必定存在正確解密結果。

詞頻分析(word frequency analysis)

利用對字元出現頻率的分析，找出解密最符合正常語言的文本。

攻擊工具

dcode.fr：可爆搜所有可能offset
CyberChef：ROT13可作為Caesar Cipher解密工具
quipqiup：強力詞頻分析工具

Python實作

def enc(raw, offset): # encode
    data = "".join([chr((ord(i)-65+offset)%26+65) for i in raw])
    return data

def dec(raw, offset): # decode
    data = "".join([chr((ord(i)-65-offset)%26+65) for i in raw])
    return data

raw = input().upper() # raw
offset = int(input()) # offset
print(enc(raw, offset))
print(dec(raw, offset))

Vigenère Cipher

維吉尼亞密碼基本上可以視為凱撒密碼的加強版，凱撒密碼使用單獨offset對明文進行加密，而維吉尼亞用來加密的key則是一個字串，利用加上每個字的offset來對字進行加密，若是key的長度小於明文則重複使用直到加密完成，稱為金鑰流。本質上也能被視為是一種替換式密碼(Substitution Cipher)，如下表所示。

攻擊手法

卡西斯基試驗(Kasiski examination)

這是第一個被提出破解維吉尼亞的方法，早期的解決方案都是透過對於明文的認識、或者使用可識別的詞語作為密鑰，但卡西斯基試驗不需要任何限制。基本的概念如下：

卡西斯基試驗是基於常用單詞，如the、some等，有可能被同樣的密鑰字母進行加密，而在密文中重複出現相同子字串。此時便能以重複出現長度之因數推測出密鑰可能的長度，而若有多個此類子字串，則能夠以最小公因數獲得密鑰的長度。通常文本越長的資料越容易被卡西斯基試驗攻破(越容易重複使用密鑰加密相同字串)。

弗里德曼試驗(Friedman examination)

弗里德曼試驗於1920年代發明，這項試驗使用了重合指數(index of coincidence)來描述密文字母頻率的不勻性，從而破譯密碼。

$\kappa_p$指目標語言中兩個任意字母相同的概率(英文為$0.067$)，$\kappa_r$指字母表中這種情況出現的概率(英文中為$\frac{1}{26}=0.0385$)，根據弗里德曼試驗推導出的結果，密鑰長度可以被認定為$\frac{\kappa_p-\kappa_r}{\kappa_0-\kappa_r}$，$\kappa_0=\frac{\sum\limits_{i=1}^c{n_i(n_i-1)}}{N(N-1)}$，$c$是指字母表的長度(英文為$26$)，$N$指文本的長度，$n_1$到$n_c$是指密文的字母頻率，為整數。而這樣的試驗會隨著文本長度的增加而更為精確。

頻率分析

一旦能夠確定密鑰的長度，密文就能重新寫成多列，列數與密鑰長度對應。這樣每一列其實就是一個凱撒密碼，而此密碼的密鑰(偏移量)則對應於維吉尼亞密碼密鑰的相應字母。與破譯凱撒密碼類似的方法，就能將密文破譯。

維吉尼亞密碼事實上還有許多種變體，但也隨著時間漸漸被破譯了，這裡就不再贅述。

攻擊工具

CyberChef
cryptii：正規維吉尼亞密碼處理器
vigenere-solver：個人認為頗為強力的維吉尼亞密碼破譯工具

Python實作

def enc(raw, key):
    key_length = len(key)
    key_as_int = [ord(i) for i in key]
    raw_int = [ord(i) for i in raw]
    data = ''
    for i in range(len(raw_int)):
        value = (raw_int[i] + key_as_int[i % key_length]) % 26
        data += chr(value + 65)
    return data


def dec(raw, key):
    key_length = len(key)
    key_as_int = [ord(i) for i in key]
    raw_int = [ord(i) for i in raw]
    data = ''
    for i in range(len(raw)):
        value = (raw_int[i] - key_as_int[i % key_length]) % 26
        data += chr(value + 65)
    return data

raw = input().upper() # raw
key = input().upper() # key
print(enc(raw, key))
print(dec(raw, key))

Rail Fence Cipher

鐵路柵欄密碼是一種經典的換位密碼。它的名字來自其加密的執行方式，類似於用水平欄杆建造的柵欄。如下所示：

plaintext = "M3t30r loves cryptography" (空白忽略)
Rails = 4

Rail 1： M.....l.....r.....r....
Rail 2： .3...r.o...c.y...g.a...
Rail 3： ..t.0...v.s...p.o...p.y
Rail 4： ...3.....e.....t.....h.

ciphertext = "Mlrr 3rocyga t0vspopy 3eth"

攻擊手法

只要知道柵欄的數目便能輕鬆解密原先內容(僅為換位)

攻擊工具

dcode.fr：可協助暴力搜尋柵欄數目

Bacon Cipher

培根密碼是由法蘭西斯·培根發明的一種隱寫術。加密時，明文中的每個字母都會轉換成一組五個英文字母。其轉換依靠下表，本質上是利用A、B取代index二進位中的0、1：

攻擊工具

dcode.fr

Pigpen Cipher

豬圈密碼基本上是一種以格子為基礎的簡易替換密碼，對應的圖示如下所示：

攻擊手法

只要依據圖示逆回明文即可，十分簡單暴力

Affine Cipher

仿射密碼是將明文中字母對應成數字後，進行運算加密再對應回密文的一種模式，基本上運算式如下：

$E_n(x)=ax+b$ $mod$ $m$
$D_n(x)=a^{-1}(x-b)$ $mod$ $m$，$a^{-1}=invese(a)$(僅在$(a,m)=1$時存在)

而這種加密的轉換方式同樣被使用於線性同餘方法(LCG)，為偽隨機數生成器中的一種，稍後的文章中會提及它的攻擊手法，這裡就先稍稍帶過。

攻擊手法

若可發現加密文件兩字元之原文，則關鍵值可透過解一方程組得到(二元一次方程組)。由於我們知道$a$及$m$互質，這個事實可被用於快速破解密碼。

Others

對稱式加密的種類包羅萬象，未提及的還有包含Playfair Cipher、Dancing man、Braille等(詭異)的加密方法，但基本上在CTF競賽中通常都會出現代密碼，畢竟解密的步驟較為複雜，有時甚至需要跳脫性的思考，因此會考的古典密碼幾乎不存在，或是會出成很冷門的通靈題，出現的話通常靠的不會是大量的知識點，而是搜尋與通靈的能力，讀者若有興趣能夠自行再參閱相關的文章喔!