RSA is an encryption method used in various places; through the Cryptography assignment in the Introduction to Information Security (IIS) course taken in OMSCS, I learned about the vulnerabilities of RSA. I would like to summarize what I learned, including the principles of RSA.

RSA Overall

RSA cryptography is classified as a public-key cryptographic method and is utilized in TLS and SSH. As a public-key system, the encryption key and decryption key are different, with the encryption key being public. Specifically, two distinct prime numbers p and q are chosen, and N = pq is established. The next step involves choosing a natural number e that is coprime to (p-1) x (q-1). Additionally, a natural number d is selected to satisfy the condition that ed leaves a remainder of 1 when divided by (p-1) x (q-1).

When encrypting, if we denote the message to be encrypted as m, the ciphertext c can be computed as follows:

For decryption, the calculation becomes:

Therefore, when the sender wants to encrypt a message, they use the public key N and e for encryption. On the other hand, recovering the encrypted message requires d, which is part of the private key along with p and q, none of which are publicly disclosed, making decryption possible only for those who possess this knowledge.

RSA Cryptography Explained

Extended Euclidean Algorithm

In solving the assignment, the Euclidean algorithm and extended Euclidean algorithm were utilized. While there are aspects that I do not fully understand, I will organize what I have learned. The Euclidean algorithm is one method for finding the greatest common divisor (gcd) of two natural numbers and is efficient in computing the gcd of large natural numbers. Given that values used in cryptography are typically large to ensure they cannot be easily calculated, the Euclidean algorithm proves effective.

Moreover, the extended Euclidean algorithm seeks to find pairs (x, y) satisfying:

From the definition of RSA, e and (p-1) x (q-1) are coprime. Letting l = (p-1) x (q-1), we find that gcd(e, l) = 1. Thus, the equation can be rewritten, and the value of x that satisfies it becomes d:

Implementing the Extended Euclidean Algorithm

Solving the Linear Diophantine Equation ax + by = c using the Extended Euclidean Algorithm

Vulnerabilities

As mentioned above, when a third party attempts to decrypt, they need to compute d, which requires knowledge of p and q. Since N is public, p and q can be discovered through the prime factorization of N, but factorizing a large N takes time and is not easy, which is an essential characteristic of RSA.

However, depending on the situation, several methods exist for a third party to exploit vulnerabilities in RSA cryptography to obtain p, q, d, or even the plaintext m itself.

Weak Key Attack

This vulnerability arises when multiple Ns are generated using the same random number generator, leading to shared values of p and q. In such cases, it becomes possible to obtain either p or q, ultimately enabling decryption. The following paper points out the detection of vulnerabilities in Ns sharing similar random number generators by calculating numerous Ns available on the internet.

Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

The specific method involves computing a Product Tree represented by the product of each N, followed by deriving a Remainder Tree from it to calculate gcd with each N. If this gcd is not equal to 1, then p and q can be computed.

Fast Bulk GCD Implementation in Go to Detect Shared Primes in RSA Keys

Implementation resources, such as the one below, may also be helpful.

Batch GCD

Broadcast Attack

This attack occurs when the same message is encrypted with small e values, resulting in the possibility of calculating the original message despite differing N values. Utilizing the Chinese Remainder Theorem, the message can be computed effectively, and implementing this requires careful definitions of a and m.

Hastad’s Broadcast Attack

A Simple Implementation of the Chinese Remainder Theorem

Parity Oracle Attack

Also known as the LSB Oracle Attack, this attack allows for the recovery of plaintext when the least significant bit (LSB) of the ciphertext can be determined upon decryption. While this scenario is somewhat unrealistic, the capability to ascertain the plaintext based on the knowledge of the LSB is exploited in this case. More details can be found in the following blog.

Implemented LSB Leak Attack

Practical Padding Oracle Attacks on RSA

Reflection

In the IIS course, the assignments are heavily mathematical, often resulting in lower scores among participants. Indeed, exploring the formulas behind each vulnerability and tracing the underlying theories proved to be quite time-consuming. Nonetheless, since RSA is something I utilize daily without conscious thought, this opportunity allowed me to learn the theory behind it and made many discoveries. I believe I gained a concrete understanding of what is public and what remains secret within public keys.