[羊城杯 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')

这个问题属于一个相对简单的类别，事实上，一开始我的想法是正确的，但没有看到这个行业

flag = bin(bytes_to_long(flag))[2:]

flag二进制字符串！

因为没看有看到，这让我已知flag就是flag字符串，而

tc = pow(y_list[i],2) * pow(x,int(flag[i])) % N

这里也想当然int(flag[i])是一个字符ord，怎么办？？现在想想，如果你更小心，如果是ord语法是错误的。

我是傻逼

所以这个问题也有收获，也就是知道gmpy2.jacobi()可以直接判断一个数是否是另一个数的二次剩余(其实底层原理是判断 a^((p-1)/2) mod p 等于几

题解：

可知flag是二进制字符串，取0时tc加密过程不会乘上x，那么剩下的pow(y_list[i],2)是个平方的形式必然是n的二次剩余。如果乘上了x，那么x是p二次剩余，不是q的二次剩余，两者相乘会得到1*(-1)=-1

以此来退出flag所有二进制位

f=open("output.txt").readlines() n=int(f[0])  import gmpy2 from Crypto.Util.number import * from tqdm import tqdm ciphertext=[] for i in range(1,len(f)):     ciphertext.append(int(f[i][:-1]))  #print(ciphertext) flag='' for c in tqdm(ciphertext):     if gmpy2.jacobi(c,n)==1:         flag ='0'     if gmpy2.jacobi(c,n)==-1:         flag ='1'  print(long_to_bytes(int(flag,2)))