Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
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}$) –  tylo Feb 10 at 13:38
    
Maybe you meant RSA hacking using brute force? –  catpnosis Feb 11 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.

share|improve this answer
2  
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. –  fgrieu Feb 9 at 17:00
2  
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$. –  Henrick Hellström Feb 10 at 1:33
    
@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). –  Subhayan Feb 11 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=1
    while(gmpy.is_prime(p)==0):
        p = random.randrange(math.pow(2,bits-1),math.pow(2,bits))
    return p

BITS=20
found=False
p=genprime(BITS)
q=genprime(BITS)
n=p*q
cnt=2
s_time=time.time()
while not found:
    found=(n%cnt==0)
    cnt+=1
e_time=time.time()-s_time
if found:
    print "%d can be devided by %d"%(n, cnt-1)
    print "It took %d ms "%(cnt-1)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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