帮我解出来这道密码题 from Crypto.Util.number import * from r...

Question

帮我解出来这道密码题
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)

text
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")

Answer 1

这题可以不去“猜随机数”，只用给出的 $c$ 、 $l$ 和“按位循环左移”的关系把明文 $m$ 解出来。

思路（一句话版）

每轮有

l_i=\mathrm{wt}(c_i\oplus m_i)=\mathrm{wt}(c_i)+\mathrm{wt}(m)-2\langle m_i,c_i\rangle

其中 $m_{i}$ 是把 $m$ 左旋 $i$ 位；把内积换回到 $m$ 上可得
$\langle m_i,c_i\rangle=\langle m,\mathrm{rotr}(c_i,i)\rangle$ （对 $c_i$ 右旋 $i$ 位）。
于是对任意 $i,j$ ：

\big\langle m,\ \mathrm{rotr}(c_i,i)-\mathrm{rotr}(c_j,j)\big\rangle =\frac{\mathrm{wt}(c_i)-l_i-\mathrm{wt}(c_j)+l_j}{2}

这消掉了未知的 $\mathrm{wt}(m)$ 。把上式写成整数线性方程组 $A\,m=b$ （ $m$ 是 0/1 向量、长度为 LENGTH），方程条数有 200，通常 ≥ LENGTH，即可唯一解出 $m$ 。最后把 $m$ 还原成字节并套回 DASCTF{...}。

直接可跑的解题脚本

把你比赛给的 output.txt 放到同目录，运行即可输出 flag（脚本里严格按题面那种“字符串旋转”的位序来算，避免位序搞反）。

python
# solve.py
from Crypto.Util.number import long_to_bytes
import ast
import numpy as np

def read_output(path="output.txt"):
    # 读取 LENGTH, c, l 三行
    txt = open(path, "r", encoding="utf-8").read().strip().splitlines()
    kv = {}
    for line in txt:
        k, v = line.split("=", 1)
        k = k.strip()
        v = v.strip()
        if k == "LENGTH":
            kv[k] = int(v)
        else:
            kv[k] = ast.literal_eval(v)
    return kv["LENGTH"], kv["c"], kv["l"]

def bits_str(x, L):
    return format(x & ((1<<L)-1), f"0{L}b")

def rotr_like_problem(x, k, L):
    """右旋 k 位（和题面 rotate 的字符串位序保持一致）"""
    if L == 0: return 0
    k %= L
    if k == 0: 
        return x & ((1<<L)-1)
    s = bits_str(x, L)
    return int(s[-k:] + s[:-k], 2)

def popcount_L(x, L):
    return (x & ((1<<L)-1)).bit_count()

