Compartilhamento de segredos de Shamir: matemática polinomial

O Compartilhamento de Segredos de Shamir (1979) codifica o segredo como a interseção com o eixo y (f(0)) de um polinômio aleatório de grau (k-1) sobre um corpo finito. Quaisquer k pontos determinam unicamente o polinômio (interpolação de Lagrange); menos de k pontos não revelam nada.

Para compartilhar o segredo S com limiar k entre n participantes: escolha um primo p > S e n. Escolha coeficientes aleatórios a_1, ..., a_{k-1}. Defina f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). O participante i recebe a parcela (i, f(i)).

Segredo S=7, p=17, k=2 (polinômio linear). Escolha a_1=3. f(x)=7+3x mod 17. Parcelas: (1,10), (2,13), (3,16). Quaisquer dois pontos determinam a reta. f(0)=7. Um único ponto: infinitas retas possíveis, nenhuma informação sobre S.

Dado k pontos (x_1,y_1),...,(x_k,y_k), reconstitua f(0) usando Lagrange: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. Toda a aritmética é modular. Não há ponto flutuante — a reconstrução no corpo finito é exata.

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

Para k-1 partes, existe exatamente um polinômio de grau k-1 que passa por esses k-1 pontos para cada valor possível do segredo S. Portanto, ao conhecer k-1 partes, todos os valores de S em [0, p-1] são igualmente prováveis — nenhuma informação é revelada.

p deve ser maior que o segredo e n. Escolha comum: p = 2^127-1 (primo de Mersenne) para segredos de 128 bits. Isso garante que todas as partes caibam em 128 bits e que a aritmética seja eficiente. Como alternativa, use p=2^521-1 para segredos de 512 bits.

O SSS básico não oferece integridade às partes: um participante malicioso pode enviar uma parte falsa, fazendo com que o segredo seja reconstruído incorretamente. O VSS de Feldman (Compartilhamento Verificável de Segredos) publica compromissos g^{a_i} módulo p, permitindo verificar as partes sem revelar o polinômio.

As partes podem ser atualizadas periodicamente: gere um novo polinômio com o mesmo segredo S e redistribua novas partes; as partes antigas tornam-se inválidas. Um invasor que comprometa um participante depois da atualização obterá uma parte antiga inútil. Esse método é usado em sistemas de gerenciamento de chaves de longa duração.

ssss (linha de comando do Linux), python-secret-sharing e hashicorp/vault usam SSS para seu mecanismo de selagem; a carteira de hardware Trezor usa SSS para o backup da semente da carteira (SLIP-39). Todos operam sobre corpos primos grandes.

O SSS exige um distribuidor confiável para gerar e distribuir as partes (o distribuidor conhece o segredo). Um cenário sem distribuidor exige DKG (Geração Distribuída de Chaves). A reconstrução revela o segredo a quem tiver k partes — isso é eliminado por MPC ou assinaturas de limiar.

O SSS de Shamir codifica os segredos como interseções do polinômio com o eixo y. A interpolação de Lagrange recupera o segredo a partir de k partes. Ele oferece segurança perfeita no sentido da teoria da informação para menos de k partes. A seguir: compartilhamento visual e aditivo de segredos.