2025强网杯密码

发表于 更新于 阅读次数： 本文字数： 33k 阅读时长 ≈ 1:01

ovo

记录一下今年强网杯的密码题(零解除外)，唉拼尽全力只能做出两道，明明只差一点。空悲切了

check-little

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
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import os

flag, key = open('secret').read().split('\n')

e = 3

while 1:
    p = getPrime(1024)
    q = getPrime(1024)
    phi = (p - 1) * (q - 1)
    if phi % e != 0:
        break
N = p * q
c = pow(key, e, N)

iv = os.urandom(16)
ciphertext = AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC).encrypt(pad(flag.encode(),16)).hex()

f = open('output.txt', 'w')
f.write(f'N = {N}\n')
f.write(f'c = {c}\n')
f.write(f'iv = {iv}\n')
f.write(f'ciphertext = {ciphertext}\n')
"""
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2
"""

做了半个小时没做出来，结果ai跟我说n和c有公因数……

用p=gcd(N,c)解密即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Cryptodome.Util.number import *
from Cryptodome.Cipher import AES
import gmpy2
from tqdm import trange

n= 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c= 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
e=3
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
cc = "bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2"
cc = bytes.fromhex(cc)
print(gmpy2.gcd(n,c))
p = gmpy2.gcd(n,c)
q = n // p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
key = pow(c,d,n)
key = long_to_bytes(key)
key = key[:16]
aes = AES.new(key, AES.MODE_CBC, iv=iv)
m = aes.decrypt(cc)
print(m)

ezran

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from random import *

f = open('flag.txt', 'r')
flag = f.read().encode()

gift=b''
for i in range(3108):
    r1 = getrandbits(8)
    r2 = getrandbits(16)
    x=(pow(r1, 2*i, 257) & 0xff) ^ r2
    c=long_to_bytes(x, 2)
    gift+=c

m = list(flag)
for i in range(2025):
    shuffle(m)

c = "".join(list(map(chr,m)))

f = open('output.txt', 'w')
f.write(f"gift = {bytes_to_long(gift)}\n")
f.write(f"c = {c}\n")

看到题目的第一时间就想到了鸡块师傅博客里的这道题2024-同济大学第二届网络安全新生赛CatCTF-wp-crypto | 糖醋小鸡块的blog，之前学MT19937的时候复现过这道题。这次试了半天发现用博客里造矩阵的方法没法做，只能使用高科技-gf2bv，又因为矩阵不满秩所以需要用solve_all函数求出所有解之后进行check，最后按照索引重新shuffle2025次即可

贴一下ai的丑陋脚本

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
# -*- coding: utf-8 -*-
# 需要: pip install gf2bv
# 运行: python solve_qr257_gf2bv_all.py

import random
from contextlib import contextmanager
from time import perf_counter

from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937


