# HITCON CTF 2019 Quals - Lost Key Again (crypto)¶

The challenge has the following code:

def read_key():
key_file = open("key")
n,e,d = map(int,key_file.readlines()[:3])
return n,e,d

def calc(n,p,input):
data = "X: "+input
num = bytes_to_long(data)
res = pow(num,p,n)
return long_to_bytes(res).encode('hex')

def read_flag():
flag = open('flag').read()
assert len(flag) >= 50
assert len(flag) <= 60
prefix = os.urandom(68)
return prefix+flag

n,e,d = read_key()
flag =  calc(n,e,read_flag())
print 'Here is the flag!', flag
for i in xrange(100):
m = raw_input('give me your X value: ')
try:
m = m.decode('hex')[:15]
print calc(n,e,m)
except:
print 'no'
exit(0)


We can encrypt messages of length up to 15 bytes, prepended by $T=$ "X: "=0x583a20. The challenge only provides encryption oracle, therefore knowing $e$ and $n$ should allow to decrypt, i.e. they must be weak in some way. This already hints about some guessing, but first we need to recover $n$ and/or $e$.

Typically, to recover the modulus, when $e$ is unknown, we use multiplicativity of RSA:

$$a^e \times b^e \equiv (a \times b)^e \pmod{n}.$$

If we compute the values on the left and on the right, they will differ by a multiple of $n$. After collecting a few of them, we recover $n$ using the GCD.

Here, due to restrictions (3-byte padding and small size), we can not find values $a,b$ such that $a,b,ab$ all have correct padding "X: ".

However, the key is to notice that we are not required to obtain one enc() on the righthand side: we can use any nontrivial relations. Let's find some!

Let $pad_t(x) := 256^tT + x$. We want to find relations of the form

$$pad_{t_1}(x_1)^{e_1} pad_{t_2}(x_2)^{e_2} \ldots = pad_{t_1'}(x_1')^{e_1'} pad_{t_2'}(x_2')^{e_2'} \ldots,$$

where all $t_i$ should be at most 15, all $x_i \le 256^{t_i}$, and all $e_i$ must be small (since we will compute the expressions on both sides in integers). How can we find them? Let's map the problem to a linear one!

One approach is to consider logarithms: taking logarithm of the equation leads to a linear equation. However, logarithms in real numbers have precision issues, which are hard to tackle with. Instead, we can make logarithms base each prime to produce a vector of integers. Equivalently, we obtain multiple linear equations.

This approach is similar to the index calculus method and some sieving methods. First, we choose a factor base $B$ made of small primes up to a chosen limit and look for values that split completely in $B$ and have correct padding $pad_t$. Note that this is doable only because we can choose small numbers $pad_t(x)$, which have high chance to split in a small factor base.

In :
from __future__ import print_function, division
from sage.all import *
from Crypto.Util.number import *
from sock import Sock
class Stop(Exception): _render_traceback_ = lambda self: None

In :
T = 0x583a20 # "X: "


Experimentally, we can find that all 53 primes below 250 make a good factorbase. Our goal is to find $53 + \epsilon$ messages that split in $B$, where $\epsilon$ is the minimum kernel dimension that we would like. The larger the kernel is, the more relations will be there, and higher chance to find small ones.

In :
# factorbase
B = set(primes(250))
# number of required relations
# more extra -> larger kernel -> smaller relations!
N = len(B) + 50

def facb(v):
res = []
for p in B:
e = 0
while v % p == 0:
e += 1
v //= p
res.append((p, e))
if v == 1: return res

In :
sources = []
vecs = []
for t in range(1, 100):
if len(sources) >= N: break
for x in range(0, 256**t-1):
if len(sources) >= N: break
v = 256**t * T + x
fac = facb(v)
if fac:
ps = {p for p, e in fac}
vecs.append([e for p, e in fac])
sources.append((t, x))
print("%3d-th/%d B-smooth number: t=%2d x=%7d factors: %r" % (len(sources), N, t, x, factor(v)))
print("Done", len(sources))

  1-th/103 B-smooth number: t= 1 x=     16 factors: 2^4 * 41 * 109 * 127 * 163
