# RSA public exponent problem

I'm trying to work out a very simple RSA algorithm with my own numbers, but I seem to be running into problems.

I chose prime numbers 13 and 17, giving me a modulus of 221. $\varphi(221) = 12 * 16 = 192$

I then chose public exponent $r=19$, and using the extended euclidian algorithm I found private exponent $s=91$. ($19\cdot 91 = 1 \ mod \ 192$)

Now I encrypt my message $42$ as: $42^{19} \ mod \ 221 = 172$. Decrypting using $172^{91} \ mod \ 221$ does indeed return the original of 42. However, if I use 19 as exponent ($172^{19} \ mod \ 221$), I also get back 42, which is clearly not what is supposed to happen. Where did I go wrong?

-

Why is that "clearly not what is supposed to happen"? Such coincidences are supposed to happen from time to time.

In particular the "gold standard" for a cryptosystem is that it behaves like a randomly chosen permutation. The coincidence you've got your hands on there is that 42 encrypts to 172 and 172 encrypts to 42. Such a two-element cycle will appear in about half or all permutations of any given size, so it is not surprising that you have found a key that gives rise to one. (It is harder to find it for larger keys because then there are a lot more than 218 possible messages for it to hide among).

-
In fact a GAP calculation appears to show that on the set of invertible elements of $\mathbf{Z}_{n}$, where $n = 221$, the permutation $x \mapsto x^{19}$ has 42 $2$-cycles (and 24 $4$-cycles). –  Andreas Caranti Feb 27 '13 at 10:32
@AndreasCaranti: Huh, that's rather a lot more than one would expect from my probabilistic quasi-reasoning. Hopefully that's only an effect of the primes being so small in the toy example. –  Henning Makholm Feb 27 '13 at 13:34