Shamir Secret Sharing

Uma carteira é um aplicativo ou dispositivo para receber e enviar bitcoins. Anna quer um backup que resista à perda de alguns registros. Escolhe três de cinco: são criadas cinco parcelas diferentes e quaisquer três válidas do mesmo conjunto recuperam o segredo. Ela pode perder duas, mas não três. A quantidade necessária é o limiar; em geral, k de n significa precisar de k das n parcelas criadas, tolerando a perda de n−k. Mas o limiar não reconhece o consentimento de Anna. Se outra pessoa obtiver três parcelas, ou seus detentores colaborarem, recuperará o mesmo segredo. Um limiar menor facilita a recuperação, mas também reduz o grupo necessário para fazê-la sem Anna. [1] [6]

Anna ganha pouco guardando os cinco arquivos em uma única conta na nuvem. A perda ou invasão da conta afeta todos de uma vez. Um backup exige uma distribuição cuidadosa, o registro do método e dos parâmetros, e um teste de recuperação em um dispositivo confiável. Se o plano também servir aos herdeiros, eles precisam saber o que procurar e como lidar com isso com segurança. Uma nova divisão aleatória do mesmo segredo S cria outro conjunto; parcelas antigas e novas não devem ser misturadas. Entretanto, um conjunto antigo suficiente continua recuperando S. Redistribuir as parcelas não revoga um backup utilizável já exposto nem altera o próprio segredo. [1] [4]

Na recuperação comum, o segredo inteiro volta a existir em um único dispositivo. Se ele estiver comprometido, um invasor poderá obter o segredo nesse momento. Se for uma Private Key, um valor numérico secreto usado para criar uma assinatura digital que autoriza um gasto, seu detentor poderá depois assinar sem reunir outras parcelas. Multisig, por sua vez, exige várias assinaturas conforme as condições daquele gasto. Também existe assinatura por limiar: um protocolo MPC adicional, um cálculo conjunto seguro entre participantes, permite que as parcelas contribuam para uma assinatura sem reconstruir a chave inteira. O NIST distingue essas situações. Uma parcela de Shamir sozinha não estabelece esse protocolo de assinatura. [3] [5] [6]

Dois programas com Shamir no nome podem não conseguir ler as parcelas um do outro. As operações matemáticas, a codificação dos valores, os identificadores e a associação ao conjunto precisam ser compatíveis. SLIP-39 é um padrão concreto baseado no método: acrescenta uma lista de palavras, metadados ou informações auxiliares, grupos, criptografia e verificações de erros. O princípio geral não é, portanto, uma instrução para dividir manualmente uma Seed Phrase existente. Antes de confiar uma carteira a esse backup, é necessário conhecer o formato compatível e verificar se o procedimento previsto realmente a recupera. [2]

Em três de cinco, é claro o que significa perder duas parcelas. Uma parcela danificada ou falsificada, porém, pode levar o cálculo básico a outro segredo em vez de indicar quantidade insuficiente. O método sozinho não autentica a origem das parcelas nem a honestidade de quem as criou. Detecção e correção de erros, e verifiable secret sharing, que permite verificar a correção da divisão, são camadas adicionais com pressupostos próprios. SLIP-39 acrescenta, por exemplo, uma soma de verificação e um valor de verificação chamado digest. Isso não significa que toda aplicação de Shamir Secret Sharing ofereça os mesmos controles, nem que uma soma correta comprove uma origem confiável. [2] [5]

No esquema ideal, menos de k parcelas completas não dão ao invasor nenhuma informação nova sobre S, mesmo com capacidade de cálculo ilimitada. Uma parcela não é um terço visível das palavras originais. Essa propriedade depende de aleatoriedade correta: os números da divisão são escolhidos independentemente e com igual probabilidade. Números previsíveis, sua reutilização ou vazamentos da memória do dispositivo mudam a situação. Dados adicionais de verificação, como o digest do SLIP-39, também precisam ser avaliados separadamente. E uma senha original fraca continua podendo ser adivinhada por outros meios, mesmo que seu backup tenha sido dividido. [1] [2]

Considere o pequeno segredo S=5 e a regra f(x)=5+3*x mod 17. mod 17 significa usar o resto da divisão por 17. Três parcelas são os pares (1,8), (2,11), (3,14): o primeiro número indica uma posição e o segundo, o valor calculado. Os dois primeiros permitem obter o incremento 3 e o segredo original 8−3=5. Qualquer um dos três pares possíveis de pontos recupera o mesmo cinco. O ponto (1,8) sozinho, porém, é compatível com qualquer S de 0 a 16 quando se escolhe a=8−S mod 17 como incremento. Esses números pequenos apenas ilustram a ideia; não constituem um backup para uma carteira real. [1]

A regra geral é f(x)=S+a1*x+…+a(k−1)*x^(k−1). Essa expressão é um polinômio; S é o segredo e os demais coeficientes são elementos independentes, escolhidos uniformemente ao acaso em um corpo finito, um ambiente com regras precisas de soma e multiplicação. Uma parcela é (x,f(x)), com cada x diferente e não nulo: x=0 revelaria S diretamente. A partir de k pontos, a interpolação de Lagrange calcula f(0), o segredo. Duas cópias do mesmo ponto não acrescentam informação. No corpo primo GF(p), a divisão comum é substituída pela multiplicação pelo inverso modular, cujo produto com o divisor é 1. GF(256) também usa operações diferentes de simplesmente tomar restos módulo 256; confundi-las seria um erro. [1]