问题引入：

仿射密码是一种替换密码，利用加密函数一个字母对一个字母的加密。

加密函数： E ( x ) = ( a x + b ) ( m o d m ) E(x) = (ax + b) (mod m) E(x)=(ax+b)(modm)，其中

• a与m互质
• m是编码系统中字符的数量

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

乘法逆元：

如果存在a,x,b满足线性同余方程ax ≡ 1(mod b)（即b除以整数ax − 1，或者换句话说，将ax除以整数b之后的余数为1），则我们称：

a关于模b的乘法逆元为x，表示为a ≡ x^-1 (mod b)；

x关于模b的乘法逆元为a，表示为x ≡ a^-1 (mod b)。

简单来说，求 a a a的逆，就是找一个 x x x，使得 1 = ( a ∗ x ) ( m o d n ) 1 = (a*x){\pmod n} 1=(a∗x)(modn)

也可记作 a − 1 ≡ x ( m o d n ) a^{-1} \equiv x{\pmod {n}} a−1≡x(modn)

仿射密码 为单表加密的一种，字母系统中所有字母都藉一简单数学方程加密，对应至数值，或转回字母。 其仍有所有替代密码之弱处。所有字母皆借由方程E(x) = (ax + b) (mod m)加密，b 为移动大小。

2021/07/30_内蒙古省赛_CRYPTO_AFFINE

首先看一下加密源码：

# -*- coding: utf-8 -*-
import string
import hashlib
from Flag import m,a,b

letter=string.ascii_letters+string.digits

def encrypt(m, c, a, b):
    for i in range(len(m)):
        ch=m[i]
        t=(letter.index(ch) * a + b) % 62
        c.append(letter[t])
    d = ''.join(c)
    print (d)

m = ????
c = []
a = ????
b = ????

assert ("Flag" in m)

print("加密后的密文为：")
Cipher = encrypt(m, c, a, b)
flag = hashlib.md5("".join(str(m))).hexdigest()

"""
加密后的密文为：
YWINN4R2bEmp4blzqpm2waT2KRCayj7C5TCp2wpvl0y
"""

代码逻辑比较清晰，密码表是大小写字母加10个数字

m,a,b均未知，给了加密后的字符。

assert ("Flag" in m)

说明明文中存在"Flag"字符，可以对a,b进行爆破：

# -*- coding: utf-8 -*-
import string
import hashlib

letter=string.ascii_letters+string.digits
m='YWINN4R2bEmp4blzqpm2waT2KRCayj7C5TCp2wpvl0y'
flag='Flag'
def f():
    for i in range(100):
        for j in range(100):
            c=[]
            for len in range(4):
                ch = flag[len]
                t=(letter.index(ch) * i + j) % 62
                c.append(letter[t])
            d = ''.join(c)
            #print(d)
            if  d in m:
                print("i=",i)
                print("j=",j)
                return
f()

得到结果：

a=47
b=52 

根据加密逻辑求逆元为33

inv = gmpy2.invert(47,62)
#33

手算的话使用拓展欧几里得算法：

加密：$( 47 * x + 52 ) {\pmod {62}}$

解密：$47^{-1}(x - 52) {\pmod {62}}$
∵	   $47^{-1}    \equiv x{\pmod {62}}$

即	$1 = (47 * x){\pmod {62}}$

即逆元为33

exp:

# -*- coding: utf-8 -*-
import string
import hashlib

letter=string.ascii_letters+string.digits
m='YWINN4R2bEmp4blzqpm2waT2KRCayj7C5TCp2wpvl0y'
a=47
b=52
c=[]
for i in range(len(m)):
    ch = m[i]
    t = letter.index(ch)
    x = (33*(t-52)) % 62
    x = int(x)
    c.append(letter[x])   
d = ''.join(c)
print(d)
#62Affine1sSti1lN0tSecureEnoughToProtectFlag