# ===================== 数据：把完整 gift 列表与 c 放进来 =====================
gift = [26511, 54008, 13307, 8478, 2141, 61223, 45589, 19936, 32825, 30951, 30918, 50149, 19750, 54877, 22861, 62501, 13526, 706, 37499, 32195, 10221, 37595, 18296, 35837, 6650, 44508, 34430, 21597, 27211, 17960, 27850, 11030, 33102, 23433, 14903, 5435, 50926, 46507, 22381, 59197, 10880, 18688, 2772, 26467, 31973, 21721, 24876, 58237, 61590, 14369, 62682, 13317, 42941, 26835, 60273, 41629, 11504, 45026, 58496, 34920, 22674, 39055, 28612, 21960, 40181, 30584, 54277, 46774, 2021, 31497, 53579, 16826, 63545, 41628, 22160, 22737, 21657, 39743, 42226, 47966, 27190, 41233, 8843, 30525, 63089, 30331, 55114, 40193, 6705, 51285, 4399, 11071, 17212, 12944, 26725, 11306, 10875, 44200, 28184, 55879, 22882, 55668, 30540, 20729, 57337, 37353, 23268, 21297, 39593, 48343, 32670, 54287, 37630, 39219, 27588, 38061, 49533, 14883, 14691, 29492, 3871, 51322, 15152, 49813, 31650, 49293, 16373, 52605, 61872, 23979, 14970, 50305, 44673, 54837, 3079, 40950, 55357, 49868, 11240, 64576, 10377, 8526, 4280, 51468, 6982, 37776, 43346, 63385, 48754, 55045, 15341, 48171, 28614, 2895, 2024, 50175, 16532, 29693, 58490, 58000, 44661, 64760, 37690, 40520, 50596, 60074, 63124, 64013, 52516, 13754, 9754, 41102, 45707, 11039, 60816, 45005, 197, 29106, 3687, 49888, 65340, 41473, 9896, 57126, 56740, 12515, 5434, 33547, 34733, 52176, 26870, 40661, 36333, 23660, 35166, 64307, 49477, 2454, 42447, 56744, 14919, 23698, 49381, 19007, 33910, 60542, 27161, 58741, 588, 41094, 21115, 42138, 47237, 34291, 47472, 782, 44252, 38635, 42367, 57998, 17821, 60898, 51859, 24591, 37351, 1401, 15009, 4331, 7209, 7328, 63299, 42270, 22834, 20675, 49283, 10501, 15251, 24382, 49746, 5450, 40329, 33173, 1263, 27176, 59555, 49117, 14881, 33916, 8829, 29693, 2580, 42192, 11354, 12920, 387, 16268, 52063, 43090, 2652, 19724, 7861, 33474, 27694, 18840, 10, 15138, 48830, 53574, 48428, 24492, 15537, 42612, 19125, 36953, 12201, 22640, 28351, 46319, 24355, 65114, 59227, 17233, 54166, 11294, 62919, 44431, 4338, 5832, 13513, 52242, 45596, 11974, 13, 21052, 64536, 47570, 47422, 1909, 59106, 53386, 44586, 16324, 12674, 48875, 49471, 51752, 6511, 548, 23370, 45982, 6629, 29080, 4884, 28505, 51228, 44702, 17907, 17144, 61846, 41915, 28711, 16364, 13221, 15865, 9416, 4376, 9332, 28278, 32302, 42625, 1769, 52742, 34413, 45908, 49843, 52988, 9895, 29982, 20310, 27823, 7635, 51405, 19226, 29310, 65251, 13572, 27252, 62854, 34865, 20005, 65408, 11182, 60336, 23586, 52563, 59726, 42794, 58649, 43436, 57053, 15694, 64553, 11931, 64573, 63383, 10293, 25251, 27377, 39307, 45857, 31847, 3095, 49971, 31275, 52558, 36638, 13407, 57091, 35363, 36860, 40638, 14496, 50228, 17920, 47622, 3992, 31105, 30328, 29415, 35763, 2690, 13329, 3017, 37525, 36050, 40857, 35865, 45703, 63383, 35375, 12833, 26089, 36909, 2431, 17601, 59049, 28476, 53276, 61137, 54341, 24353, 49020, 51032, 46861, 38218, 53063, 6869, 65363, 607, 41931, 39337, 9649, 38302, 11803, 23569, 2650, 62972, 37514, 60429, 64631, 33492, 53602, 43159, 1911, 8816, 15836, 45740, 59317, 12554, 46682, 44329, 55296, 53934, 56245, 52262, 51277, 14889, 19724, 44920, 35727, 17885, 9283, 65262, 56330, 51052, 11183, 16790, 43600, 28791, 21426, 23979, 52302, 55369, 44951, 54978, 20650, 12732, 21271, 42276, 13732, 38568, 32743, 5575, 21073, 590, 60428, 18392, 38571, 2019, 29922, 32080, 23839, 29559, 64237, 62068, 36074, 19861, 16792, 58185, 28971, 55169, 3753, 39731, 12798, 44885, 53794, 38802, 34907, 58385, 57998, 25691, 46871, 56095, 61397, 46381, 8234, 62153, 11212, 40926, 24292, 22337, 47931, 20619, 33645, 53305, 56435, 19230, 2373, 43195, 23325, 41143, 22227, 46759, 33747, 13881, 22148, 6961, 20533, 58445, 39497, 7239, 10513, 64473, 7965, 8990, 25103, 65506, 28310, 48945, 8806, 45901, 28887, 39931, 7639, 46138, 46046, 3426, 6132, 36713, 59226, 19281, 60391, 59551, 6191, 10482, 2634, 20366, 48300, 305, 1015, 19838, 52562, 22072, 10304, 36880, 15038, 24241, 42370, 14183, 33762, 27005, 18450, 57039, 6727, 44169, 23678, 62029, 51831, 4136, 9923, 11886, 16884, 58446, 55057, 61931, 27324, 61514, 29116, 16302, 17198, 29934, 5602, 10922, 16798, 61068, 60948, 3104, 3181, 43006, 34647, 22038, 31427, 41301, 4512, 29353, 59717, 20650, 35786, 48654, 12144, 42724, 7559, 50161, 29951, 35949, 37015, 36269, 1489, 474, 34615, 41575, 18066, 31564, 18673, 6660, 57787, 19768, 52851, 3750, 39227, 12582, 63885, 22276, 48366, 671, 63186, 8799, 13931, 9652, 21755, 31275, 28497, 54240, 45313, 44508, 36546, 38318, 43949, 39083, 50689, 37945, 20200, 58768, 14530, 47581, 41877, 33711, 59686, 58907, 8738, 13809, 42046, 43404, 19898, 31987, 41251, 17922, 49962, 21631, 28398, 58231, 10943, 55202, 27179, 60545, 58536, 52937, 35878, 19000, 35982, 52381, 15216, 60890, 47736, 21925, 14302, 9245, 15041, 64398, 38396, 24440, 50904, 45951, 57564, 1450, 46671, 20595, 16013, 47128, 24155, 40632, 58945, 50239, 10949, 34406, 19452, 61055, 29887, 56069, 44764, 61246, 57615, 23822, 21887, 6591, 25935, 41697, 22934, 40880, 50195, 4384, 35287, 7391, 57665, 48592, 5066, 56641, 4767, 27673, 46749, 59566, 3649, 54402, 43133, 22983, 64737, 30207, 26958, 32125, 43227, 51576, 29891, 11598, 33230, 62456, 55337, 56361, 36027, 26637, 34808, 6337, 28088, 27902, 20511, 65505, 38236, 640, 2336, 17847, 24518, 13771, 43211, 37738, 13234, 42394, 44372, 36504, 25427, 32539, 36650, 51513, 35049, 36018, 12262, 1737, 52983, 32218, 3269, 13794, 23782, 25814, 44548, 5886, 55094, 7473, 32630, 23011, 52361, 65169, 50422, 32304, 49827, 5191, 50470, 36781, 61868, 2519, 28607, 55305, 43373, 50686, 50162, 16485, 62035, 60680, 49199, 34995, 26004, 51398, 58415, 6202, 52920, 22375, 33645, 23274, 55331, 50644, 19601, 36274, 37821, 49569, 27460, 56529, 13961, 9043, 7944, 19746, 47641, 28119, 64621, 51985, 30571, 18285, 64357, 20611, 35146, 12916, 22873, 20353, 62412, 9906, 6782, 50089, 22353, 53133, 6477, 22406, 24033, 9433, 5803, 24930, 22624, 25165, 36991, 20420, 17792, 42123, 2732, 57503, 20206, 35112, 60100, 7454, 12339, 22453, 27376, 55287, 22413, 34054, 58992, 14052, 5805, 22937, 12115, 38984, 22187, 25769, 24398, 10674, 42038, 36187, 52529, 49468, 19025, 59941, 39097, 5845, 43056, 14009, 32433, 25461, 46686, 16225, 36569, 6616, 58744, 26648, 13119, 49339, 4246, 55652, 10765, 38230, 38274, 65365, 62170, 23160, 727, 14636, 7153, 41647, 6500, 13318, 4106, 38713, 21150, 57824, 29843, 52429, 17359, 55878, 39427, 55221, 5530, 2073, 32091, 19123, 24208, 12401, 45161, 65160, 62848, 48889, 3819, 857, 42711, 40634, 52857, 61828, 61453, 47449, 62098, 45375, 51949, 5933, 35426, 21471, 23761, 8818, 41493, 4217, 20066, 22613, 27032, 59448, 15104, 12554, 59620, 25190, 47792, 5062, 39126, 44270, 31094, 12454, 40296, 14960, 16137, 1631, 38263, 29646, 7497, 8919, 32785, 20725, 30092, 26832, 49493, 46285, 5607, 15432, 5738, 27919, 14389, 34844, 45164, 59090, 39246, 34413, 7974, 38886, 3608, 22780, 45063, 7875, 32676, 10101, 4622, 38874, 12211, 40832, 55924, 670, 40696, 1953, 63781, 5742, 11568, 22794, 16688, 19182, 7135, 51026, 28959, 24393, 38103, 10174, 2364, 40849, 22990, 1462, 8094, 55703, 31375, 6032, 47443, 8577, 20478, 65178, 28099, 23427, 56000, 15466, 39821, 42052, 64983, 40391, 51211, 63172, 11287, 15162, 62384, 52377, 45408, 48581, 46785, 49043, 56342, 19769, 65303, 23040, 20057, 64845, 63153, 38953, 7802, 29813, 45371, 64806, 9998, 8141, 24979, 22925, 58798, 35438, 19862, 11201, 38762, 27065, 23704, 13142, 37387, 20292, 15394, 31233, 4475, 36523, 19940, 54309, 16080, 314, 62381, 56862, 29867, 38486, 12053, 42402, 46428, 63480, 7566, 31587, 5003, 17913, 33763, 26605, 36070, 2272, 32156, 15890, 6234, 53341, 523, 2022, 7176, 13913, 20965, 50598, 12411, 35806, 138, 2183, 14561, 47614, 19362, 25570, 32878, 13862, 52125, 32734, 23693, 31070, 6056, 13981, 42703, 65431, 45035, 1249, 5265, 6270, 65228, 63264, 963, 39090, 33933, 43758, 8503, 31356, 44167, 28363, 56864, 55554, 59498, 22232, 21612, 51603, 11487, 13123, 5692, 13668, 63160, 40067, 9883, 7080, 56829, 61325, 44909, 8620, 34839, 16369, 20433, 13240, 14729, 61924, 3947, 65184, 54824, 56804, 63960, 10485, 38643, 35224, 14476, 57521, 25440, 18736, 18362, 9027, 63972, 60333, 30595, 49860, 28954, 34225, 8564, 26183, 29583, 44103, 14764, 26128, 55366, 32185, 16480, 302, 3254, 62316, 41257, 23547, 57388, 55538, 11849, 29856, 31665, 41577, 32022, 4607, 63300, 35312, 5737, 46081, 49169, 62124, 34740, 59605, 18238, 16261, 61559, 1252, 21149, 35109, 32809, 12713, 28176, 52258, 14015, 35347, 39087, 14576, 4691, 28988, 55372, 50561, 41025, 15150, 15005, 5355, 31883, 20293, 48959, 15163, 52179, 51300, 7610, 18108, 25624, 8896, 29165, 32997, 17020, 37753, 12182, 65382, 49636, 1409, 59985, 18053, 14627, 12606, 55413, 4768, 39610, 48152, 4140, 44087, 41400, 32762, 55785, 14390, 3949, 9049, 19547, 42725, 40468, 16399, 12859, 54306, 59487, 31004, 48944, 1086, 24416, 23994, 51578, 51296, 58656, 62320, 28576, 65001, 47826, 10057, 34011, 45483, 27273, 54164, 44075, 38873, 14447, 60523, 47726, 64745, 59635, 43709, 58354, 42084, 7585, 61025, 24322, 49726, 58865, 18448, 33892, 21613, 63131, 22166, 31883, 57491, 27749, 11358, 33221, 17365, 56717, 51708, 52609, 263, 62705, 58571, 51837, 65226, 57881, 767, 63208, 53004, 57809, 33807, 37150, 53417, 3571, 10068, 31202, 38548, 4537, 24897, 48450, 51281, 21526, 3328, 62435, 23175, 28219, 18402, 37675, 5864, 20681, 14165, 56077, 43873, 7393, 64355, 50479, 59574, 4372, 35513, 43796, 60368, 40444, 43830, 50307, 56639, 52979, 5784, 12979, 64907, 1807, 7286, 16128, 6928, 12414, 65023, 21387, 5350, 28345, 27845, 32934, 60165, 56949, 32120, 49520, 18536, 29133, 3849, 10066, 44079, 14303, 39606, 58295, 58568, 17477, 50632, 54041, 25749, 4120, 9855, 1172, 54730, 51945, 6287, 56776, 60521, 47437, 37557, 57283, 20474, 24665, 49219, 5128, 5138, 25131, 37826, 56066, 35627, 27493, 18422, 17300, 14926, 41122, 46944, 33633, 29137, 49964, 58673, 58627, 7081, 45794, 12108, 42522, 41002, 23357, 9415, 34796, 64896, 40255, 58829, 49050, 38363, 8362, 35481, 18975, 34826, 35125, 48227, 13425, 57626, 44527, 61786, 29943, 33898, 2019, 62126, 36579, 10631, 61398, 33188, 38218, 20909, 35476, 57597, 18799, 5161, 7094, 33995, 42749, 40873, 15585, 5737, 4498, 41644, 54329, 8295, 53416, 16933, 27966, 27035, 33723, 59338, 34650, 2424, 52323, 35149, 31403, 21211, 19877, 13035, 46371, 30754, 31680, 21400, 41468, 38183, 37748, 26414, 21918, 49839, 63287, 64636, 27983, 35046, 9400, 40332, 36655, 5346, 50277, 26279, 34412, 3006, 58690, 33280, 29977, 14669, 32771, 34788, 53606, 33410, 56244, 44311, 51146, 53181, 51626, 3583, 3881, 22009, 7479, 445, 8761, 37814, 40765, 34818, 44717, 13525, 29961, 8551, 22451, 25366, 49702, 44811, 2381, 55258, 16601, 17457, 4343, 45010, 26600, 35762, 18936, 317, 22783, 46282, 11224, 10634, 4649, 42436, 18542, 39831, 54755, 33549, 20235, 21277, 55043, 56209, 58916, 21534, 62887, 4624, 42890, 38269, 53698, 18435, 28726, 12125, 18507, 30062, 31634, 49046, 16412, 13620, 22138, 35440, 30194, 12792, 2736, 12285, 24361, 20843, 58745, 59837, 1898, 14949, 9028, 4740, 18303, 63572, 36168, 36724, 13193, 29745, 36404, 17515, 16351, 33773, 45154, 6160, 27488, 47552, 7828, 14492, 46367, 42983, 2891, 34105, 38600, 63153, 62587, 43487, 18155, 2830, 12546, 16363, 9769, 13105, 23300, 26438, 30694, 20344, 50706, 51207, 6436, 37925, 1998, 54205, 26238, 48605, 44350, 45528, 41809, 60189, 46014, 61082, 26834, 53985, 39029, 10346, 59126, 13312, 35761, 20341, 65428, 31796, 53706, 61668, 34396, 47542, 30132, 31147, 61733, 53554, 45033, 2608, 54942, 267, 2168, 34561, 48884, 52499, 51710, 15339, 26759, 45956, 28485, 14215, 14681, 42617, 37101, 7467, 34215, 2374, 57326, 35117, 1119, 60046, 40645, 43365, 11738, 65048, 7908, 8657, 33776, 45667, 56167, 37511, 10050, 60006, 43866, 23776, 29484, 21257, 6952, 20004, 2936, 34567, 42602, 43233, 44086, 31544, 61738, 63256, 29109, 40386, 48032, 43116, 2099, 50039, 11402, 26920, 49389, 26628, 10761, 57274, 18883, 44973, 38294, 41235, 29096, 62353, 16450, 11677, 46719, 50336, 61535, 16613, 13419, 12960, 29924, 63106, 25649, 40376, 25297, 1575, 44704, 35852, 49825, 60987, 22742, 31310, 42117, 41025, 50348, 37823, 54692, 4293, 34062, 30196, 5178, 1185, 20448, 42584, 3903, 4296, 45210, 13636, 51812, 14202, 37220, 20853, 15629, 57599, 61803, 20206, 8917, 2981, 60569, 13546, 15335, 20300, 10861, 32939, 40489, 53457, 42409, 54410, 23323, 32497, 31868, 60631, 60862, 15177, 30789, 49424, 35637, 6885, 54699, 55525, 42559, 24584, 60934, 13009, 32387, 9787, 65049, 51088, 7516, 63678, 29248, 47589, 61839, 43283, 22849, 42833, 35202, 63526, 12224, 56614, 22340, 31916, 19292, 58318, 8410, 21433, 52062, 61598, 1234, 53855, 42636, 9785, 60770, 27987, 42557, 37471, 55127, 42912, 41874, 26682, 61611, 54729, 2605, 55169, 55703, 8248, 39667, 35244, 33045, 31595, 4568, 36157, 2593, 14197, 12310, 31475, 14556, 1849, 19926, 61531, 61531, 5718, 33158, 39841, 63910, 32277, 22497, 63064, 39195, 17027, 42786, 1165, 31814, 12079, 17469, 18919, 47985, 24166, 18904, 52571, 41658, 62107, 3238, 12550, 63390, 31045, 58990, 64232, 2560, 50581, 1831, 30245, 58531, 59405, 6813, 65103, 3664, 15048, 36028, 58885, 54765, 58588, 36169, 52836, 21315, 17979, 22192, 45395, 33005, 1897, 699, 6588, 12517, 34070, 29117, 6184, 39740, 21017, 5527, 38102, 63473, 19638, 33754, 49138, 12949, 20309, 30811, 32967, 40853, 47513, 59054, 34247, 16843, 17702, 51059, 42250, 6849, 45533, 51592, 51606, 53496, 58924, 31641, 10865, 2014, 51070, 59834, 40599, 2369, 58395, 57045, 23414, 41179, 27000, 59177, 33931, 52578, 50585, 11632, 16722, 47300, 33328, 57510, 45402, 6163, 39108, 1202, 58377, 2357, 47413, 27398, 33236, 5428, 3179, 18470, 20586, 29993, 49050, 177, 46966, 9720, 55389, 14354, 41783, 56652, 4643, 5656, 64347, 21094, 33010, 41597, 29270, 34490, 26583, 40590, 33392, 4758, 47174, 57518, 58750, 42988, 8806, 27301, 43755, 30629, 38896, 29340, 28992, 19440, 64669, 41186, 7607, 20858, 54571, 14719, 48549, 54552, 46094, 50746, 20829, 53304, 13195, 15156, 39524, 6790, 20504, 18904, 63101, 5668, 17176, 11174, 51281, 63301, 64994, 30660, 52749, 27265, 31470, 3558, 62996, 43333, 53313, 65506, 59208, 32680, 63040, 41907, 35561, 4278, 46458, 9317, 5232, 60116, 60840, 27862, 40520, 61297, 19094, 40526, 33968, 12414, 61353, 29260, 24724, 32095, 5696, 10216, 42679, 42755, 29787, 63049, 44309, 46316, 62616, 17538, 14752, 59653, 26768, 30691, 42364, 48823, 11629, 57282, 63606, 44297, 59654, 63081, 62773, 48817, 46992, 53003, 25657, 16983, 62406, 57536, 44676, 26783, 5922, 43730, 2233, 63613, 18720, 12835, 28236, 48262, 64860, 52608, 4142, 36303, 23839, 63983, 3924, 16830, 442, 3770, 19018, 11165, 58586, 64191, 23400, 31698, 57014, 55433, 20935, 30661, 26821, 34472, 22000, 29946, 42338, 20827, 58558, 35811, 35886, 39781, 30016, 6066, 61230, 39382, 54429, 20484, 26728, 54525, 22090, 52318, 50626, 35497, 13312, 24360, 32084, 39189, 5983, 36849, 6277, 17630, 10713, 63040, 42743, 43891, 51797, 51338, 53934, 41360, 45259, 56722, 15634, 10609, 54905, 31860, 51280, 51491, 35837, 26135, 32360, 13704, 5178, 58968, 62447, 40564, 61084, 13398, 1051, 20949, 20997, 37517, 29509, 25579, 55521, 29542, 7469, 4603, 9679, 30020, 26696, 24455, 34505, 28347, 64963, 48209, 22296, 42565, 39877, 40645, 54187, 23614, 51385, 21727, 45792, 459, 5549, 18292, 16261, 35818, 49396, 58919, 53228, 45146, 44871, 45760, 14070, 33188, 38210, 59926, 9303, 47400, 45204, 6930, 17989, 18581, 48552, 29694, 8703, 12661, 1480, 26567, 46825, 37740, 28922, 20692, 18967, 60694, 34196, 63478, 14657, 13400, 20867, 30695, 16432, 42296, 46948, 32543, 4639, 1591, 61382, 25261, 40160, 19793, 16100, 26313, 64501, 25271, 25281, 28304, 36219, 38847, 5063, 52224, 27326, 43054, 60880, 54397, 39270, 34290, 56271, 13767, 33505, 54925, 25842, 59824, 34437, 49583, 8551, 30021, 25752, 22105, 37298, 65130, 9507, 14003, 19740, 11315, 56096, 13313, 9129, 43047, 64164, 35482, 2904, 36865, 58234, 5782, 55280, 12781, 63989, 12293, 45576, 38221, 12661, 5818, 40374, 17718, 51550, 40405, 34194, 34747, 22144, 56855, 36456, 56997, 18179, 1930, 22221, 41998, 48863, 41410, 1651, 56886, 27376, 27671, 56422, 5565, 12649, 29574, 35709, 47943, 2878, 33338, 44937, 47719, 40947, 16491, 37271, 20081, 56299, 45571, 1673, 35787, 38785, 12209, 25135, 2673, 47762, 4759, 42158, 51582, 60508, 34094, 49549, 41910, 6495, 64499, 34269, 21985, 7363, 31384, 40554, 50368, 4296, 25925, 41625, 41652, 43985, 61635, 3172, 52491, 42231, 22955, 44167, 20141, 35243, 8866, 11221, 39199, 22597, 12062, 19091, 42049, 26293, 8761, 33683, 26475, 44538, 9, 41505, 22293, 22995, 39162, 32470, 7149, 18142, 21799, 38875, 54249, 52671, 10320, 52763, 36111, 42426, 60620, 27666, 34630, 18065, 65158, 37956, 14310, 24769, 52901, 31500, 16876, 50106, 45475, 4944, 62995, 53278, 19898, 53702, 42763, 19633, 28818, 62920, 53877, 39104, 64156, 15003, 50947, 42674, 61560, 10156, 59300, 16158, 18260, 11509, 49435, 56490, 55820, 2830, 47988, 14802, 22185, 32860, 25605, 24731, 3350, 2717, 11119, 13058, 4851, 28702, 20950, 4490, 37044, 65175, 43213, 56985, 45725, 26503, 14323, 60149, 56735, 42796, 36903, 23806, 10740, 5218, 35767, 43464, 60169, 51381, 9200, 43163, 44422, 41162, 34499, 29470, 44496, 54783, 5863, 33655, 35134, 40608, 19728, 46043, 59153, 43016, 32077, 13465, 36287, 21199, 40962, 1710, 688, 56669, 18362, 61745, 30794, 61638, 4206, 46529, 15621, 51279, 37316, 7194, 36969, 21493, 1168, 53856, 42941, 33781, 15014, 36421, 56440, 29224, 55470, 47798, 38265, 53010, 57253, 33094, 5836, 18520, 40405, 2682, 52853, 36055, 6684, 31153, 16093, 25686, 43988, 33153, 9624, 59019, 55552, 20050, 35449, 6703, 50600, 62151, 45588, 49738, 30396, 24679, 30530, 24873, 16838, 30375, 57037, 24932, 9143, 31938, 13749, 6716, 27246, 40427, 36679, 37760, 61910, 30416, 19399, 53360, 2179, 144, 44024, 30337, 8599, 15975, 29962, 19578, 12386, 38113, 55643, 39102, 39673, 4231, 48080, 34218, 58122, 34360, 24844, 28890, 3641, 65402, 24324, 38011, 10929, 19788, 20617, 54641, 14291, 63929, 42300, 63491, 58130, 39013, 47486, 47776, 21513, 27189, 1430, 49203, 52469, 57912, 54102, 36213, 8270, 57573, 25108, 22826, 47411, 40336, 59898, 25800, 14268, 54352, 52084, 40461, 64009, 26050, 20810, 56614, 12779, 9865, 19219, 249, 10452, 52472, 45978, 59418, 43722, 24839, 8519, 13978, 39544, 52949, 46227, 57583, 3339, 53513, 26829, 40016, 48785, 60018, 56306, 5968, 34451, 61535, 36444, 20115, 38677, 59328, 23577, 30015, 39971, 37850, 23677, 45289, 58171, 8357, 35872, 39377, 17585, 22308, 3503, 7373, 3293, 982, 9161, 10523, 8543, 16250, 62200, 50556, 17919, 31885, 12575, 27383, 31411, 13655, 3227, 31625, 11793, 47801, 23594, 15700, 34298, 19373, 15745, 6625, 40331, 41788, 31356, 61912, 24572, 4201, 60074, 5691, 28811, 23907, 38032, 18581, 2821, 15232, 2377, 47253, 13562, 47505, 59476, 29467, 36166, 8990, 53401, 52075, 23357, 59237, 28033, 38874, 19855, 3502, 26549, 45096, 22466, 56954, 12169, 57487, 39791, 5178, 26942, 46094, 50871, 45279, 29093, 38028, 46932, 37346, 27878, 28381, 23412, 31923, 9620, 25686, 31296, 39440, 31871, 20163, 9490, 8199, 58587, 8818, 25956, 41985, 52318, 64167, 47977, 62968, 11285, 46739, 49517, 7640, 33154, 43735, 38320, 7759, 38941, 43086, 34981, 43262, 40639, 38548, 17702, 63243, 60810, 60439, 30141, 61157, 45192, 31454, 26984, 41508, 52465, 5590, 6933, 17246, 4496, 23722, 24648, 9744, 3246, 49251, 42438, 63298, 60407, 59908, 37518, 35437, 28857, 27199, 32926, 62896, 17793, 14895, 1720, 36110, 31866, 44286, 48562, 50841, 20304, 17845, 61024, 48480, 13692, 37391, 46052, 56507, 57677, 9291, 4888, 37615, 63030, 48381, 37121, 58148, 10836, 33460, 24713, 41114, 51903, 61942, 14674, 22716, 866, 54748, 32938, 42196, 20583, 63315, 11091, 53525, 13863, 918, 44183, 49423, 14762, 40025, 30445, 14028, 19933, 41908, 4760, 35034, 28216, 37774, 44574, 7583, 33022, 37277, 58522, 59893, 9751, 64318, 56398, 38732, 26229, 45933, 51504, 2510, 49799, 57457, 64004, 49106, 63730, 6394, 28194, 34444, 42155, 41711, 1600, 24888, 11167, 14051, 20272, 11292, 351, 75, 52097, 44803, 21135, 57963, 32280, 31399, 38400, 17061, 54057, 11490, 5613, 6940, 9646, 3837, 4664, 31074, 15773, 34776, 2869, 33845, 52302, 20979, 18267, 9386, 63546, 883, 22110, 30487, 46491, 19274, 22000, 49798, 32842, 11082, 37558, 46787, 47015, 38916, 32741, 13990, 61635, 25346, 59267, 1110, 29326, 56585, 44688, 60711, 12739, 47608, 54284, 20470, 12207, 47457, 41557, 60137, 46140, 45181, 31889, 28063, 44698, 2635, 23464, 35440, 51245, 18639, 1162, 41796, 29684, 59678, 9042, 62878, 56587, 56588, 8823, 60372, 63607, 12917, 37060, 25475, 4575, 17059, 64198, 19923, 17459, 21372, 43930, 24429, 5176, 21457, 20698, 31157, 18809, 53748, 32352, 33457, 39367, 4237, 11228, 50322, 23841, 54322, 21387, 50402, 31292, 21472, 15936, 65009, 46457, 20369, 62097, 12283, 46871, 49367, 56298, 55665, 7793, 53085, 60147, 55479, 43975, 65251, 13647, 62025, 63811, 18415, 18280, 30373, 4979, 44624, 35273, 53611, 49677, 16456, 26303, 8242, 59735, 34606, 3342, 54532, 61408, 63789, 39404, 14127, 47011, 50546, 22690, 48901, 24588, 39140, 48713, 39834, 44344, 5049, 6751, 54019, 30674, 35505, 1482, 43167, 64678, 40337, 5184, 3734, 54702, 45644, 55143, 14725, 43131, 32617, 47329, 27163, 23363, 22443, 17896, 22235, 64788, 19422, 10863, 57404, 61620, 52283, 41841, 19919, 23210, 50913, 35329, 10461, 36123, 39323, 8694, 21025, 38763, 2139, 43387, 54490, 26853, 19274, 42714, 33812, 43515, 45763, 3515, 45458, 48030, 12010, 57702, 54998, 8301, 28883, 31796, 51504, 5677, 47206, 56862]

