There are some possible approaches to attacking the RSA algorithm.

First, there is the brute force.

The defense against the brute force attack is the

same for RSA as for other crypto systems,

which is to use a larger keyspace.

Therefore, the larger the number of bits in the private key D,

the higher the resistance against brute force attack.

However, because the calculations involved in

both key generation and encryption-decryption are complex,

the larger the size of the key,

the slower the system for the RSA to run.

As discussed previously, RSA security depends

on the prime factorization problem, more specifically,

from the modulus N,

it should be difficult to derive the prime factors P and Q,

which will also protect the phi of N used for the key set up.

Prime factorization problem is still

an open problem and we are relying on the fact that there is

no known algorithm that is sufficient enough to find

the prime factors given large enough N. In other words,

there's no proof that the problem is difficult,

but we are relying on the fact that,

at this point of time,

there's no known algorithm with sufficient efficiency to break

the prime factorization problem for large enough N. RSA

laboratory used to post

the RSA factoring challenges to better

gauge the state of the art for cracking prime factorization.

The RSA factoring challenges began in 1991 and ended in 2007.

The key sizes that they posted for challenges were in the order of hundreds of bits.

For example, a 729-bit long key was cracked in

2016 and the key size kept growing as the computing technology and algorithms advance.

In general, RSA does not recommend using 1024-bit key size but

recommend using 2048 bits or longer.

There can also be site channel attacks on RSA.

In fact, Paul Kocher,

in the mid 1990s,

actually targeted RSA cipher when inventing the notion of site channels,

which we also reviewed in the Cryptography and Information Theory course.

In the timing-based site channel attack,

the attacker can infer the operant size based on

observing how long it takes to compute the cryptographic operations.

For example, a higher key value or higher exponent takes longer to compute.

An analogy to timing-based site channel attack

can be a burglar guessing the combination of a

safe by tracking how long it

takes for someone to turn the dial from one number to another.

Although the timing attack is a serious threat,

there are simple countermeasures that can be used for obfuscating the operation duration,

including using constant exponentiation time algorithms and adding random delays.

Also, the RSA cipher is vulnerable to a Chosen Ciphertext Attack, or CCA.

CCA is an attack in which an attacker chooses a number of ciphertext and is then,

given the corresponding plaintext decrypted with the victim's private key.

The attacker exploits properties of RSA and selects blocks of data that,

when processed using the victim's private key,

yield information needed for cryptoanalysis.

More specifically, the vulnerability comes from the fact that

RSA uses exponentiation for encryption and,

therefore, it is multiplicative over encryptions.

For example, the ciphertext for M1 multiplied by the ciphertext for M2

is equal to the ciphertext corresponding to the encryption input of M1 times M2.

Suppose an attacker receives ciphertext C and wants to learn

the corresponding plaintext M. It can choose a CCA ciphertext C_prime,

a known ciphertext C prime,

which is equal to C_times_R_to_the_Eth_power,

mod_N, for some chosen R by the attacker.

Then the plaintext corresponding to that chosen ciphertext is M_prime,

which is equal to M_times_R, mod_N.

The attacker can take M_prime and multiply it with

the multiplicative inverse of R_mod_N to

retrieve the original message M that it wanted to learn.

Chosen Ciphertext Attack can be countered with random padding of plaintext,

which is the basis for the Optimal Asymmetric Encryption Padding,

or OAEP, recommended by RSA Security, Inc.