?CTF2025-Crypto

此篇文章只有思路，没有脚本（其实是太懒了，解出来就懒得写WP了，就靠回忆了）

week1

Basic Number theory

根据欧拉定理得，$gift=±m$，分别给gift1、gift2取模p、q下反，然后crt就好了

Strange Machine

手动测试，十六轮为一个循环

计密文为C，重复输入一个字符，第一轮为A，当第十七轮时结果同A，取第十六轮结果为B

B 异或 输入的字符（记得填充） 异或 C

beyondHex

超越hex，还有字符G，猜测17进制

python long_to_bytes(int(a,17))

certificate

最常见的证书形式，前面为数据为n、e，后面有一长串数据包含dp

可以先试试简单的（应该吧🤓）：BaseCTF2024-Crypto-naby - Naby的博客

two Es

一把梭BaseCTF2024-Crypto-naby - Naby的博客

xorRSA

找个脚本一把梭

week2

AES_mode

hint32字节，key只有16字节，异或后hint高16字节保留，则可以得到hint的值，从而得到key

密文为CBC模式加密，flag为iv，即第一轮使用flag作用iv先异或第一段明文之后加密

知道key、明文、密文，可以使用ECB模式，获取每轮的iv，从而逆推

Common RSA

求p、q：p+q的平方没有比n大多少，循环加几个n直接开根就好了（实测加4个n，加0个n也能开根但结果开出来位数啥的不对），之后p+q和p*q解方程就好了

之后会发现p-1和q-1跟e不互素，直接上AMM解，只用一个数解就可以了，参考BaseCTF2024-Crypto-naby - Naby的博客

Furious BlackCopper

hint1为p的低20位，hint2为低830-30位

可以爆破20-30位，然后copper高194位

baby Elgamal

sage用discrete_log_lambda解出x就行了

findKey in middle

key被拆成了两个16位，思路为中间相遇

分别遍历range为k1和k2求对应的pow放到字典（键为i，值为pow(3或5,i,p) ）里，之后遍历k1的字典，取模p下的反乘上x，看看k2的字典的值中是否存在，遍历到即可得到k1和k2

strange random

用MT19937Predictor一把梭

week3

week3就简单讲讲然后贴代码了（week3边写边做就有代码了）

my crypto

知识点1：已知小d求解rsa

知识点2：未知a,b,seed，求解LCG

关键点：a,b,c可能比d小

from Crypto.Util.number import *
from gmpy2 import *
from Crypto.Cipher import AES
def wienerAttack(N, e):
    cf = continued_fraction(e / N)
    convers = cf.convergents()
    for pkd in convers:
        # possible k, d
        pk, pd = pkd.as_integer_ratio()
        if pk == 0:
            continue
        
        # verify
        if (e * pd - 1) % pk != 0:
            continue
        
        # possible phi
        pphi = (e * pd - 1) // pk
        p = var('p', domain=ZZ)
        roots = solve(p ** 2 + (pphi - N - 1) * p + N, p)
        if len(roots) == 2:
            # possible p, q
            pp, pq = roots
            if pp * pq == N:
                return pp, pq, pd
    raise ValueError('Could not factor N!')
n = 
e = 
c2 = 

p, q, d = wienerAttack(n, e)
m2 = long_to_bytes(int(pow(c2, d, n)))
print(m2) # a_cryp7o_5ecure_PRNG}
p,q,d=int(p),int(q),int(d)

c1='b7a6aa2e92065c6ca0f641774daa6be7'
c1=bytes.fromhex(c1)

a=[]
while p > 0:
    a.append(p%(2**32))
    p=p>>32

s=a[::-1]
length=len(s)
t = []
for i in range(1,length):
    t.append(s[i]-s[i-1])
all_d = []
for i in range(1,length-3):
    all_d.append(gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i+2]*t[i]-t[i+1]*t[i+1])))

