Can we force a chosen ciphertext to be decrypted to a chosen plaintext while controlling only $e(=3)$ in RSA?

us flag

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$.

kelalaka avatar
in flag
Wait, can you control $c$ so that you can achieve $m$?
JAAAY avatar
us flag
@kelalaka Yes you can this is why I wrote chosen ciphertext.
fgrieu avatar
ng flag
See [this](, esp. #3 in the section on encryption.
kelalaka avatar
in flag
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](
ru flag

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.


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.