Page cover
Edit

Investigation Methodology

Task-List

Broadcast Attack Decision Tree

├── 🔢 Multiple Moduli + Same Exponent?
│   ├── ✅ YES → Use CRT (Hastad's Attack)
│   └── ❌ NO → Continue analysis
├── 🔗 Known Message Relationships?
│   ├── ✅ Linear → Franklin-Reiter Attack
│   ├── ✅ Polynomial → Coppersmith's Method
│   ├── ✅ Known Differences → Algebraic Solving
│   └── ❌ NO → Continue analysis
├── 🎯 Structured Messages?
│   ├── ✅ YES → Stereotyped Message Attack
│   └── ❌ NO → Continue analysis
├── 📐 Same Modulus?
│   ├── ✅ YES → Direct Algebraic Methods
│   └── ❌ NO → Advanced Lattice Techniques
Detection Methods

Check for small exponent

if e < 65537:
    print("WARNING: Small public exponent detected!"

Check for no padding

if message_size == modulus_size:
    print("WARNING: No padding detected!")

Check for multiple encryptions

if same_message_encrypted_multiple_times:
    print("WARNING: Broadcast attack possible!")

Check for potential Wiener's vulnerability

if e > n**0.5:
    suggestions.append("Wiener's Attack (small d suspected)")

Check for Fermat's vulnerability

sqrt_n = int(n**0.5)
if (sqrt_n + 1)**2 - n < sqrt_n:
    suggestions.append("Fermat's Factorization (close primes)"

Check modulus size for general factorization

bit_length = n.bit_length()
if bit_length < 1024:
    suggestions.append("General Factorization (weak key size)")

Check for common modulus

if additional_info and 'shared_modulus' in additional_info:
    suggestions.append("Common Modulus Attack")
POC
def analyze_rsa_parameters(e, n, additional_info=None):
    """
    Analyze RSA parameters to suggest appropriate attacks
    """
    suggestions = []
    
    # Check for small exponent
    if e < 65537:
        suggestions.append("Small Exponent Attack")
    
    # Check for potential Wiener's vulnerability
    if e > n**0.5:
        suggestions.append("Wiener's Attack (small d suspected)")
    
    # Check for Fermat's vulnerability
    sqrt_n = int(n**0.5)
    if (sqrt_n + 1)**2 - n < sqrt_n:
        suggestions.append("Fermat's Factorization (close primes)")
    
    # Check modulus size for general factorization
    bit_length = n.bit_length()
    if bit_length < 1024:
        suggestions.append("General Factorization (weak key size)")
    
    # Check for common modulus
    if additional_info and 'shared_modulus' in additional_info:
        suggestions.append("Common Modulus Attack")
    
    return suggestions
Small Parameter Attacks

Elliptic Curve Cryptography

POC
def small_parameter_ec_attack(curve_order, private_key_bits):
    """
    Attack weak elliptic curves with small parameters
    """
    if curve_order.bit_length() < 256:
        return "Vulnerable to brute force"
    
    if private_key_bits < 128:
        return "Weak private key - brute force possible"

Discrete Logarithm Systems

POC
def small_subgroup_attack(g, p, q):
    """
    Attack discrete log when subgroup order is small
    """
    if q < 2**80:  # Small subgroup
        return "Vulnerable to Pollard's Rho on small subgroup"

Lattice-Based Cryptography

def lattice_small_secret_attack(lattice_basis, error_bound):
    """
    Attack lattice systems with small secrets/errors
    Similar principle to small exponent attacks
    """
    if error_bound < lattice_dimension_threshold:
        return "Vulnerable to lattice reduction attacks"
Broadcast Attacks

Linear Relationship Attack

POC
def linear_broadcast_attack(c1, c2, n, e, a, b, c, d):
    """
    Attack when messages have linear relationship:
    m₁ = a*m + b
    m₂ = c*m + d
    
    Where m is the target message
    """
    # Given:
    # c₁ ≡ (a*m + b)^e (mod n)
    # c₂ ≡ (c*m + d)^e (mod n)
    
    # For small e (like e=3), we can expand and solve
    if e == 3:
        # Expand (a*m + b)³ and (c*m + d)³
        # Create system of equations in powers of m
        # Solve algebraically
        
        # This is complex algebra - conceptual example
        print("Solving linear system for e=3 case")
        
        # Extract coefficients and solve polynomial system
        # Returns the original message m
        pass
    
    return None

# Example usage:
# If we know m₁ = 2m + 5 and m₂ = 3m + 7
# We can solve even without CRT

Known Difference Attack

POC
def known_difference_attack(c1, c2, n, e, diff):
    """
    Attack when messages differ by a known amount:
    m₂ = m₁ + diff
    """
    # Given:
    # c₁ ≡ m₁^e (mod n)  
    # c₂ ≡ (m₁ + diff)^e (mod n)
    
    # For small e, expand (m₁ + diff)^e using binomial theorem
    # Create equation involving only m₁
    
    if e == 3:
        # c₂ ≡ m₁³ + 3*m₁²*diff + 3*m₁*diff² + diff³ (mod n)
        # Rearrange: c₂ - diff³ ≡ m₁³ + 3*m₁²*diff + 3*m₁*diff² (mod n)
        # Factor: c₂ - diff³ ≡ m₁(m₁² + 3*m₁*diff + 3*diff²) (mod n)
        
        # This creates a relationship we can exploit
        modified_c2 = (c2 - pow(diff, 3, n)) % n
        
        # Now we have a relationship between c1 and modified_c2
        # Can solve using various techniques
        pass
    
    return None

Franklin-Reiter Related Message Attack

POC
def franklin_reiter_attack(c1, c2, n, e, a, b):
    """
    Franklin-Reiter attack for related messages
    m₁ and m₂ where m₂ ≡ a*m₁ + b (mod n)
    
    This DOES NOT use CRT!
    Uses resultants and polynomial GCD
    """
    from sympy import symbols, Poly, resultant
    
    if e < 2:
        return None
    
    x = symbols('x')
    
    # Define polynomials
    # f₁(x) = x^e - c₁
    # f₂(x) = (a*x + b)^e - c₂
    
    f1 = Poly(x**e - c1, x)
    f2 = Poly((a*x + b)**e - c2, x)
    
    # Compute resultant to eliminate x
    # If m₁ is a common root, resultant will be 0
    # This gives us information about m₁
    
    res = resultant(f1, f2, x)
    
    # The resultant gives us a way to find m₁
    # without using CRT - pure polynomial algebra
    
    # Solve for roots of the resultant
    # (Implementation details depend on specific case)
    
    print("Franklin-Reiter uses polynomial resultants, not CRT")
    return None

Stereotyped Message Attack

POC
def stereotyped_message_attack(ciphertexts, n, e, known_parts, unknown_part_size):
    """
    Attack messages with known structure:
    "Dear Alice, [SECRET], Best regards, Bob"
    
    Uses Coppersmith's method, not CRT
    """
    # Messages have form: known_prefix + unknown + known_suffix
    # Use Coppersmith's technique to find small unknown parts
    
    # This works even with a single ciphertext!
    # No need for multiple encryptions or CRT
    
    # Set up polynomial with unknown part as variable
    # Use lattice reduction to find small roots
    
    print("Stereotyped messages use Coppersmith's method")
    print("No CRT required - works on single ciphertext")
    
    return None
PreviousCryptosystemsNextChinese Remainder Theorem Applications

Last updated