Understanding and Implementing RSA Algorithm in Python

Understanding and implementing RSA
RSA Algorithm

 

RSA Algorithm is widely used in secure data transmission. It was invented by Rivest, Shamir, and Adleman in the year 1978 and hence the name is RSA. It is an asymmetric cryptography algorithm which basically means this algorithm works on two different keys i.e. Public Key and Private Key. Here Public key is distributed to everyone while the Private key is kept private.

This algorithm heavily depends on Prime Numbers and their properties. Implementing RSA involves four steps:

  • Key Generation
  • Key Distribution
  • Encryption and
  • Decryption

We will look at each of this operation step by step:

Key Generation

The first phase of RSA is generating a public key and a private key. This is accomplished in several steps:

  • Step 1: The first step is to select two prime number p and q. In order to have strong public and private keys, this primes number should be very large.
  • Step 2: Then we compute ‘n’ which is nothing just product of two prime number we calculated in the above step i.e: n = p * q

‘n’ is used as modules for generating public and private keys.

‘n’ is also released as a part of public key

  • Step 3: Then we compute λ(n) which is Carmichael’s totient function. This is simply calculated using formula:λ(n) = (p – 1) * (q – 1) λ(n) is kept secret.
  • Step 4: Now we calculate e(or encryption key). The way we choose the encryption key is such that the largest common divisor between e and λ(n) is 1 i.e: gcd(e,λ(n)) = 1 or to put it in another word e and λ(n) should be co-prime.

e is released as a part of public key.

  • Step 5: After finding ‘e’ or encryption key using this we calculate decryption key or ‘d’.  The decryption key is calculated such that it is the modular multiplicative inverse of e modulo λ(n) i.e:d ≡ e^(− 1) (mod λ(n)) ‘d’ can be calculated using Extended Euclidean algorithm.

Key Distribution

Suppose that Bob wants to send a piece of information to Alice. To encrypt this information Bob must know the public key of Alice and Alice must use her private key to decrypt the information. Here Alice must transmit her public key (n,e) to Bob. And the encrypted message by the Bob can only be decrypted using Alice’s private key(d).

Encryption

After obtaining the public key of Alice, Bob now encrypts its message. Bob first converts each character in his message to it’s ASCII equivalent and obtains an integer. This integer is then encrypted using the formula:

c = m^e (mod n)

where c is the ciphertext, m is the ASCII value of the character, e and n are public key pair of Alice.

Decryption

Alice can recover m from c by using her private key exponent d by computing:

m = c^d (mod n)

Implementation

First, let’s generate our public key and private key. Open up your text editor and write the following code:


import random

__DEBUG__ = True

def generate(p_num1,p_num2,key_size = 128):
     n = p_num1 * p_num2
     tot = (p_num1 - 1) * (p_num2 - 1)
     e = generatePublicKey(tot,key_size)
     d = generatePrivateKey(e,tot)

    if __DEBUG__ == True:
       print(f"n = {n}" )
       print(f"tot = {tot}")
       print(f"e = {e}" )
       print(f"d = {d}" )

    return e,d,n

def generatePublicKey(tot,key_size):
     e = random.randint(2**(key_size-1),2**key_size - 1)
     g = gcd(e,tot)
     while g != 1:
         e = random.randint(2**(key_size-1),2**key_size - 1)
         g = gcd(e,tot)

     return e

def generatePrivateKey(e,tot):
     d = egcd(e,tot)[1]
     d = d % tot
     if d < 0 :
         d += tot
     return d

