# Is 512-bit RSA still safe for signature generation?

The standard CSP on Windows XP only supports RSA up to 512-bit, which means that it's the maximum key size I can use for authenticity verification of updates. The public key is embedded in the updater, and the update files are signed with the private key, using SHA256.

I know that RSA-768 was factored back in 2010, which is what makes me wonder if RSA-512 is still acceptable for signing purposes. How much effort is it for an attacker to break a 512-bit RSA key?

• I seriously doubt that WinXP cannot go beyond 512 bits, especially since I have done a lot of RSA-1024 with the CSP which come with a stock Windows 2000. The "base CSP" was limited to 512 bits because of the export regulations of that time, but they were lifted near the end of the Clinton presidency. Oct 2, 2012 at 22:13
• @ThomasPornin Interesting. I read on MSDN that the base CSP was 512-bits and shipped with the OS, and it implied (or, rather, I inferred) that you have to manually download the expanded CSP. Am I wrong in this assumption? Oct 3, 2012 at 7:48
• All Windows 2000, XP and more that I have come across always had several CSP installed, including the "strong" ones. Remember that IE uses them for SSL; if a basic Windows could not do more than 512-bit RSA, IE would not be able to handle common HTTPS sites. Oct 3, 2012 at 10:18
• Breaking 512 bit RSA seems to cost around 100$ATM. Nov 9, 2012 at 21:37 • Nov 22, 2015 at 9:14 ## 4 Answers No. The challenge for RSA-155 (which is 512 bits) was broken in 1999. This took 6 months on pretty advanced hardware to break at the time, which works out to 8000 MIPS years. It should be much less today. FYI, RSA 768 took just under 3 years. • Is there a decent projection of the time it'd take to break a 512-bit key today? Oct 2, 2012 at 11:35 • @Polynomial Assuming the same number of computers, but with current clock speeds and extra cores (sieving can be parallelized), and adjusting for parallel scaling, it would come out as about 11 days. Throw a few GPU's in the mix and a week could be realistic. Oct 2, 2012 at 12:05 • @Thomas Yikes. I'll see if I can find a pure-managed implementation of RSA then, so I can use 2048-bit keys. Oct 2, 2012 at 12:11 • @Polynomial: a team of enthusiast nowadays breaks a 512-bit key within days, using public domain tools. Also see this answer, especially the references to the TI-83 Plus OS Signing Key broken in 2009. – fgrieu Oct 2, 2012 at 14:53 I don't have any experience with this myself, but Tom Ritter talked about this on twitter: Matthew Green: Out of curiosity: do you happen to know offhand how much it costs to factor a 512-bit RSA key on EC2? Tom Ritter: My personal costs are \$120-\$150 with my setup. You can probably do it cheaper, heard reports of \$75.

He also published a description of how to factor RSA moduli.

Another project in a similar vein: Factoring as a Service:

The Factoring as a Service project is designed to allow anyone to factor 512-bit integers in as little as four hours using the Amazon EC2 platform for less than $100, with minimal setup. You should be able to just run the scripts from their github. It is not safe at all since Factoring as a service project (https://github.com/eniac/faas) together with Amazon EC2 allows the factorization of a 512-bit key for less than$100 in only a few hours.

Considering special purpose hardware, according to [40] sieving for a 1024-bit RSA modulus can be done in a year for about US \$10,000,000, plus a one-time development cost of about US \$20,000,000, and with a comparable time and cost for the matrix.

-- Bos et al.

RSA.816 offers very short-term protection against small organizations Should not be used for confidentiality in new systems.

http://www.keylength.com/en/3/

• Two key words in the citation are sieving and development: there is much more to factorization of a 1024-bit RSA modulus than the sieving step; and the technology for that fast sieving is not developed, at least publicly. And comparable includes "n times more costly" for arbitrarily large n.
– fgrieu
Oct 3, 2012 at 7:06