*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?*

A*symmetric 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*

*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.*

*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:*

*Generating Keys**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*17*p=**, q=19**Calculate the Product, We can calculate the product by using this formula**(p*q)**let’s think of the product value as*323*n, (17*19)=**which means*323*n=**Now let’s calculate the**totient**, let’s think of totient as**t**,**(p-1)*(q-1)=t**which means we need to calculate*288*(16)*(18) =*

*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.*

*Public Key Must be a prime number**The public key must be less than the value of totient, in our case, totient is**t=288**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*

*(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 .*

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.