Tags: jacobi cypari micali goldwasser quadratic-residue jacobi-symbol crypto goldwasser-micali legendre-symbol 

Rating:

## 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:

```python
import pwn
import json
from cypari import pari

# Connect to server
pwn.context.log_level = 'error'
sh = pwn.remote('flu.xxx', 20060)

# Receive N
N = int(sh.recvuntil(b'\n'))
print("N: ", N)
```

N: 248717112594970753710635089015145389511

```python
# Compute the two primfactors using cypari
factors = 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/goldwasser
def 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 one
p_string = ""
q_string = ""

# From the source code, we know that we expect a message of length 20
for 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 server
if 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]

```python
print('Decoded string: {}'.format(msg))
sh.sendline(msg.encode('utf-8'))

# Receive empty line before our flag
sh.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}


Original writeup (https://github.com/Dexter192/CTFs/blob/main/Hack.lu%20CTF%202021/Silver%20Water%20Industries/Silver%20Water%20Industries.ipynb).