Daily AlpacaHack: super-tomato Writeup

super-tomato

authored by kanon

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

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 🍅")

解法

今回の問題では、
$$
a^{choice} \equiv 1\pmod p
$$
となるようなchoiceを選択することでフラグが得られます。

さて、法$p$が素数のとき、フェルマーの小定理より、
$$
a^{p-1} \equiv 1 \pmod p
$$
となります。
つまり、今回の問題は、choiceの値が$p-1$となるように設定してあげれば、上記の問題を解決しフラグを得られます。

from pwn import *

HOST = "34.170.146.252"
PORT = 35506

io = remote(HOST, PORT)

io.recvuntil(b": ")
p = io.recvline().strip().decode()
print(p)
io.sendline(str(int(p)-1).encode())

io.interactive()

Flag:Alpaca{Fully_restores_HP!!}