正式定義（講義 p. 13）

想法：不再對每個字母用同一個位移，而是依一把重複使用的金鑰字串輪流使用不同的位移。

令 \(\alpha=\{\ct{a},\dots,\ct{z}\}\leftrightarrow\Zn{26}\)，\(\calM=\calC=\alpha^*\)，並固定正整數 \(n\)（金鑰長度上限）。 \[\calK=\{0,1,\dots,25\}^{\le n}=\Zn{26}\ \cup\ (\Zn{26})^2\ \cup\cdots\cup\ (\Zn{26})^n .\]

  • \(\KGen\)：從 \(\calK\) 均勻抽出 \(\sk\)。

  • \(\Enc(\sk,m)\)：拆 \(m=m_1\cdots m_\ell\) 與 \(\sk=\sk_1\cdots\sk_j\)；對 \(i\in[\ell]\) 令 \[c_i=m_i+\sk_{\,((i-1)\bmod j)+1}\pmod{26},\] 回傳 \(c=c_1\cdots c_\ell\)。

  • \(\Dec(\sk,c)\)：同樣拆解；對 \(i\in[\ell]\) 令 \(m_i=c_i-\sk_{\,((i-1)\bmod j)+1}\pmod{26}\)。

（Problem Set 3 允許假設 \(\sk\) 的長度恰為 \(n\)，即 \(\calK=(\Zn{26})^n\)。）

講義寫 \(c_i=m_i+\sk_{i\bmod j}\)。若 \(\sk\) 的下標從 \(1\) 開始，當 \(j\mid i\) 時 \(i\bmod j=0\) 會指到不存在的 \(\sk_0\)；正確的意思是「第 \(i\) 個字母用第 \(((i-1)\bmod j)+1\) 個金鑰字母」（或把金鑰下標改成從 \(0\) 開始：\(\sk_0,\dots,\sk_{j-1}\)，\(c_i=m_i+\sk_{(i-1)\bmod j}\)）。寫程式時請用 0 起始的下標。

討論：\(j\) 個交錯的 Caesar 密碼（講義 p. 14）

講義的例子 \(n=5\)、\(j=4\)、\(\ell=7\)：

金鑰長度 \(j=4\) 的 Vigenère 加密。位置 \(1,5,9,\dots\) 用 \(\sk_1\)，位置 \(2,6,10,\dots\) 用 \(\sk_2\)……：整段密文是四個「交錯」的 Caesar 密碼。

這個觀察（講義：「four ‘distinct’ Caesar ciphers」）就是全部破譯方法的基礎：只要知道 \(j\)，把密文依位置 \(\bmod j\) 分成 \(j\) 條子密文，每條都是普通的 Caesar，各自用頻率分析解決（§[sec:cryptanalysis]）。 攻擊成本是 \(26\cdot j\)，不是 \(26^j\)——金鑰可以被「分而治之」地逐段攻擊，這是金鑰空間大小不等於安全性的又一個例子。

金鑰空間大小。

\(\abs\calK=26+26^2+\cdots+26^n=\dfrac{26^{n+1}-26}{25}\ge26^n\)。例如 \(n=3\)：\(18{,}278\approx2^{14.2}\)；\(n=5\)：約 \(1.2\times10^7\approx2^{23.6}\)；\(n=10\)：約 \(2^{47}\)。 一個有趣的副作用：長度恰為 \(n\) 的金鑰佔了 \(\calK\) 的 \(26^n/\abs\calK\approx25/26\approx96\%\)，所以「從 \(\calK\) 均勻抽樣」幾乎總是抽到最長的金鑰——金鑰的長度並不均勻。