c = ")9Lsu_4s_eb__otEli_nhe_tes5gii5sT@omamkn__ari{efm0__rmu_nt(0Eu3_En_og5rfoh}nkeoToy_bthguuEh7___u"



ROUNDS = len(gift)   # 3108
STATE_WORDS = 624

# 若 True: 在 i%128==0 处使用 16bit 约束（更强，解更少；除非极罕见 r1=0 会失败）
# 若 False: 在 i%128==0 也使用 15bit 约束（更保守，解更多，靠 solve_all+verify 选出真解）
USE_16BIT_ON_128 = True

@contextmanager
def timeit(name):
    t0 = perf_counter()
    try:
        yield
    finally:
        t1 = perf_counter()
        print(f"[{name}] {t1 - t0:.2f}s")

def build_equations(lin: LinearSystem):
    """
    在线性域构造约束：
      常规轮：      (r2 >> 8) == gift.hi8             （8 bit）
      i % 64 == 0： (r2 >> 1) == (gift >> 1)          （15 bit）
      i % 128 == 0：
        - 如果 USE_16BIT_ON_128=True： (r2 >> 8) == hi ，(r2 & 0xff) == (lo ^ 1)（16 bit）
        - 否则同上 15 bit 形式
      额外：mt[0] 的最高位=1 约束（惯例）
    """
    mt = lin.gens()      # 624 个 32-bit 符号 word
    rng = MT19937(mt)

    eqs = []
    with timeit("build equations"):
        for i in range(ROUNDS):
            _ = rng.getrandbits(8)          # r1 仅推进，不建约束（pow 非线性）

            r2 = rng.getrandbits(16)        # r2 用于建线性约束

            gi = int(gift[i])
            hi = (gi >> 8) & 0xFF
            lo = gi & 0xFF

            if i % 128 == 0:
                if USE_16BIT_ON_128:
                    # 16 bit：注意是异或 ^ ，不是乘方 **
                    eqs.append((r2 >> 8) ^ hi)               # hi8
                    eqs.append((r2 & 0xFF) ^ (lo ^ 0x01))    # lo8 ^ 1
                else:
                    # 15 bit：右移1位（掩码影响的最低位被右移抹掉）
                    eqs.append((r2 >> 1) ^ (((hi << 8) | lo) >> 1))
            elif i % 64 == 0:
                eqs.append((r2 >> 1) ^ (((hi << 8) | lo) >> 1))  # 15 bit
            else:
                eqs.append((r2 >> 8) ^ hi)                       # 8 bit

        # Python random 惯例：初始 state word 的最高位为 1
        eqs.append(mt[0] ^ 0x80000000)

    return eqs, mt

