Implement The RSA Algorithm
By Sudheer Satyanarayana
Introduction
In our last post, we wrote some Python functions in preparation to implement the RSA algorithm. In this post, we will implement the RSA algorithm.
Program On The Receiver’s Side
Create the public and private keys. Share the public key with the sender.
import random
from sympy import isprime
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def modinv(a, m):
m0, x0, x1 = m, 0, 1
if m == 1:
return 0
while a > 1:
q = a // m
m, a = a % m, m
x0, x1 = x1 - q * x0, x0
if x1 < 0:
x1 += m0
return x1
def generate_prime_candidate(length):
p = random.getrandbits(length)
# Apply a mask to set MSB and LSB to 1 to ensure a proper length prime
p |= (1 << length - 1) | 1
return p
def generate_large_prime(length=1024):
p = 4
while not isprime(p):
p = generate_prime_candidate(length)
return p
def generate_keypair(keysize):
p = generate_large_prime(keysize)
q = generate_large_prime(keysize)
n = p * q
phi = (p - 1) * (q - 1)
# Choose e
e = random.randrange(2, phi)
g = gcd(e, phi)
while g != 1:
e = random.randrange(2, phi)
g = gcd(e, phi)
# Generate d
d = modinv(e, phi)
return ((n, e), (n, d))
def decrypt(private_key, ciphertext):
n, d = private_key
# Decrypt each character
plain = [chr((char ** d) % n) for char in ciphertext]
return ''.join(plain)
# RSA Key Generation
keysize = 8 # Small size for demonstration; use 1024 or 2048 for real applications
public_key, private_key = generate_keypair(keysize)
print(f"Public Key: {public_key}")
print(f"Private Key: {private_key}")
Execute the program on the receiver’s computer. Take note of the public and private key. Share the public key with the sender.
Example output:
Public Key: (37769, 22739)
Private Key: (37769, 29279)
Encrypt The Message On Sender’s Computer
public_key = (37769, 22739) # output from the previous step
def encrypt(public_key, plaintext):
n, e = public_key
# Convert plaintext to a number using its ASCII representation
plaintext = [ord(char) for char in plaintext]
# Encrypt each character
cipher = [(char ** e) % n for char in plaintext]
return cipher
# Message to be encrypted
message = "HELLO"
# Encryption
encrypted_msg = encrypt(public_key, message)
print(f"Encrypted Message: {encrypted_msg}")
Output:
Encrypted Message: [26588, 36358, 34084, 34084, 29016]
Decrypt The Message On The Receiver’s Computer
private_key = (37769, 29279) # output from the first step
encrypted_msg = [26588, 36358, 34084, 34084, 29016] # output from the previous step
def decrypt(private_key, ciphertext):
n, d = private_key
# Decrypt each character
plain = [chr((char ** d) % n) for char in ciphertext]
return ''.join(plain)
# Decryption
decrypted_msg = decrypt(private_key, encrypted_msg)
print(f"Decrypted Message: {decrypted_msg}")
Output:
Decrypted Message: HELLO
In RSA encryption, the sender converts the plaintext message into a numerical form and raises it to the power of the public key exponent e, then takes the result modulo the product of two large prime numbers n. The ciphertext C is calculated as:
For decryption, the recipient raises the ciphertext C to the power of the private key exponent d and takes the result modulo n. The original message M is recovered as:
The security of RSA relies on the difficulty of factoring the large number n into its prime factors, which is necessary to derive the private key d from the public key.
