Crypto

math_rsa

  • 题目附件如下：
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
from Crypto.Util.number import *
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
phi = (p - 1) * (q - 1)

u = getPrime(16)
t = 2 * u 
x = phi - 1
y = t + 1
k = 485723311775451084490131424696603828503121391558424003875128327297219030209620409301965720801386755451211861235029553063690749071961769290228672699730274712790110328643361418488523850331864608239660637323505924467595552293954200495174815985511827027913668477355984099228100469167128884236364008368230807336455721259701674165150959031166621381089213574626382643770012299575625039962530813909883594225301664728207560469046767485067146540498028505317113631970909809355823386324477936590351860786770580377775431764048693195017557432320430650328751116174124989038139756718362090105378540643587230129563930454260456320785629555493541609065309679709263733546183441765688806201058755252368942465271917663774868678682736973621371451440269201543952580232165981094719134791956854961433894740133317928275468758142862373593473875148862015695758191730229010960894713851228770656646728682145295722403096813082295018446712479920173040974429645523244575300611492359684052455691388127306813958610152185716611576776736342210195290674162667807163446158064125000445084485749597675094544031166691527647433823855652513968545236726519051559119550903995500324781631036492013723999955841701455597918532359171203698303815049834141108746893552928431581707889710001424400

assert((x**2 + 1)*(y**2 + 1) - 2*(x - y)*(x*y - 1) == 4*(k + x*y))

m = bytes_to_long(flag)
c = pow(m, e, n)

print("n =", n)
print("e =", e)
print("c =", c)

'''
n = 14070754234209585800232634546325624819982185952673905053702891604674100339022883248944477908133810472748877029408864634701590339742452010000798957135872412483891523031580735317558166390805963001389999673532396972009696089072742463405543527845901369617515343242940788986578427709036923957774197805224415531570285914497828532354144069019482248200179658346673726866641476722431602154777272137461817946690611413973565446874772983684785869431957078489177937408583077761820157276339873500082526060431619271198751378603409721518832711634990892781578484012381667814631979944383411800101335129369193315802989383955827098934489
e = 65537
c = 12312807681090775663449755503116041117407837995529562718510452391461356192258329776159493018768087453289696353524051692157990247921285844615014418841030154700106173452384129940303909074742769886414052488853604191654590458187680183616318236293852380899979151260836670423218871805674446000309373481725774969422672736229527525591328471860345983778028010745586148340546463680818388894336222353977838015397994043740268968888435671821802946193800752173055888706754526261663215087248329005557071106096518012133237897251421810710854712833248875972001538173403966229724632452895508035768462851571544231619079557987628227178358
'''

  • 这题主要是泄露一个式子，这个式子是如下：
    • 其中y=t+1=2u+1y=t+1=2u+1
    • 其中x=ϕ(n)−1=n−(p+q)x=\phi(n) - 1=n-(p+q)

(x2+1)∗(y2+1)−2∗(x−y)∗(x∗y−1)=4∗(k+x∗y)(x^2 + 1)*(y^2 + 1) - 2*(x - y)*(x*y - 1) = 4*(k + x*y)

  • 直接用sagemath的factor可以对该式子进行因式分解。
1
2
3
4
5
6
7
k = 
P.<x,y> = PolynomialRing(ZZ)
f = (x**2 + 1)*(y**2 + 1) - 2*(x - y)*(x*y - 1) - 4*(k + x*y)
factor(f)
"""
(x*y - x + y - 1393877055949269988542645243428109045917075304843782382429915848142225727784284860406937870535551533051449256287300948442808942235566781014699146291793792925479262054554450802027947079006020306843696147659466308841224513975724013909879952955470681477050304932332200438588432205712615761105027582981141051388392159273596829524704974472089813228846063327501722097548108345551791276998575277090833776802524595075326766440599729740043377678343501840792538888378631673472796302603318988296687557395913791350975450144017092753174292943668507487115213145616331361471787389920378850483532964105278405545043850373460301697589493241) * (x*y - x + y + 1393877055949269988542645243428109045917075304843782382429915848142225727784284860406937870535551533051449256287300948442808942235566781014699146291793792925479262054554450802027947079006020306843696147659466308841224513975724013909879952955470681477050304932332200438588432205712615761105027582981141051388392159273596829524704974472089813228846063327501722097548108345551791276998575277090833776802524595075326766440599729740043377678343501840792538888378631673472796302603318988296687557395913791350975450144017092753174292943668507487115213145616331361471787389920378850483532964105278405545043850373460301697589493239)
"""

(x∗y−x+y−a)∗(x∗y−x+y+a)⇒x∗y−x+y−a=0     x∗y−x+y+a=0(舍)\begin{array}{l}(x*y-x+y-a)*(x*y-x+y+a)\\ \Rightarrow x*y-x+y-a=0\\ ~~~~~x*y-x+y+a=0(舍) \end{array}

  • 接下来就可以列方程了求解：

{x∗y−x+y−a=0x=n−(p+q)n=pqy=2u+1⇒{x∗(2u+1)−x+(2u+1)−a=0n=pqx=n−(p+q)\begin{cases} x*y-x+y-a=0\\ x = n-(p+q)\\ n=pq\\ y=2u+1 \end{cases} \Rightarrow \begin{cases} x*(2u+1)-x+(2u+1)-a=0 \\n=pq \\x=n-(p+q) \end{cases}

  • 具体exp如下：
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
from Crypto.Util.number import *
import gmpy2
import tqdm
n =
e = 
c = 
b = 
candidate = []
for i in range(2^15,2^16-1):
    if isPrime(i):
        candidate.append(i)
#print(candidate)
x,y= var('x,y')
sol = 0
for j in tqdm.tqdm(candidate,leave=True):
    eq1 = y == j*2+1
    eq2 = x*y-x+y-b==0
    result = solve([eq1,eq2],[x,y])
    a = int(result[0][0].rhs())
    d = a*(j*2+1)-a+(j*2+1)-b
    if d==0:
        sol = a
        print(a)
        break

p,q = var('p,q')
eq3 = p*q==n
eq4 = n-(p+q) == sol
res = solve([eq3,eq4],[p,q])
p = int(res[0][0].rhs())
q = n//p

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))
# VNCTF{hell0_rsa_w0rld!}

