Essays/RSA Challenge

Original RSA Challenge

In the 1977 August issue of Scientific American an article by Martin Gardner published a 129 digit number that became known as RSA129

RSA129=:114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541x
exp=:9007

This number is a product of two large primes and, together with a smaller number (9007) called the public exponent, formed the basis for a new revolutionary approach to secure communications.

To send a secret message, each character of the message is encoded as a pair of digits: 00=space, 01=A, 02=B, etc. These digits are joined together to form a large decimal number (but less then RSA129 modulus itself; if a longer message needs to be encrypted, it is split into shorter blocks which are encrypted separately). This number is raised to the power equal to public exponent (9007) modulo RSA129. The result is the encrypted message. To decrypt this message the recipient has to raise it to a different power (called the secret exponent) modulo RSA129, and the result will be the original number which can be split into 2 digit chunks and converted back into letters.

Here is an example

   A=:' ',a.{~65+i.26 NB. alphabet
   ]m=. 100x #. A i. 'PER ASPERA AD ASTRA' NB. encoded message
16051800011916051801000104000119201801

We need to make sure that our message m is mutually prime with RSA129. The chances against that would be extremely small, but we will check it anyway.

   m +. RSA129
1

After this we may apply the encryption step

   9007 RSA129&|@^~ m NB. encrypted message
22271985799044993244688288345536107614529544348331663696...

Anybody can encrypt a message but only the person who knows the secret exponent can decrypt and read it.

The original article somewhat optimistically (or pessimistically, depending) stated that it would take 40 quadrillion years to find the secret exponent and decrypt the message encrypted this way, and offered a hefty $100 prize to the first person who decrypts the following message:

message=:96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154x

Factors

Fortunately (or unfortunately, depending), the secret factors were recovered through a massive distributed effort slightly before the predicted date.

   p=:3490529510847650949147849619903898133417764638493387843990820577x
   q=:32769132993266709549961988190834461413177642967992942539798288533x
   RSA129-:p*q
1

How can these factors possibly help us find the secret exponent and decrypt the message?
The short answer is that the set of numbers mutually prime with $n$ form an abelian group (called the multiplicative group and denoted $Z_{n}^{*}$) with respect to multiplication modulo $n$. The order of this group is (by definition) equal to $\phi (n)$, the Euler totient function. Once we know the prime factors of $n=p\times q$ we can calculate $\phi (n)=(p-1)(q-1)$ and since the order of any element a divides the order of the group, $a^{\phi (n)}\equiv 1$ (modulo n), for any e we can find d such that $e\cdot d\equiv 1$ (modulo $\phi (n)$), and $(a^{e})^{d}\equiv a^{e\cdot d}\equiv a$ (modulo n).

The long answer can be found, for example, in [4].

   load 'math/misc/gcd'
   phi=.q *&<: p
   ]d=.phi| 1 { ; gcd 9007,phi  NB. secret exponent
106698614368578024442868771328920154...
   ]r=.100 #.^:_1 message RSA129&|@^ d
20 8 5 0 13 1 7 9 3 0 23 15 18 4 19 0 1 18 5 0 19 17 21 5 1 13 9 19 8 0 15 19 19 9 6 18 1 7 5
   r{A
...

References

• [1] Gardner, M. "Mathematical Games: A New Kind of Cipher That Would Take Millions of Years to Break." Sci. Amer. 237, 120-124, Aug. 1977.
• [2] Leutwyler, K. "Superhack: Forty Quadrillion Years Early, a 129-Digit Code Is Broken." Sci. Amer. 271, 17-20, 1994.
• [3] [1]
• [4] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, "Handbook of Applied Cryptography" [2]

---

Contributed by Andrew Nikitin