羊城杯-2025复现

• 打的时候看到这么多解，人都有点自闭，不过在当天晚上也算是做完了。不算很难，就俩道题

random

题目如下

from Crypto.Util.number import *
from gmpy2 import legendre
from secret import flag

m = bytes_to_long(flag)

p, q = getPrime(256), getPrime(256)
n = p * q

x = getRandomRange(0, n)
while legendre(x, p) != -1 or legendre(x, q) != -1:
    x = getRandomRange(0, n)
def encrypt(msg , n, x):
    y = getRandomRange(0, n) 
    enc = []
    while msg:
        bit = msg & 1
        msg >>= 1
        enc.append((pow(y, 2) * pow(x, bit)) % n)
        y += getRandomRange(1, 2**48)
    return enc

with open('output.txt', 'w') as file:
    file.write(f"n = {n}\n")
    file.write(f"x = {x}\n")
    file.write(f"enc = {encrypt(m, n, x)}\n")

本题看似是一个Goldwasser-Micali 公钥加密系统,不过有个漏洞这个y很小。
所以我们可以利用
x_inv来判断来获得可能的y^2,我们假设第一个bit是1求出低一个y后利用能否求出正确的 getRandomRange(1, 2**48) 。可以求出下一个的是否是0或1.

from sage.all import *

from Crypto.Util.number import *

from tqdm import tqdm

n = 7494062703769887703668081866565274579333132167014632821313548612356114287792191446305040778987677683423969025588609780586722302041792065732461222120206217
x = 176589407974509728660827257088337183280645510941533692756437851307282715528543669659120503474533510718918949406280646936944629296899342927397139761503564
enc = []
x_inv=inverse(x,n)
P.<d> = PolynomialRing(Zmod(n))
y0=enc[0]*x_inv % n
f="1"
for c in tqdm(enc[1:]):
	A=c*x_inv -y0% n

	poly=(A-d**2)**2-4*d**2*y0

	roots=poly.small_roots(epsilon=1/20)

	if roots:

		f="1"+f

		else:

			f="0"+f

print(f)
flag_int = int(f, 2)
print(long_to_bytes(flag_int))

lfsr

先看代码

from Crypto.Util.number import *  
from random import *  
from os import urandom  
from secret import flag  
  
  
flag = flag.strip(b"DASCTF{").strip(b"}")  
m = bytes_to_long(flag)  
LENGTH = m.bit_length()  
  
  
class LFSR():  
    def __init__(self,length):  
        self.seed = urandom(32)  
        self.length = length  
        seed(self.seed)  
  
    def next(self):  
        return getrandbits(self.length)  
  
def rotate(msg,l=1):  
    temp = bin(msg)[2:].zfill(LENGTH)  
    return int(temp[l:] + temp[:l],2)  
  
  
lfsr = LFSR(LENGTH)  
c = []  
l = []  
for i in range(200):  
    temp = lfsr.next()  
    c.append(temp ^ m)  
    l.append(bin(temp)[2:].count("1"))  
    m = rotate(m)  
  
with open("output.txt","w") as f:  
    f.write("LENGTH = " + str(LENGTH) + "\n")  
    f.write("c = " + str(c) + "\n")  
    f.write("l = " + str(l) + "\n")

+汉明重量的概念相信大家都不陌生，不过做这个题需要推导出一个东西

我们先来推导一个公式
$wt(ci​⊕mi​)=∑j​(c{i,j}​+m_{j+i}−2c_{i,j}​m_{j+i}​)$
并不是很难的东西，
首先我们要知道在xor中如果，$x,y ∈ {0,1}$
$x\oplus y=x+y-2xy$
于是汉明重量:
$wt(c_i\oplus m_i)=\sum_j(c_{i,j}+m_{i+j}-2c_{i,j}m_{j+i})$
提取得到
$\sum j(1-2c{i,j})m_{j+i}=wt(c_i\oplus m_i)-wt(c_i)$
然后$wt(c_i \oplus m_i)=l_i$
我们把他放进pulp这种线性规划求解就行了
或者你也可以用矩阵的形式

import ast  
  
from Crypto.Util.number import long_to_bytes  
from pulp import *  
LENGTH = 295  
c_list = []  
      
l_list =[]  
def bit_list(x, L):  
    return [(x >> (L-1-i)) & 1 for i in range(L)]  
  
def build_system(L, c_list, l_list):  
    T = len(c_list)  
    A = [[0]*L for _ in range(T)]  
    b = [0]*T  
    for i in range(T):  
        c = c_list[i]  
        cbits = bit_list(c, L)  
        wc = sum(cbits)  
        b[i] = l_list[i] - wc  
        for j in range(L):  
            coeff = 1 - 2*cbits[j]      # 1 if cbit=0, -1 if cbit=1  
            idx = (j + i) % L           # m 循环左移对应原始 m 的索引  
            A[i][idx] = coeff  
            print(idx)  
    return A, b  
  
def solve_ilp(A, b):  
    T = len(A)  
    L = len(A[0])  
    prob = LpProblem("m")  
    m_vars = [LpVariable(f"m_{j}", cat=LpBinary) for j in range(L)]  
    for i in range(T):  
        prob += (lpSum(A[i][j]*m_vars[j] for j in range(L)) == b[i])  
    prob.solve()  
    return [int(v.varValue) for v in m_vars]  
  
def bits_to_int(bits):  
    x = 0  
    for b in bits:  
        x = (x << 1) | b  
    return x  
  
def main():  
  
    A, b = build_system(LENGTH, c_list, l_list)  
    sol = solve_ilp(A, b)  
    m_int = bits_to_int(sol)  
    m_bytes = long_to_bytes(m_int)  
    print("flag:", m_bytes)  
  
if __name__ == "__main__":  
    main()