Chapter 24 – Public Key Cryptography and the RSA Cipher 419

(Remember, prime numbers have no factors besides 1 and themselves. If you multiply two prime
numbers, that new number will only have the factors of 1 and itself, and also the two prime
numbers.)

So to solve everything and hack the RSA cipher, all we need to do is figure out what the factors
are for n. Since there are two and only two numbers that multiply to n, we won’t have several
different numbers to choose from. Then we can calculate (p – 1) × (q – 1) and then calculate d.
This seems pretty easy. We already have code that finds factors in primeSieve.py’s isPrime()
function:

Source code from primeSieve.py

7. def isPrime(num):


8. 
   

   Returns True if num is a prime number, otherwise False.

   
   


9. 
   


10. 
    

    Note: Generally, isPrime() is slower than primeSieve().

    
    


11. 
    


12. 
    

    all numbers less than 2 are not prime

    
    


13. if num < 2:


14. return False


15. 
    


16. 
    

    see if num is divisible by any number up to the square root of num

    
    


17. for i in range(2, int(math.sqrt(num)) + 1):


18. if num % i == 0:


19. return False


20. return True

We can just modify this code to return the first factors it finds (since we know that there can be
only two factors for n besides 1 and n):

def isPrime(num):

Returns (p,q) where p and q are factors of num

see if num is divisible by any number up to the square root of num

for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0:
return (i, num / i)
return None # no factors exist for num, num must be prime

We can just call this function, pass it n (which we get from the public key file), and wait for it to
find our factors, p and q. Then we can know what (p – 1) × (q – 1) is, which means we can
calculate the mod inverse of e mod (p – 1) × (q – 1), which is d, the decryption key. Then it
would be easy to calculate M, the plaintext message.