Chapter 24 – Public Key Cryptography and the RSA Cipher 383

To both you and Emmanuel, it looks like you are communicating secretly with each other. But
actually, the spy agency is doing a man-in-the-middle attack and reading all of your messages.
You and Emmanuel are actually encrypting your messages public keys generated by the spy
agency! Again, this problem is caused by the fact that the public key cipher only provides
confidentiality, but does not provide authentication.

Generating Public and Private Keys.........................................................................................................................

A key in the RSA scheme is made of two numbers. There are three steps to creating the keys:

1. Create two random, very large prime numbers. These numbers will be called p and q.
   Multiply these numbers to get a number which we will call n.


2. Create a random number, called e, which is relatively prime with (p – 1) × (q – 1).


3. Calculate the modular inverse of e. This number will be called d.

The public key will be the two numbers n and e. The private key will be the two numbers n and d.
(Notice that both keys have the number n in them.) We will cover how to encrypt and decrypt
with these numbers when the RSA cipher program is explained. First let’s write a program to
generate these keys.

Source Code for the RSA Key Generation Program

Open a new file editor window by clicking on File ► New Window. Type in the following code
into the file editor, and then save it as makeRsaKeys.py.

Source code for makeRsaKeys.py

1. 
   

   RSA Key Generator

   
   


2. 
   

   http://inventwithpython.com/hacking (BSD Licensed)

   
   


3. 
   


4. import random, sys, os, rabinMiller, cryptomath


5. 
   


6. 
   


7. def main():


8. 
   

   create a public/private keypair with 1024 bit keys

   
   


9. print('Making key files...')


10. makeKeyFiles('al_sweigart', 1024)


11. print('Key files made.')


12. 
    


13. def generateKey(keySize):


14. 
    

    Creates a public/private key pair with keys that are keySize bits in

    
    


15. 
    

    size. This function may take a while to run.

    
    


16. 
    


17. 
    

    Step 1: Create two prime numbers, p and q. Calculate n = p * q.

    
    


18. print('Generating p prime...')