I studied some encryption and decryption and I have found some very interesting problem to solve on the internet. I hope I am writing to right site - there are so many in StackExchange otherwise I hope some moderator will move it.

So, how to choose the appropriate public lets say (i, m) and private (j, m) keys which could be subsequently used to (de)encrypt in RSA when there are primes lets say p = 17 and q = 5?

I tried something like:



64 should be magic number but still do not know what to do next, can anyone help me here?
I would really appreciate how to choose and in which way these keys ...

  • $\begingroup$ I assume you mean keys, not kies? $\endgroup$
    – orlp
    Jun 12, 2013 at 2:13
  • $\begingroup$ Yes sorry .. Corrected $\endgroup$
    – Byakugan
    Jun 12, 2013 at 2:20
  • $\begingroup$ I'm not entirely sure what you're asking. Your last sentence doesn't really make sense. $\endgroup$
    – Savara
    Jun 12, 2013 at 10:03

1 Answer 1


I assume that $m = pq$ (85) is the modulus, and the number you computed (64) is $\phi(m)$. Now we must choose the exponents ($i$ for public, $j$ for secret? , weird notation) in such a way that $ij = 1$ modulo $\phi(m)$. In fact we can work modulo 16 if we like, because that is the least common multiple of $p-1$ and $q-1$. So if we choose $i = 3$, we choose $j=11$, as $33 \equiv 1 \mod 16$. Or $i=11$, $j=3$, this is symmetrical. Or we could choose $i = 5$ and then $j=13$ works, or vice versa again.

Then encryption of a number smaller than $m$ is exponentiation to the power $i$, modulo $m$ and decryption is exponentiation to the power $j$, modulo $m$.

Of course these numbers are way too small to provide any security, but that's the general idea.

  • $\begingroup$ How did you get the number 16 from 64? I thought it must be always 64 no metter what. And how did you get the i,j numbers from that exactly? $\endgroup$
    – Byakugan
    Jun 12, 2013 at 10:25
  • $\begingroup$ We can use either one, both work. Either $(p-1)(q-1)$ or the least common multiple of $(p-1)$ and $q-1$. And you just pick any $i$ that has an inverse $j$ modulo that number. $\endgroup$ Jun 12, 2013 at 11:37
  • $\begingroup$ Ok thank you I uderstand now why I can choose number 16 but still I do not know how to get the keys - which mechanism to use to get them? Or just guessing?? What if I need bigger numbers? $\endgroup$
    – Byakugan
    Jun 12, 2013 at 14:32
  • $\begingroup$ Mostly people choose some $i$ that has no divisors in common with $\phi(m)$ (in this case 64), and this is easy to check (Euclid's algorithm) and then $j$ is its inverse (also found by the (extended) Euclidean algorithm). We can choose any such $i$ (and keep its inverse $j$ secret). Often $i=3$ or $i=2^{16}+1$ is chosen, but we need not do that. It's the same for bigger numbers. $\endgroup$ Jun 12, 2013 at 15:21
  • $\begingroup$ Question is answered thank you, still do not know how exactly to get the I and J numbers, though. But never mind - for me it would be like step-by-step manual only works :) but thank you anyway. $\endgroup$
    – Byakugan
    Jun 13, 2013 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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