The encryption oracle only allows you to encrypt a custom message $m$ or the secret message $m_s$. In both cases it asks you to choose a public exponent $e>16$. Of course, $n$, is not available.

If I had multiple queries, the first step should be to ask the oracle to encrypt two custom messages with the same exponent to compute $n$ with this GCD formula.

Then, I should ask the encrypted secret message twice $(c,c')$, with two different public exponents such that $gcd(e,e')=1$, then use the Extended GCD to get the $a,b$ coefficients.

The decrypted secret message would then be: $m_s=(c^a\mod n\cdot c'^b\mod n)\mod n$

By having only two queries, how is it possible to compute $n$ and decrypt the secret message?. Obviously, one of the two queries should be the encrypted secret message.

  • $\begingroup$ The details of the security model are kind only implicitly given in your attack description. It would be useful if you could explicitly state the security model first. From what you describe, we are not exactly in the common IND-CPA model. So knowing that helps, better understand your question and provide some help (if possible). $\endgroup$ Commented Nov 20, 2023 at 14:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.