2025.10-切题

发表于

10月切题

pycryptojail

题目

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
#!/usr/local/bin/python3
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
import os
import subprocess

def rsagen():
    p, q = getPrime(768), getPrime(768)
    n = p * q
    e = 0x10001
    d = pow(e, -1, (p - 1) * (q - 1))
    return (n, e)

def rsaenc(pk, msg):
    n, e = pk
    m = bytes_to_long(msg[:192])
    c = pow(m, e, n)
    return long_to_bytes(c)

if __name__ == '__main__':
    secret = os.urandom(8).hex()
    flag = open('flag.txt', 'r').read().strip()

    pk = rsagen()
    while True:
        code = input('>>> ')
        if any(c not in '0123456789abcdefghijklmnopqrstuvwxyz_+-*/ ' for c in code):
            print("You can't do that!")
            continue

        template = f'flag_you_will_never_guess_this_{secret} = {flag!r}\n\nprint({code})'
        output = subprocess.run(
            ['python3', '-c', template],
            stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
        ).stdout

        print(rsaenc(pk, output).hex())

题目允许运行你输入任意的位于 0123456789abcdefghijklmnopqrstuvwxyz_+-*/ 的字符串，然后目的是计算出 flag。

恢复 n

由于输出是给 rsa 加密了，但是我们没有 rsa 模数所以第一步肯定是先恢复 n

这就非常简单了，随便输个值 m 进去，得到密文 c 肯定有

n∣me−cn\mid m^e-c

那么我们多输入几个进去做 gcd⁡\gcd 就可以拿到 n 了。

恢复 secret

接下来就是核心了，如果我们想要 print(flag)，那么我们肯定要想办法得到 secret

如果考虑爆破 secret 的话，时间复杂度是 O(1616)O(16^{16})，显然是不大现实的

我们考虑 python 的一个特征，如果我们已经定义了一个变量 abcdefghijk，再输入 abcdefghijk 的话，会有

1
2
3
4
5
6
>>> abcdefghijk=123456
>>> abcdefggggg
Traceback (most recent call last):
  File "<python-input-3>", line 1, in <module>
    abcdefggggg
NameError: name 'abcdefggggg' is not defined. Did you mean: 'abcdefghijk'?

这里就会出现一个很神奇的 trick，如果我们的输入和正确的变量最够接近，那么 NameError 就会给我们正确变量的名称

而 python 使用 Levenshtein distance 来判断是否足够接近。按照源码，No more than 1/3 of the involved characters should need changed

如果我们输入 flag_you_will_never_guess_thiszzzzzzzzzzzzzzzzz，肯定会报

1
2
3
4
Traceback (most recent call last):
  File "<python-input-4>", line 1, in <module>
    flag_you_will_never_guess_thiszzzzzzzzzzzzzzzzz
NameError: name 'flag_you_will_never_guess_thiszzzzzzzzzzzzzzzzz' is not defined

假如正确的变量是 flag_you_will_never_guess_this_648087513328cc46

如果我们有一个值和其对上，比如 flag_you_will_never_guess_thisz6zzzzzzzzzzzzzzz，就会返回

1
NameError: name 'flag_you_will_never_guess_thisz6zzzzzzzzzzzzzzz' is not defined. Did you mean: 'flag_you_will_never_guess_this_648087513328cc46'?

那么我们可以做这样子一个判断，我们输入

1
2
3
4
flag_you_will_never_guess_thisz0zzzzzzzzzzzzzzz
flag_you_will_never_guess_thisz1zzzzzzzzzzzzzzz
flag_you_will_never_guess_thisz2zzzzzzzzzzzzzzz
...

看对没有 Did you mean 的报错进行加密，如果和返回的密文一样，我们就判断这个位置是猜对的。

然后对下个位置进行

1
2
3
flag_you_will_never_guess_thiszz0zzzzzzzzzzzzzz
flag_you_will_never_guess_thiszz1zzzzzzzzzzzzzz
flag_you_will_never_guess_thiszz2zzzzzzzzzzzzzz

这样子的猜测。

计算 flag

我们拿到了正确的变量名称后面就是计算 flag 了，如果直接输入变量名称的话只会给出 flag 的密文。如何才可以想办法弄到 flag 呢？

在没有任何私钥的情况下我们似乎还有一个方式可以做，就是 Franklin–Reiter，但是有个问题就是 flag 是字符，如何才能让其拼接上其它任意的字符呢，而且我们没有 '" 可以使用，这时候题目里面就给出了提示，注意题目里有一行 if __name__ == '__main__':，这不就是一个很好的 trick，因为我们可以输入 flag_you_will_never_guess_this_648087513328cc46+__name__

，这样子就会返回 flag 和 '__main__' 的拼接。那我们把 flag 作为未知的变量，对于两个加密的式子做 gcdgcd 肯定就有共根 flag 了，就是一个简单的 Franklin–Reiter 打法了。

exp

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
from Crypto.Util.number import *
from sage.all import *
from pwn import remote

r = remote("challs1.pyjail.club", 17549)

e = 65537

def find_n():
    r.sendlineafter(b'>>> ', b'0')
    c1 = int(r.recvline(), 16)
    r.sendlineafter(b'>>> ', b'1')
    c2 = int(r.recvline(), 16)
    r.sendlineafter(b'>>> ', b'2')
    c3 = int(r.recvline(), 16)
    n = gcd([pow(12298, e) - c1, pow(12554, e) - c2, pow(12810, e) - c3])
    return n

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x**m)
    b_top, b_bot = b.quo_rem(x**m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x**(m // 2))
    e_top, e_bot = e.quo_rem(x**(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GGCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GGCD(d, r)

sys.setrecursionlimit(500000)

n = find_n()
print(n)

def get_Traceback(name):
    return f'Traceback (most recent call last):\n  File "<string>", line 3, in <module>\nNameError: name \'{name}\' is not defined\n'

h = '0123456789abcdef'
t1 = 'flag_you_will_never_guess_thisz'
t2 = 'zzzzzzzzzzzzzzzz'
correct = ''

for m in range(16):
    for i in h:
        s = t1 + t2[:m] + i + t2[m + 1:]
        r.sendlineafter(b'>>> ', s.encode())
        c = int(r.recvline(), 16)
        if pow(bytes_to_long(get_Traceback(s).encode()), e, n) != c:
            print(s)
            correct += i
            break

ts = 'flag_you_will_never_guess_this_' + correct
print(ts)
r.sendlineafter(b'>>> ', ts.encode())
c1 = int(r.recvline(), 16)
r.sendlineafter(b'>>> ', (ts + '+__name__').encode())
c2 = int(r.recvline(), 16)

x = PolynomialRing(Zmod(n), 'x').gen()
f1 = (x * 256 + ord('\n'))**e - c1
f2 = (x * 256**9 + bytes_to_long(b'__main__\n'))**e - c2
res = GGCD(f1, f2)
m = -res.monic().coefficients()[0]
print(long_to_bytes(int(m)))