Schnorr

  • 题目附件如下：
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
from Crypto.Util.number import bytes_to_long, isPrime
from hashlib import sha256
#from secret import flag, init_seed
flag = 'flag'
init_seed = 1
class SecureSchnorrProver:
    # 构造方法: 初始化具有加密安全随机性的Schnorr协议以
    def __init__(self, security_bits: int = 512):
        """
        Initialize Schnorr protocol with cryptographically secure randomness
        """
        self._init_deterministic_rng(init_seed) # 初始化随机数
        
        self.p = self._get_prime(security_bits) # 生成512位的素数
        self.g = self._get_random_element()     # 生成一个生成元,在[2,p-2]范围内
        
        # Secret from flag (witness for discrete log problem)
        self.secret_a = bytes_to_long(flag.encode()) % (self.p - 1)  # 将flag作为秘密 a
        
        # Public key (statement of the discrete log problem) # 计算公钥 A = g^{a} % p
        self.A = pow(self.g, self.secret_a, self.p)

    # 构造方法有出现,计算种子的哈希值,初始化counter
    def _init_deterministic_rng(self, seed): #
        """
        Initialize CSPRNG with deterministic seed 
        """
        self.rng_state = sha256(str(seed).encode()).digest()
        self.counter = 0

    # 得到安全的随机数
    # data = rng_state + counter
    # counter+=1
    def _get_secure_random_bits(self, bits: int) -> int:
        """
        Get cryptographically secure random bits using seeded CSPRNG
        """
        data = self.rng_state + self.counter.to_bytes(8, 'big')
        self.counter += 1
        
        result = 0
        
        while len(bin(result)[2:]) < bits:
            hash_output = sha256(data).digest()
            result = (result << 256) | int.from_bytes(hash_output, 'big')
            data = hash_output + self.counter.to_bytes(8, 'big')
            self.counter += 1
        
        return result % (1 << bits)
    # 构造方法有出现过,生成随机数
    def _get_prime(self, bits: int) -> int:
        """
        Generate a random prime of specified bit length
        """
        while True:
            num = self._get_secure_random_bits(bits)
            num |= (1 << (bits - 1)) | 1
            
            if isPrime(num):
                return num
    # 构造方法有出现过,生成生成元
    def _get_random_element(self) -> int:
        """
        Get a random element in range [2, p-2]
        """
        return self._get_secure_random_bits(self.p.bit_length() - 1) % (self.p - 2) + 2
    # 运行
    def run(self):
        """
        Execute the Schnorr zero-knowledge proof protocol
        运行Schnorr零知识证明协议
        """
        # Opening statement
        print("=" * 10)
        # 这个挑战中我知道flag
        print("I know the flag for this challenge!")
        # 但是我将证明我知道它
        print("But I will ONLY prove that I know it.")
        # 你从我的证明中获取不了任何信息
        print("You CANNOT extract ANY information about the flag from my proof!")
        print("=" * 10)
        print()
        # 展现公共参数g,p,A
        # Show public parameters
        print("[PUBLIC PARAMETERS]")
        print(f"p = {self.p}")
        print(f"g = {self.g}")
        print(f"A = {self.A}")
        print()
        # flag是指数a,满足A = g^a mod p
        print("Note: The flag is the witness 'a' such that A = g^a mod p")
        print("      where a = bytes_to_long(flag) mod (p-1)")
        print()

        # 统计轮次数
        round_num = 0
        
        while True:
            round_num += 1
            # 第几轮
            print(f"--- Round {round_num} ---")
            print()

            # Commitment phase
            # 生成一个安全的伪随机数b =
            print("[COMMITMENT]")
            b = self._get_secure_random_bits(self.p.bit_length() - 1) % (self.p - 2) + 1
            # 计算 B = g^{b}  mod p ,并生成B
            B = pow(self.g, b, self.p)
            print(f"B = {B}")
            print()
            
            # Challenge phase
            # 挑战如下,如果你是一个诚实的验证着,你应该提供一个随机挑战
            print("[CHALLENGE]")
            print("(If you are an HONEST verifier, you should provide a RANDOM challenge!)")
            print(f"Please provide challenge x (integer: 1 ≤ x ≤ {self.p - 2}):")
            # 尝试输入x,x必须在[1,p-2]之间
            while True:
                try:
                    x = int(input("x = ").strip())
                    if 1 <= x < self.p - 1:
                        break
                    print(f"Invalid! x must be between 1 and {self.p - 2}")
                except (ValueError, EOFError):
                    print("Invalid input!")
                    exit(0)
            
            print()
            #响应
            # Response phase
            print("[RESPONSE]")
            # 计算z = (x*a+b)% p - 1 ,并输入z
            z = (x * self.secret_a + b) % (self.p - 1)
            print(f"z = {z}")
            print()
            # 验证
            # Verification
            print("[VERIFICATION]")
            # g^{z} = A ^ x * B mod p = g ^{x*a+b % p-q}  = g^{ax}*g^{b}
            print("Check if: g^z ≡ A^x · B (mod p)")
            # 计算左边
            left = pow(self.g, z, self.p)
            # 计算右边
            right = (pow(self.A, x, self.p) * B) % self.p
            # 左边等于右边就成功,不等于就认证失败
            if left == right:
                print("✓ Equation holds! This round proves I know the secret with high probability!")
            else:
                print("✗ Verification failed!")
            
            print()
            
            # Ask to continue
            # 询问是否要继续下一轮
            print("Continue to next round? (y/n):")
            choice = input().strip().lower()
            if choice != 'y':
                break
            print()
        
        print()
        print("=" * 10)
        print(f"Protocol completed after {round_num} round(s).")
        print("You learned ZERO knowledge about the flag!")
        print("=" * 10)

