暗号理論の問題

難易度 4大学院入試の標準レベル大学数学暗号理論

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

ある暗号文について、平文の文字 $E$ が $M$ に、平文の文字 $G$ が $A$ に暗号化されていることがわかった。この暗号の復号関数を
$D (y) \equiv cy + d (mod 26), 0 \leq c \leq 25, 0 \leq d \leq 25$
の形に表すとき、整数の組 $(c, d)$ を求めよ。

この問題で使うもの

アフィン暗号（説明と入口の問題）
法 $m$ での逆元（拡張ユークリッドの互除法）（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

文字を数に直して、 $a$ と $b$ についての 2 つの合同式を立て、差をとって $b$ を消去しよう。

ヒント 2

$2 a \equiv 14 (mod 26)$ は $2$ で割れないので、 $a \equiv 7 (mod 13)$ と同値であることに注意する。 $0 \leq a \leq 25$ の候補は 2 つあり、 $a$ が $26$ と互いに素という条件で 1 つに絞れる。

ヒント 3

$a = 7$ , $b = 10$ となる。復号には $7$ の法 $26$ での逆元が必要で、 $7 \times 15 \equiv 1 (mod 26)$ である。

答えと解説

答えを見る

(15, 6)

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

解説を読む

$E = 4$ , $G = 6$ , $M = 12$ , $A = 0$ なので、条件は
$4 a + b \equiv 12, 6 a + b \equiv 0 (mod 26)$
である。

$a$ を求める 2 式の差をとると
$2 a \equiv - 12 \equiv 14 (mod 26)$
$2$ は法 $26$ で逆元をもたないので、そのまま割ることはできない。 $2 a - 14 = 26 k$ （ $k$ は整数）と書けるので、両辺を $2$ で割って $a - 7 = 13 k$ 、すなわち
$a \equiv 7 (mod 13)$
$0 \leq a \leq 25$ の範囲では $a = 7$ または $a = 20$ の 2 つの候補がある。 $a = 20$ は $g cd (20, 26) = 2$ で $26$ と互いに素でないから鍵になりえない。よって $a = 7$ 。

$b$ を求める $6 a + b \equiv 0$ より $b \equiv - 42 \equiv - 42 + 52 = 10 (mod 26)$ 。よって $b = 10$ 。
（確認： $4 \times 7 + 10 = 38 \equiv 12$ で $M$ 、 $6 \times 7 + 10 = 52 \equiv 0$ で $A$ となる。）

復号関数 $y \equiv 7 x + 10$ を $x$ について解く。 $7$ の法 $26$ での逆元は、 $7 \times 15 = 105 = 4 \times 26 + 1$ より $15$ である。よって
$x \equiv 15 (y - 10) = 15 y - 150 (mod 26)$
$- 150 + 6 \times 26 = 6$ なので
$D (y) \equiv 15 y + 6 (mod 26)$
（確認： $D (12) = 186 = 7 \times 26 + 4 \equiv 4$ で $E$ 、 $D (0) = 6$ で $G$ となる。）

したがって $(c, d) = (15, 6)$ 。

別解

E=4, M=12, G=6, A=0 なので $4 a + b \equiv 12$ , $6 a + b \equiv 0 (mod 26)$ 。辺々引くと $2 a \equiv - 12 \equiv 14 (mod 26)$ 、よって $a \equiv 7 (mod 13)$ 、 $0 \leq a \leq 25$ では $a = 7, 20$ 。 $a$ は 26 と互いに素でなければならず 20 は偶数なので不適、 $a = 7$ 。 $b \equiv 12 - 28 = - 16 \equiv 10$ 。確認: $6 \cdot 7 + 10 = 52 \equiv 0$ 。復号は $x \equiv 7^{- 1} (y - 10)$ 。 $7 \cdot 15 = 105 = 4 \cdot 26 + 1$ より $7^{- 1} \equiv 15$ 。 $c = 15$ 、 $d \equiv - 15 \cdot 10 = - 150 \equiv - 150 + 156 = 6$ 。よって $D (y) \equiv 15 y + 6$ 。検算: $D (12) = 180 + 6 = 186 = 7 \cdot 26 + 4 \equiv 4$ （M→E）、 $D (0) = 6$ （A→G）で一致。

この問題の確認

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

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

確認の方法について

間違いを報告する

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