Tamu CTF 2023 - PRNG (crypto, lcg)

WriteUp › Tamu
, , ,

I know they say don’t roll your own crypto, but secure RNG should be easy. How hard could it be?
Author: anomie

  • [78 solves / 441 points]

이 문제 푸는데 가장 오래 걸린 것 같다.

Analysis

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
import secrets
from flag import flag, m, a, c

class Rand:
    def __init__(self, seed):
        self.m = m
        self.a = a
        self.c = c
        self.seed = seed
        if seed % 2 == 0: # initial state must be odd
            self.seed += 1

    def rand(self):
        self.seed = (self.a * self.seed + self.c) % self.m
        return self.seed

def main():
    seed = secrets.choice(range(0, 0x7fffffffffffffff))
    rng = Rand(seed)
    
    chall = []
    for _ in range(10):
        chall.append(rng.rand())

    print(f"Authenticate. Provide the next 10 numbers following")
    for c in chall:
        print(c)

    for _ in range(10):
        x = int(input('> '))
        if x != rng.rand():
            print("Access denied.")
            exit()
    
    print("Access granted.")
    print(flag)


if __name__ == "__main__":
    main()

seed = secrets.choice(range(0, 0x7fffffffffffffff))이런 식으로 seed를 랜덤으로 만들고, Rand 클래스 객체를 만든다. 그리고 rng.rand()한 값 10개를 출력해주는데 이것을 바탕으로 다음 rng.rand()를 10번 연속으로 맞춰야 flag를 출력해준다. 문제는 rng.rand()가 아래같이 구현되어 있어서 문제에서 출력해준 rng.rand() 값을 바탕으로 다음 rng.rand() 값을 구할 수 있을 것 같은 기분이다.

1
2
3
def rand(self):
    self.seed = (self.a * self.seed + self.c) % self.m
    return self.seed

m, a, c가 고정되어 있어서 방정식을 이용해서 구할 수 있을 것 같다!

1
(a * seed[i] + c) % m == seed[i+1]

참고로 이걸 LCG 알고리즘이라고 하는데 위의 식에 따라 난수가 생성되는 알고리즘이다. 이 알고리즘은 변수를 통해 난수를 생성하기 때문에 변수를 알면 난수를 예측할 수 있다는 취약한 성질을 가지고 있다. 여기서 m, a, c를 구해야한다는 확신을 가졌다.

z3

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
from z3 import *

seed = [15292707418901107848, 3732399702731999469, 17727906530283792422, 5740441724751270531, 8708853459937082772, 10615078376953059625, 13017389135088601170, 12756134783055003231, 13176328566446297056, 5276211473026467749]

# a = BitVec('a', 64)
# c = BitVec('c', 64)
# m = BitVec('m', 64)
a = Int('a')
c = Int('c')
m = Int('m')

s = Solver()

s.add(m > 0)
s.add(a > 0)
s.add(c >= 0)
s.add(m > a)
s.add(m > c)

for i in range(9):
    # s.add((a * seed[i] + c) % m == seed[i+1])
    s.add( ((a%m * seed[i]%m + c%m) % m) == seed[i+1])
    print(s.check())
    # print(s.model())

print(s.check())
print(s.model())

처음에는 이런식으로 z3를 이용해서 문제를 풀고 싶었다. 하지만 속도가 너무 오래 걸렸다. m, a, c를 구하는데 하루종일 걸릴 것 같아서 돌려놓고 다른 방법을 찾기로 했다.

Solve

결국 아래 롸업 참고해서 m, a, c를 구하는 스크립트를 찾았고 그대로 이용했다!.

Solved Code

  • lcg_cracker.py
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
import math
import functools

