[AlpacaHack]WriteUp for super-tomato

Blog

2026.01.03

問題
WriteUp
1. フェルマーの小定理

問題

super-tomato - AlpacaHack

Gluttony pink needs the tomato...

アクセスすると素数が表示され、入力待ちの状態です

WriteUp

ソースコードのpow関数が1の時にフラグを入手することができます

ここでのpow関数は、aのchoice乗をpで割ったあまりです。

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)
print(f"DEBUG: a = {a}")
if pow(a, choice, p) == 1:
    print(f"here is the flag: {flag}")
else:
    print("NO NO 🍅")

フェルマーの小定理

powでわかるのがchoiceとpの値で、

`print(f”here is my 🍅: {p}”)`でpの値が表示されます
choiceは自分で入力をすることができます

powは、数値の累乗を計算することができ引数を3つにすると3つ目で割ったあまりを返します

つまり、pで割った結果が1になれば良いです

フェルマーの小定理があり、以下の

pを素数として、aをpの倍数ではないとき

p-1の倍数は1になります

フェルマーの小定理 - Wikipedia

つまりpが以下のような場合であれば

here is my 🍅: 22635544950031082642458163010280034150333571218509991307388214840061710348615613764599075119892499939425639815543524229770531598561455638936108382273463170097915512661972152086453285765917313048818180568140108350833864217724393033185729638434325581089560319583409740638037797614468323288200081444397668897673139437296885176787476540468787494808313798742948933867285359864909362375042767160253675010579206798676469660703454401378066241367177195902221417036130787226474799758557805838707998634813267342261115395438720556391406908886848103449296728194195262686117811327986439243476082987080019159947496466260793098490853

p-1した値がpow関数「1」になります

22635544950031082642458163010280034150333571218509991307388214840061710348615613764599075119892499939425639815543524229770531598561455638936108382273463170097915512661972152086453285765917313048818180568140108350833864217724393033185729638434325581089560319583409740638037797614468323288200081444397668897673139437296885176787476540468787494808313798742948933867285359864909362375042767160253675010579206798676469660703454401378066241367177195902221417036130787226474799758557805838707998634813267342261115395438720556391406908886848103449296728194195262686117811327986439243476082987080019159947496466260793098490852

その値をchoiceにすればフラグが表示されます