Understanding RSA Encryption: Security and Vulnerability in Networks

Introduction

The Rivest-Shamir-Adleman (RSA) encryption algorithm was invented as a solution for a public-key cryptography system. This became the most widely used cryptography system. RSA is used to exchange keys which then will be used in a symmetric cipher like the Advanced Encryption Standard (AES) to encrypt and decrypt the bulk data. [1, P. 173] [2, P. 296] [3]

The RSA encryption algorithm

The underlying one-way function of RSA is the integer factorization problem: Multiplying two large primes is computationally easy (in fact, you can do it with paper and pencil), but factoring the resulting product is very hard. [1, P. 174] Given the public key $(n,e) = k_{pub}$ and the plaintext $x$, the encryption function is:

$y = ek_{pub}(x) \equiv y^e \mod n \\ \text{,where } x, y \in \mathbb{Z}_n$

In practice, x, y, n and d are very long numbers, usually 1024 bit long or more. [1, P. 174]

Requirements

• It must be computationally infeasible to determine the private-key d given the public-key values e and n.
• We cannot encrypt more than l bits with one RSA encryption, where l is the bit length of n.
• It should be relatively easy to calculate $xe \mod n$, and to calculate $yd \mod n$ (encrypt and decrypt).

For $(M^e)^d \mod n = M$to be true, $e$ and $d$ have to be multiplicative inverses $\mod \phi(n)$. $\phi(n)$ is the number of positive numbers that are relatively prime to $n.$

The public key $(e, n)$ is known to everyone. Even the attacker. The private key $(d, n)$ is only known by the actor who is supposed to decrypt the message. If Alice wants to send a message to Bob, she uses Bobs public key to encrypt the message. This public key cannot be used to decrypt the message. The message can only be decrypted using bobs private key. The public and private key have to be generated in a way that $e*d \equiv 1 \mod \phi(n)$

Applicable usage for RSA

The RSA algorithm is primarily used for signing documents or encrypting keys rather than encrypting large amounts of data. This is because the RSA algorithm, being an asymmetric encryption algorithm, is significantly slower compared to symmetric encryption algorithms. To overcome this limitation in practice, the RSA algorithm is typically used to securely encrypt the key of a symmetric encryption algorithm. This allows two parties to exchange session keys securely using RSA, and then use the faster symmetric encryption algorithm like AES to encrypt and communicate large volumes of data. [4]

Modern RSA-based encryption

Based on the RSA encryption algorithm, numerous modified implementations have been proposed over the years. These mainly focus on enhancing the security and runtime of the RSA algorithm.

RSA Cryptosystem based on n Prime Numbers and Offline Storage

In their paper ”Enhanced, Modified and Secured RSA Cryptosystem based on n Prime Numbers and Offline Storage for Medical Data Transmission via Mobile Phone” [5] the authors propose a modernized RSA encryption method that uses multiple prime numbers and offline storage to enhance the security of medical data transmission via mobile phones.

The main contribution of this paper is the proposal of a more secure RSA algorithm that uses multiple prime numbers (n primes) and offline storage for essential RSA parameters. This enhanced RSA algorithm performs a triple encryption-decryption using these n prime numbers, making it harder to break the factorization of the variable N. As a result, the key generation time is longer than that of the traditional RSA. The authors argue that this approach makes the security of medical data less vulnerable to hackers who might attempt to discover the factorization of the two prime numbers used in the traditional RSA.

Improved RSA Algorithm for Enhanced Security

In ”An ImprovedRSA Algorithm for Enhanced Security,” [6] Balasubramanian, Arun, and Sekar present modifications to the traditional RSA algorithm. They suggest a method to subtly conceal RSAs publicly disclosed parameters, offering an added layer of obfuscation by ensuring the public values differ from those used internally. This approach integrates two distinct algorithms, with a mechanism for random selection during encryption, adding unpredictability to the process. The authors also touch upon the vulnerabilities of the RSA algorithm, such as factorization and timing attacks, and hint at a more streamlined implementation of the modular exponentiation algorithm. Their work underscores the importance of refining and adapting cryptographic systems in response to evolving challenges.

