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) % nelse: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，也可以通过在线网站进行解码
def get(a, b):if b == 0:return 1, 0else:k = a // bremainder = a % bx1, y1 = get(b, remainder)x, y = y1, x1 - k * y1return x, ys = input("请输入解密字符：").upper()a = int(input("请输入a："))b = int(input("请输入b："))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) % 26res = chr(cipher + 65)print(res, end='')
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 randomtext = 'aCdhpnlmNKuRJbfVIXUvyTrSPqjBMzgwHZkAxWGiYetEsocDLFOQ'def Affline_Encode(plain, a, b):cipher = ''for i in plain:if i not in text:cipher += ielse:x = text.find(i)cipher += text[(x*a + b) % len(text)]return cipherwhile True:a=random.randint(1<<99, 1<<100)b=random.randint(1<<99, 1<<100)if GCD(a,52) == 1:breakassert 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 += ielse: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 gmpy2for 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 += _ielse:x = text.find(_i)cipher += text[(x * a_ + _b) % len(text)]return cipherdef 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_)breakdef decrypt(m, _a, _b):import gmpy2for 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 dif __name__ == '__main__':text = 'aCdhpnlmNKuRJbfVIXUvyTrSPqjBMzgwHZkAxWGiYetEsocDLFOQ'# 自定义key，视题目情况进行修改s = 'CezmBh{BKDdD_oP_rKD_rdtF_cMHu}'# 需要解密的字符串Get_Ab('DASCTF')# 根据已知的部分密文获取a, ba, 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即使本题所需的值。
0x04 写在最后
今天的简介就到这里啦，小编的水平有限，如有差误望各位大佬指正φ(*￣0￣)
原文始发于微信公众号（7coinSec）：就仿射密码(Affline)来一篇杂谈
