就仿射密码(Affline)来一篇杂谈

0x00 前言

在密码学古典密码中，仿射密码无疑是单表代换加密中的典型。
在绝大多数单表代换加密中都有个通用特点，那就是在单表替换加密中，所有的加密方式几乎都有一个共性，那就是明密文一一对应。
所以说，一般有以下两种方式来进行破解
在密钥空间较小的情况下，采用暴力破解方式
在密文长度足够长的时候，使用词频分析，http://quipqiup.com/
而当密钥空间足够大的时候，且密文长度足够短的情况下，破解就变得较为困难。

0x01 相关知识简介

仿射密码是一种表单代换密码，字母表的每个字母相应的值使用一个简单的数学函数对应一个数值，再把对应数值转换成字母。

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

仿射密码的加密函数是 E(x)=(ax+b)(mod m)，其中

x 表示明文按照某种编码得到的数字
a 和 m 互质
m 是编码系统中字母的数目（通常都是26）

解密函数是 D(x)=a−1(x−b)(mod m)，其中 a^−1 是 a 在 Zm 群的乘法逆元。

所以对于仿射加密来说，要解密就要先求出a的逆元。

逆元的定义：群G中任意一个元素a，都在G中有唯一的逆元a^−1,具有性质aa^−1=a^−1a=e，其中e为群的单位元。

乘法逆元

模p意义下，一个数a如果有逆元x，那么除以a相当于乘以x。
在模n的意义下，a存在逆元的充要条件是n不等于1，且（a，n）互质。

def ModReverse(a,n):     if gcd == 1:        return (arr[0] % n + n) % n    else:        return -1

在满足存在逆元的条件（gcd==1，也就是互质）的情况下，返回(arr[0] % n + n) % n也就是返回了逆元。

0x02 相关样例演示

样例 1

下面我们以 E(x)=(5x+8)mod 26函数为例子进行介绍，加密字符串为 AFFINE CIPHER，这里我们直接采用字母表 26 个字母作为编码系统

其对应的加密结果是 IHHWVCSWFRCP。

对于解密过程，正常解密者具有a与b，可以计算得到a^−1为 21，所以其解密函数是D(x)=21(x−8)(mod26)，解密如下

可以看出其特点在于只有 26 个英文字母。

样例 2

这里我们已知加密函数为 y = 3x + 9，而加密之后的密文为："JYYHWVPIDCOZ"

我们通过前面的基础知识简介可以知道它的加密函数是:

y=ax+b(mod m)，其中a和m互质，m是字母的数目。

解密函数是：x=a−1(y-b)(mod m)，其中a^−1是a的数论倒数。

所以经过计算可以得出 a^−1= 9，也就是说解密函数可以描述为：y = 9*(x-9) (mod m)，其中m为加密时的字母数，也就是26

下面进行层层计算演示：

密文	J	Y	Y	H	W	V	P	I	D	C	O	Z
y	9	24	24	7	22	21	15	8	3	2	14	25
x = 9 * (y - 9)	0	135	135	-18	117	108	54	-9	-54	-72	45	144
x mod 26	0	5	5	8	13	4	2	17	24	15	19	14
明文	A	F	F	I	N	E	C	R	Y	P	T	O

据此可以推出明文为：AFFINECRYPTO

以下贴出解码所需要的exp，也可以通过在线网站进行解码

# 改进欧几里得算法求线性方程的x与ydef get(a, b):    if b == 0:        return 1, 0    else:        k = a // b        remainder = a % b        x1, y1 = get(b, remainder)        x, y = y1, x1 - k * y1    return x, y

s = input("请输入解密字符：").upper()a = int(input("请输入a："))b = int(input("请输入b："))
# 求a关于26的乘法逆元x, y = get(a, 26)a1 = x % 26print("所求a的逆元为：", a1)
n = len(s)for i in range(n):    cipher = a1 * (ord(s[i]) - 65 - b) % 26    res = chr(cipher + 65)    print(res, end='')# AFFINECRYPTO

0x03 仿射变种-自定义密钥

