仿射密码

说明

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

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

加密

加密函数为：

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 的模乘法逆元是满足以下条件的 x：ax 除以 m 后的余数为 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 的模乘法逆元：

• (15 * x) mod 26 = 1
• (15 * 7) mod 26 = 1，即 105 mod 26 = 1
• 7 是 15 mod 26 的模乘法逆元

---

来源

Wikipedia