Q: Does this factorization mean that RSA keys now can be more easily cracked?
No. While an impressive achievement, the factorization was based on existing factoring methods, and took roughly the amount of time that was expected. There was some fine-tuning compared to a previous factorization, but no fundamental advances.
Q: Web browsers today feature, at most, 128-bit security. Does this mean they are all vulnerable?
No, the "128-bit security" typically mentioned in connection with Web browsers has to do with the security of session encryption -- not the RSA algorithm. Session encryption is typically performed with a different algorithm, RC4, which has a different set of security levels than RSA. For instance, 40 bits is the typical level for exportable products based on RC4,whereas 512 bits is the typical level for RSA. RC4 and other session encryption algorithms are not affected by the recent factorization.
Q: What practical significance do the results of this factorization have?
The practical significance is a reminder of the importance of choosing sufficiently large key sizes. Just as the DES Challenges that RSA Laboratories sponsored in recent years have emphasized the potential risks of staying at the 56-bit level for session encryption, the RSA Factoring Challenges highlight the issues around staying at the 512-bit level for the RSA algorithm. Although these lower key sizes have been popular in products developed in the past, RSA Laboratories has been recommending larger key sizes in both cases for several years. Most new standards for cryptography specify higher key sizes, and the factorization result is an encouragement to follow those recommendations.
Q: Using the techniques presented here, how difficult would it be for someone who is well-financed (i.e. has lots of powerful computers and expertise) to actually crack an RSA key and decrypt an encoded message or impersonate another web site?
Someone who is well financed could potentially apply techniques like these to crack a "real" 512-bit RSA key and compromise the security of messages or web sites, but it would be expensive and would require significant expertise in computational number theory methods. The techniques would have to be repeated for *each* key -- several thousand computer-years each time. Moreover, the final step of factoring requires a supercomputer, a very expensive investment. Thus, it is not clear that the expected return would justify the required cost. Solving challenges for "fun" with "free" resources and time is one thing, making a business is something quite different. And systems with recommended key sizes, such as 768 or 1024 bits remain well out of reach.
Q: When do you think the next level in the RSA challenge will be factored?
The previous challenge, RSA-140, was factored earlier this year. RSA-155 was significant because it matched a common benchmark, 512 bits. RSA-150 hasn't been done yet, since RSA-155 was the more interesting milestone, even though RSA-150 would have been a little easier (since it's shorter than RSA-155). Perhaps we'll see RSA-160 next; it could take a few months with a much larger effort than for RSA-155, or could take a lot longer.
