20210626-GKCTF-CryptoSecPartWriteUp

 

Crypto

BUU已经上题

20210626GKCTF-39773b44.png

20210626GKCTF-f8641481.png

RRRRsa

  • 题目代码

    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
    from Crypto.Util.number import *
    from gmpy2 import gcd

    flag = b'xxxxxxxxxxxxx'
    p = getPrime(512)
    q = getPrime(512)
    m = bytes_to_long(flag)
    n = p*q
    e = 65537
    c = pow(m,e,n)
    print('c={}'.format(c))

    p1 = getPrime(512)
    q1 = getPrime(512)
    n1 = p1*q1
    e1 = 65537
    assert gcd(e1,(p1-1)*(q1-1)) == 1
    c1 = pow(p,e1,n1)
    print('n1={}'.format(n1))
    print('c1={}'.format(c1))
    hint1 = pow(2020 * p1 + q1, 202020, n1)
    hint2 = pow(2021 * p1 + 212121, q1, n1)
    print('hint1={}'.format(hint1))
    print('hint2={}'.format(hint2))

    p2 = getPrime(512)
    q2 = getPrime(512)
    n2 = p2*q2
    e2 = 65537
    assert gcd(e1,(p2-1)*(q2-1)) == 1
    c2 = pow(q,e2,n2)
    hint3 = pow(2020 * p2 + 2021 * q2, 202020, n2)
    hint4 = pow(2021 * p2 + 2020 * q2, 212121, n2)
    print('n2={}'.format(n2))
    print('c2={}'.format(c2))
    print('hint3={}'.format(hint3))
    print('hint4={}'.format(hint4))

    #c=13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
    #n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
    #c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
    #hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
    #hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
    #n2=114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
    #c2=67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
    #hint3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
    #hint4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513
  • 已知

    $c\equiv m^e\ (mod\ n)$

    $c_1\equiv p^e\ (mod\ n_1)$

    $hint_1\equiv (2020\cdot p_1+q_1)^{202020}\ (mod\ n_1)$

    $hint_2\equiv (2021\cdot p_1+212121)^{q_1}\ (mod\ n_1)$

    $c_2\equiv q^{e_1}\ (mod\ n_2)$

    $hint_3\equiv (2020\cdot p_2+2021\cdot q_2)^{202020}\ (mod\ n_2)$

    $hint_4\equiv (2021\cdot p_2+2020q_2)^{212121}\ (mod\ n_2)$

  • 思路如下

    这道题目,大致可以分成两个部分,分别分解$n_1$和$n_2$,求出$p$和$q$,就可以解密flag了

    首先肯定会二项式展开,然后就是把各种定理给用起来,此外这类题目的特点就是数字对称,思路尽量往消元的方向走

  • 推导

    跟着官方WP推导一遍

    $hint_1\equiv (2020\cdot p_1+q_1)^{202020}\equiv (2020\cdot p_1)^{202020}+q_1^{202020}\ (mod\ n_1)$

    $\Rightarrow hint_1=(2020\cdot p_1)^{202020}+k_1q_1$

    $hint_2\equiv (2021\cdot p_1+212121)^{q_1}\ (mod\ n_1)$

    即$hint_2\equiv (2021\cdot p_1+212121)^{q_1}\ (mod\ q_1)$,结合费马小定理

    $\Rightarrow hint_2=2021\cdot p_1+212121+k_2q_1$

    $\Rightarrow (hint_2-212121)^{202020}\equiv (2021\cdot p_1+k_2q_1)^{202020}\equiv (2021\cdot p_1)^{202020}+(k_2q_1)^{202020}\ (mod\ n_1)$

    $\Rightarrow (hint_2-212121)^{202020}=(2021\cdot p_1)^{202020}+kq_1$

    算出下面两个式子

    $$
    hint_1\times 2021^{202020}\equiv [(2020\cdot p_1)^{202020}+k_1q_1]\times 2021^{202020}\ (mod\ n_1)
    $$

$$
(hint_2-212121)^{202020}\times 2020^{202020}\equiv ((2021\cdot p_1)^{202020}+kq_1)\times 2020^{202020}\ (mod\ n_1)
$$

