RSA Algorithm an Asymmetric Key Encryption in Python

Hola, everyone! Today we will learn about the asymmetric key algorithms and an example RSA algorithm.

What is Asymmetric Key Encryption?

Asymmetric encryption involves a mechanism called Public Key and Private Key. Everyone in the network can access the public key but the private key is anonymous. The user generates a private key using a function.

To encrypt a message, one can use the public key.
Send the message over a channel. The private key is generated on the receiver side.
The private key is used to decrypt the encrypted message.

The RSA Algorithm

The Rivest-Shamir-Adleman(RSA) Algorithm is a public-key crypto algorithm. It is based on the principle that prime factorization of a large composite number is tough. Only the private key of the receiver can decrypt the cipher message. RSA is a key pair generator.

Choose two different large random prime numbers $p$ and $q$
Calculate $n = p q$ $n$ is the modulus for the public key and the private keys
Calculate $ϕ ( n ) = ( p - 1 ) ( q - 1 )$
Choose an integer $k s$ uch that 1 < $k$ < $ϕ ( n ) and$ $k$ is co-prime to $ϕ ( n )$ : $k$ and $ϕ ( n )$ share no factors other than 1; gcd (k, $ϕ ( n ))$ = 1.
$k$ is released as the public key exponent
Compute $d$ to satisfy the $d k \equiv 1 ( mod ϕ ( n ) )$ i.e.: $d k = 1 + x ϕ ( n ) for som$ e integer $x$
$d$ is kept as the private key exponent

The public key consists of n and k.

The private key consists of p, q, and the private exponent d.

RSA Algorithm working example

Alice sends a message as m=44 to Bob

Choose two prime numbers: 79, 89.
Now n = 79*89 = 7031
Compute totient = (p-1)(q-1) = 6864 = t.
Find ‘k’ which is coprime with 6864 i.e., gcd(5,6864) = 1, k = 5.
Choose d, such that it satisfies de mod Φ(n) = 1 here, d = 1373.

The public key is c = m⁵mod 7031 = 4119

The private key is m = c¹³⁷³mod 7031.

RSA Algorithm Python Program

from decimal import Decimal 
  
def gcd(m,n): 
    if n==0: 
        return a 
    else: 
        return gcd(n,m%n) 
#input variables
p = input()
q = input()
no = input()
#calculate n
n = p*q 
#calculate totient
totient = (p-1)*(q-1) 

#calculate K
for k in range(2,totient): 
    if gcd(k,totient)== 1: 
        break
  
  
for i in range(1,10): 
    x = 1 + i*totient 
    if x % k == 0: 
        d = int(x/k) 
        break
local_cipher = Decimal(0) 
local_cipher =pow(message,k) 
cipher_text = ctt % n 
  
decrypt_t = Decimal(0) 
decrypt_t= pow(cipher_text,d) 
decrpyted_text = decrypt_t % n 
  
print('n = '+str(n))
print(' k = '+str(k))
print(' totient = '+str(t))
print(' d = '+str(d)) 
print('cipher text = '+str(ct))
print(' decrypted text = '+str(dt))

Input : p = 79 , q = 89 , message = 44

Output :

p = 79 , q = 89

t = 1373

k = 5

cipher text = 4119

decypted text = 44

3 responses to “RSA Algorithm an Asymmetric Key Encryption in Python”

DK says:
April 29, 2020 at 12:36 pm
What inputs does it take?
It gives me an error
TypeError: can’t multiply sequence by non-int of type ‘str’
Reply
- Abhishek says:
  January 26, 2021 at 11:53 am
  u have to convert it to type int sooo use
  p = int(input())
  Reply
Rushank Satardekar says:
March 25, 2021 at 9:12 pm
#this code works perfectly by mitesh and rushank
from decimal import Decimal
def gcd(k,totient):
while totient!= 0:
c = k % totient
k = totient
totient= c
return k
#input variables
d=0
p = int(input(“enter p”))
q = int(input(“enter q”))
message = int(input(“enter message”))
#calculate n
n = p*q
#calculate totient
totient = (p-1)*(q-1)
#calculate K
for k in range(2,totient):
if gcd(k,totient)== 1:
break
for i in range(1,10):
x = 1 + i*totient
if x % k == 0:
d = int(x/k)
break
local_cipher = Decimal(0)
local_cipher =pow(message,k)
cipher_text = local_cipher % n
decrypt_t = Decimal(0)
decrypt_t= pow(cipher_text,d)
decrpyted_text = decrypt_t % n
print(‘n = ‘+str(n))
print(‘ k = ‘+str(k))
print(‘ totient = ‘+str(totient))
print(‘ d = ‘+str(d))
print(‘cipher text = ‘+str(cipher_text))
print(‘ decrypted text = ‘+str(decrpyted_text))
Reply