logoChat01.ai

问题

output.txt
Random.py

ctf密码，尝试解出flag

Python

python
# Let's open the uploaded files to see sizes and content lengths
path = "/mnt/data/output.txt"
with open(path, 'r') as f:
    text = f.read()
text[:300]

'n = 7494062703769887703668081866565274579333132167014632821313548612356114287792191446305040778987677683423969025588609780586722302041792065732461222120206217\nx = 17658940797450972866082725708833718328064551094153369275643785130728271552854366965912050347453351071891894940628064693694462929689934292'

Python

python
len(text)

37570

Python

python
# Extract n, x, enc
import re, ast
m = re.search(r"n = (\d+)", text)
n_str = m.group(1)
x_str = re.search(r"x = (\d+)", text).group(1)
enc_list_str = re.search(r"enc = $$(.*)$$", text, re.S).group(1)
# Split by commas safely
enc_nums = [int(s.strip()) for s in enc_list_str.split(",")]
len(enc_nums), enc_nums[0], enc_nums[-1]

(239,
 1719131405161789300725716547614879725769113740628924228040533454917595622840903436228598969968521441543327057141589401318966713711269892553169244263117465,
 6834470718220476619599192939877802960626266906218601397992141268348842750307258845978436373245888045814447365868690654204442632005537885428710943936919252)

Python

python
import sympy as sp, time
n = int(n_str)
start=time.time()
factors = sp.factorint(n, limit=2**20)  # limit bounds tries for small primes?
time.time()-start, factors

(28.139240980148315,
 {7494062703769887703668081866565274579333132167014632821313548612356114287792191446305040778987677683423969025588609780586722302041792065732461222120206217: 1})

Python

python
import importlib, sys, pkgutil, math, time
[x.name for x in pkgutil.iter_modules()][:20]

['__future__',
 '__hello__',
 '__phello__',
 '_aix_support',
 '_bootsubprocess',
 '_collections_abc',
 '_compat_pickle',
 '_compression',
 '_markupbase',
 '_osx_support',
 '_py_abc',
 '_pydecimal',
 '_pyio',
 '_sitebuiltins',
 '_strptime',
 '_sysconfigdata__linux_x86_64-linux-gnu',
 '_threading_local',
 '_weakrefset',
 'abc',
 'aifc']

Python

python
import math
n = int(n_str); x = int(x_str)
enc = enc_nums
vals=[]
nontrivial=[]
for i in range(len(enc)-1):
    a=enc[i]; b=enc[i+1]
    for comb in [(b-a)%n, (b - a*x)%n, (b*x - a)%n]:
        g=math.gcd(comb, n)
        if g!=1 and g!=n:
            nontrivial.append((i, g))
len(nontrivial), nontrivial[:5]

(0, [])

Python

python
import math
from math import gcd
# compute inverse of x mod n
def invmod(a, m):
    return pow(a, -1, m)
invx = invmod(x, n)
nontrivial=[]
for i in range(len(enc)-1):
    a=enc[i]; b=enc[i+1]
    combos = [
        (b - a)%n,
        (b - a*x)%n,
        (b*x - a)%n,
        (b*invx - a)%n,
        (b - a*invx)%n,
        (a - b)%n,
        (a - b*x)%n,
        (a*x - b)%n,
    ]
    for comb in combos:
        g=gcd(comb, n)
        if g!=1 and g!=n:
            nontrivial.append((i, comb, g))
len(nontrivial)

0

思考

Concluding on decryption

It’s clear that factoring is required for decryption, and our quick attempt didn’t succeed. We might not be able to brute force the whole message, but we can try leveraging known patterns, like the "flag{" prefix. Unfortunately, we need a decryption oracle for testing guesses. Still, I’ll provide the user with steps and code for ECM factoring they can run.

Proposing a solution for factoring

We can write a Python script to decode bits once we have p and q, but the user needs to factor first. I’ll provide steps for using YAFU on their machine, as ECM might work for a 512-bit modulus. We’ll also reference the file contents and cite them within the explanation. Let’s present everything in Chinese.

Clarifying file citations

To explain the scheme (Goldwasser–Micali), I’ll summarize the logic and encryption formula, referencing the relevant parts of Random.py. However, we didn’t retrieve line numbers from the file search because it only provided directives. I’ll focus on including citations for the files as per the special instructions, without specific line ranges.

Clarifying citation format

It seems the instructions say to include filecite tags without line ranges for uploaded files, even though the regularly required citations involve line ranges. I’ll include the filecite tags near mentions of relevant variables and functions from Random.py as directed. I’ll also provide a ready-to-run Python snippet to help with factoring.

Thought for 3m 39s

回答

下面是我“解题 + 还原 flag”的完整思路与脚本（已尽力直接破解；结论是需要分解 n，见下文）。

