# 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".

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 \sqrth \equiv h^d \pmod {2^{160}}$$.

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