def build_system(L, c_list, l_list):
    n = len(c_list)
    # v_i = rotr(c_i, i) 的 0/1 向量；w_i = wt(c_i)
    v_bits = []
    w = []
    for i in range(n):
        vi = rotr_like_problem(c_list[i], i, L)
        v_bits.append([int(b) for b in bits_str(vi, L)])
        w.append(popcount_L(c_list[i], L))
    v0 = np.array(v_bits[0], dtype=np.int64)

    # 构造 A m = b，使用 j=0 作基准，得到 n-1 条方程
    rows = []
    rhs = []
    for i in range(1, n):
        rows.append(np.array(v_bits[i], dtype=np.int64) - v0)  # 元素在 {-1,0,1}
        val = (w[i] - l_list[i] - w[0] + l_list[0])
        if val % 2 != 0:
            raise ValueError(f"奇偶性不符：i={i}, value={val}")
        rhs.append(val // 2)
    A = np.stack(rows, axis=0)     # shape: (n-1, L)
    b = np.array(rhs, dtype=np.int64)
    return A, b, w

def solve_m(L, c_list, l_list):
    A, b, w = build_system(L, c_list, l_list)
    # 最小二乘求解，再四舍五入到 {0,1}
    # 如果方阵可逆，此解应当就是精确的 0/1
    m_real, *_ = np.linalg.lstsq(A.astype(float), b.astype(float), rcond=None)
    m_round = np.rint(m_real).astype(int)
    # 把落在 {-1,2} 的罕见数纠正回 0/1
    m_round = np.clip(m_round, 0, 1)

    # 验证：利用原始等式检查所有 i
    m_int = int("".join(map(str, m_round.tolist())), 2)
    s = sum(m_round.tolist())  # wt(m)
    for i, (ci, li) in enumerate(zip(c_list, l_list)):
        vi = rotr_like_problem(ci, i, L)
        # 计算 ⟨m, v_i⟩：按位与后计数即可
        inner = popcount_L(m_int & vi, L)
        l_check = w[i] + s - 2*inner
        if l_check != li:
            raise AssertionError(f"校验失败：i={i}, got {l_check}, want {li}")
    return m_int

def main():
    L, c_list, l_list = read_output("output.txt")
    m_int = solve_m(L, c_list, l_list)
    # 还原字节（保持指定位长，避免丢失前导 0）
    blen = (L + 7)//8
    inner = long_to_bytes(m_int, blen)
    try:
        inner_str = inner.decode()
    except:
        inner_str = inner.decode(errors="replace")
    flag = f"DASCTF{{{inner_str}}}"
    print(flag)

if __name__ == "__main__":
    main()

使用

把题目跑出来的 output.txt 放到脚本同目录；
python3 solve.py；
终端会直接打印完整的 DASCTF{...}。

为啥可行（稍微展开）

$l_i=\mathrm{wt}(c_i\oplus m_i)$ 展开得 $\mathrm{wt}(c_i)+\mathrm{wt}(m)-2\langle m_i,c_i\rangle$ 。
由于 $m_i$ 是把 $m$ 左旋 $i$ 位，而我们要与 $c_i$ 在同一对齐下做点积（按位与后计数），只需把 $c_i$ 右旋 $i$ 位得到 $v_i$ ： $\langle m_i,c_i\rangle=\langle m,v_i\rangle$ 。
两式相减（任取 $i$ 与 $0$ ）可以消掉 $\mathrm{wt}(m)$ ，得到纯关于 $m$ 的线性方程。
200 轮通常比 LENGTH 大（或相当），解唯一；解出来后再回代逐轮验证即可确保正确性。

把你的 output.txt 跑一下就能出 flag；如果遇到报错（例如“奇偶性不符”或“校验失败”），把那段报错贴给我，我会帮你快速定位修正。

Answer 2

思路超简：因为

\begin{cases} f_1(x)=x^3-c_1\equiv 0\pmod n,\\ f_2(x)=(ax+b)^3-c_2\equiv 0\pmod n, \end{cases}

且 $m_1$ 同时是它们在模 $p$ 和模 $q$ 下的公共根，所以在环 $(\mathbb Z/n\mathbb Z)[x]$ 里这两个多项式的 $\gcd$ 必含一次因子 $(x-m_1)$ 。直接做多项式 $\gcd$ （模 $n$ ）就能把 $m_1$ 提出来，然后转成字节就是 flag。

我已按上面的做法算出了结果（验证过 $m_1^3\equiv c_1\pmod n$ 且 $(a m_1+b)^3\equiv c_2\pmod n$ ）：

flag{ddf3a17f-d87a-4c1d-b310-e589b6387b88}

如果你想自己复现，给你一段可直接跑的最短代码（用 sympy 做模 $n$ 多项式 gcd）：

python
from sympy import symbols, Poly, gcd
from Crypto.Util.number import long_to_bytes

# 题面给的参数
c1 = 5642597249335749325251776399429871072785913803371776452538366123937991818222507923973945381568798932642174716071707196330657009269440300759911107903854718
c2 = 241002164369885429814814709450757207279897911186515565017820448950034036037374569885387444570190024300219510566717738093628969673506001197289958989452266
n  = 7584268073054587943278592330300908240421397562537303520086668809875870841193530925767991551110344114782672427850808129000637869193036026426733141648971879
a, b, e = 2025, 20250420, 3

x = symbols('x')
f1 = Poly(x**3 - c1, x, modulus=n)
f2 = Poly((a*x + b)**3 - c2, x, modulus=n)

g = gcd(f1, f2)             # g 应为 x - m1
m1 = (-g.all_coeffs()[-1]) % n
assert pow(m1, e, n) == c1  # 校验
m2 = a*m1 + b
assert pow(m2, e, n) == c2  # 校验

flag = long_to_bytes(int(m1)).decode()
print(flag)  # flag{ddf3a17f-d87a-4c1d-b310-e589b6387b88}

要点回顾：

相关消息（仿射关系 $m_2=ax+b$ ）+ 相同指数、相同模数 ⇒ 在 $(\mathbb Z/n\mathbb Z)[x]$ 里有公共一次因子；
直接做多项式 gcd 就能拿到根，不需要分解 $n$ ，也不用 Coppersmith。

Answer 3

这题是“同模不同指数（Common-Modulus）”的变体：已知同一个明文 $m$ 在同一模数 $n=pq$ 下分别用指数 $e_1,e_2$ 加密，且你知道它们的乘积 $e_1e_2=3087$ 。关键关系是

c_1 \equiv m^{e_1}\pmod n,\quad c_2 \equiv m^{e_2}\pmod n,\quad \Rightarrow\quad c_1^{e_2}\equiv c_2^{e_1}\pmod n.

只要 $\gcd(e_1,e_2)=1$ ，就能用扩展欧几里得找到 $u,v$ 使 $u e_1+v e_2=1$ ，于是

m \equiv (m^{e_1})^{u}\cdot (m^{e_2})^{v}\equiv c_1^{u}\cdot c_2^{v}\pmod n.

负指数通过取模逆元解决。

下面给一段“可直接跑”的完整解法，会先从 3087 的所有因子对里自动找出满足 $\gcd(e_1,e_2)=1$ 且 $c_1^{e_2}\equiv c_2^{e_1}\pmod n$ 的那一对（这一步通常会定位到 $e_1=9,e_2=343$ ），随后做贝祖还原出 $m$ ，并转换成字节打印出 flag。

把你题面里打印出来的 flag1、flag2、n 原样填进即可得到明文/flag。

python
# solve_common_modulus_product.py
from Crypto.Util.number import long_to_bytes
from math import gcd

# ======= 把题面给的数字粘到这里 =======
c1 = int("""<把 flag1 的十进制数粘贴到这>""")
c2 = int("""<把 flag2 的十进制数粘贴到这>""")
n  = int("""<把 n 的十进制数粘贴到这>""")
prod = 3087  # e1 * e2
# =====================================

def all_coprime_factor_pairs(N: int):
    pairs = []
    for a in range(1, int(N**0.5) + 1):
        if N % a == 0:
            b = N // a
            if gcd(a, b) == 1:
                pairs.append((a, b))
                if a != b:
                    pairs.append((b, a))
    # 去重并排序，方便观察
    pairs = sorted(set(pairs))
    return pairs

def egcd(a, b):
    # 返回 (g, x, y) 使 ax + by = g = gcd(a,b)
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def mod_pow_signed(base, exp, mod):
    if exp >= 0:
        return pow(base, exp, mod)
    # 负指数：先求逆元再正幂
    inv = pow(base, -1, mod)
    return pow(inv, -exp, mod)

# 1) 穷举 3087 的互素因子对，找出满足 c1^e2 == c2^e1 (mod n) 的那一对
candidates = []
for e1, e2 in all_coprime_factor_pairs(prod):
    if pow(c1, e2, n) == pow(c2, e1, n):
        candidates.append((e1, e2))

if not candidates:
    raise SystemExit("没找到满足条件的 (e1,e2)；确认数字是否粘贴完整。")

print("候选 (e1, e2)：", candidates)

# 2) 任选一个候选对（通常唯一）做贝祖还原
e1, e2 = candidates[0]
g, u, v = egcd(e1, e2)
assert g == 1, "e1,e2 必须互素"
# u*e1 + v*e2 = 1  ⇒  m ≡ c1^u * c2^v (mod n)
m = (mod_pow_signed(c1, u, n) * mod_pow_signed(c2, v, n)) % n

# 3) 校验、输出
assert pow(m, e1, n) == c1 and pow(m, e2, n) == c2, "回代校验失败"

pt = long_to_bytes(m)
# 尝试以 utf-8 打印；看起来像 set() 的字符串就把外层多余字符去掉
try:
    s = pt.decode()
except:
    s = pt.decode(errors="replace")

print("plaintext bytes =", pt)
print("plaintext str   =", s)

说明与小结

这题的坑点在于“只给乘积 e1e2=3087”。做法是：先用 $c_1^{e_2}\equiv c_2^{e_1}\pmod n$ 在所有互素因子对里筛一遍（3087 的素因子分解为 $3^2\cdot 7^3$ ，满足互素的因子对极少，通常就是 $(9,343)$ 和 $(343,9)$ ），筛中后再做贝祖。
负指数通过 pow(base, -1, n) 求逆元即可（Python 3.8+ 原生支持）。
这整个过程 不需要分解 $n$ ，只依赖同模、互素指数 + 贝祖恒等式。

把三大数粘进去跑就能得到明文（通常就是 CTF 的 flag 字符串）。如果跑出来是带花括号的格式（如 flag{...} 或 DASCTF{...}），脚本里打印的 plaintext str 就是答案；如果内容带杂字节，发我输出我再帮你清洗一下。

Answer 4

你这个报错是因为你把我示例里的占位符尖括号也粘进去了：int("""<...""") 里开头的 < 不是数字，int() 就会抛 ValueError。把尖括号去掉，或者更稳一点——直接用一个小工具把字符串里的非数字都过滤掉再转成整数。

下面给你一份一键跑通的解法脚本，它会：

允许你把那三串超长数字随便粘进来（即便带空格、换行、甚至带 flag1= 前缀或尖括号都无所谓）；
自动从 e1e2 = 3087 里挑出互素的一对指数（其实就是 $9,343$ 或反过来）；
用贝祖恒等式复原明文 $m$ ，然后转成字节/字符串打印出来。

把三串数粘到 PASTE_HERE 这三个三引号里（只要包含完整数字就行，其他字符会被忽略），直接运行即可得到明文/flag。

python
# solve_common_modulus_robust.py
import re
from math import gcd
from Crypto.Util.number import long_to_bytes

def to_int(s: str) -> int:
    # 提取并拼接所有数字再转 int（自动忽略 < > 空格 换行 flag1= 等杂质）
    digits = re.findall(r'\d+', s)
    if not digits:
        raise ValueError("没有在输入里找到任何数字")
    return int(''.join(digits))

# ======= 把题面里你打印的三串十进制数粘到下面 =======
C1_RAW = r"""PASTE_HERE"""
C2_RAW = r"""PASTE_HERE"""
N_RAW  = r"""PASTE_HERE"""
prod = 3087
# ================================================

c1 = to_int(C1_RAW)
c2 = to_int(C2_RAW)
n  = to_int(N_RAW)

def all_coprime_factor_pairs(N: int):
    pairs = []
    for a in range(1, int(N**0.5) + 1):
        if N % a == 0:
            b = N // a
            if gcd(a, b) == 1:
                pairs.append((a, b))
                if a != b:
                    pairs.append((b, a))
    return sorted(set(pairs))

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)

