The saying "A chain is no stronger than its weakest link" is a very suitable for describing attacks on cryptosystems. The attackers' instinct is to go for the weakest point of defense, and to exploit it. Sometimes the weakness may have appeared insignificant to the designer of the system, or maybe the cryptanalyst will discover something that was not seen by anyone before. The important thing to remember (and this has been proven time and time again in the history of cryptography) is that no matter how secure you think your system is, there may be something you have not considered.
At the moment RSA seems to be extremely secure. It has survived over 20 years of scrutiny and is in widespread use throughout the world. The attack that is most often considered for RSA is the factoring of the public key. If this can be achieved, all messages written with the public key can be decrypted. The point is that with very large numbers, factoring takes an unreasonable amount of time (see the factorization section for more details of the difficulty). It has not been proven that breaking the RSA algorithm is equivalent to factoring large numbers (there may be another, easier method), but neither has it been proven that factoring is not equivalent.
I mentioned before that a chain is only as strong as its weakest link. In cryptlogy terms, the links in the chain include key generation, key management, the cryptographic algorithm and the cryptographic protocol. If there is a weakness in any one of these areas, it undermines the entire system. Imagine an eavesdropper was able to generate session keys in the same order that an e-commerce site web server used to get credit card details securely from customers over the Internet; this would allow the eavesdropper to read all the transactions. The section on random number generators discusses this topic.
It's now time to get into the details of attacks on RSA.
One of the seeming weaknesses of public key cryptography is that one has to give away to everybody the algorithm that encrypts the data. If the message space is small, then one could simply try to encrypt every possible message block, until a match is found with one of the ciphertext blocks. In practice this would be an insurmountable task because the block sizes are quite large.
Another possible attack is a known ciphertext attack. This time the attacker knows both the plaintext and ciphertext (they simply has to encrypt something). They then try to crack the key to discover the private exponent, d. This might involve trying every possible key in the system on the ciphertext until it returns to the original plaintext. Once d has been discovered it is easy to find the factors of n (for example use the algorithm in chapter 8 of The Handbook of Applied Cryptography). Then the system has been broken completely and all further ciphertexts can be decrypted.
The problem with this attack is that it is slow. There are an enormous number of possible ds to try. This method is a factorizing algorithm as it allows us to factor n. Since factorizing is an intractable problem we know this is very difficult. This method is not the fastest way to factorize n. Therefore one is suggested to focus effort into using a more efficient algorithm specifically designed to factor n. This advice was given in the original paper.
This attack is very similar to the last. The idea is that we encrypt the ciphertext repeatedly, counting the iterations, until the original text appears. This number of re-cycles will decrypt any ciphertext. Again this method is very slow and for a large key it is not a practical attack. A generalisation of the attack allows the modulus to be factored and it works faster the majority of the time. But even this will still have difficulty when a large key is used. Also the use of p-- strong primes aids the security.
The bottom line is that the generalized form of the cipher attack is another factoring algorithm. It is not efficient, and therefore the attack is not good enough compared with modern factoring algorithms (e.g. Number Field Sieve).
I noticed an improvement on this algorithm. The suggested way is to use the public exponent of the public key to re-encrypt the text. However any exponent should work so long as it is coprime to (p-1).(q-1) (where p, q are factors of the modulus). So I suggest using an exponent such as 216 + 1. This number has only two 1s in its binary representation. Using binary fast exponentiation, we use only 16 modular squarings and 1 modular multiplication. This is likely to be faster than the actual public exponent. The trouble is that we cannot be sure that it is coprime to (p-1).(q-1). In practice, many RSA systems use 216 + 1 as the encrypting exponent for its speed.
One of the early weaknesses found was in a system of RSA where the users within an organization would share the public modulus. That is to say, the administration would choose the public modulus securely and generate pairs of encryption and decryption exponents (public and private keys) and distribute them all the employees/users. The reason for doing this is to make it convenient to manage and to write software for.
However, Simmons shows how this would allow any eavesdropper to view any messages encrypted with two keys; for example when a memo is sent to several employees. DeLaurentis went further to demonstrate how the system was at even more risk from insiders, who could break the system completely, allowing them to view all messages and sign with anybody's key.
Joye and Quisquater showed how to capitalise on the common modulus weakness due to a transient error when transmitting the public key. Consider the situation where an attacker, Malory, has access to the communication channel used by Alice and Bob. In other words, Malory can listen to anything that is transmitted, and can also change what is transmitted. Alice wishes to talk privately to Bob, but does not know his public key. She requests by sending an email, to which Bob replies. But during transmission, Malory is able to see the public key and decides to flip a single bit in the public exponent of Bob, changing (e,n) to (e',n).
When Alice receives the faulty key, she encrypts the prepared message and sends it to Bob (Malory also gets it). But of course, Bob cannot decrypt it because the wrong key was used. So he lets Alice know and they agree to try again, starting with Bob re-sending his public key. This time Malory does not interfere. Alice sends the message again, this time encrypted with the correct public key.
Malory now has two ciphertexts, one encrypted with the faulty exponent and one with the correct one. She also knows both these exponents and the public modulus. Therefore she can now apply the common modulus attack to retrieve Alice's message, assuming that Alice was foolish enough to encrypt exactly the same message the second time.
A demonstation of the Common Modulus attack and the Faulty Encryption attack can be found in this Mathematica notebook.
In the cycle attack section above, I suggested that the encrypting exponent could be chosen to make the system more efficient. Many RSA systems use e=3 to make encrypting faster. However, there is a vulnerabilty with this attack. If the same message is encrypted 3 times with different keys (that is same exponent, different moduli) then we can retrieve the message. The attack is based on the Chinese Remainder Theorem. See The Handbook of Applied Cryptography for an explanation and algorithm.
Factoring the public key is seen as the best way to go about cracking RSA.
Ronan Killeen
Back to home.