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.

1. Choose two different large random prime numbers p and q
   
2. Calculate n = p q
   n is the modulus for the public key and the private keys
3. Calculate  ϕ ( n ) = ( p − 1 ) ( q − 1 )
4. Choose an integer k such that 1 < k  < ϕ ( n ) and k is co-prime to ϕ ( n ) : k and ϕ ( n )  share no factors other than 1; gcd (k, ϕ ( n ))= 1.
5. k is released as the public key exponent
6. Compute d  to satisfy the  d k ≡ 1 ( mod ϕ ( n ) )  i.e.: d k = 1 + x ϕ ( n ) for some integer x
7. 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

1. Choose two prime numbers: 79, 89.
2. Now n = 79*89 = 7031
3. Compute totient = (p-1)(q-1) = 6864 = t.
4. Find ‘k’ which is coprime with 6864 i.e., gcd(5,6864) = 1, k = 5.
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