rsa_harder.py

import itertools
from Crypto.PublicKey import RSA
import rsa
from prime_harder import gcd
primes = {11686569419932107703383162663552774744862933915113253284707869537882922602129341801701099319072407175023411166244523669241309336032098918622673499657188127, 11131246239045980891868413960642856079473322711361371834137735602582730829087219289690512888291754189012026831965159936250135505792644147542416796675807853, 11806151312123409009392518372754485453270174269596514849558850255557879073108491791093777565410052149172320816201754080233725907240524730714141876635615349, 10802980800004564188057641146492519064527626339682723570964109548748456573667450847726105643798782326083556383453790696389088948007894795320835865852269093, 10528748965165596624999728922542714083188951403324560623301832487779213497115036141058099759210401985552908691552595011750853977601361638134332247749506623, 9603401553730129797591115187600790438774495348917658793586281217769106263408375819698498495120927358887072005270202250317603541908406647942476436791944881, 10282924996936949432528279570066434755265156495149789793756294954057040575517026000078098624017495626345154251355101090383190218222280747000276319370914341, 11732335954060330790913557489701153419440436600746467242138988493141989064161677542143223299120180329046298587023160618227283801688072259151973012381649149, 12581911884198369328690693712475915261225489233389106443047646372615866955211439420337937281132201284708616791715834498840597052793845146861047330149481137, 11583530275221735195698925455528529531057177050957376479246897262094644780617276559445724951779333912541076460052280846132852861668507065372173286739076791, 10394161251526005806851472927378218101586358628815237064673546783828424504637983803717125551509636062466062581196157100747451618259640514280128633138075653, 11780119941979983664515118895326497512359126864191680208114004619194625940553297551327563756630289212540838420023442621434399674209406632734490384666422551, 12840224633040193562431820258545167340438085188997791993713977067366338587492451083994911540773885640333452159119903869667193716423315120796123277015483319, 12529520502488625901939790196374784222732080710876918106516450753211469371983512716793033928310390634655822445917167247387999090695245828042063537425971837, 9599005161818432919170160266824124957879439422580605148208522567471492840823635801421610725885580922146041959053239240205796639061610829910535920569079257, 10255045293963663094851569452415945539328353829432606126197501040352938297790982826951081046441567558276780469117234705584798538325569425420324949579917917, 12574273811664188952732009158479983305352476251782445611108113702249404877207034963866859552508823485540687053461424803723196052782129594171409989666814703, 12068007193924458934136437678747032125702047288192605563386647134926126290032925205587466786811951860570462107503408192389036293790565313661792631609456701, 11744066699568025065774046431061226031470034498895625857517304615487481948929590621937639490975784841853178202245850259504066957247905008803672352823595359, 11290942893206290336467162060839444758991526481896862143525109986063294905531141292368885863941910700698869187227122590028398079775349558555477255622057419, 10904149501499779508838937522169387559067222008037250222078468940641207789002374704749002881805697450614947396846481304369494631377355799540434638017768771, 11150259051060670469426085593401548368169572250533845163175765243729597277905626922154927370575025817010830489399792479900104306822956292957555245347527337, 10686435644326419519834061085977541924823851337325441245955473420224322128303875937977144928119000410701877753052938918048905331084631063254403249277800681, 13133249075655001428060250371635962734667685709823540232462761193810919863982779544067630357132152664871091959641377675551064981373795159065247275802895237, 12151103902467944932180156158873062948573080492237500332693167713858480993084590634774392326697834681630130544763936096229609784136402007012973019838323587, 10511769371014966274149589504548271132721209664282736949308262664410599991691871141982662651989249643039453893887761574380368119126769840184192522948626037, 13402174411206225077847349173371817657213170415901972637100313812263223783770473364167425791244340142471281334438860721441914466992692539085464648873224081, 9870344454385968899552415247980146339112022118657994668625976760932892718852414219112788165478611407647374361500030152150796482293056408514281267714884407, 10244546996504312302678010996347005012781924898000944951467466962058901127789757245888366144979323898049573260774324635727115725432720736210430375147778661, 10365376618238481038945710293559281787319416819671338162030641242562334191744185456263768321697545665513883266431498609669176420625845911933990171003484231}
breakthis = b'49f573321bdb3ad0a78f0e0c7cd4f4aa2a6d5911c90540ddbbaf067c6aabaccde78c8ff70c5a4abe7d4efa19074a5249b2e6525a0168c0c49535bc993efb7e2c221f4f349a014477d4134f03413fd7241303e634499313034dbb4ac96606faed5de01e784f2706e85bf3e814f5f88027b8aeccf18c928821c9d2d830b5050a1e'
breakthis = bytes.fromhex(breakthis.decode('ascii'))
print(repr(breakthis))
nhex = 0xc20a1d8b3903e1864d14a4d1f32ce57e4665fc5683960d2f7c0f30d5d247f5fa264fa66b49e801943ab68be3d9a4b393ae22963888bf145f07101616e62e0db2b04644524516c966d8923acf12af049a1d9d6fe3e786763613ee9b8f541291dcf8f0ac9dccc5d47565ef332d466bc80dc5763f1b1139f14d3c0bae072725815f
combs = itertools.combinations(primes, 2)
e=65537
def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
for c in combs:
    p=c[1]
    q=c[0]
    n=p*q
    if n==nhex:
        print('p',p,'q',q)
        print('nhex',hex(nhex),'n',hex(n))
        print(nhex == n)
        tot = (p-1)*(q-1)
        d = modinv(e, tot)
        print('tot', tot)
        print('e',e)
        print(d)
        assert (e*d)%tot == 1
        priv = RSA.construct((n,e,d,p,q)).decrypt(breakthis)
        print(priv)