Efficient attack on RSA with known padding scheme and public key

Question

I am having some trouble with an assignment problem. I hope I can get some guidance here. The question provides us with a public key, $N$ and the padding scheme.

This is the padding scheme "Assume PIN is a positive integer smaller than $2^{16}$. Instead of directly encrypting the PIN, she writes the PIN in binary format first, then she appends 2048 1 bits at the right most side of the binary representation of PIN. For example, integer $abcd$ in hexadecimal becomes an integer $x$"

$c = (m^e) \bmod N$

The length of both $N$ and $C$ is 923 digits of hexadecimal.

From this knowledge we are supposed to perform an efficient attack on the ciphertext by which we can recover the plaintext.

Me and my team have tried to implement multiple cca aswell as cpa techniques, however we have been pretty much unable to find any thing that would work. Of course I understand that the trick to solving this question is in the padding, but we have yet to be able to discover how to do so.

I would appreciate any help in this regard.

---

Edit: The value of $N$ is

0xa05bb3783769b832a2d022646c48344948282cdcd42bff414ec90f23b7e3b1b817137664f4016319586395741996245f9c2c66dee453352dc329fe54228beaa559a610114dbe902c32572e954660adbd06f8da8c770c33bb5ad15f506073ea0c50ff4e9906e16ee70d1311e0ad81896f4807282361f5b2116488de06966b571cdb15da536226378bc1fba8a3476c5809b5a274a0117b5de3e52278d39fdfa62de29f338b0453ac3af61a30dcb2975949a3d0ec2d2b7f0d2c4d2e3ef6ddefa8caad21bc16972dcecfcd5f9332373a759632f7f02c52dd424b83985eaa673ce67023366e85899729fc1d1fede02fa9c53aa01328c9108a3c5145f47ef988688f3076d49821314210d1f4db88fa836d41f3dc3960499eb46b28261aaa1515e0fb6d7481ae051b607683cbfdc18d6b692f93d6facf4002d6fa835aac4d61911b66859a81043763e1d0ef6e47f1a7a4c8d57993b0fb67b5758ed3aca9540d39e150935cdd0c320d166da65612ae78322f96853885e6a44add306a899fab2f87cf2a1d

and the value for $C$ is

0x90fdea0c662ed2cef739c491c2f391d8cf636b80144c412580c02e3262e4fa10c6e101f4c53d09619c7cb6fc9d8edfe2a676c1c128bd8e32528aff243101b9daf655bcd5460a9bf020ff4bef0f61b94304b142b6b18830b8b4d5574e8b54903de67df71f39234fdf9f66723ab1bf426d1c0a95fabae8485e9edf7f4c868ca2816398b1f46ffda2a84b5d52ff36bad829ddc2e123f86cb266256824f047fb6f6a1c7593eaf4ae5c47c6f5e633370d832345fde53324d02687a9b21e60fcefb5e2e2eb1ace969fe72afca67847acad093dec8976336ace5f135257f740f625851a3258854775a3f4f123eae1a6253b2740de37d112bca596f36e4c0d4cfc50b05643b8ec0b52619ae7d0ae990e041ba01bc149ac4a510c81e3aef3f4f2843a50f15c637e274e714c6a768e0c7d96e28a5365b64aee0315623794724573648516ebc9b0f5135a180ac3141a98f2ef0f005f6980781036c9b1c7975774708d1929d1935ae782de80722124220a9dd3fadc457d8bdb8be762b0158187ee619142637d

Answer 1

As the padding is deterministic and the amount of input values is minimal, you can just try and encrypt each possible value with the public key. If the result - the ciphertext - is identical to the one you have then you've found the input value and therefore the PIN. You are guaranteed success in $2^{16}$ tries after all, that's 65536 tries in total.

Answer 2

It might help to describe the padding arithmetically: first shift $p$ (the pin) $2048$ bits to the left, so compute $2^{2048}\cdot p$. To replace the trailing $0$'s by $1$'s we add $2^{2048}-1$. So given $p$ the message to be encrypted by the RSA function is

$$m=2^k \cdot p + (2^k-1) = (p+1)\cdot 2^k - 1$$

with $k=2048$ and working in the ring $\mathbb{Z}_n$.

So finding $p$ given $C$ comes down to finding a small root of the polynomial $(Kx - 1)^e$ modulo $n$ (setting $K=2^k \pmod{n}$), and you might use Coppersmith's method to do that, e.g. in Sage or some such program. I don't have high hopes, but maybe it helps.