[羊城杯 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')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

分析代码，发现x 的生成涉及到平方剩余。利用雅可比符号可表示为$(\frac{x}{p})(\frac{x}{q})=-1$。观察加密部分，根据flag[i]的值有以下两种情况：
{ t c = y i 2 m o d   n   , f l a g [ i ] = 0 t c = y i 2 ∗ x m o d   n   , f l a g [ i ] = 1

{tc=yi2​mod n ,flag[i]=0tc=yi2​∗xmod n ,flag[i]=1​
$y_i$是模 n 的平方剩余，于是利用雅可比符号的可乘性，上面两个式子是否平方剩余可表示为
{ ( t c n ) = ( y i 2 n ) = 1   , f l a g [ i ] = 0 ( t c n ) = ( y i 2 n ) ( x n ) = ( x p ) ( x q ) = − 1   , f l a g [ i ] = 1

{(tcn)=(yi2n)=1 ,flag[i]=0(tcn)=(yi2n)(xn)=(xp)(xq)=−1 ,flag[i]=1" role="presentation" style="position: relative;">⎧⎩⎨⎪⎪⎪⎪⎪⎪(tcn)=(y2in)=1 ,flag[i]=0(tcn)=(y2in)(xn)=(xp)(xq)=−1 ,flag[i]=1$$\{\begin{array}{l}({\displaystyle \frac{tc}{n}})=({\displaystyle \frac{y_i^2}{n}})=1,flag[i]=0\\ ({\displaystyle \frac{tc}{n}})=({\displaystyle \frac{y_i^2}{n}})({\displaystyle \frac{x}{n}})=({\displaystyle \frac{x}{p}})({\displaystyle \frac{x}{q}})=-1,flag[i]=1\end{array}$$

⎩ ⎨ ⎧​(ntc​)=(nyi2​​)=1 ,flag[i]=0(ntc​)=(nyi2​​)(nx​)=(px​)(qx​)=−1 ,flag[i]=1​
根据雅可比的值的不同，推出flag。

from Crypto.Util.number import *
from gmpy2 import jacobi

f = open(r'output.txt','r')
n = int(f.readline())

cipher = f.readlines()

flag = ''
for each in cipher:
    tc = int(each)
    if jacobi(tc,n) == -1:
        flag += '1'
    else:
        flag += '0'

print(long_to_bytes(int(flag,2)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

参考：

羊城杯 2020GMC题解_mortal15的博客-CSDN博客