4 ms·

Let me try to explain that. You start with a random 2048-bit integer. You then change the lower bytes to make it divisible by 3. This is easy because you're onl

Let me try to explain that. You start with a random 2048-bit integer. You then change the lower bytes to make it divisible by 3. This is easy because you're only working on the public key. Now that the public key is divisible by 3, you use Fermat's little theorem which tells you that the private key must be divisible by 3 and have a sum of digits that is divisible by 3. This lets you skip most possible private keys, thereby reducing the compute needed to factorize it by a few orders of magnitude. And maybe you get lucky and they use that RSA implementation which uses exactly 2 prime factors, because then you already know that one of them is 3 and you just divide the public key by 3 to get the other prime factor. EDIT: Wikipedia says "The structure of the RSA public key requires that N be a large semiprime (i.e., a product of two large prime numbers), that 2 < e < N, that e be coprime to φ(N), and that 0 ≤ C < N." and later "the same algorithm allows anyone who factors N to obtain the private key." which in the contest of the Xbox hack means that if you force N to be divisible by the prime 3, then the other prime which is used for generating the private key has to be N/3 => You have successfully factored it. EDIT2: Here's code for signing with the Habibi key: https://github.com/XboxDev/xbedump/blob/b8cd5cd0f8b1cbc4e64f41daf925a873d34dacf1/xboxlib.c#L408 https://github.com/XboxDev/xbedump/blob/b8cd5cd0f8b1cbc4e64f... As you can see, it'll replace the last 4 bytes with 0x89, 0x9c, 0x90, 0x6b and then start by dividing it by 3 and using that to generate a suitable private key.

Retr0id 2y ago
Ah, thanks for finding that code. Here's the original public modulus as an integer: http://factordb.com/index.php?query=20740119327258723760276023509063017138455993606274883526731955113241109007354362374128996096291046353572306742110305456946824862203867115042369878729703475765112280167498189046437794602966168812419423365196979669431929588951126804648743029387833666031765734337165949634731375592471670294246180877815104812674626967450097045005117546657068700545263064105024888769118032059917845867653040419404003684559882509195398630922824050405379620513589699993980205694266973236095772153476388267418476533663512746243310317853861946430053072890502949319703765023792161144942611323629444409600173894963797156859916567288947565058003 http://factordb.com/index.php?query=207401193272587237602760... (which can't be factored, at least not any time soon) And here's the patched version: http://factordb.com/index.php?query=17371852435364932234198289696093135719112415166564334627199356168762835335592424536862497360014159738630046885057635916854759097620974245668452590354310167264683476531173163058898476418183674505913561130980902214026382023954011273122886903301549955103489770026619711887767398427379601400787983076212603189569524432427260515921063513404354797519457735139609222411461524050349340285765258649294004182458325847322598311747736621083339542109085138257913063024645042563940841231676725819951388256701826786497550629695215511595269950707608531548300114399973695889243598772097105699530419181744793002739781116244276221499347 http://factordb.com/index.php?query=173718524353649322341982... And exactly as you say, it's divisible by 3, leaving behind a single large prime (so I was wrong about there being more factors)

Retr0id 2y ago

Ah, thanks for finding that code. Here's the original public modulus as an integer: http://factordb.com/index.php?query=20740119327258723760276023509063017138455993606274883526731955113241109007354362374128996096291046353572306742110305456946824862203867115042369878729703475765112280167498189046437794602966168812419423365196979669431929588951126804648743029387833666031765734337165949634731375592471670294246180877815104812674626967450097045005117546657068700545263064105024888769118032059917845867653040419404003684559882509195398630922824050405379620513589699993980205694266973236095772153476388267418476533663512746243310317853861946430053072890502949319703765023792161144942611323629444409600173894963797156859916567288947565058003 http://factordb.com/index.php?query=207401193272587237602760... (which can't be factored, at least not any time soon) And here's the patched version: http://factordb.com/index.php?query=17371852435364932234198289696093135719112415166564334627199356168762835335592424536862497360014159738630046885057635916854759097620974245668452590354310167264683476531173163058898476418183674505913561130980902214026382023954011273122886903301549955103489770026619711887767398427379601400787983076212603189569524432427260515921063513404354797519457735139609222411461524050349340285765258649294004182458325847322598311747736621083339542109085138257913063024645042563940841231676725819951388256701826786497550629695215511595269950707608531548300114399973695889243598772097105699530419181744793002739781116244276221499347 http://factordb.com/index.php?query=173718524353649322341982... And exactly as you say, it's divisible by 3, leaving behind a single large prime (so I was wrong about there being more factors)