if __name__ == "__main__":
    prover = SecureSchnorrProver(security_bits=512)
    prover.run()
  • 这题属于一个零知识证明的题目，是基于离散对数问题的零知识证明题目，附件大致描述如下：
    • 生成一个512位的素数pp，生成一个生成元g∈[2,p−1]g\in[2,p-1]，将flag作为指数（同时也是秘密aa）
    • 通过上面上个量，用户已知g,p,A≡ga mod( p)g,p,A\equiv g^{a}~mod(~p)
    • 接下来会进入一轮证明，每一轮证明都会有如下量：
      • 生成一个随机数b∈[1,p−1]b\in[1,p-1]，并且会计算输出B≡gb mod( p)B\equiv g^{b}~mod(~p)
      • 此时会要求用户输入一个数x∈[1,p−1]x\in [1,p-1]，计算输出z≡(x∗a+b) mod( p−1)z \equiv (x*a+b)~mod(~p-1)
      • 接下来就是进入验证阶段：gz≡Ax⋅B mod( p)g^{z}\equiv A^{x}·B~mod(~p)，如果两边结果相等就说明证明成功
      • 验证的推导就是这样gz≡gax+b≡gax⋅gb≡(ga)x⋅B≡Ax⋅B mod( p)g^{z}\equiv g^{ax+b}\equiv g^{ax}·g^{b}\equiv (g^{a})^{x}·B\equiv A^{x}·B~mod(~p)
      • 归纳一下已知：g,p,A,B,xg,p,A,B,x
    • 这边有个问题，某些随机数是固定的，因为种子每次都一样，经过远程连接p,g,Ap,g,A都是固定的，并且每次BB都是固定的。
  • 这题重点应该在z≡(x∗a+b) mod( p−1)z\equiv (x*a+b)~mod(~p-1)，假设我们收集到两组zz（重新nc一次，从第一次获取，这时bb就会一样的），这样我们交互分别输入x1=1,x2=2x_1=1,x_2=2