New RSA Encryption Mechanism Using One-Time Encryption Keys and Unpredictable Bio-Signal

In the paper titled ”New RSA Encryption Mechanism Using One-Time Encryption Keys and Unpredictable Bio-Signal for Wireless Communication Devices” [7] by Hoyoung Yu and Youngmin Kim, the authors address the challenges of applying the traditional RSA encryption method to wireless communication devices, particularly IoT devices. They highlight the inefficiencies of using large RSA keys in such devices due to their limited hardware capabilities and power constraints. To overcome these challenges, the authors introduce a novel RSA mechanism that leverages a True Prime Random Number Generator (TPRNG) based on unpredictable bio-signals. This TPRNG produces prime numbers that are resistant to prediction, enhancing the security of the RSA encryption process. The proposed RSA mechanism utilizes smaller 32-bit keys, which are more suitable for wireless communication devices. After the encryption and decryption processes are completed, the keys are immediately discarded and regenerated, adding an additional layer of security. This approach not only ensures efficient real-time data exchange but also mitigates potential vulnerabilities associated with maintaining large keys in memory, making it a promising solution for modern wireless communication devices.

Use Case Scenario

For the use case we imagine the following scenario: Alice is a journalist who works for a reputable news agency. She has obtained some sensitive information about a corruption scandal involving a high-ranking government official. She wants to share this information with her editor, Bob, who is in another country. However, she is afraid that her communication might be intercepted by the government or other malicious parties who want to prevent the story from being published.

Case A: Alice sends an encrypted message to Bob who can use his private key to decrypt it. The malicious party does not possess Bob's private key so they cannot read the message.
Case B: The malicious party intercepted Alice's original message and replaced it with their own. Bob notices the attack because Alice's public key cannot confirm a signature.

As shown in case A of figure 1, RSA encryption does not require Alice and Bob to share a common secret key beforehand, which might be difficult or risky in their situation. This means that Alice and Bob can communicate securely without having to meet in person or use a third-party service that might be compromised or monitored. Even if the malicious party got a hold of the encrypted message, they would not be able to decrypt it without Bob’s private key. Since we also implemented signing, Bob can ensure that the received message is from Alice. Case B of figure 1 shows how an attacker could alter the content of a message sent by Alice. Bob would see this message as being sent by Alice but when checking the signature the attack would be obvious to him. Alice could also use RSA to share a key with Bob which is then used to encrypt a longer message

Design And Implementation

The RSA encryption algorithm was first developed in a jupyter notebook and then split up into different files. Then an application focusing on the use case was developed using the PyQt6 library. This section provides an in-depth exposition of each component.

Generating RSA Key Pairs

RSA encryption relies on the challenge of factoring large composite numbers. Generating secure RSA key pairs is therefore crucial for the encryption's security. This subsection outlines the RSA key pair generation process, as implemented by me.

Greatest Common Divisor (GCD)
Before diving into RSA key pair generation, it’s important to introduce the gcd function shown in listing 1. The RSA algorithm requires determining numbers that are co-prime to each other. The gcd function, which calculates the greatest common divisor of two integers using the Euclidean algorithm, assists in this verification. This algorithm was taken from GeeksForGeeks [13]

def gcd(a, b):
    if (a == 0):
        return b
    return gcd(b % a, a)

Prime Number Generation
The function large_prime_generator is instrumental in selecting two distinct large prime numbers, crucial for the RSA algorithm. The helper function is_prime checks the primality of a given number. The procedures in Listing 2 provide a straightforward approach to generating primes, although optimizations could further enhance their efficiency. The runtime could for example be sped up using a text file containing pre-calculated large prime numbers could be used in combination with a random number generator to pick one line out of the list of prime numbers. This will increase the speed greatly.

def large_prime_generator(size):
    while True:
        p = random.randint(2**(size - 1), 2**size - 1)
        if is_prime(p):
            return p

