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.
and 4 others joined a min ago.
teamques10
★ 68k