{z1≡(x1∗a+b) mod( p−1)z2≡(x2∗a+b) mod( p−1)\begin{cases} z_1\equiv(x_1*a+b)~mod(~p-1)\\ z_2\equiv(x_2*a+b)~mod(~p-1) \end{cases}

  • 此时我们就可以通过这样的数据计算出来aa计算如下：

{z1≡(a+b) mod( p−1)z2≡(2∗a+b) mod( p−1)⇒z2−z1≡a mod( p−1)\begin{cases} z_1\equiv(a+b)~mod(~p-1)\\ z_2\equiv(2*a+b)~mod(~p-1) \end{cases}\Rightarrow z_2-z_1 \equiv a~mod(~p-1)

  • 这样就可以直接得出flag了：
1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
p = 11565557559424798855333327185204068437310136641385409496567722412564615038600900851617108696669858871646341524790068395795451926393494538092546156560682769
g = 5709717688325332497153440522153605353533637683454644113681576752846043064532331863137676063898756084627767432188906997886676715684730693730695936906091975
A = 4075109126848443012116179641277409498928032598430732000322152241884992550579472218626670987682594558001578403106661239073541536564712500451802717571116369
B = 839528130192525498479196454308970890042461603337469455817068565917490873930542949929568677947770767753921850053408870301884485829608926952532972851114534
z1 = 5126408682185857289501793408251290530347266275247495774627779479648526776486060620907045751170023832479804967167488894956624796038122089749883466638659144
z2 = 5126408682185857289501793408251290530347266275247507856050972117936209951513207975663030001582866857246463549745300296061801461774337384147721517521027525
flag = z2-z1 % (p-1)
print(long_to_bytes(flag))
# b'VNCTF{9415658f-8a8e-4cf9-b3f7-07c81df05223}'

HD_is_what

  • 题目附件如下：
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
import os
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
#from secret import FLAG
FLAG = b'test'
# ==========================================
a,b=82 ,57 # 选定两个参数a=82,b=57
p = 2**a * 3**b - 1 # p = 2^a * 3 ^ b - 1
Fp2.<i> = GF(p^2, modulus=x^2+1) # 构造2次扩域
R.<x> = PolynomialRing(Fp2)   # 构造域中的多项式环
# 构造椭圆曲线 y^2 = x^3 + 6*x^2 + x  mod 7592261594411736127573939894551922818228028390244351^2
E_start = EllipticCurve(Fp2, [0,6,0,1,0])
# 告诉程序该椭圆曲线的阶为(p+1)^2,之后获取椭圆曲线的阶时就会直接返回这个数
E_start.set_order((p+1)^2) 

# 获取整个群的一组点,并计算和返回 n * G,其中 n=(p+1)//l
def get_basis(E, l):
        n = (p+1) // l
        return (n*G for G in E.gens())

# 生成两组(P,Q)对
P2, Q2 = get_basis(E_start, 2**a)
P3, Q3 = get_basis(E_start, 3**b)

# 生成bob的密钥,这个密钥的范围为(0,3**b-1)
bobs_key = randint(0,3**b-1)
# 计算KB = P3 + bobs_key*Q3
KB = P3 + bobs_key*Q3
# 构造一条椭圆曲线同源
phiB = E_start.isogeny(KB, algorithm="factored")
# 计算出陪域,也就是同源映射的目标椭圆曲线
EB = phiB.codomain()
# 告诉椭圆曲线的阶
EB.set_order((p+1)**2, num_checks=0)
# 将两个点P2,Q2通过同源映射映射到新曲线上的对应的点
PB, QB = phiB(P2), phiB(Q2)

# 生成alices的密钥,范围在(0,2**a-1)
alices_key = randint(0,2**a-1)
# 计算KA
KA = P2 + alices_key*Q2
# 继续生成一个同源椭圆曲线
phiA = E_start.isogeny(KA, algorithm="factored")
# 获取同源椭圆曲线的表达式
EA = phiA.codomain()
# 告诉椭圆曲线的阶
EA.set_order((p+1)**2, num_checks=0)
# 映射P3,Q3到对应的同源椭圆曲线中
PA, QA = phiA(P3), phiA(Q3)

# Bob在Alice的曲线是重建同一个子群
shared_kernel_B = PA + bobs_key * QA
# 用刚刚算出的核,在Alices的椭圆曲线的同源曲线
phi_shared_B = EA.isogeny(shared_kernel_B, algorithm="factored")
# 获取新构造的同源的椭圆曲线
E_shared_B = phi_shared_B.codomain()
# 取不变的量为作为共享密钥shared_j
shared_j = E_shared_B.j_invariant()

# 计算密钥的哈希值为作为加密flag的key
# 本题的核心点就是获取shared_j
key = sha256(str(shared_j).encode()).digest()
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(pad(FLAG, 16))

# 点转换为列表
# 虚部在前实部在后
# 每个参数形如输出的时候是虚部在第一项,虚部在第二项
# 转换的时候是实部在第一项,虚部在第二项
def point_to_list(P):
    return [int(c) for c in P[0].polynomial()] + [int(c) for c in P[1].polynomial()]
# 多项式环转换为列表
# 每个参数形如输出的时候是虚部在第一项,虚部在第二项
# 转换的时候是实部在第一项,虚部在第二项
def fp2_to_list(x):
    return [int(c) for c in x.polynomial()]

# 获取椭圆曲线y^2=x^3+a4x+a6的两个参数
bob_raw = []
bob_raw += fp2_to_list(EB.a4())
bob_raw += fp2_to_list(EB.a6())
# 获取两个点
bob_raw += point_to_list(PB)
bob_raw += point_to_list(QB)

# 同样的获取alice的两个参数以及PA和QA
alice_raw = []
alice_raw += fp2_to_list(EA.a4())
alice_raw += fp2_to_list(EA.a6())
alice_raw += point_to_list(PA)
alice_raw += point_to_list(QA)

# 将p作为状态,作为LCG的seed
state = int(p)
def next_rand():
    global state
    state = (state * 1664525 + 1013904223) % 2**32
    return state

# 维数为12
dim = 12
# bob的矩阵为12*12的矩阵
# 按一定规律生成矩阵
M_bob = matrix(ZZ, dim, dim)
for r in range(dim):
    for c in range(dim):
        M_bob[r,c] = (next_rand() % 10 + 10) if r == c else (next_rand() % 5)
# 将前面泄露的bob_raw数据转换为向量与矩阵相乘
Y_bob = vector(ZZ, bob_raw) * M_bob 

# Alice也同样如此
M_alice = matrix(ZZ, dim, dim)
for r in range(dim):
    for c in range(dim):
        M_alice[r,c] = (next_rand() % 10 + 10) if r == c else (next_rand() % 5)
Y_alice = vector(ZZ, alice_raw) * M_alice 

# 输出参数
output = {
    "params": {"a": a, "b": b},
    "points": { 
        "Pa": point_to_list(P2),
        "Qa": point_to_list(Q2),
        "Pb": point_to_list(P3),
        "Qb": point_to_list(Q3)
    },
    "bob_obfuscated": [int(x) for x in Y_bob],
    "alice_obfuscated": [int(x) for x in Y_alice],
    "iv": iv.hex(),
    "ciphertext": ciphertext.hex()
}
print(output)
#with open("output.txt", "w") as f:
#    f.write(str(output))

"""
{'params': {'a': 82, 'b': 57}, 'points': {'Pa': [7380850815870338233148512740368733393216750196703188, 5781954610054982624656905099319449213829965338618246, 1486772483200244464773044820638015227748898433862021, 4041742208160696689470310574913121590144200565209905], 'Qa': [2586575241375377553825568347148553107143283928101556, 7320346671385192793231812101943719336977545395447990, 733636809907296631648191211385947621063533411574256, 5605387748200021584999470184847449699679973078488898], 'Pb': [3426033097771937683305003923302157856773113387142756, 985698126496332100172970040944741456419416603351759, 1705990864855260484227941677048030711112818343076291, 2024639615167016143613082316835526849592146176134329], 'Qb': [3210811026802762630650301828332190426691685119105305, 169218263487330523145547468183984807764163462641345, 1011283628296715746489505093400091319095209130170219, 4260482332111897582524427327736011991754995723487706]}, 'bob_obfuscated': [203216789142581305197722930125351051178489832272874948, 103451143990351090548150562828305766374778166367334743, 128385043821113943220154406817301591600434705357425337, 148721712019250874702421429405961145245884308621636284, 107450918943296049650435208380326306041925061431182755, 108464709125122928458164660443532606143146211433427714, 223429435910571460464979624202352016712591253148328955, 158116135335965154112308826699937612715840377818614605, 167803599172317038283177182077091592826307156540816241, 143817839441487927738837134600596555719979620674913418, 186175056475907603625656541033372102161902994275461358, 195952285339273458274453344082354272141798683842481140], 'alice_obfuscated': [183828390298905838118474328843290916454768465327957660, 185807950963310833056459703998531928875591946831486097, 202219550644070674757245934429643890698528180191737908, 214188863260511182820355681072152986957678050102275625, 161269727976229633611717179589472619840461994012715891, 190710353557551571288330244751254081553527339480374966, 136211896733579722427367479142885387075540353041669882, 163011277996214335433775404719035139917392368645665784, 203102808146393180905593010731146445447359500361776599, 131383143356992706106026454760530073612421183793624652, 197453624754216387417629452253283246906315251699375152, 250895715588427247878798824490953369076564145957903096], 'iv': 'e0d8d8692e9c16a4ecfb70c660690a9c', 'ciphertext': 'b07d542002008668e55fba154c8b9cdd11dbc90724ef18cc6868ecc05d27c92b1281c9225e2d231ef4e8d38b7cdd81a2'}
"""

  • 通过大致的阅读代码，大致了解到本题的疑似考点：向量矩阵方程，同源椭圆曲线，以及高等代数的知识还有就是LCG。本题要求的起始就是j-invariant也就是j不变量

  • 接下来就按顺序描述一下这个代码的大致过程：

    • 题目给出了一个有限域p=282∗357−1p=2^{82} * 3^{57} - 1，本题是在域Fp2F_{p^2}下的超奇异椭圆曲线。

    y2=x3+6∗x2+x mod( 75922615944117361275739398945519228182280283902443512)y^2 = x^3 + 6*x^2 + x ~mod (~7592261594411736127573939894551922818228028390244351^2)

    • 接下来通过alices、bob，生成的随机数计算点：KBK_B和KAK_A，通过KAK_A和KBK_B构造同源映射ϕA、ϕB\phi_A、\phi_B，这样就可以得到两条映射后的椭圆曲线：

    EϕA:y2=x3+6x2+a4Ax+a6AEϕB:y2=x3+6x2+a4Bx+a6BE_{\phi_A}:y^2=x^3+6x^2+a_{4A}x+a_{6A} \\E_{\phi_B}:y^2=x^3+6x^2+a_{4B}x+a_{6B}

    • 然后接下来就是对于Bob来说：

    ShareB=PA+kBQAShare_B= P_A+k_BQ_A

    • 利用ShareBShare_B就获得令一个同源映射ϕBA\phi_{BA}，该映射也有一个椭圆曲线参数：

    EShare:y2=x3+6x2+a4sharex+a6shareE_{Share}:y^2=x^3+6x^2+a_{4share}x+a_{6share}

    • 最后利用该ShareBShare_B曲线获取j不变量，这个不变量就是加密flag的密钥。

  • 接下来题目会有泄露一些东西，发现泄露的是ϕA\phi_A和ϕB\phi_B映射得到到同源椭圆曲线的参数，以及原曲线上的点分别映射到ϕA、ϕB\phi_A、\phi_B所构成的椭圆曲线上的点坐标QA、PA、QB、PBQ_A、P_A、Q_B、P_B，并且这些参数都是用复数形式a+bia+bi

braw=(a4[0],a4[1],a6[0],a6[1],PBx[0],PBx[1],PBy[0],PBy[1],QBx[0],QBx[1],QBy[0],QBy[1])araw=(a4[0],a4[1],a6[0],a6[1],PAx[0],PAx[1],PAy[0],PAy[1],QAx[0],QAx[1],QAy[0],QAy[1])b_{raw}=(a_{4}[0],a_{4}[1],a_6[0],a_6[1],P_{Bx}[0],P_{Bx}[1],P_{By}[0],P_{By}[1],Q_{Bx}[0],Q_{Bx}[1],Q_{By}[0],Q_{By}[1])\\ a_{raw}=(a_{4}[0],a_{4}[1],a_6[0],a_6[1],P_{Ax}[0],P_{Ax}[1],P_{Ay}[0],P_{Ay}[1],Q_{Ax}[0],Q_{Ax}[1],Q_{Ay}[0],Q_{Ay}[1])

  • 接下来使用伪随机数LCG生成器生成了两个12×12的矩阵A、BA、B，由于种子固定，所以这个矩阵中的元素也是固定的，并且是已知的：

image-20260131175836832

image-20260131180020112

  • 本题的主要考点应该和矩阵相关（极大可能是格密码相关），通过矩阵求解同源曲线的对应参数，进而恢复出j不变量。稍微思考了一下，貌似就是正常求解方程组就行了。

b⃗B=solba⃗A=sola\vec{b}B=sol_b\\ \vec{a}A=sol_a

  • 进而得到，这样相关的参数就可以恢复了

b⃗=solbB−1a⃗=solbA−1\vec{b}=sol_bB^{-1}\\ \vec{a}=sol_bA^{-1}

image-20260131204750029

  • 最后就是解密得到flag了
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import os
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
p = 7592261594411736127573939894551922818228028390244351

state = int(p)
def next_rand():
    global state
    state = (state * 1664525 + 1013904223) % 2**32
    return state
dim = 12
M_bob = matrix(ZZ, dim, dim)
for r in range(dim):
    for c in range(dim):
        M_bob[r,c] = (next_rand() % 10 + 10) if r == c else (next_rand() % 5)
        
M_alice = matrix(ZZ, dim, dim)
for r in range(dim):
    for c in range(dim):
        M_alice[r,c] = (next_rand() % 10 + 10) if r == c else (next_rand() % 5)
solB = [203216789142581305197722930125351051178489832272874948, 103451143990351090548150562828305766374778166367334743, 128385043821113943220154406817301591600434705357425337, 148721712019250874702421429405961145245884308621636284, 107450918943296049650435208380326306041925061431182755, 108464709125122928458164660443532606143146211433427714, 223429435910571460464979624202352016712591253148328955, 158116135335965154112308826699937612715840377818614605, 167803599172317038283177182077091592826307156540816241, 143817839441487927738837134600596555719979620674913418, 186175056475907603625656541033372102161902994275461358, 195952285339273458274453344082354272141798683842481140]


solA = [183828390298905838118474328843290916454768465327957660, 185807950963310833056459703998531928875591946831486097, 202219550644070674757245934429643890698528180191737908, 214188863260511182820355681072152986957678050102275625, 161269727976229633611717179589472619840461994012715891, 190710353557551571288330244751254081553527339480374966, 136211896733579722427367479142885387075540353041669882, 163011277996214335433775404719035139917392368645665784, 203102808146393180905593010731146445447359500361776599, 131383143356992706106026454760530073612421183793624652, 197453624754216387417629452253283246906315251699375152, 250895715588427247878798824490953369076564145957903096]


xB = vector(ZZ,solB)
xA = vector(ZZ,solA)
# 求解方程
BBB = M_bob.solve_left(xB)
AAA = M_alice.solve_left(xA)
AAA = [ZZ(x) % p for x in AAA]
BBB = [ZZ(x) % p for x in BBB]

print('AAA=',AAA)
print()
print('BBB=',BBB)
# 恢复参数
a,b=82 ,57 
p = 2**a * 3**b - 1 
Fp2.<i> = GF(p^2, modulus=x^2+1) 
R.<x> = PolynomialRing(Fp2)   
E_start = EllipticCurve(Fp2, [0,6,0,1,0])
a4_A = Fp2(AAA[0]) + Fp2(AAA[1]) * i
a6_A = Fp2(AAA[2]) + Fp2(AAA[3]) * i
a4_B = Fp2(BBB[0]) + Fp2(BBB[1]) * i
a6_B = Fp2(BBB[2]) + Fp2(BBB[3]) * i
EA = EllipticCurve(Fp2, [0, 6, 0, a4_A, a6_A])
EB = EllipticCurve(Fp2, [0, 6, 0, a4_B, a6_B])

print(EA)
print(EB)
P_Ax = Fp2([AAA[4],AAA[5]]) #+ Fp2(AAA[5]) * i
P_Ay = Fp2([AAA[6],AAA[7]]) #+ Fp2(AAA[7]) * i
Q_Ax = Fp2(AAA[8]) + Fp2(AAA[9]) * i
Q_Ay = Fp2(AAA[10]) + Fp2(AAA[11]) * i
P_Bx = Fp2(BBB[4]) + Fp2(BBB[5]) * i
P_By = Fp2(BBB[6]) + Fp2(BBB[7]) * i
Q_Bx = Fp2(BBB[8]) + Fp2(BBB[9]) * i
Q_By = Fp2(BBB[10]) + Fp2(BBB[11]) * i
PA = EA(P_Ax, P_Ay)
PB = EB(P_Bx, P_By)
QA = EA(Q_Ax, Q_Ay)
QB = EB(Q_Bx, Q_By)
bobs_key = 10886546902217234201381501
shared_kernel_B = PA + bobs_key * QA
# 用刚刚算出的核,在Alices的椭圆曲线的同源曲线
phi_shared_B = EA.isogeny(shared_kernel_B, algorithm="factored")
# 获取新构造的同源的椭圆曲线
E_shared_B = phi_shared_B.codomain()
# 取不变的量为作为共享密钥shared_j
shared_j = E_shared_B.j_invariant()

# 计算密钥的哈希值为作为加密flag的key
# 本题的核心点就是获取shared_j
key = sha256(str(shared_j).encode()).digest()
iv = 'e0d8d8692e9c16a4ecfb70c660690a9c'
iv = bytes.fromhex(iv)
ct = bytes.fromhex('b07d542002008668e55fba154c8b9cdd11dbc90724ef18cc6868ecc05d27c92b1281c9225e2d231ef4e8d38b7cdd81a2')
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
print(flag)
# b'VNCTF{wo_buzhidao_shuoshenmo_zhejiushiFLAG}\x05\x05\x05\x05\x05'
  • 这边也附上一个修改后的恢复密钥脚本
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# Local imports
import public_values_aux
from public_values_aux import *

# Load Sage files
load('castryck_decru_shortcut.sage')

# Baby SIKEp64 parameters
a = 82
b = 57

# Set the prime, finite fields and starting curve
# with known endomorphism
p = 2^a*3^b - 1
public_values_aux.p = p

Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)

E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2) # Speeds things up in Sage

