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.
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
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.
# 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
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:
ml = matrix(ZZ, vecs).left_kernel().matrix().LLL()
ml[0]
(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?
p = 1
for i, c in enumerate(ml[0]):
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:
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[1], r[2], r[0]) for r in rel if r[0] > 0),
"=",
" * ".join("pad(t=%d,x=%d)^%d" % (r[1], r[2], -r[0]) for r in rel if r[0] < 0),
)
print(
" * ".join(repr(long_to_bytes(256**r[1]*T+r[2])) + "^%d" % r[0] for r in rel if r[0] > 0),
"=",
" * ".join(repr(long_to_bytes(256**r[1]*T+r[2])) + "^%d" % (-r[0]) for r in rel if r[0] < 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.
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]
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$:
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:
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
375469807216214245
d = inverse_mod(e, n - p - q + 1)
long_to_bytes(pow(encflag, d, n))
'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{@@@_5m00thneSS_CAN_give_y0u_everything_@@@}\n'
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$.