糖醋小鸡块的blog
0%

2024-ASISCTF-Quals-wp-crypto

发表于 分类于 Valine：

不管怎么说还是打了这场，所以还是记录一下吧。

Ataa

题目描述：

1
Cryptography challenges, like the Atta, require creativity and constructive thinking to unravel their complexities and secure sensitive information.

题目：

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
#!/usr/bin/env python3

import sys
from Crypto.Util.number import *
from string import *
from random import *
from math import gcd
from secret import p, flag
	
def die(*args):
	pr(*args)
	quit()
	
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()
	
def sc(): 
	return sys.stdin.buffer.readline()

def check(u, v, w, x, y, z, k, p):
	if len(set([u, v, w, x, y, z])) == 6:
		if all(map(lambda t: t % p != 0, [u, v, w, x, y, z, k])):
			if gcd(u, v, w, x, y, z, k, p) == 1:
				if (pow(u, k, p) + v * w * x * y * z) % p + (pow(v, k, p) + u * w * x * y * z) % p + \
				   (pow(w, k, p) + v * u * x * y * z) % p + (pow(x, k, p) + v * w * u * y * z) % p + \
				   (pow(y, k, p) + v * w * x * u * z) % p + (pow(z, k, p) + v * w * x * y * u) % p == 0:
					return True
	return False

def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, ".:: Welcome to ATAA task! Your mission is pass only one level! ::.", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
	nbit, _b = 128, False
	pr(border, f'p = {p}')
	pr(border, f"Please provide your desired {nbit}-integers:")
	inp = sc().decode()
	try:
		u, v, w, x, y, z, k = [int(_) for _ in inp.split(',')]
		if u.bit_length() == v.bit_length() == w.bit_length() == x.bit_length() == \
		   y.bit_length() == z.bit_length() == nbit and k.bit_length() >= nbit:
			_b = True
	except:
		die(border, f"The input you provided is not valid!")
	if _b:
		if check(u, v, w, x, y, z, k, p):
			die(border, f'Congrats, you got the flag: {flag}')
		else:
			die(border, f'The input integer is not correct! Bye!!')
	else:
		die(border, f"Your input does not meet the requirements!!!")

if __name__ == '__main__':
	main()

连接上靶机后，靶机会提供一个128bit的p，要求给出u, v, w, x, y, z, k，使得他们满足：

  • u, v, w, x, y, z是128bit，k大于等于128bit

  • u, v, w, x, y, z互不相同

  • u, v, w, x, y, z, k均不是p的整数倍

  • u, v, w, x, y, z, k, p没有公因子

    这一条算是送的，谁能和p有公因子

  • 下面等式成立：

    1
    (pow(u, k, p) + v * w * x * y * z) % p + (pow(v, k, p) + u * w * x * y * z) % p + (pow(w, k, p) + v * u * x * y * z) % p + (pow(x, k, p) + v * w * u * y * z) % p + (pow(y, k, p) + v * w * x * u * z) % p + (pow(z, k, p) + v * w * x * y * u) % p == 0

    这条也有点坑，下面说

然后就能拿到flag。

虽然题目似乎没有明说p是素数，但是实际上测下来p确实是素数，所以最自然的会想到指数k去构造一个p-1，就可以让指数部分都变成1，那么整个式子就会变成：

1
f = v * w * x * y * z + u * w * x * y * z + v * u * x * y * z + v * w * u * y * z + v * w * x * u * z + v * w * x * y * u + 6

还剩六个变量，那么似乎随便取其中五个变量（只要满足128bit），然后在模p下解最后一个就可以了。

但是交互过去不太对，然后发现上面需满足条件的最后一个并没有在和的外层模p，也就是说其实我们需要满足的是：

1
2
3
4
5
6
(pow(u, k, p) + v * w * x * y * z) % p == 0
(pow(v, k, p) + u * w * x * y * z) % p == 0
(pow(w, k, p) + v * u * x * y * z) % p == 0
(pow(x, k, p) + v * w * u * y * z) % p == 0
(pow(y, k, p) + v * w * x * u * z) % p == 0
(pow(z, k, p) + v * w * x * y * u) % p == 0

由于是轮换对称的，所以就看第一个式子，如果需要满足这个式子的话就要：

右边五个并不是个常数，所以k取p-1应该是不行了，但是有指数肯定要利用费马，那不如就取k=p-2，此时就有：

也就是：

所以也就是说我们只要满足以下条件就可以满足题目：

  • k=p-2
  • uvwxyz乘积模p下为-1

所以仍然随机取另外五个，然后求解剩下一个就可以了。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from pwn import *
from random import *

sh = remote("65.109.192.143", 13731)
sh.recvuntil(b"p = ")
p = int(sh.recvline().strip().decode())
k = p-2
while(1):
    v,w,x,y,z = [2**127 + randint(0,2**127) for i in range(5)]
    u = p - pow(v*w*x*y*z,-1,p)
    if(u.bit_length() == 128):
        break

msg = list(map(str,[u, v, w, x, y, z, k]))
msg = ",".join(msg)

sh.sendline(msg.encode())
sh.recvuntil(b"you got the flag: ")
print(sh.recvline())


#ASIS{ATAA_1n_p4rGaR_M@g!!}



Avini

题目描述：

1
The Avini challenge in cryptography involves doubling a point on elliptic curves (ECC); your task is to identify the vulnerability and capture the flag.

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#!/usr/bin/env python3

import sys
from random import *
from Crypto.Util.number import *
from Crypto.PublicKey import ECC
from flag import flag

def die(*args):
	pr(*args)
	quit()
	
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()
	
def sc(): 
	return sys.stdin.buffer.readline()

