-1

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

Picture of the actual question

martin_thuriaux
  • 1

1 Answers1

2

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.

David Clyde
  • 5,251
  • Thank you so much! I really appreciate you taking time out of your day to explain this to me! – martin_thuriaux Dec 08 '22 at 07:35
  • yafu is a faster alternative. In fact, $81$ digits is very very small. Numbers of this size can be factored in less than a minute (it does not matter that here it was factored even faster). Even $100$ digits is not even close to be challenging. With a modern computer and a reasoanable siqs-implementation, it will still take just a few hours , even if parallelization is not used. – Peter Dec 08 '22 at 07:57
  • I do not know how many digits we currently need for a "secure" code (we never know whether it is actually secure!) , but $300$ digits are surely not secure , unfortunately ! – Peter Dec 08 '22 at 07:59
  • Note that ECM might find large factors faster than the quadratic sieve. It is sometimes also a matter of luck to factor a number quickly ! – Peter Dec 08 '22 at 08:01
  • @Peter we usually don't consider for today, rather we consider how long. There are estimates about this https://www.keylength.com/en/compare/ – kelalaka Dec 08 '22 at 20:23