#Sagemath c=[] a=[] b=[] n=[] Fzlist=[] Fmlist=[] Dlist=[] for i in range(70): R.<x>=PolynomialRing(Zmod(n[i])) Fz=x*(3*x^4+6*a[i]*x^2+12*b[i]*x-a[i]^2)^2-8*(x^3+a[i]*x+b[i])*(x^6+5*a[i]*x^4+20*b[i]*x^3-5*a[i]^2*x^2-4*a[i]*b[i]*x-8*b[i]^2-a[i]^3) Fm=(3*x^4+6*a[i]*x^2+12*b[i]*x-a[i]^2)^2 Fzlist.append(Fz) Fmlist.append(Fm*c[i]) Dlist.append(Fz-c[i]*Fm) Crtlist=[[0for _ in range(70)] for __ in range(10)] for i in range(70): for j in range(10): Crtlist[j][i]=ZZ(Dlist[i][j]) A=[] for i in range(10): A.append(CRT(Crtlist[i],n)) N=1 for i in n: N*=i O.<y>=PolynomialRing(Zmod(N)) S=0 for i in range(10): S+=A[i]*y^i print('Finding Roots') oo,oooo,ooooo=1,2,3 S.small_roots(epsilon=1/16) [3088969433059681806521206959873975785377227976800172674306727155831805513908352148702210247662586117242206183337522557]
from functools import reduce from Crypto.Util.number import * f = open("data", "r") ciphertext = [] a, b, n = [], [], [] for i in range(70): ci, ai, bi, ni = [int(num) for num in f.readline().strip().split(", ")] ciphertext.append(ci) a.append(ai) b.append(bi) n.append(ni) e = 3 deg = 9 coeffi = [] for i in range(70): E = EllipticCurve(IntegerModRing(n[i]), [a[i], b[i]]) P.<m> = PolynomialRing(Zmod(n[i])) f = ciphertext[i]*E._multiple_x_denominator(e, m) - E._multiple_x_numerator(e, m) coeffi.append(f.coefficients(sparse=False)) large_coeffi = [crt([int(coeffi[j][i]) for j in range(70)], [n[j] for j in range(70)]) for i in range(deg+1)] N_bitlength = sum([n[i].bit_length() for i in range(70)]) min_n = min(n) N = reduce(lambda x, y: x*y, n) Sc = large_coeffivar("x") assume(x, 'integer') f = Sc[9]*x^9+Sc[8]*x^8+Sc[7]*x^7+Sc[6]*x^6+Sc[5]*x^5+Sc[4]*x^4+Sc[3]*x^3+Sc[2]*x^2 +Sc[1]*x+Sc[0] lat = [] lat.append([large_coeffi[i]*min_n**i for i in range(deg+1)]+[1/(deg+1)]) for i in range(deg+1): lat.append([((min_n**j)*N if (i==j) else0) for j in range(deg+1)]+[0]) Mat = matrix(lat) Mat_LLL = Mat.LLL() for lin in range(deg): Sc = [int(i) for i in Mat_LLL[lin]] Sc = [(Sc[i]//(min_n**i)) for i in range(deg+1)] var("x") assume(x, 'integer') f = Sc[9]*x^9+Sc[8]*x^8+Sc[7]*x^7+Sc[6]*x^6+Sc[5]*x^5+Sc[4]*x^4+Sc[3]*x^3+Sc[2]*x^2 +Sc[1]*x+Sc[0] print(factor(f)) break ''' m = 3088969433059681806521206959873975785377227976800172674306727155831805513908352 148702210247662586117242206183337522557 print(long_to_bytes(m)) '''
#Sagemath a = 4281014323581546488462714122303747203636223358897123235803046898862939653328802115362584316327572195541081125920528501180620492421895128401613948866529122 b = 1504110610934153564757355169781343270879282969971532470271782059859117769089994716068562704547770368420258743734175281689611986131092394954948339191589449 n = 6638798722521613809421411597209101115203859862340555482590990067056543831415553727351714220257486793657912537305448979625073630917241320204281256125412671 c1= 6327639450575093157999054915625304951894564605402541939450801256931875815282143921161475586010526883609974743159835451980804875847625527741681757415519394 c2= 3275348139763310265438126795688591830796510682708632201044899744259822398076574133105844638686347122066389056025294466297206704146167073441486603569471235 d = 7309467973885 E=EllipticCurve(Zmod(n),[a,b]) Fz=E._multiple_x_numerator(137) Fm=E._multiple_x_denominator(137) print('[+] Proof Work Finished') Fmlist=list(Fm) Fzlist=list(Fz) R.<t>=PolynomialRing(Zmod(n)) Fm1,Fm2,Fz1,Fz2=0,0,0,0 for i in range(len(Fmlist)): Fm1+=Fmlist[i]*(t^i) Fm2+=Fmlist[i]*((t+d)^i) for i in range(len(Fzlist)): Fz1+=Fzlist[i]*(t^i) Fz2+=Fzlist[i]*((t+d)^i) G1,G2=c1*Fm1-Fz1,c2*Fm2-Fz2 defgcdpro(g1, g2): while g2: g1, g2 = g2, g1 % g2 return g1.monic() #return -gcdpro(g1, g2)[0] H=(gcdpro(G1,G2)) print(H) from Crypto.Util.number import * print(long_to_bytes(n-H[0])) #b'DASCTF{692d49f84fe5497fa05d6e91a1cf4e3e}\x04'