Question
problem.py:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
from Crypto.Util.number import * from Crypto.Random.random import randint import gmpy import key FLAG = long(key.FLAG.encode("hex"), 16) def get_random_prime(bits=1024): return int(gmpy.next_prime(randint(2**(bits-1), 2**bits))) def gen_n(bits=1024): p = getStrongPrime(bits) q = getStrongPrime(bits) return p*q, p, q def encrypt(pk, m): assert m < pk[0] return pow(m, pk[1], pk[0]) def decrypt(pk, sk, c): return pow(c, sk[0], pk[0]) def test(n, p, q): e = 3 * get_random_prime(20) pk, sk = (n, e), (long(gmpy.invert(e, (p-1)*(q-1))), ) print "[+] RSA Self Test: %r" % (pk, ) c = encrypt(pk, FLAG) print "[+] ciphertext = %d" % c m = decrypt(pk, sk, c) print "[+] Dec(Enc(m)) == m? : %s" % (m == FLAG) if __name__ == "__main__": n, p, q = gen_n(2048) test(n, p, q) test(n, p, q) |
transcript.py:
|
1 2 3 4 5 6 7 8 |
[+] RSA Self Test: (691611766208546073444876122261067788277978858453710639029761974358666489171591889808344592871468081368348731289584873825685836699513369087940744233044470468106283756269016888690397802087612562650740690626844050981638158798650899164329024889012339813251634342169796374490173324858177655412520581064091323105709703802894635752243504165527728325493775585018099572491218738859140069209745383085972126419677929983854492018948495162457428459536088314487922683148031388611849013227501962458386817851194913551405843074740308192841259015955432216658418219471365781271743026881045054161177699500233983945284463060091084401032681620162554495490307966608011765399197534175588394769839991952726269105973546086964385977836193216093842605576347580465390858378577913173391209728199847916944392685608959720919745441534152140791433228642857247821519585327091864890122871765266988285510728943279970135846908966516130597249552710186071954611133294079017500030355232895541367427153922527925908108643934213023557398363684188823565535815365161748782796247844503993809352854741573950620787090272760236473228652960605730173150252619759400890068298838592790770868307280012495168740250977525199965477849089021924445456338550258621310346872587368865023459114279L, 2623119) [+] ciphertext = 632613645684838434911920364870092246688638723680203743297038042884981435531349983627632652213126007404455112992754038899192740232209237012089852184466576496173356903126767617531366105427616049893559911396536574555008451239827427140619373005107923039458285095437111146013805698400274937791209388463040761234346114146112603113513874269976957472698342250573902102976387047390228485927254752372525379266486917620487089416581168720140744193600912161065888758451629009978676721731074043142666019127528370181044741033938879227651226413524178992155234346229899043794846119210274959231350300191718278291314079326011260972911790929707654859407903619102516710246683375658271085356783673232677699444921875427077745087507202504075374873842972977165904031632108921391219453633100007509368853543202918527396858214941532156620908283394786740941868393377733920317480973184132461984594109692489226477402338664642727766514992506288377119275635222078018270479534265371971469799345627297451492177595572561618185463142728664331779856911512823762928116551034186671353283417747535010208121962539603383913657773795358612010178381857101029638404248669376029927680328805839410427459248430136708902815920536603541943356116875656311481908672896225539754812052984 [+] Dec(Enc(m)) == m? : True [+] RSA Self Test: (691611766208546073444876122261067788277978858453710639029761974358666489171591889808344592871468081368348731289584873825685836699513369087940744233044470468106283756269016888690397802087612562650740690626844050981638158798650899164329024889012339813251634342169796374490173324858177655412520581064091323105709703802894635752243504165527728325493775585018099572491218738859140069209745383085972126419677929983854492018948495162457428459536088314487922683148031388611849013227501962458386817851194913551405843074740308192841259015955432216658418219471365781271743026881045054161177699500233983945284463060091084401032681620162554495490307966608011765399197534175588394769839991952726269105973546086964385977836193216093842605576347580465390858378577913173391209728199847916944392685608959720919745441534152140791433228642857247821519585327091864890122871765266988285510728943279970135846908966516130597249552710186071954611133294079017500030355232895541367427153922527925908108643934213023557398363684188823565535815365161748782796247844503993809352854741573950620787090272760236473228652960605730173150252619759400890068298838592790770868307280012495168740250977525199965477849089021924445456338550258621310346872587368865023459114279L, 2611101) [+] ciphertext = 473583830101449207063655453483957320801977763405664178108962387145963115641321631378723122470718049239150183483107837540062110255460217493574236417576528210993551734521104360323008425196350719034294427914294044848231276934402896045785500160974092767601908407706594433190832523140982335688121038712802163776950422665847149664034820576774873956120202470663588902529914328392634164212558025176982387474287314624421143326789371057668708456922968762564019631616913937820209470604081356673188045257490667304640155390478645279862586730343779998826931285683980941686981775369499484033439920659579124275957233449431588512697916708510428626881790592757578867152025501459202793986322020476004209777449674143157280081483085868896558215825742742029607229809248023263081810931655981810534293127835168642962477010095223356972141559004635008185531900175232541978761179342338914489553003329293031284557554252476291770973145365678145226167965362251186233138510776436645583796590010200995100899736056399413460647507781994189935869541735701599175369334170081795310585938471394672279359692859881857399434361716843681313191143289947464231132723256066979526475873327590657111481299295002695482778491520250596998683754980263059514032256777144682239680031331 [+] Dec(Enc(m)) == m? : True |
Solution
Compare with v1, v2 just make changed in exponent. So, what we need to do is only find the root after get the result.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import sys import gmpy2 sys.setrecursionlimit(100000); def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, 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 def main(): n= 691611766208546073444876122261067788277978858453710639029761974358666489171591889808344592871468081368348731289584873825685836699513369087940744233044470468106283756269016888690397802087612562650740690626844050981638158798650899164329024889012339813251634342169796374490173324858177655412520581064091323105709703802894635752243504165527728325493775585018099572491218738859140069209745383085972126419677929983854492018948495162457428459536088314487922683148031388611849013227501962458386817851194913551405843074740308192841259015955432216658418219471365781271743026881045054161177699500233983945284463060091084401032681620162554495490307966608011765399197534175588394769839991952726269105973546086964385977836193216093842605576347580465390858378577913173391209728199847916944392685608959720919745441534152140791433228642857247821519585327091864890122871765266988285510728943279970135846908966516130597249552710186071954611133294079017500030355232895541367427153922527925908108643934213023557398363684188823565535815365161748782796247844503993809352854741573950620787090272760236473228652960605730173150252619759400890068298838592790770868307280012495168740250977525199965477849089021924445456338550258621310346872587368865023459114279L e1= 2623119 e2= 2611101 c1= 632613645684838434911920364870092246688638723680203743297038042884981435531349983627632652213126007404455112992754038899192740232209237012089852184466576496173356903126767617531366105427616049893559911396536574555008451239827427140619373005107923039458285095437111146013805698400274937791209388463040761234346114146112603113513874269976957472698342250573902102976387047390228485927254752372525379266486917620487089416581168720140744193600912161065888758451629009978676721731074043142666019127528370181044741033938879227651226413524178992155234346229899043794846119210274959231350300191718278291314079326011260972911790929707654859407903619102516710246683375658271085356783673232677699444921875427077745087507202504075374873842972977165904031632108921391219453633100007509368853543202918527396858214941532156620908283394786740941868393377733920317480973184132461984594109692489226477402338664642727766514992506288377119275635222078018270479534265371971469799345627297451492177595572561618185463142728664331779856911512823762928116551034186671353283417747535010208121962539603383913657773795358612010178381857101029638404248669376029927680328805839410427459248430136708902815920536603541943356116875656311481908672896225539754812052984 c2= 473583830101449207063655453483957320801977763405664178108962387145963115641321631378723122470718049239150183483107837540062110255460217493574236417576528210993551734521104360323008425196350719034294427914294044848231276934402896045785500160974092767601908407706594433190832523140982335688121038712802163776950422665847149664034820576774873956120202470663588902529914328392634164212558025176982387474287314624421143326789371057668708456922968762564019631616913937820209470604081356673188045257490667304640155390478645279862586730343779998826931285683980941686981775369499484033439920659579124275957233449431588512697916708510428626881790592757578867152025501459202793986322020476004209777449674143157280081483085868896558215825742742029607229809248023263081810931655981810534293127835168642962477010095223356972141559004635008185531900175232541978761179342338914489553003329293031284557554252476291770973145365678145226167965362251186233138510776436645583796590010200995100899736056399413460647507781994189935869541735701599175369334170081795310585938471394672279359692859881857399434361716843681313191143289947464231132723256066979526475873327590657111481299295002695482778491520250596998683754980263059514032256777144682239680031331 s = egcd(e1, e2) s1 = s[1] s2 = s[2] if s1<0: s1 = - s1 c1 = modinv(c1, n) elif s2<0: s2 = - s2 c2 = modinv(c2, n) m = (pow(c1,s1,n)*pow(c2,s2,n))%n gmpy2.get_context().precision=2000 m = gmpy2.root(m,3) print str(hex(int(str(m)[:-2])))[2:-1].decode('hex') if __name__ == '__main__': main() |
Be First to Comment