# RSA padding: risk of using constants

Assume I want to make my RSA secure because I heard that textbook RSA, especially in conjunction with low exponents, is very risky. I decide to limit my message length to 100 and subsequently construct my padded message as follows:

m = '\x01'*70 + m + '\x01'*70


To improve performance, I choose $$e=3$$.

Why is this risky? After all, the padded message is large enough, i.e. knowing that $$c=m^3 + k*n$$, $$k$$ will be too high to bruteforce. At first glance I don't see any attacks that could work here therefore it should be safe?

• Why are you reinventing the wheel? Use RSA OAEP for encryption and RSA-PSS for signature. – kelalaka Apr 23 '19 at 14:04
• it's actually curiosity in this case – S. L. Apr 23 '19 at 14:06
• If you are curious you should read 20 years of RSA then the OAEP and PSS. See also comments on this question. – kelalaka Apr 23 '19 at 14:07
• That's actually the paper I read, based on that I didn't see anything precluding the implementation above. Edit: the question you linked is super helpful. – S. L. Apr 23 '19 at 14:09
• – mat Apr 23 '19 at 14:19

By narrowing the space of messages and ciphertexts you are willing to consider to a tiny fraction of fewer than $$1/2^{1000}$$ of them, you cannot prove that an algorithm for breaking this translates to an algorithm for computing cube roots modulo $$n$$ in general.

Consequently you can't rely on the decades of work that have been put into failing to find a way to compute cube roots modulo $$n$$, and you have to redo those decades of failure anew in order to get confidence in the system's security.

Digging around, I found a partial answer. There is a particular case of this problem when you use \x00 as a constant. In that case, it becomes trivial to reverse the encryption (under the assumption that $$e$$=3), since the message becomes:

m = '\x00' * 70 + m + '\x00'*70

The 00 bytes right-padding is essentially a left bit-shift of the original message (and the left-padding). Another way to see this is that the plaintext is multiplied by 256 for each added 00. This is the same as multiplying by the inverse modulo of 256 and $$n$$.

We can thus dervie the ciphertext without the padding by calculating:

$$c' \ = c * [modinv(256,n)*70]^e \mod n$$

Now the new ciphertext is short enough that it becomes vulnerable to a simple cubic root attack, i.e. check if $$c' + i*n$$ is a perfect cube for $$i$$ any positive integer, which is likely going to be relatively small.