# Efficient attack on RSA with known padding scheme and public key

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 ﬁrst, 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

• The padding is deterministic; that is, if you encrypt a specific PIN, you'll always get the same ciphertext, correct??? – poncho May 30 '19 at 15:08
• I certainly hope that your team didn't spend ages on the result if it is deterministic. Could you indicate what you have tried so far? – Maarten Bodewes May 30 '19 at 15:20
• @poncho yes it is deterministic. If I pad and than encrypt the message "Pin", each time I will get the same ciphertext. – Chow Suey May 30 '19 at 16:35
• @MaartenBodewes As mentioned we have tried multiple cca's and cpa techniques. We failed at cca because we do not have the right to decrypt the chosen cipher texts. I also tried to reverse engineer using the multiplicative property of rsa but again we failed since we couldn't actually figure out the math. If there is even any way to do so using the multiplicative property. Unfortunately this is our first cyber security unit and we have not been taught any techniques that can be used to break such an encryption. Any help will be greatly appreciated. Thanks. – Chow Suey May 30 '19 at 16:41
• @Rup The exponent we are working with is 0x10001 or 65537 which is pretty big compared to 3. Brute force is ofcourse the simplest way to solve any problem. But for this assignment we are supposed to figure out an efficient attack so brute force is not the way to go. – Chow Suey May 30 '19 at 19:11

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.

• Yes that is a possible way. But the question is asking us to do it using an efficient method and brute force is not allowed. Thanks for the help though. – Chow Suey May 30 '19 at 18:58
• Are you sure? Because this is so efficient that any computer will return the result almost instantly, and it doesn't brute force the private key. – Maarten Bodewes May 30 '19 at 19:01
• Yes bruteforce is definitely not the way to go. It was actually the first thing I tried, to find out the actual answer for the question so I could compare that to when I eventually find the answer. – Chow Suey May 30 '19 at 19:13
• @ChowSuey I think it is the intended solution, or they would have asked a longer pin. – Henno Brandsma Jun 5 '19 at 17:54

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.