Possible approaches to attacking the RSA algorithm are:
- Brute Force Attack
- Mathematical Attacks
- Timing Attack
- Diffie-Hellman key exchange
- Chosen ciphertext attacks
- Man-in-the-Middle Attack
Brute Force Attack: Security RSA
- This involves trying all possible private keys.
- The defense against this attack is to use a large key.
- However, the key should not be so large that it makes calculation too time to consume and hence impractical.
- Thus, there is a tradeoff between key size and security of RSA.
Mathematical Attacks: Security RSA
There are three approaches to attacking RSA mathematically, all of which are equivalent in effort to the factoring the product of two primes.
- Factor n into its two prime factors. This enables calculation of φ(n) = (p – 1)(q – 1), which in turn enables determination of d =e-1 (mod φ(n)).
- Determine φ(n) directly, without first determining p and q. Again, this enables determination of d =e–1 (mod φ(n)). This is equivalent to factoring n.
- Determine d directly, without first determining φ(n) which is at least as time-consuming as the factoring problem.
- Size of n should be considerably large.
- To avoid values of n that may be factored more easily, the
- P and q should differ in length by only a few digits.
- Both (p – 1) and (q – 1) should contain a large prime factor. o gcd(p – 1, q – 1) should be small.
Timing attacks: Security RSA
- These depend on the running time of the decryption algorithm.
- Moreover, It is a ciphertext-only attack.
- In RSA, modular exponentiation is done bit by bit. Suppose the system uses a modular multiplication function that is very fast in almost all cases but in a few cases takes much more time than an entire average modular exponentiation.
- The attack proceeds as follows:
- Suppose that the first j bits are known. o For a given ciphertext. The attacker can complete the first j iterations of the for-loop. o The operation of the subsequent step depends on the unknown exponent bit.
- For a few values of e and d, the modular multiplication will be extremely slow, and the attacker knows which these are.
- Therefore, if the observed time to execute the decryption algorithm always slow when this particular iteration is slow with a 1 bit, then this bit is assumed to be 1.
- Moreover, If a number of observed execution times for the entire algorithm fast, then this bit assumed to be 0.
- Generally, modular exponentiation implementations do not have such extreme timing variations but there is enough variation to make this attack practical.
Countermeasures to this attack are: Security RSA
- Constant exponentiation time: Ensure that all exponentiations take the same amount of time before returning a result. However, this degrades performance.
- Random delay: Better performance could achieved by adding a random delay to the exponentiation algorithm to confuse the timing attack. But if the defenders don’t add enough noise, attackers could still succeed by additional measurements to compensate for the random delays.
- Blinding: Multiply the ciphertext by a random number before performing exponentiation. This process prevents the attacker from knowing what ciphertext bits being processed inside the computer. And therefore prevents the bit-by-bit analysis that is essential to the timing attack. Steps for blinding are:
- Generate a secret random number r between 0 and n – 1.
- C’= C(re) mod n, where e is the public exponent.
- Compute M’= (C’)dmod n
- Compute M=M’r-1 mod n, r-1 is the multiplicative inverse of r mod n Implementing blinding incurs only a 2 to 10% performance penalty.