# 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 '13 at 2:13
Yes sorry .. Corrected – Byakugan Jun 12 '13 at 2:20
I'm not entirely sure what you're asking. Your last sentence doesn't really make sense. – Savara Jun 12 '13 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. – Henno Brandsma Jun 12 '13 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. – Henno Brandsma Jun 12 '13 at 15:21