# How to choose the appropriate public (i, m) and private (j, m) keys?

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:

17*5=85

(17-1)*(5-1)=64


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

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

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$.
• 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. Jun 12, 2013 at 11:37
• 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. Jun 12, 2013 at 15:21