1
$\begingroup$

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$

$\endgroup$
3
$\begingroup$

There are three main errors here:

  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.
  2. You must use integer arithmetic, not floating-point. In other words, you cannot have values expressed with decimals.
  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$.

You can figure out the rest.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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