c = 2911901299590689319468053634625275622654003904978205739380623481723661641396883678700531176998074009090944130064383792213854734101182591054606781359574544120823690362905523398270489939706547990345246231530733316646360394579721797156381054207414615333776383945252214100458075195770993971636731892198913293107313263096802400950280001995889600269261084002962194522369348371580184194201319826916320073496756736378234176527727677896098180012125139057850531341929674855173384488699967535868594673470466436155672157436157446615623094626238560694456848398206751930925254978950059694877328019092454478343535457958785859310484

n = 18462421850600696840560898417547472397015573128377235128769631165824737496243143255623011617642183164439083297122699666367402809023320590316626671507601587718197741629051551118897715752003980101236205623576264496389150018851480298917563748217989839440097537627133550430744085299790188310538773929752812477188498820917554309394801820203068308914778160483535285589443135601752476888259220136846332206525042550832122310211325683421203910792146807424695989321738890851054083637402667005167017061270516847880316162974354544703467411447977765663934331040806880513665688371243543136910550562656839280639831861677453524797613

e = 65537

Not all primes are created equal. Some are regal. Some are mere commoners.

Solution

As described in the previous article Super Baby RSA, the process of breaking RSA is quite easy, if you know the factorization of n.

In this problem… The hint given is that some primes are regal while some are more common.

While, finding out unused primes is interesting by itself, finding out highly used primes is a mater of cryptographic security, as finding commonly used primes will allow a lot of secure schemes to be broken by a brute force over all the possible combinations.

Wherein lies the solution of this problem. This is tagged as misc to notify that the n has no inherent cryptographic weaknesses.

Another hint was later given to make it clear that you need to find the commonly used primes reported in the logjam attack. And try to apply the same to the RSA.

There are multiple documents which show the primes that are used, and the main challenge here is to find and convert it to a usable form.

I parse the https://svn.nmap.org/nmap/scripts/ssl-dh-params.nse

These so-called Oakley primes are used by a really large portion of the internet. Which is somewhat scary in itself.

Parsing and trying out all the known 1024 bit Oakley primes pulled from NMAP source code gives two factors 179769313486231590770839156793787453197860296048756011706444423684197180216158519368947833795864925541502180565485980503646440548199239100050792877003355816639229553136239076508735759914822574862575007425302077447712589550957937778424442426617334727629299387668709205606050270810842907692932019128194467627007 and 102700630561259395087032918003696203215413680966205093401719261420927348617434421199810037690244910311348546427618773468138363558097981635746622031353236427233047123501573548251948502109660464742170278233192733579208742792462937581596612734833735829907594549504874993126473577377037753456164875577780679800659

Using this, the d is 13171628180214019278838905754167105900405269346939988185006223580409561413771524574818950076971449960121973520915955042200196617768502945219405780749949186495446138938430723470942850568391871669643102829484593783559990513472081615822964289053211665667656445508556331292855493114988327885737078503128347348572748885455807937524277633072698333853855205967604014397814455146478532842780484690925038766026524528458288022719244667551719482921152681313245063784916959178439546611189427825659985906610732208366763689820717117167105428606934433420049271816152101107904815791985824802988415964443148591069301373509901933446897

Solving RSA gives us flag flag{common_primes_are_bad_and_not_just_for_dh}

Flag

flag{common_primes_are_bad_and_not_just_for_dh}