# 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}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://szczygielka.gitbook.io/writeups/ctfs-writeups/utctf-2024/simple-signature-crypto.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.