首页 writeup

Shallow yyds !!! 被shallow讲的直接就一下就出来了太棒了!emmm我太菜了...阅读能力真弱...

# Strange_GCD :

题目描述上讲了 Approximate GCD Problem . Reffered on https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/.

这种 AGCD 问题对于解题主要是一种 LWE 的思想去做题.... 我一开始查到也是大概就是 LWE 的思想，但是自己造格子造不出来，就没做了..emm 接下来开始分析一下题目 p 444 位，q 666 位，r 333 位

Ni=qi⋅p+riN_i=q_i·p+r_i

可以知道他给的所有 Ni 都是掺杂着 扰动东西 ri ，我们可以得知这确实很像 LWE 的内容。但是格子该怎么去造呢？继续看

N0=q0⋅p+r0,N1=q1⋅p+r1N_0=q_0·p+r_0,N_1=q_1·p+r_1

可以得到

p∣gcd((N0−r0),(N1−r1))p|gcd((N_0-r_0),(N_1-r_1))

同时我们知道 如果

a∣ba|b

或者

a∣ca|c

于是我们

a∣b⋅c,a∣(b⋅c)modaa|b·c, a|(b·c)\mod a

我们就可以计算

gcd⁡(N0′,Πi=02λ−1(N1−i)modN0′)\gcd(N_0',\Pi^{2^\lambda-1}_{i=0}(N_1-i)\mod N_0')

并且 ri≈2λr_i≈2^\lambda​​

并且 N0=q0p,N1=q1pN_0=q_0p,N_1=q_1p ​ , 所以 q0N1−q1N0=q0(q1p+r1)−q1(q0p+r2)=q0r1−q1r0q_0N_1-q_1N_0=q_0(q_1p+r_1)-q_1(q_0p+r_2)=q_0r_1-q_1r_0​ 就使用这条我们就可以去构造一个向量 q=(q0,q1,...,q8)q=(q_0,q_1,...,q_8)​ 以及一个格子

L=[2λ+1N1N2...N8−N0−N0...−N0]L =\left[\begin{matrix}2^{\lambda+1}&N_1&N_2&...&N_8\\\\ &-N_{0}\\\\ &&-N_{0}\\\\ &&&...\\\\ &&&&-N_{0} \end{matrix}\right]

于是得到的目标向量 TV=(q0,q1,...,q8)⋅L=(q0⋅2λ+1,q0N1−q1N0,...,q0N8−q8N0)TV=(q_0,q_1,...,q_8)·L=(q_0·2^{\lambda+1},q_0N_1-q_1N_0,...,q_0N_8-q_8N_0) 接着我们对这个向量进行观察，q0,q1,...,qnq_0,q_1,...,q_n 都出来了，同时 r 是 333 位的 我们如果 N 整除了 q 得到的就刚好是 p , 检验一下 成立 ，那么我们就可以去解密了。

exp:

