# 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 $

Get *Introduction to Cryptography with Coding Theory, 3rd Edition* now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.