simple signature - Crypto

Task

The s in rsa stands for secure.

nc betta.utctf.live 4374

Solution

We get only information about how to connect to the server. So let's connect to see how it works:

szczygielka@hacks$ nc betta.utctf.live 4374
Welcome to the signature generator!
This service generates signatures for nonnegative integer messages.
Today's RSA parameters are: 
n = 17007115661299815607779165325006475925060995570648249126487030335644203023481846638117502461440332111444430916767200503666795042264359564422897594202938598017705990008042877313795222435128369842652331645057052654864153662402967586505198149442619066069665399964917886690584407737138071046442779048899209367834725450164047862000686231313652343200922838123212694312780180541822058518287645925643501380574048457140971384357731590128868557198143735637246158985421310165371697896791564736610273577022563266299497980201341938025773037378412970953178288939570091648227422253383650988673431907753115858499383009001338523288087
e = 65537
Enter a message as an integer (enter 0 to stop): 2
Your signature is: 6672957953572898291912874637593697014101172364647215740830900911644569712185295765745418452963497463275123251748952403305001368745981830456197804415177494270001131898055965726185773582177908222725950920241045612464232492749961514337999947924777746096071879416722777928572833948616707226872981090448612762382663274986788162021813367382415915672886879690116171900002788502748187211138753302953634267728098740540801330595107303819427658290454721300644156991165726094646851144048881902055363646383706901609234926756120255588681727697911438036366466679519130986883486700046862967465455783444359689098389239391853331493149
Enter a message as an integer (enter 0 to stop): 3
Your signature is: 2489355093949788277772248629243069986608791937535601737135622933254496365765932518220438140785809898088376102226248195015617328688580982151381273120828016088777408113045970326379287582105630891959710381877864144955748352250386354887117900428266230023602707106952578855774464713335240514344219988834753712048133975681621557356736836815344888196103902767834383982656310862090337589073425432345749789501727668558023522752244962712971711970202489196742528339273279883755796908964160428004572278447515065391236485876470418430841869466382073943825117186740672592574369890018680015742556388573397785190613698745962915695490
Enter a message as an integer (enter 0 to stop): 0
Now, come up with your own pair!
Enter a message: 5
Enter a signature:

After connecting to the server we get the values of N and e, and we are asked to enter the message as an integer. Then we get the signed message. Entering the value 0 causes that we are asked to provide a message as an integer, and then we are asked to enter the signature for this message. However, we cannot provide a signature for a message whose signature we have already received. So we need to find a way to predict the signature for the message that we didn't enter.

Signing message

The signature $S_{A}(M)$ of person A for message M in RSA is calculated as:

$$S_{A}(M)= M^{d}\:mod\:N$$

where d is a private key.

There is an attack that allows us to generate a correctly signed message under specific conditions without knowing the private key. This attack is known as a chosen message attack.

Chosen message attack

Suppose that B can construct $M_{1}, M_{2}$ and $M_{3}$ such that:

$$M_{3}= (M_{1}\cdot M_{2})\; mod\;N$$

If person B has the valid signatures of person A for messages $M_{1}$and $M_{2}$ that is $S_{A}(M_{1})$ and $S_{A}(M_{2})$, person B can form the product $mod\:N$of these signatures to get a false signature of person A on $M_{3}$, calculated as:

$$S_{A}(M_{3})= (S_{A}(M_{1})\cdot S_{A}(M_{2}))\:mod\:N$$

Since we can generate any 2 messages and receive correct signatures for them in response, we can prepare a 3rd message based on$M_{1}$ and $M_{2}$, and next sign it correctly.

Short Python script that allows for generation $M_{3}$ and valid signature of $M_{3}$:

n = 25011673034491355565316119383841920834148304370881307440379076264654004805049935539684623253540027200665674334009750614247301820995420653267666135702728517171972692591578034047207113447607412521222207637194381676425723404453006738696656996305834264352741363806013095377309558390233925633086661446820547660187228510857757411433745366697901394073513967378474888272806125467239571346750264391538117096142959943329509385228941040707678025780127293556179511169437818318810493137994849280210577883018404945381646189053678845497399559788499813960593234643983604240680392498751650896335259978167581361543353291085945801937919
m1 = 2
m2 = 3
s1 = 167106183974649927361113931296077582265492701343102798431847356552623464281261807863692437431581051699160321062080369180102963562695604416177822216229167582349016930798188117679796198707927256487811538606251055262608707991744159056334196578800682593801190837698260753752651352969256348743396809319292526395834219971511983515389920852204266639411077654359658927267648112815871565887374562515164908764600863108078885963804401084070870066226027183542083548345921103253855581130856807562521054348284751972052267957547384116330848029772121607815255250108795354332832241391942741961058111269971543196377811471452813266462
s2 = 4363665339675942456071478174726888133970485985108562245206730559181146112476612378361424317213630265297661166946814004321173239919820863983516376853680755328848155422976956848324861966285189628411883804748456507928531574062311558513056164231132407430542389868895554970138260897940197402681489946817304360067819024869171021153636623496002916949536721299379606540110395767892889930557619776683083341133195440374444928292533379990581346827433973435312644200987043481984528186190656525130576457717793623365030319164203058326024601973627718632151798023814546570137557724279726179550485065988325862554797323417407638397110
m3 = (m1 * m2) % n 
s3 = (s1 * s2) % n
print(m3)
print()
print(s3)

After entering the generated values of $M_{3}$ an $S_{A}(M_{3})$, we get the flag:

szczygielka@hacks$ nc betta.utctf.live 4374
Welcome to the signature generator!
This service generates signatures for nonnegative integer messages.
Today's RSA parameters are: 
n = 25011673034491355565316119383841920834148304370881307440379076264654004805049935539684623253540027200665674334009750614247301820995420653267666135702728517171972692591578034047207113447607412521222207637194381676425723404453006738696656996305834264352741363806013095377309558390233925633086661446820547660187228510857757411433745366697901394073513967378474888272806125467239571346750264391538117096142959943329509385228941040707678025780127293556179511169437818318810493137994849280210577883018404945381646189053678845497399559788499813960593234643983604240680392498751650896335259978167581361543353291085945801937919
e = 65537
Enter a message as an integer (enter 0 to stop): 2
Your signature is: 167106183974649927361113931296077582265492701343102798431847356552623464281261807863692437431581051699160321062080369180102963562695604416177822216229167582349016930798188117679796198707927256487811538606251055262608707991744159056334196578800682593801190837698260753752651352969256348743396809319292526395834219971511983515389920852204266639411077654359658927267648112815871565887374562515164908764600863108078885963804401084070870066226027183542083548345921103253855581130856807562521054348284751972052267957547384116330848029772121607815255250108795354332832241391942741961058111269971543196377811471452813266462
Enter a message as an integer (enter 0 to stop): 3
Your signature is: 4363665339675942456071478174726888133970485985108562245206730559181146112476612378361424317213630265297661166946814004321173239919820863983516376853680755328848155422976956848324861966285189628411883804748456507928531574062311558513056164231132407430542389868895554970138260897940197402681489946817304360067819024869171021153636623496002916949536721299379606540110395767892889930557619776683083341133195440374444928292533379990581346827433973435312644200987043481984528186190656525130576457717793623365030319164203058326024601973627718632151798023814546570137557724279726179550485065988325862554797323417407638397110
Enter a message as an integer (enter 0 to stop): 0
Now, come up with your own pair!
Enter a message: 6
Enter a signature: 11142352730904392094907478673449530745514430706355768398344149977189165761866069690468216884219849826910699820241587633104399695643388547796079632875498199535303593394523326034081764342066330809429540936127311909816091767287533721495651588175683595107248938098951595561299337614385460842122954258065580972257002915462339699490635165977534955238475875367972993473785024370232150917624118251090998844928216968453119829661818637166811611071771767170438480436038313482681781047800080455414421430425941296672232813929113527116528978640602267837078421384790834943081134779726420694400638225588785220472712941438021313574815
Congrats! Here is the flag: utflag{a1m05t_t3xtb00k_3x3rc153}

Flag:

utflag{a1m05t_t3xtb00k_3x3rc153}