\(\sk=\ct{kcl}=(10,2,11)\)，\(m=\ct{kings college london}\)（空白不加密、不消耗金鑰）： \[\begin{array}{r*{5}{c}@{\quad}*{7}{c}@{\quad}*{6}{c}} m: & \ct{k}&\ct{i}&\ct{n}&\ct{g}&\ct{s} & \ct{c}&\ct{o}&\ct{l}&\ct{l}&\ct{e}&\ct{g}&\ct{e} & \ct{l}&\ct{o}&\ct{n}&\ct{d}&\ct{o}&\ct{n}\\ \sk: & \ct{k}&\ct{c}&\ct{l}&\ct{k}&\ct{c} & \ct{l}&\ct{k}&\ct{c}&\ct{l}&\ct{k}&\ct{c}&\ct{l} & \ct{k}&\ct{c}&\ct{l}&\ct{k}&\ct{c}&\ct{l}\\ c: & \ct{u}&\ct{k}&\ct{y}&\ct{q}&\ct{u} & \ct{n}&\ct{y}&\ct{n}&\ct{w}&\ct{o}&\ct{i}&\ct{p} & \ct{v}&\ct{q}&\ct{y}&\ct{n}&\ct{q}&\ct{y} \end{array}\] 例如第一個字母 \(\ct{k}+\ct{k}=10+10=20=\ct{u}\)，第四個 \(\ct{g}+\ct{k}=6+10=16=\ct{q}\)。 注意明文 變成 （不同位移），但第 1、4 個字母和第 13、16 個字母都用 \(\sk_1\)——週期性仍然存在。

討論：潛在弱點（講義 p. 15）

L4.6cmL9.8cm 弱點 & 說明
message, ciphertext pairs give information about \(\sk\) & 一對 \((m,c)\) 的第 \(i\) 個位置給出 \(\sk_{((i-1)\bmod j)+1}=c_i-m_i\)；只要已知明文長度 \(\ge j\)，整把金鑰就出來了。
harder frequency analysis & 同一個明文字母會依位置被送到 \(j\) 個不同的密文字母，整體頻率分布被「抹平」（重合指數下降）。但只要先找出 \(j\)（Kasiski 1863、Friedman 1920），分流之後每條子密文都是 Caesar。講義註腳：Babbage 早已知道，Kasiski 1863 明確發表。
(more fundamentally) deterministic encryption & 仍是確定性、無狀態。IND-EAV 的區分對只要長一點：\(m_0=\ct{a}^{n+1}\)、\(m_1=\ct{a}^n\ct{b}\)（位置 \(1\) 與 \(n+1\) 用同一個位移；Problem 1 (iii)）。

如果金鑰不重複——長度 \(j\ge\ell\)，而且只用一次——那麼 \(c_i=m_i+\sk_i\) 每個位置都用一個獨立均勻的位移，這正是 §[sec:perfect] 的完美保密方案（Vernam 式一次性密碼本的 \(\Zn{26}\) 版本）。 Vigenère 的一切弱點都來自「金鑰比訊息短，所以必須重複」。Shannon 的定理（§[sec:perfect]）會證明這不是巧合：想要完美保密，金鑰就必須至少和訊息一樣長。

  • 1553：Giovan Battista Bellaso 在《La cifra del Sig. Giovan Battista Bellaso》中描述了用關鍵字選取位移的多字母表密碼——也就是今天叫「Vigenère」的方案。

  • 1586：Blaise de Vigenère 的《Traicté des chiffres》提出的其實是更強的自動金鑰（autokey）密碼；19 世紀的作者張冠李戴，把 Bellaso 的方案冠上他的名字。Kahn 在《The Codebreakers》中為此抱不平。

  • 1854 前後：Charles Babbage 私下破解了 Vigenère（回應 Thwaites 的挑戰），但從未發表——一說是因為他在克里米亞戰爭期間為英國海軍擔任密碼顧問。

  • 1863：普魯士軍官 Friedrich W. Kasiski 出版《Die Geheimschriften und die Dechiffrir-Kunst》，第一次公開「找重複片段、取距離的公因數」求金鑰長度的方法（講義 p. 15 的註腳）。

  • 1868、1917：Lewis Carroll 在童書專欄稱它「不可破解」；《Scientific American》1917 年仍稱它「impossible of translation」——這時 Kasiski 的書已經出版 54 年。它的綽號 le chiffre indéchiffrable 的真正意思是「沒有人發表過破法」，而非「不存在破法」。

  • 1920/1922：William F. Friedman 的《The Index of Coincidence and Its Applications in Cryptography》（Riverbank 第 22 號出版品）給出統計方法求金鑰長度，被譽為密碼分析史上最重要的單篇著作。