def verify_full_stream(state_words):
    """
    用纯 Python random 重放并严格校验 gift：
      (r2 >> 8) == hi
      (r2 & 0xff) ^ ((r1^(2i) mod 257) & 0xff) == lo
    """
    pyrand = MT19937(state_words).to_python_random()
    for i in range(ROUNDS):
        r1 = pyrand.getrandbits(8)
        r2 = pyrand.getrandbits(16)
        v = pow(r1, 2 * i, 257) & 0xFF

        gi = int(gift[i])
        hi = (gi >> 8) & 0xFF
        lo = gi & 0xFF

        if ((r2 >> 8) & 0xFF) != hi:
            return False, i
        if ((r2 & 0xFF) ^ v) != lo:
            return False, i
    return True, -1

def recover_flag(state_words, c):
    """
    前进 3108 轮后，重放 2025 次 shuffle，逆置换还原 flag。
    """
    pyrand = MT19937(state_words).to_python_random()

    # 跳过 gift 阶段
    for _ in range(ROUNDS):
        pyrand.getrandbits(8)
        pyrand.getrandbits(16)

    # 重放 2025 次 shuffle
    idx = list(range(len(c)))
    for _ in range(2025):
        pyrand.shuffle(idx)

    inv = [0] * len(c)
    for j, pos in enumerate(idx):
        inv[pos] = j
    return ''.join(c[inv[i]] for i in range(len(c)))

