アフィン暗号

説明

中東で生まれた古代の暗号システムであるアフィン暗号を実装します。

アフィン暗号は、単一換字式暗号の一種です。 各文字は数値に置き換えられ、数学的な関数で暗号化されたあと、その新しい数値に対応する文字に変換されます。 単一換字式暗号はどれも弱いですが、アフィン暗号はアトバシュ暗号よりもはるかに強力です。鍵の数がはるかに多いからです。

暗号化

暗号化の関数は次のとおりです。

E(x) = (ai + b) mod m

それぞれの意味は次のとおりです。

• iは文字のインデックスで、0からアルファベットの長さ-1までの値です。
• mはアルファベットの長さです。 ラテンアルファベットでは、mは26です。
• aとbは整数で、暗号化の鍵を構成します。

自動で復号できるようにするには、aとmが_互いに素_（coprime、relatively prime）である必要があります。つまり、共通の約数が1だけであるということです（詳しくは互いに素な整数に関するWikipediaの記事を参照してください）。 aがmと互いに素でない場合、プログラムはそれをエラーとして示す必要があります。 そうでなければ、与えられた鍵で暗号化または復号します。

この演習では、数字は有効な入力ですが、暗号化されません。 空白と句読点は除外されます。 暗号文は、固定長のグループに分けて、空白で区切って書きます。伝統的なグループの長さは5文字です。 これは、単語の区切りから暗号文を推測しにくくするためです。

復号

復号の関数は次のとおりです。

D(y) = (a^-1)(y - b) mod m

それぞれの意味は次のとおりです。

• yは暗号化された文字の数値、つまりy = E(x)です。
• a^-1はa mod mのモジュラ逆数（MMI）であることが重要です。
• モジュラ逆数は、aとmが互いに素である場合にのみ存在します。

aのMMIは、axをmで割った余りが1になるようなxです。

ax mod m = 1

モジュラ逆数の求め方とその意味についての詳しい情報は、関連するWikipediaの記事にあります。

一般的な例

• 鍵a = 5、b = 7で"test"を暗号化すると"ybty"になります。
• 鍵a = 5、b = 7で"ybty"を復号すると"test"になります。
• 間違った鍵a = 11、b = 7で"ybty"を復号すると"lqul"になります。
• 鍵a = 19、b = 13で"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx"を復号すると"thequickbrownfoxjumpsoverthelazydog"になります。
• 18と26は互いに素でないため、鍵a = 18、b = 13で"test"を暗号化するとエラーになります。

モジュラ逆数（MMI）を求める例

a = 15のMMIを求めてみます。

• (15 * x) mod 26 = 1
• (15 * 7) mod 26 = 1、つまり105 mod 26 = 1
• 7は15 mod 26のMMIです

---

出典

Wikipedia