アフィン暗号

説明

アフィン暗号の実装を作成しましょう。アフィン暗号は、中東で生まれた古い暗号方式です。

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

暗号化

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

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"になります
• 鍵a = 18、b = 13で"test"を暗号化しようとすると、18と26が互いに素でないためエラーになります

モジュラー乗法逆元（MMI）を求める例

a = 15のMMIを求める:

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

---

出典

Wikipedia