Understanding RSA and It’s Security Issue

First Let’s try to understand what the hell is RSA, and why it’s RSA?

RSA is asymmetric encryption, which means it’s an encryption algorithm and RSA Stands for Rivest, Shamir, and Adleman these are the last names of those persons who created the RSA Algorithm. Let’s not make this a history lesson, On the previous statement I described RSA is as asymmetric encryption, Now What the hell is Asymmetric encryption?

Asymmetric Encryption -> Asymmetric encryption also known as public key encryption uses two keys to encrypt and decrypt the data, 1 key encrypts in pre-transits and the other key decrypts in post-transits, it solves the issue of symmetric encryption which uses a single key for encryption and decryption. Let’s make the asymmetric more simple with the illustration below.

so you don’t need to share key to encrypt or decrypt message, both private key and public key can encrypt and decrypt message .The opposite key from the one used to encrypt a message is used to decrypt it. That means if you encrypt a message with Public key you need Private key to decrypt it.

So, we got the basic idea what RSA is, let’s understand how it’s algorithm works, don’t worry its not that much complicated.

RSA Algorithm

Before jumping into RSA Algorithm , lets sharpen our knowledge a little bit so the Algorithm looks simple.

Factors: A number that can be multiplied by another number to equal a desired number. Example: 1, 2, 4, 8 are factor of 8. See the image below for understanding it more clearly. It doesn’t have to be crisscrossed like the image below.

Prime: This number is only dividable by 1 without any reminder, example as 2,3 5.

Semi-Prime: Semi-Prime number is a positive positive integer whose factors are exactly two prime number. excluding the number itself and 1.

Semi-Prime

Modulo: It’s Just reminder division, that means the leftover/reminder are modulo. example if you 20 MOD 6 = 2.

we’ve covered most of the concepts that will help us understand the RSA algorithm. We’ve discussed prime numbers, the modulus, semi-prime numbers, Factors. Now lets cover up the generation Part.

RSA Generation Math

RSA Generation has two steps:

1. Generating Keys
2. And Using them for encryption and decryption

Generating Keys [Let’s go through all the parts of key generation ]

• Choose any two prime numbers randomly, Let’s think of those two numbers as (p,q), Now let’s set two values to them p=17, q=19
• Calculate the Product, We can calculate the product by using this formula (p*q) let’s think of the product value as n, (17*19)=323 which means n=323
• Now let’s calculate the totient, let’s think of totient as t, (p-1)*(q-1)=t which means we need to calculate (16)*(18) = 288

Now we need to generate a public key, we can define a public key as (e), but before selecting a public key we need to fulfil 3 conditions.

1. Public Key Must be a prime number
2. The public key must be less than the value of totient, in our case, totient is t=288
3. the public key must not be a factor of totient, remember previously we talked about factors, this condition describes that if we factor t=288 the public key should not match any factor. the formula for checking is (t mod e). if it returns 0 that means it’s a factor of totient.

let’s take 5 as e (public key), 5 is less than 288, so let’s check if it is a factor of 288 or not.

so 5 meets all the conditions to be a public key, let’s take it as public key e=5 (323, 5)(n,e). now let’s choose a private key and mark it as d. there is one condition that needs to be filled in before assigning the number as a private key. the condition is

1. (d*e) mod t = 1 if the private key fulfills this condition we can use it as a private key.

lets take d=173 which full-fills the condition the statement (d*e) mod t = 1 is true for 173 (323, 173)(n,d) .

Encryption and Decryption (All the parts of encryption and Decryption)

Encryption Formula: plaintext ^ e mod n = ciphertext

let’s think plaintext=65 now let’s encrypt it using our public key which is e=5, now let’s calculate the cypher using the formula. our cyphertext=12

Decryption Formula: ciphertext ^ d mod n = plaintext

Now let’s decrypt our cyphertext=12 and d=173 and n=323, now let’s apply the formula, we got the decrypted plaintext.

you can reverse the algorithm, you can use the private key to generate the cypher and the public key to decrypt the cypher. just reverse the formula

Encryption Formula: plaintext ^ d mod n = ciphertext

Decryption Formula: ciphertext ^ e mod n = plaintext

Security issues in RSA

Similar to all other components in the information security world, RSA also has some issue that helps an attacker decrypt it using some common attacks.

Factorization attack

what is a factorization attack?

