Rack de servidor com iluminação azul em data center seguro representando proteção de secrets com Shamir Secret Sharing

Shamir Secret Sharing em Python Puro: O Algoritmo Que Divide Um Segredo em 5 Pedaços e Precisa de 3 Para Reconstruir (Sem Nenhum Fragmento Revelar Nada Sozinho)

PorOlivetto

O Dia em que Perdi Um Backup Criptografado de 50 GB (E Por Que Isso Foi a Melhor Coisa Que Me Aconteceu)

Era 3 da manhã. Eu tinha acabado de perceber que a chave de descriptografia do meu backup mais importante — 50 GB de fotos de família, documentos fiscais de 7 anos, e o código-fonte de um projeto que levei 2 anos desenvolvendo — estava em um arquivo de texto no meu laptop. Laptop que eu tinha acabado de derrubar café em cima.

A ironia? Eu tinha feito tudo “certo”. Backup criptografado com AES-256-GCM. Chave gerada com entropia suficiente para resistir a ataques de força bruta por bilhões de anos. Chave armazenada em um único arquivo. Que agora estava molhado.

Consegui recuperar os dados (spoiler: o SSD sobreviveu), mas a lição ficou gravada: um único ponto de falha na gestão de secrets pode destruir anos de trabalho em segundos.

Isso me levou a descobrir o Shamir Secret Sharing — um algoritmo que divide um segredo em N pedaços (chamados “shares”) e precisa de apenas K deles para reconstruir o original. O mais impressionante? Nenhum share individual revela absolutamente nada sobre o segredo. É matemática pura, não mágica.

Neste artigo, vou te mostrar como implementei o Shamir Secret Sharing em Python puro — sem bibliotecas externas, sem dependências, só matemática e código limpo. Se você já passou perrengue com senhas perdidas, chaves extraviadas, ou simplesmente quer uma forma elegante de distribuir credenciais sensíveis, esse é o artigo que eu gostaria de ter lido antes de derrubar aquele café.

Vista aérea de switch de rede em data center representando distribuição de fragments no Shamir Secret Sharing
Distribuir secrets é como distribuir tráfego em um data center: cada caminho carrega uma parte, mas nenhum sozinho revela o todo.

O Que É Shamir Secret Sharing (E Por Que Você Deveria Se Importar)

Shamir Secret Sharing é um esquema criptográfico criado por Adi Shamir em 1979 (sim, o mesmo “S” do RSA). A ideia é simples, mas genial:

  • Você tem um segredo S (uma senha, uma chave criptográfica, um token)
  • Você divide S em N shares (por exemplo, 5)
  • Você define um threshold K (por exemplo, 3)
  • Qualquer combinação de K ou mais shares reconstrói S
  • Menos de K shares não revelam absolutamente nada sobre S

Na prática, isso significa que você pode:

  • Armazenar 5 shares em locais diferentes (servidor, pen drive, cofre físico, nuvem, papel)
  • Perder até 2 deles sem perder acesso ao segredo
  • Garantir que nenhum share individual seja útil se comprometido

É o equivalente digital de “precisa de 3 chaves diferentes para abrir o cofre do banco”. Só que aqui, as chaves são matemáticas, e o cofre é qualquer dado sensível que você quiser proteger.

A Matemática Por Trás: Polinômios e Interpolação de Lagrange

Aqui é onde a maioria dos tutoriais desiste de explicar e simplesmente diz “use esta biblioteca”. Mas se você quer realmente entender (e implementar do zero), precisamos falar de polinômios.

A ideia central é: um polinômio de grau K-1 é unicamente determinado por K pontos. Se você tem 3 pontos, existe exatamente um polinômio de grau 2 (parábola) que passa por todos eles. Com 4 pontos, um polinômio de grau 3. E assim por diante.

O algoritmo funciona assim:

  1. Escolha um segredo S (o termo constante do polinômio)
  2. Gere K-1 coeficientes aleatórios
  3. Construa o polinômio: P(x) = S + a₁x + a₂x² + … + a_{K-1}x^{K-1}
  4. Gere N pontos (x, P(x)) para N valores diferentes de x
  5. Cada ponto é um share

Para reconstruir, você usa interpolação de Lagrange — uma fórmula que, dados K pontos, reconstrói o polinômio original e avalia em x=0 para obter S.

Parece complicado? Na prática, são menos de 50 linhas de código Python. Vamos lá.

Implementação em Python Puro: Sem Dependências, Sem Mágica

Vamos implementar o Shamir Secret Sharing do zero. O código completo está abaixo, mas vou explicar cada parte.

Estrutura Básica

Precisamos de três funções principais:

  • generate_shares(secret, n, k): divide o segredo em N shares com threshold K
  • reconstruct_secret(shares): reconstrói o segredo a partir de K shares
  • lagrange_interpolation(points, x): interpola o polinômio e avalia em x

Campo Finito: A Chave para Segurança

Um detalhe crucial: todas as operações são feitas em um campo finito (finite field). Isso significa que trabalhamos com aritmética modular — tipicamente módulo um número primo grande.

Por que? Porque em um campo finito, cada share parece completamente aleatório. Sem modular, um atacante poderia extrair informações parciais dos shares. Com modular, cada share é indistinguível de ruído.

Vamos usar o primo 2¹²⁷ – 1 (um Mersenne prime), que é grande o suficiente para qualquer segredo razoável.

PRIME = (1 << 127) - 1  # 2^127 - 1

def mod_inverse(a, p):
    """Calcula o inverso modular de a mod p usando o algoritmo estendido de Euclides."""
    if a < 0:
        a = a % p
    g, x, _ = extended_gcd(a, p)
    if g != 1:
        raise ValueError("Inverso modular não existe")
    return x % p

def extended_gcd(a, b):
    """Algoritmo estendido de Euclides."""
    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

Gerando os Shares

Agora vamos gerar os shares. O segredo é o termo constante (coeficiente de x⁰). Os outros coeficientes são aleatórios.

import random

def generate_shares(secret, n, k, prime=PRIME):
    """
    Divide o segredo em n shares com threshold k.
    
    Args:
        secret: O segredo a ser dividido (inteiro)
        n: Número total de shares
        k: Threshold (mínimo de shares para reconstruir)
        prime: Número primo para o campo finito
    
    Returns:
        Lista de tuplas (x, y) representando os shares
    """
    if k > n:
        raise ValueError("Threshold k não pode ser maior que n")
    if secret >= prime:
        raise ValueError("Segredo muito grande para o primo escolhido")
    
    # Coeficientes aleatórios (exceto o termo constante, que é o segredo)
    coefficients = [secret] + [random.randrange(prime) for _ in range(k - 1)]
    
    # Gera n pontos (x, P(x))
    shares = []
    for i in range(1, n + 1):
        x = i
        y = sum(coeff * pow(x, idx, prime) for idx, coeff in enumerate(coefficients)) % prime
        shares.append((x, y))
    
    return shares

Reconstruindo o Segredo

Aqui entra a interpolação de Lagrange. Dados K pontos, reconstruímos o polinômio e avaliamos em x=0.

def lagrange_interpolation(points, x, prime=PRIME):
    """
    Interpola o polinômio definido pelos pontos e avalia em x.
    
    Args:
        points: Lista de tuplas (x_i, y_i)
        x: Ponto onde avaliar o polinômio
        prime: Número primo para o campo finito
    
    Returns:
        Valor do polinômio em x
    """
    result = 0
    for i, (xi, yi) in enumerate(points):
        # Calcula o polinômio base de Lagrange L_i(x)
        numerator = 1
        denominator = 1
        for j, (xj, _) in enumerate(points):
            if i != j:
                numerator = (numerator * (x - xj)) % prime
                denominator = (denominator * (xi - xj)) % prime
        
        # L_i(x) = numerator / denominator
        lagrange_basis = (numerator * mod_inverse(denominator, prime)) % prime
        result = (result + yi * lagrange_basis) % prime
    
    return result

def reconstruct_secret(shares, prime=PRIME):
    """
    Reconstrói o segredo a partir de k shares.
    
    Args:
        shares: Lista de tuplas (x, y) com pelo menos k shares
        prime: Número primo para o campo finito
    
    Returns:
        O segredo reconstruído (inteiro)
    """
    return lagrange_interpolation(shares, 0, prime)

Exemplo de Uso

Vamos testar com um exemplo prático:

# Exemplo de uso
if __name__ == "__main__":
    # Segredo: uma chave de 256 bits (representada como inteiro)
    secret = 0xDEADBEEF_CAFEBABE_12345678_9ABCDEF0
    
    # Divide em 5 shares, precisa de 3 para reconstruir
    shares = generate_shares(secret, n=5, k=3)
    
    print("Shares gerados:")
    for i, (x, y) in enumerate(shares, 1):
        print(f"  Share {i}: x={x}, y={y:032x}")
    
    # Reconstrói usando os primeiros 3 shares
    reconstructed = reconstruct_secret(shares[:3])
    
    print(f"\nSegredo original:   {secret:032x}")
    print(f"Segredo reconstruído: {reconstructed:032x}")
    print(f"Match: {secret == reconstructed}")
    
    # Testa com menos de 3 shares (deve falhar)
    wrong = reconstruct_secret(shares[:2])
    print(f"\nCom apenas 2 shares: {wrong:032x} (errado, como esperado)")

Se você rodar esse código, vai ver que:

  • Com 3 ou mais shares, o segredo é perfeitamente reconstruído
  • Com 2 ou menos shares, você obtém um valor completamente diferente (e inútil)

Caso de Uso Real: Distribuindo a Chave Mestra do Seu Cofre

Beleza, a matemática funciona. Mas como usar isso na prática? Aqui está o cenário que eu uso:

  1. Tenho uma chave mestra (master key) que descriptografa meu cofre de senhas
  2. Divido essa chave em 5 shares com threshold 3
  3. Distribuo os shares:
    • Share 1: arquivo criptografado no meu servidor pessoal
    • Share 2: pen drive no cofre físico
    • Share 3: impresso em papel, guardado em local seguro
    • Share 4: enviado para um familiar de confiança (sem contexto do que é)
    • Share 5: armazenado em um serviço de nuvem criptografado
  4. Se eu perder acesso a até 2 desses locais, ainda consigo reconstruir
  5. Se alguém comprometer um share, não obtém nenhuma informação útil

Segurança: O Que Pode Dar Errado (E Como Evitar)

Shamir Secret Sharing é matematicamente seguro, mas a implementação pode ter falhas. Aqui estão os principais vetores de ataque:

1. Geração de Números Aleatórios Fraca

Se os coeficientes não forem verdadeiramente aleatórios, um atacante pode prever os shares. Use sempre secrets ao invés de random para aplicações críticas:

import secrets

def generate_shares_secure(secret, n, k, prime=PRIME):
    """Versão com geração de números aleatórios criptograficamente segura."""
    coefficients = [secret] + [secrets.randbelow(prime) for _ in range(k - 1)]
    # ... resto do código igual

2. Shares Armazenados em Texto Claro

Cada share individual não revela o segredo, mas ainda é informação sensível. Armazene os shares criptografados com uma senha forte (ou use um cofre de senhas).

3. Threshold Muito Baixo

Se K=1, qualquer share reconstrói o segredo (derrotando o propósito). Se K=2, um atacante precisa de apenas 2 shares comprometidos. Escolha K com base no seu modelo de ameaça.

4. Segredo Muito Grande

O segredo deve ser menor que o primo. Para segredos maiores (como arquivos), divida em blocos e aplique Shamir em cada bloco independentemente.

Engenheira de TI com laptop em data center representando reconstrução de secrets distribuídos
Reconstruir um segredo a partir de shares distribuídos é como montar um quebra-cabeça onde cada peça está em um continente diferente.

