## Crazy

### Challenge

>Look at you kids with your vintage music
>
>Comin' through satellites while cruisin'
>
>You're part of the past, but now you're the future
>
>Signals crossing can get confusing
>
>It's enough just to make you feel crazy, crazy, crazy
>
>Sometimes, it's enough just to make you feel crazy

```python
#!/usr/bin/python

from Crypto.Util.number import *
from flag import flag
from secret import *

def encrypt(msg, pubkey, xorkey):
h = len(bin(len(bin(pubkey)[2:]))[2:]) - 1 # dirty log :/
m = bytes_to_long(msg)
if len(bin(m)[2:]) % h != 0:
m = '0' * (h - len(bin(m)[2:]) % h) + bin(m)[2:]
else:
m = bin(m)[2:]
t = len(m) // h
M = [m[h*i:h*i+h] for i in range(t)]
r = random.randint(1, pubkey)
s_0 = pow(r, 2, pubkey)
C = []
for i in range(t):
s_i = pow(s_0, 2, pubkey)
k = bin(s_i)[2:][-h:]
c = bin(int(M[i], 2) ^ int(k, 2) & xorkey)[2:].zfill(h)
C.append(c)
s_0 = s_i
enc = int(''.join(C), 2)
return (enc, pow(s_i, 2, pubkey))

for keypair in KEYS:
pubkey, privkey, xorkey = keypair
enc = encrypt(flag, pubkey, xorkey)
msg = decrypt(enc, privkey, xorkey)
if msg == flag:
print pubkey, enc
```

### Solution

After solving Jazzy there's not much to this challenge. We know that it is an implementation of Blum-Goldwasser (albeit with an additional xorkey). Blum-Goldwasser's security relies on the hardness of factoring $n = p\cdot q$ and so our best chance to solve this puzzle is to find the factors of the pubkey.

Looking at the challenge, we see we are given many many instances of the encryption. With all of these public keys, wouldn't it be a shame if some of them shared a factor?

Putting the data into an array, I checked for common factors using `gcd` in the following way:

```python
def find_factors(data):
data_length = len(data)
for i in range(data_length):
p = data[i][0]
for j in range(i+1,data_length):
x = data[j][0]
if math.gcd(p,x) != 1:
print(f'i = {i}')
print(f'j = {j}')
print(f'p = {math.gcd(p,x)}')
return i, math.gcd(p,x)
```

Very quickly we get output:

```python
i = 0
j = 7
p = 114699564889863002119717546749303415014640174666510831598557661431094864991761656658454471662058404464073476167628817149960697375037558130201947795111687982132434309682025253703831106682712999472078751154844115223133651609962643428282001182462505433609132703623568072665114357116233526985586944694577610098899
```

and so with this, the whole encryption scheme is broken (ignoring the xorkey step of course).

