Python板子

CTF
, ,

打CTF也许会用到.

TEA加密 XTEA XXTEA

ref

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
#include <stdio.h>
/**
 * @brief 这是一个简短的 TEA 解密指南，依据 IDA 反编译的结果，
 *        正确填充代码中的空缺处，运行后就可以获得 flag！
 * 
 * @attention 请先移步 main 函数，阅读此题拆解！
 */

#define uint unsigned int

/**
 * @brief TEA 解密一个 64 位数据块
 *
 * @param cipher 待解密数据（2×32 bit）
 * @param key    128 位密钥（4×32 bit）
 * @param delta  常量值
 */
void tea_decrypt(uint cipher[2], uint key[4])
{
    /**
     * @brief 解密是加密的逆过程。如果我们已知最终的密文，
     *        并可以通过某种方式恢复上一轮的状态，
     *        那么一直恢复到最初状态，就可以得到明文。
     *        在此例中，加密的逻辑是这样的：
     *     -> 先将 delta 减去 1640531527（或为加上 0x9E3779B9）
     *     -> 更新 cipher[0]
     *     -> 更新 cipher[1]
     *     -> 重复以上操作，循环 32 次
     *        由于更新某一个数据时，另外两个数据和密钥的值都是固定的，
     *        于是在解密时，我们只需要：
     *     -> 反向更新 cipher[1]
     *     -> 反向更新 cipher[0]
     *     -> 将 delta 加上 1640531527（或为减去 0x9E3779B9）
     *     -> 重复以上操作，循环 32 次
     * 
     * @attention 根据 IDA 反编译展示的逻辑，修改下面代码中填 0x0 的部分。 
     */
    uint delta = -1640531527 * 32;

    for(int i = 1; i <= 32; i++)
    {
        cipher[1] -= (cipher[0] + delta) ^ (16 * cipher[0] + key[2]) ^ ((cipher[0]>>5)+key[3]);
        cipher[0] -= (cipher[1] + delta) ^ (16 * cipher[1] + key[0]) ^ ((cipher[1]>>5)+key[1]);
        delta += 1640531527;
    }
}

/**
 * @brief XTEA 解密一个 64 位数据块
 *
 * @param cipher 待解密数据（2×32 bit）
 * @param key    128 位密钥（4×32 bit）
 * @param delta  常量值
 */
void xtea_decrypt(uint cipher[2], uint key[4])
{
    /**
     * @brief 这里的反编译可能会出现 *(_DWORD *)。
     *        不用害怕，以 (4LL * (v4 & 3) + xtea_key_address) 为例，
     *        由于 uint 的存储空间为 4 字节，乘上几个 4 就代表偏移量是几。
     * 
     * @attention 根据 IDA 反编译的结果，修改下面代码中填 0x0 的部分。
     */
    uint delta = -1640531527 * 32;

    for(int i = 1; i <= 32; i++)
    {
        cipher[1] -= (((cipher[0]>>5)^(16*cipher[0]))+cipher[0]) ^ (key[(delta >> 11) & 3] + delta);
        delta += 1640531527;
        cipher[0] -= (((cipher[1]>>5)^(16*cipher[1]))+cipher[1]) ^ (key[(delta) & 3] + delta);
    }
}

int main()
{
    /**
     * @brief 你看懂 main 函数的逻辑了吗？
     *        本题分为两个加密部分：
     *        第一，tea_encrypt 函数对 flag 前 16 字节进行加密。
     *        第二，xtea_encrypt 函数对 flag 后 16 字节进行加密。
     *        密文分别存储在 tea_cipher 和 xtea_cipher 中。
     * 
     * @attention 让我们先来解密 tea_encrypt 部分！
     *            请双击 check_tea_part 函数，找到这部分的密文以及密钥。
     */

     /**
      * @brief 密文数组由 4 个 32 位无符号整数构成。
      * 
      * @attention 双击 tea_cipher，填充以下数据！我已经帮你填好一个了。
      */
    uint cipher1[4] = {
        0xB3E7E33E,
        0xB4114672,
        0x8E088C0C,
        0x14B2C329
    };
    /**
     * @brief 密钥数组同样由 4 个 32 位无符号整数构成。
     *        双击 get_tea_key_address，再双击 tea_key，填充...
     *        等一下，我的 32 位整数呢？！实际上，呈现在你面前的 16 字节，
     *        是密钥数组在内存中原始的存储形式。按每四个字节划分，
     *        就可以得到 4 个密钥。那么，第一个密钥是 0x78563412 吗？
     *        并不是！x86-64 机器一般采用小端序存储。记住一点：
     *        低位字节存储在低地址，高位字节存储在高地址。因此，
     *        第一个密钥应该是 0x12345678。
     * 
     * @attention 完成剩下的填充！
     */
    uint key1[4] = {
        0x12345678,
        0x87654321,
        0x13572468,
        0x24681357
    };
    /**
     * @brief 加密算法 TEA 要求加密密钥为 128 比特，密文块分组长度为 64 比特。
     *        这里密文长度为 128 比特，因此要分为两个块分别加密。
     * 
     * @attention 请移步 tea_decrypt 函数，完成解密逻辑编写！
     */
    tea_decrypt(cipher1, key1);
    tea_decrypt(cipher1 + 2, key1);

    /**
     * @brief 祝贺你成功完成第一部分的解密！第二部分是 xtea 解密，
     *        整体思路和 tea 差不多，不过在加密流程中有些许出入。
     * 
     * @attention 填充对应密文。
     */
    uint cipher2[4] = {
        0x60EC68AB,
        0x940251CE,
        0xB427534C,
        0xDF435416
    };
    /**
     * @attention 填充对应密钥。注意：别忘记小端序！
     */
    uint key2[4] = {
        0xDEADBEEF,
        0xcafebabe,
        0x11223344,
        0x55667788
    };
    /**
     * @attention 移步 xtea_decrypt，继续完成解密逻辑编写。
     */
    xtea_decrypt(cipher2, key2);
    xtea_decrypt(cipher2 + 2, key2);
    /**
     * @attention 补全所有部分后，运行程序。如果解密正确，就能看到输出的 flag 啦！
     */
    printf("%.16s%.16s\n", (char *)cipher1, (char *)cipher2);

    return 0;
}

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("验证成功！")

