The title of the blog post is the answer to a decryption challenge problem in connection to a factoring problem of a 129digit number that is known as RSA129. 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 RSA129 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.

An English sentence is converted into a number according to the rule that maps A to 01, B to 02, C to 03, . . . ,Y to 25, Z to 26, with 00 representing a space between words. Call the resulting number . Then raise to 9007 and then reduce the exponentiation result modulo the following 129digit number .
11438162575788886766923577997614661201021829672124
23625625618429357069352457338978305971235639587050
58989075147599290026879543541
In modular arithmetic, the notation for this calculation is , where is the following number:
96869613754622061477140922254355882905759991124574
31987469512093081629822514570835693147662288398962
8013391990551829945157815154
The number is the ciphertext. What is the plaintext ? What is English phrase that is behind ?
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 [1] 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 129digit 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 129digit number that is known as RSA129. 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 125digit number that is a product of two 63digit 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 1024bit) may be breakable in the future.
___________________________________________________________________
Decrypting the challenge message
The modulus as indicated above is a 129digit number that is known as RSA129. 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):
3490529510847650949147849619903898133417764638493387843990820577
32769132993266709549961988190834461413177642967992942539798288533
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 .
11438162575788886766923577997614661201021829672124
23625625618428994472727416195373314872857532203455
12393667541112959643090434432
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:
12699192379026187151019849003680094594228743945957
85084518284033523340432348390555473379435474856728
2379667762974681874441038
The last column in the above table shows the remainders in the divisions. The last nonzero 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:
76830113893108432263670086472264572295083900873044
99761335618402816209615707762860613945584622883205
839698996599682534036828337
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:

(Step 1)
(Step 2)
(Step 3)
(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
10669861436857802444286877132892015478070990663393
78628012262244966310631259117744708733401685974623
06553968544513277109053606095
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 426bit 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:
20080500130107090300231518041900011805001917210501
1309190800151919090618010705
Using the predetermined mapping of A = 01, B = 02 (and so on), the numeric plaintext is converted to the following English phrase:
the magic words are squeamish ossifrage
which is the title of this blog post.
___________________________________________________________________
Remark
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.
___________________________________________________________________
Exercise
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.
20080500130107090300231518041900011805001917210501
1309190800151919090618010705
___________________________________________________________________
Reference
 Atkins D., Graff M., Lenstra, A. K. Lenstra, Leyland P. C., The magic words are squeamish ossifrage, ASIACRYPT94, Lecture Notes Comput. Sci. Volume 917, SpringerVerlag, Berlin, 1995.
___________________________________________________________________