则可以分解$n_1$,求出$p$
$$
q_1=((2)-(1),\ n_1)\notag
$$
$hint_3\equiv (2020\cdot p_2+2021\cdot q_2)^{202020}\equiv (2020\cdot p_2)^{202020}+(2021\cdot q_2)^{202020}\ (mod\ n_2)$

$hint_4\equiv (2021\cdot p_2+2020\cdot q_2)^{212121}\equiv (2021\cdot p_2)^{212121}+(2020\cdot q_2)^{212121}\ (mod\ n_2)$

算出下面两个式子(先把指数凑成一样的,再把前面系数凑成一样的
$$
hint_3^{212121}\equiv (2020\cdot p_2)^{202020\times 212121}+(2021\cdot q_2)^{202020\times212121}\ (mod\ n_2)
$$

$$
hint_4^{202020}\equiv (2021\cdot p_2)^{202020\times 212121}+(2020\cdot q_2)^{202020\times 212121}\ (mod\ n_2)
$$

则可以分解$n_2$,求出$q$
$$
q_2=((4)\times 2020^{202020\times 212121}-(3)\times 2021^{202020\times 212121},\ n_2)\notag
$$
之后便是RSA常规步骤

  • 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
    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
    #!/usr/bin/env python
    # coding: utf-8
    def gcd(n1, n2):
    if n1 == 0:
    return n2
    elif n2 == 0:
    return n1
    t = n1
    while n2 > 0:
    n1 = n2
    n2 = t % n2
    t = n1
    return n1


    def xgcd(n1, n2):
    l1 = [1, 0]
    l2 = [0, 1]
    if n1 == 0:
    return l2
    elif n2 == 0:
    return l1
    t = n1 # t表示每一次的n1
    i = 0 # 用来标记一下
    while n2 > 0:
    q = n1 // n2
    l1.append(l1[i] - l1[i + 1] * q)
    l2.append(l2[i] - l2[i + 1] * q)
    i += 1
    n1 = n2
    n2 = t % n2
    t = n1
    # 不是求逆元,负数也无妨
    return l1[i], l2[i]


    def inverse(e, phi):
    if gcd(e, phi) != 1:
    print("e和phi不互素呢")
    return
    else:
    return xgcd(e, phi)[0] % phi


    rsa_decrypt = lambda c, p, q: pow(c, inverse(0x10001, (p - 1) * (q - 1)), p * q)


    c = 13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
    n1 = 75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
    c1 = 68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
    hint1 = 23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
    hint2 = 52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
    n2 = 114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
    c2 = 67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
    hint3 = 25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
    hint4 = 104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513

    q1 = gcd(pow((hint2-212121) * 2020, 202020, n1) - (hint1 * pow(2021, 202020, n1)) % n1, n1)
    q2 = gcd((pow(hint4, 202020, n2) * pow(2020, 202020 * 212121, n2) - pow(hint3, 212121, n2) * pow(2021, 202020 * 212121, n2)) % n2, n2)

    p = rsa_decrypt(c1, n1 // q1, q1)
    q = rsa_decrypt(c2, n2 // q2, q2)

    flag = rsa_decrypt(c, p, q)
    print(bytes.fromhex(hex(flag)[2:]))

    image-20220308193051999

random

题目描述

20210626GKCTF-0436bb67.png

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import random
from hashlib import md5


def get_mask():
file = open("random.txt","w")
for i in range(104):
file.write(str(random.getrandbits(32))+"\n")
file.write(str(random.getrandbits(64))+"\n")
file.write(str(random.getrandbits(96))+"\n")
file.close()
get_mask()
flag = md5(str(random.getrandbits(32)).encode()).hexdigest()
print(flag)

生成的文本文件如下,里面有312个随机数,分别是104个32、64、96位随机数

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
2584323193
1099154419438958164
35367876945070316311325317953
481304047
12782770146993102006
24789628292419559503661788402
2776391832
9046887565683900291
50006261016517120573540241998
4167723109
8540277546428614473
5932047064656933473553742683
2951765291
10958280862127627756
61364239380151547478360346674
727043053
10156271057154381198
32168336768992329620376069852
930821842
16276235036285538859
9299952556848430743503551046
2868231632
5239154873841417200
11073503953912227254738321705
3452646652
8203253126417399900
52795367131471301612397944513
1927997107
17486869700317373240
47859970254711877167132319582
1459348891
9270456490024856463
74988967035830352654888842228
3714813644
1001128959491001919
8338265486641240510773094199
1430706700
17510828220752339511
3163106687132931419335230580
663535320
9606088298064978425
42511409828594385595915384953
908684643
5421916296165007941
9630914642938890694059952508
2209941143
14999144064788271892
3764842169035734035997078921
2718456651
8541807093002241064
70305992075768658972224974121
930303353
887596273180600202
62528479418364179541352908078
3365397759
15219084820731944344
31433566654697222176709895388
1608992428
6417140575231408939
12879789575923814684090165215
2811970399
6123213785028348335
44681647388937033220521089118
1260870056
5601104844042776691
73199461252301674455633950458
883231057
17783480959798771462
53460694547508318015132953966
1332985617
6673661714524041073
54253348096650113440476985084
3911521675
3438383273755779719
50129032267969019444282164464
3311412816
8779405363908462634
77818642029003078860467063235
4204237422
17534771551489868719
47280916590275648057356977963
2090173606
12206397967662831376
9495602410639024810670107439
2896231201
7246124017447704664
64467120363081017096405905335
392254334
12789011750322942845
5247110397471141497763090834
814200188
14344105251896958923
38888779745538270252730950782
205529919
13939756220516981581
67139045733351688501202495914
3563698832
16840754399626540384
15354843719521267197455444900
1386481456
17766886653399976694
61203331542727632580855864074
2032518919
2355401958853696908
58793908005730868677649498244
3991002745
6506506581713943242
49187675946469291318483292566
2346942877
994297989736899070
45437626728896532873251413177
3841694984
14253899037419430689
8435766077661599453131339442
1679990328
5515793210854183190
32981467195097563488749918497
744869832
11965860903258650511
73456728458781563185478913274
1341354796
14941036303190219170
3601563989190071059996878006
3361509481
17629804697469609923
39935200308805986497519634478
213152541
18320881664493742431
35325602739583757661562537619
2583841550
13763800051589427155
24638499459902141689405229579
1930742512
2392210857598517491
10441235412645941387574306751
461860348
2960745717639761142
62671223148116753112168252981
342206006
6480900103080233462
68412521040142848818877222548
114798494
8473329380799862296
13698669860489083061204052132
2900249131
4183161143099214314
18705391538460150746163889528
3766817970
12378384893542868384
55065668763750424532726429526
937387269
6844068130337459179
3209183745118985928581969258
3341723085
5988612409695647387
74389503837936256104231536479
4240599755
15332231015110371140
62955965591068690743297262172
1555895753
6058791220464667520
38335642957673073804843192014
810331063
4826913432979346480
28611765156689124521247554769
2630955218
12776823600930336401
4939603509311727391894886152
3280912700
14886149455945180990
52545650130177883790984384989
2356751225
2213402912509116749
7670693824287789893690942739
1599077432
14059140725965938936
16912587144697957583184157226
1304928684
9448367331308980026
22467661289496622162065003733
2001054151
7669140498758745837
39387592809285963406216440474
1711960460
3944628516045148813
66275496498554499967007163069
1207238325
3474935157030029491
63309877710388250418928028870
759170859
5858654703302236387
47609248816278271537847269046
1571940308
8335124609741508060
63542562244865676783377908343
1103531693
673654248555391502
30211221866217572233934551180
1089271924
7205932443049001486
69303844715341292680611559319
78608136
3404862937733764913
4259499119552843766282799518
2856032696
18313272414884625578
13693483738598197670400133831
873953734
7709221139118742639
34347437826101106015248365081
1783225370
16395574393179667285
7105819215807952823387139051
4039492686
16956581102357069698
57880199206788615132959351746
4151578751
2089635663127651746
37224845035383461896791495968
3139901611
7354140220471025697
7677374435615054008235674795
2008633712
13970520912420834879
64431013803082441566118213963
1788996018
16490194110734000780
30074301251997624246501473245
2460472485
2420976394683211164
63223457068346692358441841920
83976303
11597367904222552300
541189103864720560882255271
1271705896
8355873362347678325
6344182152495584455275136810
516191728
14301559481738139949
56972815139785900061169383374
3206833632
10471460817277304217
48253348743985600958199235128
4093394606
18421023127368906484
3209763791222301851974194188
2294793393
5804188421524711527
71797815201668391465761200460
3776041666
4108093307245233290
36986873094794981638319354001
1123598142
18262625851690101956
75211342463083839154547686361
1000669502
18244976169672436911
72759872679663719847870853888
2863001571
18304840778989692776
22413497817784765711206417816
1497794697
11739492739170519132
67625171938756611423023578679
3351136254
11816001323328933293
68942708548438536419919996191
1327110822
1299589815565305619
62081225258542372826911047279
3410663545
13158537297009141542
21762078985419016317415112411
1245509971
8804545967037621189
12841311881373962346628325162
2090373367
5289193049949531539
58444176241871300895472370959
571136405
2357132884718584788
51271731657715979715595461713
1432929573
503683219995130744
42705435265543268884777575518
1452726104
2295689344585140511
56996373195070838495288737642
187502663
13760641334049999515
64971355271690455751992498230
2679386081
172294286357194222
78658263482976308261205349174
2643925505
9627451492376735719
44487428240561493246393172961
983662371
2375149476902080328
39784456552690724305541938380
3306946267
16316178008270132149
76712503805317876365091515524
3779008319
4892998918237451139
46329724632809073972496761660
3841865427
15115042473603448600
34888855489304037538590108588
585968278
15088560943809914475
46621092548977030580425482842

解题思路

考伪随机数,而伪随机的算法一般是MT19937

简单来说,MT19937有624个状态,每个状态32位,也就是64、96位随机数分别使用了2个、3个32位的状态

题目刚好就提供了104+104*2+104*3=624个状态

脚本搜集

MT19937Predictor

直接使用现成的脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from hashlib import md5
from mt19937predictor import MT19937Predictor

with open("random.txt", "r+") as fp:
lines = fp.readlines()
line = [int(_.strip()) for _ in lines]
Predictor = MT19937Predictor()
for i in range(104):
Predictor.setrandbits(line[i*3], 32)
Predictor.setrandbits(line[i*3+1], 64)
Predictor.setrandbits(line[i*3+2], 96)

key = Predictor.getrandbits(32)
print(md5(str(key).encode()).hexdigest())

用到了mt19937predictor模块,其实就是恢复一般的MT19937,具体的推导可以参考2022DASCTF MAY 出题人挑战赛

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
import random
import sys

# compatibility
if sys.version_info[0] == 2:
def _to_bytes(n, length, byteorder):
assert byteorder == 'little'
return ('%x' % n).zfill(length * 2).decode('hex')[: : -1]
def _from_bytes(s, byteorder):
assert byteorder == 'little'
return int(str(s[: : -1]).encode('hex'), 16)
else:
_to_bytes = lambda n, *args, **kwargs: n.to_bytes(*args, **kwargs)
_from_bytes = lambda *args, **kwargs: int.from_bytes(*args, **kwargs)

N = 624 #: 624 values (of 32bit) is just enough to reconstruct the internal state
M = 397 #:
MATRIX_A = 0x9908b0df #:
UPPER_MASK = 0x80000000 #:
LOWER_MASK = 0x7fffffff #:

def tempering(y):
y ^= (y >> 11)
y ^= (y << 7) & 0x9d2c5680
y ^= (y << 15) & 0xefc60000
y ^= (y >> 18)
return y

def untempering(y):
y ^= (y >> 18)
y ^= (y << 15) & 0xefc60000
y ^= ((y << 7) & 0x9d2c5680) ^ ((y << 14) & 0x94284000) ^ ((y << 21) & 0x14200000) ^ ((y << 28) & 0x10000000)
y ^= (y >> 11) ^ (y >> 22)
return y

def generate(mt, kk):
mag01 = [0x0, MATRIX_A]
y = (mt[kk] & UPPER_MASK) | (mt[(kk + 1) % N] & LOWER_MASK)
mt[kk] = mt[(kk + M) % N] ^ (y >> 1) ^ mag01[y & 0x1]

def genrand_int32(mt, mti):
generate(mt, mti)
y = mt[mti]
mti = (mti + 1) % N
return tempering(y), mti


class MT19937Predictor(random.Random):
'''
Usage:
.. doctest::
>>> import random
>>> from mt19937predictor import MT19937Predictor
>>> predictor = MT19937Predictor()
>>> for _ in range(624):
... x = random.getrandbits(32)
... predictor.setrandbits(x, 32)
>>> random.getrandbits(32) == predictor.getrandbits(32)
True
>>> random.random() == predictor.random()
True
>>> a = list(range(100))
>>> b = list(range(100))
>>> random.shuffle(a)
>>> predictor.shuffle(b)
>>> a == b
True
'''

def __init__(self):
self._mt = [ 0 ] * N
self._mti = 0

def setrand_int32(self, y):
'''Feceive the target PRNG's outputs and reconstruct the inner state.
when 624 consecutive DOWRDs is given, the inner state is uniquely determined.
'''
assert 0 <= y < 2 ** 32
self._mt[self._mti] = untempering(y)
self._mti = (self._mti + 1) % N

def genrand_int32(self):
y, self._mti = genrand_int32(self._mt, self._mti)
return y

def setrandbits(self, y, bits):
'''The interface for :py:meth:`random.Random.getrandbits` in Python's Standard Library
'''
if not (bits % 32 == 0):
raise ValueError('number of bits must be a multiple of 32')
if not (0 <= y < 2 ** bits):
raise ValueError('invalid state')
if bits == 32:
self.setrand_int32(y)
else:
while bits > 0:
self.setrand_int32(y & 0xffffffff)
y >>= 32
bits -= 32

def getrandbits(self, bits):
'''The interface for :py:meth:`random.Random.getrandbits` in Python's Standard Library
'''
if not (bits > 0):
raise ValueError('number of bits must be greater than zero')
if bits <= 32:
return self.genrand_int32() >> (32 - bits)
else:
acc = bytearray()
while bits > 0:
r = self.genrand_int32()
if bits < 32:
r >>= 32 - bits
acc += _to_bytes(r, 4, byteorder='little')
bits -= 32
return _from_bytes(acc, byteorder='little')

def random(self):
'''The interface for :py:meth:`random.Random.random` in Python's Standard Library
'''
a = self.genrand_int32() >> 5
b = self.genrand_int32() >> 6
return ((a * 67108864.0 + b) * (1.0 / 9007199254740992.0))

def seed(self, *args):
'''
Raises:
:py:exc:`NotImplementedError`
'''
raise NotImplementedError

def setstate(self, *args):
'''
Raises:
:py:exc:`NotImplementedError`
'''
raise NotImplementedError

def getstate(self, *args):
'''
Raises:
:py:exc:`NotImplementedError`
'''
raise NotImplementedError

def gauss(self, *args):
'''
Raises:
:py:exc:`NotImplementedError`
'''
raise NotImplementedError

失败的思路

主要是想根据文件的修改时间来爆破种子

20210626GKCTF-0436bb67.png

但是没看到Python random模块具体的库函数实现,缺少具体细节,最终失败

20210626GKCTF-d5cfea9a.png

Reverse

QQQQT

拖入PEiD中查看exe格式

image-20210703093043860

32位没有加任何保护,运行一下程序,GUI如下

image-20210703093410876

然后放入ida里面静态分析,好多函数,可是没有看到熟悉的main函数,最多只有一个叫WinMain的函数,尝试分析;好样的,看不懂

然后放入OD里面分析,鼠标右键,选择Search for,点All referenced text strings,然后会看到

image-20210703095700497

东西不多,一下就能看到flag的字样

记录下push后面的地址,直接追踪过去

image-20210704133825642

回到IDA找到这个地址所在位置

image-20210704134707659

image-20210704134828743

终于找到关键函数,跳转过去shift+F12反编译一下,得到下面伪代码

1
int __thiscall sub_4012F0(_DWORD *this){  int v1; // edi  _BYTE *v2; // esi  const char *v3; // edx  _BYTE *v4; // esi  int v5; // ecx  int v6; // eax  int v7; // ecx  int v8; // edx  int v9; // edi  int v10; // esi  _BYTE *v11; // ecx  unsigned int v12; // ecx  int v14; // [esp-8h] [ebp-A8h]  char v16[4]; // [esp+10h] [ebp-90h] BYREF  char v17[4]; // [esp+14h] [ebp-8Ch] BYREF  _BYTE *v18; // [esp+18h] [ebp-88h]  const char *v19; // [esp+1Ch] [ebp-84h]  int v20; // [esp+20h] [ebp-80h]  int v21; // [esp+24h] [ebp-7Ch] BYREF  _BYTE *v22; // [esp+28h] [ebp-78h] BYREF  char v23[60]; // [esp+2Ch] [ebp-74h] BYREF  __int128 v24[2]; // [esp+68h] [ebp-38h] BYREF  __int64 v25; // [esp+88h] [ebp-18h]  int v26; // [esp+9Ch] [ebp-4h]  MEMORY[0x5FF6](*(_DWORD *)(this[6] + 4), v16);  v26 = 0;  MEMORY[0x7C7C](v16, v17);  LOBYTE(v26) = 1;  v19 = (const char *)MEMORY[0x7C48](v17);  v24[0] = 0i64;  v24[1] = 0i64;  v25 = 0i64;  strcpy(v23, "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz");  v21 = 138 * strlen(v19) / 0x64;  v14 = v21 + 1;  v1 = 0;  v22 = (_BYTE *)MEMORY[0x8114](v21 + 1);  v2 = v22;  sub_402C08(v22, 0, v14);  v3 = v19;  v20 = (int)(v19 + 1);  if ( strlen(v19) )  {    v4 = &v2[v21];    v18 = v4;    while ( 1 )    {      v20 = ((char)*v4 << 8) + v3[v1];      v5 = v20 / 58;      *v4 = v20 % 58;      if ( v5 )      {        do        {          v6 = (char)*--v4;          v7 = (v6 << 8) + v5;          v20 = v7 / 58;          *v4 = v7 % 58;          v5 = v20;        }        while ( v20 );        v4 = v18;      }      if ( ++v1 >= strlen(v19) )        break;      v3 = v19;    }    v2 = v22;  }  v8 = 0;  if ( !*v2 )  {    do      ++v8;    while ( !v2[v8] );  }  v9 = v21;  if ( v8 <= v21 )  {    v10 = v2 - (_BYTE *)v24;    do    {      v11 = (char *)v24 + v8++;      *v11 = v23[(char)v11[v10]];    }    while ( v8 <= v9 );  }  if ( !MEMORY[0x7C1A](v24, "56fkoP8KhwCf3v7CEz") )  {    if ( v19 )      v12 = strlen(v19);    else      v12 = -1;    v22 = (_BYTE *)MEMORY[0x7CCC](v19, v12);    LOBYTE(v26) = 2;    v21 = MEMORY[0x7CCC]("flag", 4);    LOBYTE(v26) = 3;    MEMORY[0x6124](this, &v21, &v22, 1024, 0);    MEMORY[0x7C66](&v21);    MEMORY[0x7C66](&v22);  }  MEMORY[0x7C30](v17);  return MEMORY[0x7C66]();}

很快便可以抓住要点

image-20210704135338529

显然是Base58编码

也没有怎么分析源码啦,就是看到这里还有一个判断

image-20210704135638645

然后我直接将这串进行Base58解密,然后套上flag提交,通过了

image-20210704135754833

something else

其他战队的wp

GKCTF X DASCTF应急挑战杯-Maple_root-Writeup

GKCTF X DASCTF应急挑战杯 Writeup —— CSAlab_Sec