Crypto-仿射密码
仿射密码
- 凯撒密码是将明文与密钥相加得到密文,仿射密码则是将明文与密钥的一部分相乘,然后再加上密钥的另一部分
- 为了便于计算,将26个英文字母用数字表示:a=0,b=1,…,z=25
- 仿射加密的密钥有两个:a和b,取值范围都是[0,25]
- a要求与26互质,互质就是者两个数的公因数只有1
- 26的因数:1、2、13
- a的因素不包含2或13即可
仿射密码加密
-
x是明文,y是密文
-
加密公式:y=(ax+b)mod26
-
加密过程:
-
a=7、b=3
-
加密:
$$
y=(7x+3)mod26
$$
-
-
假设明文为c,那么x的值为2
-
所以y=17,密文为r
仿射密码解密
-
解密公式:
$$
x=a^{-1}(y-b)mod26
$$-
如果不考虑求模,根据加密公式很容易想到解密公式应该是x=(y-b)/a
-
因为要求模,除法很可能会得到小数,而小数无法做模运算
-
解决的方法是将除法转换为乘法
-
$$
a{-1}称为a的乘法逆元,((y-b)/a)mod26与a{-1}(y-b)mod26完全等价
$$
-
-
仿射密码解密的关键就在于如何求乘法逆元
乘法逆元
-
$$
假设用m表示a的乘法逆元,那么(a*m)mod26=1
$$ -
a=7,可以写个简单的代码来求m,只要第一个符合条件的值即可:
1 | a = 7 |
- $$
解密:x=15(y-3)mod26,x=15*14mod26=2,对应明文为c
$$
例题
1 | # -*- coding: utf-8 -*- |
例题2
1 | # -*- coding: utf-8 -*- |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 z0yuan's Blog!