value_arr = [
[8867289026099616930, 3100388368458364911, 11012612612822111152, 3553763262634053301, 5401992163525506830, 3802577809068939019, 4123451793823069756, 7817012668148538993, 4418295964672193722, 9714516383028541031],
[14895006062848545614, 13184494282524308555, 5839645882409261180, 15553940338338437553, 3310727070198197498, 7079238959161008039, 8852142265661212744, 2055261898208476077, 12685862460417988070, 8327538304492250947],
[16833079321975897880, 17784340646344753597, 9634395732957591606, 690518920529962707, 10752317369148323620, 4040135522852265209, 2068189971163025250, 13577899494281881007, 14537861419972208752, 6988257997766616693],
[8811210512227857652, 17677714985016526345, 2277225101309911218, 9554579400707461183, 13629936068980515136, 18128385074177963653, 14926717179739533854, 15372561348002497115, 9242320810727858892, 10530837434097508673],
[2991159697670699038, 3475834328473165915, 24895706424277196, 1717803743275126593, 7847993843726425290, 6555997079546348215, 9641940719668788120, 1211123003602522173, 9780510953735823542, 10772469154227966291],
[3185088266943822372, 16856905608318675961, 981610330286889570, 12390880568666725551, 6420531847364688752, 294839699134285173, 1897195166556125390, 1779257976405790667, 12088335929742246396, 3991695835285178673],
[10238209914032284972, 5460209267264701729, 7819557967073387050, 4593921590486709655, 3385940490520588792, 12268964961406007325, 16455099020084682774, 10150443889560462899, 17851097652418530308, 14240629152048184665],
[8349943537494362534, 4297037802114914819, 1347703166576296724, 757798125216715945, 15394582492534297042, 10761779783422053855, 4693042107739651424, 10225256180973570853, 4566401686213427518, 1487067095664121339],
[11987973417146959732, 15513426539919950473, 515274979322588978, 17107229499549087935, 18253958825185315776, 5144561925537278725, 4486635461590751390, 14429941670409020123, 17988539351616152908, 5277362322974592449],
[3272875691678361420, 4467493841292318657, 13109169869817161546, 642261405616117559, 7422548840093008408, 14093779976259686589, 13240126529021690678, 9678270890728627667, 3717904806731450916, 16727758706245942265],
[13961749608401819040, 4130031146828829797, 8270988025545981822, 17295851551386197307, 12822136328236310828, 17730435183956521249, 5914918828169559594, 2301029522089476503, 11197084434497465848, 16282318958233527325],
[13935820998792231868, 2340957083767314929, 13952086190268317242, 3463255295617205735, 17603686513072576392, 15616004610886916077, 7593161876043215654, 7419335383114434947, 13872051444738117780, 16387601927742994473],
[2367708137021733318, 15797908864823186083, 1697811323936294452, 6468516909347007561, 3605808975914282994, 8993146379861355647, 11784545778018336384, 1476919440044939461, 9673720994553064798, 3403961970617612955],
[14632104118495609642, 13491004195881278103, 8542085830330608376, 17554856007815877917, 12246699748174721302, 14918799307125947187, 14826228137665017092, 8438817444860840537, 10429337410401897026, 201262443058381839],
[727242865172403940, 13286269549476768697, 12862139302129010978, 2043896308843279983, 11901636794219457584, 9556199557922302261, 13741726916804549518, 7395209500326784395, 12207365532390229692, 12204738417996026097],
[5226361193323484432, 10130784938838945173, 16494630052633807214, 12878085135450049259, 3144158807994921372, 14032772940844506961, 9030641085374296346, 14371680458411244615, 13968515723769642856, 4596893107208673101],
[5582569318269685702, 16262401486417281187, 15301058140219305012, 4308599473687603785, 2145458505091835378, 462684261660228223, 13478469980846195840, 7677224992909932229, 13219690446917878622, 8268181225565595803],
[1523660276195024986, 12898838688908966023, 4576153996660178088, 2159976516489910669, 1464427048127423302, 8811745952244449827, 17714660346161386420, 4826455020305256393, 984003074290762098, 12555979904933929983],
[126547082954464156, 8731748723858026833, 12194851587498199834, 11341276220445965895, 7784808114970478952, 2196181795386050893, 3962591291961098758, 15164382113382091747, 13324697695629440116, 15513681386663338889],
[2109089224935408226, 16399948004576306351, 6345023819482489712, 13531529848972103029, 11338355893597528270, 7583305562428282827, 6739249743684069884, 3839630471462031665, 6680085498946462330, 18204041658276662055],
[14630982926170580926, 13413641925454296699, 3204089170868891500, 18167967979148445793, 17657937622702801514, 912587101662897879, 7628277793611298872, 9842333695312176989, 15038238322996354134, 4620776159013544819],
[14704701709580170488, 53493907006424861, 3691079583443315478, 14876818299364597043, 11929538602131857156, 11481424303877872729, 17455025871772050498, 5358420361150629391, 796123445202395728, 18039029571546202069],
[18200670961985626810, 1467699364758740071, 9037535799805306888, 14847415754150972013, 9900762982391730086, 623115057775966211, 6101450839122565396, 15171738277846876841, 13832273043699611602, 13642892256086068191],
[2782294491294682690, 7510879162237589519, 1741828130526231632, 9505676564052672981, 10255640339800129198, 6662908645245953323, 17018838752941540572, 12154997309264547729, 8591331022323970650, 2506030181648323207],
[11234052632499834174, 386380546687390203, 8213513647720372460, 13330119481419151329, 15887784606153412586, 7899237475721923159, 10091807687235701176, 13805199692009971421, 11774830989500895702, 806599032341532403],
[8300049183692798058, 854327389806965975, 3608357675551997496, 9169006654863656285, 5472160679467528790, 8644205409068454259, 6154362867017692228, 375924128901076633, 7492020820464736130, 440602548199347791],
[11558370982278543894, 4317602607708809267, 2766674752555013636, 6433117189200424793, 1163228285800072002, 6475775425366761743, 4106646581277321552, 6657453002491912917, 16642399402912752558, 4627426230987726379],
[9176831416081544290, 6012069203501801135, 9004405420014142832, 12561419548560652149, 18187721460045624014, 574183730898547147, 2725189284580649980, 3570619898969332529, 6565100070659773562, 10270047106495137063],
[13677842479808722104, 2987183347614692829, 3201466174608737494, 17986981237197819379, 5169852428109578948, 6231680139079466777, 5710815901163520514, 6664671632382331599, 17140484865351641616, 2101834991851968149],
[4633588486946452916, 6122956346242873801, 16655618269148156786, 5539528001230618111, 13292550610721617408, 13295532528023572037, 13501284821858441438, 9251449022754878491, 11160684063961861004, 13770693391276793089],
[17299383331387067396, 13065829148296346969, 16098495694389463362, 3991558490299875087, 17163118798757658448, 3663576396867129557, 12979098425607768494, 10114075828877548587, 15341701465297442780, 7112988904079109777],
[1428568366097891942, 6337496892206785987, 13012171866948546004, 12396143281391196777, 6783659025353203346, 6903870906632240543, 15198490714885807136, 15678191199385801957, 11884036482466341374, 8341778046957283771],
[12077661547009871844, 3255163426751334585, 3245347561327467042, 2568052847080606575, 11174949785175889200, 14755028155044738613, 3526018644061625486, 3487613482027987595, 837657301706973116, 2458121596652490225],
[5523160823405994428, 12163215340822583281, 9158375199828423738, 4738590282036483047, 13368080207454952840, 60330628914165229, 4162813395077400870, 10532963154697385859, 7351438799447111316, 9187187171692787241],
[873931018331865996, 4961008043770098945, 10268161693364898186, 7526882041215013495, 2846026779968485976, 11908407080730016253, 10023349327150850422, 9081572846155269395, 17885971952298384996, 16646955843758158137],
[14117057574820939498, 14846280829748141399, 9822453198596417720, 13666484049608964573, 2203451663831423190, 4464212214691787251, 12882737634380494532, 3465181234195645209, 17736576274984900098, 6338654109127700175],
[5658271824067632014, 3039130312766025099, 6785806770050664124, 7052065290757034225, 6977159145787019578, 1808635142856008935, 14115360414807306888, 14729176788807491309, 1742274373691561510, 9536467342460434563],
[8457322449329128800, 11706182718713787173, 14516612421740595518, 5522077119785303547, 12088439790994912492, 3998862261719139297, 17667079026686888938, 1543343976564930135, 14257014014432421304, 6056531089230834397],
[5853949490429562094, 16540889291739200619, 16069972633722194204, 2023467304258303185, 10492035477856058522, 4527429097395525063, 17244702540938403560, 9292854607338542285, 14017669400234662790, 7988496783295048547],
[8990859015354022950, 11626717627012380291, 9033521094343520660, 14570401077287722281, 9233494352537050194, 9921811818931708511, 2075484779034477536, 14081241237412088741, 12374953548537439166, 5321567458443928187],
[2501824620693468540, 6605202164463364785, 13037091578942931450, 14115603409003792551, 14745943388365002056, 2899169743159803053, 15575271540930894566, 4782580049077731395, 16403374133301088852, 6581426701492482281],
[10614745564617910298, 12994425083963297607, 11171615255409057384, 14524945601133343309, 6097066497884901126, 14869218732448042211, 11405168484889573748, 12193374361579420809, 11239347632050213170, 751735515663540927],
[11822229604799408924, 4077103487938944721, 4618979562143911578, 5114940534867521479, 2442759505377501416, 2529709207661633229, 8529238665266728326, 16668401618408154467, 6421579100170458100, 367100142732370185],
[5451434008959662308, 7214065144025667001, 18155149021322681122, 16773429532725039215, 13668505188035505712, 2342910215262761781, 14086852263454150030, 12762114345439668107, 13588918370988173500, 15298163912706390769],
[2298694336461850902, 11035956626191299379, 5164500185108040964, 5862375371973345881, 17122275118260281922, 845362442548149263, 2989776314693644368, 3380380903056393685, 11885353426376544942, 8432647176761329963],
[15069683516895607374, 6790494538062018379, 7375521283540477820, 10848878574135076017, 10702858666938180602, 627485070352396967, 6402981706896287560, 17530624080524154541, 10574696765045808358, 10231057913488263747],
[11711156544779800568, 14859806420295519773, 10755718946365525526, 4274844350839196723, 18263099102261299716, 5775241043780170585, 11110006472931186498, 10273939610160252175, 7925558300094438736, 11907944568939275989],
[10746209935196001034, 3618722580142006775, 9884185071574296536, 17925983285082602877, 960993732159640310, 10968335297886526611, 498628532078719972, 15958624639722126521, 12787199791963184674, 15319814181110816623],
[17924571917219383696, 863609349597516821, 4248812901100005870, 16466929070257130859, 10966717351459380764, 386990228605656529, 8255581700080748954, 16232815094285129415, 13259597083100832744, 11021739122189430221],
[2798086452070131370, 8600524455743548439, 3140377087599190648, 13771834233539087005, 9472614355009870998, 7974347915846792371, 15274428055851676804, 2471123652321257433, 4486835346780798402, 14443733748522263951],
[364510442556624052, 6704476462697508041, 1440274083389264498, 7145191385311492351, 13402859670044630272, 2460113547601908037, 3727138121145690078, 17364857400828444443, 17583539939751363212, 14225891051723206657],
[10679737800641080988, 17478889369562075217, 7005001708662335002, 3729771981252773191, 17546593748217179240, 11676603835864512589, 12475669505140649222, 12270968464065422051, 16593340703584298868, 1242375977324421769],
[4495563215113416740, 15045956663472929273, 5153341651897229410, 5092436580427348655, 889986649005576560, 6068846560256127861, 12922043036062686926, 6177253950266920395, 1955408873097820156, 5796003727782729521],
[17028974797201535468, 12854384363204195553, 1508805523031015658, 11873860720592322391, 7639650477649973944, 10627048893980756957, 13843354809999717078, 14407534130793346035, 16442419118134640836, 9275530655007569177],
[246905628842646592, 17036488390142614917, 13372822276138677534, 387533368091169115, 8293058324581117388, 371958111100999745, 7218365592259430858, 5135875742835639, 354375426255659160, 6005160337930930493],
[15492028295530370278, 17485540190151107139, 7463908329305537620, 16947584731924202217, 7238469859068201234, 1392330285547991583, 3837069334263661216, 6503367032258901349, 6010467456834954366, 8893884900001715771],
[15432599508868324242, 13384953910469930655, 1224616136947634464, 10711537154548571621, 1226300715469377278, 10827773072548825787, 9246579057486914732, 10824656460472361633, 9031532824210888106, 14433210438136076055],
[7575212830376199740, 6180851232090336881, 2203621318913557690, 4475918415359067751, 13690465480422849032, 3858170389989450861, 7959339877338386854, 14238873398771696131, 4804828608640797460, 17938524743152647337],
[13784859698773207124, 10371371456164159209, 14648355674364024082, 14612361550801874463, 12128767025013550752, 6781441409005179237, 6750855378618577022, 4640419281943024187, 6594281201006291500, 12283545100404874785],
[7300966056528243488, 5704567910290907109, 6233560262172006654, 5840544394548772027, 15615937675964685996, 7588543366409340065, 7100658218377019306, 10330071151565990167, 11798634657090360184, 2449052096014581661],
[8154703422438920430, 9272213936998961259, 12593463146803571996, 1951985665097541841, 5559802375763525786, 14691482453492246983, 17588109310649254632, 14541177643677714637, 7217077433446522758, 18362996991361728355],
[11535030875503939418, 2707135240261100423, 2324890840920413096, 12843515433832090765, 758849396355785286, 15467120201130081571, 15766881676531186356, 18003679405497864905, 6322026040812720242, 11944683120758009599],
[17075843071584444188, 16088295295624897233, 3287730975544812186, 5492508428077421511, 10048200063151052008, 10796273630169178829, 7073117533291274630, 8429763880649607523, 9804641479826819060, 12437475454506657033],
[16044771336982165142, 284577829196297907, 1189126140835004036, 8262727422777072089, 16725869960331425730, 10386894692876175247, 15719459007493130704, 14731515241872024917, 1903627635144380462, 2223098308995390635],
[6279808029989953894, 9031640373987131587, 14440631372696876244, 279384735768673641, 830802694328929682, 1985153687567493279, 7848395926190175008, 6583740769545078757, 11556255329581195518, 4171622571591771323],
[13622640050209395886, 17624959778970735403, 17083859957859887836, 16641460448630508945, 4562638385512917082, 1227399347328901255, 10903578670855980200, 14477165340680569229, 2800228526643489606, 8748327601305266723],
[16556262401654887454, 17130717217904585819, 1427867318005118156, 6289124573805394753, 9674481897252550858, 3456464256882151095, 17135104840353806232, 1730613267001326653, 8731850980834229430, 12201907318856179027],
[15640468007513841174, 9281136243301047347, 13209102281647512068, 7537597821910303577, 3585415647943501634, 7586006749877441807, 6925631677676039504, 16699983916907935445, 8600757696655345582, 3156470710513193515],
[17890772352087682590, 16978183429219692123, 9349779972457004748, 17945519593408572737, 2308999006651560650, 11746978869281271991, 17331546810897047960, 15285109234485005885, 3208124978020964022, 18446438672641449811],
[13796524676963936198, 11176254951324465315, 14845084619296490548, 9739914677432509001, 7971326089299262962, 15065922024072147583, 6530951533243292800, 7913798024757964485, 11096485570722552670, 9340997357764518043],
[11966373344999219742, 14023021561725891163, 8357795926189806284, 4838852622100533569, 1839437598164887242, 16240729831119910071, 13805713924700698008, 11810313045161030205, 3254860872890813110, 3224471344951485267],
[8672143706284035152, 8082105374892773845, 4262948656314846894, 17442296180081161515, 4480071634479289564, 13977037599718154129, 5184902547655950938, 7270138387779134087, 3577458766602358440, 7036981937338561421],
[4549989384680726506, 354618289907751511, 6021917929925302712, 9683967543235751645, 4110973829723005398, 6956033145244098291, 350941105394440132, 5768192198506817561, 10623636149069827842, 13607875411145608143],
[3046495147871464342, 7293980392325971891, 5222557080334166916, 9868301142576036569, 16829992184202665154, 17571328139991695503, 13383276868306134736, 1108900227645716053, 2727139412716201262, 3705178740322370987],
[13457706418191751024, 6244539169753239925, 6598089017653867726, 12546284449087634379, 17143399596407397884, 2302951434699150641, 11329696404564981370, 6985800819182546727, 2404910607147382216, 18364879303492960045],
[10190231849411736798, 2149722808446877723, 756921193158150028, 15334074180493248769, 6586706252589723018, 11760873659661649527, 18290287347143097944, 7651229940624248317, 11426031839205688694, 13632945809391352083],
[1186609885310298992, 8089105791572424053, 4745977407210711246, 13877791844476698571, 16783689509705069052, 14376443599657564465, 14297172469765712506, 8827464507227927335, 352496566311782856, 5875519001803465517],
[18218920620743675198, 2726925819064078843, 3690440778325924076, 14832740746264590305, 8888187438231392234, 4542378805550860887, 18276232403656575416, 6681438840054193885, 18297422194710139350, 8143534422750105331],
[12197093384330632188, 11495960201883798321, 11258760471364730, 776854472524166439, 16709470456748381128, 9255328945646097709, 11428398743455987046, 13796262202661938371, 11158144224486615252, 13595444467484836201],
[3411583736020326432, 14038348900887904485, 9415382328368725502, 4025338077607753147, 1047166249291692972, 16914238979998160289, 4937612976171308202, 8653902029048336919, 6823429645629595768, 9648043705703317661],
[373050017720068720, 7293707148975190133, 5203703289130225614, 8567389549504086731, 854068557076332796, 3590498217138308145, 7936704024319091066, 12676999540440286759, 7715996826030860488, 15894946932261928493],
[15509005501571497128, 210223333279308173, 14505409996272264006, 4749109762470429219, 14093924357397238708, 13250088827512786889, 10365669486614266226, 14254919775421408255, 5912028597470934016, 2101603603884311621],
[7052747425629655922, 7024226451997916671, 5056279271407908352, 16841876400373747269, 18391339055796361438, 14623797837699429403, 12917870820944841612, 5889371107135593729, 538236770745831818, 244849034043292279],
[12387377937744619602, 6178850313739378271, 2065557952697413600, 13396290220154677157, 2006821505195143102, 9343475342498012795, 17510500126238127980, 9186143919309975649, 6654631926263564906, 16447745143156739799],
[17365225407392368346, 17608932392662112519, 15977970302564908840, 14122050528115164685, 15190794607049679302, 15147159758692981411, 12136355222080826932, 7305027006647235657, 5984773468501366770, 7120999704984171647],
[15405778496895363676, 11534304084335651601, 2656986649649241050, 17311382162411667975, 13893748488993786920, 17884697981384165133, 16559051850676987590, 17323189200429495203, 14708434112223865652, 311029689421391177],
[8304516776386885166, 1162591285698976427, 6431822418391167068, 1073889099961288977, 311371602490733018, 3037896498151026695, 6700673561615774248, 1177873908749632781, 7486323408886455494, 47481149297983907],
[12257118845711129146, 15637717037138088423, 9091319287374107528, 111732322688664557, 7709530265517854502, 15448754256864515459, 14499631522207124628, 4350395051975812137, 5029353406978211666, 14983991754724675935],
[2442840422067682098, 2535292459284100287, 8914483027216955328, 6356774445554714373, 14342323047955604638, 11942854402330484443, 12400214517583155532, 7064574322598357441, 7840282342838321482, 6023903518267185463],
[7228160882210756380, 681010882384296657, 10096262737097366170, 14112598132464856007, 14538579307178380520, 7037792214992468685, 5992316918031997318, 7641497722597679459, 10754508795372437492, 4191343932316122377],
[14004647814735881340, 7090007383879128497, 9595163571211524346, 16430243833760873383, 8435436033217614920, 10196020007019329453, 2549105683370770918, 9867595489197228867, 16781302101064933716, 14211712403488226281],
[5188219849389750246, 7499032207411286339, 924388247511312212, 8442556857151887849, 10687356858484161554, 18004604360734634271, 6385847952149806496, 16348395003016961125, 2787866711887669118, 7895362383153653051],
[11742528976729658208, 17024504224835696933, 12545914869961336638, 17117898636692853755, 543385214395605740, 600091645877692897, 4512835418141706730, 16237738672424938583, 13599323974747665336, 16016150572111327453],
[4123822510693261536, 7842592132191771813, 6183278983655258302, 2371136176893135739, 16034443615949953132, 18018709151683220833, 7359078527602279274, 9714328414399376343, 6205873940013109560, 3930188165584872541],
[10513212780032198286, 5988662947549168779, 7389373759282510268, 11804699400335314929, 2867519379916459066, 13391396477140159463, 1669153237193422216, 4491108924088823277, 14738610582775980326, 2393206157517303683],
[11379299908909661028, 10408442618965443129, 17206265907652614562, 6640726910619101423, 15488299063688759472, 17228223193079961525, 8155779605106041870, 9346470541030340619, 17717168824968747836, 4999540058013194097],
[9195558610552625404, 7304245622006398001, 5930857928283568506, 3400827429956091431, 13296163782455689416, 13544841377674540589, 12256851374065719910, 15619261493604851139, 7817886783580734932, 4478609929493713513],
[16939086379841039104, 6652083565329946437, 16271908238737065438, 15957024050284418331, 12676759120761319564, 7699407868182124033, 14750308840699113098, 3200385954213464951, 17912446029924013912, 26923126217001725],
[5642487325393112178, 1949999904224156415, 5422784875499931392, 5237274935304233797, 10883833135510651358, 13114723401852879131, 1025455116080630924, 15416170788434878977, 12251372200562207370, 15241198521862485879],
[12368867804257343756, 4901651103117344897, 6172532788324868874, 1629648699096265207, 1765295795384989656, 11124945439306976637, 11304728290089771766, 5263000920393084051, 12658926106641318884, 6468929893902077113],
[5879184119730049316, 18282078713472818937, 7084834217374996834, 9238215082426439599, 10247542181299577456, 6104135708707883125, 15356994279233800142, 8168193065687767755, 10202999321169426684, 3030678359727479857],
[3661724380709553882, 12851309310735046919, 1296626902659759912, 15680279988685227533, 12028162944126706118, 18286503901522451107, 7390172192799616564, 11859791313015649353, 6668861354859534322, 17429575716278629503],
[6917601336846901202, 16145890399697392607, 7261793156546992992, 3001637811584622885, 4198824188533911358, 13017707903196609531, 12778129782507580140, 14693983528674103777, 17760683498197373418, 8002052510788359255],
[6415113678347389516, 18367730110650189505, 12994780622613566026, 11196147422277578295, 16217665115061286168, 12214248516655648701, 12679664332309937718, 7899867465036776659, 10135276949960592676, 16804578820027484921],
[1034514745089929562, 16041285190076484999, 44033692704368040, 3038324796601394829, 6730226154691175494, 3217002830952318755, 612266451195374772, 5352896985061756105, 415010495070138994, 10188980086130039039],
[16023284902306193880, 17248757910263832445, 9572675090793135350, 14878538684892032659, 12048245203524914660, 1225435726289288889, 10768088819122726946, 5128365571086094703, 3369087004459053872, 11106074423160097845],
[8581606460425462400, 1835035410651253957, 15936978892679213406, 11293643246002179739, 4498132878349234188, 15223263426744333185, 17387508317624099338, 699709124941999351, 11386441473578852056, 10901210581139624061],
[14070823954108118188, 11656161000563471009, 11065113869368780202, 7176349964354217751, 15552801623992682872, 3232155780341124509, 1657819959022971798, 3709112730327744435, 16121105434390195076, 5551630550350363353],
[11439700799427395396, 14576104064689114521, 9627000483233114754, 180246689541059919, 12437021578333134480, 9604261514346904853, 17058001910102128366, 14857255153345105515, 10579681526786941724, 10575006473626466001],
[1021665812970843926, 15154708873859576115, 12657244168575861508, 6352876167385518169, 14073341854281066562, 11829896112496908815, 4606092519066437200, 4225734562521789397, 14874523708360194222, 11771211822828062507],
[6216734466751032778, 4679564510501574583, 9295301971546268824, 14186537530567793981, 1193653702571549110, 8575129182598682195, 1388103240603419812, 3545403233088209017, 4825150124862251234, 893965288723406127],
[12791741445890116146, 15633188302069088191, 8778836567613091520, 15443912806597663237, 14165571453794321310, 18193738478911486427, 989358032643053644, 12925472031242046657, 6413854617642741834, 18280854922029499447],
[299770570343140146, 2237425279967118527, 6808391728054765504, 8610427393040029445, 3823679761056380062, 5579486480956501723, 16049685711807586636, 623669692150380993, 6139720610957185354, 17812352534435653943],
[12252729471561708372, 15334850220828055017, 6640253035691354130, 15455601693674196255, 14972104662075099552, 57553555446978661, 3971195325841527678, 15758060451131687227, 17395014852932425004, 1217660061216470305],
[12657582059810151952, 6376190662551558805, 15682042020737870446, 12149743155759067115, 8228794430445808284, 14384493489474223185, 14852614867115164186, 10259501776920990023, 6929347806585350248, 16956396811650376781],
[10159570428695414592, 34084779020645509, 2351849752424540190, 14703680327616860251, 18429762625247570124, 17275024129832828737, 11385044241053879498, 10804801536916517559, 7661543098857647000, 12137639757310197821],
[6237222379025603514, 6093230457446955367, 14604531942229784840, 11588524033539366765, 6398163144705587366, 17198143289365841155, 6080266248831736340, 13710001547779671977, 5206159037610234066, 8736836194624669919],
[8018027662253772896, 18288330557933333029, 7516211485150469182, 2109758411514928379, 16446121878563196908, 9531021124577938145, 12004415016043425514, 16647896863776089431, 5006751030557970616, 13424427781728043485],
[6417662096096424832, 96826861624074693, 6681053452061153886, 18270830423190379419, 6308702187886670092, 11025337268860549249, 4431764529286281994, 10643847341400631799, 15002447681971081176, 2151221928269710717],
[6569129321295595976, 10548065400366883629, 8393493750642457446, 7302002509333463747, 5776083153851104980, 11168112067825659753, 14283225657878906770, 7865134487038331551, 7738701468067880224, 17461567232816290277],
[10447052679044684928, 1423615979410747077, 5995782210793790302, 7880602923161395355, 8806023560559282700, 17319815319884854657, 14475636354643667978, 2694728490097303287, 1468825079618410712, 9115210125122581117],
[10905423516125443002, 14604459664273502567, 11583536854555889928, 6054047794845685613, 11900928222742171814, 9507308125989584131, 10368218113446998548, 14430775026879938473, 18046040948109519058, 9244972481016856799],
[9465191183196301846, 7462149060710520883, 16826195198868047364, 17309336151903067993, 13752573763900388162, 8143641949939650831, 8508972334549358928, 15270024798909666005, 2167298923322512302, 1969673119576935979],
[11657629366455012076, 11166431115885113825, 14167239973981237738, 18308866371808719959, 8933182642552167352, 7647047903684344029, 11137471290352292822, 12169012012216588531, 9558345526014785988, 13889798715185926681],
[7936422101934613920, 12657546895911363685, 6373764353535168382, 15514626698606931259, 598085928724263212, 4374440934555058465, 6688519304946208298, 339230198549582231, 4960139626211622392, 10208240881830016029],
[7404393046297866994, 12841030204394929023, 587368565191625088, 3634942850803027909, 11003383747184754782, 2916971533656463771, 16803595085200484108, 15749928308841203329, 16833897034889036042, 17840762837351286775],
[8446708782872638488, 10973839733215955645, 878434569809323318, 5271753095714654163, 13262826203829656612, 11244548452478277113, 1110592125199952994, 2843880343958550191, 11760302996044447088, 18250911557556129653],
[4461062202533214150, 12665386795438950563, 6914717420938662964, 15946900202028954185, 11978213591134293490, 14839998545045979775, 9388975554147265664, 2203270656327024325, 4451722696888265566, 12020960905937498267],
[6325977850746611294, 12217358006196492187, 12894219110628138252, 4257403095283061889, 17059652468887996170, 14971143709569983991, 18437991906303556568, 17842844522695893373, 13671163201186236150, 2526313122663162003],
[13274782473659071826, 12069531070707926879, 2694160561917132000, 1429638035186591909, 6411304059327083710, 18104866398249088891, 13303928540647175276, 14080609692887064929, 12331376976310796138, 2314783974805559255],
[1371925501023810594, 2429139202095172975, 1589908281180970800, 17469951032939227189, 6388256481685821070, 16514583541001966731, 14254875832853055932, 5908996560254623729, 1892393035958901818, 1447910965197364199],
[14470663731499396148, 2351617493142547017, 14687654437159331314, 17323976183678073471, 14762735956375766144, 4057856935902525125, 3290967471630959454, 5715826658021583003, 7010413855588643340, 4103210119168048513],
[17829644423943822696, 12760356387293359437, 13467619258892875270, 6928525178130812899, 16899635448287299700, 3929969288121927561, 12913463848479279154, 5585290007011784127, 16450129009622072512, 9807513167640354821],
[13382992608650847226, 1089286311430877863, 1373779193892366152, 2557044010025506477, 10415340028373982438, 17682187156841826883, 2585804957255648340, 12399845387253770985, 7039104329870823698, 6082852844638493215],
[4886494782055373126, 5126746635048816675, 3257380417886869940, 3398319949679406537, 13123147643364431730, 1606727780377760255, 183752403808147968, 12678915862762209861, 7848223066243554526, 6571813433228265499],
[1464063290508461950, 8786646676536116539, 15982810322286389548, 14456011888897333537, 1340640353600226858, 270464029867895191, 215273987175216632, 14853905115089947677, 10348528887181050902, 13072218414529550899],
[4123571989791835800, 7825306189993396029, 4990548971967329206, 12306485738973786195, 597288598551873188, 4319425152660146809, 2892430354197304034, 15110253702518462255, 9589837346039005168, 16062734296857050101],
[1595176522484458364, 17833459682879869105, 13023609253880561658, 13185322979700276903, 5896825987551077192, 1052623519414190765, 17290790618450508006, 12472931955673749059, 12082077550849310804, 3559867691672622825],
[1911293633918758724, 2752052224427490713, 5424162748401343106, 5332348165501642063, 17443886019131821712, 4589770528974843157, 3099517246201800430, 10952505177119161963, 17853094272840110876, 14378395961137243857],
[5965554835967892180, 5794914060174424937, 12467444604134736786, 11703450294657463967, 14328075161854294304, 10959750261340071397, 18353005084082861822, 11978753789467955899, 14877272230068685996, 11960859820713994913],
[13635279752893255972, 50355190447529721, 3474508140879550818, 18380132836174387119, 13850568683783201392, 14905291421853763701, 13894184053884356558, 17914751958833470155, 186032220969482492, 12836223246894292017],
[16452900385875069348, 9998738129097136505, 7383400180449009122, 11392522460823735855, 11320798701036606192, 6371859275724659445, 15383176329681814606, 9974754546600765771, 5728532988199428476, 7887150637859980977],
[975484705026012068, 11968212425666177913, 14149918127746004962, 17113658981577658415, 250849011447127280, 17308581789851782389, 13700522782361681486, 4552124223768890187, 501922186991045500, 16185886828672587953],
[14049561938669887530, 10189081935325555607, 2070378736500375544, 13728924302559051293, 6511829117387406870, 6594351330701835315, 12288384049397398020, 17795016091490640729, 10371001448023803714, 14622825112679494927],
[8225176568250711902, 14134860998012572827, 16074717029970841100, 2350830645414939009, 14633361943954378762, 13577794152536347383, 14530592839530388696, 6486725947281032829, 4862232593362026486, 3452655615207898515],
[7325877545279738858, 7423460634144087639, 14156693765784153528, 17581178006209909469, 14062917637362898390, 11110625145143304947, 10316627992796425156, 10871056701990374425, 12233149488953770754, 13983831420880359375],
[16083375904554397700, 2948292991680344409, 518031615138696514, 17297437370860507919, 12931557871963743056, 6833777627439793365, 10362054450606951854, 14005482290916716587, 7147586240356760540, 13568104668168135313],
[9860557894645199144, 16295708076974882829, 17599212888693818310, 15307324528752608419, 4740980282485538868, 13532990238439804489, 11439122766868929010, 14536219818154933887, 6874987472374651008, 13205533751112129221],
[4113439792173103428, 7126184554300862361, 12091388330311160962, 4202311474540283727, 13258330637636302992, 10934354385136877333, 16600689626062471406, 1749451628318326891, 10031697911707245852, 9657625180546554065],
[12079193783672782500, 3360887756492169849, 10540326313445100258, 7859496753039404847, 7349697822141937648, 9067059737635804149, 16884567464455283022, 2890278403712776779, 14961769119086081660, 17791145162914295729],
[11283122857066504942, 3772226041787673195, 2029179851415727900, 10886201231718363857, 13278122040185041562, 12299961160999838663, 147092718349493480, 10149397566115050189, 17778901334685053318, 9259083228438272355],
[7399210033346454230, 12483402310747448307, 12804532050934558916, 16515740050135639321, 14334674963076464642, 11415136545669824719, 12881170555416737808, 3357052785696431253, 10275713328539137134, 8047944868237500907],
[11694113410536044248, 13683830157476333693, 3400333106679892470, 13262055476397961107, 11191368259691287268, 15887902896607205305, 7907399517033620770, 10654988537742836335, 15771190229583194160, 18300969566086403381],
[8049735646312071314, 2029437384246372255, 10903970997032824352, 14504235846882815717, 4668093454598497278, 8503799114233934779, 14913072597145399724, 14431085149007242145, 18067439374893472426, 10721463929109639191],
[2696097122251550912, 1563260698261496837, 15631267811495523742, 8646322718037144539, 6300457185857321548, 10456432128835499713, 2070798014976967242, 13757854517443878455, 8508013944440481048, 15203895881397092285],
[17685177855345059336, 2792163153978687597, 8191816887433928102, 11833043021654490627, 4823229250939582228, 761424988059244713, 15644836028668782034, 9582529702991966687, 15558506926611394912, 3625821661032255269],
[10285848704834387372, 8747285832609767329, 13266912091368294058, 11526474692644260887, 2116758622943281784, 16929136467119581853, 5965539587549396118, 5793861919298196659, 12394846883674985604, 6694207582934632409],
[16662993260956209502, 6048402435986255515, 11511398461441495052, 1076498669952439169, 491431931880096266, 15462059226017090807, 15417674393734823640, 12355120966258389117, 3953119281189474806, 14510813370140039059],
[808205804364973320, 425968280054504301, 10945067250051245222, 17339877305153855747, 15859913338204743188, 5976119987263734697, 6523909499587558610, 7427897702512305375, 14462851483191177312, 1812572359875447333],
[3464937459606526348, 17719755828335698689, 5178043290332802954, 6796849632481923191, 7814022798513909848, 4211994959882782717, 13926491126268733302, 1697195879645913875, 6426051253310747748, 675678709412355897],
[10444205669711294678, 1227172335406819827, 10887914848232361668, 13396361579650890521, 2011745310433865218, 9683217903969838799, 4059248720375019024, 3387000600233038485, 12342112531565036142, 3055537287348119531],
[17779609461642040498, 9307943988470387775, 15058836698332001600, 6042064057173219973, 11074050323342042654, 7792965288509326939, 2759026769566561996, 5905406362997261633, 1644669425200917194, 2801725896605976759],
[13662389174465413016, 1920905278926365757, 3415255729952375990, 14291716482199323987, 8451001365147119524, 11270027910155147129, 2868674704903984098, 13471113901279386671, 7169655502800099568, 15090883776758528245],
[4833394564540976836, 1462831626555472665, 8701661863779855874, 10118858242104403663, 15671687977950443024, 11435314203426574997, 14273428940632506990, 7189160997036746731, 16436762879087182492, 8885250160732943441],
[10230397123600839054, 4921126727494933387, 7516350870378474684, 2119375992247308017, 17109734949097391930, 18426834844018291431, 17073007225012598920, 15892621882167573741, 8233009520699042854, 14675334716947408515],
[6982897219557017034, 2204562232985833399, 4540841486346091672, 18170157378527499581, 17809006179857512886, 11336317545337982547, 7442659532519627940, 15481417753696434297, 16753412803609524450, 12287350879064986927],
[12335665912060183356, 2610720541513277297, 14119020701030169018, 14981736538184978279, 722153007028610824, 12935069337555043693, 7076068753239537318, 8633398057079732995, 5408655579795925012, 4262353531727793577],
[4267092785397013934, 17728241086750687275, 5763526120967015388, 10301676798823477905, 9839424317857014106, 14837491278590115207, 9215974168692610472, 8712919133665367693, 10895609864204719174, 13927317681743558435],
[15352056503978231050, 7827486573053500407, 5140995403114531288, 4240545414421178237, 15896472489418024182, 8498701420980123283, 14561331762632406500, 8607711641320261305, 3636292892392378402, 11096536616849938799],
[17027027727640810764, 12720036563514190977, 10685551418130251530, 17880028976314842615, 16236890500893733848, 13540800139094538621, 11978005912045584118, 14825668687925033107, 8400215412801945572, 7765797198338144441],
[15021933103315449546, 3495716001031128247, 1396731112923678104, 4140726423186031165, 9008962094192876214, 12875830066893255507, 2988559077576152484, 3296391541949453689, 6090087509997685218, 14387668568230144559],
[7157414067549684176, 14246224744479866197, 5312071462504532014, 16044793512331228331, 286107928281657948, 1294702977724846865, 15547529168176227290, 2868356329005689351, 13449145964297049128, 5653867851018809101],
[7374594347533511120, 10784919989654373717, 6289716337769721902, 9715313610791124139, 6273852491043707484, 8620708186696129297, 4533054523327269850, 17632856930228793863, 17628763394665921576, 17346309440827733773],
[2342052956166955452, 14027701385843513329, 8680703790305735738, 8672751172390114279, 8124020536212233608, 7155094787357570541, 14086194411224025382, 12716722541561067395, 10456883903364724372, 2101970457493468713],
[4772590411956129490, 15714089171910557407, 14360996586674467424, 13231328573932016677, 9071211989541121598, 17171072845922187003, 4212405651219599852, 13954828828509115617, 3652497334232293610, 12214643103804088151],
[7024552045636262550, 5078745232453774003, 18392027712538477188, 14671315152905416153, 16196565570157927362, 10758379918323891087, 4458451415966420432, 12485242522330184021, 12931506650143323182, 6830243321830822059],
[8964158918272436998, 9784410928382949603, 11041567404879664500, 5551643914605234313, 14128548633570135346, 15639163883442654911, 9191151682389195200, 7000167578729713925, 3396217015901918878, 12978045212717783259],
[930350092441786838, 8853924157354637043, 2178212425054752708, 2722704739101523993, 3399186260909639426, 13182923118250501071, 5731235547516544784, 8073627230741006229, 3677956709842881390, 13971340020934644971],
[8133993277912905324, 7843213964703918945, 6226185426993410410, 5331680767225631191, 17397835538087071544, 1412287336887081565, 5214105876660869974, 9285168089118547571, 13487299643055027524, 8286471685319318425],
[9877798999468753552, 17485344309800136981, 7450392585088596718, 16014998380955279979, 16676987937050773276, 7014035086511155921, 4353075052821416602, 5214273465324919751, 9296731706937982184, 14285189272596015821],
[13345670530455246326, 16960806989643967379, 8150805641731997412, 9003267068221273017, 12482873274852634914, 12768028574192434799, 13997000154929075248, 6562318857209508149, 10078143378426823566, 12862362384197416331],
[3527923150139187946, 3619024401379797335, 9905010736981845176, 916210124493907421, 7878266368950957270, 8644801320039054835, 6195480723989131972, 3213056259930418969, 339953050684289538, 5010016423506426575],
[2251345810918236694, 7768908363681919027, 1099098956475416068, 2050851701965502297, 12381558919652797250, 5777338065403635983, 11254700964950298960, 1811115485769460437, 14286504075835460526, 8091345326040540715],
[16278112069030549596, 16385088340534825233, 5319707000620292570, 16571645642318706695, 18192160823708113448, 880499823610318093, 5414255607983293638, 4648755476656228771, 7169478636217407796, 15078679982552795977],
[426316868124203456, 10969119826860486917, 552761031281981086, 1247023011037591771, 12257611466755625804, 15671707889208357825, 11436688080222696266, 14368226439564874551, 13730188423370108440, 6599053453350350013],
[13150327040177579016, 3482106160484922989, 457652115235515302, 13131251877541004291, 2165919938561266964, 1874523171051007657, 214890286552667090, 14827429772134029279, 8521730223222681440, 16150319117368919333],
[9685667656530826836, 4228281647083193577, 15050272543097082642, 5451137345963811871, 7193595397311986848, 16742736498078750565, 11550685797441588862, 3787324853958912059, 3070997891231209516, 8984669684148388897],
[14752986476655224134, 3385142835185126435, 12213926743259104692, 12657461967948401097, 6367904324090749810, 15110284666942049791, 9591973891266545152, 16210155917557308997, 11696113888881223902, 13821863163293729819],
[4848477814157730098, 2503575850111447743, 6726036994303929792, 2927950764232365317, 17561161994937690782, 12681812859579808987, 8048115846657894220, 1917671208108152769, 3192104843495679818, 17341049390396839735],
[15624023056168666090, 8146434600483966551, 8701665222107143608, 10119089966687257309, 15687676974167344598, 12538554942392783603, 16610063634462694340, 2396258207933709337, 17767863757749531394, 8497490419887259599],
[9904744802680554204, 897860657704830353, 6612153160504639578, 13516710305790892167, 10315807414093978792, 10814436771521575309, 8326374286606631750, 2670759490861490723, 18261708206056895412, 5679269205676273609],
[4386764090407132678, 7538817058739328995, 3669542989146255476, 13390793292867456905, 1627533522376945714, 1619348601751944639, 1054589078626870464, 17426414204125407237, 3384215293532244382, 12149926369210243035],
[9075652399451677632, 17477461129750553349, 6906453161667326110, 15376666312306711259, 9525563347718634828, 11627828412751496641, 9110165310342548810, 1412107907511113015, 5201725249719040024, 8430904830132281021],
[15464708125926866968, 15600448487509378749, 6519789362993140022, 7143608277497422803, 13293625230873831460, 13369681318526341625, 170807292839991394, 11785703205959406255, 1556781967978760560, 15184235421986720629],
[7629119045957438128, 9900380107195785653, 596696669255800334, 4278582031231119883, 74254975594446140, 5123593316016783729, 3039801404676596666, 6832112111880102247, 10247133876988264712, 6075962711227303789],
[6336908066116601936, 12971542866725846485, 9592742266024929966, 16263173775885861163, 15354346113551323356, 7985469633596869521, 16041826580607000154, 81389639309913735, 5615885112384047784, 114447206598713229],
[11040999432439563636, 5512453816238274697, 11424431846249921842, 13522546295443439295, 10718490700119730624, 1706095359879348485, 7040115389417735838, 6152615953375430875, 255387087585043276, 17621709043367986113],
[14957465477493635322, 17494193893035498407, 8061013828328535112, 2807631943382374317, 9259163356288311782, 11692973077768758083, 13605147196533588308, 16417952875340012521, 7587359902178215442, 7018999186429420319],
[4160247362847484440, 10355906930833152189, 13581303426524539702, 14772732744715658707, 4747635331355111972, 13992188610440348665, 6230322287487373922, 5617124141309113519, 199940202428248944, 13795873967549177205],
[9602519741905125674, 16937819611619365015, 6564676558034434296, 10240824735346727709, 5640631937961250582, 1821978171425706291, 15036029386116424452, 4468359514298396761, 13168901307236550722, 4763730587553970703],
[7373837261793968386, 10732681073625925071, 2685231131806765328, 813507357571291541, 791775451290461550, 17739017991622743787, 6507132557138914716, 6270288673555876689, 8374804780035804442, 6012463537474406471],
[2329707387181522384, 13175857125848631637, 5243682071787553838, 11325925552859734187, 6725612051520491100, 2898629712175095569, 15538009402986078170, 2211492530885400071, 5019032041416192040, 14271817530945321741],
[8739309380112934642, 12716536869086838655, 10444072502642941312, 1217983807690437573, 10253906435801986142, 6543269269374082459, 8763721817782450956, 14400995068283464321, 15991223804952802570, 15036542192879832055],
[3358427551366085530, 10370572159745282247, 14593204221461513704, 10806911300528658381, 7807116788095363718, 3735480241003099747, 17940463670989711604, 1960140359750142473, 6122476306792969394, 16622495547104752703],
[8362192087476912076, 5142187750910833217, 4322817412366011338, 3126496273901956535, 12814058088429933208, 17173036637316465469, 4347907257424814006, 4857695582959340627, 3139601897422574244, 13718346111352555129],
[9637178809775025514, 882551220932902359, 5555802023241607992, 14415458129479919197, 16989175027508189014, 10108200254363290227, 14936286823813615940, 16032866789114161049, 17909908100013567106, 18298550036105723727],
[18157426400011258858, 16930568662236902999, 6064361050644555192, 12612542872864172765, 3268486763278994902, 4164657781736028915, 10660225834142720964, 16132563681175233561, 6342249578518018818, 13340107222423611343],
[207789459502672138, 14337472705684377591, 11608180785615818200, 7754479037980736381, 103475483093813494, 7139808333473131155, 13031429093197707748, 13724891892583357113, 6233592829064508450, 5842791510131395951],
[3441518153478150654, 16103823705477775803, 4359191255393433516, 5636291442794086817, 1522484004891406506, 12817675968959290903, 17422670393842146424, 3125892383987248285, 12772389684315063958, 14297916753390487219],
[16496674539259128832, 13019154712597240901, 12877959631151144670, 3135499011370504731, 13435246973759758732, 4694837503945771777, 10349138519195875210, 13114283023552428151, 995069013349513304, 13319529699987763197],
[18053129989247845630, 9734116319561390267, 7571239396192070316, 5906684273385406625, 1732845241982921642, 8885857254564283671, 4381596132520370040, 7182227964552706973, 15958383637688439190, 12770570651638758835],
[19529414742290256, 1347529617218027733, 745823219496155566, 14568313997815630891, 9089485868962744284, 18431970526014152337, 17427369282727001434, 3450115717042243975, 16697055591400214952, 8398703236622631565],
[13962790238404640136, 4201834617023485421, 13225427468977219878, 8664035747660142467, 7522656229844178580, 2554445795380876841, 10236063217894537554, 5312087233760129887, 16045881728967481568, 361194876183131301]
]

reduce = functools.reduce
gcd = math.gcd

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

def modinv(b, n):
    g, x, _ = egcd(b, n)
    if g == 1:
        return x % n

def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

def crack_unknown_multiplier(states, modulus):
    # print('states', states)
    # print('modulus', modulus)
    multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)

for values in value_arr:
    try:
        m, c, a = crack_unknown_modulus(values[:5])
        print(m, c, a)
    except:
        pass
  • solve.py
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
# p.recvline()
# seed = []
# for i in range(10):
#     seed.append(int(p.recvline(), 10))
# print(repr(seed))

from pwn import *

context.log_level = 'error'

m = 18446744073709551616
c = 69
a = 69

class Rand:
    def __init__(self, seed):
        self.m = m
        self.a = a
        self.c = c
        self.seed = seed
        if seed % 2 == 0: # initial state must be odd
            self.seed += 1

    def rand(self):
        self.seed = (self.a * self.seed + self.c) % self.m
        return self.seed

p = remote("tamuctf.com", 443, ssl=True, sni="prng")
p.recvline()

values = []
for i in range(10):
    values.append(int(p.recvline(), 10))

prng = Rand(values[-1])
for i in range(10):
    print(prng.rand())
# print(values[-1])


p.interactive()
# p.close()

Flag

1
gigem{D0nt_r0ll_y0uR_oWn_RnG}