def main():
    lin = LinearSystem([32] * STATE_WORDS)

    eqs, _ = build_equations(lin)

    print("[i] solving all solutions (enumeration) ...")
    with timeit("solve_all"):
        sols = lin.solve_all(eqs)   
        checked = 0
        for state_words in sols:
            checked += 1
            ok, bad_i = verify_full_stream(state_words)
            if ok:
                print(f"[+] found valid solution after {checked} candidate(s).")
                flag = recover_flag(state_words, c)
                print("[+] flag:", flag)
                return
            if checked % 100 == 0:
                print(f"[.] checked {checked} candidates ...")

    print("[-] exhausted all candidates but none passed full verify.")

if __name__ == "__main__":
    main()

sk

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
from random import randint
from Crypto.Util.number import getPrime, inverse, long_to_bytes, bytes_to_long
from math import gcd
import signal
from secret import flag

def gen_coprime_num(pbits):
    lbits = 2 * pbits + 8
    lb = 2**lbits
    ub = 2**(lbits + 1)
    while True:
        r = randint(lb, ub)
        s = randint(lb, ub)
        if gcd(r, s) == 1:
            return r, s

def mult_mod(A, B, p):
    result = [0] * (len(A) + len(B) - 1)
    for i in range(len(A)):
        for j in range(len(B)):
            result[i + j] = (result[i + j] + A[i] * B[j]) % p
    
    return result