def genon(nbit):
	R = list(range(1, nbit))
	shuffle(R)
	B = ['1'] + ['0'] * (nbit - 1)
	u = randint(nbit // 2 + 5, 2 * nbit // 3)
	for i in range(0, u):
		B[R[i]] = '1'
	return int(''.join(B), 2)

def is_genon(n, nbit):
	return n.bit_length() == nbit and bin(n)[2:].count('1') >= nbit // 2 + 1

def main():
	border = "┃"
	pr("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr("┃ Welcome to AVINI challenge! Here we can double your points on ECC! ┃")
	pr("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")

	nbit = 256
	key = ECC.generate(curve='P-256')
	order = ECC._curves['NIST P-256'][2]
	Q = key.pointQ
	O = ECC.EccPoint(Q.x, Q.y, curve='p256').point_at_infinity()

	pr(border, f"Please provide your desired integer `n' or even the binary ")
	pr(border, f"representation of it, [D]ecimal or [B]inary?")
	
	ans = sc().decode().strip().lower()
	if ans == 'd':
		pr(border, "So send the integer n: ")
		_n = sc().decode()
		try:
			_n = int(_n)
		except:
			die(border, 'Your input is not integer!')
		if is_genon(_n, nbit):
			R, P, c = O, Q.copy(), 0
			for _b in bin(_n)[2:][::-1]:
				if _b == '1':
					R = R + P
					c += 1
				P = P.double()
				c += 1
				if 18 * c >= 19 * nbit:
					break
			if R == Q * _n and _n < order:
				die(border, f'Congrats, you got the flag: {flag}')
			else:
				die(border, f'The calculations failed! Sorry!!')
		else:
			die(border, 'Your integer does not satisfy the requirements!')
	elif ans == 'b':
		pr(border, "Now send the binary representation of n separated by comma: ")
		_B = sc().decode()
		try:
			_B = [int(_) for _ in _B.split(',')]
			_flag = all(abs(_) <= 1 for _ in _B) and len(_B) == nbit
		except:
			die(border, 'Your input is not corr3ct!')
		if _flag:
			R, P, c, i, _n = O, Q.copy(), 0, 0, 0
			for _b in _B[::-1]:
				if _b != 0:
					_n += 2 ** i * _b
					R += P if _b > 0 else -P
					c += 1
				P = P.double()
				c += 1
				i += 1
				if 71 * c >= 72 * nbit:
					break
			if _n.bit_length() == nbit and _n < order and R == Q * _n:
				die(border, f'Congrats, you got the flag: {flag}')
			else:
				die(border, f'The calculations failed! Sorry!!')
		else:
			die(border, f'Your binary representation does not satisfy the requirements!!')
	else:
		die(border, "Your choice is not correct, Goodbye!!")	

if __name__ == '__main__':
	main()

连接上靶机后，靶机会随机生成一个私钥d，然后在NIST P-256上取dG得到点Q，并取无穷远点作为O，之后我们有一次交互机会，可以选择：

  • 输入d，可以输入一个nbit的整数n，靶机会用这个整数n的二进制表示去做快速幂得到Q的n倍点。但是记n的二进制表示中1的个数为t，则：
    • 若$t < \frac{nbit}{2} + 1$，则不成功
    • 若$18(t + nbit) > 19nbit$，则无法计算完
  • 输入b，可以输入一个长度为nbit的1、0、-1组成的序列，靶机会把这个序列当作二进制表示去做快速幂得到Q的n倍点。但是记序列中非0的个数为t，则：
    • 若$71(t + nbit) > 72nbit$，则无法计算完
  • 不管选择哪种，其实按题目的内容的话，都是只要能计算完快速幂就符合要求、拿到flag了。

上面这两种显然选d的话是没有符合要求的n的，所以只能选b。而选b又没看出什么障碍，只需要序列中非0项小于等于三个就行了，所以发：

1
[1,0,0,...,0,0]

就可以通过。

确实是很莫名其妙。。。不知道想考什么

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from pwn import *

sh = remote("65.109.192.143", 33731)

sh.sendline(b"b")
sh.recvuntil(b" separated by comma: ")

t = ["1"] + ["0" for i in range(255)]
msg = ",".join(t)

sh.sendline(msg.encode())
sh.recvuntil(b"you got the flag: ")
print(sh.recvline())


#ASIS{B1n4rY_r3pRE5enTat!0N_iZ_mAtT3R_YES!!!}



Heidi

题目描述：

1
The Heidi challenge employs matrices over finite fields for message encryption, and we are unable to decrypt it.

题目：

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
#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def genkey(nbit):
	k = nbit >> 6
	p, l = getPrime(nbit), k << 1
	while True:
		M = matrix(GF(p), [[randint(0, p) for _ in range(l)] for _ in range(l)])
		if M.is_invertible():
			return p, M

def encrypt(m, key):
	p, M = key
	k = M.nrows() // 2
	u, v = [vector(randint(0, p) for _ in range(k)) for _ in '01']
	u[k - 1], U = m - sum(u[:-1]) % p, []
	for i in range(k):
		U += [(v[i] * u[i]) % p, v[i]]
	return M.inverse() * vector(U)

nbit = 512
key = genkey(nbit)
               
l = len(flag)
m1, m2 = bytes_to_long(flag[:l//2]), bytes_to_long(flag[l//2:])

c1 = encrypt(m1, key)
c2 = encrypt(m2, key)

print(f'p  = {key[0]}')
print(f'M  = {key[1]}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

output.txt：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
p  = 11662551575461840475555573447888369258720609981894210736264777774264853865648625517657867646615246309976844738740514906726900361114740532559856817475566473
M  = [10545230560563786984855496923683490476026486940118450770549073464506619127566086156979481737376593715745045825762636289092415982636744903849331044561991027  2770939188750070033130610621916886035117116785794649229334263124116641591679503085440969465109194774271112846705097407127243843388526403756695968426109009  2619573780018799165717871194932363681382195058755685389697413459696317181345652738031305734626276043937246461942417061168292200013052156392419647704791164   587417232443753346797644198418305416759457462109079143577396016060144667553797778650678545813120439536811176815061974102688218065080205615873250043107116 10008573718827580115910926267965509421082375658923055816094066727441441269064041396205970151224009498359555212699173361494709128355177042420479730419394448 11349679238711423769258106365043934702000409190944163962702681143883019805758084841424170235320080645291800442753915444626688538612431448021461815602505084  1259983683982517528624104640769414117508824651587493945567196749864448927207325443584488939350695796817884095062345172996459022692248477865911484976890677  1971222894902770228840252206358781719599149745812922000368000898504324616168136646332199731351703510417591436024000432753085479074932699265728642973361588  6669839659863156841636921153847171255855329714769739014914538022174619476759150740113746210470811794024450238412094230956104104604470512858620052633879456  3802581949594457592828363879108542960813008873564295428591688777471510363950965569917650721412016262056902496806630695062218366384844071135340776983011281  9173775727119267206301111299477830915900809890513063857586668239440017154407086958798891345751914739719483187083090695958175401343040767721933865576481217    63292815796033440929737603098751368679976667448780318616378030386447237785088204452210939061618406699554649740350145149138551040089078412650647821839141  8038110607224698830642667955922921786160643054537840638891553876593127658518422032492194777989543683234482686451247682664202847091088436250018914370900018  4620005466063990313733956207010660049630085668153164585959348477382500378456404909920166091487161042789245349592631307648239193958926571830969290111319341  7723658333415639830236075056074413401601023668675501055777319586393273424696409262534891945899607774752133819166960047216693074083029041571138165980556645  5664967064930741692594553029048945396725847760028601948577302634958037404439063837969135388070885354670837314122255590172068114698277784125117927007981444]
[10848366204360161190201838601526644734443113820650552986437505153450992200056823340141151742674767817453544156749578089227409053031617962097481521776333662   466254183492325668919451039055771698384604100182759674795120489047042278059234019059188153771401000340845808733174674039516485589960062906265173837289198 10921271090992004425571514720574041745042089099081078076313350426422014335331996431858633260478331235478857142353555763351914296132631784505192949275079145  7288970492151118783174993220841212730169158970234190580587866740148262474437762345342037679241572371879889945890007329381594422205510662492166668230830371  6397385359643440993129806932869750977092933376572936915587094071677729740486038265010370491070658662538721096098743036356996731964988645692077979419008237  2198594717244053005618379513209796592560948297208995089977741412663997213790188917071972785669240610376695576054681310132025792375692515529669708692557776  9520960910870533443469065059911888759098912524292444208141409544622578579652558232062352363957469988249666511411470457384323777085080349150779715044658869  5351828241184499297116755792921327536999933840192490755205576505604100703750341519511212041115300658003910089291549401398326757430081810294329244505940603  3855931705495057619005445737270622363218757697416337611616587269958811152610940710323990742304040689224722012302853852655935222023866303951215982601062105  3070247580379626252711429295928647357139650798883614629738592755102417062815400596483164617339683156061985035040877071341594280991144503950412416362358308  2683417472616465058329974017360746635441516338768719715437384136210837582777147723356325046733457463592487011165951107735716602545826581670143279580753593  1536629096290006627205200629837814172066314634058009077363019025097136735307946865323796047716398211865675713803243477480940579080522591906205466704816821  5637939891132291367504319761622262297162823730038779206386079671354764898484793785101427217660687218413094891619267298865986676976979649192122591011909059 10478772278065088629560760704415663594182193734519737152164133480281058188050258377463704018998238535923058404279515474367650114715916554992541075921549486  7958069612114493895717266295304173860680299751819750966899519332875705791380787758901489436892385222047714306620152588399142040202385467233510334630881914  3272738683607729769409182530657878528660283322890285221536574204115431500290325313334077212566960758636101204287262866480357961886238245198230355741070974]
[  582226298901293853784046922922712143034091186467295125509572059014391374884097946851733617042838793758226602342938908170935669072801977956256441073078611  4765907867467274822446742488572171986244654477423574919405713232657261805958122316957830710710009328386281695299565011072866700039824005518389873960941799  3143259623553180070982026857530260136622534686256534265916447885175003618658210525719825601888384250931307665123092779127552761951592253318665603589128606  4371129160084463383514075567350433656211778917917583221311028136884724968633499747977399004382490520148363863130388925149053819292465197900179286475823967   304759497253189635079227037649211281230323572612289639495215955214697481662290615364852757765929832973577923767210646106937099890668063948535738713418155  4975899645789028840399633935624338794296976491019676401658579790000712803983878522348023375942763685552000404141316655963469909834344056156102309640197309 10249228396790540381137408655980472730135869428595540912710818720470342009547171372291184063772414659431658316950240652781186533432205930326612764511737186  4682071696480216227790281256980077056957804829489600661787329342778950746972413739717357942836038283492513591458589646384094950769350009895667726474111369   467992918211696902434792525414892089169451202631727898722177877303207853852897939791256721384191676130870645554444857364488907277851774620717727951202745  7509574849549393172668449881664482943671714872071167457564489413354846333380264310504462388400636855316645201135438167508114609097346833033701548287091429  3154104640113282680173487954114382027303924687606275127463038233678354276584696557013535335760248154447205471394225495365887552866411183281041160725581051  8647200848447854933122748352447500981274999620370242550636428723103786331587498863454746691069690668310558254232665435942736154483501145390286947736501664  1868670041760171524789751730651337641863071579623266492977864408263488646344785489313786705879558501969024623720904841715255889391594972670795160142657221   953035946263548256145304091312762009584175489666343990231188919662261629856254770391615925646077371876074455547493291592166020410227048982050220786949532 10573128788230977642012758457578789804291346998738138786716846377122877684194057449075250102216807687911307238975023191027501222036821876725096762292282811  2155325357518630773467734078394913648860434826318018110876265505117445707978827048010369336191242126362342300206772896643892347150708199677967212868096918]
[11127639549383741776054498354419816260512835013668362718670377152120908136734734940373306636815007641832891961513984956005235291181404030755805565704727931  8324282279724260180927293655079098433920297636437222606919983467485581141593105800321397101041601442883299452975113537722604166447130888335484590512582757  3013808685268394146939967050907435395245828606821587178811550068669048573296855283324002011715343306121263363913106433368863178504476306254896246010702929  2744122675476963848176986537452209560371598158060427604578452103702099245350489525461179672877103373917123833756558166966941884539135876644261762720417501  1539702548810185639811350934929332071178828866994736933864881215046035003953149217144670117897724906397932562071592770556757838287984613960491707287295614  6813277606762948078724183097430758496695474893959931124487623394106991509222410688201184506655506229459977792055473944284058387257533192493446512720686728  7485797065393515416532714116593122619387345380299297181904214013793606094543492991563952859346809110217601503689648576294588452729304229384942687565714523   995398470396663151395333299316183567559311362612501353715835204745719570870956155533953079743287266947283226137876179779512195006090849528641871205702964  2452344843090275670485099696728479335462089213487192801940460447337510987595877903512691489546958472040212688824089356462939627479740051887520718163783553 10456906547270685444445605656523148021779312414223840511275349724795942313477745207978603163634096312582428755944002640721876968273402807741304526858745591 10325155193593525627901770931812351026898199522993990249136460333619451308276298819391233395834417640329426914676504457474508382548598169723637922320858989  2532436360617398385348247449174455616213691528674256426769755726061390969668562927288609698503415427462111086396180875031877068370146411883742692746140928  4978006140463095170025747410618342536948947000802567312599988534270530037319099305791723202332260811382069029630365108620214973367999151983539119628766125  6100944666797890725053854396078638303221360791176295818795054019884203452819936210766409414504687247815168158192425377716294507053892707971146100376830321  1019493096767062379630622444618220830977070206938650925347414944770573104031029086363472255574963960226456901260114850045809261450137475706432844131271750  8009505036998407620697817270797085219922940044674641679844418033113114772011345985625391795611777824264868082028272876630392967459043036201605005284030433]
[  167574730855835707849745296520302353076665725524857213545317686775265910456556682126439887291764983893037312948026733197805968235106123253113876218363586 11176418756695933306695694817737432728319314399813785124566265741885943311100368399915863071867299405010829122313929438649358012072217274248198143010327305  1418427879893213616548166272895117059612264261646643436377734760239811369132649199004997299968733699135789505417215590484106777385250260139012383551493741  8286700278702448014138508362804429492791931433232842973229374217574768224600041715228659307925047710500080338585218046515737731274053977330792696333413232  6329536571596686338501324902409706264450872398507489058735683440839641062770525442426080245329455368872627139535664520286679324524935779200744149964458395  3971712711905784542952728985960452711185787177443172195525481038030676470886944139895404570974797677313957330289696837016316935715670031991498534443330780 11084065307848051954817914510686335067177573105948552816103797886660975481552070854814728269309326612934554400175818286914245809973275821904672703992853317   533533081373246896481407124493821853427292733682179078944290762993506141575016491330148852545533444283995137103867849780092619782191639568825176213748021  2560587851166426277108975031220111420680617246450294899877556607386534923678382116227678849981182590606935745408515251906985534785346561338705092852298803  8450949764464643296265174771486269337623295830735849834606962962545097916967864887457153113259284296221254408085988442238341186742176791051568310541659875  4329923280677602767091745585577369721910105038285577996262125017089498504182250722469279444131259704182158962353013931641952416175425565736567193474109001  1517870280530826898472645649539617441585057859967174616812993006735610887866309597810189400218413943106870960299769704529223159744214533623014750428157569  5553955673142945094594180123726546883512253378884558445064996406469575819597287088972244454967142929392250497268264459534693036201525226899134428610429023  4775379850783213227183301065450973566845115994780307401231224540555572980984464222254349147598171830235032534146130784084191154007466830115207840268462998  2215813608678496723393696889324157230122242379495098407641329300149501783549232765905075530692975101374102308033809445985637345839673268950307740544845811  2532252446516128875289151781128204608693759321959222867356641665442943219257227905618585192346377773754255186251846832380455372573828395946029262995917597]
[ 1569777804566516584463139489969730189552678665175266247769552727762867284638542284297321148646788609716003689617490574100603613477434301059743596796778557  6664605222886709237768068784966122789813072907720297546241145334954363845123077284286016272791971982366876376047162456091792910319044484791420744051490543 10832425815716610433246481370262097472186217875110896997789470369392072224884973299478552675057450389739191213009560383805152629596107811281563792059592731  8709265964788185735536477075126990225945553442292745894522654645860962526483048917629022284607009667862815282298964887048049218655106889234890123968050951  2327059244920705974392419822450840425785821124466504048511551069172171135223780828009979443429924253082366339113621136995268720091200973105645136616140656 10948726698239127817635296772694385018899917203465506508904176597682516142581415011273068873804479724505934327550110710325068025698342018638110569984785656   914084726397882086006604478549637519223581740934291617971615521242861794202431358323684729365778581105859551842117737083405041772918267292720727568898241  4810161133151954601647221375802135807103513360545635501233268617461442185345098824750638147810716753493720381342614624351019879510596686063812068873325633  1398892356062405528957250427298100633095954503411359040187916350128327450606222428153530768924934431521316524462410140556553292193770120154260332885565196 10605649584392103589073422735721462819889862892947844237430851205515184470090747831425134354384001302169376485153477083692413318047792512471654229455307965 11381558376032216773430762190331802072967918647300389098304346000601312631281080361915800574822233349256756196523198162329509646178829978843728439480834989   229268940271927035065750842724564535046848809360140056760172532128371526727708744940316072905982103312794889214513462710345447329745675960086840417984175  7548334601373851889936971791868818709604774750955230713291699970772722171357561811910008608321972442656333403501651432512283497423717094645881264611960334  1663891959791989933942000823890586512067020427127602951585079267612128897300487046642207624016994533161183235793201156771458243977696717263890583484151538  6238565998641122375992107927984549724267254523530728319495509947654157820413152952180751106136380940081074646621356621803088237291827989437276423338278258  5147629550348491132131443097519485703202210038633003156299096343285362976217817640303553773775151348542792281085302076649772315233585217050126298270552201]
[ 2997850394180081522537889632608287922660804513688293377640760136576623544279323944572461946329526768746944937080029617665094214398497527603893826581181460  6201397226416401143405976231755087097812867827013187150742686100738208571121524218661339727383237720850596926947706370966076456017831947626529496996347243  1797385373736611288058954615242661128844059374951879885326507499484773767575981204560193682472808816914235955784828613891127140731851736132975706218347296  5737899328421802923453335116259806148148574191682536233778713398071565709133845075800805360828239999483981610406489013226074690660125717853762857195379925   943050275382699815241724315751806290661293581664568634666240575612597811004202563736284191054413399280483538265113126848965059819852268208503649926153831  5799363847095819367998521018340097914922146833502274542728716189653075304957830817803874635032212421958140270755872009340433806696940751242212153287240454  4470376378033488827133615017119126437806901071854055115351686456264310156485764152544853172169275863723963964486459185758006884601569516027845808434343751  9530309373273054737702943475726061006289833783159829635635435613617131271639622591730658159080616835067212336368516787856145343877203537140714633901730615  6512944720543072249812709076168588365371588104950409932543359265108825697450190064981330642102809282761950777412952083128863983111624759423745310946390499  2565353866861964643921743759091279576953629167430116965574138823609896094136741125101182425985387646010532483510245881869079735106687418714405811367316683 11500254084847996623273787924047101448713229462463270853888791924877537433224878348209119708935511314672442270462445607245623508926651699735789278304966452 11342411348667644561239442769607492249069601474173192963475521629473309285776219717816410483546922302539497395529723443297235272336676445224259664247505535  7678819616223149173761517639473769904792044987224858161362557311247363926955023484426341076949597378616802368321512295686222802107266394833607313897455462  3045685894702466453260450775643385530027311381493254841176819650955629280693843201101617292571515556683452889410128970670682088896658787791249268042058836  2609142292129438049128903837629827254201110625629296584228841013086272995740530070498891479376026698701832935934993354471914026951015233388323962092494969  8051728263203562740457142458202227591911986051642644947162282478945627157805772260545384821462168423394674235830607575118875403946473995187735224133146722]
[ 1703204925740924784587443478009517085231345257843049275741725641255983471902016460474416455634888753330526361796858840124012745330734540584842103150994779 10875822326542710261960848644003004782053711962801242053816940724706963706686016897894920499609450918713272061677454513416412239537537648348067566949859212  7782356817537113159647628753863865797419467611980355509909017533428891204846834243937919759453599174192285993763704548142463271962746160835768606842803333  4273053553305568233828065733589717557322189409469708588742591279966248879958697808735433550535760407186415096646335746373351010784163027627864166170169766  8833589445171251866752559976538620667942689848291552104938006627249611722677579971938918838042697781045672181488508431807654692686259539781648305121600292  5178822824328714980133956234552339881065404607400332482317777022735503644257266963621887838657216462397533691525174814976504981203422650401940594493907921  3666380440055662843676622424606634214466067526312948251267162251835521389318598724686180376279832025646322291497838376148917236084007553924148677121892289   373144740953751270648681474520225008047677125815527635999904473348408774370958697777449296114578791467073793070673311707003316613191018660000349977950282  8901963648583497189632627212796500321304871817592588916380588482465195341314913818181947829896454483159173888068291199617175737614342514409031501375980122  6132055707707518404756496097617548569390088373147941929468670475212178210547556253777479876257890731803759132096234729174446761229167585431837092040168959  2347806225561720070699326440053789444877180743058364488818799333585619215642579709895376043595355682476463396342584285790142902659296280612120478570006005  3978754018730303492109763303325028802176117065980969141201886375065627115542502827448799169775307455172831114517042325792624804538127323833399871220021205  2027313223728585563921035137509042436968140719051899171569946962512047694327356172065170494392026060053520662085564142862144794203167719622251973363513990  4586428701496420088411823995931050828679283453990377872063430183300740587177559703557571031269743915499380717771627572421354719731587500003326790564625097  5585547096995837309114048989432505360096937162634557224811345146847035094346327107961722290061903472194671318911954209399021736564350371098929997960160278  3232531350127885526647309778098711259999972431380519624795077015755655306305827308842525327879656038628344041010529851441621829439928705469137596691421063]
[ 9522484805207581147802385521130236167679184670981059197174105314440911718056913668206322140323763494312106036139899163131101904369321425687653280289403021  4683538888864025365788062425440564975261063112941510039767861432500658161361664386396035429151500272908161740612281652247249584780775657022694261351746302  7769087049200987635193800474183806704670000145994190043108324344352470130886346871885613694248649389797580969807333431842427091407198742733119833922793458  1588511535342055765103698908572707902395933948556460262131140101182259556787538415465669287585494644206209911006633114427536309542612024868700982954516052  7486665245715546623170038942506239393396124985006603440438562595416141107980637362828455253666921953722189338321765514036696812051724079045755036432197437  6800536709440474509704270415053440522828704831077738520915449989016092892234464646289761476938996263711569886501528306424044628681984252482309447251395195  6094058913407188850091996293944884374690191713369623297215579845945525085882386872165285116601751740638480734734636417474364616472071522058020693273095569  9617062045845871381673865310728294430930777262555655920316927675687332611445604253136716092748793771666772632603399032450788949451093671621336121615371473  7937290695574516558509341666411119380459929459770426825972068273754801022264849264166062953212675923987398047191200761489310798176423497186650797161039888  8633649583363885138323440452778145020084349724388437438480618872577561446295895344924631277086036290616287111699824111695984473673061974872290159272912146  8888206889061586358275259584044040635208116203311011286596657101515874139040535469104365633804799604902368088761703295586278827354148836041531955514128586   921473805737320344175323191030081320142697317031123504940434537210678193668511077095655113553577471948999428399201772374978332180105433705202705733981524  9897294637536259443877151632405765783593335869979320352038045991239956288242794806048210642500252413929438660791527518352996545328296776632091371099795990  4803884534865939911240420155159645125821505917514567666454729434075524346358636075055432571874467323742537475815036502969443275874173155474857810862499678  3284538323834307744493793702647530943550411407923319793062602535664404624897513493610854742447673404952255366819566912038475604246833397519898758034919664  4235761336259035345133020629783592773894673862467134428375765227870635383772843518348214013935096166564432588833786940742542389630309722215278547429665934]
[ 2411333563282420786893855664478224029221254078683836450068782440655517388210560506417465322753272797978974465561530757608788498995046492946806986363125771  3070906070360832095808849642874218631409366402115640276547988432173258539967244274456482486716085736255127617746599019950709607258302047232893915541927409  8694883543679230741623379414026149328005334232935444674535826555784431620289819303690600226476895303283255834427868706743857897270765258616136482579407151 10555709010867728190887917845600096795106634239450879472496998297684707447556752706878636130459858354774631938596925204404256558105213530215273811582551829  9409894184909308562322912966147503018893501612935289677931932631869084299203236584318931422615588191836763665762017680136813689443194344457924484672619470  1499182486740577680393380605249559933485025715269079845886856178480859177262942528742995531422016516576102187385039857353292995903745890321779634094995179 10751832852934836906628054237784422064993985767250347246348459697631816539271217118278051742665567352699893605858840098893490720795538391381201542474768988  6018537117891320808048016906604497326189753593943474423738460206057469351533589722644252246703905627987852546640010690456310583927068705203501126968179071  4130082105776591706303269371365144099844524435518526033544852989751273550939603502978522161516441086567796134143206974590995621368341783384941653131766468  9130096087099362092611337965696888023996823069353441989784863213409293007023740006257004812130963238024827621927577185782162074038199510357984312956075487  9063407851310386850660568396843024404758091353134029054687836928714864629232680057855530883954759892319193682102184512130984773666250909838803243414078744  8626015035844544370150336616089468767101218983016498247579612355557991180446564833417313810603525319866950416344723747183098585766080954811674972456752874  8391289060874751673653262929399741104666280364248928009579192418830612963385377087618906581701450339006020787262506499283954422235427673282504733686724436  9259298150488309506306137158940724684749389296745820930640103922061126282766880195347952234444796249637081736578281668559812195443185563880405216233246752 11656517372345244893441337306389880981837490036689874469745576739700054124964132350254792441044730012548092332748535295170167017079016039707047594295678807  1037921753331909957334249667589721937353366148893069789934217022980032820386768382694745894507748414199388028378516650728757243512201897781100100477953350]
[ 1870441265814450197569761244581993635194893244329061536550641823817036286779809792709412565009363133217940225463451974344821852240987994787165508599885367  1780378938789693753903501307382406980073491239939239049417635821031599560241228890087384423232031397888157080753634892366468687004182849733695905338416893  9043997999458244570826057697144520919277791075436586209599833089618051380988926577067195940436749688993478476234853310800724262613981842922113750319123868  8073244239729151608620997635732006072712787906221151258667546610103073972751117746637572568537779469443941278875218038632352175392211894551862952047179694  7339467016122976239727026605963879762518264993728257555607929145393673882627591771372949791988174303305929018781541060889166254388651151435389554176426142  2465783395178081441360804333061413713866813585759988321263090221983898323300869798347463996207472228210320289531804555480226513481563688270678190527472955  6631814738431278439205875884564840157113627841893927054308554354609483872377926468134156122793372337272760064067326265656761087690384370614927075385938205  1294708456352760826427025156414384706258564521364087263617648335591332605528505097643431562435872627808157543152103706263622602852615603842364729817356412  5919124655593726948181324899659731077006438415228547146536138724811766568305369573789194846287463907372515588382737472428302879399652339536640807294672302  4033516428741350950270187793171903513454201729086283456867646256146595210031097556991133802505356810009767130497445059022408461955008925085881488770562447  3287628474670831538118344790677812833002551700091615270560766075292122909817275540511414867600447411424895287707479032209926344202582873378564107848518647  1659114360136013396261107919036705766089228746238821997511969056243137368708365657326846603833333583724876162545142898561994668866171997844858584249684231 11523091044895161002439322233363120111992483327781178702891378343195848749088813001388098236917297351110003961844332021273450423444936914123758259948388597  9644959932693987802572070598854222543647821014575844181271949000442783075108945330222729180810118440166157281262184694549841956985843297382497650380358949  9825199257119029411253573677042454272629405863171831703025146521832993361858805819124659178364976734106970589818026460828840899987593769609448927862198728  5966162168774672225865000624710994323850468370956358193204405739976937535849790038443580669597398251504250967294431365605986196246662264088144187465407413]
[11389844625400983111632802117273518527792639607832000487618370196299844739227200590193154747001248363576893580506363192110368419618054050589409215966448050  5907175581194877263147954380363329184256744154721236428476307335184079300630855424168344522057127975861501377177883063337442275864871465228413836933710967  9584573906923183296170838006745027566831313473801821357495402474835794881758716604397549078605684595949026586287607864173531234696019750246884681757617474  4570384233064673596578194878867715071000853928957767381587887062705772320329533068506668520675378265392451410992776799743300161519069437980502715891141811 10598121732585238856183256227184675849265162104509613820467207261847845293956656965560010870015582422718321201644945327226369580444802449169792827612441981  9413150163703163097370398217271456299052536491986879973547741619913870269529861209318930745741032360981844936425248805157277241984671670660809812335939166 11262028974483920130632787607892841340618171389842623579679124671663094124852999175355056379923320734015532701126140255780430364094606601708620039259085787  7623195189059907926026281270680326819993135087088999036275254711732485169635699253449231899076422641902666152078272216370246368112345525088477966372898954   629090681978038578144567434197511109316116380612480680483747016729583529188967036225779513694233704878308116697082327486479016484669444128245364883493436 11584578577436368187314284041550145040102692906614906734889001757902248703974918365017642377546630873065038888939646638143258908812786933859982200321086513  6394511763921016690271883230270961300732030576133530513541038127366740679594113116228983531073837729653115947822106586185869450260002504462520406156945233 11450657744623684926938229262598769264548273005776213934879945710026693048080614998749315291038406653507065049869780257998225308270849335915814759133290130  6349016415383796459790615831302652587257801922778877178445489055270136207315023533389791710694998990079297909455024798089571266097111985186986284696099618 11256328667277069571395425054076978226830451147562476089698801828354209656537558300034588550868704317328309674637961427360637844026895093485739195206826383 10675531209844398408770736626479000683279046948026530059352956168320112070029736724305480461121440828983592554099957306293011983874908502121588587059473992  8666438623320283730063157502753030251505948561850523555032604922230417579084809915585294227716898907238402276411862848306784973845424045141751296026960872]
[ 8397646488965352797880344518612026046772901102928359219419241210608166911187498192731111773891406660947985269256478103799126241048003999683657055824372224 10021760358718161037465341621518494139551329672260735793381865990611885121611887939409513030011818228371009023839714766694113784152434692881383891782719925  8979421276216568709080021384800936118300649562371355424529521854145777822435072836937283147096002181306822987474555971122283761644609268103755298074436843  5969131421922569216826832018200833342084584098352194403646766085188152224600694785230165030297719540831270321172201097510083317299280216641501067009695143 11162750234555322065939938071893430229077867741205104449160649817458219081497809664052344647891144801062740122494542131630076870638930287438707836132614653  9164147641923636697688623106663005485051159750009093264149802041247122154568016861749014596576798595452138143821407199523888526984027535660469552798272924  8617734345111611940044759692065733604166295739393963038087862828352852880564904357289902403234905722392311920387264086703521303176920160632818715367013017  1436571864516090489307370938576765136254485413331710961201046566771938722566508725214492290062525754895801979967774127815691131849758893727912765321602680  1250413226308587843099449692723109990534939031485769809075721561044903754243720697293855292715576325841169394870972873390863461614178562069273135886938648   751236649873176407479291606348103204811747712780196402662023876932128686918398640089825402320324868306854927813800343866105536520410529461119120368650860   453069723222368416881486483911950668138419383121240762354437173547576724613722672983739835564205902295097476150278509062624429607367275626845939772526812  3368084674576560647589203668405924662833057310652059063028436821980773040037895814100878270259671641397928396962893212059678292317434956042604386280157266  6281508974832275870894093563025419893700527972622188924247640162387603121261145239817111815455891711932418174341940771733939402196709085746511661631692447  9683054057946161094749928432683140108475688180124954349286662274813874512632270877456346886261395421259897860015268404568176598554964246409077790063019963  8127645881702485418357641619445522648725237664482414269277005229668763158549519346268574723766608966699504330063008164706481208866638416775922432959368839  9596313955398550252713349388198413314796603687553500013381328884853120125976215186308785303963336227648163637123983281157390312455842733600207439762249946]
[ 6897579440485093275440941814484632591048635019693091627380561412961490044638518843085217496740214201158150985451832099028958743646130565166819393292834571 11504869974283068414532888675565397162645504054049483321285207192530405172011513354131031857265966312249530939291997822002432126197092567844134300124901848   132627997868381269431524225292682662444179350675646014675341439163585579292768549702101933930954672524528344948088780925695184105352217389006348313110337  2061678209985825522732804114498146316866509540209590336232312019128427472761224763715178065931094937607631760270658950258618082798120754240250576404733796    29444996071058460615393804879974167064648117202658310000138246009475025457016655483775718792808620590657503672266856770843806159522708875085375788755525   196444444980258267816497009861957025298098060503376571056725949649075967620552943295048011668470162192160805378947012122041790679013434453241450230877069   415532069123491794981616735755887405459039412611589653489138512909484122764325531826964252126060894724484958733042866793963128214232365200115145228393178 11202220304080308198734799534296956842016864278153646296088788903099924846924765438623875017667675464907336633556100306925424105959497363815292913227040083  3152864554692428645036948099053687725954776916682463021671620178051226047317568195403312010455614780352781174061225890922948584634897984596007796119845871  2703204098736599158365472031931765976385409948168610388016031008022229224802439226051581432550337828714991968502837905394441715808457289809604962046153587   918445635293318673188002192395618663583072712209914118839933822741333508296787730526278449674938486887221768516751104259902111905025729753929988227369328  1447875706869450361598651263332249308488105196829458752972588240713715475437029333944497299442427310314505451227045797968368154550383975173027411300854084  8171387616234798131124673250079198983336444454540484375108694736873832822770326081704347017679968488005494969717313982085654231697952479519241665047254754   897616872912287780414847615233198397225285855684926074710933094055296678639080187389081444179352730892730890384203388761997465477409117384019939171819975  7535958468428611647884576105165744283754487501563136382347710955725638122777473989486775226574840720803179069501727566999307477849922603958190816638064505 11648362011405806648312519230479974885052898927958630342136862368068940578544878526380473294387329214351838156778506232539790384514834721848226592656499623]
[ 5131405885334035932262234571113811405609428191014843252430658143285836801391272917121643149447787967422040614973013038055969380390135296694590143788259245  4299800458172831580070935059111373225515177641739666376446078374778336826046469286038229762490776893330845992428220222702911045327221717133617311845959931  1073186135675429745206953817046509082099469126865477761364404163139813944324945480653080695499969429276109927808148823024432349821779776222012777630059327  9067476814819929608650021909190280536752720057067461003893233898333116139312379911007723089543887994878129197829157922180418679109160305835756826928481198  8358167354992118639376210506424128839288841602056272696543529708242073457817879770380926455017104031663145712490504038671871944065157375882096092472975051  5224664056690383762723154009842313545840413519029959060930243565098549444980967852204844091435971195148596144039188505068349067662796941245920141273388221  2249143626860619165534840995160580212915599619200678736936791314958831627255389530004515331294447253203673068602733617708683979302279247200887437728313912  8076342246235155189882781398225698730681697221324598022222235756013438590841416172853923048691241086099108713917651711583612488577154665483518093617797944  4958791470803887068193755412283607295421374360138234854606842211840023282054791830866737451931430101612963338855541882274558441086530372885521129736173706  5158610233843471913484001871217853464000889094226012035331250520228041913818785426368476262918699399020992250997162751231492601359700737249187126330681138  1581896428910552081519226674670265455586743884714258618746140934380251097029147337470191713861512704215639806576597824847599739367190628380204239395339603  7724667247511915255454922654331661148309115333919546884341143918322655125539111921648098280825833953929059738575552788245828338300854427822770125450397442  3960489595716495425647663888395730950482903059070577297925636506806601701744807804337278396821360617485792915889739087457473192436719998319111965361288415  6134015209677961098815086314163834841914626133621002593041480845458997870077583829849270716448091073991696433958478909901308666940996441764456681192941310  9495899915191730948016946372195441287345094967787803624633530078429412158625603588848491077965700765128240200136826032588677496386023298686605141873747533  4915609158211969907149021527557793454323638177305197730481659267111500774127276667966464640383884309214971505833204014557838987277951232262696742422290800]
[ 6313485820374975246860818228644031125980939305495377386516366585742277167082977191509447761162391460341345647191508937921263241776733279945049222303373775  9445115289233320099392728232739317521778995735623243688682825536292118385291516891419682433210583251749477427330778686981311891881332210340598217025065556  8191886594932320197690206168134110911871921688208216468109519824029103083672667796351171085979077152433376182700596969448040058634093253356041958812879303  9578033582428330866813378005386565603384349791756040521216395116353160406454901744284215823301694199028404288588957389283491004307066719703796947340809917  9482969889043070320403029947789530810539312697547301170109161327261127083973440546623016094249204362933347893171796941149146619375571407445303773331703825  8224539987360979051101159687426683697015188123742820718828857927563555238876237081442960097271377015949080907160002720785299757232074089769839600588194176  2705691002874101971933645182212004165430174861368524142860472839252300504548346169147908980526093986823196980830073444468721880718974370439753178372196315  2609763494203936257328069396755221481156356892280394905624943949760709204289092307426690709372561006022971022530803793416445778855095848319858772634002839 10058117298049709223368321763572892376150662995062088818328235184342451794867069434538805489226053549346245767640663292339114561737612613272679674426322210  3750204344710700393263525322284597963116737777486731083842387863016798596533770326500254636417998674081416055130189130382026284995387315387203159974614703 10426453382866347989819589705743288597665458677205697338952897650994934168038402737633757945475829500250799666240291760299133671945183212193601169135936326 11005118424096139891056602174690293895599463958926434241810568312780035367787522922283140700466316394733324995598465970361059225475702555598455217205310551 10673938806271485606255021403473960428706528980451983024674696469094904911023607435695197821415844283375000312149112388533215845657915684251370485967917650  4398840328539709147708139362315643355433822270279575543855001988703316665955128032565661551958496363551067840991254943070538208054602950169872544372514109    42747420965516818941154714037247003833719572583043096473043557949973442371088389260754633589580537962141694599969376716547931143734765210813833586730186  9318840545999061093142299397801391135591542884015241740827434875020014184390667433629300670281188594099508302974529368093003590258401800751626574496975832]
c1 = (3166144113409433580813839031075964666543896435346867530089667515883537394676829565440634835190211114307010012912223822601686448889916897002334562419856150, 10930272896342945537739204783295333208495837516324321926979170851729300196271710716278290222755507156341783478160552618068107920037848213689859563140304929, 6379294382906040063502382979515406746321050805763801492231038885805768658505261665790627474174574396155133349719104456231931872055400176757859142277938586, 4397226929465131626989235057995008131894700605320928902757769427654147508029881204496097908648600342139081339733579419437437611261347032873453734502302070, 10006687917554749824127523870087186903098832943183979078977253862182953618886168436175942455681168931455049247294000700777615047812177633384216463375212881, 9321528903175051614070436150773481383594117436801678673883753968725160991698004859010169292566405150898656782077869726788230991863332634655159947917337853, 11524595593714027829792271088013642169783062061016324650759542861867198708018353842116190557787841379428414029322101828745071816007779642308357182498707100, 3188272381186549813302488278983329764885991625209917261939355083764048843300425577092390182426328880903269642151422699815423035997121538747368410215890918, 7610544694889030820080872733267332558240673674364968816746504598286389841757328582833296560075950873372082666405744504513879614579909913688553634045250845, 1465223179962290139936817702021062368956104853286036934686668101654064560330192726518145736189706334373930794409762488984124447091696433442215169732414895, 7025242267860931929401203620461262571571817332118436446169714841907666740181879376388985187361678135766188368485738209951956700783076041228005655652725793, 2665234620538688231167407939697346933754977146456580170193130367040949742393963909955559408816394881100545076543913434246925083790524693255847017082367387, 8600038730619055635902514545162508151144468789888696406296488651951157822189322145348010655551094806680329595209446924831992722415317667008746582082495675, 5542289822291791589715598176945254589111648232497656942612307873723644116486750493489701827783213540500405854206420118306886256549724655800326129898007895, 6573102035055801544872080972838984718118985369132207122010762536460412595265165167869412398677958808547838640685170917385093807206098062348143388107030461, 894990089240641252427255584481344341276584793315096681055638444558465749972035134569532322393381833391097043773177158869261589289555369898197568077479988)
c2 = (2494767299922768119966304157615544573281840712788050743310815843088606208826506798182423422612207921940191247843274664715522595500311725626787860311905779, 2382892837591516109796897578502619296738643486683059699110807061070647166859189870727637960681046613417850607198029130794496709351068093782480286800998312, 1938092671564729554410991610167064221338650843766282587438194653554180283448855577553129777267130474546763513710399512542827162548035887348885043284096892, 10056275305991735937461320919611368609107706999663414104392795690847294597338193779095228050105708278793597862090819360353804639855761860539119376561636538, 5932330661095519477541489017993825757488186784982658176722299977717898047999350995760469796176058082979227588900412665248435726471814698310501937767916848, 9674272255243904514628785356944352826058199311974554196761660992556564821545050628111582703612893432116577904974535922839925808445152893994869601237044110, 416121676363446620962571546745210868149450177349664715322759306013106618214436850123014365098930655624947877614392478106533783289360220629828711949548935, 1353741652212740844105673273558085980677642556949776050496826731304236059184964882227673922119867175097022437189123084120379459278386848690418338375196151, 3006871626772781231819888001720781266327049479293607803876487587088207535243116644892632593359322107339179460799063650468928143130800033677808065764573744, 784916531617250326992925022015957310339285250090392790736598710698527323713523943874546261817072810796863187183817174542557666498314118508366438566378607, 5833649388956828428504159063143421417915264475018821550654308483202441342809930834060051525291450843350208318543444273560349326130493390363249983502511726, 3558761440688563821959675021188168744275978189685744824332633745398421189026582096205885594433864178853745824802650832002143622606930736987689799939601193, 7043556561389701875853310212783761959226879202877197403227687173033725507323019359495673562666222088557972469469856102954556490294532543627371681455240366, 3034929722789552417427593116596567447493798371268181326072733599789255734353372957964532478787763914652720202163546211557367706500320940355978031490492397, 99030763885712035359521393349205763705723430110750166632832701106799607821327068761308965990810132567427530648228435398583626878014752326840794229591972, 3262108991133706000945565316697095077633537965775913520975580240043868288609456199183795480855854397847657367405787846138551116563298369395227781069106672)

题目加密流程如下：

  • 随机生成512bit的素数p以及一个16x16的可逆矩阵M

  • 把flag分成前后两部分，转为整数m1、m2分别进行加密，下面以m1为例

  • 分别生成两个长为8的随机向量u、v，并改变u的最后一个值使得向量u所有值的和为m1

  • 用u、v按如下方式生成向量U：

    1
    U += [(v[i] * u[i]) % p, v[i]]

  • 计算加密向量C：

  • 给出p、M、C，要求还原flag

既然给了M，那只需要：

  • 求出U：

  • 用U求出v，进而求出u

  • 求出u的和即为m

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
M = Matrix(Zmod(p),M)
U1 = M*vector(Zmod(p),c1)
U2 = M*vector(Zmod(p),c2)

U1_ = []
for i in range(8):
    U1_.append(U1[2*i] * inverse(U1[2*i+1], p) % p)
print(long_to_bytes(int(sum(U1_))))

U2_ = []
for i in range(8):
    U2_.append(U2[2*i] * inverse(U2[2*i+1], p) % p)
print(long_to_bytes(int(sum(U2_))))

#CCTF{8uIlD_a_HE_bAs3d_0N_thE_pr!v4Te_keY_3nCrypT1On_5ch3Me!!}

处理这矩阵的时间都比做题的时间长TT



Clement

题目描述：

1
Welcome to Clement Crypto Challenge, we have gained access to a very powerful supercomputer with high processing capabilities. Try to connect to the app running on this computer and find the flag.

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#!/usr/bin/env python3

import time
from functools import wraps
from Crypto.Util.number import *
from signal import *
from secret import rapid_factoreal_check, flag

def die(*args):
	pr(*args)
	quit()
	
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()
	
def sc():
	return sys.stdin.buffer.readline()

class TimeoutError(Exception):
	pass

def exec_limit(mt):
	def decorator(func):
		@wraps(func)
		def wrapper(*args, **kwargs):
			def _handle_timeout(signum, frame):
				raise TimeoutError(f"Function execution time exceeded {mt} seconds.")
			old_handler = signal(SIGALRM, _handle_timeout)
			alarm(int(mt))
			try:
				result = func(*args, **kwargs)
			except TimeoutError:
				return False
			finally:
				signal(SIGALRM, old_handler)
			return result
		return wrapper
	return decorator

TIMEOUT = 3
@exec_limit(TIMEOUT)
def factoreal(n, k, b):
	if b: # When YOU have access to supercomputer!
		i, s = 1, 1
		while i < n + 1:
			s = (s * i) % k
			i += 1
		if (4 * s + n + 5) % k == 0:
			return True
		return False
	else: # Otherwise
		return rapid_factoreal_check(n)

def main():
	global secret, border
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, "Welcome to Clement Crypto Challenge, we have gained access to a   ", border)
	pr(border, "very powerful supercomputer with high processing capabilities. Try", border)
	pr(border, "to connect to the app running on this computer and find the flag. ", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
	b, c, nbit, STEP = False, 0, 64, 40
	for level in range(STEP):
		pr(border, f"Your are at level {level + 1} of {STEP}")
		pr(border, f"Please submit an {nbit}-integer:")
		_n = sc().decode()
		try:
			_n = int(_n)
			_k = _n**2 + 4*_n + 3
		except:
			die(border, 'Your input is not integer! Bye!!')
		if _n.bit_length() == nbit:
			try:
				_b = factoreal(_n, _k, b)
			except TimeoutError:
				pass
		else:
			die(border, f"Your input integer is NOT {nbit}-bit! Bye!!") 
		if _b:
			c += 1
			nbit = int(1.1 * nbit) + getRandomRange(1, 12)
			if c >= STEP:
				die(border, f'Congratulation! You got the flag: {flag}')
		else:
			die(border, "Wrong response! Start again. Bye!!") 

if __name__ == '__main__':
	main()

题目需要连续通过19轮挑战（降低过难度），每轮挑战流程是：

  • 输入一个nbit的整数n，检验其满足：

  • 提高nbit的值

由同余定理我们可以知道其实每轮需要满足的是：

而既然有阶乘，自然会想到威尔逊定理，比如对于第一条等式，在n+1为素数的时候有：

所以：

因此n+1为素数就满足一式。而如果n+1是合数的话有：

所以不满足。

同样的，对于第二个式子也要利用威尔逊定理，所以我们不妨把它写成：

也就是：

如果n+3是素数，那么有：

也就是：

所以自然满足。

而如果n+3是合数，那么有：

而由前面的推论，我们知道n+1一定是素数，所以他和n+3没有公因子。而n+2和n+3又肯定是互素的，所以上面的式子一定不成立。因此满足题目挑战的充要条件就是：

  • n+1和n+3都是素数

所以其实就是简单爆一爆找twin primes而已。而由于有3s的timeout，所以用gmpy2的nextprime去找会比较快。

exp：

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

sh = remote("65.109.192.143", 37771)

for i in range(19):
    sh.recvuntil(b"Please submit an ")
    nbit = int(sh.recvline().strip().decode().split("-")[0])
    
    t = getRandomNBitInteger(nbit)
    while(1):
        t = next_prime(t)
        n = t - 1
        if(is_prime(t+2)):
            break

    sh.sendline(str(n).encode())
    print(nbit,sh.recvline())


#ASIS{gg_THeOR3M_0n_Tw!N_PrIm35!}



Goliver

题目描述：

1
Welcome to the Goliver World! You can play with ECC points on BTC curve. Your mission is to find the secret key and sweep wallets!

题目：

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
#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def die(*args):
	pr(*args)
	quit()
	
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()
	
def sc(): 
	return sys.stdin.buffer.readline()

def ADD(A, B):
	s = (B[1] - A[1]) * inverse(B[0] - A[0], p) % p
	x = (s ** 2 - A[0] - B[0]) % p
	y = (s * (A[0] - x) - A[1]) % p
	return (x, y)

def DOUBLE(A):
	s = ((3 * A[0] **2 + a) * inverse(2 * A[1], p)) % p
	x = (s ** 2 - 2 * A[0]) % p
	y = (s * (A[0] - x) - A[1]) % p
	return (x, y)

def MUL(A, d):
	_B = bin(d)[2:]
	_Q = A
	for i in range(1, len(_B)):
		_Q = DOUBLE(_Q);
		if _B[i] == '1':
			_Q = ADD(_Q, A);
	return _Q

def GENKEY():
	skey = getRandomRange(1, p)
	assert (G[1] ** 2 - G[0] ** 3 - a * G[0] - b) % p == 0
	pubkey = MUL(G, skey)
	if pubkey[1] % 2 == 0:
		pkey = "02" + hex(pubkey[0])[2:].zfill(64)
	else:
		pkey = "03" + hex(pubkey[0])[2:].zfill(64)
	return (pkey, skey)

def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, "Welcome to the Goliver World! You can play with ECC points on BTC ", border)
	pr(border, "curve. Your mission is to find the secret key and sweep wallets!  ", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
	global p, a, b, G
	p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
	a, b = 0, 7
	n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
	x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
	y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
	G = (x, y)
	pkey, skey = GENKEY()
	level, STEP, _b = 0, 10, False
	while True:
		pr("| Options: \n|\t[E]ncrypt point \n|\t[G]et the flag \n|\t[P]ublic key \n|\t[Q]uit")
		ans = sc().decode().strip().lower()
		if ans == 'e':
			pr(border, f"Please provide your desired point `H` on the Secp256k1 curve:")
			inp = sc().decode()
			try:
				_x, _y = [int(_) for _ in inp.split(',')]
				if (_x**3 + a * _x + b - _y**2) % p < 0x0f:
					_b = True
			except:
				die(border, f"The input point you provided is not valid!")
			if _b:
				_Q = MUL((_x, _y), skey)
				print(border, f"skey * H = {_Q}")
				if level == STEP:
					die(border, f'You have only {STEP} rounds to compute.')
				else:
					level += 1
			else:
				die(border, f'The input point is not on the curve! Bye!!')
		elif ans == 'g':
			pr(border, 'Please send the private key: ')
			_skey = sc().decode()
			try:
				_skey = int(_skey)
			except:
				die(border, 'The private key is incorrect! Quitting...')
			if _skey == skey:
				die(border, f'Congrats, you got the flag: {flag}')
			else:
				die(border, f'The private key is incorrect! Quitting...')
		elif ans == 'p':
			pr(border, f'pubkey = {pkey}')
		elif ans == 'q':
			die(border, "Quitting...")
		else:
			die(border, "Bye...")

if __name__ == '__main__':
	main()

题目基于Secp256k1曲线，大体是说靶机有一个私钥sk，我们可以交互最多十次，每次发送一个点H，靶机会计算sk倍的H之后返回。如果我们能在10此以内求出sk并提供给靶机就可以拿到flag。

而题目的这一部分简直是明示：

1
2
3
4
try:
	_x, _y = [int(_) for _ in inp.split(',')]
	if (_x**3 + a * _x + b - _y**2) % p < 0x0f:
		_b = True

这里的意思是说，靶机不会严格检查我们发送的点的坐标是不是在Secp256k1曲线上，而允许我们发送的点在：

只要其中7-b’在模p下小于15就行。

这就很简单了，我们取b’为0，发送的点就会在一条singular curve上：

由于singular curve有一个曲线加法群到模p加法群的映射：

所以简单求逆就可以拿到sk。

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
from Crypto.Util.number import *
from random import *
from pwn import *

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
F = GF(p)

sh = remote("65.109.204.171", 17371)
sh.sendline(b"e")
sh.recvuntil(b"Please provide your desired point `H` on the Secp256k1 curve:")

PR.<y> = PolynomialRing(F)
while(1):
    x = randint(1,p)
    f = y^2 - x^3
    res = f.roots()
    if(res != []):
        y = int(f.roots()[0][0])
        break

H = (x,y)
sh.sendline((str(x)+","+str(y)).encode())
sh.recvuntil(b"skey * H = ")
x1,y1 = eval(sh.recvline().strip().decode())


sk = int(F(x1)/F(y1)*F(y)/F(x))
sh.sendline(b"g")
sh.recvuntil(b'Please send the private key: ')
sh.sendline(str(sk).encode())
sh.recvuntil(b"you got the flag: ")
print(sh.recvline())


#ASIS{7w!sT_4tTAck_0n_8itcOin_Ell!ptic_cuRv3!}

当然也可以用其他b’去在低阶子群下crt得到sk，结合题目可以最多交互10次来看更像是预期解，但是显然比这个麻烦。



*Gasdeep

题目描述：

1
The Gasdeep challenge utilizes finite fields for message encryption; your objective is to explore potential weaknesses in the system to find a way to break it.

题目：

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
#!/usr/bin/env sage

from Crypto.Util.number import *
from secret import params, flag

def h(a):
	if a == 0:
		return 0
	else:
		g = F.gen()
		for _ in range(256):
			if g ** _ == a:
				return _

def H(M):
	assert M.nrows() == M.ncols()
	k, _H = M.nrows(), []
	for i in range(k):
		for j in range(k):
			_h = h(M[i, j])
			_H.append(bin(_h)[2:].zfill(8))
	return ''.join(_H)

def M2i(M):
	_H = H(M)
	return int(_H, 2)

def random_oracle(M):
	assert M.nrows() == M.ncols()
	k = M.nrows()
	try:
		r = M.order()
	except:
		r = k
	return H(M ** r)

def XOR(_H, _K):
	assert len(_H) == len(_K)
	X = [str(int(_h) ^^ int(_k)) for _h, _k in zip(_H, _K)]
	return ''.join(X)

def makey(params):
	u, k, d = params
	A, B = [random_matrix(F, k) for _ in '01']
	while True:
		f = PolynomialRing(F, 'x').random_element(degree = d)
		if f % A.characteristic_polynomial() != 0:
			break
	m, n = [randint(2, u) for _ in '01']
	R = f(A) ** m * B * f(A) ** n
	pkey = (A, B, R)
	skey = (f, m, n)
	return(pkey, skey)

def encrypt(pkey, msg):
	A, B, R = pkey
	k = A.nrows()
	_m = bytes_to_long(msg)
	_m = bin(_m)[2:]
	assert len(_m) <= 8 * k**2
	_M = _m.zfill(8 * k**2)
	while True:
		h = PolynomialRing(F, 'x').random_element(degree = d)
		if h % A.characteristic_polynomial() != 0:
			break
	m, n = [randint(2, u) for _ in '01']
	C, S = [h(A) ** m * _ * h(A) ** n for _ in [B, R]]
	D = XOR(random_oracle(S), _M)
	return(C, D) 

global F, d
F = GF(256)

u, k, d = params
assert u <= 1 << 64
pkey, _ = makey(params)
A, B, R = pkey

enc = encrypt(pkey, flag)
C, D = enc

print(f'g = {F.polynomial()}')
print(f'A = {M2i(A)}')
print(f'B = {M2i(B)}')
print(f'R = {M2i(R)}')
print(f'C = {M2i(C)}')
print(f'D = {int(D, 2)}')

输出太长就不放在这里了。

题目有点复杂，先理一下加密流程，为：

  • 密钥生成：

    • 有秘密参数u、k、d，用于生成密钥

      从后面可以知道u小于等于2^64，k=100，d确实不知道

    • 生成两个GF(2^8)下的k阶方阵A、B

    • 随机生成度为d的多项式f，要求f不能是A的特征多项式的倍数

      否则有$f(A) = O$

    • 随机生成两个(2,u)之间的正整数m、n，并计算R：

    • 公钥为$(A,B,R)$，私钥为$(f,m,n)$

  • 生成完密钥后进行加密：

    • 先把待加密消息m转为01串，并填充长度到8k^2，记为M

    • 随机生成度为d的多项式h，同样要求h不能是A的特征多项式的倍数

    • 随机生成两个(2,u)之间的正整数m’、n’，并计算C、S：

    • 计算密文D：

给出A、B、R、C、D，要求还原flag。

先不管题目M2i之类的数据处理，就从密钥生成和加密这两个步骤出发，我们的目标是通过已知的几个矩阵A、B、R、C来求出S，之后自然就能解密出D了。

而S为：

我们不知道f、h，也不知道m’、m、n、n’，所以要从已知的信息直接求出S来。

一个很重要的信息在于，既然A自己的任意幂次都是可以交换的，那么所有关于A的多项式当然也都可交换，也就是下面的式子恒成立：

所以上面S的式子中的f、h也就可以交换，但这种交换越不过中间的B：

我们把R的式子变一下形：

记：

那么就有：

所以如果我们能求出来X、Y，我们就可以直接求出S了。

而X、Y都是k阶方阵，相当于我们一共有2k^2个变量，而上面的这个约束只有k^2条等式，显然不太够：

但是注意到我们还有很重要的约束没有用，那就是X、Y对于A的可交换性：

这样又多了2k^2条等式，所以显然可以解出X、Y来，因此就可以求出S来解flag了。

这其实就是这篇论文对于这种加密体制的攻击情形之一：

1425.pdf (iacr.org)

赛后factoreal在discord提供了这篇论文，但是他好像没意识到这题0 solve的核心问题不在于找不找得到论文XD

似乎到这里就结束了，然而我怎么解都解不出这样的X、Y来，而用自己的测试数据发现能做，丢个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
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
from Crypto.Util.number import *

def h(a):
	if a == 0:
		return 0
	else:
		g = F.gen()
		for _ in range(256):
			if g ** _ == a:
				return _

def H(M):
	assert M.nrows() == M.ncols()
	k, _H = M.nrows(), []
	for i in range(k):
		for j in range(k):
			_h = h(M[i, j])
			_H.append(bin(_h)[2:].zfill(8))
	return ''.join(_H)

def M2i(M):
	_H = H(M)
	return int(_H, 2)

def random_oracle(M):
	assert M.nrows() == M.ncols()
	k = M.nrows()
	try:
		r = M.order()
	except:
		r = k
	return H(M ** r)

def XOR(_H, _K):
	assert len(_H) == len(_K)
	X = [str(int(_h) ^^ int(_k)) for _h, _k in zip(_H, _K)]
	return ''.join(X)

def makey(params):
	u, k, d = params
	A, B = [random_matrix(F, k) for _ in '01']
	while True:
		f = PolynomialRing(F, 'x').random_element(degree = d)
		if f % A.characteristic_polynomial() != 0:
			break
	m, n = [randint(2, u) for _ in '01']
	R = f(A) ** m * B * f(A) ** n
	pkey = (A, B, R)
	skey = (f, m, n)
	return(pkey, skey)

def encrypt(pkey, msg):
	A, B, R = pkey
	k = A.nrows()
	_m = bytes_to_long(msg)
	_m = bin(_m)[2:]
	assert len(_m) <= 8 * k**2
	_M = _m.zfill(8 * k**2)
	while True:
		h = PolynomialRing(F, 'x').random_element(degree = d)
		if h % A.characteristic_polynomial() != 0:
			break
	m, n = [randint(2, u) for _ in '01']
	C, S = [h(A) ** m * _ * h(A) ** n for _ in [B, R]]
	D = XOR(random_oracle(S), _M)
	return(C, D, S) 

global F, d
F = GF(256)

u, k, d = 2^64,100,40
pkey, _ = makey((u, k, d))
A, B, R = pkey
flag = b"CTF"
enc = encrypt(pkey, flag)
C, D, S = enc

############################################################ part1 handle data
# find that :
# RX = YB
# AX = XA
# AY = YA

# AX = XA
if(0):
    L = Matrix(F, k^2, k^2)
    R = vector(F, [0]*k^2)
    for i in range(k):
        for j in range(k):
            for t in range(k):
                L[k*i+j, k*i+t] += A[t,j]
                L[k*i+j, j+k*t] -= A[i,t]
    X = L.solve_right(R)

    temp = L.right_kernel().basis()[0]
    print(L.right_kernel().basis())
    X = Matrix(F,k,k)
    for i in range(k):
        for j in range(k):
            X[i,j] = temp[k*i+j]
    print(X*A == A*X)


# AX = XA and AY = YA and RX = YB
if(1):
    L = Matrix(F, 3*k^2, 2*k^2)
    Right = vector(F, [0]*3*k^2)

    #AX = XA
    for i in range(k):
        for j in range(k):
            for t in range(k):
                L[k*i+j, k*i+t] += A[t,j]
                L[k*i+j, j+k*t] -= A[i,t]

    #AY = YA
    for i in range(k):
        for j in range(k):
            for t in range(k):
                L[k^2+k*i+j, k^2+k*i+t] += A[t,j]
                L[k^2+k*i+j, k^2+j+k*t] -= A[i,t]

    #RX = YB
    for i in range(k):
        for j in range(k):
            for t in range(k):
                L[2*k^2+k*i+j, k^2+k*i+t] -= B[t,j]
                L[2*k^2+k*i+j, j+k*t] += R[i,t]

    XY = L.right_kernel().basis()[0]
    X = Matrix(F, k, k)
    Y = Matrix(F, k, k)
    for i in range(k):
        for j in range(k):
            X[i,j] = XY[k*i+j]
            Y[i,j] = XY[k^2+k*i+j]
	
    print(A*X == X*A and A*Y == Y*A and R*X == Y*B)

    ss = Y*C*X^(-1)
    print(ss == S)

    print(long_to_bytes(int(XOR(random_oracle(ss), D),2)))

所以应该是题目的数据处理函数出了问题。细看了一下发现：

1
2
3
4
5
6
7
8
def h(a):
	if a == 0:
		return 0
	else:
		g = F.gen()
		for _ in range(256):
			if g ** _ == a:
				return _

这个函数对于输入0、1输出的都是0，所以没有办法通过M2i的输出正确的逆回去，得到原来的矩阵A、B、R、C，所以自然也就是0解。

昨年ASIS Quals我记得也有个做不出来的题目，这下优良传统了XD