形式上只是集合

定義裡的「空間」在數學上就是集合（set）：一堆沒有重複的東西。貓的照片、位元字串、一顆超新星——什麼都可以（講義 p. 8）。這種抽象有好處（定理對任何集合都成立），但常常不夠具體。密碼學裡，這些集合幾乎總是某個字母表上的字串。

字母表、字串與 Kleene 星號

一個 \(\alpha\) 是一個有限非空集合，其元素稱為。對 \(n\in\N=\{0,1,2,\dots\}\)：

  • \(\alpha^n\) 是所有長度為 \(n\) 的符號序列（字串）所成的集合；\(\abs{\alpha^n}=\abs{\alpha}^n\)。

  • \(\alpha^0=\{\varepsilon\}\)，其中 \(\varepsilon\) 是（長度 0 的字串，恰有一個）。

  • ：\(\alpha^*=\bigcup_{i\in\N}\alpha^i\)，所有有限長度字串的集合（包含 \(\varepsilon\)）。它是可數無限集合。

\[\alpha^0=\{\varepsilon\},\quad \alpha^1=\{0,1\},\quad \alpha^2=\{00,01,10,11\},\quad \alpha^3=\{000,\dots,111\},\quad \alpha^*=\bigcup_{i\in\N}\alpha^i .\] \(\alpha^1\) 的元素是一個位元（bit）；\(\alpha^n\) 有 \(2^n\) 個元素，所以「\(n\) 位元金鑰」的金鑰空間大小是 \(2^n\)——這是為什麼 128 位元金鑰的暴力搜尋需要約 \(2^{128}\approx3.4\times10^{38}\) 次嘗試。

歷史密碼通常使用傳統意義下的字母表。常把字母編碼為數字 \(\mathrm{a}=0,\mathrm{b}=1,\dots,\mathrm{z}=25\)，於是字母運算變成 \(\Z_{26}=\{0,\dots,25\}\) 上的模 26 算術——Problem 2 的 Caesar 密碼 \(c_i=m_i+\sk \bmod 26\) 正是如此。\(\abs{\alpha^n}=26^n\)；\(26!\approx4.0\times10^{26}\approx2^{88.4}\) 是「26 個字母的全部排列數」，下週單字母替換密碼會用到。

講義要你記住的兩個常見設定（講義 p. 9）

令 \(\alpha_\calK,\alpha_\calM,\alpha_\calC\) 分別是金鑰、訊息、密文空間的字母表。

L3.2cmL5.4cmL6.2cm 設定 & 空間 & 典型例子
歷史密碼 & \(\alpha_\calK=\alpha_\calM=\alpha_\calC=\{\mathrm{a},\dots,\mathrm{z}\}\)；\(\calK=\alpha_\calK^{\,n}\)（固定長度金鑰），\(\calM=\alpha_\calM^*\)、\(\calC=\alpha_\calC^*\)（任意長度） & Caesar（\(n=1\)，金鑰是一個位移量）、Vigenère（\(n\) 個字母的關鍵字）、單字母替換（金鑰是一個排列）
現代密碼 & \(\alpha_\calK=\alpha_\calM=\bits\)，\(\alpha_\calC=\bits^{\ell}\)；\(\calK=\bits^n\)，\(\calM=\bits^*\)，\(\calC=(\bits^{\ell})^*\) & 區塊加密模式：金鑰 \(n=128\) 或 \(256\) 位元，密文由 \(\ell=128\) 位元的區塊串成；AES-GCM、ChaCha20-Poly1305

兩個觀察：

  • 金鑰空間 \(\calK=\alpha^n\) 是固定長度、有限的，大小 \(\abs{\alpha}^n\)；訊息與密文空間則是 \(\alpha^*\)，無限。因此「暴力搜尋金鑰」在原則上總是可行（有限），只是可能不可行（太大）——Problem 2 (ii) 討論何時連這都不夠。

  • 現代設定裡密文字母表是 \(\bits^{\ell}\) 而非 \(\bits\)，表示密文以「區塊」為單位；密文長度是區塊長度的倍數，這會透露訊息長度的粗略資訊——這就是為什麼 IND 遊戲要求 \(\abs{m_0}=\abs{m_1}\)（§[sec:ind]）。

  • \(\abs{\bits^{128}}=2^{128}\)；\(\abs{\{\mathrm a..\mathrm z\}^{5}}=26^5=11{,}881{,}376\)。

  • \(\abs{\alpha^{\le n}}=\sum_{i=0}^{n}\abs{\alpha}^i=\dfrac{\abs{\alpha}^{n+1}-1}{\abs{\alpha}-1}\)（長度不超過 \(n\) 的字串數）。

  • \(\alpha^*\) 無限但可數（把字串依長度、再依字典序排成一列）。