Python板子

CTF
, ,

打CTF也许会用到.

TEA加密 XTEA XXTEA

ref

RC4

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
26
27
28
29
30
def rc4_crypt(data, key):
    """RC4加解密算法，data和key均为bytes类型"""
    # 初始化S盒
    S = list(range(256))
    j = 0
    out = []

    # KSA算法 (Key-Scheduling Algorithm)
    for i in range(256):
        j = (j + S[i] + key[i % len(key)]) % 256
        S[i], S[j] = S[j], S[i]

    # PRGA算法 (Pseudo-Random Generation Algorithm)
    i = j = 0
    for byte in data:
        i = (i + 1) % 256
        j = (j + S[i]) % 256
        S[i], S[j] = S[j], S[i]
        t = (S[i] + S[j]) % 256
        out.append(byte ^ S[t])
    
    return bytes(out)

# 使用示例
key = b"secret_key"
plaintext = b"hello world"
ciphertext = rc4_crypt(plaintext, key)
print(ciphertext.hex())
decrypted = rc4_crypt(ciphertext, key)
print(decrypted.decode())

long_to_bytes

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
def long_to_bytes(n, byteorder='big'):
    if n == 0:
        return b'\x00'
    if n < 0:
        raise ValueError("不支持负数转换")
    bytes_list = []
    while n > 0:
        # 取最低8位（一个字节）
        byte = n & 0xFF
        bytes_list.append(byte)
        # 右移8位
        n = n >> 8
    if byteorder == 'big':
        bytes_list.reverse()
    return bytes(bytes_list)

def bytes_to_long(bytes_data,byteorder='big'):
    if not bytes_data:
        return 0
    if byteorder=='little':
        bytes_data=bytes_data[::-1]
    result=0
    for byte in bytes_data:
        result=(result<<8)|byte
    return result

离散对数(sage脚本)

求解 $a^m\equiv y\mod p$ 的脚本

1
m = discrete_log(Integers(p_val)(y_val), Integers(p_val)(a_val))

二分(最小值)

1
2
3
4
5
6
7
8
9
10
11
def BSCheck(num):
    # Checker自己写

def BS(l,r):
    while l<r:
        mid=(l+r)>>1
        if BSCheck(mid):
            r=mid
        else:
            l=mid+1
    return l

二次剩余

输入:输出所有解或者无解(Hola!)

1
2
T
N p

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
26
27
28
29
30
31
32
33
34
35
36
37
class expand:
    def __init__(self, x, y, z):
        '''x+yi,其中i^2=z'''
        self.re = x
        self.im = y
        self.id = z

    def __mul__(self, other):
        ans = expand(0, 0, self.id)
        ans.re = self.re*other.re+self.im*other.im*self.id
        ans.im = self.re*other.im+self.im*other.re
        return ans

    def mod(self, p):
        return expand(self.re % p, self.im % p, self.id)


