3

For a contest I am trying to learn how to break a RSA key given only the public key:

  • e = 65537
  • n = 632459103267572196107100983820469021721602147490918660274601

So I followed this webpage and this answer. And tried:

    >>> n = 632459103267572196107100983820469021721602147490918660274601
    >>> import math
    >>> math.floor(math.sqrt(n))
    795272974058324394239265341440
    >>> c = math.floor(math.sqrt(n))
    >>> for i in range(c-1,c-41,-2):
    ...     if c%i ==0:
    ...         print(i, c%i)
    ...

But it doesn't give me anything. I have started a brute force approach:

>>> print(repr(math.sqrt(n)))
7.952729740583244e+29
>>> c = math.sqrt(n)
>>> int(c)
795272974058324394239265341440
>>> for i in range(c-1, 2, -2):
...     if n%i == 0:
...         print(i, n%i)
...

But it has been running for half a day. I know it is stupid because I am testing even not prime numbers. Is there a wiser way?

At the very beginning I started with c, which is an even number. I guess that decreasing with a step 2 from an even number is stupid as it only leads me to test non factorizer?

Update

After reading Dan's comment, I am now trying to search for a small factor rather than start from the big one.

>>> for i in range(1,c-1,2):
...     if c%i ==0 and i%2 != 0 and i%5 !=0:
...         print(i, c%i)
...
1 0
Revolucion for Monica
  • 2,848
  • 8
  • 39
  • 78
  • @orangecaterpillar's answer is good. A couple other things to keep in mind... don't bother trying odd numbers ending in 5, by definition (except for '5') they won't be prime. Also, if this is for a contest, they might have created the modulus by multiplying a small prime (e.g. something smaller than 10,000) by a very large prime. This isn't how normal RSA key generation works but for a contest, they might be looking to reward the clever. So maybe try those once too before you descend from the square root. – Dan Apr 27 '20 at 21:48
  • @Dan Thanks for your insight! However I don't see how it entice to be more clever to have a small prime number ... Surely I'm missing something – Revolucion for Monica Apr 27 '20 at 21:56
  • First of all, despite the various comments and answers, the number is not too big to factor on a laptop using the quadratic sieve algorithm. If you are inspired you might try to code this yourself. However, the quadratic sieve is too complicated to expect a contestant to to program it up. So, either the modulus was constructed to be vulnerable to some shortcut attack, or you have left out some information, or you're expected simply to go online and find a suitable factoring program to do it for you. You would have a better idea of which of these is the case. – President James K. Polk Apr 28 '20 at 02:02
  • Hi @RevolucionforMonica -- no you're not missing anything, what I'm saying is the same thing as President, who said it best... "either the modulus was constructed to be vulnerable to some shortcut attack". What I'm suggesting is that your algorithm (starting near the square root) will first try factors that are similar in size, and then move to the extremes... but perhaps the factors are something like 107 and . Your algorithm will only find that at the very end (takes a long time). Can't hurt to just try brute-forcing the first ~10,000 small prime numbers and see if one works. – Dan Apr 29 '20 at 00:35
  • @Dan: Your advice is good in general. But I have already factored the number and it has no small factors. Interestingly, someone wrote a program to try all the "shortcut" RSA attacks they've seen in these contests. The code is [here](https://github.com/Ganapati/RsaCtfTool). – President James K. Polk Apr 29 '20 at 12:55
  • @PresidentJamesMoveonPolk -- excellent, very cool. Thanks for the update & sharing the code / link. – Dan Apr 30 '20 at 16:22
  • Thank you Mr @PresidentJamesMoveonPolk – Revolucion for Monica Apr 30 '20 at 16:26
  • @PresidentJamesMoveonPolk -- wow, that was shockingly quick. I don't think it even took 2 seconds to run. Thanks for introducing me to that tool. – Dan Apr 30 '20 at 20:32

1 Answers1

2

TL;DR: Cracking long RSA keys is computationally hard (i.e. there is no known solution that runs in polynomial time) and while your algorithm might not be the most efficient, no one has found one that can crack long RSA keys (with a classical computer - Shor's algorithm for a quantum computer could crack long RSA keys in polynomial time).

Longer Answer:

To estimate how long your program would take to execute, I wrote the following python:

import time

n = 632459103267572196107100983820469021721602147490918660274601
c = 795272974058324394239265341440

test_size = 100000

start_time = time.time()

for i in range(c-1, c-test_size, -2):
    if n%i == 0:
        print(i, n%i)

time_elapsed = (time.time() - start_time)

print("Elapsed Time for %i iterations: %f seconds" % (test_size, time_elapsed))
seconds_in_a_year = 31557600
projected_time = time_elapsed * (c / 2 / test_size) / seconds_in_a_year
print("Projected Time for %i iterations: %i years" % (c, projected_time))

When I ran this on my computer, the output was:

Elapsed Time for 100000 iterations: 0.024008 seconds
Projected Time for 795272974058324394239265341440 iterations: 3025094101018381 years

That's too many years!

One thing to note about the article and answer you linked to is that they provide examples with short keys. The reason the RSA cryptosystem is used and works is that when large enough keys are generated, it is computationally intractable (i.e. it would take many lifetimes even if all the compute resources on earth worked together) to use any known procedure to determine the private key given the public key. As computers get faster, what is considered a large enough key may change a little, and other public-key cryptosystems that are even harder to crack can also be used for greater security, but as it stands, 1,024 to 4,096 bit RSA is widely used in production environments. The n you provided is 199 bits (math.log(n,2)), so I imagine it can be brute forced in a reasonable amount of time... just not using a laptop and not using python (if you try the same brute force approach in C it will still not run in a reasonable time - but it will be faster than python). If you're interested in other algorithms for solving the discrete log problem or integer factorization, I don't know much about that, but I can tell you that there are no known efficient algorithms for non-quantum computers.

If I have time I'll come back and update this answer with some C code to compare, I just wanted to point out that you aren't doing anything wrong, you're trying to solve an intractable problem.

orangecaterpillar
  • 714
  • 9
  • 12