文章 - crypto-格密码实战入门(svp问题)

SVP (最短向量问题，Shortest Vector Problem)：最短向量问题(The Shortest Vector Problem,SVP)，而在格学说里两个知名难题中的其中一个，是指在格L中找到一个最短的非零向量，即找到一个最短非零向量。

前面介绍的NTRU算法，我们基本的了解了一下LLL格基规约算法的使用，为了更深入地理解和掌握LLL格基规约算法，以及它在构建格（lattice）中的应用，我们将通过一系列实践题目来加深认识。这些题目旨在引导我们逐步从理论走向实践，从构建格开始，到运用LLL算法进行格基规约，最终解决实际问题。

为了方便理解在这里简单介绍一下有关知识：

LLL格基规约算法

LLL算法（Lenstra-Lenstra-Lovász算法）一种求解最短向量问题的近似算法。它主要用于找到给定格（lattice）中的一组较短且相对正交的基向量。

Hermite定理

这个定理给出了最短向量的上界

对于n维的格L，都有一个非零向量v属于L，满足：

解释一下||v||表示格基的数量积，n为维度，det(L)为格L(矩阵)的行列式

详细的内容这里就不介绍了，如果有兴趣可以看我的那篇NTRU算法，或者上网搜索了解。接下来就是LLL格基规约算法的例题实践

[羊城杯 2022]LRSA

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

m=bytes_to_long(flag)

def getPQ(p,q):
    P=getPrime(2048)
    Q=getPrime(2048)
    t=(p*P-58*P+q)%Q
    assert (isPrime(Q))
    return P,Q,t

B=getRandomNBitInteger(11)
p=getPrime(B)
q=getPrime(B)
n=p*q
e=65537
c=pow(m,e,n)
P,Q,t=getPQ(p,q)

print("B=",B)
print("P*P*Q=",P*P*Q)
print("P*Q*Q=",P*Q*Q)
print("t=",t)
print("c=",c)

# P*P*Q=17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
# P*Q*Q=17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
# B=1023
# t=44
# c=4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746

分析

先用最大公约数求出PQ

#Q= 26068172028162605137516470004551766376185367701690988148920400408760716114172673253571631718337447931195718779018987169967053546674529251665443499183399035216407895285607965767100708187327533611193709308966698251023076404422362272378862918994525181107002728889256377161661579892599243396304207048944032235378667269998644227976609632271355152717352269223310163307304914315780234040829575689991453848537587516055955657960061856059046256125836544109066275645648666876772298883460637600522819402448386193499472702636751025558486665290530268273787746964353937663176851849214999005525738643454160169651485201028944583316101
#P= 25947339118736016261419550658264175914664266822085997909314096786508816404704696671837899420298768803641977765786592354116676036035881712512184992851487828263900367476619650087372125353190561974783134059421570649293920248116730478378196277387377082481961542018611824082110164117796622604412648512092528479878502094797494405077897059911764470830302447618882229233093021156725194893124743848364119720591518073753197359351271987724752861168913839307431377592888760273762302003490303315903644695784992125784390012046834505490167165377346036077504298195544062111718133371983287540723388743607671934081891907851056034062109

然后给我们的等式

根据上面的式子来构造格，先来变形一下：

再用Hermite定理判断一下：

根据题目中给的数据大小的基本信息，显然成立，可以用格基规约算法，

脚本

B=1023
t=44
e=65537
c=4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746
Q= 26068172028162605137516470004551766376185367701690988148920400408760716114172673253571631718337447931195718779018987169967053546674529251665443499183399035216407895285607965767100708187327533611193709308966698251023076404422362272378862918994525181107002728889256377161661579892599243396304207048944032235378667269998644227976609632271355152717352269223310163307304914315780234040829575689991453848537587516055955657960061856059046256125836544109066275645648666876772298883460637600522819402448386193499472702636751025558486665290530268273787746964353937663176851849214999005525738643454160169651485201028944583316101
P= 25947339118736016261419550658264175914664266822085997909314096786508816404704696671837899420298768803641977765786592354116676036035881712512184992851487828263900367476619650087372125353190561974783134059421570649293920248116730478378196277387377082481961542018611824082110164117796622604412648512092528479878502094797494405077897059911764470830302447618882229233093021156725194893124743848364119720591518073753197359351271987724752861168913839307431377592888760273762302003490303315903644695784992125784390012046834505490167165377346036077504298195544062111718133371983287540723388743607671934081891907851056034062109
M = matrix([[1,P], [0,-Q]])
L = M.LLL()
p=abs(L[0][0])+58
q=abs(L[0][1])+t
import libnum
import gmpy2
from Crypto.Util.number import long_to_bytes
from Crypto.Util.number import *