for d in all_d:
    d=int(abs(d))
    if not isPrime(d) or d.bit_length()!=32:
        continue
    b=(s[2]-s[1])*invert((s[1]-s[0]),d)%d
    c=(s[1]-b*s[0])%d
    
    while not isPrime(int(b)):
        b=int(b+d)
    while not isPrime(int(c)):
        c=int(c+d)
    bni=invert(b,d)
    m=int(s[0])
    keys=[b,c,d]
    print(keys)
    k = b''.join([long_to_bytes(i) for i in keys])
    for _ in range(16*2000):
        if isPrime(m) and m.bit_length()==32:
            key=long_to_bytes(m)+k
            cipher = AES.new(key,AES.MODE_ECB)
            m1 = cipher.decrypt(c1)
            if b'flag{' in m1:
                print(m1)
                exit()
        m = int((bni*(m-c))%d)

粗心的刀客塔

知识点：franklinReiter

关键点：

$$M=m>>24\\ c=(2^{24}*M+x)^e\mod n\\ leak=M^e\mod n$$

from Crypto.Util.number import *

def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic() # 
n =
c =
leak =

e = 101

b1s = []
for i in range(32, 127):
    for j in range(32, 127):
        b1=i*256**2+j*256+125
        b1s.append(b1)
for b1 in b1s:
    R.<x> = Zmod(n)[]
    g1=(2**24*x+b1)^e - c
    g2=x^e - leak

    g=-gcd(g1, g2)[0]
    flag1=long_to_bytes(int(g))
    if b'flag' in flag1:
        print(flag1)
        print(long_to_bytes(b1))
        break

BackPack

知识点：背包密码

关键点：去除已知flag头尾

a = 
b = 
flag_ = [102, 108, 97, 103, 123]
for i in range(5):
    b -= a[i] * flag_[i]
b -= a[17] * 125
a = a[5:17]
n = len(a)
L=Matrix(ZZ,n+1,n+1)
for i in range(n):
    L[i,i]=1
    L[i,-1]=a[-i-1]
L[-1,-1]=-b
x=L.LLL()
print('flag{',end="")
for i in x[0]:
    print(chr(int(i)),end="")
print('}')

Great Block Cipher

（不想看了。

知识点：AI

关键点：ChatGPT

# decryption implementation based on provided encrypt function
from typing import List

sbox = [75, 203, 236, 186, 19, 102, 179, 172, 92, 254, 54, 41, 124, 49, 195, 32, 191, 103, 157, 2, 128, 3, 156, 58, 159, 169, 189, 71, 168, 127, 109, 18, 232, 144, 40, 164, 192, 182, 181, 14, 204, 56, 226, 43, 206, 74, 129, 248, 11, 53, 72, 210, 33, 215, 250, 91, 161, 183, 239, 143, 167, 63, 152, 126, 48, 84, 146, 76, 234, 180, 107, 227, 142, 65, 147, 209, 89, 188, 225, 110, 116, 24, 150, 216, 45, 115, 95, 135, 36, 101, 138, 199, 69, 55, 86, 241, 59, 16, 83, 114, 39, 200, 151, 125, 8, 177, 198, 145, 247, 237, 171, 21, 136, 184, 185, 117, 242, 111, 119, 174, 28, 96, 246, 131, 10, 231, 130, 46, 104, 208, 38, 187, 218, 122, 139, 80, 79, 235, 64, 47, 238, 99, 140, 163, 90, 30, 252, 93, 173, 31, 249, 7, 9, 155, 230, 42, 82, 205, 57, 148, 240, 133, 0, 178, 165, 17, 213, 20, 222, 50, 221, 97, 137, 176, 243, 25, 113, 175, 220, 224, 118, 12, 166, 141, 202, 51, 61, 193, 158, 245, 134, 123, 211, 196, 1, 4, 244, 253, 22, 108, 201, 223, 73, 228, 212, 27, 78, 60, 153, 207, 219, 85, 88, 197, 121, 120, 70, 6, 233, 162, 105, 100, 112, 229, 214, 81, 23, 44, 13, 67, 15, 98, 37, 170, 149, 62, 132, 190, 251, 34, 217, 87, 29, 35, 68, 194, 5, 255, 52, 160, 66, 94, 26, 154, 77, 106]

