Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$ ?

share|improve this question
    
Computing roots under modulo is a VERY HARD task. –  Gautam Shenoy Nov 14 '12 at 16:01
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? –  TMM Nov 14 '12 at 16:02
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
    
Thanks to all of you. Is it hard or impossible ? –  Tom Nov 14 '12 at 16:50
    
@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. –  Ross Millikan Nov 14 '12 at 16:58
    
Thank you very much ! –  Tom Nov 14 '12 at 18:48
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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