2-th/103 B-smooth number: t= 1 x=     60 factors: 2^2 * 7^2 * 17 * 19 * 103 * 227
3-th/103 B-smooth number: t= 1 x=    179 factors: 3^2 * 7 * 17 * 61 * 139 * 163
4-th/103 B-smooth number: t= 2 x=   2128 factors: 2^4 * 11 * 31 * 41 * 67 * 131 * 193
5-th/103 B-smooth number: t= 2 x=   3551 factors: 3^4 * 7^2 * 61 * 83 * 109 * 173
6-th/103 B-smooth number: t= 2 x=   4096 factors: 2^12 * 41 * 109 * 127 * 163
7-th/103 B-smooth number: t= 2 x=   5216 factors: 2^5 * 3^2 * 13^3 * 29 * 107 * 193
8-th/103 B-smooth number: t= 2 x=   7738 factors: 2 * 11^2 * 13 * 47 * 103 * 139 * 179
9-th/103 B-smooth number: t= 2 x=   8222 factors: 2 * 3^3 * 5^2 * 11^3 * 23 * 53 * 173
10-th/103 B-smooth number: t= 2 x=   9522 factors: 2 * 5^3 * 7 * 71 * 113 * 137 * 197
11-th/103 B-smooth number: t= 2 x=  14342 factors: 2 * 3^2 * 5 * 13^2 * 31 * 73 * 101 * 109
12-th/103 B-smooth number: t= 2 x=  15059 factors: 3 * 7 * 53 * 67 * 113 * 193 * 233
13-th/103 B-smooth number: t= 2 x=  15360 factors: 2^10 * 7^2 * 17 * 19 * 103 * 227
14-th/103 B-smooth number: t= 2 x=  18496 factors: 2^6 * 7^2 * 11 * 31 * 37 * 61 * 157
15-th/103 B-smooth number: t= 2 x=  19112 factors: 2^3 * 3^2 * 5 * 7 * 11^2 * 47 * 137 * 193
16-th/103 B-smooth number: t= 2 x=  19882 factors: 2 * 5 * 7 * 11 * 17^2 * 19^2 * 53 * 89
17-th/103 B-smooth number: t= 2 x=  23195 factors: 3 * 13 * 23^3 * 37 * 113 * 191
18-th/103 B-smooth number: t= 2 x=  24212 factors: 2^2 * 3 * 5 * 43^2 * 113 * 167 * 181
19-th/103 B-smooth number: t= 2 x=  26060 factors: 2^2 * 3^2 * 31 * 61 * 151 * 191 * 193
20-th/103 B-smooth number: t= 2 x=  29687 factors: 3^3 * 5 * 31 * 47 * 53 * 163 * 223
21-th/103 B-smooth number: t= 2 x=  29888 factors: 2^6 * 3 * 23 * 43 * 59 * 149 * 227
22-th/103 B-smooth number: t= 2 x=  30256 factors: 2^4 * 7^2 * 19 * 23 * 73 * 109 * 139
23-th/103 B-smooth number: t= 2 x=  31187 factors: 3 * 5 * 7^2 * 17 * 19 * 37 * 179 * 241
24-th/103 B-smooth number: t= 2 x=  35766 factors: 2 * 11 * 13 * 19^2 * 97 * 157 * 241
25-th/103 B-smooth number: t= 2 x=  36032 factors: 2^6 * 3^6 * 5 * 17 * 19 * 47 * 107
26-th/103 B-smooth number: t= 2 x=  42800 factors: 2^4 * 3^2 * 7^2 * 29 * 31^2 * 41 * 47
27-th/103 B-smooth number: t= 2 x=  44753 factors: 3^3 * 7 * 11 * 17 * 19 * 31 * 109 * 167
28-th/103 B-smooth number: t= 2 x=  45824 factors: 2^8 * 3^2 * 7 * 17 * 61 * 139 * 163
29-th/103 B-smooth number: t= 2 x=  46048 factors: 2^5 * 7 * 29^2 * 89 * 97 * 233
30-th/103 B-smooth number: t= 2 x=  49637 factors: 3 * 5 * 11 * 13 * 71 * 97 * 113 * 227
31-th/103 B-smooth number: t= 2 x=  50612 factors: 2^2 * 3^7 * 5 * 7 * 13 * 31 * 37 * 83
32-th/103 B-smooth number: t= 2 x=  51536 factors: 2^4 * 3 * 7 * 17 * 19 * 79 * 193 * 229
33-th/103 B-smooth number: t= 2 x=  51947 factors: 3 * 5^2 * 11 * 43^3 * 53 * 109
34-th/103 B-smooth number: t= 2 x=  52106 factors: 2 * 3^2 * 19 * 23 * 47 * 53 * 83 * 233
35-th/103 B-smooth number: t= 2 x=  55393 factors: 7^5 * 19 * 67 * 89 * 199
36-th/103 B-smooth number: t= 2 x=  56039 factors: 3^4 * 11 * 19 * 23 * 79 * 97 * 127
37-th/103 B-smooth number: t= 2 x=  60284 factors: 2^2 * 3 * 13 * 31 * 47 * 67 * 149 * 167
38-th/103 B-smooth number: t= 2 x=  62519 factors: 3^5 * 7 * 101 * 113 * 131 * 149
39-th/103 B-smooth number: t= 2 x=  62897 factors: 3^3 * 5^4 * 7 * 13 * 29 * 67 * 127
40-th/103 B-smooth number: t= 2 x=  65144 factors: 2^3 * 3 * 7^2 * 53 * 137 * 199 * 223
41-th/103 B-smooth number: t= 3 x=   3732 factors: 2^2 * 5^2 * 7^3 * 13 * 17 * 29 * 41 * 47 * 229
42-th/103 B-smooth number: t= 3 x=  12062 factors: 2 * 3^5 * 5 * 7^2 * 17^2 * 23^2 * 73^2
43-th/103 B-smooth number: t= 3 x=  47230 factors: 2 * 7 * 13 * 19 * 89 * 107 * 113 * 131 * 199
44-th/103 B-smooth number: t= 3 x=  92327 factors: 3 * 5 * 11 * 13 * 29 * 37 * 47 * 61^2 * 241
45-th/103 B-smooth number: t= 3 x= 118496 factors: 2^5 * 3^5 * 11^2 * 13^2 * 61 * 73 * 137
46-th/103 B-smooth number: t= 3 x= 135227 factors: 3^2 * 5 * 7 * 11 * 13^2 * 17 * 23 * 31 * 79 * 173
47-th/103 B-smooth number: t= 3 x= 148773 factors: 13 * 97 * 101 * 107 * 137 * 223 * 233
48-th/103 B-smooth number: t= 3 x= 167357 factors: 3^2 * 5^2 * 7 * 17 * 61 * 67^2 * 101 * 131
49-th/103 B-smooth number: t= 3 x= 226307 factors: 3^4 * 5^2 * 11^2 * 23^2 * 29 * 131 * 197
50-th/103 B-smooth number: t= 3 x= 247850 factors: 2 * 3 * 7^2 * 31 * 47 * 71 * 103 * 173 * 179
51-th/103 B-smooth number: t= 3 x= 253436 factors: 2^2 * 3 * 7^3 * 13 * 43 * 53 * 59 * 97 * 139
52-th/103 B-smooth number: t= 3 x= 289264 factors: 2^4 * 13 * 17 * 53 * 101 * 107 * 211 * 227
53-th/103 B-smooth number: t= 3 x= 296982 factors: 2 * 5^2 * 11 * 17 * 61^2 * 71 * 173 * 227
54-th/103 B-smooth number: t= 3 x= 334844 factors: 2^2 * 3 * 11^2 * 23 * 53^3 * 109 * 179
55-th/103 B-smooth number: t= 3 x= 348687 factors: 5 * 13 * 29 * 103^2 * 109 * 191 * 233
56-th/103 B-smooth number: t= 3 x= 405532 factors: 2^2 * 5^2 * 7^2 * 19 * 37 * 41 * 73 * 97^2
57-th/103 B-smooth number: t= 3 x= 500696 factors: 2^3 * 3 * 13 * 37^2 * 83 * 107^2 * 239
58-th/103 B-smooth number: t= 3 x= 502308 factors: 2^2 * 11^3 * 13 * 17 * 47 * 61 * 149 * 193
59-th/103 B-smooth number: t= 3 x= 529907 factors: 3 * 5^2 * 11 * 13 * 23 * 107 * 137 * 139 * 193
60-th/103 B-smooth number: t= 3 x= 530856 factors: 2^3 * 13^2 * 19 * 61 * 71 * 89 * 97 * 101
61-th/103 B-smooth number: t= 3 x= 544768 factors: 2^12 * 11 * 31 * 41 * 67 * 131 * 193
62-th/103 B-smooth number: t= 3 x= 578000 factors: 2^4 * 3^2 * 23 * 31^2 * 43 * 67 * 71 * 149
63-th/103 B-smooth number: t= 3 x= 630007 factors: 5^3 * 11 * 13 * 41 * 47 * 73 * 173 * 223
64-th/103 B-smooth number: t= 3 x= 642184 factors: 2^3 * 11^2 * 17 * 37 * 41 * 71 * 229 * 239
65-th/103 B-smooth number: t= 3 x= 662930 factors: 2 * 3 * 11 * 41 * 73 * 131 * 139 * 149 * 181
66-th/103 B-smooth number: t= 3 x= 674328 factors: 2^3 * 29 * 41 * 47 * 61 * 139 * 157 * 163
67-th/103 B-smooth number: t= 3 x= 674876 factors: 2^2 * 3^2 * 11 * 19 * 23 * 79 * 181 * 197 * 199
68-th/103 B-smooth number: t= 3 x= 720337 factors: 5 * 89 * 137 * 139 * 211 * 227 * 239
69-th/103 B-smooth number: t= 3 x= 736417 factors: 5 * 19 * 29 * 79 * 107 * 113 * 191 * 193
70-th/103 B-smooth number: t= 3 x= 793144 factors: 2^3 * 13^2 * 17 * 37 * 47 * 97 * 131 * 191
71-th/103 B-smooth number: t= 3 x= 841240 factors: 2^3 * 7^2 * 11 * 19 * 163 * 173 * 199 * 211
72-th/103 B-smooth number: t= 3 x= 844166 factors: 2 * 3^2 * 7 * 11 * 19 * 31 * 97 * 107^3
73-th/103 B-smooth number: t= 3 x= 909056 factors: 2^8 * 3^4 * 7^2 * 61 * 83 * 109 * 173
74-th/103 B-smooth number: t= 3 x=1004870 factors: 2 * 3^2 * 29 * 31 * 41 * 53 * 89 * 139 * 223
75-th/103 B-smooth number: t= 3 x=1033607 factors: 3^3 * 5^2 * 7 * 23 * 31 * 37 * 71 * 97 * 113
76-th/103 B-smooth number: t= 3 x=1048576 factors: 2^20 * 41 * 109 * 127 * 163
77-th/103 B-smooth number: t= 3 x=1081632 factors: 2^5 * 5^5 * 113 * 179 * 199 * 241
78-th/103 B-smooth number: t= 3 x=1081991 factors: 3^6 * 7 * 13 * 17 * 41 * 61 * 163 * 211
79-th/103 B-smooth number: t= 3 x=1108199 factors: 3^2 * 7 * 11 * 13 * 37 * 89 * 109 * 131 * 229
80-th/103 B-smooth number: t= 3 x=1111880 factors: 2^3 * 3^8 * 29 * 41 * 73 * 107 * 199
81-th/103 B-smooth number: t= 3 x=1190435 factors: 3 * 7 * 11^3 * 47^2 * 89 * 127 * 139
82-th/103 B-smooth number: t= 3 x=1262921 factors: 3 * 157 * 163 * 167 * 193 * 197 * 199
83-th/103 B-smooth number: t= 3 x=1280964 factors: 2^2 * 41 * 43 * 67 * 79 * 109 * 113 * 211
84-th/103 B-smooth number: t= 3 x=1335296 factors: 2^13 * 3^2 * 13^3 * 29 * 107 * 193
85-th/103 B-smooth number: t= 3 x=1341632 factors: 2^6 * 3^2 * 5^4 * 17 * 37 * 53 * 59 * 137
86-th/103 B-smooth number: t= 3 x=1352359 factors: 7^2 * 17 * 19^2 * 83 * 109 * 181 * 197
87-th/103 B-smooth number: t= 3 x=1366210 factors: 2 * 13 * 19 * 23 * 29 * 89 * 149^3
88-th/103 B-smooth number: t= 3 x=1407564 factors: 2^2 * 11 * 23^2 * 29 * 53 * 71 * 181 * 211
89-th/103 B-smooth number: t= 3 x=1412228 factors: 2^2 * 3^6 * 11^2 * 19 * 37 * 47 * 53 * 157
90-th/103 B-smooth number: t= 3 x=1424320 factors: 2^6 * 13 * 17 * 71 * 73 * 83 * 107 * 149
91-th/103 B-smooth number: t= 3 x=1431275 factors: 3 * 13 * 31 * 107 * 109 * 181 * 191 * 199
92-th/103 B-smooth number: t= 3 x=1468832 factors: 2^5 * 3 * 5^2 * 7^2 * 13 * 53 * 67 * 107 * 167
93-th/103 B-smooth number: t= 3 x=1518636 factors: 2^2 * 17 * 47 * 73 * 101 * 137 * 151 * 199
94-th/103 B-smooth number: t= 3 x=1530920 factors: 2^3 * 3^3 * 13 * 79 * 113 * 157^3
95-th/103 B-smooth number: t= 3 x=1629907 factors: 5^2 * 11^2 * 29 * 79 * 241^3
96-th/103 B-smooth number: t= 3 x=1646382 factors: 2 * 5^3 * 47 * 53 * 67 * 89 * 151 * 173
97-th/103 B-smooth number: t= 3 x=1684132 factors: 2^2 * 5^4 * 43 * 137 * 151 * 181 * 241
98-th/103 B-smooth number: t= 3 x=1728280 factors: 2^3 * 7 * 11^2 * 17 * 127 * 149 * 191 * 233
99-th/103 B-smooth number: t= 3 x=1771841 factors: 3^3 * 7 * 19^3 * 31 * 83 * 127 * 229
100-th/103 B-smooth number: t= 3 x=1817859 factors: 7^4 * 19 * 37 * 41^2 * 179 * 191
101-th/103 B-smooth number: t= 3 x=1837964 factors: 2^2 * 3^7 * 17^2 * 31 * 61 * 103 * 197
102-th/103 B-smooth number: t= 3 x=1897317 factors: 5 * 11^2 * 19 * 41 * 61 * 127 * 163^2
103-th/103 B-smooth number: t= 3 x=1942904 factors: 2^3 * 3^2 * 29 * 71 * 83 * 173 * 199 * 229
Done 103