In the RSA encryption algorithm, there are two keys: a public key and a private key. The security of RSA is based on the difficulty of factoring a large number into its prime factors. A factorization attack is an attempt to figure out those two original prime numbers, which would allow an attacker to calculate the private key. If an attacker can factorize the big number into its prime factors, they can break the security of RSA. In simple terms, if an attacker somehow knows e (public key), and n (product) the attacker is able to factorize and break the RSA by finding the private key. this attack is not possible if the length of the n is longer than 300. (Key Size Guideline).

We’ve covered the theoretical part now let’s cover the practical scenario. For this we are using an RSA Challenge Generator, and we are using python3 to calculate the factorization and find the private key.

let’s try with a 60-bit prime challenge, in this case, our e=65537 (public key) which is used to encrypt the plain text to cypher, and the value of the product n=764499076479205600378581343439581367 and the cipher we need to decrypt is cipher=150914038644245037992148531205711831, let’s write a python script to calculate the factorial of n and calculate the private key to decrypt the cipher, we are using a library named sympy to calculate the factorial.

from sympy import factorint
e = 65537
n=764499076479205600378581343439581367
c=150914038644245037992148531205711831

factors = factorint(n)
p, q = list(factors.keys())
totient = (p - 1) * (q - 1)
d = pow(e, -1, totient) #private key calculation
m = pow(c, d, n)

print(f"Private key: {d}")
print(f"Decrypted MSG: {m}")

let’s run the script and see if it is able to find the private key and decrypt the msg.

the script is same for other limited-to 128bit, the increase of bit will increase the time of calculating factor. if your computer has a GPU the chance of handling much bigger lengths. you can check out the challenges in RSA_Factoring_challenge, put forward by RSA Laboratories on March 18, 1991[1].

Wieners attack

The title seems offensive, let’s go in little deeper about this attack in a more easy way, Wiener’s Attack is a way to break RSA if the private key is too small. let’s break down this explanation into two parts. 1. Why does size matter? , 2. How does the attack work?

Why does size matter? →A big part of the RSA Encryption is a private key a number we marked as d previously, If d is too small compared to another number called n(the product of two random prime numbers), Wiener’s Attack can work.

How does the attack work? → Wiener’s Attack uses math tricks involving fractions. If d is too small, an attacker can figure out the private key and decrypt messages without permission. In simpler terms, Wiener’s attack is like playing with fractions to guess the private key. But, if you use a big enough private key, this guessing game becomes very hard and practically impossible, which is why it’s important to follow best practices in choosing key sizes for RSA.

If you want to know more about the attack and understand the in-depth you can see these documents Cryptanalysis of Short RSA Secret Exponents, A variant of Wiener’s attack on RSA, for practical demonstration I am using owiener by orisano. let’s write a simple script to see how to use it with owiener.

import owiener
e = 4805054278857670490961232238450763248932257077920876363791536503861155274352289134505009741863918247921515546177391127175463544741368225721957798416107743
n = 6727075990400738687345725133831068548505159909089226909308151105405617384093373931141833301653602476784414065504536979164089581789354173719785815972324079
c = 719124097362780301249612993034449477
d = owiener.attack(e, n)
print("Private key: " + str(d))

you can learn more about this attack from https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack

there are more attacks that can be used to crack weak implemented RSA encryption. Let’s understand those with two points, so it is not that hard to understand.

Brute Force

• Idea: Trying every possible combination to break the RSA key.
• Challenge: Impractical with large key sizes.

Common Modulus Attacks

• Situation: Two parties use the same modulus for RSA.
• Risk: Compromising one party’s private key might expose information about the other.

Side-Channel Attacks

• Idea: Exploiting information leaked during cryptographic processes.
• Examples: Power consumption, electromagnetic radiation, or sound analysis.

etc. (RSA is Secure if you are able to implement it correctly).

if you are a CTF player, you have to go through the RSA Challenges, here are a few references you can use to learn,

• (baby_RSA) [Coppersmith method]
• Basics — Crypto — RSA
• Basic RSA challenges in CTF by An Hoang
• The Obligatory RSA Challenge

for CTF challenges you can use this tool to solve most of the challenges related to the RSA .

GitHub - RsaCtfTool/RsaCtfTool: RSA attack tool (mainly for ctf) - retrieve private key from weak…

Human Makes mistake, please refer to any part of this article if the representation of RSA is not correct for some reason or i have explained something in the wrong way, thanks.