Let \(\textsf{HISTORICAL-CIPHERS}=\{\text{Caesar},\ \text{monoalphabetic substitution},\ \text{Vigenère}\}\). In each question below you may assume \(\sk\) for Vigenère has length \(n\), a positive integer.

In this question we will examine ways in which historical examples of SKE fail to achieve security definitions demanded of contemporary cryptography without requiring sometimes tedious cryptanalysis.

題目的最後一句話就是講義 p. 18 的訊息：證明不安全只需要 Week 2 的定義，不需要頻率分析。 全題使用 \(\alpha=\{\ct{a},\dots,\ct{z}\}\leftrightarrow\Zn{26}\)，所有加法在 \(\Zn{26}\) 中進行。

(i) 以 SKE 框架定義三個密碼

For each cipher in HISTORICAL-CIPHERS define it in the framework of \(\mathrm{SKE}=(\KGen,\Enc,\Dec)\). In particular define the message, ciphertext and key spaces; \(\calM\), \(\calC\) and \(\calK\). Then define \(\Enc\) and \(\Dec\). (If the historical description does not specify \(\KGen\) you may assume a key is uniformly sampled from \(\calK\).)

三個密碼共用 \(\calM=\calC=\alpha^*\)（任意長度的字母串），\(\KGen\) 都是「從 \(\calK\) 均勻抽樣」。令 \(m=m_1\cdots m_\ell\)、\(c=c_1\cdots c_\ell\)。

L1.7cmL3.0cmL4.1cmL4.1cm & Caesar & 單字母替換 & Vigenère（長度 \(n\)）
\(\calK\) & \(\Zn{26}=\{0,\dots,25\}\) & \(\Perm(\alpha)\)（\(\alpha\) 上所有雙射） & \((\Zn{26})^n\)
\(\abs\calK\) & \(26\) & \(26!\approx2^{88.4}\) & \(26^n\)
\(\Enc(\sk,m)\) & \(c_i=m_i+\sk\) & \(c_i=\sk(m_i)\) & \(c_i=m_i+\sk_{((i-1)\bmod n)+1}\)
\(\Dec(\sk,c)\) & \(m_i=c_i-\sk\) & \(m_i=\sk^{-1}(c_i)\) & \(m_i=c_i-\sk_{((i-1)\bmod n)+1}\)
正確性 & \((m_i+\sk)-\sk=m_i\) & \(\sk^{-1}(\sk(m_i))=m_i\) & 同 Caesar，逐位置

每個方案都對 \(i\in[\ell]\) 逐字母運算，最後回傳 \(c=c_1\cdots c_\ell\)（或 \(m=m_1\cdots m_\ell\)）。 備註：

  • Caesar 是替換密碼的特例（位移是排列），也是 Vigenère 的特例（\(n=1\)）。

  • 若不假設 Vigenère 金鑰長度恰為 \(n\)，講義的定義是 \(\calK=\{0,\dots,25\}^{\le n}\)，\(\abs\calK=\sum_{i=1}^n26^i\)，\(\Enc\) 中的 \(n\) 換成實際長度 \(j=\abs\sk\)。

  • 三者都是確定性、無狀態的 SKE——這一點是 (iii) 的根源。

(ii) 用 \(\Enc(\sk,\cdot)\) 取回金鑰

For each cipher in HISTORICAL-CIPHERS describe how to recover \(\sk\) given access to \(\Enc(\sk,\cdot)\).

這是 Week 2 IND-CPA 模型中的「加密預言機」。每個密碼都只需要一次查詢：

查詢 \(m=\ct{a}\)（即 \(0\)），得 \(c=0+\sk=\sk\)。密文本身就是金鑰（以字母表示：\(c\) 是第 \(\sk\) 個字母）。任何單字母 \(m\) 也行：\(\sk=c-m\)。

查詢 \(m=\ct{abcdefghijklmnopqrstuvwxyz}\)（26 個字母各一次），得 \(c=\sk(\ct{a})\sk(\ct{b})\cdots\sk(\ct{z})\)——這正是金鑰兩列表的下列，整張排列表一次到手。若每次只能查一個字母，26 次查詢亦可。

查詢 \(m=\ct{a}^n\)（\(n\) 個 ），得 \(c_i=0+\sk_i=\sk_i\)，\(i=1,\dots,n\)，即 \(c=\sk\)。若不知道 \(n\)（只知上限），查詢 \(\ct{a}^{n}\) 後，\(c\) 會呈現週期 \(j=\abs\sk\) 的重複；取最短週期即得 \(\sk\)。

一般原則：對確定性的「加法型」密碼，加密單位元 \(0\) 就直接吐出金鑰；對「查表型」密碼，加密整張表的輸入就吐出整張表。

(iii) 一對 \(m_0,m_1\) 區分出 \(b\)