def egcd(a,b):
     if a == 0:
         return (b, 0, 1)
     else:
         g, y, x = egcd(b % a, a)

     return (g, x - (b // a) * y, y)


def gcd(e,tot):
     temp = 0
     while True:
         temp = e % tot
         if temp == 0:
             return tot
         e = tot
         tot = temp


def isPrime(num):
     if num < 2 : return False
     if num == 2 : return True
     if num & 0x01 == 0 : return False
     n = int(num ** 0.5 )
     for i in range(3,n,2):
         if num % i == 0:
             return False

     return True

Here generate function takes three arguments which are two prime number and one is the size of the key. Here I have taken the size of the key to be 128 bit long.

Next, we calculate ‘n’ and Carmichael’s totient function(i.e tot) which is straight forward.

Then we calculate our ‘e’ and ‘d’. The way I have calculated ‘e’ key is:

  • First I have chosen a random number which is 128 bit long.
  • Then I check whether the generated number e and tot has the greatest common divisor(gcd) is equal to 1. If it is 1 we have found our e if not go to step above.

For calculating d I have used extended euclidean distance algorithm. Now I will not go into the math part as it is not the concern of this article but if you want to know how this algorithm work you can refer to this article.

Now we have our e,d and n.Next we write our encrypt and decrypt function:


def encrypt(text,e,n):
     ctext = [pow(ord(char),e,n) for char in text]
     return ctext

def decrypt(ctext,d,n):
     try:
         text = [chr(pow(char,d,n)) for char in ctext]
         return "".join(text)
     except TypeError as e:
         print(e)

As I have explained in encrypt function first we convert each character of plain text to it’s ASCII equivalent the we calculate the cipher text using formula: c = m^e (mod n) which is what we have done. In decrypt function we do the reverse we first decrypt the message using the private key with formula:

m = c^d (mod n)

which gives us ASCII value then we convert this back to its character equivalent.

That’s all we have written our RSA algorithm. Now let’s test our algorithm write the following code:

def getPrime(limit = PRIME_LIMIT):
     num = 0
     while True:
         num = random.randint(0,limit)
         if isPrime(num):
             break
     if __DEBUG__ == True:
         print(f"Generated Prime number: {num}")
     return num

PRIME_LIMIT = 1000000000000

if __name__ == '__main__':
     e,d,n = generate(getPrime(),getPrime())
     export(e,d,n)
     plainText = "This is plain Text"
     cipher = encrypt(plainText,e,n)
     print(cipher)
     dicipher = decrypt(cipher,d,n)
     print(dicipher)

Run the above program and you will see every time new keys are generated and it encrypt and decrypt our plainText

GITHUB

Stimulation

Now let’s try to stimulate RSA process. I have written a python scripts which will help us to run this stimulation. First, create a new file as main.py and write the following code:

# main.py

#! /usr/bin/bash

import sys
from rsa import *

def printHelp():
     print("Usage: \nmain.py -g")
     print("main.py -e inputFile -o ouputFile -k publicKey")
     print("main.py -d inputFile -o ouputFile ")
     print("Options")
     print("-g,--generate : To generate public key and private key")
     print("-e,--encrypt : Encrypt")
     print("-i,--input : Input file")
     print("-k,--key : public key file")

def generateKeys():
 ## Generating Keys
     e,d,n = generate(getPrime(),getPrime(),key_size = 128)
     export(e,d,n)
     print("Keys Generated")
 
def Encrypt(public_key,text_file):
     text = ""
     e = 0
     n = 0

 ## Reading public key
     with open(public_key,'r') as fp:
         _,e,n = fp.readline(),int(fp.readline()),int(fp.readline())

     with open(text_file,'r') as fp:
         text = fp.read()
     cipher_text = encrypt(text,e,n)

     with open("encrypted.txt",'w') as fp:
     for i in cipher_text:
         fp.write(f"{i}\n")
     print("File Encrypted")

def Decrypt(text_file):
     e = 0
     n = 0
     cipher_text = []

 ## Reading private Key
     with open('private.key','r') as fp:
         _,d,n = fp.readline(),int(fp.readline()),int(fp.readline())


     with open(text_file,'r') as fp:
         cipher_text = [ int(i) for i in fp.readlines()]

     original_message = decrypt(cipher_text,d,n)
     with open("decrypted.txt",'w') as fp:
         for ch in original_message:
             fp.write(f"{ch}")

     print("File Decrypted")

if __name__ == '__main__':
     if len(sys.argv) <= 1:
         printHelp()
     else:
         public_key = ""
         text_file = ""
         keyFile = ""
         outputFile = ""
         gen = False
         enc = False
         dec = False
         i = 1
         while i != len(sys.argv):
             if sys.argv[i] == '-g' or sys.argv[i] == '--generate':
                 gen = True
                 i += 1
             elif sys.argv[i] == '-e' or sys.argv[i] == '--encrypt':
                 enc = True
                 i += 1
             elif sys.argv[i] == '-d' or sys.argv[i] == '--decrypt':
                 dec = True
                 i += 1
             elif sys.argv[i] == '-i' or sys.argv[i] == '--input':
                 i += 1
                 text_file = sys.argv[i]
             elif sys.argv[i] == '-o' or sys.argv[i] == '--output':
                 i += 1
                 outputFile = sys.argv[i]
             elif sys.argv[i] == '-k' or sys.argv[i] == '--key' :
                 i += 1
                 public_key = sys.argv[i]
            else:
                 i += 1

         if gen == True:
             generateKeys()
             exit(0)
         elif enc == True:
             if public_key == "" or text_file == "" :
                 printHelp()
             else:
                 Encrypt(public_key,text_file)
         elif dec == True:
             if text_file == "":
                 printHelp()
             else:
                 Decrypt(text_file)
         else:
             printHelp()

Now create two directories, Alice and Bob, for two-person. Now go to each directory and run the following command as:

 python main.py -g

This will generate private and public keys for each person in each directory. Now suppose Bob wants to send a message to Alice. The message is “Hello world” and which is stored in the file name file.txt. So Bob will need the public key of Alice to encrypt the file which we have just generated in Alice directory. Type following command to encrypt the file

python main.py -e -i file.txt -k ../Alice/public.key

Notice that here I have use Alice’s public key to encrypt the file

This command will generate encrypted.txt file. Now copy this generated file to Alice’s directory.To decrypt this file run the following command:

 python main.py -d -i encrypted.txt

This will create decrypted.txt file which will contain Bob’s original message which is ‘Hello world’.

 

GITHUB

Sharing is caring!

Leave a Comment

Your email address will not be published. Required fields are marked *

shares
Scroll to Top