暗号理論の問題
英字 文字を と数に対応させる。鍵を とするアフィン暗号
で暗号化された文字 ()を元に戻す復号関数を
の形で表すとき、整数の組 を求めよ。
この問題で使うもの
- アフィン暗号(説明と入口の問題)
この問題を解けるようになるまで(24 技能)
読み込み中…
右端(太枠)がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
アフィン暗号の復号関数 を使います。まず法 での の逆元を拡張ユークリッドの互除法で求めましょう。
ヒント 2
を逆にたどって となる整数 を見つけます。
ヒント 3
より 。あとは を展開し、定数項を 以上 以下に直します。
答えと解説
答えを見る
どこでつまずきましたか?(選ぶと、戻る場所を案内します)
解説を読む
方針 復号関数は である。まず の法 での逆元 を求める。
手順 1: の確認と互除法
より なので、逆元が存在する。
手順 2:互除法を逆にたどる
よって であり、 だから
(確認:)。
手順 3:復号関数を求める
を について解くと、 の両辺に を掛けて
より 。したがって
検算 (B)を暗号化すると 。 となり、元に戻る。
よって 。
別解
より 。 の を法とする逆元を求める。 なので 。したがって 。 なので 。よって 、すなわち 。
検算: のとき 、 なので に戻る。 のとき 、 なので に戻る。