0
$\begingroup$

I have an RSA encryption with public key $(3,n)$ with 2048 bits modulus $n$.

I want to find the value of the plaintext $m$ so that the ciphertext (in bytes representation) value ends with \x00+MySpesificString.

$ciphertext = pow(m,e,n)$

where $m$ can be any string and ciphertext has the following format

any string+\x00+MySpesificString

How I can find the possible value of $m$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Welcome to cryptography. Did you try the cube root attack? $\endgroup$
    – kelalaka
    Commented Jul 1, 2020 at 18:02
  • $\begingroup$ i did, but unfortunately it doesnt work $\endgroup$
    – user81147
    Commented Jul 1, 2020 at 18:04
  • $\begingroup$ nope. m has no structure, it can be anything. But the cipher did. the cipher structure is anything as a prefix , and end with suffix = '\x00'+MySpecificString. for example cipher = aaaaabbbbb\x00+MySpecificString, cc22244\x00+MySpecificString, etc $\endgroup$
    – user81147
    Commented Jul 1, 2020 at 18:14
  • $\begingroup$ Is this homework or CTF? $\endgroup$
    – kelalaka
    Commented Jul 1, 2020 at 18:43

1 Answer 1

Reset to default
1
$\begingroup$

I assume this is homework (I have time imagining that this is a problem that you need to solve; if it is, turn "use real RSA padding").

Since this is assumed to be homework, I'll give you the initial steps, and let you do the rest of the work.

First off, what you're asking is to find a value $m$ such that $(m^3 \bmod n) \bmod 2^{136 } = \text{"\x00"} + \text{"MySpesificString"}$; noting hat $\text{"\x00"} + \text{"MySpesificString"}$ consists of 136 bits.

Now, we are not told anything about $n$, except that it is "2048 bits", that is, it is in the range $2^{2048} > n \ge 2^{2047}$. Now, we want a value of $m$ that would work for any $n$ in this range; we can do this if $m^3 < 2^{2047}$, and so $m^3 \bmod n = m^3$

Hence, we're looking for a value $m$ for which $m < \sqrt[3]{2^{2047}} \approx 2^{682.333}$ and for which $m^3 \equiv \text{"MySpesificString"} \pmod{2^{136}}$.

That may still sound daunting; however can we find a value $m$ that satisfies the last equations modulo $2^1$? And, if we have a value $m$ that satisfies the last equation modulus $2^k$, can we find a value $m'$ that satisfies it modulo $2^{k+1}$?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Actually i know the value of n , but it too long to write here. The specific string's len is 14 bytes. with '\x00' will be 15 bytes long. The ciphertext's len is can be any long, the prefix in ciphertext ( before '\x00' ) is can be anything. ex: it can be '4612864\x00'+ $(My 14 len Spesific String)$, or 'zx\x00'+ $(My 14 len Spesific String)$ , or anything fullfil the structure. For the m value, it can be anything, and any length. It might be more than 1 possible value of m, since the ciphertext's prefix is can be different for every possible ciphertext. $\endgroup$
    – user81147
    Commented Jul 1, 2020 at 20:10
  • $\begingroup$ @user81147: yes, I understand the problem. Did you go through the steps I outlined on how to solve it? $\endgroup$
    – poncho
    Commented Jul 2, 2020 at 11:59

Your Answer

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

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