Welcome to Hackcon 2017. This is organised by a couple of students from IIIT Delhi, along with our techfest esya.
Some of us are organising our first CTF, have fun and let us know how it was.
1 2 3 4
$ curl http://esya.iiitd.edu.in/ | grep d4rk % Total % Received % Xferd Average Speed Time Time Time Current Dload Upload Total Spent Left Speed 2 52017 2 1193 0 0 1835 0 0:00:28 --:--:-- 0:00:28 1835 <!----The flag is d4rk{w3lc0m3_t0_35y4_2017}c0de---->
Go read about RSA and how it works, then try to solve this.
1 2 3 4 5 6 7
p = 152571978722786084351886931023496370376798999987339944199021200531651275691099103449347349897964635706112525455731825020638894818859922778593149300143162720366876072994268633705232631614015865065113917174134807989294330527442191261958994565247945255072784239755770729665527959042883079517088277506164871850439
c = 8511718779884002348933302329129034304748857434273552143349006561412761982574325566387289878631104742338583716487885551483795770878333568637517519439482152832740954108568568151340772337201643636336669393323584931481091714361927928549187423697803637825181374486997812604036706926194198296656150267412049091252088273904913718189248082391969963422192111264078757219427099935562601838047817410081362261577538573299114227343694888309834727224639741066786960337752762092049561527128427933146887521537659100047835461395832978920369260824158334744269055059394177455075510916989043073375102773439498560915413630238758363023648
#!/usr/bin/python2 # credit : http://jhafranco.com/2012/01/29/rsa-implementation-in-python/ defint2Text(number, size): text = "".join([chr((number >> j) & 0xff) for j inreversed(range(0, size << 3, 8))]) return text.lstrip("\x00") # credit : http://stackoverflow.com/questions/4798654/modular-multiplicative-inverse-function-in-python defegcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) defmodinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m p = 152571978722786084351886931023496370376798999987339944199021200531651275691099103449347349897964635706112525455731825020638894818859922778593149300143162720366876072994268633705232631614015865065113917174134807989294330527442191261958994565247945255072784239755770729665527959042883079517088277506164871850439 q = 147521976719041268733467288485176351894757998182920217874425681969830447338980333917821370916051260709883910633752027981630326988193070984505456700948150616796672915601007075205372397177359025857236701866904448906965019938049507857761886750656621746762474747080300831166523844026738913325930146507823506104359 e = 65537 c = 8511718779884002348933302329129034304748857434273552143349006561412761982574325566387289878631104742338583716487885551483795770878333568637517519439482152832740954108568568151340772337201643636336669393323584931481091714361927928549187423697803637825181374486997812604036706926194198296656150267412049091252088273904913718189248082391969963422192111264078757219427099935562601838047817410081362261577538573299114227343694888309834727224639741066786960337752762092049561527128427933146887521537659100047835461395832978920369260824158334744269055059394177455075510916989043073375102773439498560915413630238758363023648 phi = (p-1)*(q-1) d = modinv(e, phi) n = p*q m_int = pow(c,d,n) print int2Text(m_int, len(str(m_int)))
$ xortool -x file.txt The most probable key lengths: 2: 11.8% 6: 19.8% 8: 9.2% 12: 14.8% 14: 6.9% 18: 11.1% 20: 5.3% 24: 8.6% 30: 6.9% 36: 5.6% Key-length can be 3*n Key-length can be 4*n Key-length can be 6*n Most possible char is needed to guess the key!
$ xortool -x -l 6 -o file.txt && grep -ri d4rk xortool_out 100 possible key(s) of length 6: rxqbqd sypcpe pzs`sf q{rarg v|ufu` ... Found 58 plaintexts with 95.0%+ printable characters See files filename-key.csv, filename-char_used-perc_printable.csv xortool_out/94.out:and maces, the Asuras in large numbers vomited blood and lay prostrate on the earth. Cut off from the trunks with sharp double-edged swords, heads adorned with bright gold, fell continually on the field of battle. Their bodies drenched in gore, the great Asuras lay dead everywhere. It seemed as if red-dyed mountain peaks d4rk{Try_r34ding_mahabharata_s0met1me}c0de lay scattered all around. And when the Sun rose in his splendour, thousands of warriors struck one another with weapons. And cries of distress were heard everywhere. The warriors fighting at a distance from one another brought one another down by sharp iron missiles, and those fighting at close quarters slew one another with blows of their fists. And the air was filled with shrieks of distress. Everywhere were heard the alarming sounds,--'cut', 'pierce', 'at them', 'hurl down', 'advance'.
n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381
e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205
c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635
#!/usr/bin/python from sympy.solvers import solve from sympy import Symbol defpartial_quotiens(x, y): pq = [] while x != 1: pq.append(x / y) a = y b = x % y x = a y = b #print pq return pq defrational(pq): i = len(pq) - 1 num = pq[i] denom = 1 while i > 0: i -= 1 a = (pq[i] * num) + denom b = num num = a denom = b #print (num, denom) return (num, denom) defconvergents(pq): c = [] for i inrange(1, len(pq)): c.append(rational(pq[0:i])) #print c return c defphiN(e, d, k): return ((e * d) - 1) / k # e = 17993 # n = 90581 # wiener_attack(e, n) --> p = 239, q = 379 e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205 n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381 pq = partial_quotiens(e, n) c = convergents(pq) x = Symbol('x') for (k, d) in c: if k != 0: y = n - phiN(e, d, k) + 1 roots = solve(x**2 - y*x + n, x) iflen(roots) == 2: p = roots[0] q = roots[1] if p * q == n: print'p = ', p print'q = ', q break
1 2 3
$ python2 wiener.py p = 10114792273660656874618568712406420344176220457790563178092222929337786916374923318745284718351487926620784106195715878875311958793629905453919697155685507 q = 10843221374140991753173625949764386011485161421520044246309105053489500519257941272796681417497061734054081478280518835582353321569961722963922828311576983
Let's read the message with our first python script:
#!/usr/bin/python2 # credit : http://jhafranco.com/2012/01/29/rsa-implementation-in-python/ defint2Text(number, size): text = "".join([chr((number >> j) & 0xff) for j inreversed(range(0, size << 3, 8))]) return text.lstrip("\x00") # credit : http://stackoverflow.com/questions/4798654/modular-multiplicative-inverse-function-in-python defegcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) defmodinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m p = 10114792273660656874618568712406420344176220457790563178092222929337786916374923318745284718351487926620784106195715878875311958793629905453919697155685507 q = 10843221374140991753173625949764386011485161421520044246309105053489500519257941272796681417497061734054081478280518835582353321569961722963922828311576983 e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205 c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635 phi = (p-1)*(q-1) d = modinv(e, phi) n = p*q m_int = pow(c,d,n) print int2Text(m_int, len(str(m_int)))