def gen_key(p):
    f = [randint(1, 2**128) for i in ":)"]
    h = [randint(1, 2**128) for i in ":("]
    
    R1, S1 = gen_coprime_num(p.bit_length())
    R2, S2 = gen_coprime_num(p.bit_length())

    B = [[randint(1, p - 1) for i in ":("] for j in ":)"]

    P = []
    for b in B:
        P.append(mult_mod(f, b, p))
    
    Q = []
    for b in B:
        Q.append(mult_mod(h, b, p))

    for i in range(len(P)):
        for j in range(len(P[i])):
            P[i][j] = P[i][j] * R1 % S1
            Q[i][j] = Q[i][j] * R2 % S2

    sk = [(R1, S1), (R2, S2), f, h, p]
    pk = [P, Q, p]

    return sk, pk

def encrypt(pk, pt):
    P, Q, p = pk
    pt = bytes_to_long(pt)

    PP = 0
    QQ = 0

    for i in range(len(P)):
        u = randint(1, p)
        for j in range(len(P[0])):
            PP = PP + P[i][j] * (u * pt**j % p)
            QQ = QQ + Q[i][j] * (u * pt**j % p)

    return PP, QQ

def decrypt(sk, ct):
    RS1, RS2, f, h, p = sk
    R1, S1 = RS1
    R2, S2 = RS2

    P, Q = ct
    invR1 = inverse(R1, S1)
    invR2 = inverse(R2, S2)
    P = (P * invR1 % S1) % p
    Q = (Q * invR2 % S2) % p

    f0q = f[0] * Q % p
    f1q = f[1] * Q % p
    h0p = h[0] * P % p
    h1p = h[1] * P % p

    a = f1q + p - h1p % p
    b = f0q + p - h0p % p

    pt = -b * inverse(a, p) % p
    pt = long_to_bytes(pt)

    return pt

