Dowload the given package and unpack it, we got a python code with its output (public keys and encrypted texts)
```
#!/usr/bin/python

from Crypto.PublicKey import RSA
import gmpy
from secret import r, s, p, q, FLAG

assert ((p-1) % r)**2 + ((q-1) % s)**4 + ((r**3 - 1) % p)**8 + ((s**3 - 1) % q)**16 == 0
assert gmpy.is_prime(r) + gmpy.is_prime(s) + gmpy.is_prime(p) + gmpy.is_prime(q) == 4

def keysaz(a, b):
e, n = 65537, a * b
d = gmpy.invert(e, (a-1)*(b-1))
key = RSA.construct((long(n), long(e), long(d)))
return key

key_0, key_1 = keysaz(gmpy.next_prime(r+s), gmpy.next_prime((r+s)<<2)), keysaz(p, q)
pkey_0, pkey_1 = key_0.publickey().exportKey(), key_1.publickey().exportKey()

print pkey_0
enc_0 = key_0.encrypt(FLAG[:18], 1L)[0]
print 'enc_0 =\n', enc_0.encode('base64')

print pkey_1
enc_1 = key_1.encrypt(FLAG[18:], 1L)[0]
print 'enc_1 =\n', enc_1.encode('base64')
```

From the code, the message is breaking into 2 parts, each encripted with RSA using a different key.

### Part 1
For the first key:
```
key_0 = keysaz(gmpy.next_prime(r+s), gmpy.next_prime((r+s)<<2))
```
Here $N = pq$ $(p < q)$, and $p$, $q$ have an near linear relation $q\approx4p$.
We have $q=2\sqrt{N}+\epsilon$, $\epsilon$ is very small compared to $N$, according to [Primes number Theorem](https://en.wikipedia.org/wiki/Prime_number_theorem).

We can now find $\epsilon$ using [Reformulation of Coppersmith's attack by Howgrave-Graham](https://github.com/mimoo/RSA-and-LLL-attacks#factoring-with-high-bits-known).
```
qbar = isqrt(4*n1) # approximation q' of q
F.<x> = PolynomialRing(Zmod(n1), implementation='NTL');
pol = x + qbar

beta = 0.5 # we should have q >= N^beta
dd = pol.degree()
epsilon = beta / 7 # <= beta/7
mm = ceil(beta**2 / (dd * epsilon)) # optimized
tt = floor(dd * mm * ((1/beta) - 1)) # optimized
XX = ceil(n1**((beta**2/dd) - epsilon)) # we should have |diff| < X
roots = coppersmith_howgrave_univariate(pol, n1, beta, mm, tt, XX)
```
It gives root $-976$ and $q=-976+[\sqrt{4N}]=90829988108297459126723951986073924022504128225586222454376617387900632408868147010157825639889602300446053601539575136123106704382046836252729190919472251$

Now that we've factored N, it is trival to decrypt the cipher and get first half of message:
```
p1 = (n1//q1)
d1 = (inverse(e1, (p1-1)*(q1-1)//2))
m1 = RSA.construct((n1, e, long(d1))).decrypt(c1)
print 'msg1:', m1
```
> msg1: ASIS{0240093faf9ce
and we also get the range limit on r+s:
```
r_s_min = max(p1.previous_prime(), (q1.previous_prime()>>2)+1)
r_s_max = min(p1-1, q1>>2)
print 'r+s: [%d, %d]' % (r_s_min, r_s_max)
```
> r+s: [22707497027074364781680987996518481005626032056396555613594154346975158102217036752539456409972400575111513400384893784030776676095511709063182297729867955, 22707497027074364781680987996518481005626032056396555613594154346975158102217036752539456409972400575111513400384893784030776676095511709063182297729868062]

### Part 2
For the second key:
```
assert ((p-1) % r)**2 + ((q-1) % s)**4 + ((r**3 - 1) % p)**8 + ((s**3 - 1) % q)**16 == 0
assert gmpy.is_prime(r) + gmpy.is_prime(s) + gmpy.is_prime(p) + gmpy.is_prime(q) == 4
key_1 = keysaz(p,q)
```
There are many constraint posed on p,q,r and s:
1. p, q, r, s are all primes;
2. $r | (p-1)$
3. $s | (q-1)$
4. $p | (r^3-1)$
5. $q | (s^3-1)$

From 2 and 4, $r < p$, and $p | (r^2+r+1)$

Suppose $r^2+r+1=kp$, since $p\equiv 1$ (mod $r$), we have $k\equiv 1$ (mod $r$)

If $k \ge r+1$, then $$r^2+r+1-kp\le r^2+r+1-(r+1)p = (r+1)(r-p)+1 \le -(r+1)+1 < 0$$
Thus $k=1$, and $p=r^2+r+1$. Similar $q=s^2+s+1$.

Now we have $$N=pq=(r^2+r+1)(s^2+s+1)=(rs)^2+(r+s-1)rs+(r+s)^2+(r+s)+1$$
Enumerate $r+s$ from the limited range got from Part 1, we can try solving $rs$ and finally $r$,$s$.
```
p = q = None
for r_s in range(r_s_min, r_s_max):
# solve x**2+(r+s-1)*x+((r+s)**2+(r+s)+1-N) = 0
d2 = (r_s-1)**2-4*(r_s**2+r_s+1-N)
d = isqrt(d2)
if d**2 != d2:
continue
rs = (d-(r_s-1))/2
# solve x**2 - r_s*x + rs = 0
dd2 = r_s**2-4*rs
dd = isqrt(dd2)
if dd**2 != dd2:
continue
r, s = (r_s+dd)/2, abs(r_s-dd)/2
p, q = (r**2+r+1, s**2+s+1)
break
```
And finally the flag:
```
d = (inverse(e, (p-1)*(q-1)//2))
m2 = RSA.construct((N, e, long(d))).decrypt(c2)
print 'msg2:', m2
print m1+m2
```
> msg2: 4d7be86d87d49a95cf7}
>
> ASIS{0240093faf9ce4d7be86d87d49a95cf7}