ヴィジュネル暗号

鍵語の各文字をずらし量として周期的に使い、 $c_{i} \equiv m_{i} + k_{i mod ℓ} (mod 26)$ で暗号化・復号でき、平文と暗号文の一部から鍵語を求められる

前提

合同式（数学A 整数の性質）

この技能までの道筋（17 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）

説明

ヴィジュネル暗号は、アルファベットを $0$ 〜 $25$ の数に置き換え、鍵語の文字が表す数だけ各文字をずらす暗号です。ずらし量には鍵語の文字を順に繰り返して使います。そのため、同じ平文の文字でも、位置によって違う暗号文の文字になります。この技能を身につけると、合同式の計算だけで暗号化と復号ができ、平文と暗号文の一部が分かっているときには鍵語も割り出せます。

なぜそうしてよいのか

まず文字を $A = 0, B = 1, \dots, Z = 25$ と数に置き換えます。 $26$ で割った余りで考えるので、 $Z$ の次は $A$ に戻ります。 $26$ を法とする合同式では、 $x$ を $x + k$ に移す操作は $0$ 〜 $25$ の並べ替えになります。 $x - k$ に移せば元に戻るからです。これは、すべての文字を同じ $k$ だけずらす暗号（シーザー暗号）にあたります。

ヴィジュネル暗号では、このずらし量を位置ごとに変えます。鍵語の長さを $ℓ$ とし、鍵語の文字を数にしたものを $k_{0}, k_{1}, \dots, k_{ℓ - 1}$ とします。平文の $i$ 文字目（ $i = 0, 1, 2, \dots$ と $0$ から数える）には、 $i$ を $ℓ$ で割った余りを番号とする鍵 $k_{i mod ℓ}$ を使います。式で書くと $c_{i} \equiv m_{i} + k_{i mod ℓ} (mod 26)$ です。位置 $i$ を $ℓ$ で割った余りで分類すると、同じ余りの位置どうしは、同じずらし量のシーザー暗号になっています。

合同式では差をとる計算もそのまま使えます。したがって、この式は $m_{i} \equiv c_{i} - k_{i mod ℓ}$ とも $k_{i mod ℓ} \equiv c_{i} - m_{i}$ とも書き換えられます。前者が復号の式です。後者からは、余りが $0, 1, \dots, ℓ - 1$ になる位置を $1$ つずつ含む $ℓ$ 文字分について、平文と暗号文の対応が分かれば鍵語がすべて決まることが分かります。

手順

文字を数に直す： $A = 0, B = 1, \dots, Z = 25$ とする。空白や記号は除き、文字だけに $i = 0, 1, 2, \dots$ と番号を振る
鍵語の文字も数にして $k_{0}, k_{1}, \dots, k_{ℓ - 1}$ とする。 $i$ 番目の文字に使う鍵は $k_{i mod ℓ}$
暗号化： $c_{i} \equiv m_{i} + k_{i mod ℓ} (mod 26)$ を計算し、 $0$ 〜 $25$ の数に直す
復号： $m_{i} \equiv c_{i} - k_{i mod ℓ} (mod 26)$ を計算する。負になったら $26$ を足して $0$ 〜 $25$ に直す
鍵語を求める：対応の分かる位置で $k_{i mod ℓ} \equiv c_{i} - m_{i} (mod 26)$ を計算し、余り $0, 1, \dots, ℓ - 1$ のすべてについて鍵をそろえる
最後に数を文字に戻す

例題

文字を $A = 0, B = 1, \dots, Z = 25$ と数に対応させる。長さ $3$ の鍵語でヴィジュネル暗号化した暗号文は $KXRKGI$ であり、平文の先頭 $3$ 文字は $ATT$ であることが分かっている。鍵語を数にしたもの $(k_{0}, k_{1}, k_{2})$ を求めよ。ただし各 $k_{j}$ は $0 \leq k_{j} \leq 25$ の整数とし、暗号化は $c_{i} \equiv m_{i} + k_{i mod 3} (mod 26)$ （ $i = 0, 1, 2, \dots$ ）で行われているとする。

例題の解答

【手順1】文字を数に直す。平文の先頭は $A, T, T$ なので、 $m_{0} = 0, m_{1} = 19, m_{2} = 19$ 。暗号文の先頭 $3$ 文字は $K, X, R$ なので、 $c_{0} = 10, c_{1} = 23, c_{2} = 17$ 。

