Introduction
In today's world, everyone is dependent on the Internet, which is an insecure channel to send a piece of information. We are using applications such as Whatsapp, Facebook, Instagram, Snapchat, etc. All these applications don't have any meaning without the internet. We use these applications to send and receive information, and these applications promise us to keep secure our information/data. These applications use Cryptographic Systems like RSA to secure the insecure channel (i.e., Internet).
In this blog, we will discuss different attacks on RSA Cryptosystem.
Attacks on RSA
Some of the possible attacks on RSA are:-
-
Brute force attack
-
Timing attacks
-
Computing phi(n)
Let’s discuss these attacks one by one.
Brute Force Attack
Let’s understand the brute force attack in simple steps:
-
Finding the two prime numbers, p and q, that were multiplied to get the modulus n is the first step in decrypting the private key.
-
Factoring n is equivalent to calculating φ(n) for a given n.
-
With the currently available algorithms, factoring the problem takes at least as long as figuring out d given e and n.
-
Since factoring N allows us to brute-forcibly crack a private key, RSA's security depends on how challenging it is to factor huge numbers.
Since the algorithm can be attacked by brute force, the RSA designers have put some constraints on p and q.
Also read - active and passive attacks
Timing Attack
Let’s understand the timing attack in simple steps.
-
A timing attack is similar to a thief figuring out a safe's combination by watching how long it takes someone to flip the dial from one number to the next.
-
It has been found that the value of the key influences how long the RSA algorithm needs to complete its cryptographic operations.
-
Therefore, a rough estimate of the private key can be generated based on the time needed to apply it to certain information.
-
Depending on how close an attacker may approach the process of carrying out the crypto operation, the significance of this danger grows.
-
If the attacker cannot watch the processing time closely, the attack is not practical.
- Rivest has proposed a solution that normalizes computation time so that different keys have comparable execution limits.
Computing φ(n)
We know that computing φ(n) is no easier than factoring n.
If we know n and φ(n), and n is the product of two primes p and q, then n can be easily factored by solving the two equations:-
n = p*q (Eqn 1)
φ(n) = (p − 1)(q − 1) (Eqn 2)
For the two “unknowns,” p and q. The following steps make it simple to do this. When we put q = n/p into the second equation, we get a quadratic equation with the number p being unknown:-
p2 - (n- φ(n)+1)p +n = 0.
The two roots of the above equation will be p and q, the factors of n. Therefore, a cryptanalyst can factor n and undermine the system if he discovers the value of φ(n). In other words, computing φ(n) is not any simpler than factoring n.
You can read about the difference between Active Attack and Passive Attack in detail here.
84+ registered