問題

ぴんくいろ の ぼうしょく は とまと を もとめて いる…

from Crypto.Util.number import *
import os

flag = os.getenv("FLAG", "flag{EXAMPLE_TOMATO}")

p = getPrime(2048)

print(f"I think 🍅 equals to prime.")
print(f"here is my 🍅: {p}")
print("I need ONE 🍅!!!")
choice = int(input("what is your 🍅> "))

if choice <= 0:
    print("I need a POSITIVE 🍅!!!")
    exit()

a = getPrime(1024)

if pow(a, choice, p) == 1:
    print(f"here is the flag: {flag}")
else:
    print("NO NO 🍅")

解法

We are given a 2048-bit prime p, then we must provide a positive integer choice such that:

$a^{choice}\equiv 1 \pmod p$

where a is a random 1024-bit prime chosen after we submit choice.

So we need an exponent that makes the congruence true for almost any a in advance.

Fermat’s Little Theorem: $a^{p−1}≡1 \pmod p$

So we can just submit:

$choice=p−1$ then the check will always pass, regardless of the random a.

ソルバ

from ptrlib import *

io = remote("nc 34.170.146.252 29160")
p = int(io.recvlineafter(": ").strip())
choice = p - 1
io.sendlineafter("> ", choice)
print(io.recvline())