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

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

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