四月

from secrets import randbelow
from Crypto.Util.number import getPrime
import sys

SIZE = 256
class PCG: # Polynomial Congruential Generator
    def __init__(self):
        self.m = getPrime(256)
        self.coeff = [randbelow(self.m-1) for _ in range(SIZE)] # 随机数列表
        self.x = randbelow(self.m-1) # 随机数
    def __call__(self): # f = a*x^255.......b*x^1 + c
        newx = 0
        for c in self.coeff:
            newx *= self.x
            newx += c
            newx %= self.m
        self.x = newx
        return self.x
    def printm(self):
        print(self.m)
        return
pcg = PCG()

print(pcg.m) # 模 
for i in range(SIZE*3):
    print(pcg())

sys.stdout.flush()
correct = True
for i in range(SIZE // 2):
    guess = int(input())
    if guess != pcg():
        correct = False

if correct:
    print(open('flag.txt','r').read())
else:
    print("you failed")
sys.stdout.flush()

    def __call__(self): # f = a*x^255.......b*x^1 + c
        newx = 0
        for c in self.coeff:
            newx *= self.x
            newx += c
            newx %= self.m

points = []
m = int(sh.recvline().strip().decode())
T = []
for i in range(256*3):
    t = int(sh.recvline().strip().decode())
    T.append(t)
for i in range(len(T)-1):
    points.append((T[i],T[i+1]))

print("m =" , m)
print("points =" , points) # 255个点
print("T =",T) # 256个随机数

PR = PolynomialRing(Zmod(m), 'x')
f = PR.lagrange_polynomial(points) # 插值sage调用
print(f)
for i in range(128):
    tt = f(T[-1])
    T.append(tt)
    print(tt)

from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from math import lcm,gcd
from secrets import randbelow
from hashlib import sha256

NUM_BITS = 2048

def getModulus(bits):
    n = 1
    primes = []
    while n.bit_length() < bits:
        p = getPrime(24)
        if p not in primes:
            n *= p
            primes.append(p)
    return n,primes

def sign(n,msg,d):
    h = bytes_to_long(sha256(msg).digest())
    k = randbelow(q-2)+1
    x = pow(h,k,n)
    r = pow(x,d,n)
    s = pow(h+x,d,n)
    return r,s

def verify(n,msg,e,r,s):
    h = bytes_to_long(sha256(msg).digest())
    v1 = pow(r,e,n)
    v2 = pow(s,e,n)
    return v2 == (v1 + h) % n

n,primes = getModulus(NUM_BITS)
q = 1
for p in primes:
    q = lcm(q,p-1)
msgs = []
e = 65537
d = pow(e,-1,q)

print(f"The modulus is ... a mystery left for you to unfold.")
print(f"Your verification exponent {e = }")
msg = input("Give the oracle a message to sign: ").encode()
msgs.append(msg)
r,s = sign(n,msg,d)
print(f"Your verification signature is ({r}, {s})")

msg = input("Give the oracle another message to sign: ").encode()
msgs.append(msg)
r,s = sign(n,msg,d)
print(f"Your second verification signature is ({r}, {s})")

comm = input("Ask the oracle a question: ").encode()
r,s = input("Give the verification signature: ").split(",")
r,s = int(r),int(s)

if comm in msgs:
    print("Hey, no cheating")
    exit()
if verify(n,comm,e,r,s):
    if comm == b"What is the flag?":
        print("The flag is: ",end="")
        with open("flag.txt","r") as flag:
            print(flag.read())
    else:
        print("Not the right question.")
else:
    print("Invalid signature")

if comm in msgs:
    print("Hey, no cheating")
    exit()

if verify(n,comm,e,r,s):
    if comm == b"What is the flag?":
        print("The flag is: ",end="")
        with open("flag.txt","r") as flag:
            print(flag.read())