Sarah's Cryptosystem

Author: GabiTulba
Contest: TJCTF 2018

Problem statement:

I had a friend who published this public key cryptosystem as part of her science fair project, but I’m not sure it’s so secure…
Public Key
Ciphertext

My opinion:

This was a super fun to solve challenge, mostly because I didn’t know that such a cryptosystem(even if easily breakable) existed.

The challenge:

So, we were given some public key, and ciphertext of an unknown cryptosystem.
Googleing Sarah Cryptosystem we find a pretty interesting story about a woman named Sarah Flannery.
She developed in 1999 an algorithm called Cayley–Purser which caused quite a big fuss, sadly this algorithm was cryptographically insecure.
After understanding how the algorithm works I googled some more until I found a paper which explains the attack.

Getting the flag:

I implemented the attack in sagemath, I won’t explain it here since it’s explained in great detail in the paper above (I hope you’ll understand the math behind it).

import binascii
n=14678582949426387051583136040455803382111419934165976555967410717578108685173293909893707428060574534387147043662980233493070333867526564630646606195171973454732346210530445592981735448140608367433802310679262003264086048483330926831158965247002647763969506296491800206264566632210018217460947909473322948120728022781961264083482251077179808522571497366192225541800367737775624875274409378360680791167750022903325344080185661894498877429106792051549616294445505734756445036773060160075172879734624325424601794213946464848991659189822047433670420325360836239402912250660089868320598256013395839998681853749012528228581
R=IntegerModRing(n)
alpha=Matrix(R,[[8775523445886632877189593855724016105923853238110388600944519847143895931293223855922653616887818042631073479198110684379321723227593601822918289162810287213179985843203577275519823312297337476543699814699295603780534270489652026567901889418668978700166470523932709861086261372827841681274942513882086473642725585135101230370081888674776607714279827857691943339921005145456087934796083827529605415734994951876822070091633768569949775791638494032484021726668931928950677970506977610850040146356447929936780822436403930820545470690234566354431325668976387986291875340697228987789945329449200068296170375614076050879785,10914524698710595970321127027090232144165968780037471063432770955497704137163051702799686631313041237560141667848373235442103054608670912249269855896811394714345108278448088454633357108221934703236017373213591822419492870186573388565800341211631487277520861910315169726614530318669774452500398973789004100413146262726432287549267494369387541010183759368058060150046771812028618651061152940554853598757579002480497094323215709965636785996674504414081628163168221618141288158620642854534927045304055157302218392073869315722029506251754742712127700711498342611023211817174640260717060042688885087479683913557571909322741],[7157097076807988382820230716569936455045674994109312852250577929895736096519606523374055940413673063662855431457666708138113796135396777078373960733319810698100562529245781853196798527091875213512132913044623809323407761879224741043837559073372914528336917930561267239951428201709786511309170906978181350528532725746865810552547336005227276113230516321894984875520782802662233942788568094083797220677632043304323815963819260590985920987957137053105329635183018297003173809322151759301586528750262563904360082125151280110181914762714140881033279744601200352729150802483479611105828702510738590423345140053057578524340,6713517055261601175137199194349037776884391949750887153570211478360609355102967635024812020436930124099492062499378568948225812905028941236992161990751892519351796091752765093957342028716103643486587421078902623905472869718701549301991454011667516034361143511456327353811233114869084210135013109411719670903088224240407539506990465851216587326439231276390112484389076650763830466007812636524179883923113881730406583476993810068817032731764701328227580833401955012377095618568561222016759038286127435444274370666887116694944714906875307424805468192270291152231535013278536905457590268616934245276058674669841799113000]])
beta=Matrix(R,[[12810735484592687475611067000733910475407959255726938964445865510797360682518042234111788624482348253873675205750379533519653600377466554571549725126735899237320794286392351216351163142150947930793285681157153739873680235151717822189508483187266968937840184927172004631125869801171730273839416495272679596762491128032081715204511086070136862783519124351766930742835431179567064478518796272613388247961834821952570326773065235010566961759660603378159648515475855652044014147336517739031539091701655351031055956799114677224875340483094077563775106615052814649767904459580694503137691824535465579841465656799088385158184,5473642859795523867833744594642413120108472695987405903092128057784530587542920832212387191217752619328277772827610816009681072385077130472910935496153590538664127336809080066339982095054400770410661108644231317771694643744529400989304882179751725342517277312600577613299747065205530030840353840528208991751919855348274256156989437092383943692362355213688529247118405117679336493204906404070181358635721597885844629007865171487595667542012053680470870441869320997247103844383487375469966170305723116660050719640797029789529431834500103108427981321996630378373859429074160615524314703440598519278440916672490604153920],[13360817683734425907882869818387715917823570500779542648139881285594085839307884087170316732892285057644413961106686702548122776388566314151602576134967429938148568359628406913487102447957478975857422968377905367007255678006848155389204533214902608595212870988879519805436914172362269969647424235793945764717194382563938554317735619273113439313925766674058624269423418548409043902139520249198229905104623538910887468568657824562399052674509890480922031471957602349880575143764865589002518416822823718373354855636110399881258158604068094158661436001036363550606724638058264988946662672731808136009525669966413346830771,11468410759599236635289052912588911752422573812150145093904993075149484717580340039481523574675433246733347559877762204982600910077123361122258919844601069472735734932609308953048318256198076234640234139592390905314780413453276360192939595448983886080692089673968929164049655081883685358729758224963749521058341303254696491886950891802778644958745186969893311825203619560214820869460365078215849849124479129495345651512821938654650764639191895571807669232427640112077550730446976794444904863440462011108462395868920803221927297239615558407269413543933560885245839360611664257149625120359949226340501748237522041814167]])
gamma=Matrix(R,[[8974468230919934099206660576279424449497301852364989153036761168858007344533698037386796827211384328629017837524968363275804995875927577734686609421586684272633348191411693574979321023787212983912221475247860537390362046603629961287235797201556980167513141941168597299233052362222944059064374704020090477871823209626756840704609536921524143960339208893818545992537157471214137960274837610171236744600814714862928730197678579742105704214054822862593357666332950197265426170385072044723785511598793270720596355301285113545159975155209975455186823617585677822352197860436786511800833967339913846225776224546725792541520,9348474986948437407830611381930796417076181343543633204466467018618007961332994440548537170881111598282300398838403220784637434773325124478963236440587878188677991827315886822018947642220599876747471178815812118951916817010191177047705089048910549002617216646224139781669862185568251097552368622389943664551466943434989962245869206459898126080327957813064720085824151158276722547935648805466702908342289509228148396591724592467606473409258370670569095588764643480541155047718125969649815181530297399896574878462796500132797468732289756350942722963262157882852028757481193014591962402361412541547286212463585329356315],[6306347499602839310711897806816115365577798048588869401080589959551960579025882710953775758799196156090574498840338655413952106340930233167025430911291561146300436232756032168584609901161123027915957142144417373944831498112379530014743564725043850573029577893137274785944999828913842318958600038316305161651550987813123688899364506103198777508061052140024401991543826294645053810175935470329060181419638113822346335627126011428883634941577955928094830457687467602021018818112233819135752762796122449991940293951126794842445023346469946015215788444862522482934643865011428843298464296450568025153162421666513865829972,10460558892626942486591136156075757543686422206929425172766487988979302284782458711707743391644192252658479654211588038112081380743223452728011518065689480909606243379075821247336392033167618986362705759995101660106860761650744887913049696267564350252223724264010048527822196072691569796251914527187015010584106518547809025845913716411807489385594922654444064967642748725710272671436875870600558952201656006726706186246198382807891707075834051796788676605755301264887244933074977001813150376143934759392995053660467071628525606350521290098742782796859849651804582344638795615115444324738258958494327221705047139386067]])
mu_prime=Matrix(R,[[9110140425150750491145178173245810683649850676433167642203918443227873747929200498497484988659356796565844607239572829879322347251589944478091113697792108086550736898839464575439745480624731810294886238002427135623698710042800014612820928298917430445137640355738788165343967441826643874136160621009753218683651627226187219386196831000264065035194030979035604667050555295409076871639269434935429836264844914788522151184701643589729070919260048693228620818713776827956449530727987176756766935883945609304801285829253475548773757845833684396147327615752864245759762697131554282702952182820064236136029154931285534920336,3965680634933532371253173918575965512311075743978870329108827645259543845600676708465361739792712505100830375151369030591386585033111483748387572594721593780367638957423544648137126096616048548831526404791201118063342916940780558823392780847378257409456603871959593407713453397146511731920904022568991968961066446033963676957027561582191560877662951544766699653019054058615445793884586251692712331360647356139500007887786373834135022309564632684555593104495467262752494409415310095975103762605447355421569804147145717716270216276407829288807696993083792180120763011612628844075543633935302644043351200000415397765490],[11531027939277663954924629808580850615128112189088429194733892444735389287125194989846483062137239631428856897300952091045885111504233971340222047595797974590299676147530138095131682563465058026356505341896547427515760211337648937509712681168680093916223136691048129594400887163117578083595198924212238020929650571543544239651025512948151083606981283495326581076022774788713191375373448616247020080804624589709887909060660751012839089160151250018439586685425207828386848506215840120679779020276348065756876412067877471560174945643434266029362965328759176908923082695706418412446830824537449603065572349763237675405751,920729326437589730826095157469278350649316030890671041698866840091079079560109369898686162156986131867647612585803281076434525638323194196281197301522301314276691124338087536821687420513860352733995693071965887098334916285637808557203009371600993398395622919226813090045525901909117810003835895044704787089673163783368582595086734902024400720579716370279086180005814810492044173344668033992612757135892010975432640563801946449146558990089998260694779271111218515320264883756992522656100346966776474372573294784374889012500155152418754863716677395313380366718512341128264823401715112635658331018694834964614709946974]])
epsilon=Matrix(R,[[7165571226081578603835883150774616488728231051550287925851522690184895637139822876962972947112432251543801438173797575868444468354880336070457468476668646627601203589691836971847199834387550427409515139148865668672460930793878765006885214789102699287706918802228358033100073207658646769916917956918825343988728574869415991085833912621668186850044268946624373249357696907897355173351832256550108577060760939032564672939219868381918863800411991549406942127512322082415984088851421306484618925402688553375021971356743060341861158734723134788643394112904978199797407328350398837621015931420540971820281023718934332599845,5311927137961618089465719533669959680179138808868451304787316556962730054216658384560427124537238182468330318432740185730773011315312521714917801639551804882300325955312260236798444551041370383751633970374956257915677214485582117483657761988919505553702104281197415775417014673469569050740206878224979551841366120847702679675682180740324259166151472145699221113252321870669004434874193357913127321023174144885899598070482292843947693798831055666003932625354269654187369701819908413086086194211158098010905312163522905960656367473770480743567823177465080036681918250028808180971378615523862092243350157331116954510698],[5453403043375115387776266465045212861994650155363814552052041113915923817009277472100191728376696957972330437923466587434020093694118621324930290244063889644426827678183126312734629316012791372652267229717880892934548663470390609038951254084596015737291790063273550517220952776485662834693648438708321765082221299643494798339214081530177171662673636605795986063100859446521438876886565157432362462831922149860311355669958620420565847240178703164000319792911764660820039884624929685147146215415904174517092317941864314088161460161442692320572464940560312915345911620266153658276926959641065541429189055966572657819520,8323469275066655448490909899298437394080014136310987828663208635319609649256368613984492690212315915186764103523691677459103067777742206989452982676893533104930578345264505397629965506625890692620772096629332559013546209414474810863008128641233795446820695233160679181797421280038279121493037666374980800557085234506092778791238441904325008190674790187457682574952384888322563227452064207503676722597347894574663980629407710256847944722991203811304660432558564858911789500224117526382180259239886812006033221746547987173629026862386738990593399748341700938726003025625367055626519666645593341751948026564983517392940]])

lhs=beta-alpha.inverse()
rhs=alpha.inverse()*gamma-gamma*beta

d=lhs.solve_right(rhs)[0][0]
psi=d*matrix.identity(2)+gamma
lam=psi.inverse()*epsilon*psi
mu=lam*mu_prime*lam

out=''
for line in mu:
    for part in line:
        out+=binascii.unhexlify(hex(int(part))[2:].strip('L'))
print out

The program outputs:

The Cayley-Purser algorithm was a public-key cryptography algorithm published in early 1999 by 16-year-old Irishwoman Sarah Flannery, based on an unpublished work by Michael Purser, founder of Baltimore Technologies, a Dublin data security company. Flannery named it for mathematician Arthur Cayley. It has since been found to be flawed as a public-key algorithm, but was the subject of considerable media attention. Nice job! Your flag is tjctf{c0uld_th1s_b3_tH3_n3Xt_RS4?}

Flag: tjctf{c0uld_th1s_b3_tH3_n3Xt_RS4?}