字符替换

自定义base64的来了

1
2
3
4
5
6
7
8
9
10
CUSTOM = "Six5tarsPJYouNgLlKEw4Ik1nGABCDFHMOQRTUVWXZbcdefhjmpqvyz0236789+/"
STD =    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"

s="KwC2gtPmKwn2NwTyKwGilvt0KwOiuqTvKw43utP2KwOxgttpKwC2gtPmKwn2lwUiKwIxNvtzKwn2lTa5Kw42KTP0KwIiNtt0Kw42NRT3KwM2g4JaKwn3NTarKwIxu5OrKw42NRT3KwOxKwUrKwIxu5OrKw42NRT3KwIxKtP3Kwn3N4PjKwIiK5T0Kw43lRUxKwIiNtt0Kw42NRT3Kw42NwOxKwOiKTPzKwKxg5OxKw42g5TpKwDxl4JrKwIxu5OrKw42NRT3KwIxKtP3KwM2g4JaKwC2g4P3KwDxKwOaKw42NwMqKwIxu5OrKw42NRT3KwIiN5TzKwKxg5OxKw42g5TpKwDxl4JrKwIiNtt0Kw42NRT3KwOxK4JaKwKxg5OtKwGxlwU5Kwn3N4PjKwIiK5T0KwT3lTPzKwn3N4PjKwIiK5T0KwKxg5MqKwIxu5OrKw42NRT3Kw43lvPjKwIxu5OrKw42NRT3KwM2g4JaKwn3NTarKw42KTPqKwn2lTa5Kw42KTP0"

for i in s:
    for j in range(0,len(CUSTOM)):
        if CUSTOM[j]==i:
            print(STD[j],end='')
            break

高斯消元

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
def lagrange(p, x, y, xp):
    """
    在模 p 意义下求：

        y[i] = sum(c[j] * x[i] ** xp[j])  (mod p)

    返回：
        [c[0], c[1], ..., c[n-1]]

    参数：
        p  : 质数模数
        x  : 采样点横坐标
        y  : 采样点纵坐标
        xp : 未知项的次数

    要求：
        len(x) == len(y) == len(xp)

    例如：
        y = a*x + b*x^2 + c*x^5

        xp = [1, 2, 5]

        返回 [a, b, c]
    """
    n = len(x)

    assert len(y) == n
    assert len(xp) == n

    # 构造广义 Vandermonde 矩阵
    # A[i][j] = x[i] ^ xp[j]
    A = [
        [pow(x[i], xp[j], p) for j in range(n)]
        for i in range(n)
    ]

    # 增广矩阵
    for i in range(n):
        A[i].append(y[i] % p)

    # 高斯消元
    for col in range(n):
        # 找主元
        pivot = col
        while pivot < n and A[pivot][col] == 0:
            pivot += 1

        if pivot == n:
            raise ValueError("系数矩阵不可逆，无法唯一确定系数")

        # 换行
        A[col], A[pivot] = A[pivot], A[col]

        # 主元归一化
        inv = pow(A[col][col], p - 2, p)
        for j in range(col, n + 1):
            A[col][j] = A[col][j] * inv % p

        # 消去其他行
        for i in range(n):
            if i == col or A[i][col] == 0:
                continue

            factor = A[i][col]

            for j in range(col, n + 1):
                A[i][j] = (A[i][j] - factor * A[col][j]) % p

    # 最后一列就是答案
    return [A[i][n] for i in range(n)]