I want to implement brute force hacking using RSA. How can I simulate and measure time duration? What software (or software-based simulator) would be needed?

  • 1
    $\begingroup$ First, you shoudl specify, what you actually want to brute-force. Is it factoring $n$, or finding $d$, or finding $m$ to a certain ciphertext $c$? Anyway, brute force in general is a bad idea here, since the "try out everything" approach has a MUCH higher complexity than factoring with the GNFS (very rough approximation: $2^{n}$ vs $2^{n/3}$) $\endgroup$
    – tylo
    Commented Feb 10, 2014 at 13:38
  • $\begingroup$ Maybe you meant RSA hacking using brute force? $\endgroup$
    – catpnosis
    Commented Feb 11, 2014 at 3:23

2 Answers 2


Firstly, I assume we are talking about classical computers

Implementing a brute force attack on a RSA may not be the most sensible thing, unless of course the security parameter of your target system is small.. (160 bit numbers! )

Even then you may not want to implement a brute force here.. try using Fermat's Factoring or Pollards $\rho$ method.

If you just want to measure time try to do a more theoretical research, i.e. use the time take per multiplication op. and the no. of operations your computer can perform in a sec to determine exactly how long will it take you to brute force a $n-$bit security.

To sum it up, YOU CANNOT BRUTE FORCE THE (properly implemented) MODERN DAY RSA (~4096 bit numbers) even if you use all computers in your state.

  • 2
    $\begingroup$ Did you mean 160 digits (about 530 bits) rather than 160 bit? That's more like the limit of brute-forcing RSA for an individual. $\endgroup$
    – fgrieu
    Commented Feb 9, 2014 at 17:00
  • 2
    $\begingroup$ 160 bits sound about right if by "brute force" one means literally iterating through all odd numbers from $\sqrt(N)$ and checking if the value divides $N$. $\endgroup$ Commented Feb 10, 2014 at 1:33
  • $\begingroup$ @fgrieu 530 bit is in the ballpark of brute force, however, it will take some time (months) to do that with a modern day PC (I assume the asker does not have access to supercomputers or clusters). $\endgroup$
    – Subhayan
    Commented Feb 11, 2014 at 3:18

I don't understand what you mean simulate, but if you need a toy example in python the code is at the end of the message. If you need to show the performance of more advanced algorithms use factor(x) in pari/gp. See here for details.

import gmpy, time, random, math

def genprime(bits):
        p = random.randrange(math.pow(2,bits-1),math.pow(2,bits))
    return p

while not found:
if found:
    print "%d can be devided by %d"%(n, cnt-1)
    print "It took %d ms "%(cnt-1)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.