Como funciona o Shamir Secret Sharing: algoritmo e formato

Compartilhamento de segredo Shamir

Divida um segredo em N shares de modo que quaisquer M delas o recuperem e M − 1 ou menos não revelem nada. É o esquema de limiar que Adi Shamir publicou em 1979, aqui combinado com AES-256-GCM para que um resultado errado nunca passe por certo.

Para que serve

• Backup de seed phrase ou de senha mestra sem um ponto único de falha: perder uma share não perde o segredo, e roubar uma não o entrega.
• Herança e custódia compartilhada: por exemplo, 3 de 5 familiares ou sócios precisam se juntar.
• Chaves de recuperação de cofres, servidores ou contas de administrador.

A ideia de Shamir

Um polinômio de grau M − 1 fica determinado por M pontos, e nenhum conjunto menor de pontos o determina. Shamir esconde o segredo no termo constante:

f(x) = s + a₁·x + a₂·x² + … + a₍M−1₎·x^(M−1)

• s é o segredo; a₁ … a₍M−1₎ são sorteados ao acaso.
• A share número x é o par (x, f(x)), para x = 1, 2, …, N. O x = 0 nunca é entregue, porque f(0) = s.
• Com M pontos dá para reconstruir o polinômio e ler f(0). Com M − 1, todo segredo possível é igualmente compatível com os pontos conhecidos.

Exemplo pequeno (M = 2, números módulo 11)

Segredo s = 7, coeficiente sorteado a₁ = 3, então f(x) = 7 + 3x (mod 11):

• Com as shares 1 e 3: a reta que passa por (1, 10) e (3, 5) tem inclinação (5 − 10) / (3 − 1) = −5 · 2⁻¹ = −5 · 6 = 3 (mod 11), e cruza o eixo em 10 − 3 = 7. O segredo volta.
• Só com a share 1: para qualquer s de 0 a 10 existe uma reta que passa por (0, s) e (1, 10). O ponto sozinho não favorece nenhum valor, então não vaza nenhuma informação.

Aritmética em GF(2⁸)

A ferramenta não usa inteiros módulo um primo. Ela trabalha byte a byte no corpo finito GF(2⁸), o mesmo do AES (FIPS-197):

• os elementos são os 256 valores de um byte;
• soma e subtração são XOR;
• a multiplicação é a de polinômios com coeficientes em 1, reduzida módulo x⁸ + x⁴ + x³ + x + 1 (0x11b);
• todo elemento diferente de zero tem inverso, calculado como a²⁵⁴.

Cada byte da chave recebe o seu próprio polinômio aleatório, e a share guarda os valores de todos eles no mesmo x. Por isso o limite é 255 shares: há 255 valores de x não nulos.

Para recuperar, a ferramenta faz a interpolação de Lagrange em x = 0:

s = Σᵢ yᵢ · Πⱼ≠ᵢ xⱼ / (xⱼ ⊕ xᵢ)

Os pesos dependem só dos números das shares, então são calculados uma vez e aplicados a cada byte.

Cifrar e depois dividir

Dividir o segredo diretamente com Shamir tem dois problemas: cada share fica do tamanho do segredo, e M shares erradas ainda produzem bytes, sem nenhum aviso. A ferramenta faz assim:

1. sorteia uma chave de 256 bits, um nonce de 12 bytes e um set id de 4 bytes (crypto.getRandomValues);
2. cifra o segredo com AES-256-GCM. O cabeçalho (versão, M, N, set id) entra como dado autenticado (AAD);
3. divide só a chave com Shamir;
4. cada share leva a sua parte da chave mais o texto cifrado, que é igual em todas.

Assim o resultado só vale se o tag de 128 bits do GCM conferir. Uma share danificada, shares de menos ou um cabeçalho reetiquetado (por exemplo, trocar M = 3 por M = 2) nunca viram um segredo errado: a recuperação simplesmente falha.

Formato da share (v3)

Cada share é um texto em base64 URL-safe (sem =) com estes bytes:

O AAD do GCM é [0x00][0x03][M][N][set id]. Uma share tem cerca de 75 bytes + o tamanho do segredo, ou seja, uns 100 caracteres para um segredo curto.

O que a recuperação verifica

• Checksum por linha: enquanto você digita, cada linha é conferida. Uma share digitada errado aparece como Danificada antes de qualquer combinação.
• Mesmo set: linhas de outra divisão aparecem como Outro set. Duas linhas diferentes com o mesmo número aparecem como Conflito. Linhas repetidas contam uma vez.
• Tag GCM: o segredo só é mostrado se autenticar.
• Share adulterada: com mais de M shares que não abrem juntas, a ferramenta testa grupos de M (até 2.000 combinações) e aponta a share que ficou de fora de todos os grupos que abriram.
• Verificação ao gerar: antes de mostrar as shares, a ferramenta decodifica todas, confere que M abrem o segredo e que M − 1 não abrem.
• Autoteste: ao abrir, ela refaz uma ida e volta e abre um vetor congelado de shares. Se a aritmética ou o formato mudassem, shares guardadas ficariam inúteis, então a ferramenta trava antes disso.

Limites e compatibilidade

• Segredos de até 16 KB, porque cada share carrega o texto cifrado inteiro. Para arquivos grandes, cifre o arquivo e divida só a chave.
• De 2 a 255 shares, com 2 ≤ M ≤ N.
• As shares são compatíveis com o offline-tools (formato v3), nos dois sentidos. O formato v2, antigo e não autenticado, não é lido aqui.
• Não são compatíveis com ssss nem com SLIP-39: são outros formatos.

Boas práticas

• Guarde cada share em um lugar diferente, ou entregue cada uma a uma pessoa diferente. M shares juntas (na mesma gaveta, nuvem ou foto) equivalem ao segredo.
• Teste a recuperação logo depois de gerar, com M shares diferentes das que você copiou primeiro.
• Anote M, N e o set id junto de cada share. Eles já vão dentro do texto, mas ajudam quem for juntar as peças.
• O QR de cada share é prático para guardar no papel, mas qualquer foto dele expõe a share.
• Use um dispositivo confiável e sem extensões suspeitas na hora de digitar o segredo.