Low Public Exponent Attack

When the public exponent $e$ is sufficiently small relative to the modulus $n$, and the padded plaintext satisfies $m^e < n$, the modular reduction becomes ineffective. In this scenario, the ciphertext $c$ is effectively an integer $e$-th power. By iterating through potential multiples of $n$ added to $c$, one can identify the exact $e$-th power and extract the original message.

import gmpy2
import binascii
from Crypto.Util.number import long_to_bytes

def recover_message_low_e(cipher, modulus, exponent, search_limit=100000):
    offset = 0
    while offset <= search_limit:
        candidate = cipher + offset * modulus
        root, is_perfect = gmpy2.iroot(candidate, exponent)
        if is_perfect:
            return long_to_bytes(int(root))
        offset += 1
    raise ValueError("Failed to extract root within search bounds")

# Usage Example
# cipher_value = ...
# modulus_value = ...
# recovered_bytes = recover_message_low_e(cipher_value, modulus_value, 3)
# print(recovered_bytes.hex())

Franklin-Reiter Related Message Attack

If two distinct messages $m_1$ and $m_2$ share a linear relationship $m_2 = A \cdot m_1 + B$, and both are encrypted under the same modulus and exponent, their ciphertexts reveal algebraic dependencies. By constructing univariate polynomials $f_1(x) = (Ax+B)^e - c_1$ and $f_2(x) = x^e - c_2$ over $\mathbb{Z}_n$, their greatest common divisor yields $(x - m_1)$ when $\gcd(A, n) = 1$. If the exponent is unknown but confined to a manageable range, a brute-force search over candidates efficiently recovers the shared root.

def franklin_reiter_recovery(modulus, cipher_linear, cipher_direct, slope, intercept, exponent_bounds):
    R.<x> = PolynomialRing(Zmod(modulus))
    for exp in exponent_bounds:
        poly_f1 = (slope * x + intercept)^exp - cipher_linear
        poly_f2 = x^exp - cipher_direct
        
        common_divisor = poly_f1.gcd(poly_f2)
        if common_divisor.degree() == 1:
            recovered_plaintext = -common_divisor[0] % modulus
            return long_to_bytes(int(recovered_plaintext))
    return None

# Implementation requires mapping the exponent search range and coefficient values

Adleman-Manders-Miller Modular Root Extraction

Computing $e$-th roots modulo a prime $p$ becomes necesary when the encryption exponent divides $p-1$ (i.e., $e \mid p-1$). Standard Euler theorem approaches fail due to multiple roots existing in the field. The Adleman-Manders-Miller (AMM) algorithm addresses this by decomposing $p-1 = s \cdot r^t$, identifying a non-residue, and iteratively refining a base until the target residue is matched. The solution space contains exactly $e$ candidates, requiring exhaustive checking against known flag formats.

def amm_root_extraction(target_val, prime_p, order_e):
    GFp = GF(prime_p)
    g_target = GFp(target_val)
    
    # Decompose p-1
    t, s = 0, prime_p - 1
    while s % order_e == 0:
        t += 1
        s //= order_e
        
    # Find non-residue
    zeta = None
    for _ in range(1000):
        rand = GFp.random_element()
        if rand^(s * (order_e - 1)) != 1:
            zeta = rand
            break
            
    k = inverse_mod((k_val := s), order_e) # Simplified helper
    alpha = zeta^(s)
    beta = g_target^(k)
    h = 1
    gamma = zeta^s
    
    for i in range(t - 1):
        temp = beta^(order_e^(t - 2 - i))
        if temp != 1:
            j = discrete_log(temp, alpha)
        else:
            j = 0
        beta *= gamma^j
        h *= gamma^j
        gamma ^= order_e
        
    result = g_target^(k_val) * h
    return int(result)

Multi-Factor Modulus Decomposition

Certain RSA implementations substitute traditional semiprime moduli with products of numerous small primes. While mathematically valid under certain protocols, this drastically reduces the computational complexity required to calculate Euler’s totient function $\phi(n) = \prod (p_i - 1)$. Once the prime factors are exposed via external databases or trial division, the private exponent is derived directly, allowing straightforward decryption of partitioned ciphertext segments.

from Crypto.Util.number import long_to_bytes, inverse
from math import prod

def decrypt_composite_modulus(cipher, prime_factors, public_exp):
    phi_val = prod([pf - 1 for pf in prime_factors])
    private_d = inverse(public_exp, phi_val)
    decrypted_int = pow(cipher, private_d, prod(prime_factors))
    return long_to_bytes(decrypted_int)

# Workflow involves aggregating partial decryptions and concatenating byte arrays

Håstad’s Broadcast Attack Variant

Encrypting an identical plaintext across multiple independent RSA key pairs sharing the same small exponent creates a vulnerable system. Applying the Chinese Remainder Theorem (CRT) to the collected ciphertext-modulus pairs reconstructs $M = m^e \pmod{N_{total}}$. If the original message satisfies $m^e < N_{total}$, the modular wrapper vanishes, leaving a pure integer whose $e$-th root yields the exact plaintext.

import gmpy2
from sympy.ntheory.modular import crt
from Crypto.Util.number import long_to_bytes

def broadcast_attack_solver(key_pairs, exponent):
    moduli = [pair[0] for pair in key_pairs]
    residues = [pair[1] for pair in key_pairs]
    
    combined_value, _ = crt(moduli, residues)
    root_val, is_exact = gmpy2.iroot(combined_value, exponent)
    
    if not is_exact:
        raise RuntimeError("CRT result exceeds theoretical bound or exponent mismatch")
    
    return long_to_bytes(int(root_val))

# Execute by passing list of tuples: [(n1, c1), (n2, c2), ...]