RSA cryptosystem was first discovered in 1977 by Adi Shimir, Ron Rivest and LEN Adleman (Dan, 1999). The RSA system is most commonly used cryptosystem for providing privacy and enabling authenticity of digital data. The RSA system is used by various commercial systems. RSA is used to secure web traffic, to ensure authenticity and privacy of Email, to secure login sessions, and the system is also the backbone of electronic credit-card payment systems.
Since it was released, the RSA system has been scrutinized for vulnerabilities, years of research illustrate some intriguing attacks, but none of them is devastating. They show the danger of the wrong usage of RSA. This report aims at exploring some of these attacks.
Discussions
RSA system encryption can be explained as follows. Let N=pq where it is the product of two large primes of the same size (n/2 bits). The size for N is n=1024 bits. Let e and d be two integers satisfying ed=1 mod (N) in this case mod (N)=(p-1) (q-1).
We call N RSA modulus, e is known as encryption exponent, and d is decryption exponent. (N, e) is the public key. (N, d) the pair is known as the secret key, and only the receiver of an encrypted message knows it (Coppersmith, Franklin, Patarin, & Reiter, 1996).
M is encrypted by computing C=Med =M (mod N)
This is based on Euler’s theorem.
Factoring large integers
Factoring large integers is known as the first attack on RSA public key (N,e). Once an attacker gets the factorization of N, he can easily construct φ(N)in which the decryption exponent d=e-1 mod φ(N) is calculated. This factoring of the modulus is called brute-force attack. Even though the factoring of modulus is improving, this attack is not risky to the security of RSA system if RSA is used properly. Currently, the fastest factoring algorithm is the General Number Field Sieve with executing time of ((c+o (1)) n1/3log 2/3n)
a) Elementary attacks
Elementary attacks involve misuse of RSA. For instance, choosing a common modulus N to serve many users. For our example, let’s assume N is used by many users, and Jane sends a Message M to John, Which is encrypted by the RSA function, C=M (eb) mod N. It emerges like Marvin cannot decrypt C because he does not know db. However, Marvin can use his own keys, dm and em, to factor N, and as a result recover John’s private key, db. So the resulting is compromised.
b) Small Private Key attacks
In our lab study we decide to improve the RSA performance in the matter of running time, Jane uses a small value of da, as compared to a large random number. This small private key dramatically improves performance; however, an attack posed by M. Wiener shows that a small d cause a total collapse of RSA cryptosystem (HASTAD, 1988). This break of RSA is based on Wiener’s Theorem, which provides lower constraints for d. The theory proves that Marvin may find d when d<1/3*N(1/4).
More to his success in RSA attack, Wiener discovered more techniques that allow fast decryption and not susceptible to his attack.
Illustrated below is two sample techniques.
Use of Chinese Remainder Theorem: If one chooses d such that both dp=d mod (p-1) & dp=d mod (q-1) are small, therefore a fast decryption of C can be done as follows: Compute first, Mp=Cdp mod p & Mq=Cdq mod q. We can then use the CRT to calculate the unique value M ∈ZN hence, M=Mp mod p and M=Mq mod q. The M satisfies M=Cd mod N as needed (Wiener, 1990). The theorem by Wieners does not apply due to to the value of d mod φ(N) being large.
Choosing large public key:
Here we replace e by e’, where e’=e+t* φ(N) for large t. If e’ is large enough, for instance, e’>N0.5, Weiner’s attack cannot happen regardless of how small d is.
c) Small Public Key attacks
Like the private key preferences, to minimize encryption time, it is common to use a small public key (e), but attacks on small e turn out to be less effective. Coppersmith’s theorem is the most powerful attacks on small e. The theorem gives an algorithm for finding all roots of N.Thes roots are less than x=N(1/d).
Implementation Attacks on RSA
RSA security implementation is not an ordinary task. Attacks on this category happen due to implementation pitfalls of RSA cryptosystems. An attack posed by Kocher, called “Timing Attacks” (KOCHER, 1996), and is an example of attacks on the RSA implementation.
What if a smartcard that has storage of a private RSA key is used, and Marvin cannot examine its contents and expose the key. But, by accurately measuring the time it takes the smartcard to execute an RSA decryption, Marvin can quickly find the private decryption exponent d. This is known as “Timing attacks”. The attack can be done by simple implementation of RSA by use of repeated squaring algorithm.
Recommendations to prevent attacks
The following are the recommendations we made to prevent RSA attacks
• We should not use RSA modulus N with multiple users
• We can improve decryption execution by usage of large e, or even using CRT to decrypt C, both of these may work against Weiner’s attack.
• We need to add appropriate time-delay during signatures generation so that modular exponentiation takes a fixed amount of time; this will prevent timing attack.
• Use of randomized pad to form a defense against Hastad’s broadcast attack
Conclusion
Since the discovery of RSA cryptosystem, there has been researching on breaking RSA system. Insightful attacks have been discovered, but no major devastating attacks have been confirmed by now. From the attacks we have discussed, it is good to learn how to avoid pitfall when implementing RSA system, and the same time derives methods to defend the system against the attack. There is an ongoing study that may bring new attack issues and challenges to RSA system, and this becomes our essential tool to enhance the security of RSA cryptosystem.
References
Coppersmith D., Franklin M., Patarin J. & Reiter M. (1996). Low-exponent RSA with related messages.
Dan B. (1999). Twenty Years of Attacks on the RSA Cryptosystem
HASTAD J. (1988). Solving simultaneous modular equations of low degree, SIAM J. Comput.
KOCHER, P. (1996) .Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems.
Wiener M. (1990). Cryptanalysis of short RSA secret exponents, IEEE Transactions on Information Theory.
1
eebazoush
redo.docx
0
