固定一把金鑰 \(\sk\) 之後，加密就是一個普通的數學函數。這一節複習函數的三個性質，並算一算「有多少個這樣的函數」——這是 Problem 1 的全部數學工具。
單射、滿射、雙射
一個 \(f\colon X\to Y\) 把每一個 \(x\in X\) 對應到恰好一個 \(y\in Y\)，記 \(f(x)=y\)。\(f(X)=\{f(x):x\in X\}\subseteq Y\) 稱為 \(f\) 的。
\(f\) 是：不同的輸入對應不同的輸出，即 \(f(x)=f(x')\Rightarrow x=x'\)（等價地 \(x\ne x'\Rightarrow f(x)\ne f(x')\)）。
\(f\) 是：每個 \(y\in Y\) 至少被一個 \(x\) 打到，即 \(f(X)=Y\)。
\(f\) 是：既單射又滿射；此時每個 \(y\) 恰有一個原像，反函數 \(f^{-1}\colon Y\to X\) 存在。
單射看輸入：不同輸入、不同輸出（箭頭不會合流）。滿射看輸出：每個輸出都有人指著。Problem 1 (ii) 會證明：單射 \(\Rightarrow\abs{Y}\ge\abs{X}\)，滿射 \(\Rightarrow\abs{X}\ge\abs{Y}\)，雙射 \(\Rightarrow\abs{X}=\abs{Y}\)（鴿籠原理）。
\(\Esk\) 與 \(\Dsk\)（講義 p. 10）
令 \(\calM=\{m_1,\dots,m_s\}\)、\(\calC=\{c_1,\dots,c_t\}\)，\(t\ge s\)，並固定 \(\sk\in\calK\)。寫 \(\Esk(\cdot)=\Enc(\sk,\cdot)\)、\(\Dsk(\cdot)=\Dec(\sk,\cdot)\)。依定義 \[\Esk\colon\calM\to\calC,\qquad \Dsk\colon\calC\to\calM\cup\{\bot\}.\] 講義註腳預告：Problem Set 2 會證明 \(\Esk\) 必須是單射，因此 \(t\ge s\) 是必要的（Problem 1 (v)）。此時正確性 \(\Dsk(\Esk(m))=m\) 說的是：\(\Dsk\) 是 \(\Esk\) 的左反函數——\(\Dsk\circ\Esk=\mathrm{id}_\calM\)。在像 \(\Esk(\calM)\) 之外，\(\Dsk\) 不受約束（可輸出 \(\bot\)）。
有多少個函數？（講義 p. 11）
設 \(\abs{X}=s\)、\(\abs{Y}=t\)。
\(X\to Y\) 的函數共有 \(t^s\) 個。
若 \(t\ge s\)，\(X\to Y\) 的單射共有 \(\displaystyle t(t-1)\cdots(t-s+1)=\frac{t!}{(t-s)!}=\binom{t}{s}\cdot s!\) 個；若 \(t<s\) 則一個也沒有。
若 \(t=s\)，單射即雙射，共有 \(s!\) 個。
Proof. (a) 依序決定 \(f(x_1),\dots,f(x_s)\)，每個有 \(t\) 種選擇且互不影響，乘法原理給出 \(t^s\)。 (b) 單射要求選過的值不能再選：\(f(x_1)\) 有 \(t\) 種，\(f(x_2)\) 有 \(t-1\) 種，…，\(f(x_s)\) 有 \(t-s+1\) 種。另一種算法：先選像集（\(s\) 個不同的 \(y\)，\(\binom{t}{s}\) 種），再決定 \(X\) 到像集的雙射（\(s!\) 種）。若 \(t<s\)，鴿籠原理說必有兩個輸入撞到同一輸出。 (c) 在 (b) 中代入 \(t=s\) 得 \(\binom{s}{s}\cdot s!=s!\)。 ◻
\(\calM=\{m_1,m_2,m_3\}\)、\(\calC=\{c_1,c_2,c_3,c_4\}\)：
函數個數 \(t^s=4^3=64\)；
單射個數 \(\binom{4}{3}\cdot3!=4\cdot6=24\)；
若去掉 \(c_4\) 使 \(t=s=3\)，單射就是雙射，共 \(3!=6\) 個。
所以在 64 個「可能的 \(\Esk\)」中，只有 24 個能讓解密無歧義；其餘 40 個都有兩個訊息撞到同一密文。
這個計數在密碼學裡的意義
一把金鑰 \(\sk\) 就是從「所有單射 \(\calM\to\calC\)」這個巨大集合中挑出一個 \(\Esk\)。從敵手的角度，知道「系統」（Kerckhoffs！）等於知道這個集合，不知道的只是「哪一個」。
單字母替換密碼（下週）：\(\calM=\calC=\{\mathrm a..\mathrm z\}\) 逐字母加密，\(\Esk\) 是 26 個字母的一個排列，\(\abs{\calK}=26!\approx2^{88.4}\)。暴力搜尋不可行——但它仍然會被頻率分析攻破。金鑰空間大只是必要條件，不是充分條件（Kerckhoffs 說的是「對所有攻擊」不可破譯）。
現代區塊加密（例如 AES-128）：\(\calM=\calC=\bits^{128}\)，每把金鑰決定一個 \(\bits^{128}\) 上的排列。所有排列有 \((2^{128})!\) 個，而金鑰只有 \(2^{128}\) 把——真實密碼只「覆蓋」了極小一部分排列。安全性的目標是：敵手分不出「AES 的某把金鑰」與「隨機挑的排列」（，之後幾週的主題）。
三個定義要能用符號寫、也要能用「箭頭圖」判斷。
計數公式 \(t^s\)、\(\binom{t}{s}s!=\frac{t!}{(t-s)!}\)、\(s!\) 及其推導（乘法原理、鴿籠）。
知道 \(\Dsk\) 是 \(\Esk\) 的左反函數，且只在像集上被正確性約束。