def mod_pow_signed(base, exp, mod):
    if exp >= 0:
        return pow(base, exp, mod)
    inv = pow(base, -1, mod)  # Python 3.8+ 支持模逆
    return pow(inv, -exp, mod)

# 1) 在互素因子对里筛选满足 c1^e2 == c2^e1 (mod n)
cands = []
for e1, e2 in all_coprime_factor_pairs(prod):
    if pow(c1, e2, n) == pow(c2, e1, n):
        cands.append((e1, e2))
if not cands:
    raise SystemExit("没有找到满足的 (e1,e2)。请检查三串数字是否完整。")

# 通常就是 (9,343) 或 (343,9)
e1, e2 = cands[0]

# 2) 贝祖还原出 m：找到 u,v 使 u*e1+v*e2=1，m ≡ c1^u * c2^v (mod n)
g, u, v = egcd(e1, e2)
assert g == 1
m = (mod_pow_signed(c1, u, n) * mod_pow_signed(c2, v, n)) % n

# 3) 校验并输出
assert pow(m, e1, n) == c1 and pow(m, e2, n) == c2, "回代校验失败"

pt = long_to_bytes(m)
try:
    s = pt.decode()
except:
    s = pt.decode(errors="replace")

print(f"(e1, e2) = {e1, e2}")
print("plaintext bytes =", pt)
print("plaintext str   =", s)

你遇到的错误怎么修

你写的是：c1 = int("""<4636...""")，开头的 < 不是数字，所以 int() 报错。
用上面这个脚本就不会踩坑了；或者简单点，直接写：
c1 = int("4636...171594")（不要带 < > 或 flag1= 前缀）。

跑完脚本如果输出的是形如 flag{...} 或 DASCTF{...} 的字符串，那就是答案；如果看到奇怪的字节串，把输出发我，我再帮你整理一下～

问题

思考

Considering methods for linear equations

Exploring bit sampling and correlation

Considering bit sampling and masks

Exploring bit overlaps and rotation

Analyzing system of equations

Exploring flag length and solution approach

Breaking down solution steps

Refining rotation and implementation steps

回答

思路（一句话版）

直接可跑的解题脚本

使用

为啥可行（稍微展开）

问题

Python

思考

Python

Python

Python

Python

思考

Validate:

Python

Python

思考

回答

问题

Python

Python

Python

Python

思考

Handling truncation issues

Seeking user input for numbers

回答

说明与小结

问题

Python

Python

思考

Addressing computation issue

Dealing with long numbers

Ensuring correct number copy

Providing input parsing solution

回答

你遇到的错误怎么修

分享这个问答