2
$\begingroup$

I have just read a very basic introduction to the RSA algorithm.

Let's suppose my two prime numbers are $p=29$ and $q=37$. Then $n=pq=1073$ and $e=5$. $n$ and $e$ are public.

If I want to send the letter U, which is n°21 in the alphabet, I would send $21^e$ (mod $1073$) that is $263$.

Normally I should calculate $(21^e)^d$, where $d=605$. But why not calculate $(263)^{1/5}$ ?

  • 1
    The problem is that calculating $(263)^{1/5}$ is hard, when working modulo an $n$ with unknown prime factors. How would you calculate this $5$th root?2012-11-14

2 Answers 2

1

Because modular exponentiation is easy. How would you calculate $263^{1/5}?$ If you could, the encryption would not be secure.

  • 0
    @Tom: For this case, you can just try all the numbers from $1$ to $1072$ and see which works. If there were a general answer, that would break RSA.2012-11-14
0

You already calculated $ d= 605 \equiv 5^{-1} \equiv 1 / 5 \pmod{ \phi(n)} $ .