Comparação: Shamir vs. Outras Abordagens

Shamir Secret Sharing não é a única forma de proteger secrets distribuídos. Vamos comparar:

Abordagem Prós Contras Quando usar
Shamir (K-de-N) Tolerante a falhas, matematicamente seguro Implementação mais complexa Secrets críticos, backup de chaves
Backup em múltiplos locais Simples, fácil de entender Cada backup é um ponto de falha Dados não-críticos, redundância básica
Hardware Security Module (HSM) Segurança física, proteção contra extração Caro, single point of failure Empresas, compliance regulatório
Multi-signature wallets Nativo em blockchain, auditoria transparente Limitado a criptomoedas Ativos digitais, contratos inteligentes

Para uso pessoal e pequenos times, Shamir oferece o melhor equilíbrio entre segurança, custo e flexibilidade.

Integração com o Mundo Real: Scripts e Automação

Aqui está um script bash que uso para dividir e reconstruir secrets na linha de comando:

#!/bin/bash
# split_secret.sh - Divide um segredo em shares

SECRET=$1
N=$2
K=$3

python3 - << EOF
from shamir import generate_shares

secret = int("$SECRET", 16)  # Assume hex
shares = generate_shares(secret, $N, $K)

for i, (x, y) in enumerate(shares, 1):
    print(f"SHARE_{i}={x}:{y:032x}")
EOF

#!/bin/bash
# reconstruct_secret.sh - Reconstrói um segredo a partir de shares

SHARES=("$@")

python3 - << EOF
from shamir import reconstruct_secret

shares = []
for share in "${SHARES[@]}":
    x, y = share.split(':')
    shares.append((int(x), int(y, 16)))

secret = reconstruct_secret(shares)
print(f"{secret:032x}")
EOF

Isso permite integrar Shamir em pipelines de CI/CD, scripts de backup, ou qualquer automação que precise lidar com secrets sensíveis.

Quando NÃO Usar Shamir Secret Sharing

Apesar de elegante, Shamir não é bala de prata. Evite quando:

  • Latência é crítica: A reconstrução envolve operações modulares pesadas. Para secrets usados frequentemente, prefira um cofre de senhas tradicional.
  • Colaboração em tempo real: Se múltiplas pessoas precisam acessar o segredo simultaneamente, Shamir não é ideal (cada reconstrução requer coordenação).
  • Segredos mutáveis: Se o segredo muda frequentemente, você precisa regenerar todos os shares. Para senhas que rotacionam, use um cofre dinâmico.
  • Ambientes hostis: Se o ambiente de reconstrução pode estar comprometido, Shamir não protege contra keyloggers ou screen capture.

Próximos Passos: Explorando Variações e Melhorias

Shamir Secret Sharing é a base, mas existem variações interessantes:

  • Verifiable Secret Sharing (VSS): Permite verificar se os shares são válidos sem revelar o segredo
  • Proactive Secret Sharing: Atualiza os shares periodicamente sem mudar o segredo (útil para revogar shares comprometidos)
  • Multi-secret Sharing: Divide múltiplos segredos em um único conjunto de shares

Se você curtiu esse artigo, recomendo explorar também:

Conclusão: Matemática > Confiança Cega

Shamir Secret Sharing é uma daquelas ferramentas que parece complexa demais até você implementar. Depois disso, parece óbvio demais para não usar.

A lição que tirei do meu quase-desastre com o backup molhado foi simples: nunca confie em um único ponto de falha para proteger algo importante. Seja uma chave criptográfica, uma senha mestra, ou qualquer dado sensível, distribua o risco.

E a beleza do Shamir é que ele não depende de confiança em terceiros, em hardware caro, ou em serviços de nuvem. Depende de matemática — e matemática não derruba café em cima de laptops.

Agora é sua vez: qual automação de segurança você gostaria de ver implementada do zero aqui no AutoMente? Me conta nos comentários que eu trago no próximo artigo.

Posts Similares