0
$\begingroup$

I have bumped into this challenge from a well known CTF site. I don't want to make a reference to it because I don't want this to be a hint for anyone. And also to avoid giving out the source code of the challenge I will try to describe the code. The thing is that they provide a small script with a class that implements Textbook RSA (no padding or anything). On this script $e$ is predefined and is equal to 3, so $e=3$. The other RSA parameters, like $p$,$q$,$N$,$d$ etc. are newly generated according to the protocol each time you run the script. Cryptographic randomness is also present when required (e.g in the generation of $p$ and $q$). The library pycryptodome is used for the math and random operations. So the script is stateless except for the value of $e$. The point is that along with the file of the script they provide an encrypted form of the flag "presumably" with the script they provide. The content of the flag, of course, isn't the output of the script. But decrypting the encrypted flag with the script give the actual flag. Of course there needs to be property of the RSA exploited there since the script runs with random parameters except for $e$. My question is how can someone manipulate the ciphertext in order for the plaintext to be the same regardless of the parameters $p,q,N,d$?

PS : Of course $p$ and $q$ are random primes and $N$ is their product and $d$ is the multiplicative inverse of 3 in the subgroup of inverses of $N$.

$\endgroup$
4
  • $\begingroup$ Wait, can you control $c$ so that you can achieve $m$? $\endgroup$
    – kelalaka
    Oct 13, 2022 at 16:51
  • $\begingroup$ @kelalaka Yes you can this is why I wrote chosen ciphertext. $\endgroup$
    – tur11ng
    Oct 13, 2022 at 17:32
  • $\begingroup$ See this, esp. #3 in the section on encryption. $\endgroup$
    – fgrieu
    Oct 13, 2022 at 17:34
  • 1
    $\begingroup$ This is why I've asked. Instead of lots of word you can simply give the case. fgrieu is right, it is classical cube-root attack on RSA see more on 20 years of RSA by Dan Boneh $\endgroup$
    – kelalaka
    Oct 13, 2022 at 19:30

1 Answer 1

1
$\begingroup$

This could only be the case if the ciphertext, $c$, is a perfect cube i.e. $c=m^3$ for some message/flag. In this case provided that $N$ is greater than $c$, there will be no reduction and so $c$ will not change. This is equivalent to choosing a message/flag that is less than the cube root of the smallest possible modulus.

If this is the case, direct computation of the cube root will recover the message irrespective of the modulus generated.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.