仿射密码

基本概念

仿射密码是一种单表替换密码，字母表中的每个字母对应的值使用仿射函数映射到对应的数值，再把对应数值转换为字母进行加密。

仿射函数：

$f(x)=(ax+b)\bmod 26$

依据仿射函数进行加密的密码体制称为仿射密码。

当$a=1$时，不难发现其实质就成了凯撒密码。

加密函数：

$e(x)=(ax+b)\bmod m$

其中，$a$和$m$互质，m是字母数目，为26。

解密函数：

$d(x)=a^{-1}(x-b)\bmod m$

$a^{-1}$是$a$在$m$上的逆元，满足$aa^{-1}\equiv 1(\bmod 26)$

计算原理

加密函数的同余方程我们可以转化为$ax\equiv y-b(\bmod 26)$，由于要对密文进行解密，我们需要让仿射函数为一个单射，这个同余方程需要有唯一解，需要使$gcd(a,26)=1$

这里，我们求出和26所有互素的数为1,3,5,7,9,11,15,17,19,21,23,25，总共12个，$b$的取值为$Z_{26}$的某个数，所以我们得到仿射密码的秘钥空间为$12×26=312$

用欧拉函数的相关知识可以得到，仿射密码的秘钥空间为$m\phi(m)$

这里提示我们可以用爆破的思想来进行解密。

如某已知是仿射密码加密的密文为HIVMURCQWQIWUHEV，我们可以对其进行如下爆破：

import gmpy2

cipher='HIVMURCQWQIWUHEV'
A=[1,3,5,7,9,11,15,17,19,21,23,25]
for a in A:
    for b in range(0,26):
        flag=''
        for i in cipher:
            flag+=chr(gmpy2.invert(a,26)*(ord(i)-ord('A')-b)%26+ord('A'))
        print(flag)

在得到的312个结果里，我们能找到一个FANGSHEMIMAISFUN看起来符合要求。

但是，经过以上的研究，发现这种方法爆破得到的结果过多，简单的文本还好，如果比较长的密文再用这种方法就不大好了，既花费大量运算，看久了眼睛也难受，所以，对于比较长的密文，我们可以用一些别的方法。

利用单表替换求解ab

如果我们截获了以下密文：

FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH

如果我们可以认定其进行了仿射加密，我们可以采用单表替换的思想，先观察这条密文，分析一下最大频数：R（8次），D（7次），E，H，K（各5次），S，F，V（各4次）。

英文字母表统计表出现频数最高的字母前三位为ETA，我们可以对其进行假设并且代入仿射函数求解方程组：

先猜测R为e，D为t：$e(4)=17,e(19)=3$

得到$(4a+b)\bmod 26=17,(19a+b)\bmod 26=3$，解得$a=6,b=19$，但是$a$不符合要求。

再猜测R为e，E为t：$e(4)=17,e(19)=4$

同理解得$a=13,b=17$，$a$不符合要求。

再猜测R为e，K为t，解得$a=3,b=5$，密钥合法。

然后简单计算一下，就能得到明文：

import gmpy2

cipher='FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH'
a=3;b=5
flag=''
for i in cipher:
    flag+=chr(gmpy2.invert(a,26)*(ord(i)-ord('A')-b)%26+ord('A'))
print(flag)
#ALGORITHMSAREQUITEGENERALDEFINITIONSOFARITHMETICPROCESSES