Introdução
Implementar o sistema de compartilhamento de segredos de Shamir (veja a descrição na Wikipedia).
A idéia é resumida a seguir.
Para distribuir um segredo para n participantes, com quórum q + 1 (ou seja, q + 1 pessoas conseguem abrir o segredo, mas menos que q + 1 pessoas nada podem fazer):
- crie um polinômio aleatório de grau q com termo constante S. Isto pode ser feito selecionando aleatoriamente q coeficientes a1, a2, …, aq. O polinômio será aqxq + ⋯ + a1x + S.
- selecione aleatoriamente n pontos do polinômio
- dê um ponto a cada participante
Para abrir o segredo:
- quando q + 1 participantes quiserem, podem usar seus pontos para determinar o polinômio -- inclusive o termo constante, S.
- para isto, usam o polinômio interpolador de Lagrange
É necessário fazer mais que a implementação simples. Pode-se escolher entre
- usar corpos finitos para tornar o esquema verdadeiramente seguro (peça ajuda com isto! -- um corpo finito é um corpo (como $\reals$), mas com um número finito de elementos)
- implementar algum tipo de verificação para que não seja possível a um participante fraudar o sistema (peça ajuda com isto também!)
Mais detalhes
Na discussão que segue, "x (mod p)" é "o resto da divisão de x por p".
Distribuição
- Faça a0 ter o valor do segredo a ser guardado.
- Escolha t − 1 números menores que p: a1, …, at − 1, de forma que a(x) = a0 + a1x + x2x2 + ⋯ + at − 1xt − 1 (mod p)
- Para cada participante i, com 1 ≤ i ≤ w, calcule a(i) e entregue a ele o par (i, a(i)).
Combinando de volta o segredo
Par obter o segredo com k chaves, usamos interpolação de lagrange:
- l(x) = l1(x) + l2(x) + ⋯ + ln(x)
- onde: lj(x) = yj∏1 ≤ x ≤ t; k ≠ j(x − xk)/(xj − xk)
Como só queremos o polinômio no zero, p(0), simplificamos para
- l(0) = yj[l1(0) + l2(0) + ⋯ + ln(0)]
- lj(0) = ∏1 ≤ x ≤ t; k ≠ j(xk)/(xk − xj)
SUGESTÃO:
- função para criar o polinômio aleatório
- função para calcular o polinômio em um ponto
função para distribuir parcela do segredo
- função
l(j,parcelas) que calcula lj(0)
função combina(parcelas) que calcula l(0), resultando em a0
Depois,
- função para garantir que, se um participante mudar sua parcela de propósito a fim de que um segredo errado seja aberto, ele seja imediatamente identificado.