## Strip
### Challenge
> Sometimes it is the people no one imagines anything of who do the things that no one can imagine.
```python#!/usr/bin/python
from Crypto.Util.number import *from secret import flag, r
def a(n): # WARNING: very slow implementation...	if n <= 2:		return n	elif n == 3:		return 24	else:		return (6*a(n-1)**2*a(n-3) - 8*a(n-1)*a(n-2)**2) // (a(n-2)*a(n-3))
def strip(n):	return int(bin(n)[2:].rstrip('0'), 2)
def encrypt(msg, r):	n = strip(a(r))	return pow(bytes_to_long(msg.encode('utf-8')), 0x10001 + 0x02, n)
print(encrypt(flag, r))```
### Solution
The challenge's `a(n)` is the [A028365](http://oeis.org/A028365) sequence on OEIS, which has a simpler form (written in PARI) is `a(n) = prod(k=1, n, 2^k-1)*2^((n^2+n)/2)`, and after stripped `a(n)` is only `prod(k=1, n, 2^k-1)`.
We estimated `r` and got `r >= 605`, factored `a(r)` by `FactorDB's API`, but the huge modulus took forever for calculating. So we took 2 prime factors from the factors of `a(r)` and let their product be the new modulus, and we finally got the flag.
Alternate solution uses the estimate of `r >= 60`. We can take all prime factors of `a(60)` that are less than `500000`, and solve `x ** e = enc (mod p)` for each of them by brute force. If we find a unique solution, we recover the value of `flag (mod p)`. We combine these with Chinese Remainder Theorem to finish.
### Implementation
#### Solution 1```pythonfrom factordb.factordb import FactorDBfrom itertools import combinations
c = ZZ(open("./flag.enc", 'r').read())
fac = []for i in range(1, 606):    print(i, end=' ')    f = FactorDB(2^i - 1)    f.connect()    fac += f.get_factor_list()
fac2 = sorted(list(set(fac)), reverse=True)
n_ = 1phi_ = 1for i,j in combinations(fac2, 2):    n_ = i*j    phi_ = (i - 1)*(j - 1)    d_ = inverse_mod(e, phi_)    m = long_to_bytes(pow(c, d_, n_))    if b'CCTF' in m:        print(m)        break```
#### Solution 2
```pythonfrom factordb.factordb import FactorDBfrom tqdm import tqdmfrom Crypto.Util.number import long_to_bytes
## modular inverse of a mod b, can be replaced with Crypto.Util.number's inversedef minv(a, b):    if a == 1:        return 1    return b - minv(b%a, a) * b // a
## Chinese Remainder Theoremdef CRT(a, b, c, d):    na = d * minv(d, b) * a + b * minv(b, d) * c    nb = b * d    na %= nb    assert na % b == a    assert na % d == c    return na, nb
enc = int(open("./flag.enc", 'r').read())
n = 1e = 0x10001 + 0x02totph = 1wow = []res = 1for i in tqdm(range(2, 68)):    res = res * (2**i - 1)    f = FactorDB(2**i - 1)    f.connect()    A = f.get_factor_list()    for num in A:        if num in wow:            totph = totph * num        else:            totph = totph * (num - 1)            wow.append(num)
AA = 0BB = 1
wow.sort()for i in tqdm(range(0, len(wow))):    print(wow[i])    if wow[i] > 50000:        continue    cnt = 0    whi = 0    for j in range(0, wow[i]):        if pow(j, e, wow[i]) == enc % wow[i]:            cnt = cnt + 1            whi = j    if cnt == 1:        AA, BB = CRT(AA, BB, whi, wow[i])        print(long_to_bytes(AA))```
### Flag
`CCTF{R3arR4n9inG_7He_9Iv3n_eQu4t10n_T0_7h3_mUcH_MOrE_traCt4bLe_0n3}`