RSA Algorithm an Asymmetric Key Encryption in Python
By Sai RamHola, 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 = 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
What inputs does it take?
It gives me an error
TypeError: can’t multiply sequence by non-int of type ‘str’