John-Bull

Author: GabiTulba
Contest: ASIS CTF 2018

Problem statement:

John is looking for his intimate close friend! Find him for John!!

My opinion:

Funny enough, I solved this challenge in the subway, in my head after my phone died. The idea is pretty simple you just needed to pay attention to what was given to you.

The problem:

We are given a couple functions in python and some output:

def make_key(k):
    while True:
        r = getRandomInteger(k) << 2
        p, q = r**2+r+1, r**2+3*r+1
        if gmpy.is_prime(p) * gmpy.is_prime(q):
            break
    pubkey = r**6 + 5*r**5 + 10*r**4 + 13*r**3 + 10*r**2 + 5*r + 1
    return pubkey

def encrypt(m, pubkey):
    return pow(bytes_to_long(m), pubkey, pubkey)

pubkey = 3415775651990117231114868059991823731694168391465118261123541073986397702947056759501589697018682285283905893102019391953165129250445987511496328390478214156138550568081360884795196720007402795178414072586445084589188812271144227913976270609786532206307549154139514246177504313696905220271023590900584622193476455815728425827517096143262953674043805121028581660274394493861460258597130188538332977679416970808454282017991307383835356188698891323239771333178860346825972405652914210954631134409600833327693593543421410732434281694454355747008933885889869077937880862749049074740126067215284910788706518425606114203333939656875871818894784079170292840540681948732880660003000926906333894065117345867196506856521542472349855590932301830372695420851264943795112040150205561483289746364835891125359307397506516272039186039783992620965800450343112765502550149168357851547665186618429181796721954012847077634388652598794182315250366936611355658686688939934516900009808518223359241944137277154786476218874224865037819222158865245588353031015122185374014406127446401298766736266831637852985756300017995390160761028057020573055543615912481389851812757348379419397130083208775789655825117981028241260930861007152057766814139170496584713321278626253968883276653358428036897577768739458725693447122759791961361097160265922640311146274535842798727318743122276126487545827596583971543880517021741131581309905790220398409615820785382645469996656013188425862658824568438227653902664968157149269346732859000330582545267782235066499139875211275390674091559851875853548905976806413521230016513322214240509217605309858575530246251875145909490471112222194075412324792050366838359937779806344187239056856471058353548936427916942194109609165854034767323294935701500110192365307711393371247166567444590592355257900093259599574780053937287600294098393324949090038950101
enc = 172254401616728337848224556256193294668254066768665624620573955921904663415844987360305683044269987528418379305124320147209588306619600641931717574384801086412717165043339754089854945269488039157031822759552038220243667748187712406870604130874288848961422658181035116276222087495309539815379227353704980160563111860011813283093207521575802100014408033039719223557618408913808906098293389776713037943338000210957134248117986210892735617670398002934139712508431588063592442750666131635721232279579114412057382482634199793027886476451072132799009262126068858578298283046601000880559403008084425323306037979617803443696059413247270929031458924282241105950888791411422687779723342754994324724737283365077742875322607687106058784350376580745162809296384205316865766883773721914203935128431492247985755204159286761485776182149007712492892483933270120585324692872062057327390303613634093538988078627329297217605056348331910353384255935457914956221810806802338940927281542361188610818936740209620052730118914762676848436107226923154169182628394200511074094416135594725057729803618271672713265182266181460723433237689954353512385555171399460870707449024037962690482864822971633650492835486036834553508571232609988066578567702464349018675580536990329927725573108328721614238899767792645665535623446031410358844459259283846182131541439033837736746980370117933542817231688533759434901524622912254499686908606070397662874360407075300248727974071742299708009048853008697832021516188431289704110567432234451743516365186915321744582268642673156685090283640357282428092579506635927396169516769103184205482482269342855874163597222301484981530193824960936155581252590505096646005478378577133665334258562017564658379524993172647857018916805201682065829122503078635804169426240558643597061660475712949155431727872200202869508621492240387907991955060578185917725771

It’s fairly simple to understand what’s happening, a random r with a bitlength of k+2 bits is chosen at random until both p and q are primes.
That polynomial pubkey seems daunting at first, but after some tries we see that pubkey = p**2 * q.

Now, we can define f(x)=x**6 + 5*x**5 + 10*x**4 + 13*x**3 + 10*x**2 + 5*x + 1. We know that f(r) = pubkey so we can define g(x) = f(x) - pubkey and now we have g(r) = 0.
In order to find r we need to find a root of g(x) which is fairly simple to do.
After we find r we can find p and q and n = p**2*q, at this point things start to get interesting.
NOTE1: I cheated and used sagemath but since g(x) is strictly increasing, r can be found using binary search.
NOTE2: this is RSA but instead of n = p * q we have n = p * p * q so it works mostly the same.

