Forging RSA1024 signature with e=3 where hash is right justified I am trying to understand (in the frame of exponent 3) how to calculate a "forgery" in the case where the desired result is:

xxxxxxxxxxx[...]xxxxxxxxxxxxxxxxxxxxHHHHHHHHHHH[...]HHHHHHHH

where HH = a 160 bit hash which are the least significant bytes, and xx are the remaining (1024-160) bits where I could put "garbage".

From: Is this Bleichenbacher &#39;06 style signature forgery possible? (Or more like, why isn&#39;t it?)

I understand that the hash must either have lsbit = 1 or the there must be multiples of 0 bits in 3's to assure a cube root is theoretically possible.

(I do not have "reputation" so I cannot comment in that thread)

That is trivial as I can simply re-request the challenge and test its hash to see if the value has those characteristics.

A traditional Bleichenbacher with the hash farther toward the msbit end with garbage space available to the less significant end is trivial.

Effectively trying to find x where: $$x^3\pmod{2^{128}} = h$$

Thoughts?
When $\gcd(e, \phi(n)) = 1$, integers modulo $n$ coprime to $n$ have a unique $e$th root modulo $n$.  This is the basis of RSA.  Unlike for an unfactored RSA modulus, $\phi(2^{160})$ is easy to compute: it's $2^{159}$.

You can calculate this cube root the same way that you do RSA, essentially.  Treat $2^{160}$ as if it were an RSA modulus, with $e = 3$.  Calculate $d = e^{-1} \pmod {2^{159}}$, which is the value:

$d = 243583606221817153033947472119380503275988757163$.

Now, for numbers $h$ coprime to $2^{160}$--that is, odd numbers--you can calculate the cube root as:

$x \equiv \sqrt[3]h \equiv h^d \pmod {2^{160}}$.

Because $x &lt; 2^{160}$, $x^3$ cannot exceed $2^{480}$, so it will not wrap modulo a 1024-bit RSA modulus $n$.  $x^3 \mod n$ as calculated by a signature verifier would retain the property that $x^3 \equiv h \pmod {2^{160}}$, and your forgery is complete.

Assuming that your hash's low bit is $1$, anyway.