暗号理論の問題

難易度 2教科書の演習問題レベル大学数学暗号理論

英字 $26$ 文字を $A = 0, B = 1, \dots, Z = 25$ と数に対応させる。整数の組 $(a, b)$ を鍵とするアフィン暗号
$E (x) \equiv a x + b (mod 26) (0 \leq E (x) \leq 25)$
で 1 文字ずつ暗号化する。ただし $a, b$ は $0 \leq a \leq 25, 0 \leq b \leq 25$ を満たす整数で、 $g cd (a, 26) = 1$ とする。

このような鍵 $(a, b)$ のうち、暗号化を 2 回続けて行うと必ず元の文字に戻る、すなわち $0 \leq x \leq 25$ を満たすすべての整数 $x$ について
$E (E (x)) \equiv x (mod 26)$
が成り立つ鍵（暗号化と復号が同じ写像になる鍵）は何個あるか。ただし $E$ が恒等写像になる鍵 $(a, b) = (1, 0)$ も数に含める。

この問題で使うもの

アフィン暗号（説明と入口の問題）
合同式（説明と入口の問題）

この問題を解けるようになるまで（24 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$E (E (x))$ を $x$ の 1 次式として書き、すべての $x$ で $x$ と合同になる条件を係数で表しましょう。

ヒント 2

$E (E (x)) \equiv a^{2} x + (a + 1) b$ より、条件は $a^{2} \equiv 1$ かつ $(a + 1) b \equiv 0 (mod 26)$ です。 $a^{2} \equiv 1 (mod 26)$ は法 $2$ と法 $13$ に分けて考えます。

ヒント 3

$a^{2} \equiv 1 (mod 26)$ を満たす $a$ は $a = 1$ と $a = 25$ の 2 つです。それぞれについて $(a + 1) b \equiv 0 (mod 26)$ を満たす $b$ の個数を数えましょう。

答えと解説

答えを見る

28

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

$E (E (x))$ を計算すると
$E (E (x)) \equiv a (a x + b) + b = a^{2} x + (a + 1) b (mod 26)$
となる。

条件の書き換え すべての $x$ について $a^{2} x + (a + 1) b \equiv x (mod 26)$ が成り立つための条件を求める。 $x = 0$ を代入すると $(a + 1) b \equiv 0$ 、 $x = 1$ を代入すると $a^{2} + (a + 1) b \equiv 1$ となり、これらから $a^{2} \equiv 1$ が得られる。逆に $a^{2} \equiv 1$ かつ $(a + 1) b \equiv 0 (mod 26)$ ならば、すべての $x$ で $a^{2} x + (a + 1) b \equiv x$ が成り立つ。よって求める条件は
$a^{2} \equiv 1 (mod 26), (a + 1) b \equiv 0 (mod 26)$
である。

$a$ の決定 $26 = 2 \cdot 13$ なので、 $a^{2} \equiv 1 (mod 26)$ は $a^{2} \equiv 1 (mod 2)$ かつ $a^{2} \equiv 1 (mod 13)$ と同値である（中国剰余定理）。
- $mod 2$ ： $a$ は奇数。
- $mod 13$ ： $(a - 1) (a + 1) \equiv 0$ で $13$ は素数なので、 $a \equiv 1$ または $a \equiv 12 (mod 13)$ 。

$0 \leq a \leq 25$ で $a \equiv 1 (mod 13)$ となるのは $1, 14$ で、奇数は $a = 1$ 。 $a \equiv 12 (mod 13)$ となるのは $12, 25$ で、奇数は $a = 25$ 。どちらも $g cd (a, 26) = 1$ を満たす。確認すると $2 5^{2} = 625 = 24 \cdot 26 + 1$ である。

$b$ の決定
- $a = 1$ のとき： $2 b \equiv 0 (mod 26)$ 、すなわち $b \equiv 0 (mod 13)$ 。よって $b = 0, 13$ の $2$ 個。
- $a = 25$ のとき： $(a + 1) b = 26 b \equiv 0 (mod 26)$ は常に成り立つので、 $b = 0, 1, \dots, 25$ の $26$ 個。

したがって条件を満たす鍵の個数は
$2 + 26 = 28$
である。

別解

$E (E (x)) = a (a x + b) + b = a^{2} x + ab + b (mod 26)$ 。これがすべての $x$ で $x$ と合同になる条件は、 $x = 0$ から $ab + b \equiv 0$ 、 $x = 1$ から $a^{2} \equiv 1 (mod 26)$ 。逆にこの2条件があれば十分である。

$a^{2} \equiv 1 (mod 26)$ は $mod 2$ と $mod 13$ に分けて考える。 $g cd (a, 26) = 1$ より $a$ は奇数で、 $mod 2$ では常に成り立つ。 $mod 13$ では $a \equiv \pm 1$ 。よって $a \equiv 1$ または $a \equiv 12 (mod 13)$ で $a$ が奇数なので、 $a = 1$ または $a = 25$ 。

(i) $a = 1$ : 条件は $2 b \equiv 0 (mod 26)$ 、すなわち $b \equiv 0 (mod 13)$ 。 $b = 0, 13$ の2個。

(ii) $a = 25 \equiv - 1$ : $ab + b = - b + b = 0$ なので $b$ は任意。 $b = 0, \dots, 25$ の26個。

合計 $2 + 26 = 28$ 個。

検算: $a = 1, b = 13$ のとき $E (E (x)) = x + 26 \equiv x$ で成立。 $a = 25$ のとき $E (E (x)) = 25 (25 x + b) + b = 625 x + 26 b$ 。 $625 = 24 \cdot 26 + 1$ なので $\equiv x$ で成立。 $a = 1, b = 1$ のとき $x + 2 \neq \equiv x$ で不成立。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる