Key Sharding (Secret Sharing)

  1import random
  2from typing import List, Tuple
  3
  4class ShamirSecretSharing:
  5    def __init__(self, prime):
  6        """Initialize with a large prime for modular arithmetic"""
  7        self.prime = prime
  8    
  9    def generate_shares(self, secret: int, threshold: int, num_shares: int) -> List[Tuple[int, int]]:
 10        """
 11        Generate shares for secret
 12        
 13        Args:
 14            secret: The secret to share
 15            threshold: Minimum shares needed to reconstruct
 16            num_shares: Total number of shares to create
 17        
 18        Returns:
 19            List of (x, y) share tuples
 20        """
 21        if threshold > num_shares:
 22            raise ValueError("Threshold cannot exceed number of shares")
 23        
 24        # Generate random coefficients for polynomial of degree (threshold - 1)
 25        coefficients = [secret] + [random.randrange(1, self.prime) 
 26                                    for _ in range(threshold - 1)]
 27        
 28        # Generate shares by evaluating polynomial at different points
 29        shares = []
 30        for x in range(1, num_shares + 1):
 31            y = self._evaluate_polynomial(coefficients, x)
 32            shares.append((x, y))
 33        
 34        return shares
 35    
 36    def _evaluate_polynomial(self, coefficients: List[int], x: int) -> int:
 37        """Evaluate polynomial at point x using Horner's method"""
 38        result = 0
 39        for coef in reversed(coefficients):
 40            result = (result * x + coef) % self.prime
 41        return result
 42    
 43    def reconstruct_secret(self, shares: List[Tuple[int, int]]) -> int:
 44        """
 45        Reconstruct secret from shares using Lagrange interpolation
 46        
 47        Args:
 48            shares: List of at least threshold (x, y) tuples
 49        
 50        Returns:
 51            The reconstructed secret
 52        """
 53        if len(shares) < 2:
 54            raise ValueError("Need at least 2 shares")
 55        
 56        # Lagrange interpolation at x=0 (to get constant term)
 57        secret = 0
 58        for i, (x_i, y_i) in enumerate(shares):
 59            numerator = 1
 60            denominator = 1
 61            
 62            for j, (x_j, _) in enumerate(shares):
 63                if i != j:
 64                    numerator = (numerator * (0 - x_j)) % self.prime
 65                    denominator = (denominator * (x_i - x_j)) % self.prime
 66            
 67            # Modular division using Fermat's little theorem
 68            lagrange_coef = (numerator * self._mod_inverse(denominator, self.prime)) % self.prime
 69            secret = (secret + y_i * lagrange_coef) % self.prime
 70        
 71        return secret
 72    
 73    def _mod_inverse(self, a: int, m: int) -> int:
 74        """Compute modular multiplicative inverse using extended Euclidean algorithm"""
 75        def extended_gcd(a, b):
 76            if a == 0:
 77                return b, 0, 1
 78            gcd, x1, y1 = extended_gcd(b % a, a)
 79            x = y1 - (b // a) * x1
 80            y = x1
 81            return gcd, x, y
 82        
 83        _, x, _ = extended_gcd(a % m, m)
 84        return (x % m + m) % m
 85
 86# Example usage
 87prime = 2**127 - 1  # Mersenne prime
 88sss = ShamirSecretSharing(prime)
 89
 90# Split secret into 5 shares, need 3 to reconstruct
 91secret = 42424242424242
 92shares = sss.generate_shares(secret, threshold=3, num_shares=5)
 93
 94print("Generated shares:")
 95for i, (x, y) in enumerate(shares, 1):
 96    print(f"  Share {i}: ({x}, {y})")
 97
 98# Reconstruct from any 3 shares
 99reconstructed = sss.reconstruct_secret(shares[:3])
100print(f"\nReconstructed secret: {reconstructed}")
101print(f"Original secret:      {secret}")
102print(f"Match: {reconstructed == secret}")

 1def encode_bytes_to_int(data: bytes) -> int:
 2    """Convert bytes to integer for secret sharing"""
 3    return int.from_bytes(data, byteorder='big')
 4
 5def decode_int_to_bytes(value: int, length: int) -> bytes:
 6    """Convert integer back to bytes"""
 7    return value.to_bytes(length, byteorder='big')
 8
 9# Example: Share a password
10password = b"MySecretPassword123!"
11secret_int = encode_bytes_to_int(password)
12
13# Generate shares
14shares = sss.generate_shares(secret_int, threshold=3, num_shares=5)
15
16# Reconstruct
17reconstructed_int = sss.reconstruct_secret(shares[:3])
18reconstructed_password = decode_int_to_bytes(reconstructed_int, len(password))
19
20print(f"Original:      {password}")
21print(f"Reconstructed: {reconstructed_password}")

 1def split_large_secret(data: bytes, chunk_size: int, threshold: int, num_shares: int):
 2    """Split large data into chunks and share each chunk"""
 3    chunks = [data[i:i+chunk_size] for i in range(0, len(data), chunk_size)]
 4    
 5    all_shares = [[] for _ in range(num_shares)]
 6    
 7    for chunk in chunks:
 8        secret_int = encode_bytes_to_int(chunk)
 9        chunk_shares = sss.generate_shares(secret_int, threshold, num_shares)
10        
11        for i, share in enumerate(chunk_shares):
12            all_shares[i].append(share)
13    
14    return all_shares
15
16def reconstruct_large_secret(shares_list: List[List[Tuple[int, int]]], chunk_size: int) -> bytes:
17    """Reconstruct large data from chunked shares"""
18    num_chunks = len(shares_list[0])
19    reconstructed_data = b''
20    
21    for chunk_idx in range(num_chunks):
22        chunk_shares = [shares[chunk_idx] for shares in shares_list]
23        secret_int = sss.reconstruct_secret(chunk_shares)
24        
25        # Handle last chunk (might be shorter)
26        if chunk_idx == num_chunks - 1:
27            # Determine actual length
28            chunk_bytes = decode_int_to_bytes(secret_int, chunk_size)
29            chunk_bytes = chunk_bytes.rstrip(b'\x00')  # Remove padding
30        else:
31            chunk_bytes = decode_int_to_bytes(secret_int, chunk_size)
32        
33        reconstructed_data += chunk_bytes
34    
35    return reconstructed_data

 1Shares: (1, 52), (2, 76), (3, 114)
 2
 3With 1 share (1, 52):
 4  - Secret could be 0, 1, 2, ..., any value
 5  - No information gained
 6
 7With 2 shares (1, 52), (2, 76):
 8  - Unique line passes through these points
 9  - Line intersects y-axis at secret value
10  - Secret fully determined: S = 42

 1class VerifiableSecretSharing(ShamirSecretSharing):
 2    def generate_shares_with_commitments(self, secret, threshold, num_shares, generator, prime):
 3        """Generate shares with commitments for verification"""
 4        coefficients = [secret] + [random.randrange(1, prime) 
 5                                    for _ in range(threshold - 1)]
 6        
 7        # Generate commitments: C_i = g^(a_i) mod p
 8        commitments = [pow(generator, coef, prime) for coef in coefficients]
 9        
10        # Generate shares
11        shares = []
12        for x in range(1, num_shares + 1):
13            y = self._evaluate_polynomial(coefficients, x)
14            shares.append((x, y))
15        
16        return shares, commitments
17    
18    def verify_share(self, share, commitments, generator, prime):
19        """Verify a share against commitments"""
20        x, y = share
21        
22        # Compute expected commitment: C = ∏ C_i^(x^i)
23        expected = 1
24        for i, commitment in enumerate(commitments):
25            expected = (expected * pow(commitment, pow(x, i, prime), prime)) % prime
26        
27        # Check: g^y = expected
28        actual = pow(generator, y, prime)
29        return actual == expected

 1def refresh_shares(old_shares, threshold, num_shares, prime):
 2    """Refresh shares without changing the secret"""
 3    # Generate random polynomial with zero constant term
 4    zero_poly_coeffs = [0] + [random.randrange(1, prime) 
 5                               for _ in range(threshold - 1)]
 6    
 7    # Add zero polynomial to each share
 8    new_shares = []
 9    for x, y in old_shares:
10        delta = evaluate_polynomial(zero_poly_coeffs, x, prime)
11        new_y = (y + delta) % prime
12        new_shares.append((x, new_y))
13    
14    return new_shares

 1Example: (3, 5) scheme with hierarchy
 2- CEO: weight 2 (counts as 2 shares)
 3- CFO: weight 2
 4- CTO: weight 1
 5- COO: weight 1
 6- Board Member: weight 1
 7
 8CEO + CTO = 3 shares ✓
 9CFO + Board Member = 3 shares ✓
10CTO + COO + Board = 3 shares ✓

1Problem: Single seed phrase is single point of failure
2
3Solution: (3, 5) secret sharing
4- Split seed phrase into 5 shares
5- Store in different locations
6- Need any 3 to recover wallet
7- Lose 2 shares? Still safe!

1Company root CA private key:
2- (3, 5) shares distributed to executives
3- No single person can sign certificates
4- Requires quorum for critical operations

1Compute f(x, y, z) where:
2- Alice has x
3- Bob has y
4- Charlie has z
5- Nobody learns others' inputs
6
7Use secret sharing to distribute inputs

1Database encryption key:
2- (2, 3) shares
3- Share 1: On-site safe
4- Share 2: Off-site backup facility
5- Share 3: Cloud HSM
6- Any 2 locations accessible → recover key

 1# Good primes for secret sharing
 2PRIMES = {
 3    'small': 2**31 - 1,           # Mersenne prime (32-bit)
 4    'medium': 2**61 - 1,          # Mersenne prime (64-bit)
 5    'large': 2**127 - 1,          # Mersenne prime (128-bit)
 6    'crypto': 2**256 - 189        # Large prime for cryptographic use
 7}
 8
 9# Choose based on secret size
10def choose_prime(secret_bytes):
11    secret_bits = len(secret_bytes) * 8
12    if secret_bits <= 30:
13        return PRIMES['small']
14    elif secret_bits <= 60:
15        return PRIMES['medium']
16    elif secret_bits <= 126:
17        return PRIMES['large']
18    else:
19        return PRIMES['crypto']

1import secrets
2
3def generate_secure_coefficients(threshold, prime):
4    """Use cryptographically secure RNG"""
5    return [secrets.randbelow(prime) for _ in range(threshold - 1)]

 1✅ DO:
 2- Use secure channels for distribution
 3- Encrypt shares during transmission
 4- Label shares clearly (but don't reveal secret)
 5- Document threshold and total shares
 6- Store shares in geographically distributed locations
 7
 8❌ DON'T:
 9- Send all shares via same channel
10- Store multiple shares together
11- Use predictable share identifiers
12- Forget which scheme was used

 1class ShareMetadata:
 2    def __init__(self, threshold, total_shares, share_id, scheme_version):
 3        self.threshold = threshold
 4        self.total_shares = total_shares
 5        self.share_id = share_id
 6        self.scheme_version = scheme_version
 7        self.created_at = datetime.now()
 8    
 9    def to_json(self):
10        return {
11            'threshold': self.threshold,
12            'total_shares': self.total_shares,
13            'share_id': self.share_id,
14            'scheme_version': self.scheme_version,
15            'created_at': self.created_at.isoformat()
16        }
17
18# Store metadata with each share (doesn't reveal secret)
19share_with_metadata = {
20    'metadata': metadata.to_json(),
21    'share': (x, y)
22}

1# ❌ BAD: Prime too small for secret
2secret = 2**128
3prime = 2**31 - 1  # Only 31 bits!
4# Secret will be reduced modulo prime, losing information
5
6# ✅ GOOD: Prime larger than secret
7secret = 2**128
8prime = 2**256 - 189  # 256 bits

1❌ Never reuse shares for different secrets
2- Reveals information about both secrets
3- Breaks information-theoretic security

1# ❌ BAD: Predictable randomness
2random.seed(12345)
3coefficients = [random.randint(1, prime) for _ in range(threshold-1)]
4
5# ✅ GOOD: Cryptographically secure
6coefficients = [secrets.randbelow(prime) for _ in range(threshold-1)]