アフィン暗号

$E (x) \equiv a x + b (mod 26)$ で文字を暗号化し、 $a^{- 1}$ を使って復号関数 $D (y) \equiv a^{- 1} (y - b) (mod 26)$ を $cy + d$ の形で求められる。平文と暗号文の文字の組 2 つから連立合同式を解いて鍵 $(a, b)$ を決定できる

前提

法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

約数の見つけ方（算数整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
ユークリッドの互除法（数学A 整数の性質）
1 次不定方程式の整数解（数学A 整数の性質）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）

説明

アフィン暗号は、アルファベットを $A = 0, B = 1, \dots, Z = 25$ と数に置き換え、鍵 $(a, b)$ を使って $E (x) \equiv a x + b (mod 26)$ で文字を別の文字に移す暗号です。この技能を身につけると、文字を暗号化できるようになります。また、法 26 での逆元 $a^{- 1}$ を使って、復号関数を $D (y) \equiv cy + d (mod 26)$ の形で書けるようになります。さらに、平文と暗号文の対応が 2 組わかっていれば、連立合同式を解いて鍵 $(a, b)$ を割り出せます。ただし、2 つの平文の文字の番号の差が 13 のとき（たとえば $A$ と $N$ ）は、2 組だけでは鍵が 1 つに決まりません。そのときは別の組がもう 1 つ必要です。

なぜそうしてよいのか

暗号化の式 $y \equiv a x + b (mod 26)$ を $x$ について解けば、復号ができます。まず両辺から $b$ を引くと $y - b \equiv a x$ となります。 $g cd (a, 26) = 1$ なら、拡張ユークリッドの互除法で $a a^{- 1} \equiv 1 (mod 26)$ を満たす整数 $a^{- 1}$ が見つかります。両辺に $a^{- 1}$ を掛けると
$x \equiv a^{- 1} (y - b) \equiv a^{- 1} y + (- a^{- 1} b) (mod 26)$
です。したがって $c \equiv a^{- 1}$ 、 $d \equiv - a^{- 1} b$ とおけば、復号関数も 1 次式 $cy + d$ の形になります。 $g cd (a, 26) \neq = 1$ 、つまり $a$ が偶数か 13 の倍数のときは、異なる文字が同じ文字に移ってしまいます。たとえば $a = 2$ なら $2 \cdot 13 = 26 \equiv 0$ なので、 $E (x)$ と $E (x + 13)$ が一致します。これでは復号できません。そのため $a$ として使えるのは、 $1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25$ の 12 通りだけです。

鍵を決めるときは、2 組の対応 $x_{1} \to y_{1}$ 、 $x_{2} \to y_{2}$ （ $x_{1} \neq \equiv x_{2}$ ）を使います。ここから $y_{1} \equiv a x_{1} + b$ と $y_{2} \equiv a x_{2} + b$ が得られます。辺々引くと $b$ が消えて、 $a$ だけの 1 次合同式 $a (x_{1} - x_{2}) \equiv y_{1} - y_{2} (mod 26)$ になります。この式の解き方は $g = g cd (x_{1} - x_{2}, 26)$ で変わり、 $g$ は 1, 2, 13 のどれかです。
- $g = 1$ のとき: $x_{1} - x_{2}$ の逆元を掛ければ、 $a$ がただ 1 つに決まります。
- $g = 2$ のとき: 1 次不定方程式と同じように両辺と法を 2 で割ると、法 13 の合同式になり、法 26 では候補が $a_{0}$ と $a_{0} + 13$ の 2 つ残ります。13 は奇数なので、この 2 つは偶奇が異なります。そこで奇数のほうを選びます。
- $g = 13$ のとき: $a$ が奇数なら $13 a \equiv 13 (mod 26)$ なので、左辺 $13 a$ は奇数の $a$ すべてで同じ値になります。つまりこの式からは $a$ が絞れません。

$a$ が決まれば、 $b \equiv y_{1} - a x_{1}$ で $b$ も決まります。

手順

文字を数に直す: $A = 0, B = 1, \dots, Z = 25$ とする。
鍵 $a$ が使えるか確かめる: $g cd (a, 26) = 1$ 、つまり $a$ が奇数で 13 でないことを確認する。
暗号化する: 平文の数 $x$ ごとに $y \equiv a x + b (mod 26)$ を計算し、 $0 \leq y \leq 25$ に直してから文字に戻す。
復号関数を作る: 互除法で $a^{- 1} mod 26$ を求める。 $c \equiv a^{- 1}$ 、 $d \equiv - a^{- 1} b (mod 26)$ をそれぞれ 0 以上 25 以下に直し、 $D (y) \equiv cy + d$ とする。
鍵を決める（対応が 2 組わかっているとき）: $a (x_{1} - x_{2}) \equiv y_{1} - y_{2} (mod 26)$ をつくり、 $g = g cd (x_{1} - x_{2}, 26)$ で場合分けする。(i) $g = 1$ : $a \equiv (x_{1} - x_{2})^{- 1} (y_{1} - y_{2})$ とただ 1 つに決まる。(ii) $g = 2$ : $y_{1} - y_{2}$ が奇数なら解はない。偶数なら両辺と法を 2 で割って法 13 で解き、候補 $a_{0}, a_{0} + 13$ のうち $g cd (a, 26) = 1$ を満たすもの（奇数のほう）を選ぶ。(iii) $g = 13$ （例: $A$ と $N$ ）: $y_{1} - y_{2} \equiv 13$ なら 12 通りの $a$ がすべて条件を満たすので、2 組では決まらない。別の平文・暗号文の組を使う。 $y_{1} - y_{2} \neq \equiv 13$ なら解はない。どの場合も、解がない、または $g cd (a, 26) = 1$ を満たす候補が残らないときは、与えられた対応がアフィン暗号として不整合である。
$b$ を求める: 決まった $a$ を使って $b \equiv y_{1} - a x_{1} (mod 26)$ を計算し、0 以上 25 以下に直す。

