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 TrueHere 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
eandtothas the greatest common divisor(gcd) is equal to 1. If it is 1 we have found oureif 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 -gThis 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.txtThis will create decrypted.txt file which will contain Bob’s original message which is ‘Hello world’.