In a few seconds we have found 103 $B$-smooth messages! We are looking for relations between them, let's look at the kernel. Furthermore, we are interested in small relations, since we will compute the corresponding values in integers. Let's apply LLL to the kernel first:

In :
ml = matrix(ZZ, vecs).left_kernel().matrix().LLL()
ml

Out:
(0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

Wow, a very small relation indeed! What does it correspond to?

In :
p = 1
for i, c in enumerate(ml):
if c:
t, x = sources[i]
p *= (256**t*T + x)**c
print("pad(t=%d,x=%d)^%d *" % (t, x, c))
print("= %d" % p)

pad(t=2,x=2128)^-1 *
pad(t=2,x=3551)^1 *
pad(t=3,x=544768)^1 *
pad(t=3,x=909056)^-1 *
= 1


Ouch, fractions? We can not invert since we don't know $n$... But we don't need to! We simply move the negative power to the righthand side and get the relation that we want:

$$pad_2(3551)pad_3(544768) = pad_2(2128)pad_3(909056).$$

Let's now collect a few smallest relations:

In :
rels = []
for row in ml[:7]:
rel = []
for i, c in enumerate(row):
t, x = sources[i]
v = 256**t*T + x
v = v**abs(c)
if c:
rel.append((c, t, x))
print(
" * ".join("pad(t=%d,x=%d)^%d" % (r, r, r) for r in rel if r > 0),
"=",
" * ".join("pad(t=%d,x=%d)^%d" % (r, r, -r) for r in rel if r < 0),
)
print(
" * ".join(repr(long_to_bytes(256**r*T+r)) + "^%d" % r for r in rel if r > 0),
"=",
" * ".join(repr(long_to_bytes(256**r*T+r)) + "^%d" % (-r) for r in rel if r < 0),
)
print()
rels.append(rel)

pad(t=2,x=3551)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=909056)^1
'X: \r\xdf'^1 * 'X: \x08P\x00'^1 = 'X: \x08P'^1 * 'X: \r\xdf\x00'^1