signal.alarm(30)
p = getPrime(256)
sk, pk = gen_key(p)
ticket = long_to_bytes(randint(1, p))
enc_ticket = encrypt(pk, ticket)
print(pk)
print(enc_ticket)

for i in range(2):
    op = int(input("op>").strip())
    if op == 1:
        msg = input("pt:").strip().encode()
        ct = encrypt(pk, msg)
        print(f"ct: {ct}")
    elif op == 2:
        user_input = input("ct:").strip().split(" ")
        if len(user_input) == 2:
            ct = [int(user_input[0]), int(user_input[1])]
        else:
            print("invalid ct.")
            break
        
        user_input = input("your f:").strip().split(" ")
        if len(user_input) == 2:
            user_f = [int(user_input[0]), int(user_input[1])]
        else:
            print("invalid f.")
            break

        user_input = input("your h:").strip().split(" ")
        if len(user_input) == 2:
            user_h = [int(user_input[0]), int(user_input[1])]
        else:
            print("invalid h.")
            break

        user_input = input("your R1 S1:").strip().split(" ")
        if len(user_input) == 2:
            user_r1s1 = [int(user_input[0]), int(user_input[1])]
        else:
            print("invalid R1 S1.")
            break

        user_input = input("your R2 S2:").strip().split(" ")
        if len(user_input) == 2:
            user_r2s2 = [int(user_input[0]), int(user_input[1])]
        else:
            print("invalid R2 S2.")
            break

        pt = decrypt((user_r1s1, user_r2s2, user_f, user_h, p), ct)
        if pt == ticket:
            print(flag)
        else:
            print(pt.hex())
    else:
        print("invalid op.")
        break

print("bye!")

唉之前明明学过用cuso的这次又没想起来xd

首先来看一下加密的核心

1
2
3
4
PP += P[i][j] * (u_i * m**j % p)
QQ += Q[i][j] * (u_i * m**j % p)
# i ∈ {0,1}, j ∈ {0,1,2}

由于P和Q都是对2x2的B分别和f=[f0,f1]，h=[h0,h1]作卷积得到的2x3的矩阵。定义
$$
r_{i,0}=u_i,\quad r_{i,1}=u_i m,\quad r_{i,2}=u_i m^{2}\quad (\bmod p).

$$
所以PP和QQ可以用如下公式表示
$$
\begin{aligned}
PP &= \sum_{i=0}^{1}\sum_{j=0}^{2} P_{ij}, sk_{i,j},\
QQ &= \sum_{i=0}^{1}\sum_{j=0}^{2} Q_{ij}, sk_{i,j}.
\end{aligned}

$$
这样就能得到6个小量，用cuso求解之后就能还原m了，最后重新加密一遍得到对应参数提交即可

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
from cuso import find_small_roots
from Crypto.Util.number import *
from math import gcd
from random import randint
from pwn import *


def gen_coprime_num(pbits):
    lbits = 2 * pbits + 8
    lb = 2**lbits
    ub = 2**(lbits + 1)
    while True:
        r = randint(lb, ub)
        s = randint(lb, ub)
        if gcd(r, s) == 1:
            return r, s

def mult_mod(A, B, p):
    result = [0] * (len(A) + len(B) - 1)
    for i in range(len(A)):
        for j in range(len(B)):
            result[i + j] = (result[i + j] + A[i] * B[j]) % p
    
    return result

def gen_key(p):
    f = [randint(1, 2**128) for i in ":)"]
    h = [randint(1, 2**128) for i in ":("]
    
    R1, S1 = gen_coprime_num(p.bit_length())
    R2, S2 = gen_coprime_num(p.bit_length())

    B = [[randint(1, p - 1) for i in ":("] for j in ":)"]

    P = []
    for b in B:
        P.append(mult_mod(f, b, p))
    
    Q = []
    for b in B:
        Q.append(mult_mod(h, b, p))

    for i in range(len(P)):
        for j in range(len(P[i])):
            P[i][j] = P[i][j] * R1 % S1
            Q[i][j] = Q[i][j] * R2 % S2

    sk = [(R1, S1), (R2, S2), f, h, p]
    pk = [P, Q, p]

    return sk, pk

def encrypt(pk, pt):
    P, Q, p = pk
    pt = bytes_to_long(pt)

    PP = 0
    QQ = 0

    for i in range(len(P)):
        u = randint(1, p)
        for j in range(len(P[0])):
            PP = PP + P[i][j] * (u * pt**j % p)
            QQ = QQ + Q[i][j] * (u * pt**j % p)

    return PP, QQ

sh = remote("47.104.146.31",7777)

context.log_level = 'debug'
token = "icq77a2e18f659f15464f04c13cb1997"
sh.sendlineafter(b"team token:",token.encode())
pk = eval(sh.recvline().strip().decode())
enc_ticket = eval(sh.recvline().strip().decode())

P,Q,p = pk
PP,QQ = enc_ticket

sk00,sk01,sk02,sk10,sk11,sk12 = var('sk00,sk01,sk02,sk10,sk11,sk12')
f1 = P[0][0]*sk00 + P[0][1]*sk01 + P[0][2]*sk02 + P[1][0]*sk10 + P[1][1]*sk11 + P[1][2]*sk12 - PP
f2 = Q[0][0]*sk00 + Q[0][1]*sk01 + Q[0][2]*sk02 + Q[1][0]*sk10 + Q[1][1]*sk11 + Q[1][2]*sk12 - QQ

relations = [f1,f2]
bounds = {sk00: (0, 2**256),sk01: (0,p),sk02 : (0,p),sk10: (0,2**256),sk11: (0,p),sk12: (0,p)}
roots = find_small_roots(
    relations,
    bounds,
)
    
for root in roots:
    u0 = root[sk00]
    u1 = root[sk10]
    m1 = root[sk01] * inverse(u0,p) % p
    m2 = root[sk11] * inverse(u1,p) % p
    if m1 == m2:
        print(m1)
        sk1, pk1 = gen_key(p)
        RS1, RS2, f, h, pp = sk1
        R1,S1 = RS1
        R2,S2 = RS2
        ct1 = encrypt(pk1,long_to_bytes(m1))
        sh.sendlineafter(b"op>",b'2')
        sh.sendlineafter(b"ct:",f"{ct1[0]} {ct1[1]}".encode())
        sh.sendlineafter(b"your f:",f"{f[0]} {f[1]}".encode())
        sh.sendlineafter(b"your h:",f"{h[0]} {h[1]}".encode())
        sh.sendlineafter(b"your R1 S1:",f"{R1} {S1}".encode())
        sh.sendlineafter(b"your R2 S2:",f"{R2} {S2}".encode())
        print(sh.recvline().strip().decode())

Blurred

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
from sage.all import *
from sage.misc import prandom
import random
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad

q = 1342261
n = 1031
PR = PolynomialRing(Zmod(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)
flag = b"flag{*****************************}"

def sample(rand):
    return (rand.getrandbits(1) - rand.getrandbits(1)) * (rand.getrandbits(1) * rand.getrandbits(1))


def GenNTRU():
    f = [sample(prandom) for _ in range(n)]
    g1 = [sample(prandom)for _ in range(n)]
    g2 = [sample(prandom) for _ in range(n)]
    g1x = Q(g1)
    g2x = Q(g2)

    while True:
        fx = Q(f)
        try:
            h1 = g1x / fx
            h2 = g2x / fx
            return (h1.lift(), h2.lift(), fx)
        except:
            prandom.shuffle(f)
            continue

for _ in range(20259):
    c = int(input("c :"))
    if c == 1:
        coin = random.getrandbits(1)
        if coin == 0:
            pk1, pk2, fx = GenNTRU()
        else:
            pk1, pk2, fx = Q.random_element().lift(), Q.random_element().lift(), Q([sample(prandom) for _ in range(n)])

        print("Hints:", pk1.list(), pk2.list())
        
    elif c == 2:
        SHA = SHA256.new()
        SHA.update(str(random.getrandbits(256)).encode())
        KEY = SHA.digest()
        cipher = AES.new(KEY, AES.MODE_ECB)
        flag = pad(flag, AES.block_size)
        print("Flag:", cipher.encrypt(flag))
    else:
        break

大致思路是通过区分coin0和coin1来得到足够的bit打MT。具体的还在学习，指路一个详细wp

2025强网杯 | DexterJie’Blog