# 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 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. - k is released as the public key exponent
- Compute d to satisfy the d k ≡ 1 ( mod ϕ ( n ) )
**i.e.**: d k = 1 + x ϕ ( n ) for some 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^{5 }mod 7031 = 4119

The private key is m = c^{1373 }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

## Leave a Reply