Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Can someone explain why 7 and 13 (max 91) with 5 as public key, gives 29 as the private key for RSA? I wish he had explained that bit too.


Say e=5 is your public key. Since the encryption step is computing x^e (mod pq), you want your private key to be a number d such that (x^e)^d = x (mod pq).

Basic algebra (Fermat's theorem) says that the last equation holds if you have ed = 1 (mod phi(pq)). Here, phi(pq) is the size of the multiplicative group mod pq, where the multiplicative group is simply the set of elements that have an inverse modulo pq.

More basic algebra tells you that phi(pq) = (p-1)(q-1), or, in your case, 72.

So, you need to find the inverse of 5 modulo 72. You can find that using the extended Euclidean algorithm for computing gcds: A number e is invertible modulo N if and only if gcd(e,N) = 1, and in this case, there exist integers a and b such that ae + bN = 1; the extended Euclidean algorithm will find them, and the number a is what you're looking for (check the definition of modular arithmetic).

To verify that the number 29 makes sense, just compute 5 * 29 (mod 72): you'll get 1.

I don't know if that helped at all. If it didn't, you'll have to start asking more specific questions :-)


That's a superb explanation. I just plugged all that into a spreadsheet to get this: http://pastebin.com/z32SB1Z4

I can see that e*d mod phi = 1 when d = 29, 101, 173 etc.

I understood the rest of the article except this part so thanks a lot for it!


That's a tight little explanation.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: