[羊城杯 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个32bit的随机数，这条路其实是走不通的，再回来看看题目的标题，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)))