[羊城杯 2020]GMC题解

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

刚做完这个问题，我看到了上面的问题getRandomNBitInteger()函数，无意识地网络MT上靠，却发现有一个神出鬼没的x存在，让我根本无法还原624个324bit随机数，这条路其实是走不通的，再回来看标题，gmc这个函数应该是关键。

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

这个函数让人想起了二次剩余的问题，生成x算法说明，x是p，q其中一个的二次剩余，而且是另外一个的非二次剩余。

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

标题中的加密如下：

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

要解决这个加密，其实就是还原每一个tc是否乘上了x，从而还原flag二进制位。

上述加密结构对了解上述条件有很大帮助，若没有乘x ，pow(y_list[i],2) %N必须是模N的二次剩余，即雅克比符号为1，同时，x模N雅克比符号可以分解成x模p雅克比符号 和 x模q雅克比符号的乘积，即-1，不难得出，如果该tc乘了x，则该tc雅克比符号必为-1，以此作为区分，可以逐一获得flag二进制位。

from Crypto.Util.number import long_to_bytes import gmpy2 plaintext = '' with open('output.txt') as f:     n = int(f.readline())     for line in f:         cipher = int(line)         if gmpy2.jacobi(cipher,n) == -1:             plaintext  = '1'         else:             plaintext  = '0' print(long_to_bytes(int(plaintext,2)))