n = p*q
phi_n =(p-1)*(q-1)
d=gmpy2.gcd(e,phi_n)
d = gmpy2.invert(e, phi_n)
m = gmpy2.powmod(c, d, n)
flag = long_to_bytes(m)
print(flag)
#b'DASCTF{8f3djoj9wedj2_dkc903cwckckdk}'

第二届黄河流域网络安全技能挑战baby_math

print(sin(__import__('libnum').s2n(flag)).n(1024))
#-0.5763216138185318403737346358040179184476364123728865572799211128243702354488581188939012847259223762780574285919778334891033655170438095281317540535577851035632940469300832811280408518388896020483094512571194149462558073200869265861278472233179527377781153969581392345206909655605217731481771369571884721388

分析

先分析一下这道题，首先将flag转成数字，再取三角函数精确到小数点后1024bit位。这道题目虽然表面简洁，但也因此条件比较少，所以我们就用这为数不多的条件来进行构造。

有了这个多项式我们就能开始构造格了：

然后开始平衡参数：

我们先估计一下

flag一般30~40位，我们就以较大的40为为标准，m约等于2^320,所以det(L)就需要大于2^320，而这里所求向量中正好为0，所以我们可以将格调整为：

但是如果这样去接的话，肯定是解不出来的，因为flag的具体情况不知道，需要我们去在通过脚本去调整参数,试了一下大概要2^683就能出我们要的解过来

脚本

from Crypto.Util.number import long_to_bytes

tmp = -0.5763216138185318403737346358040179184476364123728865572799211128243702354488581188939012847259223762780574285919778334891033655170438095281317540535577851035632940469300832811280408518388896020483094512571194149462558073200869265861278472233179527377781153969581392345206909655605217731481771369571884721388

asin = arcsin(tmp)
RR = RealField(1024)
pi = RR(pi)#使pi更加精确

L = Matrix(QQ,[[1,0,2^683],[0,2^320,2^683*asin],[0,0,2^683*2*pi]])
m = abs(L.LLL()[0][0])
print(long_to_bytes(int(m)))
# flag{b0a8c4f1-c343-40f7-86f8-4f3b9a5cc249}

[MTCTF 2021 final]ezRSA

from Crypto.Util.number import *

flag = open('flag.txt', 'rb').read()
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
e = 65537
n = p * q
c = pow(m, e, n)

