仿射密码

实践练习C++17

仿射密码把字母映射为 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 的乘法逆元。