Previous | ToC | Next Labs: Cryptography. Part 2. Math Alive

## Why RSA is Hard to Break?

Why is such a code hard to break?

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 ys (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:

 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ? ! . - Space 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 63 33 46 45 32

Did you find the previous one easy?

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

Can you decipher the following encrypted text?