# How to determine the exponent when using RSA

Can someone please explain to me how, when using RSA, to determine the exponent to be used in encryption and decryption? I have attempted a worked example on using RSA (shown below) but I can't ever get the decryption algorithm to work.

Worked example:

$p = 29$

$q = 37$

$n = 29*37 = 1073$

$\phi = (29-1)(37-1) = 1008$

$e = 3$

$d = (2(1008))+1)/3 = 672.3333333$

$m = 121512$ (taking the positions in the alphabet for 'L', 'O' and 'L')

Encrypt: $c = 121512^3 \mod 1073 = 878$

Decrypt: $878^{672.3333333} \mod 1073 = 352.91536313837299042255202310536$

1. Exponent $e$ must be chosen to be coprime with $\phi$. In your question, exponent $e = 3$ is not coprime with $\phi = 1008$. You can choose $e = 5$ instead.
3. You cannot encrypt a message bigger than the modulo (in this case, $n = 1073$).
Taking these aspects into account, the remaining steps are as follows. The private key $d$ must be computed so $e \cdot d = 1 \mod \phi$. Using this online tool, we find the private key $d = 605$. Next, we cannot encipher message 121512 since is bigger than the modulo, but we can encipher the first three digits, so $m_1 = 121$. Hence, the other half of the message is $m_2 = 512$. The encryption of $m_1$ is $c_1 = (m_1)^{e} \mod n = 121^{5} \mod 1073 = 25937424601 \mod 1073 = 544$.