Three possible approaches to attacking the RSA algorithm are as follows:

A. Brute force

B. Timing attacks

C. Other RSA vulnerabilities

A. Brute force attacks:

• The first step in cracking the private key is to find the two prime numbers p and q that were multiplied together to produce the modulus n.

• Determining φ(n) given n is equivalent to factoring n.

• With presently known algorithms determining d given e and n appears to be at least as time consuming as the factoring problem.

• Since we can brute force crack a private key by factoring N, the security of RSA depends on how difficult it is to factor large numbers.

Key size recommendations: To avoid values of n that may be factored more easily, the algorithm’s inventors suggest the following constraints on p and q.

i. p and q should differ in length by only a few digits. Thus, both p and q should be of the order of 1070 to 10100.

ii. Both (p-1) and (q-1) should contain a large prime number.

iii. gcd(p-1, q-1) should be small.

B. Timing attack:

• A timing attack is somewhat analogous to a burglar guessing the combination of a safe by observing how long it takes for someone to turn the dial from number to number.

• It has been observed that the RSA algorithm takes different amounts of time to perform its crypto operations according to the key’s value.

• So based on the time required to apply the private key to some information, some estimate can be made of the private key.

• The significance of this risk increases according to how close an attacker can get to the process performing the crypto operation.

• The attack is not feasible unless the attacker can closely monitor the processing time.

• Rivest has suggested a countermeasure that normalises the amount of computation time so that different keys take similar execution limits.

Other RSA vulnerabilities:

• While RSA naturally suffers from predictable vulnerabilities to brute force attacks at key recovery, its peculiar mathematical nature also makes it vulnerable to other attacks.

• These include attacks against message confidentiality and attacks against public key generation techniques.

• Fortunately, we can generally defend against mathematical attacks by using RSA carefully.

• The practical result is that RSA must be used sparingly.

• When encrypting for confidentiality, it is best to limit the plain text to random unpredictable data.

• RSA Data Security In (RSADSI) has developed a set of standards for applying public key cryptography.

• These standards are called public key cryptography standards (PKCS) and are available from RSADSI.

Three possible approaches to attacking the RSA algorithm are as follows:

A. Brute force

B. Timing attacks

C. Other RSA vulnerabilities

A. Brute force attacks:

• The first step in cracking the private key is to find the two prime numbers p and q that were multiplied together to produce the modulus n.

• Determining φ(n) given n is equivalent to factoring n.

• With presently known algorithms determining d given e and n appears to be at least as time consuming as the factoring problem.

• Since we can brute force crack a private key by factoring N, the security of RSA depends on how difficult it is to factor large numbers.

Key size recommendations: To avoid values of n that may be factored more easily, the algorithm’s inventors suggest the following constraints on p and q.

i. p and q should differ in length by only a few digits. Thus, both p and q should be of the order of 1070 to 10100.

ii. Both (p-1) and (q-1) should contain a large prime number.

iii. gcd(p-1, q-1) should be small.

B. Timing attack:

• A timing attack is somewhat analogous to a burglar guessing the combination of a safe by observing how long it takes for someone to turn the dial from number to number.

• It has been observed that the RSA algorithm takes different amounts of time to perform its crypto operations according to the key’s value.

• So based on the time required to apply the private key to some information, some estimate can be made of the private key.

• The significance of this risk increases according to how close an attacker can get to the process performing the crypto operation.

• The attack is not feasible unless the attacker can closely monitor the processing time.

• Rivest has suggested a countermeasure that normalises the amount of computation time so that different keys take similar execution limits.

Other RSA vulnerabilities:

• While RSA naturally suffers from predictable vulnerabilities to brute force attacks at key recovery, its peculiar mathematical nature also makes it vulnerable to other attacks.

• These include attacks against message confidentiality and attacks against public key generation techniques.

• Fortunately, we can generally defend against mathematical attacks by using RSA carefully.

• The practical result is that RSA must be used sparingly.

• When encrypting for confidentiality, it is best to limit the plain text to random unpredictable data.

• RSA Data Security In (RSADSI) has developed a set of standards for applying public key cryptography.

• These standards are called public key cryptography standards (PKCS) and are available from RSADSI.