1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| from sympy.solvers import solve from sympy.abc import h,l from Crypto.Util.number import isPrime import gmpy2
delta = 61 n1 = 150838784531830142890659431841610000561921043629625618437510373123377520444955469509903631548754842609295975005302780725591929018884805452687677684641162979092069629817740554095750189248769936750051172301891394503776919559958638203717583333429953061416588208428893436430392654983424277005324307321992921302331 n2 = 102603788692700558034198259394482879736866145355211103067657972779629890324418113112441175321034955422723378003769267804892308121194871227786783930178021669484220789624643889449429959522560822967157677629720685465873700893389751397027159036419 c = 100199300622156732994823007073822662584719346985430234367094043002848132740563819931486477742264272832060136969084318984512567787814048659200236334994498141562184235841854521058494238451300610422156322926341430748222140189349893444976932184031798101999886029853099171189139509539715437105818418407563733036131 e = 65537
R.<x> = PolynomialRing(Zmod(n1))
def factor_N2(n): pq_high = n // pow(10,183) pq_low = n % pow(10,61) pq = pq_high * pow(10,61) + pq_low f1 = pq - h*l f2 = (n - pq*pow(10,122) - pq) - pow(10,61)*(h**2 + l**2) s = solve([f1,f2],[h,l]) for i in s: p_high,p_low = int(i[0]),int(i[1]) p = int(p_high * pow(10,61) + p_low) q = int(p_low * pow(10,61) + p_high) if p > 0 and q > 0 and isPrime(p) and isPrime(q): return p,q def factor_N1(tp,tq): if len(tp)==400: p_low = int(tp,2) try: f = x*(2**400)+p_low res = f.monic().small_roots(X=2^112, beta=0.4) if res != []: p = res[0]*(2**400)+p_low if n1%p==0: q = n1//int(p) phi = (p-1)*(q-1) d = inverse_mod(e,phi) m = pow(c,d,n1) flag = bytes.fromhex(hex(m)[2:]) if b'begin' in flag: print(flag) return except: pass else: k = len(tp) p1 = int(tp,2) q1 = int(tq,2) if (p1^^q1)%(2**k)==p_xor_q%(2**k) and (p1*q1)%(2**k)==n1%(2**k): factor_N1('1' + tp, '1' + tq) factor_N1('1' + tp, '0' + tq) factor_N1('0' + tp, '1' + tq) factor_N1('0' + tp, '0' + tq)
p2,q2 = factor_N2(n2) print(f"p2 = {p2}") print(f"q2 = {q2}") p_xor_q = p2 - delta factor_N1('1','1')
|
预览: