crypto_lagalem

lagalem (crypto, 35 solved, 246p)

In the challenge we get source code and result of this code when executed with the flag present. Our goal is to use the outputs to recover the original flag.

The encryption itself is:

def encrypt(pubkey, m):
    g, h, A, B, p, q = pubkey
    assert 0 < m <= p
    r = rand(A, B, q)
    c1 = pow(g, r, p)
    c2 = (m * pow(h, r, p)) % p
    return (c1, c2)

Which is almost textbook ElGamal cryptosystem. The twist and vulnerability comes from the rand function. Normally the value of r should be random, and unpredictable. This is because otherwise we could easily recover the shared secret value which is h^r mod p, and with the shared secret we can decrypt the ciphertext simply by multiplying c2 by modinv(shared_secret, p).

If we look at how rand function works we can see:

size = 2048
rand_state = getRandomInteger(size // 2)

def rand(A, B, M):
    global rand_state
    rand_state, ret = (A * rand_state + B) % M, rand_state
    return ret

So while the first value of rand_state is a strong crypto-safe random, the next value is just a result of a linear function on the initial value.

Let's enumerate what values we actually know:

c1 = pow(g, r, p)
c2 = (m * pow(h, r, p)) % p

from the first run, and

c1 = pow(g, r_prim, p) = pow(g, ((A * r + B) mod q), p)
c2 = (m * pow(h, r_prim, p)) % p = (m * pow(h, ((A * r + B) mod q), p)) % p

from the second run.

Let's re-write the last equation as:

(m * pow(h, ((A * r + B) mod q), p)) % p = m * h^(A*r+B mod q) mod p = m * h^(A*r mod q) * h^(B mod q) mod p

This is not entirely correct mathematically, since A*r + B mod q might not be equal to A*r mod q + B mod q, but for lack of better ideas I assumed that maybe the values are selected to make this equation valid, and thus the challenge solvable.

First we want to get rid of the * h^(B mod q) mod p part, and since we know all the variables, we can just multiply this by modinv(h^B mod p). We're left with:

m * h^(A*r mod q) * h^(B mod q) mod p * modinv(h^B mod p) = m * h^(A*r mod q) mod p

Now we want to get rid of m from the equation, and we can use the c2 from first run to achieve this. We can multiply the equation we have by modinv(c2,p) which will give us:

(m * h^(A*r mod q) mod p) * modinv(m * h^r mod p,p) = h^((A-1)*r) mod p`

We want to recover the shared secret which is h^r mod p, and therefore we need to get rid of this A-1 power. We can use here the Euler Theorem, which is the same technique used in RSA decryption process.

In short, if we have a^k mod n then raising this to the power of modinv(k, phi(n)) will effectively cancel out the k leaving only a mod n. In RSA the hard part is that we don't know phi(n) because n is composite number, and in order to calculate phi we need all prime factors of this number. However, in our case the modulus is prime, and phi for a prime is simply p-1.

In our case we simply do:

h^((A-1)*r) mod p * modinv(A-1, phi(p)) = h^((A-1)*r) mod p * modinv(A-1, p-1) = h^r mod p = shared_secret

Once we have the shared secret value we can simply decrypt the c2 message by multiplying it by modinv(shared_secret, p)

The code which performs this is:

from crypto_commons.generic import long_to_bytes
from crypto_commons.rsa.rsa_commons import modinv


def main():
    (g, h, A, B, p, q) = (1468,
                          13176937611470940769675424427237214361327027262801017230328464476187661764921664954701796966426482598685480847329992216474898047298138546932927013411286080877561831522628228420965755215837424657249966873002314137994287169213354516263406270423795978394635388801400699885714033340665899016561199970830561882935631759522528099622669587315882980737349844878337007525538293173251532224267379685239505646821600410765279043812411429818495529092434724758640978876122625789495327928210547087547860489325326144621483366895679471870087870408957451137227143277719799927169623974008653573716761024220674229810095209914374390011024349L,
                          22171697832053348372915156043907956018090374461486719823366788630982715459384574553995928805167650346479356982401578161672693725423656918877111472214422442822321625228790031176477006387102261114291881317978365738605597034007565240733234828473235498045060301370063576730214239276663597216959028938702407690674202957249530224200656409763758677312265502252459474165905940522616924153211785956678275565280913390459395819438405830015823251969534345394385537526648860230429494250071276556746938056133344210445379647457181241674557283446678737258648530017213913802458974971453566678233726954727138234790969492546826523537158L,
                          21251918005448659289449540367076207273003136102402948519268321486936734267649761131906829634666742021555542747288804916060499331412675118289617172656894696939180508678248554638496093176525353583495353834532364036007392039073993229985968415793651145047522785446635657509992391925580677770086168373498842908951372029092354946478354834120976530860456422386647226785585577733215760931557612319244940761622252983954745116260878050222286503437408510241127875494413228131438716950664031868505118149350877745316461481208779725275726026031260556779604902294937659461052089402100729217965841272238065302532882861094831960922472L,
                          36416598149204678746613774367335394418818540686081178949292703167146103769686977098311936910892255381505012076996538695563763728453722792393508239790798417928810924208352785963037070885776153765280985533615624550198273407375650747001758391126814998498088382510133441013074771543464269812056636761840445695357746189203973350947418017496096468209755162029601945293367109584953080901393887040618021500119075628542529750701055865457182596931680189830763274025951607252183893164091069436120579097006203008253591406223666572333518943654621052210438476603030156263623221155480270748529488292790643952121391019941280923396132717L,
                          22703614806237330889410083770159223453128766013766321040706174044355426290328539338099711291079959714155244437030261032146984868113293511467274463709974076015468157237127672046781216262952714317506848836418718547505157984648161313592118697709984413028733405554946035544310954827596178187067728654513993575659442761349110567922330434847940441527278779320200714023296202983137830985906413366968841334238825204827013560287441312629166207563391639545363637173286538187147065563647798900324550559230799880457351250762884396716657695545274970206009025313609823106997020670498921913048309409470476279377425822906035488401579L)
    c1, c2 = (
        33793492710782731124369494459076474097807208878884233971164269278616670211040150701930155825011078169703308214232135321652078394446224640155796276327836370352633498860894979473374779013668639507298858624745688704898736146513461608044730232178589141572128789087250031273718023043376262651608195761389064329854778210975268322619838848614213216968252753471982762060566109470077138563127080437316815457079933537918356467531614438670082804203944345043085444729429607433486011840510876970137900905036806208322070921744641554316383849334181081430914313498093196130476486829383116502543520979690739362110736793492207923196520816L,
        5064525527428049600491919498697464537972502845819664938128937188305922639513846993504687207386360776106923020699628828454337579775714240066556800908455279363001454291677717261452161432964569952225095272897486314418226314084410743187186707224835212073276372184743923025929949904169574601792248026913036485498766503887136170182876527166516406031488332812278716443348188296343938621495282255755130158373758531773477662489309286204821174677297869253776424203299305194343234106107768105109553941283693258837262880530221857757115324039088850806164791445830838849835091131899191925571818438481246247468753757273234134261109718L)
    c3, c4 = (
        23858001256263338639930754561393744300621498668566466378945331004639513430979203635665722789744134073627181079853617277622660322019360636513261004488765082049390326032711679225336301342778034088938726495035474355141650387408421374480476173872396852119494181935635150757138413142985246448394125423745476143726661234600332521054350310909895716505182112634281850443223646354787752416535512150749925760599825164197040257221389261843550191277292909027805321111623815531377898276273229673439686502578126512634020924256597140201920931951309168862709610195813440797540084536725074915035709996827322859002529289313937152193672624L,
        16267453627205268534367753680421495469763757833841239080352379243552352542017520577799374052771731918885648298929081367071246911126370204338693352348289112387958308732218740188775134797384686955193576200043360689334709947260640015994980749571533954121908310007422239513584361571910193760719359731740480942535224174560848463926576528210476460419021197098876171728766893668501013719257464606515863038046180251018737679498423947578193874965936933252602254324298341970127449647765609487557270029347118240547476459496038940032926457872400805963990886019493151641503310555553381629104818030667858884055226529074481528015135269L)

    step_one = c4 * modinv(pow(h, B, p), p)
    step_two = step_one * modinv(c2, p)
    shared_secret = pow(step_two, modinv(A - 1, p - 1), p)
    m = (c2 * modinv(shared_secret, p)) % p
    print(long_to_bytes(m))

main()

And we get CBCTF{183a3ce8ed93df613b002252dfc741b2}