Modern Cryptanalysis: Techniques for Advanced Code Breaking

Chapter 3. Factoring and Discrete Logarithms

The previous chapter used a hefty dose of mathematics to develop some nice cryptographic algorithms, which are still used today. Now, we are going to look at methods used to break these algorithms.

To quickly review from the end of the last chapter, factoring and discrete logarithms represent two classes of problems of growing importance in cryptanalysis. A growing number of ciphers rely on the difficulty of these two problems as a foundation of their security, including number theoretic ciphers such as RSA and algebraic ciphers such as the Diffie-Hellman key exchange algorithm. The methods themselves aren't secure; they rely on the fact that both factoring and the discrete logarithm are difficult to do for very large numbers. To date, no methods are known to solve them very quickly for the key sizes typically used.

The algorithms here may not be suitable for breaking many in-use implementations of algorithms like RSA and Diffie-Hellman, but it is still important to understand how they work. Any future developments in the fields will likely build on this material.

Factorization

Factorization refers to the ability to take a number, n, and determine a list of all of the prime factors of the number. For small numbers, we can just start going through the list of integers and seeing if they divide into n. However, this method doesn't scale well, since the numbers we are often concerned with are hundreds of digits long — of course, these numbers ...