1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Why are you reinventing the wheel? Use RSA OAEP for encryption and RSA-PSS for signature. $\endgroup$ – kelalaka Apr 23 at 14:04
  • $\begingroup$ it's actually curiosity in this case $\endgroup$ – S. L. Apr 23 at 14:06
  • $\begingroup$ If you are curious you should read 20 years of RSA then the OAEP and PSS. See also comments on this question. $\endgroup$ – kelalaka Apr 23 at 14:07
  • $\begingroup$ 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. $\endgroup$ – S. L. Apr 23 at 14:09
  • 1
    $\begingroup$ Related: crypto.stackexchange.com/questions/68921/… $\endgroup$ – mat Apr 23 at 14:19
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.