2024-数信杯决赛-wp-crypto

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

trick

题目：

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：

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：

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

题目：

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满足安全素数的形式：

$p = 2q+1$

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$，计算：

$x_i = \frac{q-1}{r_i} \cdot a_i$ $c_i = g^{m^{x_i}} \quad(mod\;p)$

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

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

$t_i = m^{x_i} \quad(mod\;q)$

可以看出有：

$t_i^{r_i} = m^{(\frac{q-1}{r_i} \cdot a_i) \cdot r_i} = m^{a_i \cdot (q-1)} = 1 \quad(mod\;q)$

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

$t_i = g_i^{k_i}$

代回到原式子就有：

$c_i = g^{g_i^{k_i}} \quad(mod\;p)$

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

$k_i = 2^{20}a_i + b_i$ $c_i = g^{g_i^{2^{20}a_i + b_i}} \quad(mod\;p)$

化简就变为：

$c_i = g^{g_i^{2^{20}a_i}\cdot g_i^{b_i}} \quad(mod\;p)$

和RSA类似，求一个解密指数$d_i$满足：

$d_i \cdot g_i^{b_i} = 1 \quad(mod\;q)$

那么就有：

$c_i^{d_i} = g^{g_i^{2^{20}a_i}} \quad(mod\;p)$

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

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

$t_i = m^{x_i} \quad(mod\;q)$

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

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

$\sum{e_ix_i} = gcd(x_1,x_2,...)$

所有$x_i$的公因子为2，那么此时就有：

$\prod{t_i^{e_i}} = \prod{m^{e_ix_i}} = m^2 \quad(mod\;q)$

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

exp：

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

题目：

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，其递推过程为：

$P_{i+1} = P_{i} + G$

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

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

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

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

$R = P_{i+1} \quad , \quad Q = P_{i}$ $R = Q + G$

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

$k = \frac{Q_y-G_y}{Q_x-G_x}$ $R_x = k^2 - Q_x - G_x$ $R_y = Q_y + k(R_x - Q_x)$

我们要造格求解小量，而p是512bit的，我们带入上面两个式子会发现，x和y的多项式关于未知小量的度分别是3和2，也就是116x3和116x2比特t，显然只用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：

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}