We are given a challenge which contains a Sage script, which holds the following lines of code
nbits = 1024
e = 5
flag = open("flag.txt").read().strip()
assert len(flag) <= 64
m = Integer(int(flag.encode('hex'),16))
out = open("data.txt","w")
for i in range(e):
while True:
p = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False)
q = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False)
ni = p*q
phi = (p-1)*(q-1)
if gcd(phi, e) == 1:
break
while True:
ai = randint(1,ni-1)
if gcd(ai, ni) == 1:
break
bi = randint(1,ni-1)
mi = ai*m + bi
ci = pow(mi, e, ni)
out.write(str(ai)+'\n')
out.write(str(bi)+'\n')
out.write(str(ci)+'\n')
out.write(str(ni)+'\n')
…along with a text file containing the encrypted flag. Let us first parse the file and put in a JSON structure
data = {'n' : [n0, n1, ...], 'a' : [a0, a1, ...], ...}
We see that the flag is encrypted several times, up to affine transformation. If we define a polynomial 
where
It is easy to construct 
![\phi_i = \frac{1}{N_i}\cdot \prod_k N_k \cdot [\prod_k N_k / N_i]^{-1}_{N_i}](https://s0.wp.com/latex.php?latex=%5Cphi_i+%3D+%5Cfrac%7B1%7D%7BN_i%7D%5Ccdot+%5Cprod_k+N_k+%5Ccdot+%5B%5Cprod_k+N_k+%2F+N_i%5D%5E%7B-1%7D_%7BN_i%7D&bg=ffffff&fg=000000&s=0 "\phi_i = \frac{1}{N_i}\cdot \prod_k N_k \cdot [\prod_k N_k / N_i]^{-1}_{N_i}")
using the Chinese Remainder Theorem. Clearly, 
p = data['n'][0] * data['n'][1] * data['n'][2] * data['n'][3] * data['n'][4]
PR. = PolynomialRing(Zmod(p))
f = 0
# compute the target polynomial
for i in range(0, 5):
q = p / data['n'][i]
qinv = inverse_mod(q, data['n'][i])
f = f + q * qinv * ((data['a'][i]*x + data['b'][i])^5 - data['c'][i])
# make f monic
f = f * inverse_mod(f[5], p)
print f.small_roots(X=2^512, beta=1)[0]
The code outputs the long integer representation of
PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!}
, where 
. The density of primes (well, asymptotically) is 
, so we expect 
to be quite small.
. Now, we solve the following equation
and 
. So, we may simply call 
on them and check if they divide 
. Note that we need to do this for different hypotheses (different 
).
. We cannot decrypt the message! If we look closely, we see that 
. Hmm… so, we can decrypt the message 
. And the message is the flag, which is constant. What if we sample two ciphertexts encrypting the same message but under different keys? Yes… so, basically, we have 
and 
. Then, we can combine it using CRT! This is easy!
. Because of this, the task is really trivial. We can simply compute the cubic root without taking any modulus into consideration. 
can solve this efficiently! This gives us:
, where 
. So, we have 
. The observant reader have noticed that if we remove 
, it will not wrap around 
, i.e., find 
. Now we are back in the scenario of previous challenge… so, we can use the method from before! Hence, 
. Finally, we get
. We can write this as 
. Now, we can eliminate the ordo term by taking 
. Assuming that 
, we can determine 
by simple division. So, 
. In Python, we have that
. If so, we have found a factor. Turns out two moduli have a common factor, so we can factor each of them and decrypt their traffic:
, which is a function from 4 bits to a byte. 
is an error (or pertubation) vector with only one bit set. This defines a map 
. So, each plaintext byte is two ciphertext bytes.
(compute the intersection between the Hamming ball of the ciperhext block and 
. An immediate conclusion is that we need to some kind of collision attack. But how? We cannot exploit any collision in the 
while keeping 
distinct?
, we need to perform some additional computations. Obviously, we could factor the modulus 
and compute 
and then obtain the signature as easy as 
… but factoring…
digits so not a good candidate for msieve or other factoring software… so what then? 
and 
both are prime? Then, we can easily recover the signature as 
! No need for time-consuming factoring! Embodied in Python, it could look like this:
. Then, the secret becomes 
. Notably, the first block 
contains the hash, but encrypted.
as username? Then, we have encrypted 
, but we want only 
. As mentioned before, the hash fits perfectly into a single block. So, by removing the 
, 
, which is all what we need.![\mathbb F_2[x]/P(x)](https://s0.wp.com/latex.php?latex=%5Cmathbb+F_2%5Bx%5D%2FP%28x%29&bg=ffffff&fg=000000&s=0 "\mathbb F_2[x]/P(x)")
with the mapping that, for instance, an integer 
is 
in binary, which corresponds to a polynomial 
. The code is doing 
in 
.
to be the key and 
the seed. Note that all elements are in 
is unknown.
and 
. The individual square roots exist and are unique.
with the exception that elements are in 
this time. We omitt the multiplication symbol from now on.
matrices (with elements in 
and 
.
.
via a square-and-multiply type algorithm. In python, it would be
be the random value fed to the function. Once 
is computed, it returns
. Adding this to the above yields
.
. Note that given two elements of the key stream, all these elements are known. Once determined, we compute the (dicrete) 
to find 
.
fixed to obtain the flag 
. Let us reorder the function as follows:
, since we can control 
. Equivalently, we can encrypt for different values of 
, where the trailing six bits will be the trailing six bits of 
.
time and space. This is done by putting about 
values of the encryption (or decryption) in a table. Then, we generate the decryptions (or encryptions, respectively) and look in the table.
. 
, 
. (This is not true, thanks to hellman for pointing that out in the comments).
. Having a look at the Wikipedia page, I found that this is how AES-CFB/(CBC) would behave (image from Wikipedia):
, we can inject some data into the decrypted ciphertext! Assume that we want 
. Then, we can set 
, since then 
. Embodying the above in Python, we might get something like
