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?
4096 RSA key in the strongset factored?
11–20 of 114 posts
Re: 4096 RSA key in the strongset factored?
#12Can anyone confirm this is true?
You can confirm this independently with the key itself and the published prime.
Re: 4096 RSA key in the strongset factored?
#13Re: 4096 RSA key in the strongset factored?
#14I 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?
Nah, it just found a weak key bug. A very embarrassing weak key bug, but not one that breaks RSA.
Disclaimer: I'm not a cryptographer, I have very possibly misread the article. Corrections welcome.
Re: 4096 RSA key in the strongset factored?
#15I 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?
No, it seems to suggest that some version of the GPG software, under some conditions, erroneously generated a terribly weak key. It's a software (or even malware) issue rather than a mathematical issue.
Re: 4096 RSA key in the strongset factored?
#16For people who don't know hpa, the owner of the factored key: he's a core Linux kernel maintainer and has been the kernel.org sysadmin in the past: http://en.wikipedia.org/wiki/Hans_Peter_Anvin
If it's true that the normal key generation process would reject creating a key with factors this small, this is especially concerning.
Edit: Fortunately it looks like this is garbage on the keyservers, rather than a real problem with hpa's key.
Re: 4096 RSA key in the strongset factored?
#17The Phuctor operates by taking the greatest common divisor of the RSA modulus of a new PGP key with the product of other keys in its set. The factor that was found was 231. This is a result of bad prime generation, or a bad random number generator, not a advance in factoring technology.
Re: 4096 RSA key in the strongset factored?
#18From 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.
Re: 4096 RSA key in the strongset factored?
#19Earlier quoted context omitted.
You can confirm this independently with the key itself and the published prime.
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.