For each cipher in HISTORICAL-CIPHERS suppose \(\sk\) is chosen according to \(\KGen\) and \(b\in\{0,1\}\) is chosen uniformly. Give two messages \(m_0,m_1\in\calM\) of the same length such that if you are given \(c=\Enc(\sk,m_b)\) you can determine \(b\).

這是 Week 2 的 IND-EAV 遊戲（沒有預言機、只有一個挑戰密文）。想法：挑一個「有重複字母」與一個「沒有重複字母」的訊息，因為確定性的逐字母加密會保留「兩個位置的字母是否相同」——只要這兩個位置用的是同一個位移／同一張表。

Caesar 與單字母替換。

取 \(m_0=\ct{aa}\)、\(m_1=\ct{ab}\)。

  • 若 \(b=0\)：\(c=\Enc(\sk,\ct{aa})=(\sk(\ct{a}),\sk(\ct{a}))\)，兩個字母相同。

  • 若 \(b=1\)：\(c=(\sk(\ct{a}),\sk(\ct{b}))\)，因為 \(\sk\) 是單射且 \(\ct{a}\ne\ct{b}\)，兩個字母不同。

規則：\(c_1=c_2\) 則輸出 \(0\)，否則輸出 \(1\)。對每一把金鑰都正確，所以 \(\Pr[\text{猜對}]=1\)，優勢 \(\abs{\Pr[b'=b]-\tfrac12}=\tfrac12\)（最大值）。（對 Caesar，\(\sk(x)=x+\sk\) 也是單射，論證相同。）

Vigenère（金鑰長度 \(n\)）。

不再管用：位置 1、2 用不同的 \(\sk_1,\sk_2\)，\(c_1=c_2\) 與否取決於 \(\sk_1=\sk_2\) 與否，而非 \(b\)。要挑相距 \(n\) 的位置——它們用同一個 \(\sk_1\)： \[m_0=\ct{a}^{\,n+1}=\underbrace{\ct{a}\ct{a}\cdots\ct{a}}_{n+1},\qquad m_1=\ct{a}^{\,n}\ct{b}=\underbrace{\ct{a}\ct{a}\cdots\ct{a}}_{n}\ct{b}.\]

  • \(b=0\)：\(c_1=0+\sk_1\)，\(c_{n+1}=0+\sk_1\)，所以 \(c_1=c_{n+1}\)。

  • \(b=1\)：\(c_1=\sk_1\)，\(c_{n+1}=1+\sk_1\ne c_1\)。

規則：\(c_1=c_{n+1}\) 則輸出 \(0\)，否則 \(1\)；\(\Pr[\text{猜對}]=1\)，優勢 \(=\tfrac12\)。 若覺得 \(n+1\) 不夠對稱，也可取 \(m_0=\ct{a}^{2n}\)、\(m_1=\ct{a}^n\ct{b}^n\)：\(b=0\) 時 \(c\) 的前半等於後半，\(b=1\) 時每個位置都差 \(1\)。

若金鑰長度未知（\(\le n\)）。

令 \(L=\operatorname{lcm}(1,2,\dots,n)\)，取 \(m_0=\ct{a}^{L+1}\)、\(m_1=\ct{a}^L\ct{b}\)：不論實際長度 \(j\le n\) 為何，\(j\mid L\)，位置 \(1\) 與 \(L+1\) 都用 \(\sk_1\)，論證不變。

若 \(\abs{m_0}=\abs{m_1}=\ell\le n\)，Vigenère 每個位置用獨立均勻的 \(\sk_i\)、每個都只用一次——這正是 §[sec:perfect] 的 \(\Zn{26}\) 一次性方案，對長度 \(\le n\) 的單一訊息是完美保密的，任何 \(m_0,m_1\) 都無法區分。所以區分攻擊必須用到長度 \(>n\) 的訊息，讓金鑰被重用。這恰好說明：Vigenère 的弱點就是「金鑰重用」。

題目沒問、但值得注意：

這些攻擊都只需要一個密文、不需要任何計算假設、而且對 Week 2 的任何版本（IND-EAV、IND-CPA、IND-CCA）都成立——講義 p. 18 的第一點。

遇到「給出 \(m_0,m_1\) 區分確定性密碼」： (1) 找兩個位置 \(i\ne i'\)，它們在加密時用到同一份金鑰材料； (2) \(m_0\) 在這兩個位置放相同字母，\(m_1\) 放不同字母，其餘位置任意但相同； (3) 敵手看 \(c_i\overset?=c_{i'}\)。 對 Caesar／替換密碼，任意 \(i\ne i'\) 都行；對週期 \(j\) 的 Vigenère，取 \(i'=i+j\)；對 OTP，不存在這樣的 \(i,i'\)——這就是完美保密。