You shouldn't be surprised to see blatant lies from Mircea Popescu, who also claims that he's a billionare, that English literature literally does not exist, that bitcoin literally makes states and laws obsolete, and that nuclear weapons are ineffective.
4096 RSA key in the strongset factored?
41–50 of 114 posts
Re: 4096 RSA key in the strongset factored?
#42Ahem. For the first key they mention, there are more factors there!
The key is probably corrupted or generated improperly.
In[2]:= k =
81702302396037694663397550711015464924940759880679873041484988446177\
6172171921668594148071323527016137506405823108520062504849249423700259\
4069053132814039014100827620971595602214630489243361923840267775021772\
6273104520032220014977312750288854523497313948088764458519260063105896\
2876114156934248895171959246969597637127280010272143593885240940877456\
2346621961304914007384387318325143353538246979304530784267221911051575\
6839282687004365570800854541114336776383656601174049938345659212966258\
5004880376777597714978023542434421914201119537685489173509942329090631\
6620146500331426421109143608494218561796112264508065622355348025160815\
9525991476849744470271874940233007048802875107373034946075277191548484\
7399385631524708487646079936572410398967582895983187640798072309362094\
7276541676286201059814590215482904158000967692144374256909343720156287\
9602749821990244128818939838635984666162324349353489741141768543542401\
0451956954083531228374002591372549525280610594684910812811287436481207\
0897631254242477930440433097372694687097106798722692728553899453853864\
6776550988064892974349821432957828887498719376843935338230526010842568\
8024147656806932474058888992099083804597481699305852902662863062054067\
183925164590726103552998367994727700722491707;
In[3]:= Mod[k, 231]
Out[3]= 0
In[4]:= PrimeQ[k/231]
Out[4]= False
In[5]:= k/231
Out[5]= 35368962076206794226579026281824876590883445835792152831811683\
3100336005269230159564566264642219487505414028494852173187231536471611\
9914542887035988231185720389968667087270823469537008330459707290159209\
9661353364980311702259746743425433025478148700135908263534397627385308\
7038512067581886118722465442406600419739236851636368083179044971965775\
2716260756113403162300436097137367240321798068505185846117222626502991\
7972189107914583118772974372664303512699903196388139036385254695090568\
3836616885229600336622387436373827893689140346804994669042932255386289\
6496240961102381095855593553741821858969074370611369916911524829154989\
2471064729866440194694575875270536897405648832413466395253223409210905\
4322444761638801525847830149818154360350822063888699559821489522975025\
6978765054779946444242883036619140901690111688730602659902275718330614\
7862718442748840688417371783090839236356998338668549503675212615484217\
9837233961886127308887977651083372888549578043554369993467884333890665\
1433796925381495343064039151702639555279085323422856589910272101255174\
8285128474697397430689599285636983964428089826285444521184129104123814\
2175622521276041907762975783068827748521127531377359006862728425481845\
0450507289719327232580534861464796513972730400397Re: 4096 RSA key in the strongset factored?
#43Earlier quoted context omitted.
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.
https://eprint.iacr.org/2012/064.pdf https://factorable.net/weakkeys12.extended.pdf
Thanks.
The first paper mentions some 157 PGP keys and some "probably copy-paste errors." Maybe somebody can tell more about it, I wasn't able to evaluate the effects.
The second didn't analyze PGP keys, but otherwise was certainly impressive.
Re: 4096 RSA key in the strongset factored?
#44Earlier quoted context omitted.
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.
The key as seen by Phuctor had three sub-keys, one of which was an RSA key which turned out to be factorable.
Sorry, I was looking at the other one. But something is still very, very odd. (1) Two of the subkeys agree with one another for hundreds of digits and then disagree. (2) I did gpg --recv-key 51221121 and I got a key back from the keyserver with fingerprint 7EAA C969 3E7D 2205 46BE 576C BDA0 6085 493B ACE4 (only, no other keys) -- which doesn't match the key ID that it should, and is seemingly missing the vulnerable subkey entirely.
Re: 4096 RSA key in the strongset factored?
#45Earlier 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.
$ gpg --export -a $$KEYID$$ >keyfile.asc
$ gpg --list-packets --debug=0x02 keyfile.asc
Re: 4096 RSA key in the strongset factored?
#46> 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?
Also, shouldn't it only have 2 prime factors?
Re: 4096 RSA key in the strongset factored?
#47Earlier quoted context omitted.
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.
The key as seen by Phuctor had three sub-keys, one of which was an RSA key which turned out to be factorable.
Can you post the ASCII-armored key that you have? I am getting a radically different key from the keyservers, and I wonder if there could be some kind of keyserver attack or misbehavior involved here too.
Re: 4096 RSA key in the strongset factored?
#48Is there any way to get GPG to print out the two factors when the key is generated? 231 is absurd.
It might not be a good idea for other reasons to have them on your screen, where other locally-installed software could view them, they would be (more strongly) broadcast in the RF spectrum, someone might see them over your shoulder, etc.
Re: 4096 RSA key in the strongset factored?
#49Ahem. For the first key they mention, there are more factors there! The key is probably corrupted or generated improperly. In[2]:= k = 81702302396037694663397550711015464924940759880679873041484988446177\ 6172171921668594148071323527016137506405823108520062504849249423700259\ 4069053132814039014100827620971595602214630489243361923840267775021772\ 6273104520032220014977312750288854523497313948088764458519260063105896\…
Update: some more factors for the key.
In[8]:= primes = Table[Prime[i], {i, 1, 10000000}];
In[9]:= r = k/231;
Select[primes, Mod[r, #] == 0 &]
Out[10]= {19, 7704959}
In[11]:= PrimeQ[k/231/19/7704959]
Out[11]= False
In[13]:= r/19/7704959
Out[13]= 2416008079731972085604323566968184938863361678449872200338542\
2782524728573078725530058065928860640441907473143687288939310762579324\
2201448845923773741805403670269789344162077509161854710812642480618084\
6418886532753250669796572553463393409872248215326471682480854051430439\
2318772751800215263874553179418646615820937142842296219000273581288825\
2789449984922109948745889094702540699357374091188011161049671668836093\
7278541145959209900694985382835863685677859045842263065588173367519102\
3000601703070615085046450531430050636608745665363730079826233868575064\
1515845148088351185382897973393486745557331417516226266671518736327371\
0952774886507742692568074519503781293211406810410464658659799378912020\
4022428232439503300191599103479511965185485160912786274522509295156878\
2006686251281732387799849219226976241206277650039929011945237627811183\
5293192238971567100891050322477609224503267676028587870533168970890197\
7752061262164585534348926085756033558766611288812716862195529175560192\
7171277951291635708971328803457524430235472568512308733137100548610807\
1730859408357205400252076841587686986935644804331821576562378722868016\
3691408455343059061584335066277570324891522017892861973483415607333423\
704276600438478560110515119729110048093857Re: 4096 RSA key in the strongset factored?
#50From 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.
A look at the PGP ecosystem through the key
server data