Factoring and Discrete Logarithms - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 48

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
problemsofgrowingimportanceincryptanalysis. Agrowingnumberofciphersrelyonthedifficultyofthesetwo
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.
3.1 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 are hundreds of digits long merely because that is the time-security tradeoff
point, since the algorithms presented here start to drag their feet, so to speak, around that point.
In the previous chapter we learned about RSA, which uses exponentiation of numbers by public and private
exponents. If we recall, the first step in the RSA algorithm to create these exponents is to construct a number n =
pq, where p and q are both large prime numbers. Since we know p and q, we can calculate the totient of n , ϕ ( n )
= ( p - 1)( q - 1), which we then use to find two numbers, e and d, such that ed ≡ 1 (mod ( p - 1)( q - 1)). The
numbers e and n will be made public and can be used to communicate securely with anyone who knows d and n.
However, if anyone were to be able to factor n into its two prime factors, then they could easily calculate d using
the extended Euclidean algorithm (as that is exactly how d was originally derived), allowing them to read any
messages encrypted with e and n.
RSA is therefore very reliant on factoring large values of n to be a difficult problem, or its security will be
compromised. The following sections discuss the fundamental algorithms for factoring numbers.
Note that there are, theoretically, other ways to break RSA. For instance, since an attacker has access to the
public key, (e, n), then he could take a message (perhaps a very cleverly constructed message) and encrypt it,
knowing that when this encrypted message is encrypted again with the private key, and therefore exponentiated
by d modulo n, there may be some clever way to derive d. However, at this time, no such method is known.