s = getPrime(256)
M = getPrime(5048)
hint = (p - 297498275426) * inverse(s, M) % M
t = open("message.txt", "w")
t.write(f"e = {e}\nc = {c}\nn = {n}\nM = {M}\nhint = {hint}\n")
t.close()
'''
e = 65537
c = 11223534598141520071392544441952727165225232358333005778273904279807651365082135278999006409297342081157139972503703772556228315654837441044781410960887536342197257046095815516053582104516752168718754752274252871063410625756822861003235434929734796245933907621657696650609132419469456238860601166224944487116
n = 99499509473364452726944770421623721217675378717234178828554602484867641740497277374806036356486848621495917213623425604565104435195783450029879177770305417469850119739921527698744700219067563802483159458398895082044997907953256062342593605652927874232404778144112740505724215742062859322375891810785229735653
M = 28858066896535909755146975040720031655813099454455588895434479778600245612915775220883088811806723015938061791264869678085304248608125313205719043320256733514389739252845381708094678596099621503299764646358765107958130065721737938646850422959290465490270263553423913213684958592738500488797707239673645370968467090153285601432966586133693641854092761919184904521240074718850103356119966387029699913571443658384564840234765103070736676067458391659605655580766436276719610283460962533141261830775028138998594269732067550977245136631815804641115446066102981044849495663224005844657686979516481904043008222498344271373989609634617315702887646444506965035406154183377067490922195507071571055579654138590566650703038341939225657159668601565182939447340585110418258653618384852356058444795156595720943362884361136229430356254095673818462046182310826133487611183265532844700265640889105864909560170846171486510513240630480729194415061752698286990999064594811803482429976978688266632277914610443963726561921790718480343488391563503774868490108659902216386976683532579945706490286814310031310144410303859633785939399012605326754445715302492704458881700872467560968264583996658711892595658439058034434031646411995511168849724976850557976639662545139917517675296224197763447929417263845949813741362574641118781293171167041592771305352186419565096347024619027397784780864922205105185970180629777320680707022011697404359388540366320053501502698747763307336114482530784826238326983596966436776918503653153420281803168537703048371580451
hint = 24302462761412867722556483860201357169283131384498485449193507018526006760633350601593235386242712333885826513399701577522498685938541691414316724804357523659514319083860507720945068584985970098437482386854188516742033184163273293005356970701527614010961471490166306765208284126815267752826036846338185010168551115391901008731195800723630612524215610302192763771954146943262822909368086155537366851998954401585888789660061750804720858175620022924944428882337005545535959410243692854073069775794945154943244522898330286785483043492678802461244624116832548150221211726044545331789932659966539042635768789637635754297830131948383991027466194455817875377950516103513735000718642093769229006510961952865719649517629939801014585849419818774317178973918720330390674833583065434312010539617630210110724391629534996688713945139529416075521015600392479980677759342058040778532467875961508475990300178277703011765698425360329342396347848373844031930655143343217447877587074485794273364964346235973542157189093330870952677683308479410235841331914353677363106473914986073397716367455628483060709281215783434084559550690248426391913205234184130354155776334292729262232484610747771114078013979494659835579574006801652858265173309736540235377076956677464263798132149783780830729103485354096234062135454873557941791812722418582207577124971978987895472250326100927372068822672582017222521124179752698654114839303426099426224351872025466618402675104161895600513776962289703455252021742990686505176582638132300246212598903123706906104217087
'''

分析

我们分析一下题目可以知道，题目的主要问题是：

hint = (p - 297498275426) * inverse(s, M) % M

根据这段代码开始，构造格进行LLL算法：

hint = (p - 297498275426) * inverse(s, M) % M
hint*s=(p - 297498275426) % M
hint*s=(p - 297498275426) +kM
(p - 297498275426)= kM-hint*s

于是构建格：

再看Hermite定理是否满足：

M是一个非常巨大的数字显然是符合的，然后就是通过LLL算法解出p就可以了

脚本

