2.8 仿射密码

密码学入门 /

仿射密码加密思路：首先将明文乘以密钥的一部分，然后再加上密钥的剩余部分。

假设 x,y,a,b\in Z_{26}\\ 加密：e_k(x) = y\equiv a·x + b\ mod\ 26\\ 解密：d_k(y) = x\equiv a^{-1}·(y-b)\ mod\ 26\\ 密钥为：k = (a,b), 且满足限制条件 gcd(a,26) = 1

解密可以很容易地从加密函数中推导出来：

a·x+b\equiv y\ mod\ 26\\ a·x\equiv (y-b)\ mod \ 26\\ x\equiv a^{-1}·(y-b)\ mod\ 26

gcd(a, 26) = 1 这个限制条件来源于这样一个事实：解密时需要求密钥参数 a 的逆元。如果逆元存在，则元素 a 与模数必须为互素。因此, a 必须在如下集合中：

a\in \left\{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 \right\}

那么，我们怎样找到a^{-1}?目前我们只能通过试错法得到：对于给定的 a, 只需一次尝试所有可能的值a^{-1}, 直到得到：

a·a^{-1}\equiv 1\ mod\ 26

本文章首发在 LearnKu.com 网站上。