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_)
Analyzing the code we have:
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}\)
\[\Rightarrow m = ((C_2'(h^B)^{-1}C_2^{-1})^{(A-1)^{-1}})^{-1}C_2\]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}
crypto elgamal