## 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?
```python2*z**5 - x**3 + y*z = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721x**4 + y**5 + x*y*z = 89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051y**6 + 2*z**5 + z*y = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058p = nextPrime(x**2 + z**2 + y**2 << 76)q = nextPrime(z**2 + y**3 - y*x*z ^ 67)n, e = p * q, 31337m = 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$:
```pythonfrom z3 import *from sympy import *
A = 3133713317731333B = 28413320364759425177418147555143516002041291710972733253944530195017276664069717887927099709630886727522090965378073004342203980057853092114878433424202989c = 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!}`