Mod writeup

Challenge

#!/usr/local/bin/python3
import os
secret = int(os.urandom(32).hex(),16)
print("Welcome to Mod!")
num=int(input("Provide a number: "))
print(num % secret)
guess = int(input("Guess: "))
if guess==secret:
    print(open('flag.txt').read())
else:
    print("Incorrect!")

One way to solve this is to notice that if you use a number that is -1 mod secret, you'll get back secret-1.

For each secret, the number must be -1 mod secret. So the lcm of all the possible numbers would work.

import os
from math import lcm
lcm(range(int(len(os.urandom(32).hex())\*'f',16)))-1 # waiting...

This is a bit too large. According to https://oeis.org/A003418, we have a bound of a(n) >= 2^(n-1), and we want a(2^256)-1>=2^(2^256-1)-1. For reference, there's only about 10^80 < 2^267 atoms in the universe.

Then I remembered I read an article about benchmarking that said that most random numbers are very large: https://www.vidarholen.net/contents/blog/?p=1160 We can use this to get an oracle into the secret.

We can use statistics. As it turns out, half the numbers are really large (> 1/2 * MAX_VALUE) and we have a way to check that scenario. For numbers that are close together, modulo looks like subtraction!

For some secret x where x > 1/2 * MAX (which will happen roughly half the time):

MAX % x = (MAX-x) % x

We know that MAX - x < 1/2 * MAX because x > 1/2 * MAX. But that also means MAX-x < x, so (MAX-x)%x = MAX-x

Therefore, for half the numbers, you have the relation MAX % x == MAX - x

But you know what MAX is, so X is MAX - (MAX - x) = x

So try a guess of int(len(os.urandom(32).hex())*'f',16), take the output and subtract it from your input, and half the time you'll get the correct answer! No need to write a script, it's fairly reliable anyway.

Flag: scriptCTF{-1_f0r_7h3_w1n_4a3f7db1_0da9a3a24e3f}

And now I realise I could have just used -1 all along... Why did I think it had to be a positive number??

ndren/mod-writeup.md

Challenge