plaidctf 2019 R u SAd? Writeup

There are 3 files - rusad.py, key.sad.pub, flag.enc.

Yes, it is RSA problem. But decrypting process with using key is not common.
iPmQ means p^-1 mod q, and also iQmP means q^-1 mod P in below code.

def encrypt(key, data):
    data = bytes2num(pad(data, key.bits))
    assert 0 <= data and data < key.N
    data = pow(data, key.E, key.N)
    return num2bytes(data, key.bits // 8)

def decrypt(key, data):
    assert key.ispriv() and len(data) * 8 == key.bits
    data = bytes2num(data)
    assert 0 <= data and data < key.N
    v1 = pow(data, key.DmP1, key.P)
    v2 = pow(data, key.DmQ1, key.Q)
    data = (v2 * key.P * key.iPmQ + v1 * key.Q * key.iQmP) % key.N
    return unpad(num2bytes(data, key.bits // 8))

key.sad.pub has N(p*q), iPmQ, iQmP as public key. iPmQ is modular inverse of p, and iPmQ is also. These value is used by RSA-CRT cryptosystem. But in generally, either iPmQ or iQmP is used only, not both. So I thought I should make some formula with these value.

By chinese remainder algorithm, I could use ap+bq=1 formula(p, q are prime). I thought it could transformed as p*iPmQ + q*iQmP == 1, but it’s wrong because modular value is different.

So I transform iQmP and iPmQ as:

iQmP ==> kp + iQmP (for any k)
iPmQ ==> lq + iPmQ (for any l)

And I could make formular to

(kp + iQmP) q + (lq + iPmQ) p = 1
=> kpq + iQmP*q + lpq + iPmQ*p = 1
=> (k+l) pq + iQmP*q + iPmQ*p = 1
=> kpq + iQmP*q + iPmQ*p = 1 (because k, l is any value)

In addition, I could infer that iQmP < p and iPmQ < q as it is divided by modular, so it means iQmP*q + iPmQ*p < 2*p*q. Therefore, I found the k value in above code.

kpq + iQmP*q + iPmQ*p = 1
=> iQmP*q + iPmQ*p = 1-kpq < 2pq
=> 1-kpq < 2pq

So, k value has to be -1.

iQmP*q + iPmQ*p - pq - 1 = 0

On this formula I wrote sage code like below.

#rusad.sage

k, p, q = var('k p q')
iPmQ = 8576238992571591869339367870140218994273542282194520701664348646682391448576106630680498284621212787593356209740914901168733090823371040699948878786651462518529144026837660123406693635154217830755339457596520608787502271941986487262771708521404416352019507024705430920736421058347439358995939039953228936764295191673752730499288133458713995709946983920103441131785342297881050343614665686721597353967276809964115302170170393367543710777834619256462467499921754735442721965580336508363159554886933283178151617020551042141999581756444339357087838568279392954356241659416168338179236507816144395812356271365879641284797
iQmP = 20800474461367145273340906691597634098910584848634101425530321090829125122241687879745601849248837998876151999592885721935152548674120399809317994565118852444189251158193986225229214950841679795627758099753351375856214350384902504565070917605339475722050666023289412703507879513606009743774089452299903006910942117062241868053983949068811202383614893148995089157210610010137350618698066200655682358324076086051635412942424101514341843621257447734742388939312643974507540634350698445829827074747244048131430269996635105948318032075354212694854013936053043646732168771012778244153439821689497012763977957502463601486569


eq1 = p*q == 791624863672362607956099356831131364853604534581539305910340202530608819116145635786172280242888006099238658415878726648609085639898441498221890676242989932156153803416798752313174803590881722743224684700892225118961219497620039594839395302098710398557509455737717045746236278723783082574166076253616722351864293093113312339303779100928501715558725523086900830443711904148216534555379563587752574783766585298405162299420015348154910428560999297372318489063379606963196610310541923400713582218574580476129076391874763972417104970428247552426095493102113265356930843209220678746513622763556047230507409813826323653127519641722507761180370551715894779123757799654191386575031709371023058585245770842026072807521354840681453389934373985631297088292594571458141054189461792135505184038113247878020462609475899896639165065556193530858093783580972030229157998906679657691476969608156903485234277862405304786019418734022240703148376923711471550495919780707697498176112050789516280686586774453361477128822533764461655099250507644377378432909816994714226859830198325441550849414355111311567891047645058209193718307670504917114431127025248430544656281369344135327825272092527266146813922316680837029133898187541256581486770086898004104721349717
eq2 = ((-(p*q) + (iPmQ*q) + (iQmP*p) -1) == 0)

print solve([eq1, eq2], [p,q], solution_dict=True)

result is,

{
    q: 31659077809885706699482361830477717572837081779677626435829903374921581240849180063108552019274021826092781287218568613206006085334956822705610578514426596962412655157776833178744403034727698399320215892200440936975683502329350531806920697009386909154114556681774784614085691096050135180228131842452179315216957730905902673882170120973148157907231188547167482558383495097819905373068326760590890291412820411304614611983343203819383860434964843931325658872603238498210722446318497674396725811567139923114789843056157733621133155720503541819498078610854651245426825738313809229403279974283490718799392611854934535622307, 
    p: 25004672227855409995386175663336188685177638541286666056441830847618100808198668167307814236224429885295241140194633625051478252429462828073782848889819460674774292004752724556602147320684206242726073358822655212944688523823150236245522627662371134165404316388528738697090763677910441487876514668914442018764569771021916503649822836288868439220382922721194436569302106969570041514638164319835688101248578648742016186666021527781591528560611986692317045407081396778512783312692838307769559661780971287324753785154074832628454871505400166651610503632212720604214996108967812794633118832616768643612648168060802523582631
},

{
    q: 520109046090362775629610027508648543610880481327214156083260872847877417393441565683016617535106465694168358894153603203536214525110996125189862959516460388119668892877175619885884979444950120869500317296189648346750160265581209395097951444893937497168534211352899143285840662380827706981561134233245736072583741314895323719975337432588951973687101374994745578265908230087673684785779341604159091792088082461228443746295471493269521333478740566687647040942534225161981640134192517170306253613126872633375566148339987499151267873846521740018474878222628478926505038188128053555992497724294027947053526704216229240254651658797472028616144828882894409685731283307360133245360551816165187749766502527726922586934841483715445334530016940384091920488504396154461398969543533164004448301376884648447046667486310691858919464310877795916922233577138938038326202118684687681942550221893986759242054250402385463405063678531094351059745475153935718439280381765885021729240291130469974066015136739572028944889651127903979200500435316941572979715964745327174201670855494815734152965218525348557999925633420049545626146306913180914921964137054567129532584595255855147578565704954413247493788718470805158260223397224523169521381499259816411308183039/8576238992571591869339367870140218994273542282194520701664348646682391448576106630680498284621212787593356209740914901168733090823371040699948878786651462518529144026837660123406693635154217830755339457596520608787502271941986487262771708521404416352019507024705430920736421058347439358995939039953228936764295191673752730499288133458713995709946983920103441131785342297881050343614665686721597353967276809964115302170170393367543710777834619256462467499921754735442721965580336508363159554886933283178151617020551042141999581756444339357087838568279392954356241659416168338179236507816144395812356271365879641284797, 
    p: 271515817581999832326489329322482821242724053254325149827079329682731401722704070103155662707781540405070299521725123445072871114787445373032027716726529544036484910539623132427289824145931601873724367404702576772211059232038830199741443857204772901388975244384817902460395616342955375592604942020370986279280551778217988619328441668339549741871624148092155252177803674060542849769600221983593482991678502837176718553124543854885389095082258730684671448120845381801214970176349406230407328605447707842753510243534776473265837096581725812407620614879484786430425805021092625190521125039262019283453883109610094412872867982925035732564225722833000369438026516346831253329671157554857870835479268314299150220586513356966008055404357045247205167804090175303679655219918258971500735736736363229573415941989589204780245601245315734941171550003833092190831796787994970009534419386262916725992223612002919322614355055491146352088631448557535832056639398941812476446871759659046306620571637713789448183932882636557675898750072327435805453193852249387052658159342830625816696449136585963009891122011638159648092161363591736199509162888193863415123696774088280180246706387572852899320133598210031870873674790316733411965388587638187693413166679/20800474461367145273340906691597634098910584848634101425530321090829125122241687879745601849248837998876151999592885721935152548674120399809317994565118852444189251158193986225229214950841679795627758099753351375856214350384902504565070917605339475722050666023289412703507879513606009743774089452299903006910942117062241868053983949068811202383614893148995089157210610010137350618698066200655682358324076086051635412942424101514341843621257447734742388939312643974507540634350698445829827074747244048131430269996635105948318032075354212694854013936053043646732168771012778244153439821689497012763977957502463601486569
}

Great! So I edited rusad.py with value of p and q, and I got the flag.

#rusad.py

...
def genkey(bits):
    assert bits % 2 == 0
    while True:
        p = 25004672227855409995386175663336188685177638541286666056441830847618100808198668167307814236224429885295241140194633625051478252429462828073782848889819460674774292004752724556602147320684206242726073358822655212944688523823150236245522627662371134165404316388528738697090763677910441487876514668914442018764569771021916503649822836288868439220382922721194436569302106969570041514638164319835688101248578648742016186666021527781591528560611986692317045407081396778512783312692838307769559661780971287324753785154074832628454871505400166651610503632212720604214996108967812794633118832616768643612648168060802523582631
        q = 31659077809885706699482361830477717572837081779677626435829903374921581240849180063108552019274021826092781287218568613206006085334956822705610578514426596962412655157776833178744403034727698399320215892200440936975683502329350531806920697009386909154114556681774784614085691096050135180228131842452179315216957730905902673882170120973148157907231188547167482558383495097819905373068326760590890291412820411304614611983343203819383860434964843931325658872603238498210722446318497674396725811567139923114789843056157733621133155720503541819498078610854651245426825738313809229403279974283490718799392611854934535622307
        e = 65537
        d, _, g = egcd(e, (p-1) * (q-1))
        if g != 1: continue
        iQmP, iPmQ, _ = egcd(q, p)
        return Key(
            N=p*q, P=p, Q=q, E=e, D=d%((p-1)*(q-1)), DmP1=d%(p-1), DmQ1=d%(q-1),
            iQmP=iQmP%p, iPmQ=iPmQ%q, bits=bits,
        )

cheese@ubuntu:~/plaid# python3.7 rusad.py keygen --priv _testpriv --pub _testpub
cheese@ubuntu:~/plaid# python3.7 rusad.py decrypt -i flag.enc -o flag -k _testpriv
cheese@ubuntu:~/plaid# ls
flag      key.sad.pub  rusad_ece608061c4dd2d74b6011a5c7a7f83d.zip  rusad.py  _testpriv
flag.enc  _testpub
cheese@ubuntu:~/plaid# cat flag
PCTF{Rub_your_hands_palm_to_palm_vigorously_for_at_least_20_seconds_to_remove_any_private_information}

The flag is PCTF{Rub_your_hands_palm_to_palm_vigorously_for_at_least_20_seconds_to_remove_any_private_information}