0%

2024-vyctf-wp-crypto

不太清楚这个比赛是多久办的,不过赛后有师傅给我看了看三个基于Cubic Pell Curve的小题目,虽然难度都不高,但是这条曲线确实不算很常见,所以正好借此机会水一篇博客。

基础概念

Cubic Pell Curve方程形式如下:

这条曲线登场次数不多,不过近几个月倒是见过好几回了,分别是在DASCTFxHDCTF和CryptoCTF,总之关于他的加解密可以参考:

eprint.iacr.org/2024/385.pdf

三个题目都是一些比较常见的问题搬到了这条曲线上做实现。

Pell Company’s A-level products

题目:

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
from Crypto.Util.number import *
from random import choice
from secret import p, a, flag


class PellCurve:
def __init__(self, a, N):
self.a = a
self.N = N

def add(self, P, Q):
if P is None:
return Q
if Q is None:
return P
x1, y1, z1 = P
x2, y2, z2 = Q
x3 = (x1 * x2 + self.a * (y2 * z1 + y1 * z2)) % self.N
y3 = (x2 * y1 + x1 * y2 + self.a * z1 * z2) % self.N
z3 = (y1 * y2 + x2 * z1 + x1 * z2) % self.N
return (x3, y3, z3)

def mul(self, P, x):
Q = (1, 0, 0)
while x > 0:
if x & 1:
Q = self.add(Q, P)
P = self.add(P, P)
x >>= 1
return Q

def random_point(self):
G = ???
k = getRandomRange(1, self.N)
return self.mul(G,k)


def sum(M, curve):
C = None
for i in M:
C = curve.add(C, i)
return C


