Tags: modinv elgamal

Rating: 4.0

# lagalem (crypto, 35 solved, 246p)

In the challenge we get [source code](problem.py) and [result](transcript.txt) 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:

python
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:

python
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:

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


from the first run, and

python
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:

python
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}`

Original writeup (https://github.com/p4-team/ctf/tree/master/2018-07-28-code-blue-quals/crypto_lagalem).