Is there any way to get GPG to print out the two factors when the key is generated? 231 is absurd.
4096 RSA key in the strongset factored?
21–30 of 114 posts
Re: 4096 RSA key in the strongset factored?
#22This is not the first time low quality keys have been produced. I'm thinking of https://www.debian.org/security/2008/dsa-1571. Seems like quality control is a bigger problem than we would like to admit.
Re: 4096 RSA key in the strongset factored?
#23In the army battle field tactical communication are handle by streaming ciphers on the radio. The idea is not to be impossible to breach. But strong enough that time is on your side, so that you can say "move those tanks over to feature 229", and that will be tactically perishable information.
on the internet, i would treat all information the same. if they can't break it today, they will wait until they have the math or the raw power to break what you have encrypted. so only talk about what doesn't matter if someone finds out about it.
like, hey lets meet up here at time x. in two days that means nothing significant.
but anyway, first step is getting an old mobile without data.
Re: 4096 RSA key in the strongset factored?
#24I 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.
From http://nosuchlabs.com/theory
An RSA public key consists of a modulus n and an exponent e. Modulus n is a product of two large primes, p and q. If one knows p or q, one can derive the private key corresponding to the given public key.
A typical GPG public key contains one or more RSA moduli, depending on the number of sub-keys.
Under certain conditions, a public key modulus will share a common factor with an existing modulus belonging to someone else. This may happen if both keys were generated on a system with a thoroughly-broken entropy source, or if a particular GPG implementation has been back-doored.
Re: 4096 RSA key in the strongset factored?
#25This 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.
You know that in RSA the modulus n is effectively your public key, right? And that n = p * q, where p and q are essential parts of your private key?
So if you can factor n into the corresponding primes, you have just cracked the person's private key.
Implications? You can decrypt all RSA encrypted messages for that private key. You can IMPERSONATE the person whose private key you have cracked. (Signature = data encrypted with private key that can be verified with the public key.)
All encrypted messages sent to the compromised keys must be treated as leaked. All signatures made by the compromised keys are suspect.
It's as bad as it gets for the individuals in question.
Re: 4096 RSA key in the strongset factored?
#26> 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?
Re: 4096 RSA key in the strongset factored?
#27Author 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.
Re: 4096 RSA key in the strongset factored?
#28Can anyone confirm this is true?
Yes:
817023023960376946633975507110154649249407598806798730414849884461776172171921668594148071323527016137506405823108520062504849249423700259406905313281403901410082762097159560221463048924336192384026777502177262731045200322200149773127502888545234973139480887644585192600631058962876114156934248895171959246969597637127280010272143593885240940877456234662196130491400738438731832514335353824697930453078426722191105157568392826870043655708008545411143367763836566011740499383456592129662585004880376777597714978023542434421914201119537685489173509942329090631662014650033142642110914360849421856179611226450806562235534802516081595259914768497444702718749402330070488028751073730349460752771915484847399385631524708487646079936572410398967582895983187640798072309362094727654167628620105981459021548290415800096769214437425690934372015628796027498219902441288189398386359846661623243493534897411417685435424010451956954083531228374002591372549525280610594684910812811287436481207089763125424247793044043309737269468709710679872269272855389945385386467765509880648929743498214329578288874987193768439353382305260108425688024147656806932474058888992099083804597481699305852902662863062054067183925164590726103552998367994727700722491707 `mod` 231
0Re: 4096 RSA key in the strongset factored?
#29This isnot really new work, see eg https://eprint.iacr.org/2012/064.pdf (and http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf if you're interested in other RSA weaknesses)
Re: 4096 RSA key in the strongset factored?
#30In the army battle field tactical communication are handle by streaming ciphers on the radio. The idea is not to be impossible to breach. But strong enough that time is on your side, so that you can say "move those tanks over to feature 229", and that will be tactically perishable information. on the internet, i would treat all information the same. if they can't break it today, they will wait until they have the mat…
> like, hey lets meet up here at time x. in two days
> that means nothing significant.