仿射密码

说明

请实现仿射密码，这是一种起源于中东的古老加密系统。

仿射密码是一种单表代换密码。每个字符都会先映射到对应的数值，再用一个数学函数加密，然后转换回与新数值对应的字母。虽然所有单表代换密码都很弱，但仿射密码比埃特巴什密码强得多，因为它的密钥多得多。

加密

加密函数为：

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

其中：

• i是字母的下标，从0到字母表长度减 1。
• m是字母表的长度。对于拉丁字母表，m为26。
• a和b是构成加密密钥的整数。

要让自动解密成功，a和m这两个值必须_互质_（也就是_互素_），即它们的公因数只有1（更多信息见关于互质整数的维基百科条目）。如果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 是满足以下条件的x：用m除ax，余数为1：

ax mod m = 1

关于如何求模乘法逆元以及它的含义，更多信息见相关维基百科条目。

一般示例

• 使用密钥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