31–40 of 114 posts
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.
I can only confirm that we have a key, downloaded from an SKS dump, said key purporting to belong to one Mr. Anvin, containing one sub-key being an RSA public key which turned out to be factorable with trivial effort.
Anything else is mere conjecture.
Earlier quoted context omitted.
I too can post a public key I have the private key for and a factor? Or intentionally create a weak key?
Yes you can, we just need to find hpa's n value and see whether it is divisible by 231. If it is, the claim is correct. I found the n value for my own PGP public key before and I can find hpa's too, I just have to remember the right arguments to gpg.
I know of RSA, but could someone break down this article a bit? Does this mean RSA is now broken and we must find a new algorithm?
However, using a bad random prime generator might lead to birthday attack when someone is using the same prime as you. Having two keys that share a prime, it is possible to factor both.
Also, one of the "primes" used is 231, which is extremely stupid, its factors 3711, so there are two keys that are using the same non-prime number as one of "prime" factors for the key. And one of its factors is motherfucking second prime.
I suspect it's a backdoor or a blatant error in RSA key generator or prime checker.
> And the first factor - get a load of this - is 231. Which... yes, 231 = 3 * 77. Why isn't the first factor just 3 then?
But any "primes" being used should have some serious factorisation algorithms run over them before being used, so this is really embarrassing.
EDIT
And to answer contravariant's question[0]:
Also, shouldn't it only
have 2 prime factors?
Author of 'phuctor' speaking. We did not break RSA! Please put that Luger down, unload it. You have things to live for! We only found (at the time of this writing) two sets of two poor buggers each who happened to have generated RSA keys having a common factor.
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.
Exactly. The GPG that generated that keypair was obviously not doing what it was supposed to do. It can be something on the level of the famous Debian patch fiasco. The worrying thing is that nobody until now published such findings. The second found p is 21(!?) Edit: see the new post from agwa, if all the keys with bad properties came the same way it's much less worrying.
Dumb-and-stupid trial division by the first 1000 or so primes wouldn't take much time and could've easily caught this. I see this as a nice precautionary tale that we may sometimes think too highly of sophisticated algorithms that we trust them blindly, and miss looking for the bloody obvious. It's like an "is it plugged in?" sort of thing.
If I deliberately generated a public key that was divisible by 3, I wonder how long it would take for someone to notice...
I also entertain the (admittedly very slim) possibility that he did this deliberately to see what would happen.
Author of 'phuctor' speaking. We did not break RSA! Please put that Luger down, unload it. You have things to live for! We only found (at the time of this writing) two sets of two poor buggers each who happened to have generated RSA keys having a common factor.
Is the origin of the keys and why they're broken in this way known? Perhaps they were generated on embedded devices and their demise could be traced back to an early boot time entropy problem.
Can anyone confirm this is true?
Yes: 8170230239603769466339755071101546492494075988067987304148498844617761721719216685941480713235270161375064058231085200625048492494237002594069053132814039014100827620971595602214630489243361923840267775021772627310452003222001497731275028885452349731394808876445851926006310589628761141569342488951719592469695976371272800102721435938852409408774562346621961304914007384387318325143353538246979304530784267221911051…
You have one ending in 131307671292149646652772992033083 and I have one ending in 726103552998367994727700722491707 that is not divisible by 231.
Earlier quoted context omitted.
Yes: 8170230239603769466339755071101546492494075988067987304148498844617761721719216685941480713235270161375064058231085200625048492494237002594069053132814039014100827620971595602214630489243361923840267775021772627310452003222001497731275028885452349731394808876445851926006310589628761141569342488951719592469695976371272800102721435938852409408774562346621961304914007384387318325143353538246979304530784267221911051…
Wait a minute, I get a different n value by downloading that key and running gpg --list-keys --with-key-data on it. You have one ending in 131307671292149646652772992033083 and I have one ending in 726103552998367994727700722491707 that is not divisible by 231.