Introduction to Cryptography with Coding Theory, 3rd Edition

9.2 Attacks on RSA

In practice, the RSA algorithm has proven to be effective, as long as it is implemented correctly. We give a few possible implementation mistakes in the Exercises. Here are a few other potential difficulties. For more about attacks on RSA, see [Boneh].

Theorem

Let $n=pq$ have $m$ digits. If we know the first $m/4$, or the last $m/4$, digits of $p$, we can efficiently factor $n$.

In other words, if $p$ and $q$ have 300 digits, and we know the first 150 digits, or the last 150 digits, of $p$, then we can factor $n$. Therefore, if we choose a random starting point to choose our prime $p$, the method should be such that a large amount of $p$ is not predictable. For example, suppose we take a random 150-digit number $N$ and test numbers of the form $N\cdot$