T = int(input())
for t in range(T):
    n, p = map(int, input().split())
    if n==0:
        print(0)
        continue
    if pow(n,(p-1)//2,p)==p-1:
        print("Hola!")
        continue
    a=0
    while pow(a*a-n,(p-1)//2,p)==1:
        a+=1
    k=(p+1)//2
    ans,power=expand(1,0,a*a-n),expand(a,1,a*a-n)
    while k:
        if k&1:
            ans=(ans*power).mod(p)
        power=(power*power).mod(p)
        k>>=1
    print(*sorted([ans.re,p-ans.re]))

快速幂

1
2
3
4
5
6
7
8
def qp(base,po,mod):
    res=1
    while po>0:
        if po&1:
            res=res*base%mod
        base=base*base%mod
        po>>=1
    return res

组合数(杨辉三角)

1
2
3
4
5
6
7
8
yh=[[0 for _ in range(1010)] for _ in range(1010)]
def init(n):
    for i in range(1,n+1):
        yh[i][1]=yh[i][i]=1
        for j in range(2,i,1):
            yh[i][j]=(yh[i-1][j]+yh[i-1][j-1])
def C(n,m):
    return yh[n+1][m+1]

欧拉筛

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
N=1000000
ptop=0
vis=[0]*(N+5)
p=[0]*(N//10+5)
mu=[0]*(N+5)
musu=[0]*(N+5)
phi=[0]*(N+5)
phisu=[0]*(N+5)
d=[0]*(N+5)
mnnum=[0]*(N+5)
def sieve(n):
    global ptop
    phi[1]=1;phisu[1]=1;mu[1]=1;musu[1]=1;d[1]=1
    for i in range(2,n+1):
        if(vis[i]==0):
            ptop+=1
            vis[i]=-ptop
            p[ptop]=i
            mu[i]=-1#
            phi[i]=i-1#
            d[i]=2#
            mnnum[i]=1;#
        j=1
        while(True):
            if(j<=ptop and i*p[j]<=n):
                vis[i*p[j]]=p[j]
                if(i%p[j]==0):
                    phi[i*p[j]]=phi[i]*p[j]; #
                    mnnum[i*p[j]]=mnnum[i]+1; #
                    d[i*p[j]]=d[i]/mnnum[i*p[j]]*(mnnum[i*p[j]]+1); #
                    break
                else:
                    mu[i*p[j]]=-mu[i]#
                    phi[i*p[j]]=phi[i]*(p[j]-1)#
                    mnnum[i*p[j]]=1#
                    d[i*p[j]]=d[i]*2#
            else:
                break
            j+=1
        musu[i]=musu[i-1]+mu[i];#
        phisu[i]=phisu[i-1]+phi[i];#

矩阵求模意义下的逆矩阵

感谢洛谷开源.

1
2
3
4
3
1 2 3
4 5 6
7 8 9

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import sys
sys.setrecursionlimit(1000000000)
input = lambda: sys.stdin.readline()
write = lambda x: sys.stdout.write(str(x)+'\n')
MOD = 10**9+7
def get_param():
    n = int(input().strip())
    matrix = [[0]]
    for i in range(1, n+1):
        cur_l = [0]+list(map(int, input().strip().split(' ')))+[0]*n
        cur_l[i+n] = 1
        matrix.append(cur_l)
    return n, matrix
def get_inv(n, matrix):
    for col in range(1, n+1):
        max_row = col
        max_num = matrix[col][col]
        for row in range(col+1, n+1):
            if matrix[row][col] > max_num:
                max_row = row
                max_num = matrix[row][col]
        if not max_num:
            return None
        if col != max_row:
            matrix[col], matrix[max_row] = matrix[max_row], matrix[col]
        div = pow(matrix[col][col], MOD-2, MOD)
        for i in range(col, (n<<1)+1):
            matrix[col][i] *= div
            matrix[col][i] %= MOD
        for row in range(1, n+1):
            if row == col:
                continue
            for i in range(n<<1, col-1, -1):
                matrix[row][i] -= matrix[col][i]*matrix[row][col]
                matrix[row][i] %= MOD
    inv = []
    for i in range(1, n+1):
        inv.append(matrix[i][n+1:(n<<1)+1])
    return inv
if __name__ == '__main__':
    n, matrix = get_param()
    inv = get_inv(n, matrix)
    if not inv:
        write('No Solution')
    else:
        for i in inv:
            print(*i)

python画图板子

把一个神秘的函数的图像呈现在面前,找规律速度会很快.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import matplotlib.pyplot as plt

m,k,s=100,11,10 # 在这里调参
def f(n): # 函数定义
    if n > m:
        return n - s
    else:
        return f(f(n+k))

X=[i for i in range(-100,300)] # X的范围
Y=list(map(f,X))
fig,ax=plt.subplots()
ax.scatter(X,Y)
plt.show()

梅森旋转爆破 mt19937

梅森旋转是实现了一个优秀的随机数发生器,但不是一个密码学安全的随机数,所以可以实现爆破.

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class MersenneTwister:
    __n = 624
    __m = 397
    __a = 0x9908b0df
    __b = 0x9d2c5680
    __c = 0xefc60000
    __kInitOperand = 0x6c078965
    __kMaxBits = 0xffffffff
    __kUpperBits = 0x80000000
    __kLowerBits = 0x7fffffff

    def __init__(self, seed = 0):
        self.__register = [0] * self.__n
        self.__state = 0

        self.__register[0] = seed
        for i in range(1, self.__n):
            prev = self.__register[i - 1]
            temp = self.__kInitOperand * (prev ^ (prev >> 30)) + i
            self.__register[i] = temp & self.__kMaxBits

    def __twister(self):
        for i in range(self.__n):
            y = (self.__register[i] & self.__kUpperBits) + \
                    (self.__register[(i + 1) % self.__n] & self.__kLowerBits)
            self.__register[i] = self.__register[(i + self.__m) % self.__n] ^ (y >> 1)
            if y % 2:
                self.__register[i] ^= self.__a
        return None

    def __temper(self):
        if self.__state == 0:
            self.__twister()

        y = self.__register[self.__state]
        y = y ^ (y >> 11)
        y = y ^ (y << 7) & self.__b
        y = y ^ (y << 15) & self.__c
        y = y ^ (y >> 18)

        self.__state = (self.__state + 1) % self.__n

        return y

    def __call__(self):
        return self.__temper()

    def load_register(self, register):
        self.__state = 0
        self.__register = register

class TemperInverser:
    __b = 0x9d2c5680
    __c = 0xefc60000
    __kMaxBits = 0xffffffff

    def __inverse_right_shift_xor(self, value, shift):
        i, result = 0, 0
        while i * shift < 32:
            part_mask = ((self.__kMaxBits << (32 - shift)) & self.__kMaxBits) >> (i * shift)
            part = value & part_mask
            value ^= part >> shift
            result |= part
            i += 1
        return result

    def __inverse_left_shift_xor(self, value, shift, mask):
        i, result = 0, 0
        while i * shift < 32:
            part_mask = (self.__kMaxBits >> (32 - shift)) << (i * shift)
            part = value & part_mask
            value ^= (part << shift) & mask
            result |= part
            i += 1
        return result

    def __inverse_temper(self, tempered):
        value = tempered
        value = self.__inverse_right_shift_xor(value, 18)
        value = self.__inverse_left_shift_xor(value, 15, self.__c)
        value = self.__inverse_left_shift_xor(value, 7, self.__b)
        value = self.__inverse_right_shift_xor(value, 11)
        return value

    def __call__(self, tempered):
        return self.__inverse_temper(tempered)



class MersenneTwisterCracker:
    __n = 624

    def __init__(self, mt_obj):
        inverser  = TemperInverser()
        register  = [inverser(mt_obj()) for i in range(self.__n)]
        self.__mt = MersenneTwister(0)
        self.__mt.load_register(register)

    def __call__(self):
        return self.__mt()

if __name__ == "__main__":
    mt  = MersenneTwister(2000)
    for i in range(100):
        mt()
    mtc = MersenneTwisterCracker(mt)
    for i in range(100):
        assert(mt() == mtc())

LCG and deLCG

线性同余生成器和对应的cracker(根据所有状态反推ver)

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
26
27
28
29
30
31
def LCG(seed, a, b, m):
    state = seed
    while True:
        state = (a*state + b) % m
        yield state
def deLCG(gift, a, b, m):
    state=gift
    inva=gmpy2.invert(a,m)
    while True:
        state=((m+state-b)*inva)%m
        yield state


from math import gcd
from functools import reduce
from gmpy2 import invert
# LCG随机数cracker,需要连续5个输出
def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment
    # 返回mab
def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * invert(states[1] - states[0], modulus) % modulus # 注意这里求逆元
    return crack_unknown_increment(states, modulus, multiplier)
    # 返回mab
def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)
    # 返回mab

exCRT 中国剩余定理

错了再说.

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
26
27
28
29
30
31
32
33
def exgcd(a,b):
    x1=1
    x2=0
    x3=0
    x4=1
    while(b!=0):
        c=a//b
        (x1,x2,x3,x4,a,b)=(x3,x4,x1-x3*c,x2-x4*c,b,a-b*c)
    # a x y
    return a,x1,x2
def CRT(mmod,rres,n):
    sum=1
    res=0
    for i in range(1,n+1):
        sum*=mmod[i];
    for i in range(1,n+1):
        m=sum//mmod[i]
        gg,x,y=exgcd(m,mmod[i])
        x=(x%sum+sum)%sum
        c=m*x
        res=(res+rres[i]*c)%sum
    return res
def exCRT(mmod,rres,n):
    tmp=mmod[1]
    res=rres[1]
    for i in range(2,n+1):
        ttmp=((rres[i]-res)%mmod[i]+mmod[i])%mmod[i]
        gg,x,y=exgcd(tmp,mmod[i])
        x=ttmp//gg*x%mmod[i]
        res+=tmp*x
        tmp*=mmod[i]//gg
        res=(res+tmp)%tmp
    return res

XXTEA加密

让阶么奈写的.

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
import struct
from Crypto.Util.number import *

class XXTEA:
    def __init__(self,key: bytes):
        """
        初始化 XXTEA 类
        :param key: 密钥，必须是 16 字节 (128-bit) 的 bytes 对象
        """
        if len(key)!=16:
            raise ValueError("Key must be exactly 16 bytes long.")
        self.key=list(struct.unpack('<4I',key))
        self.delta=0x9E3779B9

    def _mx(self,sum_val,y,z,p,e,k):
        """
        Mixed definition (MX) 混合函数
        """
        return (
                ((z>>5^y<<2)+(y>>3^z<<4))^
                ((sum_val^y)+(k[(p&3)^e]^z))
        )&0xFFFFFFFF

    def encrypt(self,data: bytes) -> bytes:
        """
        加密数据
        :param data: 待加密的 bytes 数据
        :return: 加密后的 bytes 数据
        """
        if not data:
            return b""

        # 将 bytes 转换为 uint32 数组 (Little Endian)
        v=self._bytes_to_uint32s(data)
        k=self.key
        n=len(v)

        z=v[n-1]
        y=v[0]
        sum_val=0

        # 6 + 52/n 是标准的循环次数建议
        q=6+52//n

        while q>0:
            sum_val=(sum_val+self.delta)&0xFFFFFFFF
            e=(sum_val>>2)&3

            for p in range(n-1):
                y=v[p+1]
                v[p]=(v[p]+self._mx(sum_val,y,z,p,e,k))&0xFFFFFFFF
                z=v[p]

            p=n-1
            y=v[0]
            v[p]=(v[p]+self._mx(sum_val,y,z,p,e,k))&0xFFFFFFFF
            z=v[p]
            q-=1

        return self._uint32s_to_bytes(v,False)

    def decrypt(self,data: bytes) -> bytes:
        """
        解密数据
        :param data: 已加密的 bytes 数据
        :return: 解密后的 bytes 数据
        """
        if not data:
            return b""

        v=self._bytes_to_uint32s(data,include_length=False)
        k=self.key
        n=len(v)

        z=v[n-1]
        y=v[0]

        q=6+52//n
        sum_val=(q*self.delta)&0xFFFFFFFF

        while sum_val!=0:
            e=(sum_val>>2)&3

            p=n-1
            y=v[0]
            z=v[p-1]
            v[p]=(v[p]-self._mx(sum_val,y,z,p,e,k))&0xFFFFFFFF
            y=v[p]

            while p>0:
                p-=1
                z=v[p-1]
                v[p]=(v[p]-self._mx(sum_val,y,z,p,e,k))&0xFFFFFFFF
                y=v[p]

            sum_val=(sum_val-self.delta)&0xFFFFFFFF

        return self._uint32s_to_bytes(v,True)

    def _bytes_to_uint32s(self,data: bytes,include_length=True) -> list:
        """
        辅助函数：将 bytes 转换为 32位整数列表。
        通常 XXTEA 实现会将原始数据长度也编码进去，以便正确处理末尾的 padding。
        """
        length=len(data)

        # 计算需要多少个 32位整数
        num_ints=(length//4)+(1 if length%4 else 0)

        # 解包
        fmt=f'<{num_ints}I'
        # 如果长度不是4的倍数，需要补零
        padded_data=data+b'\x00'*((4-length%4)%4)
        v=list(struct.unpack(fmt,padded_data))

        if include_length:
            v.append(length)

        return v

    def _uint32s_to_bytes(self,v: list,check_length=True) -> bytes:
        """
        辅助函数：将 32位整数列表转换回 bytes。
        """
        if check_length:
            length=v[-1]
            v=v[:-1]

        fmt=f'<{len(v)}I'
        data=struct.pack(fmt,*v)

        if check_length:
            return data[:length]
        return data


# --- 使用示例 ---
if __name__=="__main__":
    # 1. 设置密钥 (必须是 16 字节)
    key_bytes=b"1234567890123456"
    cipher=XXTEA(key_bytes)

    # 2. 准备数据
    text="Hello, XXTEA Encryption! 这里是中文测试。"
    data_bytes=text.encode('utf-8')

    print(f"原始数据: {text}")

    # 3. 加密
    encrypted=cipher.encrypt(data_bytes)
    print(f"加密后 (Hex): {encrypted.hex()}")

    # 4. 解密
    decrypted=cipher.decrypt(encrypted)
    print(f"解密后: {decrypted.decode('utf-8')}")

    # 5. 验证
    assert data_bytes==decrypted
    print("验证成功！")