## 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 flagfrom 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:
```pythondef 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:
```pythoni = 0 j = 7p = 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
```pythondef 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
```pythonfrom 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 spacedata = [[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}`