0%

2024-数信杯决赛-wp-crypto

有好几个师傅来问了这场的题目,就写个wp。

trick

题目:

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

flag = b'xxx'
flag1,flag2 = flag[:len(flag)//2],flag[len(flag)//2:]

# trick one
def my_sum(q, p):
ret = 0
while q > 0:
ret += q * (q - 1) // 2 * (p // q)
q, p = p % q, q
return ret

def get_keys():
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
c = pow(bytes_to_long(flag1),e,n)
s = my_sum(q,p)
return n,c,s

# trick two
class strangeEnc():
def __init__(self,bits):
self.bit = bits
self.e2 = None
self.e1 = None
self.n = None
self.c2 = None
self.c1 = None

def get_keys(self):
e =
assert isPrime(e) and isPrime(e+2) and isPrime(e+4)
p,q = getPrime(self.bit),getPrime(self.bit)
self.n = p*q
phi = (p-1)*(q-1)
self.e1 = pow((e+2),2023,phi)
self.e2 = pow((e+4),2023,phi)

def enc(self,m):
self.c1 = pow(m,self.e1,self.n)
self.c2 = pow(m,self.e2,self.n)

n1,c1,s = get_keys()
enc1 = strangeEnc(512)
enc1.get_keys()
enc1.enc(bytes_to_long(flag2))
n,e2,e3,c2,c3 = enc1.n,enc1.e1,enc1.e2,enc1.c1,enc1.c2

print(f'n1 = ',n1)
print(f'c1 = ',c1)
print(f's = ',s)
print(f'n = ',n)
print(f'c2 = ',c2)
print(f'c3 = ',c3)

'''
n1 = 22383505276728850137663455393633079686429238084408197797583598736760650003679916079650214682155847316076882725141374570460302120855096764538513229862795954147385108308900387069345779449915103629739531828669308609441662300053335686176325098105502184367217993677434252119478443682025354702266792166833784426453473827860172898402795550688610803859067811964931720104933533009885427642851084316565899573561455532590544434854937254255247776951478445378589747901688556058168321108741071828667007173309988355887026701162038060926192564221402875319027966998238769416711177531710785248139168620803548356938612241925380932722399
c1 = 1875398879251872719868560355474242782099823316126827285930474891901277579939760214035965660611635384718229823179041813298873206611283777203743667296506779512722783498577223248836597765063738710749848584774655051102678241594592558007326479725436015975654991768707911096986479210248598327791663633518053344744802610403121077377183221698216942452214704851555128817663013206210786245462794073787939188187310712986483732138020871433643195026191781442811424627811943780027182774192751752696323773367738469182341814291728285268560078864055278903890022779469276094336870186451714400643212890505086008116445776789803714054907
s = 11191752638364425068831727696816539843214619042204098898791799368380325001839958039825107341077923658038441362570687285230151060427548382269256614931397977073692554154450193534672889724957551814869765914334654304720831150026667843088162549052751092183608996838717126059739221841012677351133396083416892213226585669994317200050481169069680885500843210173755018864594875542790353631179885963409919776486038376299550585483719635362703712132567116865982352527948168359492173006364155730215536286166608846636096515412786566634124854053845424324140256891074367122913731031405668717883454810908906437441661786414144891345700
n = 74756662778639436562975999330825359536823289573050471468080861637518231366096792233276979250912851132414972772183499047007690364398808857720990298542543868595743284766520494638065061281311051858351451376628785343090755545582058510677441863939290967915943438156799259309049707455111457719863806587428279966913
c2 = 64621564085446025460866271759165566020214396004425177207823794891920404777580879190969580025066850950809371591382009507114472330028747960284692087131597290543485701418187494780905960234921865134547461595039127664304406560958535606724859673641460627603499570374549012252315820754504800780212190700219217569262
c3 = 27639843852370792448968858748200299412010418689028931967221527924245149194537914958726591682560452552544925542728165476332055988130978672645320390031855755873730679978008696737722666072210193829081412559508020694493801760998905958871041371292406719376419203098956321684168036111911615688064341797998359095922
'''

题目分成两个trick,要分别解得flag的两部分。

第一部分主要在于用如下关于p、q的函数输出来分解n:

1
2
3
4
5
6
def my_sum(q, p):
ret = 0
while q > 0:
ret += q * (q - 1) // 2 * (p // q)
q, p = p % q, q
return ret

这个输出用小数字测一下,就可以发现对于素数的p、q,他的值就是$\frac{(p-1)(q-1)}{2}$,所以相当于我们有了$\phi(n)$,就可以直接解出第一段明文。

第二个trick主要在于:

1
assert isPrime(e) and isPrime(e+2) and isPrime(e+4)

很显然这三个数字模3的余数各不相同,因此至少有一个是3的倍数,而又因为他们都是素数所以只可能是3、5、7,因此就可以得到后面的e1、e2,之后共模攻击就行。

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

n1 = 22383505276728850137663455393633079686429238084408197797583598736760650003679916079650214682155847316076882725141374570460302120855096764538513229862795954147385108308900387069345779449915103629739531828669308609441662300053335686176325098105502184367217993677434252119478443682025354702266792166833784426453473827860172898402795550688610803859067811964931720104933533009885427642851084316565899573561455532590544434854937254255247776951478445378589747901688556058168321108741071828667007173309988355887026701162038060926192564221402875319027966998238769416711177531710785248139168620803548356938612241925380932722399
c1 = 1875398879251872719868560355474242782099823316126827285930474891901277579939760214035965660611635384718229823179041813298873206611283777203743667296506779512722783498577223248836597765063738710749848584774655051102678241594592558007326479725436015975654991768707911096986479210248598327791663633518053344744802610403121077377183221698216942452214704851555128817663013206210786245462794073787939188187310712986483732138020871433643195026191781442811424627811943780027182774192751752696323773367738469182341814291728285268560078864055278903890022779469276094336870186451714400643212890505086008116445776789803714054907
s = 11191752638364425068831727696816539843214619042204098898791799368380325001839958039825107341077923658038441362570687285230151060427548382269256614931397977073692554154450193534672889724957551814869765914334654304720831150026667843088162549052751092183608996838717126059739221841012677351133396083416892213226585669994317200050481169069680885500843210173755018864594875542790353631179885963409919776486038376299550585483719635362703712132567116865982352527948168359492173006364155730215536286166608846636096515412786566634124854053845424324140256891074367122913731031405668717883454810908906437441661786414144891345700
n = 74756662778639436562975999330825359536823289573050471468080861637518231366096792233276979250912851132414972772183499047007690364398808857720990298542543868595743284766520494638065061281311051858351451376628785343090755545582058510677441863939290967915943438156799259309049707455111457719863806587428279966913
c2 = 64621564085446025460866271759165566020214396004425177207823794891920404777580879190969580025066850950809371591382009507114472330028747960284692087131597290543485701418187494780905960234921865134547461595039127664304406560958535606724859673641460627603499570374549012252315820754504800780212190700219217569262
c3 = 27639843852370792448968858748200299412010418689028931967221527924245149194537914958726591682560452552544925542728165476332055988130978672645320390031855755873730679978008696737722666072210193829081412559508020694493801760998905958871041371292406719376419203098956321684168036111911615688064341797998359095922

################################################################################### part1
def my_sum(q, p):
ret = 0
while q > 0:
ret += q * (q - 1) // 2 * (p // q)
q, p = p % q, q
return ret

for i in range(10):
p, q = getPrime(128), getPrime(128)
assert my_sum(q, p) == (q-1)*(p-1) // 2

m1 = pow(c1, inverse(65537, 2*s), n1) # attually my_sum(q, p) is (q-1)*(p-1) // 2


################################################################################### part2
from gmpy2 import *

e = 3 # only 3,5,7 meets the demand
e1 = (e+2)^2023
e2 = (e+4)^2023
d,x,y = gcdext(e1,e2)
m2 = pow(c2,x,n)*pow(c3,y,n) % n
print(long_to_bytes(m1) + long_to_bytes(m2))


#flag{c4efd5020cb49b9d3257ffa0fbccc0ae}



DDLLPP

题目:

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

m = bytes_to_long(flag)
p = 156115360763408463288966087959515407156846780488826750491921450156778549686830192729652167507054847091579757631324431846770595853060183819226167
g = 16112732773996424707

order = GF(p)(g).multiplicative_order()
fac = factor(order-1)

c = []
x = []
for i in range(1, len(fac)):
xi = (order - 1) // (fac[i][0]) * getPrime(300)
ci = pow(g, pow(m, xi, order), p)
x.append(xi)
c.append(ci)

print(f"x = {x}")
print(f"c = {c}")

'''
x = [147649922240733214931938382533299162852239348315322202024816012220190164990577812905694252095760624439151794000123677274895623809190076928245613944439873573607452325298515467162143645462260131175628858455059408827679537866, 147644772650912060216213753348015513337396934565568307574474899641595228671372662635514128646171206026764270327456729799219586211940162384548230502304807283182736386643239100082734250340169696323090999431454785416052449822, 149269411636750703984577479205935816470190760232375388500570098501093159023749275406514479882987042162341103784724354021794002113424056019424236318901646922511135094047290597218316029950824101156465015382592106764226689366, 196150287310738275233976490100915145314242181250918121143881580393441675718040839096578059550733453877149829142446637258193486806259462575641487682725874844491268829888969640104850204930171839770385340396857083270374650086, 176349489748321571272565603934309732142460694086037582675840150899116324432891582015400827333320599715498609930517259021459948220481490102455623631080293179908366540916891458823890009104176809973215536171814869981029570622, 149605686008934472603553678282301090511189963461227603575425242179942083535824047539877995667786104909758015530206013788550584344630984369586721092949558231023248318500741255737481332399584789444750486399094957601650804226, 167090950560844022360160199561741977922499930289466557020320597983114664988151509771708026839823381777607944610693749808422555004194841221065937445184133790727920860624921174387660725583778620218002895521279169556687637458, 172050836264264531258995087363702968248917626047934042630528415155132231140508644029599127244879051539267358002191035421289125204823940752365920253806252280135208982388638638499493964850701542139656158750314341254497187842, 171940203480163609379955377980802940579133331691907105899695838468763589198624951628796073230487728578449404061809128906749299219776549427144505908935772797140694656690672598481007142599063775428416387593447970673282632558, 103219291391536095878880034390346953422786271761523298742391169540330754898330394255571346430660715071684164206474477771947648781967064107154643784549798248272157384762664350763722568774041179922240639096353451631378825726, 117056923364128416359225652777713478574064992861948997533153939432247506685002462469811749968546913699301322755483896459497141460002559118995887988073505736811451551865962302723189596066237079194160774624115297268028146222, 75988171484629553691726063948676260814799772175458832559939830959325834682356888352022448666576264219187808584376882565208027267132917947746488916430085062850228779315594314788358632633193395144020398274344181485674509442]
c = [89211588565232244243020044137513332743269967718877480628261718818351757152813010119069284596895225619225592906209397263094049572230279934266154, 105084158613940886109463172309553111555022087987329070889082019479640792410344881505566965101618478019481030407710176448598323171652419554631833, 106157114923928357578300476119375630224120567854699215551331601909290668630663627567930632807187355693727678752488106832973553103202592938942770, 80557564606220145949033391807467833274034216235778526123196512291405199108579104993671137966232164373337992822860664213094236154838829017972325, 39446948431345684527354210960423038896776791694000880147447072994325975700250899240792675465525991887150481970007736257124244137651624443394152, 119520811258897734242352491410708211023486196867717958794495866712623086226488074898297344260921581145340120126196702495352001228111155023751961, 1342770054334431658111079092718547092324646823520496933189758128906340841380811640267019361812318970025491217723403645803306128707939373166022, 117034748679632935974190191234946643889177466547301929478348628684004040210858236619532197365526820452011678286033898345399811113759206056247927, 142937859112056225912918426292604754870431374511209971957972472983061236076109506454150799842170514956334060919400188570742007461222222639963317, 126864447414128885965807626174194404848334608319577370194369994669518133538013998460358715002795480252978924576799926533593892178036375932388876, 22493364980376274642444643759903756666977805851594216444500605030927010663223507136840503959343412921823289896945796358190298587692628276796010, 115905066506480181865265402577373138871074064300913852519921798659037386902047909009848923352447322605148929915853806888695212542107641045508495]
'''

先观察一下数据,这个题目中的p满足安全素数的形式:

q也就是模p下乘法群的order,而q又是个q-1光滑的数字,其因子为:

1
2 * 630764016613 * 636284201767 * 666116332547 * 680344318523 * 684825194551 * 719482804681 * 741454555679 * 761339535743 * 864242985583 * 885840248239 * 925948879099 * 1088296917251

均为40bit左右。

在这基础上,题目将flag转为大整数m,之后对于每个q-1的除2以外的小因子$r_i$,计算:

其中$a_i$是个随机的300bit的素数,g是模p下乘法群的生成元。

我们的目的是求出m,不妨先把目光放在指数上,令:

可以看出有:

这说明我们能获得的一个信息是:$t_i$是模q下的一个$r_i$阶子群的元素,所以假如该$r_i$阶子群生成元为$g_i$,就有:

代回到原式子就有:

注意,对于每个q-1的小因子$r_i$,是能够找到对应的低阶子群的生成元的,也就是说$g_i$是我们知道的量,所以唯一要求的量变成了一个40bit左右的$k_i$而已,因此自然想到变成如下mitm:

化简就变为:

和RSA类似,求一个解密指数$d_i$满足:

那么就有:

然后用一边建字典,一边查字典即可mitm。

而mitm获得的是每一次的$k_i$,也就等于获得每一次的$t_i$,而我们有:

注意每个$x_i$都和q-1不互素,并且有相当大的公因子,因此不能用RSA解密的同时,也不能用AMM开根。

解决方法是利用LLL找到一组$e_i$满足:

所有$x_i$的公因子为2,那么此时就有:

这个时候就可以有限域开根得到m了。

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

x = [147649922240733214931938382533299162852239348315322202024816012220190164990577812905694252095760624439151794000123677274895623809190076928245613944439873573607452325298515467162143645462260131175628858455059408827679537866, 147644772650912060216213753348015513337396934565568307574474899641595228671372662635514128646171206026764270327456729799219586211940162384548230502304807283182736386643239100082734250340169696323090999431454785416052449822, 149269411636750703984577479205935816470190760232375388500570098501093159023749275406514479882987042162341103784724354021794002113424056019424236318901646922511135094047290597218316029950824101156465015382592106764226689366, 196150287310738275233976490100915145314242181250918121143881580393441675718040839096578059550733453877149829142446637258193486806259462575641487682725874844491268829888969640104850204930171839770385340396857083270374650086, 176349489748321571272565603934309732142460694086037582675840150899116324432891582015400827333320599715498609930517259021459948220481490102455623631080293179908366540916891458823890009104176809973215536171814869981029570622, 149605686008934472603553678282301090511189963461227603575425242179942083535824047539877995667786104909758015530206013788550584344630984369586721092949558231023248318500741255737481332399584789444750486399094957601650804226, 167090950560844022360160199561741977922499930289466557020320597983114664988151509771708026839823381777607944610693749808422555004194841221065937445184133790727920860624921174387660725583778620218002895521279169556687637458, 172050836264264531258995087363702968248917626047934042630528415155132231140508644029599127244879051539267358002191035421289125204823940752365920253806252280135208982388638638499493964850701542139656158750314341254497187842, 171940203480163609379955377980802940579133331691907105899695838468763589198624951628796073230487728578449404061809128906749299219776549427144505908935772797140694656690672598481007142599063775428416387593447970673282632558, 103219291391536095878880034390346953422786271761523298742391169540330754898330394255571346430660715071684164206474477771947648781967064107154643784549798248272157384762664350763722568774041179922240639096353451631378825726, 117056923364128416359225652777713478574064992861948997533153939432247506685002462469811749968546913699301322755483896459497141460002559118995887988073505736811451551865962302723189596066237079194160774624115297268028146222, 75988171484629553691726063948676260814799772175458832559939830959325834682356888352022448666576264219187808584376882565208027267132917947746488916430085062850228779315594314788358632633193395144020398274344181485674509442]
c = [89211588565232244243020044137513332743269967718877480628261718818351757152813010119069284596895225619225592906209397263094049572230279934266154, 105084158613940886109463172309553111555022087987329070889082019479640792410344881505566965101618478019481030407710176448598323171652419554631833, 106157114923928357578300476119375630224120567854699215551331601909290668630663627567930632807187355693727678752488106832973553103202592938942770, 80557564606220145949033391807467833274034216235778526123196512291405199108579104993671137966232164373337992822860664213094236154838829017972325, 39446948431345684527354210960423038896776791694000880147447072994325975700250899240792675465525991887150481970007736257124244137651624443394152, 119520811258897734242352491410708211023486196867717958794495866712623086226488074898297344260921581145340120126196702495352001228111155023751961, 1342770054334431658111079092718547092324646823520496933189758128906340841380811640267019361812318970025491217723403645803306128707939373166022, 117034748679632935974190191234946643889177466547301929478348628684004040210858236619532197365526820452011678286033898345399811113759206056247927, 142937859112056225912918426292604754870431374511209971957972472983061236076109506454150799842170514956334060919400188570742007461222222639963317, 126864447414128885965807626174194404848334608319577370194369994669518133538013998460358715002795480252978924576799926533593892178036375932388876, 22493364980376274642444643759903756666977805851594216444500605030927010663223507136840503959343412921823289896945796358190298587692628276796010, 115905066506480181865265402577373138871074064300913852519921798659037386902047909009848923352447322605148929915853806888695212542107641045508495]

m = 2
p = 156115360763408463288966087959515407156846780488826750491921450156778549686830192729652167507054847091579757631324431846770595853060183819226167
g = 16112732773996424707
q = (p-1) // 2
fac = [2 , 630764016613 , 636284201767 , 666116332547 , 680344318523 , 684825194551 , 719482804681 , 741454555679 , 761339535743 , 864242985583 , 885840248239 , 925948879099 , 1088296917251]
fac = fac[1:]

def my_bsgs(g, Gi, ci):
dic = {}
K = powmod(Gi, 2^20, q)
Ka = K
for a in trange(2^20):
dic[int(powmod(g, Ka, p))] = a
Ka = Ka * K % q
for b in trange(2^20):
T = powmod(ci, invert(powmod(Gi, b, q), q), p)
if(int(T) in dic.keys()):
a = dic[int(T)]
return 2^20*(a+1) + b


#G = GF(q).primitive_element()
G = 2
k = []
for i in range(len(fac)):
Gi = powmod(G, (q-1)//fac[i], q)
k.append(my_bsgs(g, Gi, c[i])) # satisfy Gi^ki = m^(ti*ai) % q

from Crypto.Util.number import *

G = 2
#Gi^ki = m^(ti*ai) % q
mt = []
t = []
for i in range(len(fac)):
Gi = pow(G, (q-1)//fac[i], q)
ki = k[i]
ti = (q - 1) // fac[i]
ai = x[i] // ti
assert isPrime(ai) and len(bin(ai)[2:]) == 300
inv_ai = inverse(ai, q-1)
mti = pow(Gi, ki*inv_ai, q)
mt.append(mti)
t.append(ti)

L = block_matrix(ZZ, [
[1, Matrix(ZZ, t).T]
])
KK = 2^36
L[:,-1:] *= KK
L = L.LLL()


for i in L:
if(i[-1] // KK == 2): # find sum(Ej*kj) = 2
E = i[:-1]
m2 = 1
for j in range(len(E)):
m2 = m2 * pow(int(mt[j]), E[j], q) % q

PR.<x> = PolynomialRing(Zmod(q))
F = x^2 - m2
res = F.roots(multiplicities = False)
for m in res:
print(long_to_bytes(int(m)))
break

#flag{7492b1c4-11e2-057d-5f51-a8456bf4976e}



ez_lcg

题目:

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


class LCG:
def __init__(self, seed, mod, a, b, G):
self.E = EllipticCurve(GF(mod), [a, b])
self.P = self.E.lift_x(Integer(seed))
self.b = self.E(G)

def next(self):
self.P = self.P + self.b
return (self.P[0] >> 116 << 116, self.P[1] >> 116 << 116)


p = 8895377688340484656114290626290544580376870218273346173254798849703394003455887799770221494681754984190581013501915959110063290475132065025943681323111193
a = getRandomRange(1, p)
b = getRandomRange(1, p)
seed = bytes_to_long(flag)
G = [
5508210920919136720319242775455433841168332013885034042922280672339533569135544985350825004642532198374377470981752325297788148514496089158710348250801534,
572911902194073057160579562233150915487979548317278729002100383390561108041874138042107730569768390754004444519587221320050529667583233426501599043114467,
]
lcg = LCG(seed, p, a, b, G)
c = []
for i in range(7):
c.append(lcg.next())

print(c)
# [(6405058374395205743474961564347375685315112086481687321104003788656369408221648243279736155405142482409259124237987640442922868240296056049933435428405248, 2871625802427011624148589027772917206866473797978456532594239812148668319658832708715328618130881261558390697213782357039672373126184712255714162986975232), (2629065438648374720091549917720168451798267355525012252857848812237356617418623949321124100870026908363319910762518597768002182224789880993764151977312256, 4608185293566986369284230246696732631326249160955425076435010708155847827064882194716191158100180159032733888316543569345734466540090185732083774157488128), (8854962001960451436086906141132375848803976856880112493350005580125974686525248462389217457858107191606052049459297773643958456562876888464507427700604928, 2372808279550032464008682727530252720344236637114752537973568269038123793880063675605063848170268821767155603943867381126147299483582270926611727154937856), (458454207790304015351695572624938740633687231437581465438165881037414167765716696130078384733726214319057761995750582404505871813477287191808453264801792, 7196612853040389709785332268916402536934455720628359938403658378209881013632170464260258616559125780014580726540592660319686433208830257252480410319847424), (1542597076807663195559339142297790351770747876802768042386153248982733377442938689443067906888948854728933312334998063280377579830367213783807559636877312, 3982250454412026182885361201070233434451375656941215209712217348866235466147373207930742321027047790565587584866781031938879355787166285738923829659435008), (1875807222180181311347024319262402204276275421087438524139346941285156125962495144522237919840530255577239220497271897199167213333617962725737126168625152, 7551075481132818607565802868415801108204696243253580857501072599757083892151852876114998500046514828407460052751602638677774746412336290708246349890977792), (317179946140537646440818822749723188140959162955604733620411154519919538478364778152541832146445959258299928867648968967466469168777111226415095985733632, 4492010555301799050701061587953721175473298742442636715396498247921741617305586933118382189469954472280616267179692728588074153633559022852633154824437760)]

题目给了一个ECLCG,其递推过程为:

其中G是给定的点,P是未知点,ECC的方程只知道模数p,而不知道a、b,而每次产生的随机数为该次P的坐标的高位:

1
return (self.P[0] >> 116 << 116, self.P[1] >> 116 << 116)

给了我们七组递推产生的随机数,要求还原初始P点,他的横坐标即为flag。

既然涉及到高位泄露那么肯定是要用格没跑了,而关系式也很简单,对于每一次的递推我们记:

那么把点加法公式带入进来就有:

我们要造格求解小量,而p是512bit的,我们带入上面两个式子会发现,x和y的多项式关于未知小量的度分别是3和2,也就是116x3和116x2比特,显然只用y的式子线性化之后解的规模更小,因此步骤就是:

  • 将未知小量代入y的方程中

  • 线性化

    就是把一些非线性的变量做换元处理,比如上式显然会有一些116bit的变量乘积$t_1t_2$之类,做换元$s = t_1t_2$,这就是线性化

  • 造格规约

这样就可以拿到所有小量了,之后就可以解出曲线的参数a、b以及所有点,然后回推初始点P就行。

这一部分其实有论文专门研究过:

Attacking the linear congruential generator on elliptic curves via lattice techniques | Cryptography and Communications (springer.com)

不过其实核心思路也就上面这个部分而已,只是手推一遍最后的等式形式可能会稍微多花点时间,所以我直接对着论文的公式抄了

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

p = 8895377688340484656114290626290544580376870218273346173254798849703394003455887799770221494681754984190581013501915959110063290475132065025943681323111193
G = [
5508210920919136720319242775455433841168332013885034042922280672339533569135544985350825004642532198374377470981752325297788148514496089158710348250801534,
572911902194073057160579562233150915487979548317278729002100383390561108041874138042107730569768390754004444519587221320050529667583233426501599043114467,
]
c = [(6405058374395205743474961564347375685315112086481687321104003788656369408221648243279736155405142482409259124237987640442922868240296056049933435428405248, 2871625802427011624148589027772917206866473797978456532594239812148668319658832708715328618130881261558390697213782357039672373126184712255714162986975232), (2629065438648374720091549917720168451798267355525012252857848812237356617418623949321124100870026908363319910762518597768002182224789880993764151977312256, 4608185293566986369284230246696732631326249160955425076435010708155847827064882194716191158100180159032733888316543569345734466540090185732083774157488128), (8854962001960451436086906141132375848803976856880112493350005580125974686525248462389217457858107191606052049459297773643958456562876888464507427700604928, 2372808279550032464008682727530252720344236637114752537973568269038123793880063675605063848170268821767155603943867381126147299483582270926611727154937856), (458454207790304015351695572624938740633687231437581465438165881037414167765716696130078384733726214319057761995750582404505871813477287191808453264801792, 7196612853040389709785332268916402536934455720628359938403658378209881013632170464260258616559125780014580726540592660319686433208830257252480410319847424), (1542597076807663195559339142297790351770747876802768042386153248982733377442938689443067906888948854728933312334998063280377579830367213783807559636877312, 3982250454412026182885361201070233434451375656941215209712217348866235466147373207930742321027047790565587584866781031938879355787166285738923829659435008), (1875807222180181311347024319262402204276275421087438524139346941285156125962495144522237919840530255577239220497271897199167213333617962725737126168625152, 7551075481132818607565802868415801108204696243253580857501072599757083892151852876114998500046514828407460052751602638677774746412336290708246349890977792), (317179946140537646440818822749723188140959162955604733620411154519919538478364778152541832146445959258299928867648968967466469168777111226415095985733632, 4492010555301799050701061587953721175473298742442636715396498247921741617305586933118382189469954472280616267179692728588074153633559022852633154824437760)]

###################################################################################### solution
xg, yg = G
bits = 116
delta = 2^bits
L = Matrix(ZZ, 2*len(c)+len(c)+len(c)-1, 2*len(c)+len(c)+len(c)-1)

###################################################### Balance
for i in range(2*len(c)):
L[i,i] = delta
for i in range(len(c)-1):
L[2*len(c)+i,2*len(c)+i] = 1
L[3*len(c)-1,3*len(c)-1] = delta^2
for i in range(1,len(c)):
L[-i,-i] = p

###################################################### linearize and make Lattice and LLL
for i in range(1, len(c)):
# "Attacking the linear congruential generator on elliptic curves via lattice techniques"
# -> Linearize
alpha0, alpha1 = c[i-1][0], c[i][0]
beta0, beta1 = c[i-1][1], c[i][1]
B0 = (beta1*alpha0 - xg*beta1 + yg*alpha0 - yg*alpha1 + beta0*alpha1 - xg*beta0) % p
B1 = (-beta1-yg) % p
B2 = (xg - alpha1) % p
B3 = (yg - beta0) % p
B4 = (xg - alpha0) % p
B5 = -1 % p

# poly = (B1*e[i-1] + B2*f[i-1] + B3*e[i] + B4*f[i] + B5*(e[i]*f[i-1] + e[i-1]*f[i]) - B0) % p
# ->
# poly = (B1*e[i-1] + B2*f[i-1] + B3*e[i] + B4*f[i] + B5*ti - B0) % p
Col = 3*len(c)+(i-1)
L[2*(i-1), Col] = B1
L[2*(i-1)+1, Col] = B2
L[2*(i-1)+2, Col] = B3
L[2*(i-1)+3, Col] = B4
L[2*len(c)+(i-1), Col] = B5
L[3*len(c)-1, Col] = -B0

L[:,-(len(c)-1):] *= p
res = L.LLL()[0]
ef = list(map(abs,res[:2*len(c)]))
ef = [i // delta for i in ef]


###################################################### construct ECC
F = []
PR.<a,b> = PolynomialRing(Zmod(p))
for i in range(len(c)):
x,y = c[i][0]+ef[2*i], c[i][1]+ef[2*i+1]
f = y^2 - (x^3 + a*x + b)
F.append(f)
res = Ideal(F).groebner_basis()
a = p - 3425876570823647199579109212659730662509543310380961279501387688733328584808044907584334125251621509152745810876438741593436577386505865180966055459354810
b = p - 7583510358412586447169029101620606211095749993162603080513365204873005095824584631323481059299667822392085633179785036321404516602240076269731225866262128

E = EllipticCurve(Zmod(p), [a,b])
G = E(G)
U0 = E(c[0][0]+ef[0], c[0][1]+ef[1])
flag = long_to_bytes(int((U0 - G).x()))

print(flag)


#flag{f7d59b1c-5b3d-4ea5-b976-e9f00c994c34}