João chinchila

Writeup Pythia

Description:

Solves: 65

Yet another oracle, but the queries are costly and limited so be frugal with them.

About the challenge

Monward - AsisCTF Finals 2022

O AsisCTF é um grande CTF internacional que acontece todo ano, atualmente todos podem participar tanto do qualifier quanto da final. É considerado um CTF difícil e um dos mais famosos de acordo com a comunidade.

Esse desafio foi resolvido por 30 times de 357 no total. Eu considero ele de nível médio.

O desafio (arquivo chall.sage) dá pra gente 3 pontos (P, Q e R) numa curva elíptica e um valor enc que é um a mensagem multiplicada ao ponto P da curva. A função monadd representa a adição de dois pontos na curva, a função monprod multiplica um valor escalar a um ponto, a função encrypt faz a multiplicação da mensagem a um ponto e a função monon verifica se o ponto ta na curva.

A primeira coisa que devemos notar é que enc também é um ponto da curva, logo temos 4 pontos. A segunda coisa que devemos perceber é a equação da curva, na função monon de acordo com essa parte do código (a*x**2 + y**2 - d*x**2*y**2) % p == 1 a função da curva é:

	#include <stdio.h>
	#include <stdint.h>

	#ifdef __i386__
	uint32_t hwrand()
	{
	uint32_t eax;
	__asm__ volatile( ".byte 0x0f, 0xc7, 0xf0;" : "=a"( eax ) );
	return eax;
	}

	/**
	* UVA 540 resolution: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=481
	**/

	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>

	#define MAX_TEAMS 1001
	#define MAX_ELEMENTS 1000001

	/**
	* Binomial heap data structure
	* Test case:
	* i 10
	* i 20
	* i 30
	* a
	* i 5
	* a
	* i 3

	#include<bits/stdc++.h>
	using namespace std;
	#define MAXN 1010
	vector<int> g[MAXN];
	int n, m, mx;
	int lvl[MAXN], dp[MAXN], sub[MAXN];

	void dfs( int u ){
	dp[u] = 0;
	sub[u] = 1;