Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

to understand RSA better I am doing a little calculation by hand, this is what I got:

Choosing: $p = 3$

$q = 5$

$n = 15$

$\phi(pq) = 2 \cdot 4 = 8$

$e > \phi(n) => e = 13$

$e \cdot d = 1 \mod 8$

$13 \cdot d = 1 \mod 8$

$(13 \cdot 5) \mod 8 = 1$

So there has to be $m \le n$ and I choose $m = 7$

Encryption:

$c = m^e \mod n$

$c = 7^{13} \mod 15$

$c = 7$

And if I decrypt it's nice coming back to 7. But it looks a bit weird to me having $m = c$ but I don't find what I should be doing wrong.. ?

share|improve this question
2  
Try larger $p$ and $q$. I've noticed when doing RSA by hand with very small $p$ and $q$ it is easy to run into corner cases in which weird things happen (for example, the reason for a previous question of mine: crypto.stackexchange.com/questions/1004/…). These corner cases only occur with negligible probability for large $p$ and $q$. Obviously if you choose $p$ and $q$ too large you can't do it by hand any more though, so you have to balance between doing it by hand and hitting weird cases. –  mikeazo Jul 1 '13 at 12:58
add comment

4 Answers

up vote 1 down vote accepted

Your math is correct. But: RSA defines choosing $e< \phi(n)$ not $e>\phi(n)$, and $e$ coprime to $\phi(n)$ obviously. The only necessary assumption here is that they are coprime (otherwise it's a lossy function and you can not decrypt any more). But since encryption with $e$ mod $\phi(n)$ results in the same ciphertext, you gain nothing but a larger exponentiation if $e$ is larger than $\phi(n)$.

About your numbers: Your choice of $p$ and $q$ lead to a curious coicidence: $5 = 5^{-1}$ mod 8. Therefore $e=d=5, ed=1$ mod 8. However, without knowledge of $\phi(n)$ it is hard to know if a random public RSA key fulfills this relation or not. By finding such an exponent, you got an involution. Roughly speaking, such a function can only send $x$ to itself or its inverse, otherwise it doesn't work.

share|improve this answer
    
okay, so choosing e < phi(n) boosts the performance of encryption. and for the rest I am understanding that it is a random case which I encountered because of small values. It's just because I really try to understand how it works and not just accepting that it does.. –  Stefan Jul 1 '13 at 19:37
add comment

In fact, your calculating is right. The problem is:

At first, $e=13=5\pmod 8$.

Next, $d=5=e$ since $d\cdot e=1\pmod 8$. This means that the decryption key is identical to the encryption key. You should avoid this of course.

Third, $7^{13}=7^5=(7^2)\cdot(7^2)\cdot 7\pmod{15}=(4\cdot 4)\cdot 7\pmod{15}=7\pmod{15}$. This is why your decryption outputs the same as the input. If you try another message, you may find that the cihertext is different to the plaintext.

share|improve this answer
    
This starts to lighten up. So the problem is choosing a n e for which the inverse modulo is not the remainder of e mod n ? In fact this is the case for all values I have tried. Then how to choose it correctly and wisely? I have also seen that ciphertext varies and is not always m=c. –  Stefan Jul 1 '13 at 11:37
add comment

What you're doing wrong is choosing $e$ to be (comparatively) way too large.
It is sufficient that $e$ and $d$ satisfy $\;\;\;\; e\hspace{-0.03 in}\cdot\hspace{-0.03 in}d \: \equiv \: 1 \;\; \pmod{\operatorname{lcm}(\hspace{.025 in}p\hspace{-0.03 in}-\hspace{-0.03 in}1,\hspace{-0.01 in}q\hspace{-0.03 in}-\hspace{-0.03 in}1)} \;\;\;\;$.
Since $\;\; 13 \equiv 1 \: \pmod{\operatorname{lcm}(\hspace{.01 in}3\hspace{-0.03 in}-\hspace{-0.03 in}1,\hspace{-0.01 in}5\hspace{-0.03 in}-\hspace{-0.03 in}1)} \;\;$, $\;\;$ your "encryption" will be just reducing modulo 15.

share|improve this answer
    
But for choosing e bigger than phi(n) and relatively prime what would be a good choice? I don't think I understood completely what you try to say. Or is it wrong to have e > phi(n) ? –  Stefan Jul 1 '13 at 8:10
    
Well, 11 would have been a good choice, since that will give the same outputs as using 3. $\:$ Decryption will still work with e > phi(n), the public operation will just be much slower than one would get by using a smaller e. –  Ricky Demer Jul 1 '13 at 8:21
    
But choosing e=11 and m=10 would also give me m=c for 10^11 mod 15 –  Stefan Jul 1 '13 at 8:32
    
Yes, since 10 is idempotent. $\:$ More generally, that will happen for at most e^2 values, regardless of what n is. $\;\;\;$ –  Ricky Demer Jul 1 '13 at 9:01
add comment

I think your problem is, that you are choosing $e > phi(n)$. But one can always modulo reduce $e$ mod $phi(n)$, so you should choose an $e < phi(n)$.

In fact, $e$ is often relativley small (i.e. small hamming-weight), to get faster encryption runtimes. That is, because the exponentiation algorithms used in real world RSA, need more multi-precision multiplications for higher hamming-weights.

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.