pad(t=2,x=4096)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=1048576)^1
'X: \x10\x00'^1 * 'X: \x08P\x00'^1 = 'X: \x08P'^1 * 'X: \x10\x00\x00'^1

pad(t=2,x=5216)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=1335296)^1
'X: \x14'^1 * 'X: \x08P\x00'^1 = 'X: \x08P'^1 * 'X: \x14\x00'^1

pad(t=2,x=2128)^1 * pad(t=2,x=15360)^1 = pad(t=1,x=60)^1 * pad(t=3,x=544768)^1
'X: \x08P'^1 * 'X: <\x00'^1 = 'X: <'^1 * 'X: \x08P\x00'^1

pad(t=2,x=3551)^1 * pad(t=2,x=4096)^1 = pad(t=1,x=16)^1 * pad(t=3,x=909056)^1
'X: \r\xdf'^1 * 'X: \x10\x00'^1 = 'X: \x10'^1 * 'X: \r\xdf\x00'^1

pad(t=2,x=3551)^1 * pad(t=2,x=45824)^1 = pad(t=1,x=179)^1 * pad(t=3,x=909056)^1
'X: \r\xdf'^1 * 'X: \xb3\x00'^1 = 'X: \xb3'^1 * 'X: \r\xdf\x00'^1

pad(t=2,x=14342)^1 * pad(t=2,x=15360)^1 * pad(t=2,x=19112)^1 * pad(t=2,x=19882)^1 * pad(t=2,x=49637)^1 * pad(t=2,x=60284)^1 * pad(t=3,x=334844)^1 * pad(t=3,x=500696)^1 * pad(t=3,x=544768)^1 * pad(t=3,x=674328)^1 * pad(t=3,x=841240)^1 * pad(t=3,x=1081991)^1 * pad(t=3,x=1190435)^1 * pad(t=3,x=1728280)^1 = pad(t=2,x=7738)^1 * pad(t=2,x=8222)^1 * pad(t=2,x=15059)^1 * pad(t=2,x=42800)^1 * pad(t=2,x=44753)^1 * pad(t=2,x=55393)^1 * pad(t=3,x=289264)^1 * pad(t=3,x=502308)^1 * pad(t=3,x=720337)^1 * pad(t=3,x=793144)^1 * pad(t=3,x=1048576)^1 * pad(t=3,x=1412228)^1 * pad(t=3,x=1424320)^1 * pad(t=3,x=1897317)^1
'X: 8\x06'^1 * 'X: <\x00'^1 * 'X: J\xa8'^1 * 'X: M\xaa'^1 * 'X: \xc1\xe5'^1 * 'X: \xeb|'^1 * 'X: \x05\x1b\xfc'^1 * 'X: \x07\xa3\xd8'^1 * 'X: \x08P\x00'^1 * 'X: \nJ\x18'^1 * 'X: \x0c\xd6\x18'^1 * 'X: \x10\x82\x87'^1 * 'X: \x12*#'^1 * 'X: \x1a_\x18'^1 = 'X: \x1e:'^1 * 'X:  \x1e'^1 * 'X: :\xd3'^1 * 'X: \xa70'^1 * 'X: \xae\xd1'^1 * 'X: \xd8a'^1 * 'X: \x04i\xf0'^1 * 'X: \x07\xaa$'^1 * 'X: \n\xfd\xd1'^1 * 'X: \x0c\x1a8'^1 * 'X: \x10\x00\x00'^1 * 'X: \x15\x8c\x84'^1 * 'X: \x15\xbb\xc0'^1 * 'X: \x1c\xf3e'^1  The first 6 relations are very short and should be enough to recover$n$! The others are of course still usable if needed: they have a reasonable amount of terms and small powers. In : cache = {} def query(x, t): if (x, t) not in cache: f.read_until(b"X value:") assert x < 256**t assert x < 256**15 bx = long_to_bytes(x) if x else "" bx = "\x00" * (t - len(bx)) + bx f.send_line(bx.encode("hex")) cache[x, t] = int(f.read_line().strip(), 16) return cache[x, t]  In : f = Sock("3.115.26.78 31337") f.read_until("flag! ") encflag = bytes_to_long(f.read_line().strip().decode("hex")) n = 0 for rel in rels[:6]: print("rel", rel) vl = vr = 1 for c, t, x in rel: v = query(x, t) if c < 0: vr *= v**(-c) else: vl *= v**c n = gcd(n, vl - vr) f.close() print() print("n =", n)  rel [(-1, 2, 2128), (1, 2, 3551), (1, 3, 544768), (-1, 3, 909056)] rel [(-1, 2, 2128), (1, 2, 4096), (1, 3, 544768), (-1, 3, 1048576)] rel [(-1, 2, 2128), (1, 2, 5216), (1, 3, 544768), (-1, 3, 1335296)] rel [(-1, 1, 60), (1, 2, 2128), (1, 2, 15360), (-1, 3, 544768)] rel [(-1, 1, 16), (1, 2, 3551), (1, 2, 4096), (-1, 3, 909056)] rel [(-1, 1, 179), (1, 2, 3551), (1, 2, 45824), (-1, 3, 909056)] n = 28152737628466294873353447700677616804377761540447615032304834412268931104665382061141878570495440888771518997616518312198719994551237036466480942443879131169765243306374805214525362072592889691405243268672638788064054189918713974963485194898322382615752287071631796323864338560758158133372985410715951157  Now comes the guessing part: we recovered$n$, so what? Even if we recover$e$(may be it's small?) we only have the encryption oracle... After trying basic factorization attacks on$n$, we can find that Pollard's$p-1$works:$p-1$is smooth for at some prime factor of$n$: In : p = 531268630871904928125236420930762796930566248599562838123179520115291463168597060453850582450268863522872788705521479922595212649079603574353380342938159 q = 52991530070696473563320564293242344753975698734819856541454993888990555556689500359127445576561403828332510518908254263289997022658687697289264351266523 assert n == p * q print(factor(p-1))  2 * 269 * 1013 * 1997 * 2293 * 5477 * 6521 * 8521 * 9029 * 13729 * 15511 * 16333 * 18119 * 19963 * 24329 * 25589 * 26561 * 37889 * 38231 * 38557 * 38851 * 47881 * 49477 * 49547 * 49549 * 59009 * 63149 * 64067 * 66733 * 67807 * 70139 * 76543 * 78277 * 85621 * 85991 * 88289  This allows us to recover the public exponent too, since we can apply Pohlig-Hellman's discrete logarithm method. Sage can do it for us transparently: In : f = Sock("3.115.26.78 31337") msg0 = T enc0 = query(0, 0) f.close() F = GF(p) e = F(enc0).log(F(msg0)) assert pow(msg0, e, n) == enc0 e  Out: 375469807216214245 In : d = inverse_mod(e, n - p - q + 1) long_to_bytes(pow(encflag, d, n))  Out: 'X: \xb2J\xb4\x82\xb6\x042!\x15\xce$\xf83\xd6\xd6nF?\x1an\xd6\xd0\xbc\xed<O>\xee\x97*"g\x14\xa6\xf0k%\xd6\xfa\xf4\x8a{\x05\x12\x86\xfe\x1f!\xb2\xb3\x16\xbfa\x04:^~\x1bjc4\xb2\x04\xeb\xfe\x9ayhitcon{@@@[email protected]@@}\n'

## Aftermath¶

After the CTF my colleague told me a very simple way to find $n$. In fact, it is basically the same as the 6 relations that I used, but I didn't realize their trivial structure, for example:

'X: \r\xdf'^1 * 'X: \x08P\x00'^1 = 'X: \x08P'^1 * 'X: \r\xdf\x00'^1
`

Clearly, there are arbitrary two messages and their copies padded by a null bytes!

Since we can append a null byte to any message, we obtain encryptions of $m$ and $256m$, and if we repeat for another message $m'$, we get:

$$m^e \times (256m')^e = (m')^e \times (256m)^e.$$

Since we obtain reduced modulo $n$ encryptions, the products are likely to be separated by a nonzero multiple of $n$, and $n$ can thus be recovered using a couple of $gcd$.