Finding N̷e̷m̷o̷ Prime Numbers

Finding N̷e̷m̷o̷ Prime Numbers

RSA gains its key security strength from the multiplication of two prime numbers (p and q) to get N. If we get p and q, then we can work out:

Phi = (p-1)(q-1)

And since we have encryption key (e), and which is normally 65,537, we solve for d in:

d x e mod (PHI) = 1

Basically we have the inverse mod of e mod PHI For example if we have an e value of 65,537 and a PHI of 10,347,768,518,374,182,260, then the decryption key value (d) will be 12,406,113,933,120,080 Test.

And so it becomes easy to crack RSA if we can crack N. But when we define that a digital certificate has 2,048 bits, how big are the values of p and q. Well if we have an n bit value and multiply it with an m bit value, we get a result which has n+m bits. And so if our RSA keys are 2,048 bits long, then our prime numbers will be half this size (1,024 bits).

So how many digits will a 1,204 bit have? Well we have use Python to determine that it has 309 digits:

>>> y=2**1024

>>> print y,len(str(y))

179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216 309

and when we multiply we get a 617 digit number.

>>> y=2**2048

>>> print y,len(str(y))

32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656 617

In the Martin Gardner column which first proposed the RSA method, the challenge was to break an N value of just 129 digits, and which would be fairly easy to crack today (but at the time Ron Rivest thought it would take 40 quadrillion years to factorize).

So if I want to generate two prime numbers what process will I take?

Well again we can turn to Python and use the Riemannr method to estimate the number of prime numbers that are 1,024 bit long:

import sys
import math

start=2**1023
end=2**1024

from mpmath import *
n=int(riemannr(end))-int(riemannr(start))
print "Est prime numbers :\t",n
print "Estimation to find is 1 in",(2**1024)/n

If we run we get determine that we have a massive number of 1,024 bit numbers, but that the chances of us finding one is 1 in 1418.

Est prime numbers : 12669164489297035838042749092693935645472324718849614339
24766525026995310075958371294812932404687423824670251209
13518137109729182502216808596722503552506608383945568062
99217183402234779768002807879623065822080202513999439628
97095578902630452877769836056051748736023462240653644712
9531599628766639300804608
Estimation to find is 1 in 1418

And so we could generate a 1,024 bit number using a getranbits() function:

>>> import random

>>> random.getrandbits(1024)

156548939571986617936593398696487626269281069361549954872290664955514361566028430228393690460599919225561780089634158011587614280666963754668325779987475479846196199822356717682549864936396590068357782045162223432591023551799214794233281216026354993428635528007054022288847392617709977816846850992096404056283L

>>> random.getrandbits(1024)

55136965950425835689158416465806396636650650968403266989581732336809191724275683828621859295706434070151101183614258416403031972397870140768974504109826757341964250565697908008752691622930769593895629599534356491697781910973306456605765264018712506188755530370692209478031117756834222205525907403426552222412L

And then test if it is a prime number. If not we decrement it, and test again. From our calculation it should only take 1,418 attempts to find one.

And so now we have integer some code to test for a prime. In this case I will use the Miller-Rabin test:

import sys
import math

import random

_mrpt_num_trials = 5 # number of bases to test
 
testval=97

def is_probable_prime(n):
 assert n >= 2
 # special case 2
 if n == 2:
 return True
 # ensure n is odd
 if n % 2 == 0:
 return False
 # write n-1 as 2**s * d
 # repeatedly try to divide n-1 by 2
 s = 0
 d = n-1
 while True:
 quotient, remainder = divmod(d, 2)
 if remainder == 1:
 break
 s += 1
 d = quotient
 assert(2**s * d == n-1)
 
 # test the base a to see whether it is a witness for the compositeness of n
 def try_composite(a):
 if pow(a, d, n) == 1:
 return False
 for i in range(s):
 if pow(a, 2**i * d, n) == n-1:
 return False
 return True # n is definitely composite
 
 for i in range(_mrpt_num_trials):
 a = random.randrange(2, n)
 if try_composite(a):
 return False
 
 return True

val = random.getrandbits(1024)
for x in range(4000):
 test = val-x
 if is_probable_prime(test):
 print “Found:”,test

A sample run gives:

Found: 10984678770764623323878741084947969949832629371144544237407544
03337401646290765857178780855834946507972652578128966513242618
23972954301989454562457411611669237492575018934204254111240208
39166423426856896124038258075724310959568802347236784318963962
9754396454368329186198846985241378274571141217417474768124739

And so we have found ̶N̶e̶m̶o̶ primes numbers.