from Crypto.Util.number import inverse, isPrime, long_to_bytes
from gmpy2 import*
N = [8321077117329356263954581766837194016859681833859374146551469738742553789565498761528408178000096341991081753628879035591190841107228873036782248755852096597317053559269854941020999105514186022112075838112491499884564745335454966665835001848999256218403570429047541524272647861099813598603292295695775504244505874838019009730562620216, 9663141503982563384103774905603769762205667685102275298721284964403449121449261483138514307090449027807047697811539118959328065885920230514670112839967221129701708335087378871176539521374006686377418843364889059913595942583737991465545688834167085579154677350865488342245644093471665857007588133415608450554035129609049971856915687905, 7080633525505006454857949889380886258474613936169915325357991912983821798902257837234148311383635716165386646093418183743215120431715933036921480432793786600194625124412063608565640368381660643929081066605712749838630092722581230189543696229548387666046034403406721477818265752443487173947232032487026509033018565048660685068628813900, 6348260112940191945095264085450804431350547836448100928568733296493334845533262312663784701113046746633754397388581143523779371919889446537883618910341310362947454041409541741124231406605654693961025815677260091930522280737378333554694234586235628097018111636491016261274584391201625445101930372416766825601778759258114504767453644116, 5453076441876067965962987075376616480678826248967242473452690159966124023105342358461519279607336831463834252487811766366887983597918775466645199024629945952612311092154451713992362747056489054444283302530500475646346968235522866557033556131387030809018889094871163097069588840212411234716020934787724757538389436231926479459435139729, 8539092301764573132139384894241535432591998166686651428176862041680365196821019488767353225937458669267710968146783359781905669306801237140282934737328995064410005908343087032652676207615356474601039341695241288937409773110450995503958663731870314493254162942656333393836208952363635746218345484752702086447693272390570444229475023063, 6519174659211289290465989985638494640591837577268694359892571134942820094011179335155100770258746122812579164176239810640710311061280175847537113068566174335469669480601670136633042879486860594176408555229541384726863069317134887988109513500264430505092783429319336134768414472691544453196941818593187717904852926051114502346647888426, 6961711680362025924587083752271982856615461409839316941574792747717174299272141804413488210456939607971950020060573061131683587521057101549266612028332060247289306929784809695126285828514889617483817766102136513569391338432827451306976412448973958662677599051104723480081915666230391091496248279567627159875132838397868850500912784991, 5464727156582411007360377345208743900616053705663005668786499961992377236151787056734059201141143278419642045996194426551642956434137382420547801325331080754615348522599387497424727626522195285281557448617564720973185851757117201639221059630112719699600469361046245232476531622290326229811709079901764559526124144866364301870192468062]
M = N[:]
M[0] = 2**334
'''
L = Matrix(ZZ,[
    M,
    [0,N[0],0,0,0,0,0,0,0],
    [0,0,N[0],0,0,0,0,0,0],
    [0,0,0,N[0],0,0,0,0,0],
    [0,0,0,0,N[0],0,0,0,0],
    [0,0,0,0,0,N[0],0,0,0],
    [0,0,0,0,0,0,N[0],0,0],
    [0,0,0,0,0,0,0,N[0],0],
    [0,0,0,0,0,0,0,0,N[0]],
])
P=L.LLL()[0]
'''
e = 0x1337
P = (9198383558649454145266329742592651804417531074705208606546350510907008625231001966812954022871638810611704119348096876032201336180492815698993817487634671245603146146272244377218492738092114522582641697639688837841786461196752729903611725131373737251243910142850547018441698749894323950503164083437568, 104098035638581595369723778375711537486830709046687306114704921816239533823901066113680320504395210089789340199402154288158599251547931748565815387310900885326892681968536308019715590493310968628489043723240348362149053110811668282038727688689374505928586075094912392544924601844136642390813222425809, 1102834391862716869946827309486981604079530638763397950737361315055931768373793498250981455412829162997772327814660070857951309312894092377859437366989526531813223828179941289064128320123411973263239142716310770401174174815638810202859450962632995611863799694649198457635953086959463939627719575381012, 753994729336183961852361196205654448289304004519434287316796470222521627865083763102251102951626213588497716067551706990220346381353586508856365765536744873026409087910505560761761024675350156647185336440841519838638415417607956807382719719007131540587566462617043290548957627028678429439567176392108, -71708524916293121808333775279085691365967960919759775147913431698619192878017855212957980666806523648996086462040461850162074426038300683815953081712090679643498963889027587516137252350693864785830427057530016147319149926968346502476418390469709928547235995568090970863872980806983047965126211827423, -1031944069356990593465028628753183012193322903943969718261363844383250576817774501764794204795605186147444430878687291921605373814843580367545369212301939780213941922732623750390324618190490307261983930269957183493345355165692496865409582827167136484989492550271511982793001065621702409883049993239817, -1960547215826715829528682564527292643865866291188443591530567078511330848396016229325567425830200701694380104625201031396661972809519249893882531604307311435727272867042265335921514343841646164420771255718802644103398765492144311189111408831887333483581772033575516358581006829893858562536866631199694, -1402335387560657499009395932180425308829816453818907356038567333645529829409747360872073366794556975860774421104509218449157997408918101385420918273310166387609041772539330599075043569860214109051067579537008367501834723009929827486300772678346407596106869832512579102180928086682172345775047825906065, 6492859743402427013224957526773612476031280993044690607784160057686880229209831538939045987606076773313125546427811186808795218860181360435151657439459135171731642225975056613348164819235317913083153227881911185574679170305638348499347070097938480392885289493284095645409615468925393679398090634630)
C = [800378461059400239726680783421062702546581299113618553895453491207714321944554499622887232532612118204284779120928524046451494597619154079853122057618867592408424421335915888671560524092660578952242621890439766919785431411789789232309134048322721650012432166587969915464252995890054635969469155870141839815222805619769926841873928532, 8685468246369062574820183134847029157229023858170863526469628501966638181721681547114662091162797572149161013458000532984909663639626346493828947027439012131912176125653717020650233650230608573276523862941298063827867869000918623143520066067119099918633173584693454642685133071154989133688921507896223776765538029556643440655490373815, 4635611296372235589362291842711945807825964919968727011796279830725567747087132786100965922682161492876463568645940638975728831156672106717718242995621775763972524561170035488180440169190421072680121175269363490806991700969253196228364471655905426168859215651384013432550900570720981720919343406680667172355882395426739478340888619526, 742099161415136628218807400531862454374875770332166710320711769923774839345990297388615457974047093967700994503615622499139058644697776431451063778211507061619987487339659448529973693084099004007650792690143707738139278995489030445825999666762580518420739517354868021396496747289677543653758101688499365196709600349831855157276274803, 4273006447766599851029197343910625305964779588947130545729882009677080459892767902139074897266046998378948193319329776150920821074305998905666368175737032487336505440974393061632257356697260043478850055918798196360043557336723402834256592984312957607731622934368169520289756716653736422872196593367101920308166527352079412344590114695, 1337615323422531101514598853478737615483725265103339849469231329210692205474781484172946466402355800190175297435923447189337380569240535257395618353403524999296122247241720498058900285176383928871155893061316083476812641934026019749574784965397208046520128690081232283708190247657782663414534596381371506499151016470118707739609022847, 6153442337491399463730666360630451953223069596225489087488144486112604050064388945200405772892415725900338512969888610774357818442533883395713661512978158729825590405567077341407532331228257558692149544940358814513930330757334104407683768945074261746314376336567331685071086776886141587264981001140113933152084084711732651014186070962, 3604640305526232611907645024550062043296875756707299105733076926046725900367109300556792007038226350415916164581084668832286944703572581980333135146219609212135443758296278947833224676930513359604019639508959092586550129343133801670578311053639151186604019506764426302411065588655525183584977810609190948096510237056027272167828516985, 2085633143403792178757363870459578017278494765962824809917819295576034993395441252397370078671500834434293581806342828037037877739374959864038090394888141183851040814572501861997433316552606005140700519616064369570511427453278726929921212633252656552135711332324923683242632912449218888750151556281762432994484741408165895663710356342]
p0 = 9198383558649454145266329742592651804417531074705208606546350510907008625231001966812954022871638810611704119348096876032201336180492815698993817487634671245603146146272244377218492738092114522582641697639688837841786461196752729903611725131373737251243910142850547018441698749894323950503164083437568//(2**334)
Q = [p0]
for i in range(1,9):
    Q.append(-(P[i]-p0*N[i])//N[0])
P = []
for i in range(len(Q)):
    P.append(N[i]//Q[i])
D = []
flag = b''
for i in range(len(Q)):
    D.append(inverse(e,(P[i]-1)*(Q[i]-1)))
    flag = flag + long_to_bytes(pow(C[i],D[i],P[i]*Q[i]))[-5:]
print(flag)
# nomore:
这道题主要就是 python3 中 y+1/x 能实现 那必然是整除，python2 中 “/” 就是整除 好家伙... 并且 k 也得小才能去爆破出来解 同时 x 也给了个上界。
(y+1)/x=>y=kx−1(y+1)/x=>y=kx-1 ，带入式子 A (x−1)7+(kx−1)5+k(x-1)^7+(kx-1)^5+k 发现他是单调递增的，我们就可以去二分法求得 x ，但是 我们得知道 k 是一个小的数 ，那么就二分法去爆破 k , x ，于是就得到了 x , y , 带入 secret 中得到 secret。我们再看看 secret 以及 secret 的大小，发现是奇数，那么 e 也是奇数，开个三次根，发现也不是很大，但是是在 190w 左右 ，并没有题目中给出那么大的界，就直接去爆破 e , p , q 其中使用一种中间相遇的思想 secret−e3−p3secret-e^3-p^3 仍然是个三次的数，就可以直接出来了。
exp :
from Crypto.Util.number import*
from gmpy2 import*
def bruteforce(secret,primes):
    for e in range(9001,10000,2):
        for p in primes:
            if iroot(secret-(e**3)-(p**3),3)[1]==0:
                continue
            else:
                return (e,p,iroot(secret-(e**3)-(p**3),3)[0])
A  = 2235930885430590738951770802593215586722001521194365487273377655750584443688709547709496531484159367793509666612116139038917661713102981488722293426038029073850795986080412124312908732573382156365974821471629333126275130148211145598662897276781331183691743094904957217401055325352877284530068805608962270139656431076370452327497416723045785664344412694060886085511378779487559306015113302658964110922621164879307182468690182325142055960562810349297544601157473985262796723316777380726315782859115449976700612343978057140270903396910431420116573138154719798955123904805279320166126412714788508008881174164656203605409187705643395043643983135944514470267283183175620492198093264226038082725867230101096344723124629565311122528005863046865164876192248803940590219355154176343702897505891392317123983475290611327887699795851456183931854177169939743970260837586185988111368384484356413787993370384262996486824251003884057486063787194241555190688935624792041028246639984544749568167915235629185515957106136630401960066317998226671344793061752525215496195839080165952892472180997564802474095868944184005854120238623750555477937802107959321257495435617363809377093354132077991399603767147974592666019334636208414969819333321639542282741932229892501074615920120228860717401055433206357806353717291748096464569063777964784860874773660469621546777686833078007220613545223169043960754010332944526795605043595879174073360317477199909570141202125189377475655277483919081658123820105695508771837612756891055031293872293977244105248233915807603916034288916844336329883443200123825714530812637709561686224468031953278836676202928878535091578725509651544544672494980806630321114490828976895602038151224026672265830787863940762596976124958000977955469148027648603199590311852993367450800166591526272653355552342455506908317529193196174849749103073968182002498580115241030154502931088245539152380579199202750010140022979979488971008874424439325749039212427088023136971891092490697689178097172878439007028844083681030357488034860471042630885195387680286557424780235116405464735985082715745087677866688657626763753940919966662710093619034074861812080778855241391731006
for k  in range(100):
    r = 4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
    l = 0
    for i in range(1021):
        x = (r+l)//2
        v = (x -1)**7+(k*x-1)**5+k
        if (v == A):
            print(x)
            print(k)
        if (v < A):
            l = x
        else:
            r = x
x = 3009497962071627970325880719364587885671010480057866287334251735956364570350347087026477982283392009667042015682364869764534877202626872343001563490279098970253786309533656152965171286503259912849977668331206169132653702870703716072003169079329188859516303445545911170476352380900189590650131003576924340724
c = 693282726315
k = 84
y = k*x-1
secret = (x + y) % 7754486886526049041 + 210729175671163973
jie = iroot(secret,3)[0]
primes = []
for i in range(1000001,jie,2):
    if isPrime(i) == 1:
        primes.append(i)
print("done")
e,p,q=bruteforce(secret,primes)
c = 693282726315
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(b'MRCTF{'+long_to_bytes(pow(c,d,n))+b'}')
# Common_Prime_RSA
这道题 emmm..... 从多元 Copper -> BSGS 解题思维.... 真尼玛放缩题... 如同浙江高考数学最后一题导数放缩？(xs Reffered on https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.1333&rep=rep1&type=pdf
先分析题目，给出了一个 明文 +g1 + 明文 段的内容，我们可以想到 CopperSmith 的解法。只要换成了首一多项式 在 sage 里跑就可以得到了
n = 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49
e = 3
c = 0x27d8d7249643668ffc115be8b61775c60596e51f6313b47ad5af8493526922f5e10026a2cdaef74e22c3eec959dd8771abe3495b18d19f97623f5a3f65f22ff8fc294fc37ceb3b43ebbbf8a9bcf622922e22c5520dbd523483b9dc54fdffcd1a1b3f02ca1f53b75413fb79399ca00034f2acf108ac9a01bd24d2b9df6e27d156
m_low = 12174832913272944860601983973507591320681689815583717341813397700955082069528318044500277669230782878838402371536356670567072055281703856945#464 位
m_high = 43068805484541415698874685945122116488177521029738607414688723817811466178438704211475601610458271809578314787221337437676782823427096603325480109722746064453605749460332117411578252753615112132108843194498669812000013922027642492460715110657531599266817556380763143511900612854154688377602965504
PR.<x> = PolynomialRing(Zmod(n))
f = (m_low+m_high+x*2**464)^e - c
f = f.monic() 
g1 = f.small_roots(X=2**232,beta=0.4,epsilon=0.04)[0]
在观察这道题目，已知 g1 , 但是要求我们去求 a 和 b ，才能够求得 n1 的因子 emmm 这道题 考点就在这了... 看上面参考的那篇论文 我们设 beta=2g1 , s =(n-1)//beta ，那么我们可以推导 s=beta∗x∗y+x+y,=beta∗u+v;∵x+y>beta∴v=x+y−beta∗c,u=xy+cs=beta*x*y+x+y,=beta*u+v;\\\\∵x+y>beta∴v=x+y-beta*c,u=xy+c
我们只要得到 c 是多少就能够得到 x 和 y 分别是多少了
通过 v 去变换得到 c=(x+y−v)/betac=(x+y-v)/beta ，观察这个式子我们发现: beta 和 v 都已经知道了，那么接下去我们看 u=xy+cu=xy+c , 并且题目中给出了 p<2q,q<2pp<2q,q<2p 则可以得到 x<2y,y<2xx<2y,y<2x 那么接下去，我们可以知道 xy≈Nbeta2xy≈\frac{N}{beta^2} 发现这是个对勾函数 ， 接下去我们就可以发现他的大概范围中 x,y∈(N2beta2,2Nbeta)x,y\in(\sqrt{\frac{N}{2beta^2}},\sqrt{\frac{2N}{beta}}) ，同时 关于对勾函数的性质 我们可以知道 x+y∈(2Nbeta,3N2beta)x+y\in(\frac{2\sqrt{N}}{beta},\frac{3\sqrt{N}}{2beta}) ，于是我们就得到了 c 的大概界 为
c∈(2Nbeta−vbeta,32N2beta−vbeta)c\in(\frac{\frac{2\sqrt{N}}{beta}-v}{beta},\frac{\frac{3\sqrt{2N}}{2beta}-v}{beta})
接下去得到 c 的界为：
g1 = 1328458990599515056771144217738449144496664370133586446617480019409757
n = 0x48b11209b62c5bc580d00fc94886272b92814ce35fcd265b2915c6917a299bc54c2c0603c41f8bf7c8f6f2a545eb03d38f99ec995bf6658bb1a2d23056ee21c7230caa2decec688ea9ee00b0d50b39e8cd23eb2c3ddeb20f5ab26777b80052c171f47b716e72f6aee9cece92776fc65119046f9a1ad92c40e2094d7ed7526d49
beta = 2*g1
s = (n-1)//beta
u = s//beta
v = s% beta
left = (2*int(sqrt(n))//beta-2-v)//beta
right = (3*int(sqrt(2)*sqrt(n))//(2*beta) - 2 - v )//beta
print(left)
print(right)
print(right-left)
print(iroot(right-left,2))
因此 D=iroot(right−left,2)[0]+1D=iroot(right-left,2)[0]+1 用 BSGS 方式 爆破得到 i=5980588,k=698170i=5980588,k=698170 , c=left+kD+ic=left+kD+i
D = iroot(right - left , 2)[0] + 1
b = pow(2 , beta, n)
dic = {}
base = pow(b , left , n)
diff = pow(b , D , n)
for i in range(D+1):
    temp = base & 0xfffffffffff
    if temp in dic:
        print(i)
    dic[temp] = i
    base *= diff 
    base %= n
print('baby step done')
base = pow(b , u , n)
diff = invert(b , n)
for i in range(D + 1):
    temp = base & 0xfffffffffff
    if temp in dic:
        print(i , dic[temp])
    base *= diff
    base %= n
#5980588 698170
那么就可以得到 x,y 于是得到 p,q
xy = u - c
x_y = v + c * beta
temp = iroot(x_y**2 - 4 * xy , 2)[0]
x = (x_y +temp) // 2
y = (x_y - temp) //2
p = x * beta + 1
q = y * beta + 1
后面直接用解，并且知道 后面是 0.3247，同时而且能看到了他是整除之后可以直接得到这些东西。
c = 0xeaf06b9050a809659f962251b14d6b93009a7010f0e8d8f0fa4d71591757e98243b8ff50ec98a4e140fd8a63bbb4b8bb0a6d302a48845b8b09d1e40874fcb586ddccbb0bbf86d21540ec6c15c1d2bf925942f6f384fdc1baae7f8e06150ccd9459eb65d0f07eea16a911fa0a17e876a145dbfec83537ca2bee4641897b9f7f5
e = 65537
phi = (p-1)*(q-1)
g2 = pow(c , invert(e , phi) , p*q)
n2 = 0x6d457110d6044472d786936acbd3cd93c7728daa3343b35ccaa5c55eba6b35c28c831bb245b8cdd8fc8cb67a72f57e62a0e1259f5e804c487a8478f6895b302d39277bd73947598a5f8ec0a535be9e9a4d34df91df948ee44cc3d13d14e23b9651089e4767c7f0e7245df55619c92fe24483225d35f5f3ee6f74375065766ffd
c2 = 0x15be2b0eaef8837a753587c47d3f31696a7d239d88837a9b7d903cd0d0648ef8e225ea555402693a23f305d19e7e13905be61b44c651dba5b26614bcf876234e765a724e0ed8af4a4e408e6a233c48ab9cc63e9c552ef9cd1999512aa0aca830fe6cbcbcc3c6bb354903124a2c3a12d442cdbdefdae6576f4bbc1515051b7111
beta = 2*g2
s = (n2-1)//beta
xy = s//beta
x_y = s% beta
temp = iroot(x_y**2 - 4 * xy , 2)[0]
x = (x_y +temp) // 2
y = (x_y - temp) //2
p = x *beta + 1
q = y * beta + 1
e = 65537
assert p * q == n2
phi = (p-1)*(q-1)
flag = pow(c2 , invert(e , phi) , p*q)
print(long_to_bytes(flag))
# Strange_CRT :
可恶可恶可恶！第一次论文看下来都看得懂。结果因为出结果的时候把 dq 当成 k ,k 当成 dq 去算 导致我花了一个晚上时间.... 调大维度.... 甚至去实现第五点的内容，结果也没有成效...ri ... 群里问 wp 看一眼造的格子 不尼玛一模一样... 害 卑微...
贴个 Link ：https://link.springer.com/content/pdf/10.1007%2F3-540-45708-9_16.pdf 主要还是多元 Coppersmith 把.
先看题目中 给出的 生成 d 的条件这么长，你推阿推啊推... 发现最后退出来结果还是就这 b 样就是 d=dp%(p-1)，d=dq%(q-1) ，那接下去看论文内部，直接看第三块 。我们可以构造出
edp+k(p−1)=1;edp−(k+1)=−kped_p+k(p-1)=1;ed_p-(k+1)=-kp
接下去我们可以通过这个式子得到一个多项式
fp(x,y)=ex−y;rootis(dp,k+1)modpf_p(x,y)=ex-y;\\\\root\ is\ (d_p,k+1)\mod p
在这个构造当中，我们有 dp≤Nδd_p≤N^\delta 因为 e<(p−1)(q−1)/2e<(p-1)(q-1)/2 所以可以推导出
∣k+1∣=∣edp−2p−1∣<edpp−1<q−12dp<Nβ+δ|k+1|=|\frac{ed_p-2}{p-1}|<\frac{ed_p}{p-1}<\frac{q-1}{2}d_p<N^{\beta+\delta}
那么我们设两个上界 X=Nδ,Y=Nβ+δX = N^\delta,Y=N^{\beta+\delta} 然后我们可以得知这个 fp 多项式 在界内存在小根 (x0,y0)(x_0,y_0) ，接下来我们就可以看到模块 4 了 ，只需要 β<0.382\beta<0.382 时，我们使用 coppersmith 中提到过的 x−shiftedx-shifted 方法去构造多项式
gm,i,j(x,y)=Nmax(0,m−j)xifpj(x,y)g_{m,i,j}(x,y)=N^{max(0,m-j)}x^if_p^j(x,y)
这同时也存在着 x0,y0=dp,k+1modpmx_0,y_0 =d_p,k+1\mod p^m，我们可以通过构造格子 n = 4 , m = 2 的格子
Bp(4)=[N2X3eNX3−NX2Ye2X3−2eX2YXY2e3X3−3e2X2Y3eXY2−Y3]B_p(4)=\left[\begin{matrix}N^2X^3\\\\ eNX^3&-NX^2Y\\\\ e^2X^3&-2eX^2Y&XY^2\\\\ e^3X^3&-3e^2X^2Y&3eXY^2&-Y^3 \end{matrix}\right]
并且满足这个格子的 目标向量 的模 小于 pmn\frac{p^m}{\sqrt{n}} ，推导一下为什么这样
∣∣SVP∣∣≤2n−14det⁡(Lp(n))1ndet⁡(Lp(n))=Nm(m+1)2(XY)n(n−1)2=(n+12)n(n−1)Nm(m+1)2+(2δ+β)n(n−1)2||SVP||≤2^{\frac{n-1}{4}}\det(L_p(n))^{\frac{1}{n}}\\\\ \det(L_p(n))=N^{\frac{m(m+1)}{2}}(XY)^{\frac{n(n-1)}{2}}=(\frac{n+1}{2})^{n(n-1)}N^{\frac{m(m+1)}{2}+(2\delta+\beta)\frac{n(n-1)}{2}}\\\\
计算一下 这个刚刚好位数一模一样... 那就直接用这个，接着主要在扩大一下界的范围 (可能不需要 x)
X=n+12Nδ,Y=n+12Nβ+δX=\frac{n+1}{2}N^\delta,Y=\frac{n+1}{2}N^{\beta+\delta}
于是格基规约格子之后得到的第一行向量，拿来直接使用，构造出多项式 然后再去因式分解这个多项式，接着我们就可以看到一个只有一个 x 和只有一个 y 的一个因式，那么没错 其中一个就是 dpd_p 另外一个就是 k-1, 没错这里的是 k−1k-1 我也不知道为什么.... 离谱... 我拿 k+1 算就错了。改了一下就对了 ，emmm 大概是因为 k 出来的其实是 负号 前面我们对多项式操作是已经把他取了一次相反数 因此这得到的 是 -k-1 .
贴个 EXp：
from Crypto.Util.number import*
from gmpy2 import*
beta = 0.34
delta = 0.02
amplification = 2048
p_bits = int(beta * amplification)#696
q_bits = int((1 - beta)* amplification)#1351
dp_bits = int((beta-delta) * amplification)#655
dq_bits = int(delta * amplification)#40
N = 7194944829894746935571965271122989443610702698015123026500274312320541540511952275333536082176132102091625202863345739074691901574020649953130369453360247690506566827078013306825941200018330639608298539682191482947557146237487451707849833303794107411686130468587672820352641436722348277258977791778239539008852841749667581869688275892813664557078043533743669277649148468667399393518112220602616186358353262921270486781426670131125521444335280904901224934061164334131460273779473387748722008412594372005590209919098686472153912130124772089012962023984089123929555594332030502775588070235834837667605812843128059372243
e = 5872666789397408936685003821802975734744078884385553897196686533187747297681714766542317071546532454504513425295170366015384657690105523240363850101369048640430719519784564240908244756652800934680608667950183962226340288720771217107508516125044088043789281574833079766048266075717484676158307477384862873719462770774288252074344824446884295300603035728339571606659365040029505127532956295163195257002051007447197735267997104725561159289832252522298457628452222155625714679911912616173849423059919537353814530280736653541415686756485413316581322357887750268983241858913704388088485132644523120028234659344174431547087
'''
X = int(pow(N,delta)*5/2)
Y = int(pow(N,(delta+beta))*5/2)
L =  Matrix(ZZ,[[N**2*X**3,0,0,0],[e*N*X**3,-N*X**2*Y,0,0],[e**2*X**3,-2*e*X**2*Y,X*Y**2,0],[e**3*X**3,-3*e**2*X**2*Y,3*e*X*Y**2,-Y**3]])
A = L.LLL()[0]
p = [] 
p.append(A[0]//(X**3))
p.append(A[1]//(X^2*Y))
p.append(A[2]//(X*Y^2))
p.append(A[3]//(Y^3))
R.<x,y> = ZZ[]
f = x**3*p[0] + x**2*y*p[1] + x*y**2*p[2] + y**3*p[3] 
f.factor()
(144242809483056840663075735623298553029680437297789965222541248349475437890222709450048997656976387390752105996145725490546933534602744908786700426835710727511955799912350818546609860818884274334936799981304721460528637717*x + 636751972323*y) 
'''
k = 144242809483056840663075735623298553029680437297789965222541248349475437890222709450048997656976387390752105996145725490546933534602744908786700426835710727511955799912350818546609860818884274334936799981304721460528637717
dq = 636751972323
c = 6601667269134560091452287214083525217696007424340765571114688738279264700361513951309195757650152324371826111195352731779137577044473630747863137747356695892337017953751159248388157498368915463745769509485009626774902347006319659852239932231921393353157319713540010424345134411781723171111939891127671029064626426950125001347122070491553845919803891156107693973027238705710354919725550360159383455222982999904576805089837067774838194257113022653159325313574447189639317397889065351340828031907571541750274329094240472180870714728295651611160552345500801797030280900507979459558944006193012524181456837126192865748097
k = k+1
q = (e*dq-1)//k+1
p = N//q
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,N)))
学习到好多好多东西！出题人煞费苦心～
请我喝[茶]~(￣▽￣)~*
De3B4to 微信支付
微信支付
De3B4to 支付宝
支付宝