I'm trying to decrypt an RSA encryption given that
c: 8533139361076999596208540806559574687666062896040360148742851107661304651861689
n: 769457290801263793712740792519696786147248001937382943813345728685422050738403253
e: 65537
I plan on finding:
φ(n) = φ(769457290801263793712740792519696786147248001937382943813345728685422050738403253)
and then using a modular multiplicative inverse calculator to find:
65537 * D = 1mod(φ(n)) – with the value I find above
Once I have D, I plan to decrypt C by using the formula:
Decrypted Message = C^D(modN)
However, I can't seem to find any suitable calculator for calculations as large as these. Could someone please recommend a calculator which is able to perform such large calculations? Also, if my theory is wrong, please correct me :)
This comes from the picoCTF question : https://play.picoctf.org/practice/challenge/162?category=2&page=1 Mind your P's and Q's
You can use Python to do arithmetic with huge numbers. If you don't want to use Python, this problem is probably short enough to let you get away with just using the WolframAlpha web interface.
Your proposed strategy is correct, but the tricky part is finding $\varphi(n)$. If there was an easy way to do that, then RSA would be insecure in general, since people could decrypt any message using the strategy you suggest. Finding $\varphi(n)$ basically requires knowing the prime factorization of $n$ which is hard. If someone chooses a huge and hard-to-factor $n$ then it will be basically infeasible to break the code.
The point of this particular exercise is to demonstrate that RSA is crackable if the choice of $n$ is too small. This problem's $n$ has "only" 81 digits; that's too big to factor by naive methods, but the fastest known algorithms can actually handle this size. You don't even need to code the algorithms yourself: I was able to get the factorization in a few seconds quickly from this online calculator. (See here for an alternative tool, but it seems slower in this case.) Once you have the factorization, you can compute $\varphi(n)$ using the product formula.