n = 8361361624563191168612863710516449028280757632934603412143152925186847721821552879338608951120157631182699762833743097837368740526055736516080136520584848113137087581886426335191207688807063024096128001406698217998816782335655663803544853496060418931569545571397849643826584234431049002394772877263603049736723071392989824939202362631409164434715938662038795641314189628730614978217987868150651491343161526447894569241770090377633602058561239329450046036247193745885174295365633411482121644408648089046016960479100220850953009927778950304754339013541019536413880264074456433907671670049288317945540495496615531150916647050158936010095037412334662561046016163777575736952349827380039938526168715655649566952708788485104126900723003264019513888897942175890007711026288941687256962012799264387545892832762304320287592575602683673845399984039272350929803217492617502601005613778976109701842829008365226259492848134417818535629827769342262020775115695472218876430557026471282526042545195944063078523279341459199475911203966762751381334277716236740637021416311325243028569997303341317394525345879188523948991698489667794912052436245063998637376874151553809424581376068719814532246179297851206862505952437301253313660876231136285877214949094995458997630235764635059528016149006613720287102941868517244509854875672887445099733909912598895743707420454623997740143407206090319567531144126090072331 e = 65537 c = 990174418341944658163682355081485155265287928299806085314916265580657672513493698560580484907432207730887132062242640756706695937403268682912083148568866147011247510439837340945334451110125182595397920602074775022416454918954623612449584637584716343806255917090525904201284852578834232447821716829253065610989317909188784426328951520866152936279891872183954439348449359491526360671152193735260099077198986264364568046834399064514350538329990985131052947670063605611113730246128926850242471820709957158609175376867993700411738314237400038584470826914946434498322430741797570259936266226325667814521838420733061335969071245580657187544161772619889518845348639672820212709030227999963744593715194928502606910452777687735614033404646237092067644786266390652682476817862879933305687452549301456541574678459748029511685529779653056108795644495442515066731075232130730326258404497646551885443146629498236191794065050199535063169471112533284663197357635908054343683637354352034115772227442563180462771041527246803861110504563589660801224223152060573760388045791699221007556911597792387829416892037414283131499832672222157450742460666013331962249415807439258417736128976044272555922344342725850924271905056434303543500959556998454661274520986141613977331669376614647269667276594163516040422089616099849315644424644920145900066426839607058422686565517159251903275091124418838917480242517812783383 k = 7
R = Zmod(n)["x"] whileTrue: Q = R.quo(R.random_element(k)) pp = gcd(ZZ(list(Q.random_element() ^ n)[1]), n) if pp != 1: qq = sum([pp**i for i inrange(k)]) rr = n // (pp * qq) assert n == pp * qq * rr break phi = (pp - 1) * (qq - 1) * (rr - 1) d = pow(e, -1, phi) m = pow(c, d, n) print(long_to_bytes(int(m))) # SICTF{d9428fc7-fa3a-4096-8ec9-191c0a4562ff}
# sage from tqdm import * from Crypto.Util.number import * from gmpy2 import * leak = "2011133132443111302000224204142244403203442000141102312242343143241244243020003333022112141220422134444214010012" n = 85988668134257353631742597258304937106964673395852009846703777410474172989069717247424903079500594820235304351355706519069516847244761609583338251489134035212061654870087550317540291994559481862615812258493738064606592165529948648774081655902831715928483206013332330998262897765489820121129058926463847702821 e = 65537 c = 64708526479058278743788046708923650158905888858865427385501446781738669889375403360886995849554813207230509920789341593771929287415439407977283018525484281064769128358863513387658744063469874845446480637925790150835186431234289848506337341595817156444941964510251032210939739594241869190746437858135599624562 p0 = int(leak+"0"*109, 5) p = 0 ff = 0 for i in trange(5): PR.<x> = PolynomialRing(Zmod(n)) f = p0 + i + x*5 f = f.monic() res = f.small_roots(X = 5**108,beta=0.49, epsilon = 0.01) if(res != []): p = int(p0 + i + int(res[0]) * 5) assert is_prime(p) ff = 1 break if ff: break if p: q = n // p phi = (p-1)*(q-1) d = invert(e, phi) m = pow(c, d, n) print(long_to_bytes(int(m)))
easyLattice(二血)
没啥好说,就是一个简单的格:
但得对最后一列的数配平一下,我是都乘上了2**256:
exp(点击展开)
from Crypto.Util.number import *
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443 p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947 L = Matrix(ZZ, [[1, h*2**256], [0, p*2**256]])
m = abs(L.LLL()[0][0]) # print(m) print(long_to_bytes(int(m))) # SICTF{e3fea01c-18f3-4638-9544-9201393940a9}A\xf0\x89\x84
[进阶]2024_New_Setback(复现)
比赛时
一开始解这题的时候,没一点思路,就不管了。。。
差不多要结束的时候,就想着说随便去网上搜搜看得了,没准碰到类似的题?
当时搜的内容是:ctf def new(C, P, Q): c, d, p = C u1, v1 = P u2, v2 = Q assert happy(C, P) and happy(C, Q) u3 = (u1 * v2 + v1 * u2) * inverse(c * (1 + d * u1 * u2 * v1 * v2), p) % p v3 = (v1 * v2 - u1 * u2) * inverse(c * (1 - d * u1 * u2 * v1 * v2), p) % p return (int(u3), int(v3))
from Crypto.Util.number import * from secret import flag, Curve
defhappy(C, P): c, d, p = C u, v = P return (u**2 + v**2 - c**2 * (1 + d * u**2*v**2)) % p == 0
defnew(C, P, Q): c, d, p = C u1, v1 = P u2, v2 = Q assert happy(C, P) and happy(C, Q) u3 = (u1 * v2 + v1 * u2) * inverse(c * (1 + d * u1 * u2 * v1 * v2), p) % p v3 = (v1 * v2 - u1 * u2) * inverse(c * (1 - d * u1 * u2 * v1 * v2), p) % p return (int(u3), int(v3))
defyear(C, P, m): assert happy(C, P) c, d, p = C B = bin(m)[2:] l = len(B) u, v = P PP = (-u, v) O = new(C, P, PP) Q = O if m == 0: return O elif m == 1: return P else: for _ inrange(l-1): P = new(C, P, P) m = m - 2**(l-1) Q, P = P, (u, v) return new(C, Q, year(C, P, m))
c, d, p = Curve
flag = flag.lstrip(b'SICTF{').rstrip(b'}') l = len(flag) l_flag, r_flag = flag[:l // 2], flag[l // 2:]
m1, m2 = bytes_to_long(l_flag), bytes_to_long(r_flag) assert m1 < p and m2 < p
P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662) Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)
#part1 get c2、d、p P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662) Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207) C1 = (730393937659426993430595540476247076383331, 461597565155009635099537158476419433012710) C2 = (500532897653416664117493978883484252869079, 620853965501593867437705135137758828401933) PR.<c,d> = PolynomialRing(ZZ) f1 = P[0]**2 + P[1]**2 - c**2 * (1 + d * P[0]**2*P[1]**2) f2 = Q[0]**2 + Q[1]**2 - c**2 * (1 + d * Q[0]**2*Q[1]**2) f3 = C1[0]**2 + C1[1]**2 - c**2 * (1 + d * C1[0]**2*C1[1]**2) f4 = C2[0]**2 + C2[1]**2 - c**2 * (1 + d * C2[0]**2*C2[1]**2) res = ideal([f1,f2,f3,f4]).groebner_basis() p = res[2].coefficients()[-1] for i inrange(2, 1000): if p % i == 0: p //= i
# Since the above is the value in the ZZ field, we need to take the module p for (c^2, d) c2 = p-(res[0].coefficients()[-1])%p d = p-(res[1].coefficients()[-1])%p # print(c2, d, p)
# get c PR.<c> = PolynomialRing(Zmod(p)) f = c^2 - c2 # print(f.roots())
# get 2 possible values of c c = 662698094423288904843781932253259903384619 # c = 241270766892588524651461499096659309771090
#part2 map to ECC a = 1 F = GF(p) dd = F(d*c^4) A = F(2) * F(a+dd) / F(a-dd) B = F(4) / F(a-dd) a = F(3-A^2) / F(3*B^2) b = F(2*A^3-9*A) / F(27*B^3)
# 转成理想 G = ideal(fs) """ 计算groebner_basis """ res = G.groebner_basis() # 下面也可以写成:a = p-(res[0].coefficients()[-1]),但没必要 a = -res[0].coefficients()[-1] b = -res[1].coefficients()[-1] x = -res[2].coefficients()[-1]
# 范德蒙德行列式 M = Matrix.vandermonde([1, 2, 3, 4, 5, 6])[:]
# 这里其实和前面的多项式法类似,只是转成了矩阵而已 eqs = M * vector(v) - vector(vv)
# 转成理想 I = ideal(list(eqs))
# 计算groebner_basis: """ 1,可以用前面多项式情况下的最后一步: res = G.groebner_basis() a = -res[0].coefficients()[-1] b = -res[1].coefficients()[-1] x = -res[2].coefficients()[-1] """
""" 2,也可以使用variety() 这个可以理解成与groebner_basis()的功能一致,但返回的是含有多个形如{x1:r1, x2:r2, ..., xn:rn}的字典的列表 """ # 假如输出只有一组,就直接取0即可 sol = I.variety()[0] a = sol['a'] b = sol['b'] x = sol['x']
# sage # 来源:https://www.cnblogs.com/mumuhhh/p/18019200 from Crypto.Util.number import *
p = 8432316544210923620966806031040552674652729976238765323782536889706914762471638598119051165931563126522925761119650997703305509546949570434637437942542827 v_me_50 = [(1, 5237331460408741346823741966490617418367283531029963248255318507187035341590236835730694472064897540292182231844047116067936691956970631907605500080014355), (2, 5798977431976767515500795413771120575460553181185728489626756434911307088093739452469315524092208822863785429164219547384598943937099787390543171055679780), (3, 5030862375386942201139427367618716490378481408210696947331523552250206476805124204780313138835912303941204343248384742875319182761611109448446270069831113), (4, 4705360705603328842229554954026497175574981026785287316439514185860486128679614980330307863925942038530792583274904352630757089631411920876914529907563209)] flag = 7251453750672416392395590357197330390627853878488142305852099080761477796591562813165554150640801022882531891827653530623183405183605476913024545431842867
shu = [i[1] for i in v_me_50] PR.<a, b, x> = GF(p)[] defh(): global a, b, x x = a*x + b return x mu = [h() for _ inrange(6)] x_list = [X**i for i inrange(6)]
# 计算groebner_basis: """ 1,可以用前面多项式情况下的最后一步: res = G.groebner_basis() a = -res[0].coefficients()[-1] b = -res[1].coefficients()[-1] x = -res[2].coefficients()[-1] """
""" 2,也可以使用variety() 这个可以理解成与groebner_basis()的功能一致,但返回的是含有多个形如{x1:r1, x2:r2, ..., xn:rn}的字典的列表 官方定义:使用msolve计算零维理想的变化。 """ # 结果只有一组,所以末尾直接取的0 sol = I.variety()[0] a = sol["a"] b = sol["b"] x = sol["x"] """ print(a) print(b) print(x) """
defsmall_roots(f, bound,r,s,N,m): ''' small private d RSA with moduli N=p^r*q^s,that d < 1-(3*r+s)/(r+s)^2 - eps the eps is ((15*s+1)*r^4-(2*s^2-10*s)*r^3-(s^3-6*s^2+8*s)*r^2+(2*s^3-12*s^2+6*s)*r+s^4-4*s^3+s^2) /(4*m*(r-s)*(r+s)^3) in theory,by this we can choose the proper m which is lower than theory. return : one factor of N.you can factor N by this for example: p,q : 256 r,s : 5,3 d : 1300,m = 9 d : 1350,m = 14 d : 1360,m = 20 d : 1370,m = 30 d > 1370,m = 40 # spend long time to do this(2800s) you can choose the larger m to approach the theory solution ''' t1 = int((r*(r+s-2))/((r-1)*(r+s))*m) t2 = m bounds = [bound ,1] f = f.change_ring(ZZ) G = Sequence([], f.parent()) x = f.variables()[0] for k inrange(t2+1): for i inrange(t2+1-k): d=max([0,ceil((r-1)*(t1-k)/r),ceil((s-1)*(t2-k)/s)]) base=N ^ d * f ^ k * x ^ i G.append(base) B, monomials = G.coefficient_matrix() monomials = vector(monomials) factors = [monomial(*bounds) for monomial in monomials] for i, factor inenumerate(factors): B.rescale_col(i, factor) B = B.dense_matrix().LLL() # B = flatter(B) ''' another question is can't use flatter because flatter not support the matrix that its row far greater than its cols ''' B = B.change_ring(QQ) for i, factor inenumerate(factors): B.rescale_col(i, 1 / factor) H = Sequence([], f.parent().change_ring(QQ)) for h infilter(None, B * monomials): for i in h.coefficients(): if gcd(i,N)!=1and gcd(i,N)!=N: return gcd(h.coefficients()[0],N) return0
c = 6027704939934795526809476320408984749353451163184148193613218899917989403800738729505135647560822568147775955030636790796412038749080589962404088890138 N = 2345049742327685796181532105032554795628696111708534285951012187089560814230641663133312117797131139088986342455315166062482479446527815702735474197358418746066993291802284464812612727625991647573889402281825863578807474887341632160586307943897790827019291411639756252138594856687013363652094621849674259604512491449809337670874218320926522274379234396955495643125680407916326561528774056618181536326260093822819468635513422755218190798616168156924793527386350080400722536575372660262573683231490166520738579903818495107264328324326819989553511070207494208500239603511665056894947107356065440333537271115434438827753 e = 1560967245790387854530279132085915310737094193704812456970549221459036227794862560384548159924112528879771688534015861357630951162558357151823378870345945435342412220708167081427844035498174919749839232806280901968067512188264340755833308035745702731211924571583963089915893479992177245815565483658484702813753029786985027579475059989141119719224961817402605977566829967197490932672021566512826377376988752959467389833419735737545201988916590880487156074463948048461415870071893002222885078350961871888123567241990517365430474025391208925638731208820904957752596249597885523540692851123131898267246576902438472358221 r,s= 5,3 edge = 1380