BSides Ahmedabad CTF 2021 | dlppp

bsidesahmedabadctf_2021 binomial_theorem paillier暗号

#bsidesahmedabadctf_2021

import os
from Crypto.Util.number import getPrime, getRandomNBitInteger

flag = os.getenv("FLAG", "XXXX{sample_flag}").encode()
m = int.from_bytes(flag, 'big')

p = getPrime(512)
y = pow(1 + p, m, p**3)

assert m < p
print(f"p = {hex(p)}")
print(f"y = {hex(y)}")

y = (1 + p)^m \mod p^3

binomial theoremを思い出したりPaillier暗号を思い出したりするとすぐに解ける

with open("./output.txt", "r") as f:
    exec(f.read())

m = ((y - 1) % (p*p)) // p
print(int.to_bytes(int(m), 64, 'big'))