How to find m so that RSA cipher end with '\x00'+SpesificString , if we freely input the plaintext? 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$?
I assume this is homework (I have time imagining that this is a problem that you need to solve; if it is, turn &quot;use real RSA padding&quot;).
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 &quot;2048 bits&quot;, that is, it is in the range $2^{2048} &gt; 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 &lt; 2^{2047}$, and so $m^3 \bmod n = m^3$
Hence, we're looking for a value $m$ for which $m &lt; \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}$?