from Crypto.Util.number import inverse, long_to_bytes
n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893 e = 65537 c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505
from sage.allimport * from Crypto.Util.number import long_to_bytes
# Given values p = 8147594556101158967571180945694180896742294483544853070485096002084187305007965554901340220135102394516080775084644243545680089670612459698730714507241869 e = 65537 B_list = [ [2155477851953408309667286450183162647077775173298899672730310990871751073331268840697064969968224381692698267285466913831393859280698670494293432275120170, 4113196339199671283644050914377933292797783829068402678379946926727565560805246629977929420627263995348168282358929186302526949449679561299204123214741547], [3652128051559825585352835887172797117251184204957364197630337114276860638429451378581133662832585442502338145987792778148110514594776496633267082169998598, 2475627430652911131017666156879485088601207383028954405788583206976605890994185119936790889665919339591067412273564551745588770370229650653217822472440992] ]
# Define matrix B over GF(p) F = GF(p) B = matrix(F, B_list)
# Compute trace and determinant tr = B.trace() det = B.det() discriminant = tr^2 - 4*det
# Check if discriminant is a square ifnot discriminant.is_square(): print("Discriminant is not a square, no solution exists") exit()
# Compute eigenvalues of B sqrt_disc = discriminant.sqrt() inv2 = F(2).inverse_of_unit() # Fixed line mu1 = (tr + sqrt_disc) * inv2 mu2 = (tr - sqrt_disc) * inv2
# Compute modular inverse of e modulo p-1 d = inverse_mod(e, p-1)
# Compute eigenvalues of A lambda1 = mu1^d lambda2 = mu2^d
# Compute eigenvectors of B (which are also eigenvectors of A) I = identity_matrix(F, 2) ker1 = (B - mu1 * I).right_kernel() v1 = ker1.basis()[0] ker2 = (B - mu2 * I).right_kernel() v2 = ker2.basis()[0]
# Construct matrix P P = matrix([v1, v2]).transpose()
# Construct diagonal matrix D D = diagonal_matrix([lambda1, lambda2])
# Compute matrix A A = P * D * P.inverse()
# Extract flag and convert to bytes flag_int = Integer(A[0,0]) flag = long_to_bytes(flag_int)
# Output the flag print(flag)
LitCTF{13dd217e-9a67-4093-8a1b-d2592c45ba82}
leak
import itertools
deffind_small_roots(polynomial, bounds, m=1, d=None): """ Implementation of Coppersmith's method to find small roots of a multivariate polynomial. Args: polynomial: The polynomial for which to find small roots bounds: List of bounds for each variable's size m: Parameter for lattice construction (default 1) d: Degree parameter (default None, will use polynomial's degree) Returns: List of small roots found """ ifnot d: d = polynomial.degree()
# Get base ring and its cardinality base_ring = polynomial.base_ring() ring_cardinality = base_ring.cardinality()
# Normalize the polynomial by making it monic polynomial /= polynomial.coefficients().pop(0) polynomial = polynomial.change_ring(ZZ) # Convert to integer polynomial
# Construct the lattice basis lattice_basis = Sequence([], polynomial.parent()) for i inrange(m + 1): base = ring_cardinality^(m - i) * polynomial^i # Generate all possible monomial shifts for shifts in itertools.product(range(d), repeat=polynomial.nvariables()): shifted_poly = base * prod(map(power, polynomial.variables(), shifts)) lattice_basis.append(shifted_poly)
# Apply size reduction to the lattice scaling_factors = [monomial(*bounds) for monomial in monomials] for i, factor inenumerate(scaling_factors): coeff_matrix.rescale_col(i, factor)
# Revert the size reduction coeff_matrix = coeff_matrix.change_ring(QQ) for i, factor inenumerate(scaling_factors): coeff_matrix.rescale_col(i, 1 / factor)
# Extract potential solutions solution_polynomials = Sequence([], polynomial.parent().change_ring(QQ)) for h infilter(None, coeff_matrix * monomials): solution_polynomials.append(h) ideal = solution_polynomials.ideal() if ideal.dimension() == -1: solution_polynomials.pop() # Remove if the ideal is trivial elif ideal.dimension() == 0: # Found solutions - convert to integers roots = [] for root in ideal.variety(ring=ZZ): root = tuple(base_ring(root[var]) for var in polynomial.variables()) roots.append(root) return roots
# ===== Polynomial Construction ===== # Define polynomial ring over Z/nZ polynomial_ring.<x, y> = PolynomialRing(Zmod(modulus))
# Construct the polynomial: f = e*(hint*2^180 + x) + y - 1 # We're looking for small roots (x,y) where x < 2^180 and y < 2^100 target_polynomial = public_exponent*(partial_hint*2^180 + x) + y - 1
# ===== Find Small Roots ===== # Find small roots using Coppersmith's method delta_h, k_value = find_small_roots(target_polynomial, [2^180, 2^100], m=1, d=3)[0]
# ===== Factor the Modulus ===== # Reconstruct the temporary value used in the polynomial temp_value = partial_hint*2^180 + delta_h # Calculate p as a factor of n prime_factor = gcd(modulus, (public_exponent*temp_value - 1)//k_value + 1) print("[+] Found prime factor p =", prime_factor)
# ===== Decrypt the Ciphertext ===== # Compute the private exponent d (mod p-1) private_exponent = pow(public_exponent, -1, prime_factor-1) # Modular inverse
# Decrypt the ciphertext plaintext = pow(ciphertext, private_exponent, prime_factor)
# Convert the message to bytes flag_bytes = int(plaintext).to_bytes((int(plaintext).bit_length() + 7) // 8, 'big') print("[+] Decrypted flag:", flag_bytes.decode())
LitCTF{03ecda15d1a89b06454c6050c1bd489f}
baby
import gmpy2 from Crypto.Util.number import long_to_bytes
g = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547 d = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498
definv(d, g): return gmpy2.invert(d, g)
defconv(a, b): h, k, h_prev, k_prev = 1, 0, 0, 1 while b: q = a // b h, h_prev = q * h + h_prev, h k, k_prev = q * k + k_prev, k a, b = b, a % b yield h, k
deffind_t(c, m, n): for h, t in c: if m <= t < n and gmpy2.is_prime(t): return t
