4096 RSA key in the strongset factored?

#1

Post by davout » Sun, May 17, 2015, 5:19 PM UTC

4096 RSA key in the strongset factored?
trilema.com

Re: 4096 RSA key in the strongset factored?

#2

Post by dragontamer » Sun, May 17, 2015, 5:46 PM UTC

This is kind of hilarious.

I think the article might be a bit dense for those who aren't aware of RSA's algorithm though.

Re: 4096 RSA key in the strongset factored?

#3

Post by davout » Sun, May 17, 2015, 5:48 PM UTC

oh, wait a second, it just factored a second one... (and no, it's not the one sharing a prime with the first factored one).

So summed up: 2 known keys factored so far, 2 more waiting to be identified among the running product (should apparently take a week to identify).

Re: 4096 RSA key in the strongset factored?

#4

Post by hurin » Sun, May 17, 2015, 5:50 PM UTC

Can anyone confirm this is true?

Re: 4096 RSA key in the strongset factored?

#5

Post by arenaninja » Sun, May 17, 2015, 5:51 PM UTC

dragontamer wrote: post #2

This is kind of hilarious. I think the article might be a bit dense for those who aren't aware of RSA's algorithm though.

I agree. I've rolled OpenSSL certs for servers, but crypto isn't really a forte of mine. A generic rundown of implications would be nice.

Re: 4096 RSA key in the strongset factored?

#6

Post by jjoonathan » Sun, May 17, 2015, 5:52 PM UTC

> And the first factor - get a load of this - is 231. Which... yes, 231 = 3 * 77.

The best part.

Re: 4096 RSA key in the strongset factored?

#7

Post by belovedeagle » Sun, May 17, 2015, 5:52 PM UTC

davout wrote: post #3

oh, wait a second, it just factored a second one... (and no, it's not the one sharing a prime with the first factored one). So summed up: 2 known keys factored so far, 2 more waiting to be identified among the running product (should apparently take a week to identify).

> 2 more waiting to be identified among the running product

I don't know anything about this factoring project; does this mean that keys are somehow "tested" in batches, and if the batch comes out "dirty" then you know you can easily factor something in that batch (for some value of "easy")?

EDIT: Ah, nevermind, just figured it out. For those coming after, there's a running product of all public moduli in the tested set; you can test one key against all of them simultaneously. When you find a GCD /= 1, you've found a factor, and you know the key you just tested has it, but there's an older key which has that factor too, and you don't know which one. Presumably you either go and test them one by one or store "snapshots" of the running product to test.

Re: 4096 RSA key in the strongset factored?

#8

Post by lotsofmangos » Sun, May 17, 2015, 5:53 PM UTC

dragontamer wrote: post #2

This is kind of hilarious. I think the article might be a bit dense for those who aren't aware of RSA's algorithm though.

The ongoing conversation is pretty fun too - http://log.bitcoin-assets.com/?date=17-05-2015#1134741

Re: 4096 RSA key in the strongset factored?

#9

Post by revelation » Sun, May 17, 2015, 5:53 PM UTC

hurin wrote: post #4

Can anyone confirm this is true?

Well, it lists the key and says the first factor is 231. If you have a big enough calculator, this is trivial to verify.

Re: 4096 RSA key in the strongset factored?

#10

Post by green7ea » Sun, May 17, 2015, 5:53 PM UTC

From my understanding, this doesn't show that he can break RSA but rather that the key generator that generated the keys in the GPG strong suite were completely broken. The factors were 7 and 77 which is completly ridiculous, they should be in the range of 2^2048. This does mean further scrutiny on key generators is a must.