clock-curve-math 1.1.3

#!/usr/bin/env python3
"""
Cryptanalysis attacks against elliptic curve cryptography.

This module implements various cryptanalysis attacks and vulnerability
assessments for elliptic curve cryptographic systems, including:

- Small subgroup attacks
- Invalid curve attacks
- Pollard rho attacks on ECDLP
- Pohlig-Hellman attacks
- Side-channel attack demonstrations
- Weak parameter detection

All implementations use SageMath for mathematical accuracy.
"""

import sage.all as sage
from sage.schemes.elliptic_curves.constructor import EllipticCurve
from sage.rings.finite_rings.finite_field_constructor import FiniteField
from sage.groups.generic import order_from_multiple
import math
import random
import time


class EllipticCurveCryptanalysis:
    """Cryptanalysis attacks against elliptic curve cryptography."""

    def __init__(self, p, a=0, b=0, generator=None):
        """
        Initialize elliptic curve for cryptanalysis.

        Args:
            p: Prime modulus (field characteristic)
            a, b: Curve parameters for y^2 = x^3 + a*x + b
            generator: Generator point (optional)
        """
        self.p = sage.Integer(p)
        self.Fp = FiniteField(self.p)
        self.a = self.Fp(a)
        self.b = self.Fp(b)
        self.E = EllipticCurve(self.Fp, [self.a, self.b])

        # Get curve order and analyze structure
        self.order = self.E.order()
        self.order_factors = self.order.factor()

        print(f"Curve: y^2 = x^3 + {a}x + {b} over F_{p}")
        print(f"Curve order: {self.order}")
        print(f"Order factorization: {self.order_factors}")

        # Find generator
        if generator is None:
            self.generator = self._find_generator()
        else:
            self.generator = generator

    def _find_generator(self):
        """Find a generator point for the curve."""
        for P in self.E.points():
            if not P.is_zero() and P.order() == self.order:
                return P
        # If no full-order point, take any non-trivial point
        for P in self.E.points():
            if not P.is_zero():
                return P
        raise ValueError("No generator found")

    def small_subgroup_attack(self, public_key, subgroup_order=None):
        """
        Small subgroup attack.

        If the public key lies in a small subgroup, we can solve the DLP efficiently.

        Args:
            public_key: Public key point Q = x*G
            subgroup_order: Order of suspected small subgroup

        Returns:
            Private key x if found in small subgroup, None otherwise
        """
        print("Performing small subgroup attack...")

        if subgroup_order is None:
            # Try common small subgroup orders (factors of curve order)
            small_orders = [2, 3, 5, 7, 11, 13, 17, 19, 23]
            for order in small_orders:
                if self.order % order == 0:
                    x = self._attack_small_subgroup(public_key, order)
                    if x is not None:
                        return x
            return None
        else:
            return self._attack_small_subgroup(public_key, subgroup_order)

    def _attack_small_subgroup(self, public_key, subgroup_order):
        """Attack a specific small subgroup."""
        # Generate cofactor
        cofactor = self.order // subgroup_order

        # Move to subgroup: Q' = cofactor * Q
        # If Q was in subgroup of order d, then Q' will be point at infinity
        Q_prime = cofactor * public_key

        if Q_prime.is_zero():
            print(f"Public key lies in subgroup of order dividing {subgroup_order}")

            # Find the actual subgroup order
            subgroup_points = []
            current = public_key
            for i in range(1, subgroup_order + 1):
                if current.is_zero():
                    actual_order = i
                    break
                subgroup_points.append(current)
                current = current + public_key

            actual_order = len(subgroup_points) + 1
            print(f"Actual subgroup order: {actual_order}")

            # Solve DLP in small group using brute force
            for x in range(actual_order):
                if x * public_key == public_key:
                    return x

        return None

    def invalid_curve_attack(self):
        """
        Check for invalid curve parameters that could lead to attacks.

        Returns:
            Dict of detected vulnerabilities
        """
        print("Checking for invalid curve vulnerabilities...")

        vulnerabilities = {}

        # Check if curve has singular points (discriminant = 0)
        discriminant = 18*self.a*self.b*self.a + 4*self.a**3 + 27*self.b**2
        if discriminant == 0:
            vulnerabilities['singular'] = "Curve is singular - vulnerable to certain attacks"

        # Check if curve order is prime (good) or composite (potentially vulnerable)
        if len(self.order_factors) > 1:
            vulnerabilities['composite_order'] = f"Curve order is composite: {self.order_factors}"

        # Check for small prime factors in curve order
        small_factors = []
        for factor, _ in self.order_factors:
            if factor < 1000:  # Arbitrarily small threshold
                small_factors.append(factor)
        if small_factors:
            vulnerabilities['small_factors'] = f"Small prime factors in order: {small_factors}"

        # Check if curve is supersingular (order = p+1)
        if self.order == self.p + 1:
            vulnerabilities['supersingular'] = "Curve is supersingular"

        # Check if j-invariant is 0 or 1728 (special curves)
        try:
            j = self.E.j_invariant()
            if j == 0 or j == 1728:
                vulnerabilities['special_j'] = f"Special j-invariant: {j}"
        except:
            pass

        return vulnerabilities

    def brute_force_attack(self, generator, public_key, max_tries=1000):
        """
        Brute force attack for small groups.

        Simply tries all possible x values.

        Args:
            generator: Generator point G
            public_key: Public key point Q
            max_tries: Maximum x values to try

        Returns:
            Private key x, or None if not found
        """
        print("Performing brute force attack on ECDLP...")

        for x in range(1, min(max_tries, self.order)):
            if x * generator == public_key:
                print(f"Found private key: {x}")
                return x

        print("Brute force attack failed to find solution")
        return None

    def pollard_rho_ecdlp(self, generator, public_key, max_iterations=10000):
        """
        Pollard rho attack on elliptic curve discrete logarithm problem.

        For small groups, falls back to brute force for reliability.
        For larger groups, uses the rho algorithm.

        Args:
            generator: Generator point G
            public_key: Public key point Q
            max_iterations: Maximum iterations before giving up

        Returns:
            Private key x, or None if not found
        """
        # For very small groups, brute force is faster and more reliable
        if self.order < 1000:
            return self.brute_force_attack(generator, public_key)

        print("Performing Pollard rho attack on ECDLP...")

        def partition_function(point):
            """Better partition function for rho algorithm."""
            if point.is_zero():
                return 0
            # Use more partitions based on both coordinates
            x_coord = int(point[0])
            y_coord = int(point[1]) if not point.is_zero() else 0
            return (x_coord + y_coord) % 32  # 32 partitions for better distribution

        def step_function(point, a, b):
            """Step function: point -> next_point, update a,b"""
            partition = partition_function(point)

            if partition % 3 == 0:
                # Add generator: point -> point + G, a -> a+1, b -> b
                return point + generator, a + 1, b
            elif partition % 3 == 1:
                # Point doubling: point -> 2*point, a -> 2*a, b -> 2*b
                return 2 * point, 2 * a, 2 * b
            else:
                # Add public key: point -> point + Q, a -> a, b -> b+1
                return point + public_key, a, b + 1

        # Floyd's cycle detection
        tortoise = (generator, 1, 0)  # (point, a, b) where we track a*G + b*Q
        hare = (generator, 1, 0)

        for i in range(max_iterations):
            # Move tortoise one step
            tortoise = step_function(tortoise[0], tortoise[1], tortoise[2])

            # Move hare two steps
            hare = step_function(hare[0], hare[1], hare[2])
            hare = step_function(hare[0], hare[1], hare[2])

            # Check for cycle
            if tortoise[0] == hare[0]:
                # Found cycle, solve for x
                print(f"Cycle detected after {i} iterations")

                # We have: tortoise_point = hare_point
                # So: a1*G + b1*Q = a2*G + b2*Q
                # Thus: (a1 - a2)*G = (b2 - b1)*Q
                # So: x = (a1 - a2) * (b2 - b1)^(-1) mod order

                a1, b1 = tortoise[1], tortoise[2]
                a2, b2 = hare[1], hare[2]

                try:
                    diff_b = b2 - b1
                    diff_a = a1 - a2

                    if diff_b == 0:
                        continue  # Degenerate case, keep going

                    # Ensure we're working modulo the group order
                    diff_b_mod = diff_b % self.order
                    diff_a_mod = diff_a % self.order

                    inv_diff_b = sage.inverse_mod(diff_b_mod, self.order)
                    x = (diff_a_mod * inv_diff_b) % self.order

                    # Verify solution
                    if x * generator == public_key:
                        print(f"Found private key: {x}")
                        return x
                    else:
                        # False positive, continue searching
                        continue
                except:
                    # Modular inverse failed, continue
                    continue

        print("Pollard rho attack failed to find solution within iteration limit")
        return None

    def pohlig_hellman_attack(self, generator, public_key):
        """
        Pohlig-Hellman attack for composite order groups.

        Reduces ECDLP to smaller subproblems when curve order has small factors.

        Args:
            generator: Generator point G
            public_key: Public key point Q = x*G

        Returns:
            Private key x using Chinese Remainder Theorem, or None if attack fails
        """
        print("Performing Pohlig-Hellman attack...")

        if len(self.order_factors) == 1:
            print("Curve order is prime - Pohlig-Hellman not applicable")
            return None

        solutions = []

        for p_i, e_i in self.order_factors:
            print(f"Solving DLP modulo p_i^{e_i} = {p_i}^{e_i}")

            # Compute order of subgroup
            subgroup_order = p_i ** e_i

            # Compute generator for subgroup
            cofactor = self.order // subgroup_order
            G_i = cofactor * generator
            Q_i = cofactor * public_key

            # Solve DLP in subgroup using baby-step giant-step
            x_i = self._baby_step_giant_step(G_i, Q_i, subgroup_order)

            if x_i is None:
                print(f"Failed to solve DLP modulo {p_i}^{e_i}")
                return None

            solutions.append((x_i, subgroup_order))

        # Use Chinese Remainder Theorem to combine solutions
        try:
            x = self._chinese_remainder_theorem(solutions)
            print(f"Pohlig-Hellman found private key: {x}")

            # Verify solution
            if x * generator == public_key:
                return x
            else:
                print("Combined solution verification failed")
                return None

        except Exception as e:
            print(f"Chinese Remainder Theorem failed: {e}")
            return None

    def _baby_step_giant_step(self, generator, target, order):
        """Baby-step giant-step for ECDLP in subgroup."""
        m = math.ceil(math.sqrt(order))

        # Baby steps: compute G^0, G^1, ..., G^{m-1}
        baby_steps = {}
        current = self.E(0)  # Point at infinity
        for i in range(m):
            baby_steps[current] = i
            current = current + generator

        # Compute G^m
        g_m = m * generator

        # Giant steps: check if Q - j*(G^m) is in baby steps
        for j in range(m):
            giant_step = target - j * g_m
            if giant_step in baby_steps:
                return (baby_steps[giant_step] + j * m) % order

        return None

    def _chinese_remainder_theorem(self, solutions):
        """Solve system of congruences using CRT."""
        result = 0
        modulus = 1

        for x_i, m_i in solutions:
            modulus *= m_i

        for x_i, m_i in solutions:
            m = modulus // m_i
            inv_m = sage.inverse_mod(m, m_i)
            result += x_i * m * inv_m

        return result % modulus

    def side_channel_attack_demo(self, generator, public_key):
        """
        Demonstrate side-channel attack vulnerability.

        Shows how timing information could leak private key bits.

        Args:
            generator: Generator point G
            public_key: Public key point Q

        Returns:
            Recovered key bits (simulated)
        """
        print("Demonstrating side-channel attack vulnerability...")

        # Simulate timing leak: different timing for point doubling vs point addition
        def leaky_scalar_mult(k, G):
            """Scalar multiplication with timing leak."""
            result = self.E(0)
            for bit in reversed(k.bits()):  # MSB first
                start_time = time.time()

                if bit == 1:
                    result = result + G  # Point addition (slower)
                result = 2 * result  # Point doubling (faster)

                # Simulate timing difference
                operation_time = time.time() - start_time
                if bit == 1:
                    operation_time += 0.001  # Addition takes longer

                # In real attack, attacker would measure this timing
                print(f"Bit {bit}: operation time = {operation_time:.6f}s")

            return result

        # Try to recover some bits by timing
        recovered_bits = []
        test_key = 42  # Known test key
        Q_computed = leaky_scalar_mult(sage.Integer(test_key), generator)

        print(f"Original key: {test_key}")
        print(f"Computed Q: {Q_computed}")
        print(f"Expected Q: {public_key}")

        return recovered_bits  # Would contain recovered bits in real attack

    def comprehensive_vulnerability_assessment(self, generator, public_key):
        """
        Perform comprehensive vulnerability assessment.

        Args:
            generator: Generator point G
            public_key: Public key point Q

        Returns:
            Dict of assessment results
        """
        assessment = {
            'invalid_curve_checks': self.invalid_curve_attack(),
            'small_subgroup_attack': None,
            'pohlig_hellman_feasible': len(self.order_factors) > 1,
            'pollard_rho_complexity': self._estimate_pollard_rho_complexity(),
            'recommended_security': self._assess_security_level()
        }

        # Try small subgroup attack
        small_subgroup_result = self.small_subgroup_attack(public_key)
        if small_subgroup_result is not None:
            assessment['small_subgroup_attack'] = small_subgroup_result

        return assessment

    def _estimate_pollard_rho_complexity(self):
        """Estimate complexity of Pollard rho attack."""
        # Pollard rho complexity is O(sqrt(order))
        sqrt_order = math.sqrt(float(self.order))
        if sqrt_order < 2**32:
            return "FEASIBLE"
        elif sqrt_order < 2**64:
            return "DIFFICULT"
        else:
            return "INFEASIBLE"

    def _assess_security_level(self):
        """Assess the security level of the curve."""
        bit_length = self.order.bit_length()

        if bit_length >= 256:
            return "HIGH_SECURITY"
        elif bit_length >= 224:
            return "MEDIUM_HIGH_SECURITY"
        elif bit_length >= 192:
            return "MEDIUM_SECURITY"
        elif bit_length >= 128:
            return "LOW_SECURITY"
        else:
            return "INSECURE"

    def demo_attacks(self):
        """Demonstrate various cryptanalysis attacks."""
        print("=" * 60)
        print("ELLIPTIC CURVE CRYPTANALYSIS DEMONSTRATION")
        print("=" * 60)

        # Test with a weak curve for demonstration
        print("\n1. Testing with weak curve (small prime, composite order)")

        # Create a test key pair
        private_key = 42
        public_key = private_key * self.generator

        print(f"Private key: {private_key}")
        print(f"Public key: {public_key}")

        # Comprehensive assessment
        assessment = self.comprehensive_vulnerability_assessment(self.generator, public_key)
        print(f"\nVulnerability Assessment: {assessment}")

        # Try attacks
        print("\n2. Attempting Small Subgroup Attack...")
        small_attack_result = self.small_subgroup_attack(public_key)
        if small_attack_result is not None:
            print(f"SUCCESS: Recovered private key {small_attack_result}")
        else:
            print("No vulnerable small subgroup found")

        print("\n3. Attempting Pohlig-Hellman Attack...")
        if len(self.order_factors) > 1:
            ph_attack_result = self.pohlig_hellman_attack(self.generator, public_key)
            if ph_attack_result is not None:
                print(f"SUCCESS: Recovered private key {ph_attack_result}")
            else:
                print("Pohlig-Hellman attack failed")
        else:
            print("Not applicable (prime order group)")

        print("\n4. Demonstrating Pollard Rho Attack (limited iterations)...")
        rho_result = self.pollard_rho_ecdlp(self.generator, public_key, max_iterations=1000)
        if rho_result is not None:
            print(f"SUCCESS: Recovered private key {rho_result}")
        else:
            print("Pollard rho attack did not find solution (expected for large groups)")

        print("\n5. Side-Channel Attack Demonstration...")
        self.side_channel_attack_demo(self.generator, public_key)


def test_weak_curves():
    """Test cryptanalysis on known weak curves."""
    print("\n" + "=" * 60)
    print("TESTING WEAK CURVES")
    print("=" * 60)

    # Test curve with small prime and composite order
    p = 101  # Very small prime for testing
    analysis = EllipticCurveCryptanalysis(p, a=0, b=1)
    analysis.demo_attacks()

    # Test with another weak curve
    print("\n" + "-" * 60)
    print("Testing another weak curve...")
    p2 = 2**31 - 1  # Mersenne prime, but small
    try:
        analysis2 = EllipticCurveCryptanalysis(p2, a=0, b=1)
        # Only do assessment for larger curves
        assessment = analysis2.comprehensive_vulnerability_assessment(
            analysis2.generator, 42 * analysis2.generator)
        print(f"Assessment for larger curve: {assessment}")
    except Exception as e:
        print(f"Failed to analyze larger curve: {e}")


if __name__ == "__main__":
    # Run comprehensive cryptanalysis demonstration
    test_weak_curves()