def is_prime(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

Modular Inverse Calculation
The modular_inverse function, shown in Listing 3, calculates the modular multiplicative inverse of an integer, a crucial step in deriving the private key in the RSA algorithm. This function was inspired by GeeksForGeeks. [14]

def modular_inverse(a, n):
    t, new_t = 0, 1
    r, new_r = n, a
    while new_r != 0:
        quotient = r // new_r
        t, new_t = new_t, t - quotient * new_t
        r, new_r = new_r, r - quotient * new_r
    if r > 1:
        raise ValueError("The modular inverse does not exist.")
    if t < 0:
        t += n
    return t

RSA Key Pair Generation
The rsa_key_generation function encapsulates the entire process of generating the RSA key pair. It integrates the utility functions and mathematical operations to produce both the public and private keys crucial for RSA encryption and decryption. The steps executed by the function in Listing 4 are:

1. Utilize the large_prime_generator function to generate a prime number $p$.
2. Generate another prime number $q$ distinct from $p$ using the same function.
3. Compute $(n=p×q)$, which serves as the modulus for both the public and private keys.
4. Determine $p \phi(n)$ using the formula $\phi(n) = (p-1)(q-1)$, representing Euler's totient function for $n$.
5. Select a random number $e$ between $2$ and $\phi(n)$ and ensure that it's coprime to $\phi(n)$ using the gdc function.
6. Compute the private key $d$ using the modular_inverse function such that $d \times e \equiv 1 \mod \phi(n)$.
7. Return both the public key $(n, e)$ and the private key $(n,d)$.

def rsa_key_generation(size):
    p = large_prime_generator(size // 2)
    q = p
    while q == p:
        q = large_prime_generator(size // 2)
    n = p*q
    phi_n = (p-1)*(q-1)
    e = random.randint(2, phi_n)
    while (gcd(e, phi_n) != 1):
        e = random.randrange(2, phi_n)
    d = modular_inverse(e, phi_n)
    return (n, e), (n, d)

Using this algorithm to generate RSA key pairs would not work in real life since it slows down significantly for keys that are larger than 80 bits. In reality it is assumed that keys with a length of 512 bits are not secure, thus 2048 bit keys are most common.

Encryption Process

Having obtained a public key, we can use the encryption process to encrypt some plain text. This subsection provides insights into the encryption process as implemented by me.

String to Blocks Conversion
Before the encryption process can commence, the message to be encrypted needs to be converted into suitable blocks. The string_to_blocks function shown in Listing 5 achieves this by performing the following steps:

1. Convert the string message into its binary representation.
2. Determine the padding needed based on the desired block size $n$.
3. Append zeros to the binary message to ensure it's a multiple of the block size.
4. Split the binary message into blocks of size $n$.
5. Convert each binary block into its decimal representation

def string_to_blocks(message, n):
    binary_message = ''.join(format(ord(char), '08b') for char in message)
    padding_needed = (n - len(binary_message) % n) % n
    binary_message += '0' * padding_needed
    blocks = [binary_message[i:i + n] for i in range(0, len(binary_message), n)]
    decimal_numbers = [int(block, 2) for block in blocks]
    return decimal_numbers

Block Encryption
The encrypt_block function shown in Listing 6 takes each block and encrypts it using the public key.

def encrypt_block(block, public_key):
    n, e = public_key
    ciphertext = pow(block, e, n)
    return ciphertexts

Message Encryption
The main encryption function, encrypt_message, integrates the previously discussed functions and operations to encrypt an entire message. Using the methods illustrated in Listing 7, a message is transformed from its raw form into a series of encrypted blocks, ensuring confidentiality during transmission or storage.

def encrypt_message(message, public_key):
    n, e = public_key
    max_block_value = n - 1
    block_length = math.floor(math.log2(max_block_value+1))
    blocks = string_to_blocks(message, block_length)
    encrypted_blocks = [encrypt_block(block, public_key) for block in blocks]
    return encrypted_blocks

Decryption Process

Upon receiving an encrypted message, the decryption process becomes essential to retrieve the original plaintext using the private key. This subsection offers a thorough look into the decryption process, as crafted by me.

Blocks to String Conversion
An integral part of the decryption process is converting the decrypted blocks back into the original message format. The blocks_to_string function, depicted in Listing 8, performs this task by taking the following actions:

1. Convert the decimal numbers (decrypted blocks) into binary strings, ensuring they match the block length.
2. Concatenate the binary strings to form a single continuous binary message.
3. Segregate the binary message into 8-bit blocks and convert each to its respective character.

def blocks_to_string(decimal_numbers, n, block_length):
    binary_strings = [format(num, '0{}b'.format(n)) for num in decimal_numbers]
    binary_message = ''.join(binary_strings)
    message = ''.join([chr(int(binary_message[i:i+8], 2)) for i in range(0, len(binary_message), 8)])
    return message

Block Decryption
The decrypt_block function, illustrated in Listing 9, decrypts each block using the private key. Modular exponentiation facilitates this decryption.

def decrypt_block(ciphertext, private_key):
    n, d = private_key
    decrypted_block = pow(ciphertext, d, n)
    return decrypted_block

Message Decryption
The main decryption function, decrypt_message, uses the previously discussed functions and procedures to decrypt an entire message. Using the methods depicted in Listing 10, the encrypted message is transformed back into its original plaintext form, allowing for secure communication.

def decrypt_message(encrypted_blocks, private_key):
    n, e = private_key
    max_block_value = n - 1
    block_length = math.floor(math.log2(max_block_value+1))
    decrypted_blocks = []
    for block in encrypted_blocks:
        decrypted_blocks.append(decrypt_block(block, private_key))
    return blocks_to_string(decrypted_blocks, block_length, block_length)

Application And Key Distribution System

The application is designed to show how RSA encryption can be used in a basic messaging system for journalists and their editors. However, it's a simple version meant for demonstration of key distribution systems and encrypted communication.

Application Overview
When a user opens the application, they first see a login page. After logging in or registering, they're taken to their main user page. Here, they can see any encrypted messages they've received. When they click on a message, the application decrypts it so they can read it. There's also an option for users to send encrypted messages to others. When sending a message, the application encrypts it using the recipient's public key and then with the senders public key. This ensures the recipient can be assured that the massage was actually sent by the supposed sender. The encrypted message then gets saved in the database until the recipient logs in to read it.

Flowchart showing how users interact with the application.

Database and Key Handling
The application uses an SQLite database called users.db. This database has a table for user names and their public keys, and another table for storing encrypted messages, who sent them, and their intended recipient. When a user registers, the application creates an RSA key pair for them. The public key is saved in the database, and the private key is saved as a txt file offline. This way of handling keys is simple, but it puts a lot of responsibility on the user to keep their private key safe.

Limitations and Context
While this application provides a clear example of how RSA encryption can be used in messaging, it's important to remember it's just a basic version and lacks the security features needed for real-world use. The application's login system is basic. It checks if a username is already in use and if not, it creates a new account. There's no password or two-factor authentication, so it's not secure by modern standards. When a new user registers, the system generates an RSA key pair for them. Their public key gets saved in the application's database, but the private key is just given to the user to keep offline. This means the security of messages depends on users keeping their private key secret and safe, which isn't ideal for a real-world application.

Test Results

The user application was tested with different Messages and multiple users. The messages were correctly encrypted and decrypted regardless of the message length. We also tested weather a message that was altered by an attacker could be detected. To do this, the private key of Charlie was changed to simulate a situation where an attacker who does not have access to charlies private key, sends a message posing as him. Figure 3 shows how the malicious message from the attacker posing as Charlie will appear to Bob.

Encrypted message sent by an attacker and signed using the wrong key.

We also tested the time it takes for our application to generate keys with different lengths from 8 bit up to 128 bit. Figure 4 shows how the key generation time grows exponentially with larger key values.

Time vs Key Size

Discussion

The RSA encryption algorithm has gained attention due to its notable security features and its ability to resist numerous cryptographic attacks.

Strengths Of RSA Encryption

The mathematical foundation of RSA, rooted in the challenge of factoring large composite numbers, stands as one of its primary strengths. The RSA algorithm uses a one-way function, making it challenging for attackers to reverse engineer the key pair [15]. Moreover, using larger key sizes enhances the algorithm's security, offering resistance against brute-force attacks. Efficient encryption and decryption processes, especially with optimized algorithms, further enhance its effectiveness. [16]

Limitations And Vulnerabilities

Despite RSA's strengths, it has its vulnerabilities. The selection of prime numbers remains a concern as its computational intensive and an improper choice can introduce vulnerabilities. The security of the RSA algorithm depends heavily on the private key's confidentiality. A compromised private key endangers the entire encryption. While RSA can resist many current attacks, it might not withstand all future cryptanalytic techniques. For example, the advent of quantum computers could threaten RSA by factoring large numbers quickly, potentially making RSA insecure. [17]

[1] C. Paar and J. Pelzl, Understanding Cryptography: A Textbook for Students and Practitioners. Springer Berlin Heidelberg, 2009. [Online]. Available: https://books.google.no/books?id=f24wFELSzkoC

[2] W. Stallings, Cryptography and Network Security: Principles and Practice, Global Edition, 8th ed. Pearson, 2022.

[3] L. Kee, “Rsa is dead — we just haven’t accepted it yet.” [Online]. Available: Forbes Article

[4] Naqi, W. Wei, J. Zhang, W. Wang, J. Zhao, J. Li, P. Shen, X. Yin, X. Xiao, and J. Hu, “Analysis and research of the rsa algorithm,” Information Technology Journal, vol. 12, pp. 1818–1824, 2013.

[5] A. H. Thiziers, H. C. Th´eodore, J. Zoueu, and B. Michel, “Enhanced, modified and secured rsa cryptosystem based on n prime numbers and offline storage for medical data transmission via mobile phone,” International Journal of Advanced Computer Science and Applications, 2019.

[6] D. K. Balasubramanian, M. Arun, and D. K. R. Sekar, “An improved rsa algorithm for enhanced security,” Indian Journal of Cryptography and Network Security, 2022.

[7] H. Yu and Y. Kim, “New rsa encryption mechanism using one-time encryption keys and unpredictable bio-signal for wireless communication devices,” Electronics, vol. 9, p. 246, 2020.

[8] “A record number of journalists are in jail right now, according to ...” 2021. [Online]. Available: CNN Article

[9] “Journalists killed worldwide 2022,” 2022. [Online]. Available: Statista Article

[10] "Cpj: Record number of journalists jailed in 2021,” 2021. [Online]. Available: DW Article

[11] “Rsf: More journalists imprisoned or killed in 2022,” 2022. [Online]. Available: DW Article

[12] (2023) Internet censorship 2023: A global map of internet restrictions. [Online]. Available: Comparitech Article

[13] “Euclidean algorithms (Basic and Extended) - GeeksforGeeks — geeksforgeeks.org,” GeeksforGeeks Article, [Accessed 13-10-2023].

[14] “Modular multiplicative inverse - GeeksforGeeks — geeksforgeeks.org,” GeeksforGeeks Article, [Accessed 13-10-2023].

[15] A. Philips, J. Jayaraj, T. JoshF., and P. Venkateshkumar, “Enhanced rsa key encryption application for metering data in smart grid,” Int. J. Pervasive Comput. Commun., vol. 17, pp. 596–610, 2021.

[16] G. Roc´ıoRodriguez, M. GerardoCastang, and C. A. Vanegas, “Information encryption and decryption analysis, vulnerabilities and reliability implementing the rsa algorithm in python,” pp. 391–404, 2021.

[17] A. Hamza and B. Kumar, “A review paper on des, aes, rsa encryption standards,” in SMART, 2020, pp. 333–338.