Essays/RSA Challenge

From J Wiki
Jump to: navigation, search

Original RSA Challenge

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


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

To send a secret message, each character of the message is encoded as pair of digits: 00=space, 01=A, 02=B, etc. These digits are joined together to form large decimal number (but less then RSA129 modulus itself; if 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 encrypted message. To decrypt this message recipient has to raise it to different power (called secret exponent) modulo RSA129 and the result will be 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

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

After this we may apply encryption step

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

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

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



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


How these factors can possibly help us find secret exponent and decrypt the message?
The short answer is that set of numbers mutually prime with form abelian group (called multiplicative group and denoted ) with respect to multiplication modulo . The order of this group (by definition) is equal to , Euler totient function. Once we know prime factors of we can calculate and since order of any element a divides order of the group, (modulo n), and for any e we can find d such that (modulo ), and (modulo n).

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

   load '~system/packages/math/gcd.ijs'
   phi=.q *&<: p
   ]d=.phi| 1 { ; gcd 9007,phi  NB. secret exponent
   ]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


  • [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