Craking long RSA keys from public key only

Question

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

Answer 1

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.