RSA padding: risk of using constants

Question

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?

Answer 1

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.

Answer 2

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.