SuSeC CTF 2020 – Inaction Writeup (ppc)

import re, sys, os, signal, string, random
from hashlib import *
from secret import flag

p = 2**2281 - 1
s = 2**228
pad = 2228

def idle_square(x, toil, pad):
    for i in range(toil):
        x = pow(x ^ pad, 2, p)
    return x

def gen_chall(toil):
	x = random.randint(1, s)
	return [x, toil, pad]

def main():
	pr("-"*72)
	pr("|" + " hi all, in each level try to solve given challenge ".center(70) + "|")
	pr("-"*72)
	stage = 40
	for i in range(stage):
		x, toil, pad = gen_chall(stage)
		y = idle_square(x, toil, pad)
		pr('y =', y)
		pr('please send solution:')
		ans = sc()
		try:
			ans = int(ans)
		except:
			die('Sorry, the given answer is not integer! Bye!!')
		if ans == x:
			if i == 39:
				die('Congratz! You got the flag:', flag)
			else:
				pr('Great! Please solve the next level :P')
		else:
			die('Your answer is not correct, try again, Bye!')

p = 2**2281 - 1
s = 2**228
pad = 2228

all = []
def solve(y, stage):
    if stage <= 0:
        all.append(y)
        return
    possible_current_stage_answers = prime_mod_sqrt(y, p)
    for possible_current_stage_answer in possible_current_stage_answers:
        x = (possible_current_stage_answer ^ pad) % p
        solve(x, stage - 1)

solve(y, 40)
x = min(all)

from pwn import *


def legendre_symbol(a, p):
    """
    Legendre symbol
    Define if a is a quadratic residue modulo odd prime
    http://en.wikipedia.org/wiki/Legendre_symbol
    """
    ls = pow(a, (p - 1)//2, p)
    if ls == p - 1:
        return -1
    return ls

def prime_mod_sqrt(a, p):
    """
    Square root modulo prime number
    Solve the equation
        x^2 = a mod p
    and return list of x solution
    http://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm
    """
    a %= p

    # Simple case
    if a == 0:
        return [0]
    if p == 2:
        return [a]

    # Check solution existence on odd prime
    if legendre_symbol(a, p) != 1:
        return []

    # Simple case
    if p % 4 == 3:
        x = pow(a, (p + 1)//4, p)
        return [x, p-x]

    # Factor p-1 on the form q * 2^s (with Q odd)
    q, s = p - 1, 0
    while q % 2 == 0:
        s += 1
        q //= 2

    # Select a z which is a quadratic non resudue modulo p
    z = 1
    while legendre_symbol(z, p) != -1:
        z += 1
    c = pow(z, q, p)

    # Search for a solution
    x = pow(a, (q + 1)//2, p)
    t = pow(a, q, p)
    m = s
    while t != 1:
        # Find the lowest i such that t^(2^i) = 1
        i, e = 0, 2
        for i in range(1, m):
            if pow(t, e, p) == 1:
                break
            e *= 2

        # Update next value to iterate
        b = pow(c, 2**(m - i - 1), p)
        x = (x * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        m = i

    return [x, p-x]

p = 2**2281 - 1
s = 2**228
pad = 2228

all = []
def solve(y, stage):
    global all
    if stage <= 0:
        all.append(y)
        return
    possible_current_stage_answers = prime_mod_sqrt(y, p)
    for possible_current_stage_answer in possible_current_stage_answers:
        x = (possible_current_stage_answer ^ pad) % p
        solve(x, stage - 1)


s = remote('66.172.27.57', 3114)

for i in range(1,41):
    y = int(s.recvline_contains('y = ')[4:])
    s.recvline_contains("please send solution:\n")
    print("[*] ------- Step {} ------- ".format(i))
    print("[*] Got new y: {}".format(y))
    solve(y, 40)
    x = min(all)
    all = []
    print("[*] Valid x : {}".format(x))
    s.sendline(str(x))

s.interactive()