Crypto boffin: writing is on the wall for 1024-bit RSA

If the govn'mt lets us...

The presupposes that governments will let commercial encryption use stronger keys when 1024 bit RSA becomes insecure. Remember, the US (among others) fought anything stronger than a 48-bit key for a time - until the procurement cycle allowed them to buy hardware to break the (then) strong 128 bit keys.

However, given that anyone can use open-source software to provide arbitrary levels of encryption for private messaging, I suppose that allowing 2048 or larger keys will be allowed. With escrow, of course...

RSA is already dead

Adi Shamir's TWINKLE device in was already killing 512-bit RSA in 1999. Shamir promised a 1024-bit version of the technology, before it just disappeared from the academic radar. You can bet that the Lenstra technique, like TWINKLE or any other big threat to PKI, will be rapidly annexed by the intelligence services if it's for real.

web security

Aren't our browsers still doing 128bit RSA? Obviously web hosts won't want to switch to anything deeper because of the electrical costs, but if it's getting to be that easy to factor larger keys... when will e-commerce catch up?

Re: web security

128-bit RSA? Harris, you better brush up on your crypto.

Huh?

Article: "The largest proper RSA number yet broken was a 200-digit "non-special" number whose two prime factors were identified in 2005 after 18 months of calculations that used over a half century of computer time. The 1024-bit numbers used in RSA encryption are around 100 orders of magnitude bigger than this."

Huh??

Comment: "Aren't our browsers still doing 128bit RSA?"

Um, no. Browsers have never used 128 bit RSA, and no, you can't compare RSA key sizes to non-RSA key sizes. It's apples and oranges.

Well, the browsers

In browsers you'll find

TLS v1.0 128 bit ARC4 (1024 bit RSA/MD5)

TLS v1.0 256 bit AES (1024 bit RSA/SHA)

etc

As I understand this article talks abouth the key length shown in the brackets.

Orders of Magnitude

John Stag: An order of magnitude is generally defined as a power of 10 (although technically you can use any scale as long as you're consistent and your audience understands which scale your using.) The largest proper RSA-style number factored was 200 decimal digits, and 1024-bit numbers are 308-309 decimal digits (i.e, 2^1024 ~= 10^308). Since each digit equates to another power of ten, or another order of magnitude, the numbers in use today are 108-109 orders of magnitude larger.

Since we're talking computer stuff, we could (should?) use binary orders of magnitude. A 200-digit decimal number takes 664-668 binary digits, so from that reckoning we oculd say that the RSA numbers used today are (1024-668) = 356 orders of magnitude larger.

Symmetric v. Asymmetric

The asymmetric encryption (RSA) which is used to eventually encrypt a secret key that will be used with much more efficient symmetric algorithms (eg AES) to encrypt communications is whats being talked about here.

Because asymmetric encryption can be broken without the original keys - by the computer-assisted mathematical wizardry described in the article, basically - it requires the much greater bit strength to keep cracking computationally infeasible.

Even with the symmetric encryption it is all just a game of brinkmanship - crypto vs moores law

Apologies for any mistakes - I am not a crypto person (hate the math) or if I am preaching to the choir..

Re Orders of Magnitude

Steven Knox ..... huh? speak english boy ... you lost me right after John Stag ....

to be honest I won't be happy until RSA is running in the Gbits :P

distributed grid key attacks

I'm sure I read of a scheme (the original article was in German I recall) on the darker side of the Playstation3 where a team was assembling a voluntary distributed grid project to primarily crack all PS3 game codes, then to secondarily use the assembled horde of Cell power to go after assorted general crypto keys. A sort of closed user special interest group version of SETI or Folding.

What about when the kilocore (=1000 8 bits CPU's on a chip) class of supercomputer chips start getting built up into widespread devices - then it'll be up to quantum entaglement to keep data (temporarily) 'secret'. Moores Law is perceived as still valid for the next 25 years or so, so in the end I don't know how secret data will eventually be kept secret!

to 'worry' the Info Assurance experts further, do we know how many coherent qubits the D-Wave has achieved yet?

Quantum computers

An interesting RSA attack approach involves running Shor's algrorithm on a quantum computer (QC) to factorise the product of 2 primes. All they need is a QC with a similar number of qubits as the size of the RSA key in bits which isn't drowned in its own noise. They have used this technique to factorise 15 so far, so I guess it works in principle, but that was on a QC with about a quarter the qubits of the largest QC currently demonstrated. Wikipedia has useful articles explaining this technology and related concepts if you are interested.

Cracking RSA

Ow ... most sites use 1024bit. And the stoopid US export restrictions mean we're getting 128-symmetric, 1024-asymmetric for some time. (I'm in Mexico City).

To the dude about 128-bit RSA ... it isn't RSA that's 128. That's the symmetric cipher (usually AES, I think).

As for myself, anything really really sensitive is encrypted with my 4096bit RSA, and with 256-Blowfish for symmetric.