# Generation of the endomorphism 2i
two_i = generate_distortion_map(E_start)

# Generate public torsion points, for SIKE implementations
# these are fixed but to save loading in constants we can
# just generate them on the fly
#P2, Q2, P3, Q3 = generate_torsion_points(E_start, a, b)
#check_torsion_points(E_start, a, b, P2, Q2, P3, Q3)

# Generate Bob's key pair
#bob_private_key, EB, PB, QB = gen_bob_keypair(E_start, b, P2, Q2, P3, Q3)
#solution = Integer(bob_private_key).digits(base=3)

print(f"Running the attack against Baby SIDHp64 parameters, which has a prime: 2^{a}*3^{b} - 1")
#print(f"If all goes well then the following digits should be found: {solution}")

# ===================================
# =====  ATTACK  ====================
# ===================================
BBB= [6980879823713977230088481552851762479947956999588439, 454638990445894111337435111797349961437910869483074, 5506041012553788721252726674071908328286902172346972, 341431269109523876762511804745267620243077067992008, 932143382127805288292801471320422556894186185417332, 3154333410000897808841106189404794449901091740165379, 6558662418603825667456120287644417773016448829400646, 7463035382787605971237359354459346935821497250275167, 4823880665248255194552866921491026859391910070468517, 3169002404673168544133803290589938191676939083376700, 6358995594641549992207738546437351624432542820686659, 7049770895382681008763684737833691774249403185417335]
PA = [7380850815870338233148512740368733393216750196703188, 5781954610054982624656905099319449213829965338618246, 1486772483200244464773044820638015227748898433862021, 4041742208160696689470310574913121590144200565209905]
QA = [2586575241375377553825568347148553107143283928101556, 7320346671385192793231812101943719336977545395447990, 733636809907296631648191211385947621063533411574256, 5605387748200021584999470184847449699679973078488898]
PB = [3426033097771937683305003923302157856773113387142756, 985698126496332100172970040944741456419416603351759, 1705990864855260484227941677048030711112818343076291, 2024639615167016143613082316835526849592146176134329]
QB = [3210811026802762630650301828332190426691685119105305, 169218263487330523145547468183984807764163462641345, 1011283628296715746489505093400091319095209130170219, 4260482332111897582524427327736011991754995723487706]
P2x = Fp2(PA[0]) + Fp2(PA[1]) * i
P2y = Fp2(PA[2]) + Fp2(PA[3]) * i
Q2x = Fp2(QA[0]) + Fp2(QA[1]) * i
Q2y = Fp2(QA[2]) + Fp2(QA[3]) * i
P2 = E_start(P2x, P2y)
Q2 = E_start(Q2x, Q2y)
PBx = Fp2(PB[0]) + Fp2(PB[1]) * i
PBy = Fp2(PB[2]) + Fp2(PB[3]) * i
QBx = Fp2(QB[0]) + Fp2(QB[1]) * i
QBy = Fp2(QB[2]) + Fp2(QB[3]) * i
P3 = E_start(PBx, PBy)
Q3 = E_start(QBx, QBy)
a4_B = Fp2(BBB[0]) + Fp2(BBB[1]) * i
a6_B = Fp2(BBB[2]) + Fp2(BBB[3]) * i
P_Bx = Fp2(BBB[4]) + Fp2(BBB[5]) * i
P_By = Fp2(BBB[6]) + Fp2(BBB[7]) * i
Q_Bx = Fp2(BBB[8]) + Fp2(BBB[9]) * i
Q_By = Fp2(BBB[10]) + Fp2(BBB[11]) * i
EB = EllipticCurve(Fp2, [0, 6, 0, a4_B, a6_B])
PB = EB(P_Bx, P_By)
QB = EB(Q_Bx, Q_By)
def RunAttack(num_cores):
    return CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=num_cores)
    #return CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=num_cores)

if __name__ == '__main__' and '__file__' in globals():
    if '--parallel' in sys.argv:
        # Set number of cores for parallel computation
        num_cores = os.cpu_count()
        print(f"Performing the attack in parallel using {num_cores} cores")
    else:
        num_cores = 1
    recovered_key = RunAttack(num_cores)

NumberGuesser*

  • 题目附件如下：
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
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
#from secret import flag
import random
import os
flag = 'test_flag'
class NumberGuesser:
    def __init__(self,MAX_CHANCES: int = 10, n: int = 624):
        self.MAX_CHANCES = MAX_CHANCES
        self.n = n
        self.seed = os.urandom(8)
        random.seed(self.seed)

        self.hints = [random.getrandbits(32) for _ in range(self.n)]
        self.enc = self.encrypt_flag(flag,self.seed)

    def encrypt_flag(self,flag: str, iv:bytes) -> bytes:
        key = random.getrandbits(128).to_bytes(16,'big')
        ct = AES.new(key,AES.MODE_CBC,iv*2).encrypt(pad(flag.encode(), AES.block_size))
        return ct
    
    def banner(self):
        print("=== Number Guess Challenge ===")
        print(f"- Internally generates {self.n} 32-bit random numbers")
        print(f"- You may query at most {self.MAX_CHANCES} indices (0 ~ {self.n - 1})")
        print("- The seed is 8 bytes of true randomness, influencing AES-CBC key generation\n")
        print("Encrypted flag:")
        print(self.enc.hex(), "\n")

    def query_loop(self):
        for CHANCES in range(1, self.MAX_CHANCES + 1):
            print(f"[{CHANCES}/{self.MAX_CHANCES}]")
            try:
                index = int(input(f"Enter index (0~{self.n - 1}): ").strip())
                if 0 <= index < self.n:
                    print(f"hint[{index}] = {self.hints[index]}\n")
                else:
                    print("Index out of range.\n")
            except ValueError:
                print("Invalid input. Please enter an integer.\n")       
        print("Query phase ended. Use the hints to recover the PRNG state and decrypt the flag.")

    def run(self):
        self.banner()
        self.query_loop()

if __name__ == "__main__":
    NumberGuesser().run()
  • 这题本质上就是MT19937伪随机数预测，但是这题条件限制的比较死。晚上睡不着，搜索了一下关于mt19937的相关知识点，发现这题可能与旋转状态有关，通过看题目附件大致说一下题目的过程：
    • 先初始化一下，首先就是随机生成8字节，作为随机数的种子。
    • 然后就是生成624组32位的随机数（注意生成完之后就会进行状态扭转）
    • 接下来就生成一个128位的随机数，其实就是4组32位的随机数（应该是按照先生成的随机数放在最低位），这里还要注意一点，题目会将种子作为向量iv与128位的随机数一起参与加密flag。
    • 此时用户能查询10次，这样没有足够的位数可以使用一些库去一把梭，很大可能就是逆向状态扭转函数。
  • 首先我们看一下MT19937的旋转状态函数：
    • 发现旋转的时候需要用上mt[0]、mt[1]、mt[2]、mt[3]、mt[4]mt[0]、mt[1]、mt[2]、mt[3]、mt[4]，还需要用上mt[397]、mt[398]、mt[399]、mt[400]mt[397]、mt[398]、mt[399]、mt[400]
    • 有了上述的状态应该就能恢复部分的状态了，但是上面查询的次数才9次，而题目给了10次查询机会。最后一次查询可能是用于恢复种子的。
1
2
3
4
5
6
7
8
def twist(self):
    for i in range(0, 624):
        y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
        self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

        if y % 2 != 0:
            self.mt[i] = self.mt[i] ^ 0x9908b0df

  • 预测接下来的128位难度不大，难度主要在于逆向种子，关键在于这个函数，看了sean师傅的博客MT19937 - SeanDictionary | 折腾日记，发现有python中MT19937的具体Python代码：
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
class Py_MT19937:
    def __init__(self, seed):
        # 传入的种子,如果种子大于32位，就会对种子分组32位一组
        key = []
        while seed > 0:
            key.append(seed & 0xFFFFFFFF)
            seed >>= 32
        # 初始化mt矩阵
        self.mt = [0] * 624
        self.mti = 0
        # 调用_init_by_array
        self._init_by_array(key, len(key))

    def _int32(self, x):
        return int(0xFFFFFFFF & x)
	
    def _init_genrand(self, seed):
        self.mt[0] = seed
        for i in range(1, 624):
            self.mt[i] = self._int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)

    def _init_by_array(self, init_key, key_length):
        # 先会使用固定的数19650218初始化mt状态矩阵
        self._init_genrand(19650218)
        i = 1
        j = 0
        k = max(624, key_length)
        # 接下来在用key数组初始化状态矩阵
        for _ in range(k):
            self.mt[i] = self._int32((self.mt[i] ^ ((self._int32(self.mt[i - 1]) ^ (self._int32(self.mt[i - 1]) >> 30)) * 1664525)) +init_key[j] + j)
            i += 1
            j = (j + 1) % key_length
            if i >= 624:
                self.mt[0] = self.mt[623]
                i = 1
		# 然后再进行一定的变换
        for _ in range(623):
            self.mt[i] = self._int32((self.mt[i] ^ ((self._int32(self.mt[i - 1]) ^ (self._int32(self.mt[i - 1]) >> 30)) * 1566083941)) - i)
            i += 1
            if i >= 624:
                self.mt[0] = self.mt[623]
                i = 1
        # 之后设置mt[0]为固定的数
        self.mt[0] = 0x80000000

  • 这边发现种子会参与状态矩阵的初始化，但是这边还有一个问题，当我们第一次调用getrandbits()的时候，就会直接进行状态旋转，所以我们还需要求出状态旋转之前的矩阵，已知状态旋转前的mt[0]= 0x80000000。

  • 在扭转之前的mt[1]和mt[2]就有关于种子的信息，而在mt[0]是由self._init_genrand(19650218)初始化之后得到的信息。

  • 所以我们要求种子，就需要先求mt[1]和mt[2]，而这两个状态在旋转的时候与旋转之前的mt[1]、mt[2]、mt[3]、mt[398]、mt[399]有关

  • 而mt[398]和mt[399]会与旋转之前的mt[398]、mt[399]、mt[400]有关，还会与旋转之后的mt[171]、mt[172]有关，这样的话感觉已知信息不够，可能只能约束求解爆破？

  • 但是我们知道旋转之前的mt[0]=0x80000000，并且知道旋转之后的mt[0]，我们最多是能恢复旋转之后mt[397]，要恢复mt[397]，我们就需要已知mt[397]，以及旋转后的mt[170]。虽然我们不知道旋转前的mt[398]，但是可以求。