from Crypto.Util.number import *
import gmpy2
M = 28858066896535909755146975040720031655813099454455588895434479778600245612915775220883088811806723015938061791264869678085304248608125313205719043320256733514389739252845381708094678596099621503299764646358765107958130065721737938646850422959290465490270263553423913213684958592738500488797707239673645370968467090153285601432966586133693641854092761919184904521240074718850103356119966387029699913571443658384564840234765103070736676067458391659605655580766436276719610283460962533141261830775028138998594269732067550977245136631815804641115446066102981044849495663224005844657686979516481904043008222498344271373989609634617315702887646444506965035406154183377067490922195507071571055579654138590566650703038341939225657159668601565182939447340585110418258653618384852356058444795156595720943362884361136229430356254095673818462046182310826133487611183265532844700265640889105864909560170846171486510513240630480729194415061752698286990999064594811803482429976978688266632277914610443963726561921790718480343488391563503774868490108659902216386976683532579945706490286814310031310144410303859633785939399012605326754445715302492704458881700872467560968264583996658711892595658439058034434031646411995511168849724976850557976639662545139917517675296224197763447929417263845949813741362574641118781293171167041592771305352186419565096347024619027397784780864922205105185970180629777320680707022011697404359388540366320053501502698747763307336114482530784826238326983596966436776918503653153420281803168537703048371580451
hint = 24302462761412867722556483860201357169283131384498485449193507018526006760633350601593235386242712333885826513399701577522498685938541691414316724804357523659514319083860507720945068584985970098437482386854188516742033184163273293005356970701527614010961471490166306765208284126815267752826036846338185010168551115391901008731195800723630612524215610302192763771954146943262822909368086155537366851998954401585888789660061750804720858175620022924944428882337005545535959410243692854073069775794945154943244522898330286785483043492678802461244624116832548150221211726044545331789932659966539042635768789637635754297830131948383991027466194455817875377950516103513735000718642093769229006510961952865719649517629939801014585849419818774317178973918720330390674833583065434312010539617630210110724391629534996688713945139529416075521015600392479980677759342058040778532467875961508475990300178277703011765698425360329342396347848373844031930655143343217447877587074485794273364964346235973542157189093330870952677683308479410235841331914353677363106473914986073397716367455628483060709281215783434084559550690248426391913205234184130354155776334292729262232484610747771114078013979494659835579574006801652858265173309736540235377076956677464263798132149783780830729103485354096234062135454873557941791812722418582207577124971978987895472250326100927372068822672582017222521124179752698654114839303426099426224351872025466618402675104161895600513776962289703455252021742990686505176582638132300246212598903123706906104217087


M = matrix([[1, hint], [0, M]])
L = M.LLL()


shortest_vector = L[0]
if shortest_vector < 0:
    shortest_vector = -shortest_vector


s, p = shortest_vector
p=p+297498275426
q=n//p

phi_n =(p-1)*(q-1)
d = gmpy2.invert(e, phi_n)
m = gmpy2.powmod(c, d, n)
flag = long_to_bytes(m)
print(flag)
#b'flag{388bb794-ccda-f02e-79c6-8e44659c2481}'

Lattice1

from Crypto.Util.number import *
import random

flag = b'******'
m = bytes_to_long(flag)

a = getPrime(1024)
b = getPrime(1536)

p = getPrime(512)
q = getPrime(512)
r = random.randint(2**14, 2**15)
assert ((p-r) * a + q) % b < 50

c = pow(m, 65537, p*q)

print(f'c = {c}')
print(f'a = {a}')
print(f'b = {b}')
'''
c = 78168998533427639204842155877581577797354503479929547596593341570371249960925614073689003464816147666662937166442652068942931518685068382940712171137636333670133426565340852055387100597883633466292241406019919037053324433086548680586265243208526469135810446004349904985765547633536396188822210185259239807712
a = 134812492661960841508904741709490501744478747431860442812349873283670029478557996515894514952323891966807395438595833662645026902457124893765483848187664404810892289353889878515048084718565523356944401254704006179297186883488636493997227870769852726117603572452948662628907410024781493099700499334357552050587
b = 1522865915656883867403482317171460381324798227298365523650851184567802496240011768078593938858595296724393891397782658816647243489780661999411811900439319821784266117539188498407648397194849631941074737391852399318951669593881907935220986282638388656503090963153968254244131928887025800088609341714974103921219202972691321661198135553928411002184780139571149772037283749086504201758438589417378336940732926352806256093865255824803202598635567105242590697162972609
'''

分析

((p-r) * a + q) % b < 50

这次我们从这个式子入手可以变化为：

((p-r) * a + q) % b = x
 (p-r) * a +kb = x-q

用上面的式子构建格：

但这里我们知道没有确定x,r的值需要我们去遍历一下x,r的值

b = getPrime(1536)
p = getPrime(512)
q = getPrime(512)

从这里可以知道，Hermite定理成立可以使用LLL算法

脚本

from Crypto.Util.number import *