inv_sbox = [0]*256
for i,v in enumerate(sbox):
    inv_sbox[v]=i

def xor_bytes(a: bytes, b: bytes) -> List[int]:
    return [x^y for x,y in zip(a,b)]

def generate_ks(key: bytes):
    ks = [key[:4], key[4:8], key[8:12], key[12:]]
    for i in range(16*4):
        nk = 0
        for j in range(4):
            nk = int.from_bytes(ks[i+j],'big') ^ (3377808869 * nk % (1<<32))
        ks.append(nk.to_bytes(4,'little'))
    return ks

# build linear mixing matrix and its inverse mod 256
def build_mix_matrix():
    b = [10, 13, 3, 11, 7, 9, 0, 15, 5, 12, 8, 4, 6, 14, 2, 1]
    # matrix M such that a = M * m (mod 256), where m is 16-vector of bytes
    M = [[0]*16 for _ in range(16)]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                row = 4*i + j
                col = j + 4*k
                M[row][col] = (M[row][col] + b[4*i+k]) % 256
    return M

def mat_vec_mul(M, v):
    return [sum((M[i][j]*v[j] for j in range(16)))%256 for i in range(16)]

def mat_inv_mod256(M):
    # Gauss-Jordan to invert matrix modulo 256
    n = len(M)
    # make augmented matrix
    A = [[M[i][j] % 256 for j in range(n)] + [1 if i==j else 0 for j in range(n)] for i in range(n)]
    # forward elimination
    def egcd(a,b):
        if b==0: return (a,1,0)
        g,x1,y1 = egcd(b, a%b)
        return (g, y1, x1 - (a//b)*y1)
    for col in range(n):
        # find pivot with gcd(pivot,256)=1
        pivot = None
        for r in range(col, n):
            if A[r][col] % 2 == 1:  # odd => invertible mod256
                pivot = r
                break
        if pivot is None:
            raise ValueError("Matrix not invertible mod 256")
        if pivot != col:
            A[col], A[pivot] = A[pivot], A[col]
        inv = pow(A[col][col], -1, 256)
        # normalize row
        for j in range(2*n):
            A[col][j] = (A[col][j] * inv) % 256
        # eliminate other rows
        for r in range(n):
            if r==col: continue
            factor = A[r][col]
            if factor:
                for j in range(col, 2*n):
                    A[r][j] = (A[r][j] - factor * A[col][j]) % 256
    invM = [[A[i][j+n] for j in range(n)] for i in range(n)]
    return invM

M = build_mix_matrix()
M_inv = mat_inv_mod256(M)

def invert_bit_permutation(word_bytes: bytes, i_index: int) -> bytes:
    # word_bytes : 4 bytes big-endian as produced by encryption step
    d = i_index + 3
    out_int = int.from_bytes(word_bytes, 'big')
    c = bin(out_int)[2:].zfill(32)
    # prepare b list lengths
    c1, c2 = 32//d, 32%d
    b_parts = ['']*d
    # fill column-wise as algorithm did when constructing c
    pos = 0
    for j in range(c1+1):
        for k in range(d):
            if len(b_parts[k]) < (c1+1 if k < c2 else c1):
                b_parts[k] += c[pos]
                pos += 1
    a = ''.join(b_parts)
    orig_int = int(a,2)
    orig_bytes = orig_int.to_bytes(4, 'little')  # original used little endian
    return orig_bytes

def decrypt_block(cipher_block: bytes, ks, iv_prev: bytes):
    m = list(cipher_block)
    # reverse rounds
    for loop in reversed(range(16)):
        # invert final xor of this loop: xor with ks for this loop+1
        round_key = b''.join(ks[4*(loop+1):4*(loop+2)])
        m = xor_bytes(bytes(m), round_key)
        if loop < 15:
            # invert linear mix using M_inv
            m = mat_vec_mul(M_inv, m)
        # invert the 4 word bit-permutation
        newm = [0]*16
        for i in range(4):
            word_out = bytes(m[4*i:4*i+4])
            orig = invert_bit_permutation(word_out, i)
            # orig is 4 bytes little-endian, assign values to newm in order
            for j in range(4):
                newm[4*i+j] = orig[j]
        m = newm
        # invert sbox substitution
        m = [inv_sbox[byte] for byte in m]
    # after rounds, invert initial xors: note encryption did m = xor(m, iv) then xor with ks[:4]
    m = xor_bytes(bytes(m), b''.join(ks[:4]))
    m = xor_bytes(bytes(m), iv_prev)
    return bytes(m)

# provided data
what = b'www.bilibili.com/video/BV1ox4y1e71S'
key, iv = what[:16], what[-16:]
cipher_hex = "aa624dc4a26a879cbdc61585e1c92650d5d84c9195508d73172008e3bf1cf6edfa5eb1d1590b0de1424a563c91aeb5d8"
cipher = bytes.fromhex(cipher_hex)

ks = generate_ks(key)

# decrypt blocks
plain = b''
block_count = len(cipher)//16
prev_iv = iv
for i in range(block_count):
    cblock = cipher[16*i:16*(i+1)]
    dec = decrypt_block(cblock, ks, prev_iv)
    plain += dec
    prev_iv = cblock  # chaining used iv = m_final

print("decrypted (raw):", plain)
# remove padding
pad_len = plain[-1]
print("pad_len:", pad_len)
print("plaintext:", plain[:-pad_len])

期末考试

知识点：矩阵对角化，相似矩阵，特征向量

关键点：缩放

p = 251
D = [[221, 145, 242, 96, 133, 32], [79, 42, 48, 69, 127, 19], [222, 112, 115, 170, 108, 76], [112, 122, 165, 137, 67, 164], [29, 148, 80, 173, 33, 72], [92, 101, 143, 18, 14, 109]]
D=matrix(GF(p),D)

# 特征值
A=D.eigenvalues()

# 特征向量
B=[vector[0] for (_,vector,_) in D.eigenvectors_right()]

# 验证
mat_B=matrix(GF(p),B).transpose()
assert mat_B*matrix(GF(p),diagonal_matrix(A))*mat_B.inverse()==D

# 缩放
k=[102,108,97,103,123]

n=len(B)
flag=[""]*n
for b in B:
    ind=-1
    for i in range(len(k)):
        m=""
        x=k[i]*inverse_mod(int(b[0]),p)%p
        for j in b:
            tmp=int(x*j%p)
            if 33<=tmp<=126:
                m+=chr(tmp)
        if len(m)==n:
            ind=i
            break
    if ind!=-1:
        flag[ind]=m
    else :
        # 最后一个用'}'处理
        x=125*inverse_mod(int(b[n-1]),p)%p
        m=""
        for j in b:
            tmp=int(x*j%p)
            m+=chr(tmp)
        flag[n-1]=m
for i in range(n):
    for j in range(n):
        print(flag[j][i],end="")

*abc equation

week4

不想看了

Myneighbors

我不会，长大后再来学习

Isogeny | 糖醋小鸡块的blog

p较小，直接爆破magical_num

from secret import magical_num, flag
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib 

p = 431
F.<i> = GF(p^2, modulus = x^2 + 1)	# 扩域 p^2个元素，所以magical_num可以爆破
E = EllipticCurve(j=F(magical_num))
assert E.is_supersingular()	# E是超奇异椭圆曲线

# 鸡块博客2.4.2.2. 2
P = E(0).division_points(2)[1:] # 阶为2的所有点，排除第一个（无限远点）

neighbors = []  # 根据所有阶为2的点（子群）生成同源
for idx in range(len((P))):
    phi = E.isogeny(P[idx]) # 映射关系
    EE = phi.codomain() # 对应曲线
    neighbors.append(EE.j_invariant())  # 对应J不变量

assert E.j_invariant() in neighbors

P = E(0).division_points(3)[1:]
shuffle(P)

phi = E.isogeny(P[0])
E = phi.codomain()
H = hashlib.md5(str(E.j_invariant()).encode()).hexdigest().encode()
key, iv = H[:16], H[16:]

aes = AES.new(key, AES.MODE_CBC, iv)
cipher = aes.encrypt(pad(flag, 16))
print(f'cipher: {cipher.hex()}')
#cipher: 49e90a91357fef12c54234b3cb553bb2fdd61f2af8c7e78b3d5ffdeac7022af0

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib 

cipher=bytes.fromhex("49e90a91357fef12c54234b3cb553bb2fdd61f2af8c7e78b3d5ffdeac7022af0")

p = 431
F.<i> = GF(p^2, modulus = x^2 + 1)

for magical_num in range(p^2):
    E = EllipticCurve(j=F(magical_num))
    if E.is_supersingular():
        P = E(0).division_points(2)[1:]
        neighbors = []
        for idx in range(len((P))):
            phi = E.isogeny(P[idx])
            EE = phi.codomain()
            neighbors.append(EE.j_invariant())

        if E.j_invariant() in neighbors :

            P = E(0).division_points(3)[1:]
            shuffle(P)
            for p0 in P:
                try:
                    phi = E.isogeny(p0)
                    E = phi.codomain()
                    H = hashlib.md5(str(E.j_invariant()).encode()).hexdigest().encode()
                    key, iv = H[:16], H[16:]

                    aes = AES.new(key, AES.MODE_CBC, iv)
                    flag = aes.decrypt(cipher)
                    if b'flag' in flag :
                        print(flag)
                except:
                    pass

linear function?

很神奇，原来我用的的AMM居然开不出来根，最后换了Dexter师傅的就出来了。

2023MoeCTF | DexterJie’Blog

from Crypto.Util.number import *
from gmpy2 import *
import random
import time
P = 208351617316091241234326746312124448251235562226470491514186331217050270460481
G = GF(P)

g1 = 165341976123736548335459112293962522231127264153295903604264502197418873026337
g2 = 170915747120703530230385586293442518689765397278386308589786290207533442146523
pk1 = 11589158479692898111868014330824763021736695091380856551306940309853826892678
pk2 = 56614577954354505447188182303177869506146009993379305915003210547359661002599
c1 = 203767997651769026611878084970895835495584375049533533997092667742078368771381
c2 = 42280289742972723242969330279542671973937468908942256409868101442841553691921


x=discrete_log(G(pk1), G(g1))
y=discrete_log(G(pk2), G(g2))


my=c1
mx=(c2*inverse_mod(int(pow(g2,x,P)),P))%P

phi=P-1
m3=int(pow(mx,inverse_mod(x//3,phi),P))
print(m3)

p=P
e=3
c=m3

def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(d, a)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

def onemod(p,r): 
    t=p-2 
    while pow(t,(p-1) // r,p)==1: 
        t -= 1 
    return pow(t,(p-1) // r,p) 
 
def solution(p,root,e):  
    g = onemod(p,e) 
    may = set() 
    for i in range(e): 
        may.add(root * pow(g,i,p)%p) 
    return may

cp = c % p

mp = AMM(cp,e,p)

mps = solution(p,mp,e)
for i in mps:
    m=int(i)
    for q in range(1000):
        x=long_to_bytes((m-q*114514114514)%P)
        if b'flag' in x and x[-1]==125:
            print(x)
# flag{pair1n9_13_s000_fun}

Xaleid◆scopiX

输入空字符获取basis

输入单字符逆一下得到prime(求basis的逆可能会失败)

求s3直接拼接即可

输入logout开启新一轮，s1为空，s2为admin，后面拼接即可

from Crypto.Util.number import *
from pwn import *


def kaleidoscope(basis,prime,msg):
    r = basis
    for i in msg:
        r = r * prime % (1 << 128)
        r = r ^ i
    return r

sh=remote('challenge.ilovectf.cn',30814)

key=int(sh.recvline().split(b': ')[1].strip())

sh.sendlineafter(b'name: ',b'')
sh.recvuntil(b'Hello, ')
s1=int(sh.recvuntil(b'!')[:-2])

sh.sendlineafter(b'account: ',b'1')
s2=int(sh.recvline().split(b': ')[1].strip())

basis=s1
prime=((s2^ord('1'))*inverse(basis,1<<128))%(1<<128)
print(basis,prime)

s3=kaleidoscope(key,prime,b'1')
sh.sendlineafter(b'password: ',str(s3).encode())

sh.sendlineafter(b'operation: ',b'logout')

key=int(sh.recvline().split(b': ')[1].strip())

sh.sendlineafter(b'name: ',b'')
sh.recvuntil(b'Hello, ')
s1=int(sh.recvuntil(b'!')[:-2])

sh.sendlineafter(b'account: ',b'admin')
s2=int(sh.recvline().split(b': ')[1].strip())

s3=kaleidoscope(key,prime,b'admin')
sh.sendlineafter(b'password: ',str(s3).encode())
sh.sendlineafter(b'operation: ',b'flag')
print(sh.recvline())

sh.close()

ezECC

学会了吗？如会

参考4.2.1：躲猫猫 | 糖醋小鸡块的blog

from Crypto.Util.number import *
from sage.modular.overconvergent.hecke_series import ech_form
from sage.coding.decoder import Decoder, DecodingError
from sage.coding.grs_code import GeneralizedReedSolomonCode
import random

class Syndrome_decode(Decoder):
    def __init__(self, code):
        super(Syndrome_decode, self).__init__(code, code.ambient_space(),
                "EvaluationVector")

    def _repr_(self):
        return "Key equation decoder for %s" % self.code()

    def _partial_xgcd(self, a, b, PolRing):
        prev_t = PolRing.zero()
        t = PolRing.one()

        prev_r = a
        r = b

        while(r.degree() >= t.degree()):
            q = prev_r.quo_rem(r)[0]
            prev_r, r = r, prev_r - q * r
            prev_t, t = t, prev_t - q * t

        return (r, t)
    
    def _forney_formula(self, error_evaluator, error_locator):
        C = self.code()
        alphas = C.evaluation_points()
        col_mults = C.parity_column_multipliers()
        ELPp = error_locator.derivative()
        F = C.base_ring()
        zero, one = F.zero(), F.one()
        e = []

        for i in range(C.length()):
            alpha_inv = one/alphas[i]
            if error_locator(alpha_inv) == zero:
                e.append(-alphas[i]/col_mults[i] * error_evaluator(alpha_inv)/ELPp(alpha_inv))
            else:
                e.append(zero)

        return vector(F, e)

    def decode(self,S):
        C = self.code()

        PolRing = C.base_field()['x']
        x = PolRing.gen()
        
        S = PolRing([i for i in S])

        a = x ** (C.minimum_distance() - 1)

        (EEP, ELP) = self._partial_xgcd(a, S, PolRing)

        e = self._forney_formula(EEP, ELP)
        return e
n, k = 255, 223
F = GF(2^8, repr='int')

r=n-k
S=
S = matrix(F, r, r, [F._cache.fetch_int(x) for x in S])

P=
P = matrix(F, n, n, [F._cache.fetch_int(x) for x in P])


key=
key=vector(F,[F._cache.fetch_int(x) for x in key])

C = codes.GeneralizedReedSolomonCode(F.list()[1:],k)

T=S^(-1)*key
H = C.parity_check_matrix()
D = Syndrome_decode(C)
res = D.decode(T)
res=(res*P.T.inverse()).list()


from Crypto.Cipher import AES
import hashlib 

c= 
key = hashlib.sha256(str(res).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
flag = aes.decrypt(c)
print(flag)