import decimal import math from Crypto.Util.number import long_to_bytes # Returns GCD, x, y such that a * x + b * y = GCD(a, b) 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) """ GCD of 97/20 97=4*20+17 20=1*17+3 17=5*3+2 3=1*2+1 2=2*1+0 GCD is 1 (remainder is 0 at end) GCD of 100/20 100=5*20+0 GCD is 20 """ 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 cube_root(x): return decimal.Decimal(x) ** (decimal.Decimal(1) / decimal.Decimal(3)) def big_exponent(base, exp, mod): answer = 1 while exp > 0: if exp % 2 == 0: base = (pow(base, 2)) % mod exp //= 2 else: answer = (base * answer) % mod exp -= 1 return answer # https://stackoverflow.com/questions/356090/how-to-compute-the-nth-root-of-a-very-big-integer def find_invpow(x,n): high = 1 while high ** n <= x: high *= 2 low = high/2 while low < high: mid = (low + high) // 2 if low < mid and mid**n < x: low = mid elif high > mid and mid**n > x: high = mid else: return mid return mid + 1 def find_invpowAlt(x,n): low = 10 ** (len(str(x)) / n) high = low * 10 while low < high: mid = (low + high) // 2 if low < mid and mid**n < x: low = mid elif high > mid and mid**n > x: high = mid else: return mid return mid + 1 """ # basic c = 44431629706061305008143502423137012887277828135988218627924826848164974267369140114151116956542699876402139670467425045450301114213737667412294102131791639564117923536368256828998437520972285622395911648477760804325095186682980015103833775233929473511843707365929109604516730159351999709137396760951561724605394354694071245237933265597444643797363943646984709831864750620734406848781544782140580781553249778510852115417666510789869996230415178275721761766565175907645048897615709905109681846646689243575820894299256876151171950776037745474751371071726067019383683284965811296018491131082246881726583726305095371092727 p = 212691419494563911012016458107764706057027846660556923783295585947349837091530859782385987932959348656441135167812270695168242808938780720834424043119692739636350805618004977676905871536695150965234220710456913491845984031497483010709484108563662345764645393885590662297355667270911004188786194404493930584763 q = 343771555081128227560810773103703230186239929820487041012723599379603845162266648302382922824441150879585264855730391652295840969079127665092831035812274337557171176301884861906361106483559667673320137971212932682795921938761120540964583816300085118595116098901061368547890422579172952819065405212828098113467 e = 102218683034763828584589001371647041187532369615830565599787446410855812507707 totient = (p - 1) * (q - 1) d = modinv(e, totient) flag = big_exponent(c, d, p * q) print(long_to_bytes(flag)) """ """ # broadcast attack c1 = 261345950255088824199206969589297492768083568554363001807292202086148198632298416227800170521403879169323939870136918495166376001415603107530798184803733942230649625863328280827871999560410058158409477539013408803889636337981870043792827095136037430392653831785807945977864288192407940225619843273330120029313 n1 = 1001191535967882284769094654562963158339094991366537360172618359025855097846977704928598237040115495676223744383629803332394884046043603063054821999994629411352862317941517957323746992871914047324555019615398720677218748535278252779545622933662625193622517947605928420931496443792865516592262228294965047903627 c2 = 147535246350781145803699087910221608128508531245679654307942476916759248403409499940709875170482499717373851969854700407365859710668248221534523112910895863625501694252104929562808450560410931902051428001118134260015071473417379253511812576559427770355902270332217159041674805147868562215268081818231962157802 n2 = 405864605704280029572517043538873770190562953923346989456102827133294619540434679181357855400199671537151039095796094162418263148474324455458511633891792967156338297585653540910958574924436510557629146762715107527852413979916669819333765187674010542434580990241759130158992365304284892615408513239024879592309 c3 = 633230627388596886579908367739501184580838393691617645602928172655297372237425265855898468213006428127058041006464863408951623696827190570241149630919096283514787011922034385643767864879634861850565793738024061098801151563062727926809059198778760627479771564465550880228117974715945657575773914891371732645934 n3 = 1204664380009414697639782865058772653140636684336678901863196025928054706723976869222235722439176825580211657044153004521482757717615318907205106770256270292154250168657084197056536811063984234635803887040926920542363612936352393496049379544437329226857538524494283148837536712608224655107228808472106636903723 e = 3 t1 = c1 * (n2 * n3) * modinv(n2 * n3, n1) t2 = c2 * (n1 * n3) * modinv(n1 * n3, n2) t3 = c3 * (n1 * n2) * modinv(n1 * n2, n3) c = (t1 + t2 + t3) % (n1 * n2 * n3) with decimal.localcontext() as context: context.prec = 150 m = cube_root(c) print(long_to_bytes(m)) # http://crypto.stackexchange.com/questions/6713/low-public-exponent-attack-for-rsa """ """ # weird rsa # dp and dq are given instead of e c = 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885 p = 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243 q = 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629 dp = 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961 dq = 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659 qinv = modinv(q,p) m1 = pow(c,dp,p) m2 = pow(c,dq,q) h = (qinv * (m1-m2)) % p m = m2 + (h*q) print(long_to_bytes(m)) """