a = 134812492661960841508904741709490501744478747431860442812349873283670029478557996515894514952323891966807395438595833662645026902457124893765483848187664404810892289353889878515048084718565523356944401254704006179297186883488636493997227870769852726117603572452948662628907410024781493099700499334357552050587
b = 1522865915656883867403482317171460381324798227298365523650851184567802496240011768078593938858595296724393891397782658816647243489780661999411811900439319821784266117539188498407648397194849631941074737391852399318951669593881907935220986282638388656503090963153968254244131928887025800088609341714974103921219202972691321661198135553928411002184780139571149772037283749086504201758438589417378336940732926352806256093865255824803202598635567105242590697162972609


L = Matrix(ZZ, [[1, a],
                [0, b]])

p, q = map(abs, L.LLL()[0])
print('p=',p)
print('q=',q)
#p= 11296178014269303494837745604378279247866909144617752153545368028888626096702713262852534563523632474606208277782361536096982136624743993713145172222722488
#q= 7624362591338746517094639431704851643734620831459014789016367356254899957320105688627749759067762076121643496058348997115185171145960008965900436924472153

然后就是遍历x和r了：

import gmpy2
from Crypto.Util.number import *
from math import *
from tqdm import *
c = 78168998533427639204842155877581577797354503479929547596593341570371249960925614073689003464816147666662937166442652068942931518685068382940712171137636333670133426565340852055387100597883633466292241406019919037053324433086548680586265243208526469135810446004349904985765547633536396188822210185259239807712
p= 11296178014269303494837745604378279247866909144617752153545368028888626096702713262852534563523632474606208277782361536096982136624743993713145172222722488
q= 7624362591338746517094639431704851643734620831459014789016367356254899957320105688627749759067762076121643496058348997115185171145960008965900436924472153
e=65537

for r in trange(2**14, 2**15):
    for x in range(50):
        P = p + r
        Q = q + x
        phi = (P - 1)*(Q - 1)
        if gcd(phi, e) != 1:
            continue
        d = inverse_mod(e, phi)
        m = power_mod(c, d, P*Q)
        if b'NSSCTF' in long_to_bytes(int(m)):
            print(long_to_bytes(int(m)))
            break
#NSSCTF{0fc9dee6-ebfb-40bd-b800-b3ebe440be70}

总结

通过前面几道实践题目，我们深入探索和实践了LLL格基规约算法。这些题目的解决过程不仅强化了我们的理论知识，更重要的是，提升了我们将算法应用于实际问题的能力。现在，让我们来总结一下解决这类问题的关键步骤及其重要性。

1. 构建多项式

在解题的初始阶段，构建合适的多项式是至关重要的。这一步通常需要我们对问题进行深入的分析，明确问题的目标和约束条件。多项式的构建直接影响到后续格的构建和规约过程，因此，我们必须确保所构建的多项式能够准确地反映问题的本质。

2. 构建格

构建格是LLL算法应用中的核心步骤之一。在这一步，我们需要根据前面构建的多项式来定义格的结构。格的构建需要考虑到问题的具体情况，确保所构建的格能够有效地表示问题的解空间。一个合适的格能够大大提高我们找到问题解的效率。

3. 判断Hermite定理是否成立

在构建完格之后，我们需要判断Hermite定理是否成立。Hermite定理为我们提供了一个判断格基是否规约的标准。如果定理不成立，我们就需要调整参数，直到找到一个满足Hermite定理的格基。这一过程可能需要多次迭代和调整，但它确保了我们最终得到的格基是规约的，从而提高了找到最短向量或近似最短向量的准确性。

4. 对得到的解进行筛选

最后，当我们通过LLL算法找到一组解时，可能需要对这些解进行筛选。特别是在存在多个解的情况下，我们需要根据问题的具体要求来选择最合适的解。筛选过程可能涉及到对解的性质、长度或其他特征的评估，以确保我们最终选择的解是符合问题需求的。

总的来说，这些实践题目确实属于入门级别，但它们为我们提供了一个机会来熟悉和实践LLL算法。正如一个刚开始学习RSA的人不一定能立即解决所有RSA相关问题一样，我们通过这些实践题目逐步深入理解和掌握LLL算法。通过这些题目的锻炼，我们不仅提升了运用算法解决实际问题的能力，还为将来解决更复杂的问题打下了坚实的基础。