Rating:
# TPSD
## Source
Solving Diophantine equations is a notoriously challenging problem in number theory, and finding non-trivial integer solutions for certain equations is considered a major open problem in mathematics.
## Exploit
There is no script provided, so we will manually interact with the challange to get the instructions using python and pwntools.
- So, the challenge asks us to send 3 integers p,q and r such that `p^3+q^3+r^3 = 1`. It also gives us the range of how long the bit length of p,q and r should be for each level.
- Also atleast one of those 3 must be prime.
- We can generate p,q and r such that `p^3+q^3+r^3 = 1` by providing the values
- `P = 9*(b**4)`
- `Q = -3*b-9*(b**4)`
- `R = 1+9*(b**3)`
## Script
### 1. Setting the Connection and Function to get p,q and r
```
from pwn import *
host=r'05.cr.yp.toc.tf'
port=11137
from Crypto.Util.number import *
from math import *
from sympy import isprime
def find_b(l,r):
l = round(((2**l+1)//9)**(1/3))
r = round(((2**r+1)//9)**(1/3))
for b_ in range(l,r):
a = 9*(b_**3)+1
if isprime(a):
return b_
```
- Initialises the connection credentials.
- R is the lowest absolute number among p,qand r , so we find the range of b such that R is in the given bit range and since we are starting from low to high, R will be pretty low in the range hence P and Q which are higher than R will also be in the range.
- It checks if R is prime since we need atleast one prime and then returns b.
### 2. Getting the instructions
```
while True:
try:
r=remote(host,port)
for i in range(9):
print(r.recvline())
```
- Sets up a connection to the challenge and recieves the Instruction messages.
### 3. Getting the Range and forming the 3 numbers
```
while True:
print(r.recvline())
range_=r.recvline().decode().strip()
l_r=range_.split('(')[1].split(')')[0]
left,right=map(int,l_r.split(', '))
print(left,right)
b = find_b(left,right)
P = 9*(b**4)
Q=-3*b-9*(b**4)
R=1+9*(b**3)
```
- This goes on as long as there is a EOF error then the first loop breaks as there is r.close and break in except block of code
### 4. Sending the numbers and getting the feedback.
```
s=str(P)+','+str(Q)+','+str(R)
print(s)
r.sendline(s.encode())
print(r.recvline())
except:
r.close()
break
```
- Sends the numbers as many times as prompted , gets the flag, hits EOF error and breaks.
## Flag
The flag is CCTF{pr1m3S_in_7ErnArY_Cu8!c_3qu4tI0nS!}
