仿射密码把字母映射为 0~25 的整数,再用数学函数替换为另一个字母。它是一种单表替换密码,可用于学习模运算,不适合保护真实秘密。
任务说明
实现一种源于中东的古老加密方法:仿射密码。
它属于单表替换:先把字符映射为数字,经过数学函数变换,再转回对应字母。单表替换都容易破解,但仿射密码比 Atbash 拥有更多密钥。
加密
加密函数为:
E(x) = (ai + b) mod m
其中:
i是字母从 0 开始的索引。m是字母表长度,拉丁字母表取 26。- 整数
a和b构成密钥。
a 与 m 必须互质,即唯一公因数是 1,才能正确解密。更多背景见互质整数。不互质时应报告错误;否则按给定密钥加密或解密。
数字允许输入,但不加密。删除空格与标点。密文每 5 个字符一组,以空格分隔,避免暴露单词边界。
解密
解密函数为:
D(y) = (a^-1)(y - b) mod m
其中:
y是密文字母的数值,即y = E(x)。a^-1表示 a 模 m 的模乘逆元,不是普通倒数。- 只有 a 与 m 互质时,逆元才存在。
a 的模乘逆元是满足下式的 x,使 ax 除以 m 余 1:
ax mod m = 1
逆元含义与求法可参考相关文章。
综合示例
- 密钥
a=5,b=7:test加密为ybty。 - 同一密钥将
ybty解密为test。 - 错误密钥
a=11,b=7将其解密为lqul。 a=19,b=13将kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx解密为thequickbrownfoxjumpsoverthelazydog。a=18,b=13无效,因为 18 与 26 不互质。
求模乘逆元示例
求 a=15 的逆元:
- 要求
(15*x) mod 26 = 1。 15*7=105,而105 mod 26=1。- 因此 7 是 15 模 26 的乘法逆元。