With the factors of the pubkey, we can follow the dycryption algorithm on [Wikipedia](https://en.wikipedia.org/wiki/Blum–Goldwasser_cryptosystem#Decryption) to get

```python
def xgcd(a, b):
"""return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
x0, x1, y0, y1 = 0, 1, 1, 0
while a != 0:
(q, a), b = divmod(b, a), a
y0, y1 = y1, y0 - q * y1
x0, x1 = x1, x0 - q * x1
return b, x0, y0

def decrypt(c, pubkey, p, q, s):
h = len(bin(len(bin(pubkey)[2:]))[2:]) - 1 # dirty log :/
if len(bin(c)[2:]) % h != 0:
c = '0' * (h - len(bin(c)[2:]) % h) + bin(c)[2:]
else:
c = bin(c)[2:]
t = len(c) // h

# Recover s0
dp = (((p + 1) // 4)**(t + 1)) % (p - 1)
dq = (((q + 1) // 4)**(t + 1)) % (q - 1)
up = pow(s, dp, p)
uq = pow(s, dq, q)
_, rp, rq = xgcd(p,q)
s_0 = (uq * rp * p + up * rq * q ) % pubkey

C = [c[h*i:h*i+h] for i in range(t)]
M = []
for i in range(t):
s_i = pow(s_0, 2, pubkey)
k = bin(s_i)[2:][-h:]
m = bin(int(C[i], 2) ^ int(k, 2))[2:].zfill(h)
M.append(m)
s_0 = s_i

msg = long_to_bytes(int(''.join(M),2))
return msg
```

With the crypto system all sorted out and checked against the encryption function (without the xorkey) we just need to find a way to do this last step. I started trying to think of a clever way to undo the xor with knowledge of several ct / msg pairs (many of the public keys share common factors) but then i realised that the block size is only 10 bits long and a brute force of `xorkey` would only mean guessing 1024 values.

So, i took the easy way and included a loop inside my decrypt trying all values for the `xorkey` and storing any decryptions that had the flag format: `ASIS{`. The script takes seconds and finds the flag.

### Implementation

```python
from Crypto.Util.number import *
import math

def find_factors(data):
data_length = len(data)
for i in range(data_length):
p = data[i][0]
for j in range(i+1,data_length):
x = data[j][0]
if math.gcd(p,x) != 1:
return i, math.gcd(p,x)

def encrypt(msg, pubkey, xorkey):
h = len(bin(len(bin(pubkey)[2:]))[2:]) - 1 # dirty log :/
m = bytes_to_long(msg)
if len(bin(m)[2:]) % h != 0:
m = '0' * (h - len(bin(m)[2:]) % h) + bin(m)[2:]
else:
m = bin(m)[2:]
t = len(m) // h
M = [m[h*i:h*i+h] for i in range(t)]
r = random.randint(1, pubkey)
s_0 = pow(r, 2, pubkey)
C = []
for i in range(t):
s_i = pow(s_0, 2, pubkey)
k = bin(s_i)[2:][-h:]
c = bin(int(M[i], 2) ^ int(k, 2) & xorkey)[2:].zfill(h)
C.append(c)
s_0 = s_i
enc = int(''.join(C), 2)
return (enc, pow(s_i, 2, pubkey))

def xgcd(a, b):
"""return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
x0, x1, y0, y1 = 0, 1, 1, 0
while a != 0:
(q, a), b = divmod(b, a), a
y0, y1 = y1, y0 - q * y1
x0, x1 = x1, x0 - q * x1
return b, x0, y0

def decrypt(c, pubkey, p, q, s):
# Idiot checks
assert p*q == pubkey
assert isPrime(p) and isPrime(q)

h = len(bin(len(bin(pubkey)[2:]))[2:]) - 1 # dirty log :/
if len(bin(c)[2:]) % h != 0:
c = '0' * (h - len(bin(c)[2:]) % h) + bin(c)[2:]
else:
c = bin(c)[2:]
t = len(c) // h

# Recover s0
dp = (((p + 1) // 4)**(t + 1)) % (p - 1)
dq = (((q + 1) // 4)**(t + 1)) % (q - 1)
up = pow(s, dp, p)
uq = pow(s, dq, q)
_, rp, rq = xgcd(p,q)
s0 = (uq * rp * p + up * rq * q ) % pubkey

C = [c[h*i:h*i+h] for i in range(t)]

# Brute xorkey (max size: 2**10 - 1)
flags = []
for X in range(1024):
# Restore value for brute, and empty M
s_0 = s0
M = []

for i in range(t):
s_i = pow(s_0, 2, pubkey)
k = bin(s_i)[2:][-h:]
m = bin(int(C[i], 2) ^ int(k, 2) & X)[2:].zfill(h)
M.append(m)
s_0 = s_i

fl = long_to_bytes(int(''.join(M),2))
try:
flag = fl.decode()
if "ASIS{" in flag:
flags.append(flag)
except:
pass
return flags

# data from challenge.txt, truncated to only two values save space
data = [[12097881278174698631026228331130314850080947749821686944446636213641310652138488716240453597129801720504043924252478136044035819232933933717808745477909546176235871786148513645805314150829468800301698799525780070273753857243854268554322340900904051857831398492096742127894417784386491191471947863787022245824307084379225579368393254254088207494229400873467930160606087032014972366802086915193167585867760542665623158008113534159892785943512727008525032377162641992852773743617023163398493300810949683112862817889094615912113456275357250831609021007534115476194023075806921879501827098755262073621876526524581992383113, (238917053353586684315740899995117428310480789049456179039998548040503724437945996038505262855730406127564439624355248861040378761737917431951065125651177801663731449217955736133484999926924447066163260418501214626962823479203542542670429310307929651996028669399692119495087327652345, 2361624084930103837444679853087134813420441002241341446622609644025375866099233019653831282014136118204068405467230446591931324445417288447017795525046075282581037551835081365996994851977871855718435321568545719382569106432442084085157579504951352401314610314893848177952589894962335072249886688614676995039846245628481594015356555808852415257590789843672862086889766599032421071154614466932749223855909572291554620301269793104658552481172052104139007105875898227773975867750358642521359331140861015951930087364330158718293540721277710068251667789725792771210694545702423605041261814818477350926741922865054617709373)],[11618071445988286159614546200227554667389205281749443004629117264129957740203770615641847148204810865669191685874152730267573467338950993270113782537765608776375192263405546036787453939829561684834308717115775768421300006618296897365279937358126799904528083922552306565620644818855350306352024366076974759484150214528610355358152789696678410732699598714566977211903625075198935310947340456263339204820065134900427056843183640181066232714511087292771420839344635982165997540089604798288048766074061479118366637656581936395586923631199316711697776366024769039316868119838263452674798226118946060593631451490164411150841, (108436642448932709219121968294434475477600203743366957190466733100162456074942118592019300422638950272524217814290069806411298263273760197756252555274382639125596214182186934977255300451278487595744525177460939465622410473654789382565188319818335934171653755811872501026071194087051, 10240139028494174526454562399217609608280817984150287983207668274231906642607868694849967043415262875107269045985517134901896201464915880088854955991401353416951487254838341232922059441309704096261457984093029892511268213868493162068362288179130193503313930139616441614927005917140608739837772400963531761014330142192223670723732255263011157267423056439150678533763741625000032136535639171133174846473584929951274026212224887370702861958817381113058491861009468609746592170191042660753210307932264867242863839876056977399186229782377108228334204340285592604094505980554432810891123635608989340677684302928462277247999)]]

i, p = find_factors(data)
n = data[i][0]
c, s = data[i][1]
q = n // p

print(decrypt(c, n, p, q, s))
```

#### Flag

`ASIS{1N_h0nOr_oF__Lenore__C4r0l_Blum}`

Original writeup (https://jack4818.github.io/ASIS-Quals-2020/#crazy).