# pwnthem0le

## pwnthem0le is a Turin-based, hacking students group born out of CyberChallenge 2018. Read more about us!

17 September 2018

# Code Blue CTF 2018 - Lagalem Writeup

by mr96

We’re given a piece of Python code and the result of the encryption of the flag:

from Crypto.Util.number import *
from key import FLAG

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

def keygen(size):
q = getPrime(size)
k = 2
while True:
p = q * k + 1
if isPrime(p):
break
k += 1
g = 2
while True:
if pow(g, q, p) == 1:
break
g += 1
A = getRandomInteger(size) % q
B = getRandomInteger(size) % q
x = getRandomInteger(size) % q
h = pow(g, x, p)
return (g, h, A, B, p, q), (x, )

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

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)

# pubkey, privkey = keygen(size)

m = bytes_to_long(FLAG)
c1, c2 = encrypt(pubkey, m)
c1_, c2_ = encrypt(pubkey, m)

print pubkey
print (c1, c2)
print (c1_, c2_)

## Code Analysis

Analyzing the code we have:

• $q$, $p=qk+1$ random primes
• $g$ such that $g^q \equiv 1 \pmod{p}$
• $A,B,x \in \{0,...,q-1\}$ random values
• $r$ random
• $m$ that is the flag
• $C_1=g^r \pmod{p}$, $C_2=mh^r \pmod{p}$, $C_1'=g^{r'} \pmod{p}$, $C_2'=mh^{r'}\pmod{p}$ that are the encryption results

## Attack

We’re given $g,h,A,B,p,q$ as a public key, so basically we have to find $x$ or $r$. The problem with this encryption is that $r$ and $r'$ are correlated and are used to encrypt the same message $m$, so let’s try to work on $r$. Because we are working modulo a prime $p$ we know that the modular inverse of $h^r$ exists, so $m = (h^r)^{-1}C_2$. Working on $C_2'$ we find $C_2'=mh^{r'}=mh^{Ar}h^B$ $\Rightarrow C_2'(h^B)^{-1}=mh^{Ar}$ $\Rightarrow C_2'(h^B)^{-1}C_2^{-1}=h^{(A-1)r}$

Now recalling Fermat’s little theorem: if $p$ is a prime and $a \in \mathbb{Z}_p$ we have $a^{p-1}\equiv 1 \pmod{p}$. Noticing that $gcd(A-1,p-1)=1$ we know that there exists the multiplicative inverse of $A-1$ modulo $p-1$ $(A-1)^{-1}$, so $(h^{(A-1)r})^{(A-1)^{-1}}=(h^r)^{(A-1)(A-1)^{-1}}=h^r \pmod{p}$

The Python code to perform this attack is the following:

def tobytes(n): #long to bytes
return n.to_bytes((n.bit_length() + 7) // 8, 'big')

def modinv(a, n): #modular inverse of a modulo n
t, r = 0, n
new_t, new_r = 1, a
while new_r != 0:
quotient = r // new_r
t, new_t = new_t, t - quotient * new_t
r, new_r = new_r, r - quotient * new_r
if r > 1:
raise Exception("a is not invertible modulo n")
if t < 0:
t = t + n
return t

(g, h, A, B, p, q) = (1468, 13176937611470940769675424427237214361327027262801017230328464476187661764921664954701796966426482598685480847329992216474898047298138546932927013411286080877561831522628228420965755215837424657249966873002314137994287169213354516263406270423795978394635388801400699885714033340665899016561199970830561882935631759522528099622669587315882980737349844878337007525538293173251532224267379685239505646821600410765279043812411429818495529092434724758640978876122625789495327928210547087547860489325326144621483366895679471870087870408957451137227143277719799927169623974008653573716761024220674229810095209914374390011024349L, 22171697832053348372915156043907956018090374461486719823366788630982715459384574553995928805167650346479356982401578161672693725423656918877111472214422442822321625228790031176477006387102261114291881317978365738605597034007565240733234828473235498045060301370063576730214239276663597216959028938702407690674202957249530224200656409763758677312265502252459474165905940522616924153211785956678275565280913390459395819438405830015823251969534345394385537526648860230429494250071276556746938056133344210445379647457181241674557283446678737258648530017213913802458974971453566678233726954727138234790969492546826523537158L, 21251918005448659289449540367076207273003136102402948519268321486936734267649761131906829634666742021555542747288804916060499331412675118289617172656894696939180508678248554638496093176525353583495353834532364036007392039073993229985968415793651145047522785446635657509992391925580677770086168373498842908951372029092354946478354834120976530860456422386647226785585577733215760931557612319244940761622252983954745116260878050222286503437408510241127875494413228131438716950664031868505118149350877745316461481208779725275726026031260556779604902294937659461052089402100729217965841272238065302532882861094831960922472L, 36416598149204678746613774367335394418818540686081178949292703167146103769686977098311936910892255381505012076996538695563763728453722792393508239790798417928810924208352785963037070885776153765280985533615624550198273407375650747001758391126814998498088382510133441013074771543464269812056636761840445695357746189203973350947418017496096468209755162029601945293367109584953080901393887040618021500119075628542529750701055865457182596931680189830763274025951607252183893164091069436120579097006203008253591406223666572333518943654621052210438476603030156263623221155480270748529488292790643952121391019941280923396132717L, 22703614806237330889410083770159223453128766013766321040706174044355426290328539338099711291079959714155244437030261032146984868113293511467274463709974076015468157237127672046781216262952714317506848836418718547505157984648161313592118697709984413028733405554946035544310954827596178187067728654513993575659442761349110567922330434847940441527278779320200714023296202983137830985906413366968841334238825204827013560287441312629166207563391639545363637173286538187147065563647798900324550559230799880457351250762884396716657695545274970206009025313609823106997020670498921913048309409470476279377425822906035488401579L)
c2 = 5064525527428049600491919498697464537972502845819664938128937188305922639513846993504687207386360776106923020699628828454337579775714240066556800908455279363001454291677717261452161432964569952225095272897486314418226314084410743187186707224835212073276372184743923025929949904169574601792248026913036485498766503887136170182876527166516406031488332812278716443348188296343938621495282255755130158373758531773477662489309286204821174677297869253776424203299305194343234106107768105109553941283693258837262880530221857757115324039088850806164791445830838849835091131899191925571818438481246247468753757273234134261109718L)
c21 = 16267453627205268534367753680421495469763757833841239080352379243552352542017520577799374052771731918885648298929081367071246911126370204338693352348289112387958308732218740188775134797384686955193576200043360689334709947260640015994980749571533954121908310007422239513584361571910193760719359731740480942535224174560848463926576528210476460419021197098876171728766893668501013719257464606515863038046180251018737679498423947578193874965936933252602254324298341970127449647765609487557270029347118240547476459496038940032926457872400805963990886019493151641503310555553381629104818030667858884055226529074481528015135269L)

m = (c2 * modinv(pow(c21 * modinv(pow(h, B, p), p)*modinv(c2, p), modinv(A - 1, p - 1), p), p)) % p
print(tobytes(m))

that prints out the flag: CBCTF{183a3ce8ed93df613b002252dfc741b2}

tags: crypto  elgamal