【手順2】 $i = 0, 1, 2$ のとき $i mod 3 = i$ なので、使われた鍵はそれぞれ $k_{0}, k_{1}, k_{2}$ である。

【手順5】 $k_{i mod 3} \equiv c_{i} - m_{i} (mod 26)$ を計算する。
- $k_{0} \equiv 10 - 0 = 10$
- $k_{1} \equiv 23 - 19 = 4$
- $k_{2} \equiv 17 - 19 = - 2 \equiv - 2 + 26 = 24$

よって $(k_{0}, k_{1}, k_{2}) = (10, 4, 24)$ である。

【手順6】文字に戻すと、鍵語は $KEY$ である。

確認として、【手順4】で残りの文字を復号する。
- $c_{3} = 10$ には $k_{0}$ を使う： $m_{3} \equiv 10 - 10 = 0$ （ $A$ ）
- $c_{4} = 6$ には $k_{1}$ を使う： $m_{4} \equiv 6 - 4 = 2$ （ $C$ ）
- $c_{5} = 8$ には $k_{2}$ を使う： $m_{5} \equiv 8 - 24 = - 16 \equiv - 16 + 26 = 10$ （ $K$ ）

平文は $ATTACK$ となり、意味の通る文になる。

答え: $(10, 4, 24)$

よくある誤り

復号でも鍵を足してしまう誤り。例えば $c = 17, k = 24$ から $17 + 24 = 41 \equiv 15$ としてしまう。正しくは引き算で、 $m \equiv 17 - 24 = - 7 \equiv 19 (mod 26)$ である。
引き算の結果が負のまま止めてしまう誤り。例えば $k \equiv 17 - 19 = - 2$ のままでは、どの文字に対応するか読めない。正しくは $26$ を足して $0$ 〜 $25$ に直し、 $k = 24$ （ $Y$ ）とする。
位置を $1$ から数えたために鍵がずれる誤り。先頭の文字に $k_{1 mod 3} = k_{1}$ を使ってしまう。正しくは $i = 0$ から数え、先頭の文字には $k_{0}$ 、 $4$ 文字目（ $i = 3$ ）には $k_{3 mod 3} = k_{0}$ を使う。
問題で指定された対応 $A = 0, \dots, Z = 25$ に従わず、 $A = 1, B = 2, \dots$ と数えてしまう誤り。こうすると、鍵語の文字 $A$ （本来はずらし量 $0$ ）がずらし量 $1$ になり、鍵・平文・暗号文の数値がずれて、同じ鍵語でも別の暗号文ができてしまう。例えば $A = 0$ の対応では、鍵 $B$ で平文 $A$ を暗号化すると $c = 0 + 1 = 1$ で $B$ になる。ところが $A = 1$ の対応で同じ式を使うと $c = 1 + 2 = 3$ となり、 $C$ になってしまう。正しくは $A = 0$ から始め、 $26$ で割った余り $0$ 〜 $25$ と文字を $1$ 対 $1$ に対応させる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

難易度 3（期末試験の応用レベル）
英字 $26$ 文字を $A = 0, B = 1, \dots, Z = 25$ と数に対応させ、 $Z /26 Z$ の元とみなす。正の整数 $m$ と鍵 $K = (k_{0}, k_{1}, \dots, k_{m - 1}) \in (Z /26 Z)^{m}$ に対し、鍵の長さ $m$ のヴィジュネル暗号は、平文 $x_{0} x_{1} x_{2} \dots$ を
$y_{j} \equiv x_{j} + k_{j mod m} (mod 26) (j = 0, 1, 2, \dots)$
で暗号文 $y_{0} y_{1} y_{2} \dots$ に変換する（ $j mod m$ は $j$ を $m$ で割った余り）。鍵の成分はどれも $0$ から $25$ の任意の値をとってよいものとする。
いま、長さ $18$ の文字列全体の集合 $(Z /26 Z)^{18}$ 上で、まず鍵の長さ $6$ の鍵 $K = (k_{0}, \dots, k_{5})$ でヴィジュネル暗号化し、その結果をさらに鍵の長さ $9$ の鍵 $L = (l_{0}, \dots, l_{8})$ でヴィジュネル暗号化する二重暗号化を考える。鍵の組 $(K, L)$ は全部で $2 6^{15}$ 通りある。
鍵の組 $(K, L)$ をすべて動かしたとき、この二重暗号化によって得られる $(Z /26 Z)^{18}$ から $(Z /26 Z)^{18}$ への写像は何通りあるか。答えは $26$ の累乗の形で答えよ。