Unlocking Secrets: A Beginner’s Guide to RSA Encryption and Decryption in Python

Pronay Biswas

In the realm of cryptography, RSA stands tall as a formidable and widely-utilized asymmetric encryption algorithm. It plays a pivotal role in the realm of securing digital communications and safeguarding sensitive information. In this article, we’ll embark on a journey to comprehend RSA encryption and delve into a Python program that showcases the art of RSA decryption.

Understanding RSA Encryption

RSA, an abbreviation for Rivest-Shamir-Adleman, takes its name from the brilliant minds behind its inception in 1977. Unlike symmetric encryption, which employs a single key for both encryption and decryption, RSA operates with a pair of keys: a public key for encryption and a private key for decryption.

To gain a grasp of how RSA encryption functions, let’s briefly summarize its core mechanics:

Key Generation:

1. Two large prime numbers p and q are carefully selected.
2. The modulus n is derived as n = p * q.
3. Euler’s totient function φ(n) is calculated as φ(n) = (p — 1)(q — 1).
4. An encryption exponent e is chosen, satisfying the condition 1 < e < φ(n) and ensuring it’s coprime to φ(n).
5. The decryption exponent d is computed as the modular multiplicative inverse of e modulo φ(n).

Encryption:

To transmit an encrypted message, the sender acquires the recipient’s public key, consisting of (n, e). The plaintext message is numerically encoded, and the ciphertext is determined using this formula:

ciphertext = (plaintext^e) mod n

Decryption:

The recipient utilizes their private key (n, d) to decrypt the ciphertext. The plaintext is calculated as:

plaintext = (ciphertext^d) mod n

With a solid foundation in RSA encryption, let’s now venture into our Python program.

# Import the 'inverse' function from the 'Cryptodome.Util.number' module
from Cryptodome.Util.number import inverse

# Define the plaintext message 'm' to be encrypted
m = 12

# Define the prime numbers 'p' and 'q' for RSA encryption
p = 3
q = 17

# Calculate the modulus 'n' by multiplying 'p' and 'q'
n = (p * q)

# Calculate Euler's totient function 'phi' for 'n'
phi = (p - 1) * (q - 1)

# Choose the public exponent 'e' (usually a small prime number, commonly 3 or 65537).
e = 5

# Calculate the private exponent 'd' using the modular multiplicative inverse of 'e' modulo 'phi'
d = inverse(e, phi)

# Encrypt the plaintext 'm' using the public key (n, e) and the 'pow' function
c = pow(m, e, n)

# Print the encrypted message.
print(f"The encrypted message is- {c}")

# Decrypt the ciphertext 'c' using the private key (n, d) and the 'pow' function
m = pow(c, d, n)

# Print the decrypted message
print(f"The decrypted message is- {m}")

Output of the above program-

The encrypted message is- 3
The decrypted message is- 12

This program functions as follows:

1. Import the inverse function from the Cryptodome.Util.number module: This function is used to calculate the modular multiplicative inverse, a crucial part of RSA key generation.
2. Define the plaintext message m to be encrypted: The variable m holds the message you want to encrypt. In this case, it’s set to the integer 12.
3. Define the prime numbers p and q for RSA encryption: p and q are two distinct prime numbers used to generate the RSA modulus n.
4. Calculate the modulus n by multiplying p and q: The modulus n is a part of both the public and private keys and is used in encryption and decryption.
5. Calculate Euler’s totient function phi for n: The Euler’s totient function (also known as phi or ϕ) of n is calculated as (p — 1) * (q — 1). It is used in the RSA key generation process.
6. Choose the public exponent e: e is the public exponent and is typically a small prime number, often set to 3 or 65537. It’s part of the public key.
7. Calculate the private exponent d using the modular multiplicative inverse of e modulo phi: The inverse function is used to compute d such that (d * e) % phi = 1. d is a critical component of the private key.
8. Encrypt the plaintext m using the public key (n, e) and the pow function: The plaintext m is raised to the power of e modulo n to produce the ciphertext c.
9. Print the encrypted message: The code prints the ciphertext c to the console.
10. Decrypt the ciphertext c using the private key (n, d) and the pow function: The ciphertext c is raised to the power of d modulo n to recover the original plaintext m.
11. Print the decrypted message: The code prints the decrypted plaintext m to the console.

RSA CTF Challenge Solution:

Given data-

#Given value with the challenge
c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
e = 65537

The Solution for the CTF Challenge-

# Import necessary functions from the 'Cryptodome' library.
from Cryptodome.Util.number import inverse, long_to_bytes

# Define the ciphertext 'c', modulus 'n', and public exponent 'e'.
c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
e = 65537

# Define the prime factors 'p' and 'q' of the modulus 'n'.
p = 189239861511125143212536989589123569301
q = 386123125371923651191219869811293586459

# Calculate Euler's totient function 'phi' for 'n'.
phi = (p - 1) * (q - 1)

# Calculate the private exponent 'd' using the modular multiplicative inverse of 'e' modulo 'phi'.
d = inverse(e, phi)

# Decrypt the ciphertext 'c' using the private key (n, d) and the 'pow' function.
m = pow(c, d, n)

# Convert the decrypted message 'm' from a long integer to bytes.
flag = long_to_bytes(m)

# Print the flag (decrypted message).
print(f"The flag is- {flag}")

The flag is- b’wctf2020{just_@_piece_0f_cak3}’