kangaroo 0.1.0

#!/usr/bin/env python3
"""Deep pattern analysis - looking for exploitable structure."""

from collections import Counter, defaultdict

# secp256k1 parameters
P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8


def mod_inverse(a: int, m: int) -> int:
    if a < 0:
        a = a % m
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        raise ValueError("No inverse")
    return x % m


def extended_gcd(a: int, b: int):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    return gcd, y1 - (b // a) * x1, x1


def point_add(p1, p2):
    if p1 is None:
        return p2
    if p2 is None:
        return p1
    x1, y1 = p1
    x2, y2 = p2
    if x1 == x2:
        if y1 != y2:
            return None
        s = (3 * x1 * x1 * mod_inverse(2 * y1, P)) % P
    else:
        s = ((y2 - y1) * mod_inverse(x2 - x1, P)) % P
    x3 = (s * s - x1 - x2) % P
    y3 = (s * (x1 - x3) - y1) % P
    return (x3, y3)


def scalar_mult(k: int, point):
    if k == 0:
        return None
    result = None
    addend = point
    while k:
        if k & 1:
            result = point_add(result, addend)
        addend = point_add(addend, addend)
        k >>= 1
    return result


G = (Gx, Gy)


def analyze_power_of_2_keys():
    """Analyze public keys for powers of 2."""
    print("=" * 70)
    print("POWERS OF 2 ANALYSIS")
    print("=" * 70)

    print("\nPublic keys for 2^n:")
    print(f"{'n':>3} | {'X (first 16 hex)':^20} | {'Y parity':^8} | X mod 256")
    print("-" * 70)

    for n in range(0, 40):
        k = 1 << n
        point = scalar_mult(k, G)
        x, y = point
        x_hex = format(x, "064x")[:16]
        parity = "even" if y % 2 == 0 else "odd"
        x_mod = x % 256

        print(f"{n:3} | {x_hex:^20} | {parity:^8} | {x_mod:3}")


def analyze_sequential_structure():
    """Look for structure in how X changes with k."""
    print("\n" + "=" * 70)
    print("SEQUENTIAL STRUCTURE ANALYSIS")
    print("=" * 70)

    # Generate keys 1-1000
    points = []
    current = G
    points.append((1, current))

    for k in range(2, 1001):
        current = point_add(current, G)
        points.append((k, current))

    # Analyze X coordinate low bits vs private key low bits
    print("\nCorrelation: private key bits vs X coordinate bits")
    print("(Looking for any predictable relationship)")

    for bit in range(8):
        matches = 0
        for k, (x, y) in points:
            k_bit = (k >> bit) & 1
            x_bit = (x >> bit) & 1
            if k_bit == x_bit:
                matches += 1
        ratio = matches / len(points)
        deviation = abs(ratio - 0.5) * 100
        marker = "***" if deviation > 10 else ""
        print(f"  Bit {bit}: {ratio:.3f} correlation {marker}")

    # Look for patterns in X mod small numbers
    print("\nX mod small numbers vs k mod same:")
    for m in [3, 5, 7, 11, 13]:
        correlation = defaultdict(lambda: defaultdict(int))
        for k, (x, y) in points:
            correlation[k % m][x % m] += 1

        # Check if there's a predictable mapping
        predictable = True
        for k_mod in range(m):
            counts = correlation[k_mod]
            if len(counts) > 1:
                max_count = max(counts.values())
                total = sum(counts.values())
                if max_count / total < 0.9:
                    predictable = False
                    break

        status = "PREDICTABLE!" if predictable else "random"
        print(f"  mod {m:2}: {status}")


def analyze_halving_relationship():
    """Analyze relationship between k and k/2 (or 2k)."""
    print("\n" + "=" * 70)
    print("HALVING/DOUBLING RELATIONSHIP")
    print("=" * 70)

    print("\nP(2k) vs P(k) relationship:")
    print("P(2k) = 2*P(k) (point doubling)")
    print("\nChecking if X(2k) has predictable relationship to X(k):")

    for k in [1, 2, 3, 5, 7, 11, 13, 17, 19, 100, 1000]:
        pk = scalar_mult(k, G)
        p2k = scalar_mult(2 * k, G)

        # Also compute 2*P(k) directly
        p2k_doubled = point_add(pk, pk)

        # They should be equal
        assert p2k == p2k_doubled, "Point doubling mismatch!"

        xk = pk[0]
        x2k = p2k[0]

        # Look for relationship
        ratio = x2k / xk if xk != 0 else 0
        xor_high = (xk ^ x2k) >> 248

        print(f"  k={k:5}: X(k)/X(2k) high XOR = 0x{xor_high:02x}")


def analyze_additive_structure():
    """Analyze P(a+b) vs P(a) + P(b)."""
    print("\n" + "=" * 70)
    print("ADDITIVE STRUCTURE (the key property)")
    print("=" * 70)

    print("\nP(a+b) = P(a) + P(b) - this is how Kangaroo works!")
    print("If we find structure here, we can optimize search.\n")

    # The question: given X(a) and X(b), can we predict something about X(a+b)?
    print("Testing: Can we predict bits of X(a+b) from X(a) and X(b)?")

    results = []
    for a in range(1, 101):
        for b in range(1, 101):
            if a == b:
                continue
            pa = scalar_mult(a, G)
            pb = scalar_mult(b, G)
            pab = scalar_mult(a + b, G)

            xa, xb, xab = pa[0], pb[0], pab[0]

            # Check various combinations
            xor_ab = xa ^ xb
            xor_result = xab ^ xor_ab

            results.append((a, b, xa, xb, xab, xor_result))

    # Analyze patterns in xor_result
    high_bytes = [r[5] >> 248 for r in results]
    byte_counts = Counter(high_bytes)

    print("\nHigh byte of (X(a+b) XOR (X(a) XOR X(b))) distribution:")
    for byte, count in byte_counts.most_common(10):
        print(f"  0x{byte:02x}: {count} ({100 * count / len(results):.1f}%)")

    # Check if there's any bit that's predictable
    print("\nChecking predictability of each bit of X(a+b):")
    for bit in [0, 1, 2, 3, 4, 5, 6, 7, 255, 254, 253]:
        # Try to predict bit of X(a+b) from bits of X(a), X(b)
        correct = 0
        for a, b, xa, xb, xab, _ in results:
            # Simple prediction: XOR of same bits
            predicted = ((xa >> bit) & 1) ^ ((xb >> bit) & 1)
            actual = (xab >> bit) & 1
            if predicted == actual:
                correct += 1

        accuracy = correct / len(results)
        marker = "***" if abs(accuracy - 0.5) > 0.1 else ""
        print(f"  Bit {bit:3}: XOR prediction accuracy = {accuracy:.3f} {marker}")


def analyze_distance_from_known():
    """If we know P(k), what can we infer about P(k+d) for small d?"""
    print("\n" + "=" * 70)
    print("DISTANCE-BASED INFERENCE")
    print("=" * 70)

    print("\nGiven P(k), can we narrow down candidates for P(k+d)?")
    print("This is what would reduce Kangaroo complexity.\n")

    # Precompute d*G for small d
    d_points = {}
    for d in range(1, 257):
        d_points[d] = scalar_mult(d, G)

    # For various k, check P(k+d) = P(k) + d*G
    print("Checking if X(k+d) - X(k) has structure based on d:")

    for d in [1, 2, 4, 8, 16, 32, 64, 128, 256]:
        diffs = []
        for k in range(1, 501):
            pk = scalar_mult(k, G)
            pkd = scalar_mult(k + d, G)
            diff = (pkd[0] - pk[0]) % P
            diffs.append(diff)

        # Check variance of diffs
        # If diffs are all similar, we found structure!
        unique_diffs = len(set(diffs))
        print(f"  d={d:3}: {unique_diffs} unique X differences out of 500")


def analyze_negation_symmetry():
    """Analyze -P = (x, -y) relationship."""
    print("\n" + "=" * 70)
    print("NEGATION SYMMETRY")
    print("=" * 70)

    print("\nFor P(k), we have P(N-k) = -P(k) = (X(k), -Y(k))")
    print("This means X(k) = X(N-k) - same X coordinate!\n")

    # This is actually exploitable - we only need to search half the range
    print("This is already exploited: search [0, N/2] covers all X values")

    # But what about partial ranges?
    print("\nFor puzzle with range [start, start+2^r]:")
    print("If range includes both k and N-k, we get 'free' collision")

    # Check for our test range
    for bits in [20, 30, 40, 50]:
        range_size = 1 << bits
        # For small ranges, N-k is very far from k
        # So this doesn't help unless range is close to N/2
        print(
            f"  {bits}-bit range: N-k distance = ~{(N - range_size) // (1 << bits)} range sizes away"
        )


def analyze_multipoint_relationships():
    """Look for relationships between multiple points."""
    print("\n" + "=" * 70)
    print("MULTI-POINT RELATIONSHIPS")
    print("=" * 70)

    print("\nChecking if knowing P(a), P(b), P(c) helps predict P(a+b-c):")

    # P(a+b-c) should equal P(a) + P(b) - P(c)
    # But can we predict X(a+b-c) from X(a), X(b), X(c)?

    samples = []
    for _ in range(1000):
        import random

        a = random.randint(1, 10000)
        b = random.randint(1, 10000)
        c = random.randint(1, min(a + b - 1, 10000))

        pa = scalar_mult(a, G)
        pb = scalar_mult(b, G)
        pc = scalar_mult(c, G)
        pabc = scalar_mult(a + b - c, G)

        samples.append((pa[0], pb[0], pc[0], pabc[0]))

    # Try various prediction formulas
    print("\nTrying prediction formulas for X(a+b-c):")

    formulas = [
        ("XOR all", lambda xa, xb, xc: xa ^ xb ^ xc),
        ("(xa + xb - xc) mod P", lambda xa, xb, xc: (xa + xb - xc) % P),
        (
            "(xa * xb / xc) mod P",
            lambda xa, xb, xc: (xa * xb * mod_inverse(xc, P)) % P if xc != 0 else 0,
        ),
    ]

    for name, formula in formulas:
        correct_bits = [0] * 8
        for xa, xb, xc, xabc in samples:
            try:
                predicted = formula(xa, xb, xc)
                for bit in range(8):
                    if ((predicted >> bit) & 1) == ((xabc >> bit) & 1):
                        correct_bits[bit] += 1
            except:
                pass

        accuracies = [c / len(samples) for c in correct_bits]
        max_acc = max(accuracies)
        print(f"  {name}: max bit accuracy = {max_acc:.3f}")


def main():
    print("=" * 70)
    print("DEEP PATTERN ANALYSIS FOR KANGAROO OPTIMIZATION")
    print("Looking for exploitable structure in secp256k1")
    print("=" * 70)

    analyze_power_of_2_keys()
    analyze_sequential_structure()
    analyze_halving_relationship()
    analyze_additive_structure()
    analyze_distance_from_known()
    analyze_negation_symmetry()
    analyze_multipoint_relationships()

    print("\n" + "=" * 70)
    print("CONCLUSIONS")
    print("=" * 70)
    print("""
Key findings for Kangaroo optimization:

1. NEGATION SYMMETRY: X(k) = X(N-k) - already known, halves search space

2. ADDITIVE PROPERTY: P(a+b) = P(a) + P(b) - this is what Kangaroo exploits

3. NO PREDICTABLE BITS: Cannot predict X(a+b) bits from X(a), X(b) bits

4. POTENTIAL OPTIMIZATIONS:
   - Better jump table design (current: powers of 2)
   - Batch inversion for faster point operations
   - Memory-time tradeoff (store more distinguished points)
   - GPU parallelization (already implemented)

5. THEORETICAL LIMITS:
   - O(√n) is believed optimal for generic group algorithms
   - Improvement requires exploiting non-generic structure
   - secp256k1 has no known weak structure
""")


if __name__ == "__main__":
    main()