例題

文字を $A = 0, B = 1, \dots, Z = 25$ と対応させ、アフィン暗号 $E (x) \equiv 7 x + 3 (mod 26)$ で暗号化する。復号関数を $D (y) \equiv cy + d (mod 26)$ （ $0 \leq c \leq 25$ , $0 \leq d \leq 25$ ）の形で表すとき、組 $(c, d)$ を求めよ。

例題の解答

【手順 2】 $g cd (7, 26) = 1$ なので、 $7^{- 1} mod 26$ が存在する。したがって復号できる。

【手順 4】まず互除法で $7^{- 1}$ を求める。
$26 = 3 \cdot 7 + 5$ 、 $7 = 1 \cdot 5 + 2$ 、 $5 = 2 \cdot 2 + 1$
これを下から逆にたどると、
$1 = 5 - 2 \cdot 2 = 5 - 2 (7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3 (26 - 3 \cdot 7) - 2 \cdot 7 = 3 \cdot 26 - 11 \cdot 7$
となる。よって $7^{- 1} \equiv - 11 \equiv 15 (mod 26)$ である。確かめると、 $7 \cdot 15 = 105 = 4 \cdot 26 + 1$ で正しい。

次に $y \equiv 7 x + 3$ を $x$ について解く。両辺から 3 を引いて $15$ を掛けると、 $x \equiv 15 (y - 3) = 15 y - 45 (mod 26)$ となる。 $- 45 + 52 = 7$ だから、 $x \equiv 15 y + 7 (mod 26)$ である。よって $c = 15$ 、 $d = 7$ 。

検算: $H = 7$ を暗号化すると $E (7) = 52 \equiv 0$ で $A$ になる。これを復号すると $D (0) = 7$ となり、 $H$ に戻る。

答え: $(15, 7)$

よくある誤り

復号を「 $a^{- 1}$ を掛けてから $b$ を引く」と考え、 $D (y) \equiv a^{- 1} y - b$ としてしまう誤り。例: $E (x) \equiv 7 x + 3$ で $D (y) \equiv 15 y - 3 \equiv 15 y + 23$ とする。正しくは先に $b$ を引いてから $a^{- 1}$ を掛けるので、 $d \equiv - a^{- 1} b = - 15 \cdot 3 \equiv 7$ となり、 $D (y) \equiv 15 y + 7$ である。
$g cd (a, 26) \neq = 1$ の $a$ でも鍵に使えると思ってしまう誤り。例: $E (x) \equiv 2 x + 1$ では $E (0) = 1$ 、 $E (13) = 27 \equiv 1$ となり、 $A$ と $N$ が同じ文字に移るので復号できない。正しくは、 $a$ は 26 と互いに素な 12 通りに限られる。
鍵の決定で、 $x_{1} - x_{2}$ が 26 と互いに素でないのに、ふつうの割り算をしてしまう誤り。例: $2 a \equiv 6 (mod 26)$ から「 $a \equiv 3$ だけ」と結論する。正しくは $2 a - 6 = 26 k$ より $a - 3 = 13 k$ 、つまり $a \equiv 3 (mod 13)$ なので、法 26 では $a = 3, 16$ の 2 通りが候補になる。このうち $g cd (a, 26) = 1$ を満たす $a = 3$ を選ぶ。補足: $x_{1} - x_{2}$ が 13 の倍数のときは、候補を絞ることすらできない。例として $A (0) \to D (3)$ 、 $N (13) \to Q (16)$ では $13 a \equiv - 13 \equiv 13 (mod 26)$ となり、奇数の $a$ がすべてこれを満たす。このように 12 通りの $a$ が残るので、別の平文・暗号文の組がもう 1 つ必要になる。
逆元を分数 $\frac{1}{a}$ と考えたり、 $- 11$ や $- 45$ のような負の値を $0 \sim 25$ に直さずに文字に戻したりしてしまう誤り。正しくは、 $7^{- 1}$ は $7 c \equiv 1 (mod 26)$ を満たす整数 $c = 15$ のことである。また、計算結果は 26 の倍数を足したり引いたりして $0 \leq y \leq 25$ に直してから文字に対応させる（例: $- 45 \equiv 7$ ）。

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

アフィン暗号

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題