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 random
from 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*587934254364063975369377416367
div_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?10101111101
0 A
1 S
2 I
3 S
4 {
5 15QUqu
6 0123456789PQRSTUVWXYZ_pqrstuvwxyz{}
7 159AEIMQUYaeimquy}
8 GOW_
9 4567DEFGLMNOTUVW_defglmnotuvw}
10 159aeimquy}
11 ABCHIJKabchijk
12 139QSYqsy{
13 QSUWY_
14 LMNOlmno
15 159aeimquy}
16 HJLNhjln
17 4t
18 AIQYaiqy
19 46dflntv
20 Aa
21 028bhjprxz
22 im
23 13579ACEGIKMOQSUWY_acegikmoqsuwy{}
24 BFJNbfjn
25 delm
26 0123
27 PQRSTUVWXYZ_pqrstuvwxyz{}
28 014589ADEHILMPQTUXYadehilmpqtuxy}
29 ahi
30 LNln
31 emu}
32 0246
33 23RSZrsz{
34 CGKOSW_cgkosw{
35 012389ABCHIJKPQRSXYZabchijkpqrsxyz{
36 AEQU
37 13579acegikmoqsuwy{}
38 AIQY
39 37cgkosw{
40 ACIKacik
41 04
42 Nn
43 5
44 }
```

## 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 AEQU
37 13579acegikmoqsuwy{}
38 AIQY
39 37cgkosw{
40 ACIKacik
41 04
42 Nn
43 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 ahi
30 LNln
31 emu}
32 0246
33 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 LMNOlmno
15 159quy}
16 hjln
17 4t
18 AIQYaiqy
19 46dflntv
20 Aa
21 028bhjprxz
22 im
23 13579ACEGIKMOQSUWY_acegikmoqsuwy{}
24 BFJNbfjn
25 delm
26 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 15QUqu
6 4567tuvw}
7 159AEIMQUYaeimquy}
8 GOW_
9 4567DEFGLMNOTUVW_defglmnotuvw}
10 159aeimquy}
11 ABCHIJKabchijk
12 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*587934254364063975369377416367
div_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}`