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