In Dead Drop 1 and Dead Drop 2, the flag is encrypted using similar encryption method:```#!/usr/bin/python
from Crypto.Util.number import *import randomfrom flag import flag
p = 22883778425835100065427559392880895775739
flag_b = bin(bytes_to_long(flag))[2:]l = len(flag_b)
enc = []for _ in range(l):	a = [random.randint(1, p - 1) for _ in range(l)]	a_s = 1	for i in range(l):		a_s = a_s * a[i] ** int(flag_b[i]) % p	enc.append([a, a_s])
f = open('flag.enc', 'w')f.write(str(p) + '\n' + str(enc))f.close()```
Brief explanation:- Flag is converted to binary- A random array is generated with the same length `l`as the flag bits- The product (modulo `p`) of all array element corresponding to bit 1 of the flag is calculated- This calculation is repeated `l` times- We are given the arrays and the products, with those we have to find a way to recover the flag
The fact that this challenge has a sequel means that there are at least 2 ways to solve it, however only 1 of them is able to solve the sequel. The other [writeup by team "from Sousse, with love"](https://ctftime.org/writeup/22123) describes the method that can solve both, but it is quite complicated. The method described in this writeup is a lot easier to understand for most people (however it cannot solve Dead Drop 2).
The encryption can be broken in 3 steps:- Exploit the properties of modulo multiplication to recover the flag bits- Use regex word search to guess the flag- Brute force the missing bits to recover the final flag
## 1. Exploit the properties of modulo multiplication to recover the flag bits
Properties of multiplication:- If `a_s` is not divisible by `d`, none of its factor should not be divisible by `d`- If `a_s` is divisible by a prime divisor `d`, at least one of its factor must be divisible by `d`The above properties hold true for multiplication modulo `p` if `d` is a divisor of `p`.
Exploiting those properties, the 0 and 1 bits can be recovered as follow:- If `a_s` is not divisible by `d`, and `a[i]` is divisible by `d`, that means `a[i]` is not included in the multiplication (`flag_b[i] = 0`)- If `a_s` is divisible by `d`, and `a[i]` is the only element divisible by `d`, that means `a[i]` is included in the multiplication (`flag_b[i] = 1`)
We also know that the flag format is `ASIS{XXXXXXXX}`, in which only alphanumeric and underscore `_` are used. With this knowledge combined we can recover 2/3 of the flag bits.
Program 1:
```#!/usr/bin/python
from Crypto.Util.number import *import binascii
p = 19*113*2657*6823*587934254364063975369377416367div_list = [19, 113, 2657, 6823, 587934254364063975369377416367]
# flag_enc.enc contains the encrypted data (p removed)enc = open('flag_enc.enc', "rb").read().decode().replace('L', '')enc = eval(enc)
l = len(enc)print('Length:', l)
def has_divisor(n):        return any([n % i == 0 for i in div_list])
def make_elem(c):        if c == '0':                return -100        elif c == '1':                return 100        else:                return 0
def make_array(s):        return [make_elem(c) for c in s if c != ' ']
def back2bit(n):        if n > 0:                return '1'        elif n < 0:                return '0'        else:                return '?'
def recover_0bits(i):        a, a_s = enc[i]        for d in div_list:                if a_s % d != 0:                        for j in range(l):                                if a[j] % d == 0:                                        flag_b[j] = -100
def recover_1bits(i):        a, a_s = enc[i]        for d in div_list:                if a_s % d == 0:                        found = False                        for j in range(l):                                if a[j] % d == 0 and flag_b[j] == 100:                                        found = True                        if found:                                continue                        count = 0                        for j in range(l):                                if a[j] % d == 0 and flag_b[j] >= 0:                                        count += 1                        for j in range(l):                                if a[j] % d == 0 and flag_b[j] >= 0:                                        if count == 1:                                                flag_b[j] = 100
def substitute_binary(bin_str, n, ln):        bin_n = bin(n)[2:].zfill(ln)        c = 0        new_str = ''        for s in bin_str:                if s == '?':                        new_str += bin_n[c]                        c += 1                else:                        new_str += s        return new_str
def text_from_bits(bits, encoding='utf-8', errors='surrogatepass'):        n = int(bits, 2)        return long_to_bytes(n).decode(encoding, errors)
ALPHA = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{_}'def printable(s):        return len([x for x in s if x not in ALPHA]) == 0
def brute_binary(bin_str, prefix = '', substr=''):        bin_str = bin_str.replace(' ', '')        ln = bin_str.count('?')        res = []        for i in range(1 << ln):                nbs = substitute_binary(bin_str, i, ln)                nbst = text_from_bits(nbs)                if printable(nbst) and substr in nbst:                        res.append(nbst)                        #print(nbs, prefix + nbst)        return res
''' MAIN SOLVING CODE '''flag_b = make_array('1000001 01010011 01001001 01010011 01111011') + [0] * (l - 47) + make_array('01111101')
for i in range(7, l, 8):        flag_b[i] = -100
for i in range(l):        recover_0bits(i)for x in range(10):        for i in range(l):                recover_1bits(i) 
flag_b = [back2bit(x) for x in flag_b]flag_b = '0' + ''.join(flag_b)print(flag_b)
for i in range(0, l + 1, 8):        c = flag_b[i:i + 8]        c = ''.join(brute_binary(c))        print(i >> 3, c)```
Ouput:
```1000001010100110100100101010011011110110??10?010??1????0?????010?0??1110????1??0?1???010??0?0??0??1?0?10101???10??011??0?1???0101?01??00?11010001???0010?1??1?00??000010?1??0?00?101?010??????101?0??100110?10?00??00??01?1????0?????0?0?10?00?01?011?0011??10100110??00??1?01?01????110????0??0?0?0?010?1????1010??0010?1???110??0?0?100?10?000???11100011?101011111010 A1 S2 I3 S4 {5 15QUqu6 0123456789PQRSTUVWXYZ_pqrstuvwxyz{}7 159AEIMQUYaeimquy}8 GOW_9 4567DEFGLMNOTUVW_defglmnotuvw}10 159aeimquy}11 ABCHIJKabchijk12 139QSYqsy{13 QSUWY_14 LMNOlmno15 159aeimquy}16 HJLNhjln17 4t18 AIQYaiqy19 46dflntv20 Aa21 028bhjprxz22 im23 13579ACEGIKMOQSUWY_acegikmoqsuwy{}24 BFJNbfjn25 delm26 012327 PQRSTUVWXYZ_pqrstuvwxyz{}28 014589ADEHILMPQTUXYadehilmpqtuxy}29 ahi30 LNln31 emu}32 024633 23RSZrsz{34 CGKOSW_cgkosw{35 012389ABCHIJKPQRSXYZabchijkpqrsxyz{36 AEQU37 13579acegikmoqsuwy{}38 AIQY39 37cgkosw{40 ACIKacik41 0442 Nn43 544 }```
## 2. Use regex word search to guess the flag
We know that the text inside the flag consists of multiple meaningful words written in mixed case 13375p34k, seperated by underscore. Possibilities for underscores are at index 6, 8, 9, 13, 23, 27, 34, so we have 5-7 words.
The first words are short so let's try backwards.
Last word:```35 012389ABCHIJKPQRSXYZabchijkpqrsxyz{36 AEQU37 13579acegikmoqsuwy{}38 AIQY39 37cgkosw{40 ACIKacik41 0442 Nn43 5```
Regex: `[olebgabchijkpqrsxyz][aequ][lstacegikmoqsuwy][aiqy][etcgkosw][acik][oa]ns` => [dcode.fr](https://www.dcode.fr/word-search-regexp) gives us 6 options, of which `equations` seems the most suitable.
```28 014589ADEHILMPQTUXYadehilmpqtuxy}29 ahi30 LNln31 emu}32 024633 23RSZrsz{```
Regex: `[osbgadehilmpqtuxy][ahi][ln][emu][oab][ersz]` => [dcode.fr](https://www.dcode.fr/word-search-regexp) gives us 5 options, of which `linear` seems the most suitable.
The middle word is a bit tricky, position 23 is not underscore:```14 LMNOlmno15 159quy}16 hjln17 4t18 AIQYaiqy19 46dflntv20 Aa21 028bhjprxz22 im23 13579ACEGIKMOQSUWY_acegikmoqsuwy{}24 BFJNbfjn25 delm26 0123```
Regex: `[lmno][lisgquy][hjln][at][aiqy][abdflntv][a][obhjprxz][im][liestgacegikmoqsuwy][bfjn][delm][oile]` => [dcode.fr](https://www.dcode.fr/word-search-regexp) gives us `multivariable`.
With these 3 words decrypted, we substitute them back to narrow down the possibilities for the first 2 words:
```flag_b = make_array('1000001010100110100100101010011011110110??10?010??1????0?????010?0??1110????1??0?1???010??0?0??0??1?0?1 01011111 01?01101 01110101 01?01100 01110100 01?01001 01110110 01?00001 01110010 01101001 01?00001 01?00010 01101100 00110011 01011111 01?01100 01101001 01?01110 01100101 00110100 01?10010 01011111 00110011 01010001 01110101 01000001 00110111 01?01001 00110000 01?01110 00110101 01111101')```
Output:
```5 15QUqu6 4567tuvw}7 159AEIMQUYaeimquy}8 GOW_9 4567DEFGLMNOTUVW_defglmnotuvw}10 159aeimquy}11 ABCHIJKabchijk12 139QSYqsy{```
Now there are over one hundred possibilitites, of which `its_like` make the most sense (remember tripolar flag also starts with `its`).
The flag we recovered so far: `ASIS{its_like_multivariable_linear_equations}` (the words need to be replaced with the correct combination of lowercase/uppercase and digits).
## 3. Brute force the missing bits to recover the final flag
With only 13 bits missing, we can bruteforce them to recover the final flag:
```#!/usr/bin/python
from Crypto.Util.number import *import binascii
p = 19*113*2657*6823*587934254364063975369377416367div_list = [19, 113, 2657, 6823, 587934254364063975369377416367]
enc = open('flag_enc.enc', "rb").read().decode().replace('L', '')enc = eval(enc)
l = len(enc)print('Length:', l)
def substitute_binary(bin_str, n, ln):        bin_n = bin(n)[2:].zfill(ln)        c = 0        new_str = ''        for s in bin_str:                if s == '?':                        new_str += bin_n[c]                        c += 1                else:                        new_str += s        return new_str
def text_from_bits(bits, encoding='utf-8', errors='surrogatepass'):        n = int(bits, 2)        return long_to_bytes(n).decode(encoding, errors)
def enc_p(a, arr):	a_s = 1	for i in range(l):		a_s = a_s * a[i] ** int(arr[i]) % p	return a_s
def final_brute(bin_str):        a, a_s = enc[0]        bin_str = bin_str.replace(' ', '')        ln = bin_str.count('?')        for i in range(1 << ln):                nbs = substitute_binary(bin_str, i, ln)                res = enc_p(a, nbs)                if res == a_s:                        print('Found', text_from_bits('0' + nbs))                        break        return res
flag_b = '1000001 01010011 01001001 01010011 01111011 00110001 00110111 00110101 01011111 01?01100 01101001 01?01011 00110011 01011111 01?01101 01110101 01?01100 01110100 01?01001 01110110 01?00001 01110010 01101001 01?00001 01?00010 01101100 00110011 01011111 01?01100 01101001 01?01110 01100101 00110100 01?10010 01011111 00110011 01010001 01110101 01000001 00110111 01?01001 00110000 01?01110 00110101 01111101'final_brute(flag_b)```
Final flag: `ASIS{175_Lik3_Multivariabl3_LiNe4r_3QuA7i0n5}`