I have working Python code (below) that cracks an RSA key and times the prime factorization. How do I put this code into a module that takes a list of integers representing n for creating an n-bit prime number for range 0...2^n? I want to pass in a list of integers and return a table of the n-values and run times like this:
n run time
15 0.2
16 1.1
17 1.4
18 10.6
19 30.2
20 46.6
code:
import random
import math
import timeit
while True:
try:
n = input("Please enter a number n for creating an n-bit prime number for range 0...2^n: ")
n = int(n)
break
except ValueError:
print('\nPlease enter an integer value.')
def isPrime(m):
for i in range(2, m//2, 1):
if m % i == 0:
return False
return True
def nBitPrime(n):
r = random.random()
m = int(r * (2**n))
if m >= 2 and isPrime(m) == True:
return m
return nBitPrime(n)
def getPQ(n):
pq = nBitPrime(n) * nBitPrime(n)
return pq
pq = getPQ(n)
def factor(pq):
p = math.floor(math.sqrt(getPQ(n)))
if p % 2 == 0:
p += 1
while p < pq:
if pq % p == 0:
return p, int(pq/p)
p += 2
def wrapper(func,*args):
def wrapped():
return func(*args)
return wrapped
wrapped = wrapper(factor, n)
speed = (timeit.timeit(wrapped, number=1))*1000
print(round(speed, 4))
Thanks in advance.
There are several issues here. To start with, your factor function regenerates a new pq value, ignoring the one you produced earlier. This counts the time to get pq twice. Also, measuring time on a single execution for a process that uses a random number generator doesn't give you a good idea of the performance. You need to make several runs to get an average.
I cleaned up your code a bit and changed the way time is measured to get an average over 100 runs:
your code:
import random
import math
import timeit
def isPrime(m):
for i in range(2, m//2, 1):
if m % i == 0:
return False
return True
def nBitPrime(n):
r = random.random()
m = int(r * (2**n))
if m >= 2 and isPrime(m) == True:
return m
return nBitPrime(n)
def getPQ(n):
pq = nBitPrime(n) * nBitPrime(n)
return pq
def factor(pq):
p = math.floor(math.sqrt(pq))
if p % 2 == 0:
p += 1
while p < pq:
if pq % p == 0:
return p, int(pq/p)
p += 2
while True:
try:
n = input("Please enter a number n for creating an n-bit prime number for range 0...2^n: ")
n = int(n)
time = timeit.timeit(lambda:factor(getPQ(n)), number=100)
print(f"{time*10:.4f}")
except ValueError:
print('\nPlease enter an integer value.')
Apart from simple code optimizations, using a prime number generator and a list of primes will speed it up considerably.
Here are sample implementations of the same functions, in a more efficient and Pythonic way, to help you make better functions of your own:
prime number generation (as needed)
primes = [2,3]
primeSkip = {9:3}
# fill primes list up to the square root of N
def morePrimes(N):
lastPrime = primes[-1]
while lastPrime*lastPrime<N:
lastPrime += 2
if lastPrime not in primeSkip:
primeSkip[lastPrime*lastPrime] = lastPrime
primes.append(lastPrime)
continue
prime = primeSkip.pop(lastPrime)
multiple = lastPrime + 2*prime
while multiple in primeSkip: multiple += 2*prime
primeSkip[multiple] = prime
prime test
# prime test uses the known prime list as a search mechanism
# and only checks divisions for primes when a larger number is given
from bisect import bisect_left
def isPrime(N):
if N<=primes[-1]:
return primes[bisect_left(primes,N)] == N
morePrimes(N)
for p in primes:
if N%p == 0: return False
if p*p>N: return True
return True
random n-bit prime
# non-recursive implementation (faster than recursive)
# also uses randrange() to get the appropriate values without multiplication
# and floating point arithmetics
def nBitPrime(n):
p = random.randrange(2,2**n)
while not isPrime(p):
p = random.randrange(2,2**n)
return p
factorisation
# factorisation uses primes going backward from the square root of pq
# given that p and q are supposed to be large primes, this should converge
# faster to the two factors.
def factor(pq):
morePrimes(pq)
i = bisect_left(primes,int(pq**0.5)+1)
i = min(i,len(primes)-1)
while i>0:
p = primes[i]
if pq%p == 0: return p,pq//p
i -= 1
test runs
Your original code (cleaned up):
Please enter a number n for creating an n-bit prime number for range 0...2^n: 10
0.0531
Please enter a number n for creating an n-bit prime number for range 0...2^n: 15
1.2645
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
38.0535
...
# With the improved functions
Please enter a number n for creating an n-bit prime number for range 0...2^n: 10
0.0359
Please enter a number n for creating an n-bit prime number for range 0...2^n: 15
0.2044
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
3.76593
There is some overhead to the prime based function that offsets the benefits for smaller bit sizes but they provide a noticeable improvement on the higher end
other considerations
The values you are generating for p and q are do not meet the criteria that are usually used to select them. They have to be large primes that are far apart enough from each other. A purely random generation will produce weak values of pq that are easy to factor (although, below 32 bits the prime based factorisation will find them quickly)
This may be a little better:
def getPQ(n):
p = random.randrange(2**(n-4),2**(n-2))
while not isPrime(p):
p = random.randrange(2**(n-4),2**(n-2))
q = random.randrange(p*2,2**n)
while not isPrime(q):
q = random.randrange(p*2,2**n)
return p*q
It would also be a good idea to measure the factorisation time separately from random pq generation. Your cracking function would typically be used on an existing key so generating pq has already been done beforehand to produce the key. This will highlight the large performance difference between your implementation of the factor() function and the prime based one.
while True:
try:
n = input("Please enter a number n for creating an n-bit prime number for range 0...2^n: ")
n = int(n)
pq = getPQ(n)
print("pq",pq) # exclude this from time measurement
time = timeit.timeit(lambda:factor(pq), number=100)
print(f"{time*10:.4f}")
except ValueError:
print('\nPlease enter an integer value.')
Testing only the factor() function performance:
# Your code:
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 78161507029
4.5724
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 414308573933
17.8163
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 192833207923
14.7995
...
# Prime based:
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 36909677657
1.9210
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 62575471813
1.1313
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 761609512621
1.5924