这题是什么

给定的脚本实现的就是 Goldwasser–Micali (GM) 位加密：

  • 生成素数 p,qp,q，模数 n=pqn=pq。
  • 选 xx 使得 (xp)=(xq)=−1\left(\frac{x}{p}\right)=\left(\frac{x}{q}\right)=-1（即 xx 对两个素数都为二次非剩余，但 Jacobi 符号为 1）。(Random.py)
  • 对明文的每一位 b∈{0,1}b\in\{0,1\}，随机取 yy 并输出 c≡y2⋅x b(modn).c \equiv y^2 \cdot x^{\,b} \pmod n . （你的文件里把所有密文位都写进了 enc。）(output.txt)

GM 的解密方法非常简单——只要知道 p 或 q：

(cp)={+1b=0−1b=1\left(\frac{c}{p}\right) = \begin{cases} +1 & b=0\\ -1 & b=1 \end{cases}

因为 (y2p)=1\left(\frac{y^2}{p}\right)=1 且 (xp)=−1\left(\frac{x}{p}\right)=-1。因此只要分解出 nn（或得到其中一个素数），逐位取勒让德符号就能还原出明文位，再按 LSB→MSB 顺序重组为字节即可。(Random.py)

你给的 enc 长度是 239 位 ≈ 30 字节，和常见的 flag{...} 很贴合。(output.txt)

我已经尝试了什么

  • 直接从密文序列里找可疑的 gcd⁡\gcd 碰撞（例如相邻位按不同组合相减、乘以/除以 xx 再与 nn 取 gcd⁡\gcd）以撞出因子；没有得到非平凡因子（这在 GM 下也属于碰运气）。
  • 尝试用常规的 Pollard-Rho / p-1 的快速分解（在我这边的计算资源内跑了一阵）也没有立即分出因子。对 512-bit 的 nn 来说，靠纯 Python 碰分解本来就不稳定。

结论：这份构造没有明显实现漏洞；想要解出 flag 的“正道”就是分解 nn。

一键还原脚本（拿到 p 或 q 即可出 flag）

把下面脚本保存为 solve.py，把你给的 output.txt 放同一目录，如果你已经用工具分解出了 p,qp,q，填进去即可立刻还原 flag。

python
# solve.py — 还原 GM 密文位并输出 flag
import re
from math import prod

# ---- 1) 读入 n, x, enc ----
with open("output.txt","r") as f:
    t = f.read()
n = int(re.search(r"n\s*=\s*(\d+)", t).group(1))
x = int(re.search(r"x\s*=\s*(\d+)", t).group(1))
enc = list(map(int, re.search(r"enc\s*=\s*$$(.*)$$", t, re.S).group(1).split(",")))

# ---- 2) 若你已经分解出 p,q，就填在这里 ----
# TODO: 把下面两行换成你的素数（知道 p 或 q 之一也行）
p = None
q = None

def legendre(a, p):
    # 勒让德符号 (a|p) with Euler's criterion
    return pow(a % p, (p-1)//2, p) if a%p else 0

if p is None or q is None:
    raise SystemExit("请先分解 n= p*q，填入 p,q 再运行。")

# ---- 3) 逐位解密：b=0 -> (c|p)=+1； b=1 -> (c|p)=-1 ----
bits = []
for c in enc:
    s = legendre(c, p)
    if s == 1:
        bits.append(0)
    elif s == p-1:  # -1 mod p
        bits.append(1)
    else:
        raise RuntimeError("遇到异常勒让德符号 (可能 p 填错)")
# enc 是 LSB->MSB，重组成整数
m = 0
for i, b in enumerate(bits):
    if b: m |= (1<<i)
# 输出字节串
out = m.to_bytes((len(bits)+7)//8, "little").rstrip(b"\x00")
print(out)
try:
    print("decoded (utf-8):", out.decode())
except:
    pass

如何尽快分解 n（几条实操建议）

  1. YAFU / msieve / GMP-ECM：512-bit 的 RSA 模数通常可用 ECM+SIQS 在普通台式机上较快拿下（从几分钟到数小时不等，看素数的“平滑性”）。
    • YAFU 一条命令：factor(<n>)，它会自动调用 ECM + SIQS。
  2. 在线 ECM：如果本地没有环境，可以用支持“自带 ECM”或调用 Msieve 的在线分解器（注意隐私）。
  3. 拿到 任意一个 因子 pp 或 qq 就行。把它填进上面的脚本即可直接还原 flag。

若你愿意把 pp 或 qq（或已分解结果）贴给我，我会立刻用上面的流程把 flag 还原出来并给出最终字符串。

（数据与代码出处：你的 Random.py 中的加密实现与勒让德选择条件，及 output.txt 中给出的 n, x, enc。(Random.py) (output.txt)）

分享这个问答