The title of the blog post is the answer to a decryption challenge problem in connection to a factoring problem of a 129-digit number that is known as RSA-129. The challenge problem was posed in 1977. Our goal here is to use this challenge problem to demonstrate how to encrypt and decrypt in the RSA algorithm. The author of this blog recently built a calculator that can handle modular exponentiation involving large numbers. The challenge problem of RSA-129 provides an opportunity to verify the calculator.
In the August 1977, Martin Gardner wrote an article called “A new kind of cipher that would take millions of years to break” in his Mathematical Games column in Scientific American. This article posed a challenge problem created by the inventors of the RSA cryptosystem. Here’s the gist of the problem.
During the 17 years after the publication of the challenge problem, no one other than the creators of the problem knew the English phrase. In 1994, a team led by Atkins, Graff, Lenstra and Leyland  cracked the code and found that the answer is the title of this blog post. The effort that led to the answer was a massive computing project that was distributed over the Internet. Their goal was to factor the 129-digit number (the modulus) into the two prime factors and . A more detailed description of the problem can also be found in a piece from MAA (see here).
Once the factors of the modulus are known, the decryption exponent was calculated using the extended Euclidean algorithm. Then raise the ciphertext to and reduce modulo . The result is the plaintext . Using the predetermined rule described earlier, the plaintext is translated back to the original English phrase. In the remainder of this post, we demonstrate how this process works with the prime factors and as a given.
The modulus is a 129-digit number that is known as RSA-129. It is the product of two prime numbers with 64 and 65 digits. Instead of taking millions of years to factor this modulus as suggested in the title of Martin Gardner’s article, it took a mere 17 years! In 1977, Rivest, one of the creators of the RSA algorithm, estimated that factoring a 125-digit number that is a product of two 63-digit prime numbers would require at least 40 quadrillion years using the best factoring algorithm available. This goes to show that what was considered hard or impossible at one point in time may one day become doable or even easy due to advances in computer power and factoring algorithms. What is considered a secure RSA modulus today (say 1024-bit) may be breakable in the future.
Decrypting the challenge message
The modulus as indicated above is a 129-digit number that is known as RSA-129. The number pair and 9007 is an RSA public key. With only the knowledge of public key represented by and and the ciphertext , how hard is it to recover the plaintext ? An answer emerged only after 17 years of the publication of the challenge. In this post, we demonstrate how to retrieve the plaintext from the ciphertext by using the prime factors and of the modulus . Here’s are the factors and (found here):
As mentioned earlier, we take the prime factors and of as a given. Then compute the product of and :
The function is important one in number theory and goes by a special name, Euler’s phi function. Then the decryption exponent is the number satisfying the following congruence relationship:
where . In other words, the number is the multiplicative inverse of modulo . The typical approach in finding is to use the extended Euclidean algorithm. Once is found, the following modular exponentiation is computed:
We use the predetermined rule to recover the original English phrase. The steps are summarized as follows:
- Using the Euclidean algorithm to compute , the greatest common divisor (GCD) of and .
- The GCD in the previous step should be 1. Performing Euclidean algorithm is so that we can work backward (the extended Euclidean algorithm) to compute modulo .
- Use the fast powering algorithm to compute .
- Use the predetermined mapping scheme to obtain the plaintext.
Step 1. Euclidean algorithm
The following is the product of and .
Next, use Euclidean algorithm to find , which should be 1. The point is that we will work backward to find the multiplicative inverse of 9007. The Euclidean algorithm consists of a series of divisions until reaching the GCD. The divisions are shown in the following matrix:
where is the following number:
The last column in the above table shows the remainders in the divisions. The last non-zero remainder (marked by *) is the GCD of 9007 and , in this case 1. Next, we apply extended Euclidean algorithm to solve the following equation:
The solution will be the decryption exponent .
Step 2. Extended Euclidean algorithm
The extended Euclidean algorithm is to take the above table of divisions and perform back substitutions. The process of doing back substitutions is logically clear but can be tedious. We use a tabular formulation of this process as shown below.
where is the following number:
Let’s explain the table for the back substitution. The first number in the first column is . The rest of the numbers in the first column are the divisors in the Euclidean algorithm. Note that the bottom number is always the GCD. The second column consists of the quotients in the Euclidean algorithm. The third column is where the back substitution takes place. It works from bottom up. At the bottom of the third column, the numbers are always 0 and 1 (in bold). To make it clear to see, there is blank row separating the bottom two rows from the rows above. The fourth column has the signs of the back substitution numbers. Starting with minus at the bottom, the signs are alternating: minus, plus, minus, plus etc (going from bottom to top).
We now demonstrate the calculation for the back substitution. The following shows the calculation for the rows labeled Step 1, Step 2, Step 3 and Step 9:
The idea is that each number is the sum of the cross multiplications of the two rows below. This recurrence relation is a more efficient way of performing extended Euclidean algorithm.
The first two rows of the above table give the solution to the equation . In the first two rows, cross multiply the divisor and back substitution columns (along with the sign) as follows:
Then is the solution to . We need to be positive. To find , simply add to . Thus is the least positive integer such that where
One additional comment about the above table. When you cross multiply divisor column and back substitution column for any two rows, the result is the GCD. In particular, when this is done on the first two rows, we solve the equation and find the multiplicative inverse of as a result.
Step 3 and Step 4. Decipher
With the decryption key solved in the above step, we are now ready to calculate the following modular exponentiation:
The standard approach is to use the fast powering algorithm. The idea is to use the binary expansion of the exponent to convert the exponentiation into a series of squarings and multiplications. The exponent is a 426-bit numbers, which means that the fast powering algorithm only requires 425 squarings and at most 425 multiplications. The algorithm is fast and efficient since it runs in polynomial time. Our calculator produces the following result:
Using the predetermined mapping of A = 01, B = 02 (and so on), the numeric plaintext is converted to the following English phrase:
which is the title of this blog post.
The above demonstration shows how to derive the decryption key from the knowledge of the two prime factors and of the modulus . Thus the prime factors and should be kept secret. Of course, the decryption key should also be kept secret so that the originator/creator of the public key is the only one who can read the encrypted messages sent to him or her.
Suppose the public key and is as above. Verify that encrypting the plaintext will derive the ciphertext given in the challenge problem. The plaintext is repeated below.
- Atkins D., Graff M., Lenstra, A. K. Lenstra, Leyland P. C., The magic words are squeamish ossifrage, ASIACRYPT-94, Lecture Notes Comput. Sci. Volume 917, Springer-Verlag, Berlin, 1995.