Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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).

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.