E = PellCurve(a, p)
M = [E.random_point() for _ in range(64)]
key = [choice((0, 1)) for _ in range(64)]
c = sum([E.mul(M[i], key[i]) for i in range(64)], E)
assert flag == "vyctf{" + "".join(map(str, key)) + "}"
print("M = ", f"{M}")
print("c = ", f"{c}")
# M = [(1883517185424539320299837178282579401305938, 1229577549497465129374106153811601618552460, 2716673030362160267094735492757010227449299), (830032769678953263817386447091551727643245, 3122926093223163409007558196604022177688990, 5183507371978181226450441847254503540317696), (5425375409378014489528442925615648897738048, 5512776024931240922421849561546414305546198, 1989067703415507300306002915138935503367455), (565608994718233538569271826741929054273060, 4794771478795989838620562960237748296971765, 1094872379539573554823667505178624047033544), (4295645279315859136251000281207423856534707, 1137213853687810976454084971930331240226605, 5194105804282717231408802134970025672173519), (5002458281755986935972538524526968579330595, 1043320653358572419392693422551095404483725, 2410618104237812675284724078620827675292760), (5680304162427919657409266400275300792287945, 5409660226293604580723929354042196085709115, 5415075696625436996620126948043151726144444), (3313599527951997167196934225917767017237487, 5602085242558249324241838953979742566675049, 4577474923292493930809986162386067589788059), (2692035631782401134340951908583681363408340, 5323964889049669251814034563318488795199426, 1106906126959088308781666793569176703773519), (3195824268765202581670496580234484865276114, 541763085237474271848053866100595999937877, 6045678080274608949155708689438342303479570), (5098489958285669909618681341018009764231996, 567034184839864565296003248778574690458400, 605055075119120694583765492541266901614985), (2251482744097716376297322632987586240523579, 114184119715564412304213604850376772793551, 4456966389887242734936326288577022637469041), (2054221094423292669779015588072740246608598, 3892632738984948725535901098258157459980528, 6357005820623186627706460955279554765402165), (80110024193347778029820187633747322323398, 4648387082443987950738199662711450469706201, 3148040804470338994680520153991452725682723), (4082573729491839112867189532922635683167913, 4441124248818229713738033320126097681704036, 3396715673600612758402075301330211026958707), (3808909828889259152313552663842269993850543, 461457031589252797944507246233500479660154, 1493839442625571088404914177241595880816149), (224097468429487611116768098401758165343256, 2709136382556236720319739295968843724122805, 2659123166018517860499156226026503227290502), (4354709018406160042847643167809952850712909, 4574261325013667118560455098312021411071965, 5047075839531863146031964697090095505876591), (4186097304543875538338984376210367562929193, 3798727289507206001487250381152630247653747, 4825512562974469236444605493132118539780015), (5777063124569517486487818390439182853960573, 4661462137826823012395397607035741841182358, 2051865274158085094707210625304982572692107), (3613257770568471646486537972218125008190406, 2276179058747097484062795252569182122736697, 1732202552206982123861968799451810898425637), (4350295458903644423639049573704688724538783, 4986460189754412229454976450001740650527332, 2226186980868494288727061773697745101575014), (858771134228218804947848202094814930078715, 3473948072222638693999737352085899968537367, 3833930179936483434252976604253458241077574), (2890783623559572009048395110970217379891655, 1919665845030726680667421627365784024227508, 3957891423869707241275544529731955268900956), (809525232448824018135896714520455927218315, 4624738220440373023882725152813477454781486, 6300874740957559603489235864987957405516779), (2869863968390729263509622610814152159218254, 3890182464640848778409153220928728771001360, 2209215203719220624298610842248691121356188), (2191798171824611492700989310992980607355513, 16879945382768949985472107179718217809678, 6273331369412504259544999531930340561272020), (2766240531403386408481640389068419061375968, 4680802687081513993833416295286333159316078, 72902241392256266859448986156337561772298), (6052180269476650935320350878566794019475436, 1663834548063474145833160058973485693567096, 5475733377602703457024030039020819022922035), (2332557163127486951911402887726743018281639, 5727196730743872023509854086466570707762766, 2388009196274221518469639440927533973736277), (5089555749005696256160101894478268581908237, 5551876720096370124626837018294261280620053, 1567795905380036348927747789868601576215284), (1000453743445189668794334871667341159399312, 5673854601168185113517738348690616174054272, 3239875776253020614671920236491764972624381), (5931929575952179338954644277779580742169802, 4883784410238328032432385712724292534462724, 955301433963659161892167345618279462977442), (917799349955771410253730719448659373789441, 4247312265114108821500341578655429615020870, 5455224894675950765679923021429530718817597), (5639994845382362521347775596276796468108436, 2136345421307438479074190690584601073758684, 6430811344060961731057625590061852900091613), (291597227336835903114592168676011490095503, 5020788616963282390025622172055992884810595, 2276940530599280771506887373949731735813575), (5614884058380341562911544918527687105771918, 1927206937412374898644967908800188682540558, 6228617886948743334729884401911716290834386), (4031851102812510766323694927311911581357741, 6058491888561415862009803352466652620252303, 5793062644915287992299094125267529551763696), (3605009353259681367678848088476757538904993, 4206627646650091542412626184890256108282562, 4625570488656442871634601595104272816689688), (5218729471648314744182172798271293974378080, 685648274084635696499865165330122635580863, 295555820051694261986772842980046056521633), (6314079529795851493636073215529668051766538, 2575958562338308180445077756869928692312978, 3133508551231525218911278957788646999215242), (4574225077061178302272374619038170309329971, 2057584280858948245979252420677925686077222, 3798282354449084725421938572469491223528375), (4141654469919855627807335893360494696498391, 5207716618602228072644450970710924606254789, 2633391257385812171825124741715055629938919), (4014571950751237283416579207441179504016455, 2762336118623645152964464736682078505599575, 3817777571266262752210340193954194217266027), (1037326565531390156092239751558541772812495, 3364738613790404555923950519876405892690950, 5651699809366474433269992877448881328740813), (4983534686704707507198527462467424152415425, 1263254254476195778530901196161013414037417, 5295416094361380894215698586519116782269870), (4683611659075802288793483787787637685158148, 4543739745937733025728584758912139204015581, 3632844823998253436362352573379355251792396), (1912336962084176279862520250444473725586542, 6027325499497080929886741311952486560132563, 3388726103854589344630853900437458609847001), (1873591336833730674423737397585031919267239, 740129179597842850235936677482985595979969, 1785449262084867159091291953677661336975633), (4707184354428768971690260257142047345516452, 2254967183828912440014418026499100647854790, 264953876610356175552023604098714634846989), (3151521553668228404361866269503404884753700, 5160898393586095677195648012581807889764636, 413065431335386831463801386152279112744554), (6201334628105087076606552323457152743563314, 680122108230817477272864116101461598698480, 4048598157012425562058715033831068345092761), (940744339988965651864545629867270163509227, 4328268505481624266652903158565596905529505, 5038682162436684418398161125843942256265310), (2596862058424273256608276342351850715889848, 259388985054017615140742190722007899675774, 5046311293959175213164259736329657344118957), (2788731160970150983548781095793940789103280, 5981326728975341975113960844232716312813149, 5584030233802957448189061397052470753141861), (53563762438719940678457598455149576185475, 3551182599969285945430632748092869917492310, 4204665138025426917894742983706055632839847), (2558492684681780832281403555566099988667373, 1864638907209560779375289768746282459680486, 2876758333691795549335905309664366418224371), (2779377179428013229793463492748327138820089, 4383216409307704275729342638826813433149711, 3368643742006747116375473323683244453376971), (2139092887431861131814132701901752971875682, 919985898434834041196530705751218862856108, 1545292006423948929446018296069706911210482), (1151380688419800148593068398007689855417659, 5697670806029951779704191764956200604784722, 2395474318127434229064391754308815532069646), (1735852090832018873501069837336831947614559, 382036314419130772479100002645655071429107, 2836454455597501904245331244157604925330357), (2144076590264405882681241757855528263142970, 4117431024443775758228936987426464726614502, 1771722392696942120923490392199204091951683), (769581749535418139080737224266215882022830, 2214437166073033862147096408726593958868079, 48833877532457880081614693586092781278635), (4442650680868952149116238059964382373793221, 2433474197346746613356843499953833108142599, 5688412316628291870719234032448805647519545)]
# c = (5861392358276466039029270753631165865219027, 806771596873403559505046548063497647159419, 1715786609924291881692236299575902356731902)

题目随机生成64个曲线上的点$M_i$,并生成长64的01列表作为key,之后计算如下点当作密文:

仅给出$M_i$和$C$,要求解出列表key得到明文。

第一个地方在于题目没有给出曲线的参数a和p,但是由于我们有曲线方程形式以及多个曲线上的点,因此用几个点做groebner_basis就可以得到曲线参数了。

之后的问题在于如何恢复key,这个部分和我今年在NKCTF出的fly to the hyper一题很像,核心思路在于,我们拥有的式子其实很类似于一个01背包:

只是这里的背包元素不是数字而是点,没有办法直接做背包格规约,因此要想办法做点到数域的转换,转换的思路就是dlp。具体来说,如果我们找到曲线的生成元$G$,那么将所有点对$G$做DLP之后将会得到:

因此我们有:

此时就变成了我们熟悉的背包形式,不过这又引出了几个新问题:

  • Cubic Pell Curve的阶是多少?
  • 如何找到Cubic Pell Curve的生成元?
  • 如何做DLP?

首先是求阶,直接factor一下p-1的话会发现非常的光滑,所以曲线的阶大概率是p-1的某个倍数了,用mul函数测一测就会发现正好是p-1。

要找理论依据的话可以看论文section3的Lemma2:

image-20241106234421292

由于p的确是模3余1的,并且a也是三次剩余,所以曲线上阶应该是$(p-1)^2$,点阶是曲线阶的因子,所以阶是$p-1$很合理

接下来是找生成元,这里有个简单办法可以跳过这一步,注意到他的random_point是:

1
2
3
4
def random_point(self):
G = ???
k = getRandomRange(1, self.N)
return self.mul(G,k)

也就是说所有点都来自同一个$G$生成的点群内,那么当这次的k与点阶互素时,得到的新点也是$G$生成的循环群的生成元,所以从M中随便选一个当作$G$做就有一定概率成功。

最后是DLP,因为阶是光滑的,所以手写一个Pohlig-Hellman就行,这里偷了一点懒,其实可以在Pohlig-Hellman中间把点的重复倍乘换成逐次点加,并且用bsgs去加速,但是这个题求的并不算慢所以没啥必要优化。

之后就是做背包格规约,这里用优化的背包格+BKZ效果会好一些。

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

class PellCurve:
def __init__(self, a, N):
self.a = a
self.N = N

def add(self, P, Q):
if P is None:
return Q
if Q is None:
return P
x1, y1, z1 = P
x2, y2, z2 = Q
x3 = (x1 * x2 + self.a * (y2 * z1 + y1 * z2)) % self.N
y3 = (x2 * y1 + x1 * y2 + self.a * z1 * z2) % self.N
z3 = (y1 * y2 + x2 * z1 + x1 * z2) % self.N
return (x3, y3, z3)

