Rating:
## RSAphantine
### Challenge
> [RSA](https://cryp.toc.tf/tasks/RSAphantine_b1f2e30c7e90cfacb9ef4d0b5ce80abe33d1eb08.txz) and solving equations, but should be a real mathematician to solve it with a diophantine equation?
```python
2*z**5 - x**3 + y*z = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721
x**4 + y**5 + x*y*z = 89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051
y**6 + 2*z**5 + z*y = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058
p = nextPrime(x**2 + z**2 + y**2 << 76)
q = nextPrime(z**2 + y**3 - y*x*z ^ 67)
n, e = p * q, 31337
m = bytes_to_long(FLAG)
c = pow(m, e, n)
c = 486675922771716096231737399040548486325658137529857293201278143425470143429646265649376948017991651364539656238516890519597468182912015548139675971112490154510727743335620826075143903361868438931223801236515950567326769413127995861265368340866053590373839051019268657129382281794222269715218496547178894867320406378387056032984394810093686367691759705672
```
### Solution
This challenge gives us the following set of three equations and three unknowns $x$, $y$, and $z$; it then generates parameters for RSA encryption using the following equations:
$$
p = \text{nextPrime}(\frac{x^2+y^2+z^2}{2^{76}})\\
q = \text{nextPrime}(z^2+y^3- (xyz \oplus 67))
$$
It doesn't look like we can attack the equations for $p$ or $q$ directly, so we solve the diophantine equations first:
$$
2z^5-x^3+yz=47769... = a\\
x^4+y^5+xyz=89701... = b\\
y^6+2z^5+yz=47769... = c
$$
Note that while the right hand side of the first and third equations appear to be the same, they are different numbers. We first compute $c-a = x^3+y^6 = (x+y^2)(x^2-xy^2+y^4)$ by sum of cubes; factoring $c-a$, we recover the factors $3133713317731333$ and $28413320364759425...$.
Plugging the equations into z3, we solve for $x$, $y$, and $z$:
```python
from z3 import *
from sympy import *
A = 3133713317731333
B = 28413320364759425177418147555143516002041291710972733253944530195017276664069717887927099709630886727522090965378073004342203980057853092114878433424202989
c = 486675922771716096231737399040548486325658137529857293201278143425470143429646265649376948017991651364539656238516890519597468182912015548139675971112490154510727743335620826075143903361868438931223801236515950567326769413127995861265368340866053590373839051019268657129382281794222269715218496547178894867320406378387056032984394810093686367691759705672
x = Int("x")
y = Int("y")
z = Int("z")
s = Solver()
s.add(y**2 + x == A)
s.add(y**4 - x*y**2 + x**2 == B)
s.add(y>0)
s.add(2*z**5 - x**3 + y*z == 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721)
s.add(x**4 + y**5 + x*y*z == 89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051)
s.add(y**6 + 2*z**5 + z*y == 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058)
if s.check() == sat:
m = s.model()
x = m[x].as_long()
y = m[y].as_long()
z = m[z].as_long()
p = nextprime(x**2 + z**2 + y**2 << 76)
q = nextprime(z**2 + y**3 - y*x*z ^ 67)
d = pow(31337, -1, (p-1)*(q-1))
print(bytes.fromhex(hex(pow(c, d, p*q))[2:]).decode())
```
##### Flag
`CCTF{y0Ur_jO8_C4l13D_Diophantine_An4LySI5!}`
