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))
17976931348623159077293051907890247336179769789423065727343008115773267580550096313270847732240753602112011387987139335765878976881441662249284743063947412437776789342486548527630221960124609411945308295208500576883815068234246288147391311…