暗号理論の問題
英字 文字を と数に対応させます。整数 (、)を鍵とするアフィン暗号
で、1 文字ずつ暗号化します。暗号文の文字は、 を 以上 以下の整数で表したものです。
この暗号で、平文の文字 は に、平文の文字 は に暗号化されました。鍵 を求めてください。
この問題で使うもの
- アフィン暗号(説明と入口の問題)
この問題を解けるようになるまで(24 技能)
読み込み中…
右端(太枠)がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
アフィン暗号の「平文と暗号文の組 2 つから鍵を決める」方法を使います。文字を数に直し、 についての連立合同式をつくりましょう。
ヒント 2
と を引き算して を消すと、 の形になります。 を拡張ユークリッドの互除法で求めましょう。
ヒント 3
引き算すると となり、 なので です。両辺に を掛けて を求め、それを に代入して を求めます。
答えと解説
答えを見る
どこでつまずきましたか?(選ぶと、戻る場所を案内します)
解説を読む
手順 1:文字を数に直して連立合同式をつくる
です。 より、次の 2 つの式が成り立ちます。
手順 2: を消去する
より
手順 3: を求める
なので、 には法 での逆元があります。互除法を行うと
となります。これを逆にたどると
となります。よって であり、 です(確認:)。
手順 4: を求める
手順 2 の式の両辺に を掛けると
となります。 より です。 なので、鍵の条件も満たしています。
手順 5: を求める
に を代入すると
となり、 より です。
確認
- なので になります。
- なので になります。
どちらも条件と一致します。
よって、鍵は です。
別解
E=4, W=22, T=19, F=5 なので、、。
辺々を引くと 。
で、 より 。よって 。 なので鍵として適する。
。
検算: (W)、(F)で一致する。
したがって 。