# 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 < < ϕ ( 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 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 = m5 mod 7031 = 4119

The private key is m = c1373 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

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

1. DK says:

What inputs does it take?
It gives me an error
TypeError: can’t multiply sequence by non-int of type ‘str’

• Abhishek says:

u have to convert it to type int sooo use
p = int(input())

2. Rushank Satardekar says:

#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))