If you know n and r (the public encryption key), all you have to do is find an appropriate s and you can decrypt!

The problem is to find s such that

rs = 1 (mod (p-1)(q-1)).

This would be easy (using the Euclidean algorithm) if you knew r and (p-1)(q-1). Outsiders only know r and n, but they do not know p and q, even though they know the product n=p*q. So outsiders have no easy way of computing (p-1)(q-1). Finding p and q amounts to factoring the number n that you were given.

Can you crack the following code? Here n = 3071, r = 17. The following is an encrypted text. Fill in your guess for s; the computer will compute all the y^s (mod n) and attempt to translate the resulting numbers back to letters (this may fail if some of the numbers do not make sense in the hash code because they are too big; those numbers are just decoded to the default '?').

Try it! Can you crack the code?

NOTE: Here, we use a different hash code than the one we used before to represent each character as an integer: the ASCII code. It transforms the letter "A" to 65, "B" to 66,..., "Z" to 90, Space to 32, "?" to 63... We also use the charcter "?"  for all other characters that are not in the following table:

Did you find the previous one easy?

Here is another one: n = 1441499, r = 103.

Can you decipher the following encrypted text?