[羊城杯 2020]GMC

[羊城杯 2020]GMC

题目

from Crypto.Util.number import getPrime,bytes_to_long,getRandomNBitInteger
from secret import flag
from gmpy2 import gcd


def gmc(a, p):
    if pow(a, (p-1)//2, p) == 1:
        return 1
    else:
        return -1


def gen_key():
    [gp,gq] = [getPrime(512) for i in range(2)]
    gN = gp * gq
    return gN, gq, gp


def gen_x(gq,gp):
    while True:
        x = getRandomNBitInteger(512)
        if gmc(x,gp) ^ gmc(x,gq) == -2:
            return x


def gen_y(gN):
    gy_list = []
    while len(gy_list) != F_LEN:
        ty = getRandomNBitInteger(768)
        if gcd(ty,gN) == 1:
            gy_list.append(ty)
    return gy_list


if __name__ == '__main__':

    flag = bin(bytes_to_long(flag))[2:]
    F_LEN = len(flag)
    N, q, p = gen_key()
    x = gen_x(q, p)
    y_list = gen_y(N)
    ciphertext = []

    for i in range(F_LEN):
        tc = pow(y_list[i],2) * pow(x,int(flag[i])) % N
        ciphertext.append(tc)

    with open('./output.txt','w') as f:
        f.write(str(N) + '\n')
        for i in range(F_LEN):
            f.write(str(ciphertext[i]) + '\n')

解题

程序如何加密的还是挺容易看出来的，关键就是怎么逆过去了。。。

from Crypto.Util.number import *
def isqr(x,p):
    if p==1 or x==1:
        return 1
    sgn=1
    while x%2==0:
        x=x//2
        if p%8==3 or p%8==5:
            sgn=-sgn
    if x<p:
        _tmp=p
        p=x
        x=_tmp
        if x%4==3 and p%4==3 :
            sgn=-sgn
    return sgn*isqr(x%p,p)
n,s=0,[]
fp=open("output.txt","r")
n=int(fp.readline())
while True:
    try:
        a=int(fp.readline())
        s.append(a)
    except:
        break
assert len(s)+1==304
ans=""
for i in s:
    if(isqr(i,n)==1):
        ans+='0'
    else:
        ans+='1'
print(long_to_bytes(int(ans,2)))

参考代码

运行得到：b'GWHT{876db950c1424a8e49d50cdcc0b3a86e}'

答案

flag{876db950c1424a8e49d50cdcc0b3a86e}