Code Blue CTF 2018 - Lagalem Writeup

crypto
,

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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:

  • , random primes
  • such that
  • random values
  • random
  • that is the flag
  • , , , that are the encryption results

Attack

We’re given as a public key, so basically we have to find or . The problem with this encryption is that and are correlated and are used to encrypt the same message , so let’s try to work on . Because we are working modulo a prime we know that the modular inverse of exists, so . Working on we find

Now recalling Fermat’s little theorem: if is a prime and we have .
Noticing that we know that there exists the multiplicative inverse of modulo , so

The Python code to perform this attack is the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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}