def mul(self, P, x):
Q = (1, 0, 0)
while x > 0:
if x & 1:
Q = self.add(Q, P)
P = self.add(P, P)
x >>= 1
return Q

def cubic_pell_dlp(a, p, P, kP):
PCa = PellCurve(a,p)
#https://eprint.iacr.org/2024/385.pdf
order = (p-1)^2
order = p-1 # actually
primes = [2 , 3 , 13463 , 22993 , 36299 , 37087 , 46279 , 74903 , 75431 , 99109 , 99497]

c = []
for i in primes:
r = order // i
rP = PCa.mul(P, r)
rkP = PCa.mul(kP, r)
for j in range(i):
if(PCa.mul(rP, j) == rkP):
c.append(j)
break

k = int(crt(c, primes))
assert PCa.mul(P, k) == kP
return k


M =
c =

#################################################### get params
if(0):
F = []
PR.<a, b> = PolynomialRing(ZZ)
for i in range(10):
x, y, z = M[i]
f = x^3 + a*y^3 + a^2*z^3 - 3*a*x*y*z - 1
F.append(f)
res = Ideal(F).groebner_basis()
print(res)

p = 6447052766212423581405069725091189142664263
a = p - 6447052766212423581405052027737004347006630

#################################################### dlp
if(0):
Bag = [1]
for i in trange(1,64):
Bag.append(cubic_pell_dlp(a, p, M[0], M[i]))

#################################################### knapsack
C = cubic_pell_dlp(a, p, M[0], c)

L = Matrix(ZZ, len(Bag)+2, len(Bag)+2)
for i in range(64):
L[i,i] = 2
L[i,-1] = Bag[i]
L[-2,i] = -1
L[-2,-2] = 1
L[-2,-1] = -C
L[-1,-1] = p-1

L[:, -1:] *= 2^20
res = L.BKZ()[0]