1
2
3
4
5
6
7
def twist(self):
    for i in range(0, 624):
        y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
        self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

        if y % 2 != 0:
            self.mt[i] = self.mt[i] ^ 0x9908b0df

ezov*

  • 题目附件如下：
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
# from hashlib import shake_128
import sys
import os

class OV:
    def __init__(self, o, v, q, key=None):
        self.params = (o, v, q) # 初始化三个参数
        self.F = GF(q) 
        # 当没有公私钥的时候就自己生成一个,有的话就用传入的
        self.pub, self.priv = self.keygen() if key == None else key
    # 哈希函数,shake_128
    def Hash(self, msg):
        h = shake_128(msg).hexdigest(128)
        # 返回的是一个向量,该向量就是哈希值每2字节转换成整数,shake_128中的128表示128字节
        # 所以这个向量的分量有128//2
        #print(h)
        x = vector(self.F, [int(h[i:i+4], 16) for i in range(0,len(h),4)])
        print(len(x))
        return x
        
    # 密钥生成操作    
    def keygen(self):
        o, v, q = self.params
        n = o + v
        Fs = []
        Ps = []

        while True:
            # 生成私钥之一T
            T = random_matrix(self.F, n, n)
            #判断T是否可逆,需要满足T可逆
            if T.is_invertible():
                break
        # 生成64个公钥
        for _ in range(o):
            while True:
                # 随机生成GF(q)下的 64*64的矩阵
                Qvv = random_matrix(self.F, v, v)
                # 求其对应的逆矩阵,强制转换为对称矩阵,在对应的GF(q)中
                Qvv = self.F(2)^(-1) * (Qvv + Qvv.transpose()) 
                # 随机生成64*64的矩阵
                Qvo = random_matrix(self.F, v, o)
                # 使用矩阵分块的形式定义矩阵128*128的矩阵?
                Q = block_matrix(self.F, [[Qvv, Qvo], [Qvo.transpose(), 0]])
                # 判断是否是可逆矩阵
                if Q.is_invertible():
                    break
            # 私钥就是Q
            Fs.append(Q)
            # 公钥是T * Q * T
            Ps.append(T.transpose() * Q * T)

        return Ps, (Fs, T)
    # 进行签名操作
    def sign(self, msg):
        # 相关参数
        o, v, q = self.params
        # 接收私钥
        Fs, T = self.priv
        # n = 64 + 64 = 128
        n = o + v
        # 计算签名传过来的msg参数
        M = self.Hash(msg.encode())
        # 定义一个多项式环,有o个变量
        PR = PolynomialRing(self.F, 'x', o)
        # 取出该环的生成元
        X_oil = PR.gens()
        while True:
            # 随机生成一个1*64的矩阵
            V = random_vector(self.F, v).list()
            # 生成一个向量,前64是数字,后64是o个变量的多项式环
            Y = vector(PR, V + list(X_oil))
            print(Y)
            L = []
            B = []
            for i in range(o):
                # 应该是计算一个二次型矩阵
                tmp = Y*Fs[i]*Y
                # 提取该多项式的前64个系数
                L.append([tmp.coefficient(X_oil[j]) for j in range(o)])
                B.append(tmp([0 for _ in range(o)]))
                
            # 转换为GF(q)下的矩阵L
            L = matrix(self.F, L)
            # 定义向量B
            B = vector(B)
            # target = M - B
            target = M - B
            # 判断L是否可逆
            if L.is_invertible():
                # 求解LX = target
                X_oil = L.solve_right(target)
                # 生成Y
                Y = vector(self.F, V + list(X_oil))
                # 接下来就是计算并返回矩阵相乘
                return T.inverse() * Y
        

    def verify(self, msg, token):
        # 计算消息的哈希值
        msg = self.Hash(msg.encode())
        # 将用户的签名值传入进来,转换成一个向量
        t = vector(token)
        # 进行验证
        for i in range(self.params[0]):
            if t*self.pub[i]*t != msg[i]:
                return False
        return True

# 菜单
def menu():
    print('[+] 1. sign')
    print('[+] 2. verify')

def main():
    # 获取flag
    flag = os.getenv('A1CTF_FLAG')
    # 定义 o,v
    o, v = 64, 64
    # n = o + v = 128
    n = o+v
    # q = 65537
    q = 0x10001
    # 打开公钥文件
    pub = []
    with open('pub.txt', 'r') as file:
        for i in range(o):
            file.readline()
            # 构造公钥矩阵
            pub.append(matrix(GF(q), eval(''.join([file.readline().strip() for _ in range(n)]))))

    # Fs目前是什么还不明白
    Fs = []
    T = None
    # 打开秘密,继续构造矩阵,Fs应该是用秘密构造的矩阵
    with open('secret.txt', 'r') as file:
        for i in range(o):
            file.readline()
            Fs.append(matrix(GF(q), eval(''.join([file.readline().strip() for _ in range(n)]))))
        # T也是用秘密构造的矩阵
        file.readline()
        T = matrix(GF(q), eval(''.join([file.readline().strip() for _ in range(n)])))
    # 私钥
    priv = (Fs, T)
    # 创建OV类,传递(64,64,65537),并且会传入公钥矩阵和私钥矩阵
    ov = OV(o, v, q, key=(pub, priv))
    
    ov = OV(o, v, q)
    # 开始挑战
    while True:
        menu()
        try:
            choice = int(input('>'))
            # 选项1是签名
            if choice == 1: 
                # 输入消息
                msg = input('your msg:')
                # 对消息进行数据类型的处理
                if isinstance(msg, bytes): msg = msg.decode()
                # 如果要签名的消息是admin,直接报错
                if msg == 'admin': raise RuntimeError
                # 对消息进行签名操作
                sig = ov.sign(msg)
                print(f' signature: {sig}')
            # 选项2是认证,如果是admin身份就会打印出flag
            if choice == 2:
                sig = input('your signature:').strip()[1:-1]
                if isinstance(sig, bytes): sig = sig.decode()
                sig = vector(GF(q), [int(_.strip()) for _ in sig.split(',')])
                if ov.verify('admin', sig): print(flag)
        except:
            print('error!')
            sys.exit()

if __name__ == "__main__":
    main()

PWN