近日在一道Cr题中遇到一个根据自定义密钥进行仿射加密的题，其在加密函数是 E(x)=(ax+b)(mod m)不变的情况下，更换加密所需的密钥而非正常情况下的26个英文字母，此时其解密函数仍是 D(x)=a^−1(x−b)(mod m)，但已不可通过常规的解密网站或工具进行解密。接下来我们通过对例题进行逐步详解

加密脚本如下：

from Crypto.Util.number import *from flag import flagimport random
text = 'aCdhpnlmNKuRJbfVIXUvyTrSPqjBMzgwHZkAxWGiYetEsocDLFOQ'
def Affline_Encode(plain, a, b): cipher = '' for i in plain:  if i not in text:   cipher += i  else:   x = text.find(i)   cipher += text[(x*a + b) % len(text)]
 return cipher
while True: a=random.randint(1<<99, 1<<100) b=random.randint(1<<99, 1<<100) if GCD(a,52) == 1:  break
assert flag[:6]=='DASCTF'print(Affline_Encode(flag, a, b))# cipher = 'CezmBh{BKDdD_oP_rKD_rdtF_cMHu}'

通过如上脚本可以看出其密钥为：aCdhpnlmNKuRJbfVIXUvyTrSPqjBMzgwHZkAxWGiYetEsocDLFOQ，长度为52，此时a的值便为0，而Q的值则为51。

而加密函数Affline_Encode即为仿射加密函数，其数式就是E(x)=(ax+b)(mod m)

# E(x)=(ax+b)(mod m)def Affline_Encode(plain, a, b): cipher = '' for i in plain:  if i not in text:   cipher += i  else:   x = text.find(i)   cipher += text[(x*a + b) % len(text)]
 return cipher

而题中并没有给出系数a，b的值，CezmBh{BKDdD_oP_rKD_rdtF_cMHu}即为加密后的密文，此时我们可以根据已知的部分明文DASCTF和其所给出的加密函数来对a，b进行爆破，爆破a，b的函数部分如下：

def Get_Ab(S):    for a_ in range(len(text)):        for b_ in range(len(text)):            Cipher = encrypt(S, a_, b_)            for k in range(len(s)):                if Cipher == s[:6]:                    print(Cipher, a_, b_)                    break

运行可以得到爆破所得结果：

CezmBh 1 6CezmBh 27 32

如此可以看出a，b的取值有两组，再通过其解密函数：D(x)=a^−1(x−b)(modm)来对其进行解码，而在本题中的密钥与常规题型有所不同，但本质上还是一致的，如此我们可以将解密函数定义如下：

# D(x)=a^−1(x−b)(mod m)def decrypt(m, _a, _b):    import gmpy2    for i_ in range(len(m)):        c = m[i_]        t = ((text.index(c) - _b) * gmpy2.invert(_a, len(text))) % len(text)        d = ''.join(text[t])        return d

其所返回的d也就是我们解码后的明文字符，如此我们即可解出

完整exp如下：

def encrypt(plain, a_, _b):    cipher = ''    for _i in plain:        if _i not in text:            cipher += _i        else:            x = text.find(_i)            cipher += text[(x * a_ + _b) % len(text)]    return cipher

def Get_Ab(S):    for a_ in range(len(text)):        for b_ in range(len(text)):            Cipher = encrypt(S, a_, b_)            for k in range(len(s)):                if Cipher == s[:6]:                    print(Cipher, a_, b_)                    break

def decrypt(m, _a, _b):    import gmpy2    for i_ in range(len(m)):        c = m[i_]        t = ((text.index(c) - _b) * gmpy2.invert(_a, len(text))) % len(text)        d = ''.join(text[t])        return d

if __name__ == '__main__':    text = 'aCdhpnlmNKuRJbfVIXUvyTrSPqjBMzgwHZkAxWGiYetEsocDLFOQ'    # 自定义key，视题目情况进行修改    s = 'CezmBh{BKDdD_oP_rKD_rdtF_cMHu}'    # 需要解密的字符串    Get_Ab('DASCTF')    # 根据已知的部分密文获取a, b    a, b = 27, 32    # 对非key的字符进行过滤，然后解码    for i in range(len(s)):        if s[i] not in text:            print(s[i], end="")        else:            print(decrypt(s[i], a, b), end="")# DASCTF{There_is_the_truE_fLag}

经测试第二组a，b即使本题所需的值。