key = []
for i in range(len(Bag)):
key.append((res[i] + 1) // 2)
print(key)

#################################################### check
def sum(M, curve):
C = None
for i in M:
C = curve.add(C, i)
return C

E = PellCurve(a, p)
cc = sum([E.mul(M[i], key[i]) for i in range(64)], E)
assert cc == c

#################################################### get flag
flag = "vyctf{" + "".join(map(str, key)) + "}"
print(flag)


#vyctf{0010011100000101010011100001101111110101011001000101011111101001}



Pell Company’s B-level products

题目:

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
from Crypto.Util.number import *
from secret import flag


class Pell_Curve:
def __init__(self, a, N):
self.a = a
self.N = N

def is_on_curve(self, point):
if point is None:
return True
x, y, z = point
return (
x**3 + self.a * y**3 + self.a**2 * z**3 - 3 * self.a * x * y * z
) % self.N == 1

def add(self, P, Q):
x1, y1, z1 = P
x2, y2, z2 = Q
x3 = (x1 * x2 + self.a * (y2 * z1 + y1 * z2)) % self.N
y3 = (x2 * y1 + x1 * y2 + self.a * z1 * z2) % self.N
z3 = (y1 * y2 + x2 * z1 + x1 * z2) % self.N
return (x3, y3, z3)

def mul(self, P, x):
Q = (1, 0, 0)
while x > 0:
if x & 1:
Q = self.add(Q, P)
P = self.add(P, P)
x >>= 1
return Q


def cubic_residue(a, p):
return pow(a, (p - 1) // GCD(3, p - 1), p) == 1


flag1 = flag[: len(flag) // 2]
flag2 = flag[len(flag) // 2 :]
m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)
p = getPrime(512)
q = getPrime(512)
assert p % 3 == 1 and q % 3 == 1
n = p * q
a = (1 - m1**3) * inverse(m2**3, n) % n
d = getPrime(400)
cr_p = cubic_residue(a, p)
cr_q = cubic_residue(a, q)
if not cr_p and not cr_q:
e = inverse(d, (p**2 + p + 1) * (q**2 + q + 1))
elif cr_p and cr_q:
e = inverse(d, (p - 1) ** 2 * (q - 1) ** 2)
elif not cr_p and cr_q:
e = inverse(d, (p**2 + p + 1) * (q - 1) ** 2)
else: # cr_p and not cr_q
e = inverse(d, (p - 1) ** 2 * (q**2 + q + 1))
M = (m1, m2, 0)
curve = Pell_Curve(a, n)
print(curve.mul(M, e))
print(n)
print(e)
"""
(18651704911965069518581195835755344628286583043192331182401551490551283590671122550950109003529689245482633928900782246334607547422529359499998839876687476725231164317679561857025380505688235655619764511588181243877410281250100062973738672030667299593220892000278088427665293099732579737599006177322470079851, 31397861767983140122135497121128707712857449359263658425393642945254333193137444951325946933651959173827092248926195011350857699448599461019379099126907985606111213659857419379796034341293508242987940486496880505960649198981029282894781003694587273709945051808377327563310602734180828485458002806035588030111, 24762374784771416543482851014109269295665013774959725373829410358586752863456858191168335644211597913386246106593314466283725901250259609411472578034994619674523120410812349794790706535257025439301157867633857139922315976439344451881103246997673492221390726863135081391105193481452040198383055622567036687732)
92699162439172361238547194222128583102549260809218150978451619617020664107111087298362330972163961391665418991909607896401110418428822348346671272088118965489377171070258369042978232802249784654414422343694235412266385283165413087795774064174777617970417912426116068452289533263498959824500926331062264413439
920376747567452004463098313440304015094485778772331075496295784862804013780976739198378305426974272857514093193785593896542650666019167140681428366222911876817443794283171266459230549559249675014309804610408623685733222811934244329240154181235166886019948084131423333322065867963625522980839981025912991506555552428812587401284025562097820189735421665429319677335684777440645280955412582049649891053473128069471090454197223798220753970108135518003459495692182779290757258324286961690103842874258835647821047285511405965298927971362379614387218364285702984420139271278660910048109581493977426710571991415006717061087
"""

注意到题目中一个明显的点在于私钥d只有400bit,肯定算个小量,而曲线的阶也把四种可能性都给出了:

1
2
3
4
5
6
7
8
if not cr_p and not cr_q:
e = inverse(d, (p**2 + p + 1) * (q**2 + q + 1))
elif cr_p and cr_q:
e = inverse(d, (p - 1) ** 2 * (q - 1) ** 2)
elif not cr_p and cr_q:
e = inverse(d, (p**2 + p + 1) * (q - 1) ** 2)
else: # cr_p and not cr_q
e = inverse(d, (p - 1) ** 2 * (q**2 + q + 1))

没给出的话可以参考论文的section3的Corollary4:

image-20241106235721533

所以其实本质上是个低解密指数攻击,只需要逐个尝试阶是哪种情况去做copper就好, 会发现可以在第二种情况求解出题目的p、q和d来。

之后是要求明文,按加密方式来讲也就是要求出M,而为了求出M我们还需要求出a,才能对M的e倍点在曲线上做d倍的倍乘从而恢复M。而a的求解很简单,我们只需要代入$eM$的坐标$(x,y,z)$,然后分别在p、q下求解如下方程的根:

之后crt起来就行。

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

eP = (18651704911965069518581195835755344628286583043192331182401551490551283590671122550950109003529689245482633928900782246334607547422529359499998839876687476725231164317679561857025380505688235655619764511588181243877410281250100062973738672030667299593220892000278088427665293099732579737599006177322470079851, 31397861767983140122135497121128707712857449359263658425393642945254333193137444951325946933651959173827092248926195011350857699448599461019379099126907985606111213659857419379796034341293508242987940486496880505960649198981029282894781003694587273709945051808377327563310602734180828485458002806035588030111, 24762374784771416543482851014109269295665013774959725373829410358586752863456858191168335644211597913386246106593314466283725901250259609411472578034994619674523120410812349794790706535257025439301157867633857139922315976439344451881103246997673492221390726863135081391105193481452040198383055622567036687732)
n = 92699162439172361238547194222128583102549260809218150978451619617020664107111087298362330972163961391665418991909607896401110418428822348346671272088118965489377171070258369042978232802249784654414422343694235412266385283165413087795774064174777617970417912426116068452289533263498959824500926331062264413439
e = 920376747567452004463098313440304015094485778772331075496295784862804013780976739198378305426974272857514093193785593896542650666019167140681428366222911876817443794283171266459230549559249675014309804610408623685733222811934244329240154181235166886019948084131423333322065867963625522980839981025912991506555552428812587401284025562097820189735421665429319677335684777440645280955412582049649891053473128069471090454197223798220753970108135518003459495692182779290757258324286961690103842874258835647821047285511405965298927971362379614387218364285702984420139271278660910048109581493977426710571991415006717061087

if(0): # (p^2+p+1)*(q^2+q+1)
PR.<x,y>=PolynomialRing(Zmod(e))
f = 1 + x*(n^2-n+1 + (n+1)*y + y^2)
res = small_roots(f, (2^dbits,2^513), m=4, d=4)
print(res)

if(1): # (p-1)^2*(q-1)^2
PR.<x,y>=PolynomialRing(Zmod(e))
f = 1 + x*(n^2+2*n+1 - 2*(n+1)*y + y^2)
res = small_roots(f, (2^dbits,2^513), m=4, d=4)
print(res)

class Pell_Curve:
def __init__(self, a, N):
self.a = a
self.N = N

def is_on_curve(self, point):
if point is None:
return True
x, y, z = point
return (
x**3 + self.a * y**3 + self.a**2 * z**3 - 3 * self.a * x * y * z
) % self.N == 1

def add(self, P, Q):
x1, y1, z1 = P
x2, y2, z2 = Q
x3 = (x1 * x2 + self.a * (y2 * z1 + y1 * z2)) % self.N
y3 = (x2 * y1 + x1 * y2 + self.a * z1 * z2) % self.N
z3 = (y1 * y2 + x2 * z1 + x1 * z2) % self.N
return (x3, y3, z3)

def mul(self, P, x):
Q = (1, 0, 0)
while x > 0:
if x & 1:
Q = self.add(Q, P)
P = self.add(P, P)
x >>= 1
return Q

from gmpy2 import *

pplusq = int(res[0][1])
pminusq = iroot(pplusq^2-4*n,2)[0]
p = (pplusq + pminusq) // 2
q = n // p
d = inverse(e, (p-1)^2*(q-1)^2)


x, y, z = eP
PR.<a> = PolynomialRing(Zmod(p))
fp = x**3 + a * y**3 + a**2 * z**3 - 3 * a * x * y * z - 1
resp = fp.roots()

PR.<a> = PolynomialRing(Zmod(q))
fq = x**3 + a * y**3 + a**2 * z**3 - 3 * a * x * y * z - 1
resq = fq.roots()
for i in resp:
for j in resq:
nlist = [p, q]
clist = [int(i[0]),int(j[0])]
A = int(crt(clist,nlist))
curve = Pell_Curve(A, n)
P = curve.mul(eP, d)
if(P[-1] == 0):
print(long_to_bytes(P[0]) + long_to_bytes(P[1]))
break


#vyctf{ffefc2b4c1482c8beef04fbdd0e38e7a931d4f41c2e63f7aa13b2e1d1ef7f970}



Pell Company’s C-level products

题目:

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
from sage.all import *
from hashlib import md5
from secret import flag

class PellCurve:
def __init__(self, a):
self.a = a

def is_on_curve(self, point):
if point is None:
return True
x, y, z = point
return x**3 + self.a * y**3 + self.a**2 * z**3 - 3 * self.a * x * y * z == 1

def add(self, P, Q):
if P is None:
return Q
if Q is None:
return P
x1, y1, z1 = P
x2, y2, z2 = Q
x3 = x1 * x2 + self.a * (y2 * z1 + y1 * z2)
y3 = x2 * y1 + x1 * y2 + self.a * z1 * z2
z3 = y1 * y2 + x2 * z1 + x1 * z2
return (x3, y3, z3)

def mul(self, P, x):
Q = (1, 0, 0)
while x > 0:
if x & 1:
Q = self.add(Q, P)
P = self.add(P, P)
x >>= 1
return Q

p = 7736463902201159740118932754011620145975008450384170845336675440861463026232568288223917198358124838723791482203770314299407932769813520037488990861475959
F.<i> = GF(p^2, modulus = x^2 + 1)
a = 130871745725209969614611893778594556915917233718507537270216668557136798272256283626165318253326763675138867993923391676212211045756677402353944883581233*i + 5463457605278021750020034082584583115139797651958508111949555067802962790173669690412609317078294589296489273547950180647147876900894834443846190572571696
E = PellCurve(a)
m1 = F.random_element()
m2 = F.random_element()
m3 = F.random_element()
M = (m1, m2, m3)
assert E.is_on_curve(M)
assert flag == b'vyctf{' + md5(str(M).encode()).hexdigest() + b'}'
e = 65537
print(E.mul(M, e))
# (2823882525778414914237398444108151393981113566541635183419622340039938672184328753758298548918787428250116134068382389334242105084692173414429956902849843*i + 501164702491749333682765358946697947688573177272098751657325300437649872050414128812118537575250147254280402586079012846286096796869401052168743886107534, 4837862363807903068128257976189130805733302116355328166297724960707625322363141989215336919343579452694002337840915182469494036549146117604660339020586849*i + 5855454475841727264607070318284344764898062377628596605227993533284577537898511837503348698520691620933858945624294084052067465791776401535155921640195193, 1609275482227124565984917792847227243210616298250428043294264717677853880558271216887565178289497667137239621710313302332913077497191916722279615976512906*i + 3892604125227602536136942214234553550698298099202459739427237115820941172342061217458683184695896406467762300558873832431907789989774953944404027390892931)

这个题最容易,仅仅是把Cubic Pell Curve放到了模p下的二次扩域上来,我们唯一需要求解的就是曲线的阶从而求逆得到原点。

而由第二题中的曲线阶可以观察到,这种曲线的阶是分圆多项式或者$(p-1)^k$,而分圆多项式又是$p^k-1$的因子,所以我们只需要在小范围内把:

这样形式的阶都试一试就好了,就会发现$p^6-1$就是阶的一个倍数。

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
from Crypto.Util.number import *
from hashlib import md5

class PellCurve:
def __init__(self, a):
self.a = a

def is_on_curve(self, point):
if point is None:
return True
x, y, z = point
return x**3 + self.a * y**3 + self.a**2 * z**3 - 3 * self.a * x * y * z == 1

def add(self, P, Q):
if P is None:
return Q
if Q is None:
return P
x1, y1, z1 = P
x2, y2, z2 = Q
x3 = x1 * x2 + self.a * (y2 * z1 + y1 * z2)
y3 = x2 * y1 + x1 * y2 + self.a * z1 * z2
z3 = y1 * y2 + x2 * z1 + x1 * z2
return (x3, y3, z3)

def mul(self, P, x):
Q = (1, 0, 0)
while x > 0:
if x & 1:
Q = self.add(Q, P)
P = self.add(P, P)
x >>= 1
return Q

p = 7736463902201159740118932754011620145975008450384170845336675440861463026232568288223917198358124838723791482203770314299407932769813520037488990861475959
F.<i> = GF(p^2, modulus = x^2 + 1)
a = 130871745725209969614611893778594556915917233718507537270216668557136798272256283626165318253326763675138867993923391676212211045756677402353944883581233*i + 5463457605278021750020034082584583115139797651958508111949555067802962790173669690412609317078294589296489273547950180647147876900894834443846190572571696
E = PellCurve(a)
e = 65537
eM = (2823882525778414914237398444108151393981113566541635183419622340039938672184328753758298548918787428250116134068382389334242105084692173414429956902849843*i + 501164702491749333682765358946697947688573177272098751657325300437649872050414128812118537575250147254280402586079012846286096796869401052168743886107534, 4837862363807903068128257976189130805733302116355328166297724960707625322363141989215336919343579452694002337840915182469494036549146117604660339020586849*i + 5855454475841727264607070318284344764898062377628596605227993533284577537898511837503348698520691620933858945624294084052067465791776401535155921640195193, 1609275482227124565984917792847227243210616298250428043294264717677853880558271216887565178289497667137239621710313302332913077497191916722279615976512906*i + 3892604125227602536136942214234553550698298099202459739427237115820941172342061217458683184695896406467762300558873832431907789989774953944404027390892931)


if(0):
for t in range(20):
print(t)
order = p^t - 1
M = E.mul(eM, order)
for i in M:
print(i)
print()

order = p^6 - 1
M = E.mul(eM, inverse(e, order))

assert E.mul(M, e) == eM

flag = 'vyctf{' + md5(str(M).encode()).hexdigest() + '}'
print(flag)


#vyctf{19636b9eb26a0f0701691f84a643b081}