## Hack.lu CTF 2021 - Silver Water Industries writeup
In the challenge we are provided with some GO source code which can be found [here](https://github.com/Dexter192/CTFs/blob/main/Hack.lu%20CTF%202021/Silver%20Water%20Industries/public/main.go). This code generates a random message and encrypts it using the [**Goldwasser-Micali-cryptosystem**](https://en.wikipedia.org/wiki/Goldwasser%E2%80%93Micali_cryptosystem). 
In the challenge, we are given the public key $(N,a)$, where $N=p\cdot q$ and $a=-1$. 
In order to decrypt the encoded message $(c_1, c_2, \dots, c_n$), we require the private key $(p,q)$. If we have the private key, we can decrypt $c_i$ by checking if $c_i$ is a [quadratic residue](https://en.wikipedia.org/wiki/Quadratic_residue) modulo N, i.e., if there exists an integer x such that: $x^2 \equiv c_i \text{ mod } N$
If $c_i$ is a quadratic residue, then we set bit $m_i = 1$. Otherwise, $m_i = 0$. Doing this for all bits gives us the original message $(m_1, m_2, \dots, m_n)$
We can check if $c_i$ is a quadratic residue by calculating $c_i^{(p-1)/2}\equiv 1\mod p$ and $c^{{(q-1)/2}}\equiv 1\mod q$. However, since $c_i$, $p$ and $q$ are all large integers, this will likely give us an overflow error. 
An alternative method to check if it is a $c_i$ is a quadratic residue is by calculating the [Jacobi symbol](https://en.wikipedia.org/wiki/Jacobi_symbol). The Jacobi symbol $\left({\frac{a}{p}}\right)$ is the product of [Legendre symbols](https://en.wikipedia.org/wiki/Legendre_symbol) for each prime factorization of $p$. The Legendre symbol is defined as follows: 
\begin{equation*}  \left(\frac{a}{p} \right) =    \begin{cases}      0 & \text{if } a \equiv 0 (\text{mod } p),\\      1 & \text{if } a \not\equiv 0 (\text{mod } p) \text{ and for some integer } x: a \equiv x^2 (\mod p) \\      -1 & \text{if } a \not\equiv 0 (\text{mod } p ) \text{ and there is no such x.}    \end{cases}       \end{equation*}
If the Jacobi symbol for an encrypted bit $c_i$ is 1, then we know that the decrypted bit $m_i$ is 0
If the Jacobi symbol for an encrypted bit $c_i$ is -1, then we know that the decrypted bit $m_i$ is 1
Using the Jacobi symbol, we can decrypt the message as follows:
```pythonimport pwnimport jsonfrom cypari import pari
# Connect to serverpwn.context.log_level = 'error'sh = pwn.remote('flu.xxx', 20060)
# Receive NN = int(sh.recvuntil(b'\n'))print("N: ", N)```
    N:  248717112594970753710635089015145389511 
```python# Compute the two primfactors using cyparifactors = pari.factor(N)p = int(factors[0][0])q = int(factors[0][1])print("Prime factors are p={} and q={}".format(p,q))```
    Prime factors are p=15410376348350331311 and q=16139587182865636201 
```python# Source for Jacobi code: https://asecuritysite.com/encryption/goldwasserdef jacobi(a, n):    if a == 0:        return 0    if a == 1:        return 1
    e = 0    a1 = a    while a1%2==0:        e += 1        a1 = a1 // 2    assert 2 ** e * a1 == a
    s = 0
    if e%2==0:        s = 1    elif n % 8 in {1, 7}:        s = 1    elif n % 8 in {3, 5}:        s = -1
    if n % 4 == 3 and a1 % 4 == 3:        s *= -1
    n1 = n % a1
    if a1 == 1:        return s    else:        return s * jacobi(n1, a1)```
```python# The jacobi symbol for one of the two factors will always be 0 (I think this is a bug and both should return the string)# To be safe, we compute both strings and throw away the empty onep_string = ""q_string = ""
# From the source code, we know that we expect a message of length 20for i in range(20):    p_list = []    q_list = []
    # Receive the token from the server and turn into a list of encoded bits    token = sh.recvuntil(b'\n').decode('utf-8')    print(token)    j_text = token.replace(' ', ',')    bit_enc_list = json.loads(j_text)
    # Compute the Jacobi symbol for each bit    for bit_enc in bit_enc_list:        # Encoded bit is 0 if jacobi(b, q) == 1 if it is -1, it is 0        # Basically this is checking if c**((p-1)/2) is congruent to 1 mod p (and c**((q-1)/2) is congruent to 1 mod q)        bit_p = 1 if jacobi(bit_enc, p) == -1 else 0        bit_q = 1 if jacobi(bit_enc, q) == -1 else 0
        p_list.append(bit_p)        q_list.append(bit_q)
    # Turn the bit array into an int    p_int = int("".join(str(i) for i in p_list),2)    q_int = int("".join(str(i) for i in q_list),2)
    # and the int into a char which we append to the string    p_string = p_string + chr(p_int)    q_string = q_string + chr(q_int)
# Throw away the empty string and send the decoded string to the serverif not p_string[0] == '\x00':    msg = p_string.format()else:    msg = q_string.format()```
    [181835648058226969047204292458197048971 231534013682053426000013393492090827562 175395200091718383235865187450520634973 187026641593733662800728641094554745232 1311176162996742335684091141517673178 35978590366067457923783237630294317865 19622110064869041551324077912385380466 69097982603657815927145776701210961248]     [176447136217570795208795948188472662683 142500897770388549087075010307353200612 60025693622084183068061047084482005407 139459374980649593967848783185904014065 76992016221494157894181605184881987214 229300290812478786160637728909804973305 12720039913878585734671251292928405964 13175100868269983032665969908191077269]     [51876868130017665707728890333312437355 64232958373112548719109254588545491941 25164545950282185541304313393675681595 173672098251074424977321551567763330488 191819361407623104815649981026352663318 225203508480309270970380096685459692304 194530637612334888219072618286866093906 160438425282124612893437501490903219473]     [221361640689365454847078156102648544200 59798894315425706113756525203092225358 30825394756403855224431355331500797261 63318770823673315407325581007473269176 174736562958547893658771706681166330637 179358010320242278239715126326805811670 239146595576374107015464238703714317880 143109177151219082450652048186705596430]     [207246780392944099568862906265794059305 166088595600896192806053345696847430800 42998838075436877788799134816795036066 55459003993344845519752887833050816875 156072269996163477763160852982740593829 118204558437044439290182375722582600191 57707079848578615098366542067761020465 42480068277946755737917468687562089477]     [201109961350066827274753173612616485124 244867643881266102025025319132258436729 161439534824512964082084980166521032272 32214312676572382397446778306474293364 244240291573172683468322973519752655585 113974902552485372049096925517217912749 93154934864203699741733208841954765710 14920949186771151979748650626558436317]     [232445197251942300430269379711609396845 48835621918253055938562618869218009988 184776980508286760976532917462257526021 231473270931986275898271611917854930553 62282218730545789368062732612581966322 181135409855915303755875613566941969885 192890169244481893779373754227616230865 172661174546490870287126975214680016898]     [200777503896716467417262008841492433041 214738774440594555114958904883392789186 42817523126028203587543320280142801650 184730040658215158963403722158998226306 40020941123544806758384339038391275280 141875783173371043653387593915946218103 118820389063466333681864927909382615864 93394364352318377599167951202175494982]     [68517889147031322070930436830872771235 165956728932490848132526281943903100303 248705498932808089869061362043934824943 95652684336603143872695026347537100609 244134777573811721344626388935094879599 23021463934292728452483794817888821600 59721302949785599476928605817926228231 138070855869673854816348693040710394645]     [95746917994354352989660750993699089579 237772694973590623832888611304407469899 117158324267624250460840465513497238716 97604811237558004114921911118711135230 202797693500087971489914298122349957440 7338522140106802982631417571822491307 119711018925300303298502615060594255814 17078442994855023919960981826727403603]     [122914248744165614485595191257808161213 244770325730184243095938231676553430448 246880723594336794666337784033598317687 22718177447561112981614824431571537499 221978775338903488708839561619904755867 108368547260837164748817580543892190411 144050050495943338750784421521675325783 233498745169267681921534785759573861985]     [7423187603932785914736430712860799213 5983257827453742633535287972973675141 3110844580913471478417414317355612993 13018252021059395856050742245138720776 24445318822149095855081042620563506041 44965087056119510758292057797748643179 45422745424441766737928244336932007114 58117998367645844587777679930523495720]     [19193522735252676512002661444858042996 18484651526385646995054274446089294026 133796129395558934584888509979251493860 70723353008624756680102417609888173364 47947661296005892205095412450477315739 52161807438684028819757453569558602473 148571768946882204306268197120596044951 157045052241685207466043057477443275632]     [36931288851446718958450351205319787934 166865448286561986427132087855563927791 103117529384246712317060942870930111112 124930541743146491972237154903989564501 2376078681219932997271116806883404382 182267517488488438120090884115274912346 95739731073708026364412037040955541776 136451686075180874956053731937903935261]     [87422165590848888761401798024568762267 241330770678914828499194195108512786530 207726209431417677313207082793387941479 106196609344797360186570990860071004601 18769405216049405812372176499408491640 41992364111844169551623564736296495937 242627479045452633204127019045283506444 216615812622747541510580689856374058896]     [226431168714947165923489732069728934596 104741407148443212084816282328978262766 2465030187338774281994573351626833582 25139189992946307815366088181099531605 229829338063274187590364022255392279200 212456138699592754933186251374915739492 93111645735842147412109329224064355400 87666496622905556650033481311896534376]     [116056200153491523086658076875740902111 239201576580013936325095260707258349531 16837974120758258572036752102415941732 121695237638909836007905737578424369399 137843149791809130598369821556675631169 91459401502588268295403429829959223809 11333597149407905741288913720735001173 155315911391843911295375691024880645721]     [137328431864424403694581663024462245896 20084833340254705829146803334650634438 232363419221591665949740513759741306979 204021351397001414956316826204544494058 193841871036125445205682801335006555563 20806571956923648848314942575656393291 5743930171993637971005407303034300971 51210263027186070980681395651432507964]     [215961843295102613410879327034481055560 16764012596577311824870724555234430650 200482698552111887478052745152295701470 9124302300355970102905041971826829925 51610558259092272453282278225192589006 182166939206936572190864455433216127353 227487330364513910554317876797548317526 171739504500151378641181788130784545154]     [85579765204004492593612898869941250371 51509534333930186319921538643219321667 12079383386123934011352511160843002243 208668117164424776131729451016669751789 166512864862257017761777174799458583464 116783278586414790734025230893853890183 231668977284192249270485684699425477243 152161022708874134332330470165822154911]  
```pythonprint('Decoded string: {}'.format(msg))sh.sendline(msg.encode('utf-8'))
# Receive empty line before our flagsh.recvuntil(b'\n')flag = sh.recvuntil(b'\n')print(flag.decode('utf-8'))```
    Decoded string: lMYiZv9T7pkdMrpUXr0U    flag{Oh_NO_aT_LEast_mY_AlGORithM_is_ExpanDiNg}  