We know that m**n % n = enc. We can’t simply reverse this equation since gcd(n, phi) = p but we can do something that’ll be useful later. Since phi=p*(p-1)*(q-1) that means that
gcd(q, phi) = 1 and therefore we can calculate qinv = inverse(q,phi) so we’ll get enc**qinv % n = m**(p**2) % n.
Now, actually p and q are both very big and probably the message is smaller than both of them so we can change the modulo in our equation from n to q enc = m**(p**2) % q.
At this point you probably know how to get the flag, since q is prime phi = q-1 and that means that gcd(p**2,phi) = 1 so we can get our message. pinv = inverse(p**2,phi), m = enc**pinv % q.

The code:

pubkey = 3415775651990117231114868059991823731694168391465118261123541073986397702947056759501589697018682285283905893102019391953165129250445987511496328390478214156138550568081360884795196720007402795178414072586445084589188812271144227913976270609786532206307549154139514246177504313696905220271023590900584622193476455815728425827517096143262953674043805121028581660274394493861460258597130188538332977679416970808454282017991307383835356188698891323239771333178860346825972405652914210954631134409600833327693593543421410732434281694454355747008933885889869077937880862749049074740126067215284910788706518425606114203333939656875871818894784079170292840540681948732880660003000926906333894065117345867196506856521542472349855590932301830372695420851264943795112040150205561483289746364835891125359307397506516272039186039783992620965800450343112765502550149168357851547665186618429181796721954012847077634388652598794182315250366936611355658686688939934516900009808518223359241944137277154786476218874224865037819222158865245588353031015122185374014406127446401298766736266831637852985756300017995390160761028057020573055543615912481389851812757348379419397130083208775789655825117981028241260930861007152057766814139170496584713321278626253968883276653358428036897577768739458725693447122759791961361097160265922640311146274535842798727318743122276126487545827596583971543880517021741131581309905790220398409615820785382645469996656013188425862658824568438227653902664968157149269346732859000330582545267782235066499139875211275390674091559851875853548905976806413521230016513322214240509217605309858575530246251875145909490471112222194075412324792050366838359937779806344187239056856471058353548936427916942194109609165854034767323294935701500110192365307711393371247166567444590592355257900093259599574780053937287600294098393324949090038950101
enc = 172254401616728337848224556256193294668254066768665624620573955921904663415844987360305683044269987528418379305124320147209588306619600641931717574384801086412717165043339754089854945269488039157031822759552038220243667748187712406870604130874288848961422658181035116276222087495309539815379227353704980160563111860011813283093207521575802100014408033039719223557618408913808906098293389776713037943338000210957134248117986210892735617670398002934139712508431588063592442750666131635721232279579114412057382482634199793027886476451072132799009262126068858578298283046601000880559403008084425323306037979617803443696059413247270929031458924282241105950888791411422687779723342754994324724737283365077742875322607687106058784350376580745162809296384205316865766883773721914203935128431492247985755204159286761485776182149007712492892483933270120585324692872062057327390303613634093538988078627329297217605056348331910353384255935457914956221810806802338940927281542361188610818936740209620052730118914762676848436107226923154169182628394200511074094416135594725057729803618271672713265182266181460723433237689954353512385555171399460870707449024037962690482864822971633650492835486036834553508571232609988066578567702464349018675580536990329927725573108328721614238899767792645665535623446031410358844459259283846182131541439033837736746980370117933542817231688533759434901524622912254499686908606070397662874360407075300248727974071742299708009048853008697832021516188431289704110567432234451743516365186915321744582268642673156685090283640357282428092579506635927396169516769103184205482482269342855874163597222301484981530193824960936155581252590505096646005478378577133665334258562017564658379524993172647857018916805201682065829122503078635804169426240558643597061660475712949155431727872200202869508621492240387907991955060578185917725771

R.<x> =ZZ[]
poly=x**6 + 5*x**5 + 10*x**4 + 13*x**3 + 10*x**2 + 5*x + 1 - pubkey #x**6 + 5*x**5 + 10*x**4 + 13*x**3 + 10*x**2 + 5*x + 1==(p**2*q)

r=poly.roots()[0][0]

p=r**2+r+1
q=r**2+3*r+1
n=p*p*q
phi=p*(p-1)*(q-1)

qinv=inverse_mod(q,phi)
enc=pow(enc,qinv,n) #enc=m**(p**2) % (p**2*q), the exponent is not coprime with phi=p*(p-1)*(q-1) so we can't find a solution to the equation d*p**2 % n == 1 right now

enc=enc%q # since m is probably smaller than q we can get away with this
#now enc=m**(p**2) % q, the exponent is now coprime with phi=q-1 and we can find d such that d*p**2 % q = 1
pinv=inverse_mod(p*p,q-1)
enc=pow(enc,pinv,q) #enc=m

print hex(int(enc))[2:].strip('L').decode('hex') #print flag

The flag:

ASIS{Wo0W_Y0u_4r3_Mas73R_In__Schmidt-Samoa__}