Uma introdução ao algoritmo criptográfico de compartilhamento de segredos de Shamir

O Compartilhamento de Segredos de Adi Shamir é um algoritmo criptográfico que permite que partes distintas compartilhem conjuntamente a propriedade de um único segredo, mantendo ações . O segredo original só pode ser reconstruído usando um número mínimo de compartilhamentos, o que permite que diferentes partes cooperem sem a necessidade de confiar plenamente umas nas outras.

Exemplo de Problema

Para ilustrar, vamos imaginar que uma família de quatro pessoas compartilhe uma única carteira Bitcoin. Esta carteira Bitcoin contém uma única chave privada que todos os membros da família possuem. Como existe uma única chave, qualquer membro da família pode usar essa chave para gastar todos os Bitcoins.

A família tem um problema: se cada um ficar com uma cópia, apenas uma de suas cópias precisa ser comprometida para que todas as moedas sejam roubadas. Se apenas um deles ficar com a chave, essa pessoa pode perdê-la ou decidir trair os outros membros da família.

Felizmente, um dos membros da família também é criptógrafo. Em vez de compartilhar ingenuamente a chave original, eles usam SSS (Shamir's secret sharing). A família cria quatro compartilhamentos e define um limite de três, com a chave Bitcoin como o segredo original. Agora, o plano deles tem as seguintes propriedades:

• Eles não armazenaram a chave bitcoin em um único local, o que dificulta o roubo
• Os membros da família precisam cooperar para gastar o Bitcoin, um membro da família não pode trair os outros
• Se um membro da família morrer ou perder sua parte, os outros três membros ainda poderão reconstruir a chave

Entendendo o Limiar

Todo esquema de compartilhamento Shamir tem um número total de compartilhamentos e um limite. O limite é o número de compartilhamentos necessários para reconstruir o segredo original. Por exemplo, com cinco compartilhamentos e um limite de três, você só precisa de três dos cinco compartilhamentos para calcular o segredo original.

A Matemática - Linhas

Uma das propriedades matemáticas fundamentais usadas no compartilhamento do segredo de Shamir é o fato de que são necessários k pontos para definir um polinômio de grau k - 1. Por exemplo:

• Apenas uma linha pode ser traçada entre dois pontos
• Apenas uma parábola possível passa pelos mesmos três pontos
• Apenas uma curva cúbica passa pelos mesmos quatro pontos
• Um número infinito de linhas pode ser traçado através do mesmo ponto
• Um número infinito de parábolas pode ser traçado através dos mesmos dois pontos

A matemática - passo a passo

Vamos construir um esquema para compartilhar nosso segredo 1954 ( S) com 4 ( n) compartilhamentos e um limite de 3 ( k) .

Primeiro, escolhemos aleatoriamente k - 1 inteiros positivos, portanto, em nosso caso, 2 inteiros positivos. Escolhemos aleatoriamente 43 e 12.

Então, construímos um polinômio da forma

 y = a0 + a1*x + a2*x^2

Onde a0 é o segredo e a1 e a2 são nossos números inteiros escolhidos aleatoriamente. Ficamos com:

 y = 1954 + 43x + 12x^2

Então, usamos esta fórmula para criar 4 pontos (shares) que damos a cada participante.

Compartilhar 1

(x, y) onde x = 1

a = 1954 + 43*1 + 12*1^2 = 2009

(1, 2009)

Compartilhar 2

(x, y) onde x = 2

a = 1954 + 43*2 + 12*2^2 = 2088

(2, 2088)

Compartilhar 3

(x, y) onde x = 3

a = 1954 + 43*3 + 12*3^2 = 2191

(3, 2191)

Compartilhar 4

(x, y) onde x = 4

a = 1954 + 43*4 + 12*4^2 = 2318

(4, 2318)

Reconstrução

Cada participante em nosso esquema agora possui um (x,y) ponto, que é uma única ação. Lembre-se de que definimos nosso limite para 3 e que 3 pontos definem uma parábola (polinômio de grau 2) perfeitamente. Isso significa que, se usarmos três pontos, podemos traçar uma parábola e calcular a0 (o segredo). Vamos supor que temos o controle das ações 1, 2 e 4.

Passo 1 - Traçar os pontos (shares) que controlamos

Passo 2 - Desenhe a parábola correspondente

Passo 3 - Encontre o ponto onde x=0 . Seu valor y é o segredo

No nosso caso, o segredo é 1954 .

Na verdade, não é tão simples. Precisamos de campos finitos.

Embora o exemplo com o qual trabalhamos acima seja ótimo para fins de demonstração, na verdade não é muito seguro. Para cada compartilhamento que um invasor obtém, ele obtém cada vez mais informações sobre o segredo. Embora dois pontos não descrevam perfeitamente uma parábola, eles ainda vazam informações críticas sobre a parábola.

A solução está na aritmética de campo finito . Ao plotar a função em um campo finito de tamanho suficiente, o gráfico do polinômio torna-se desarticulado e disperso, o que significa que o invasor é incapaz de fazer suposições fundamentadas sobre o caminho da função subjacente.

Adi Shamir

Adi Shamir é um criptógrafo israelense famoso por Shamir's Secret Sharing, mas também é um co-inventor do amplamente utilizado algoritmo RSA, sobre o qual a grande maioria da Internet é construída. Shamir nasceu em Tel Aviv e formou-se em matemática pela universidade de lá. Mais tarde, ele obteve seu mestrado e doutorado. graduou-se em Ciência da Computação pelo Instituto Weizmann em 1975 e 1977, respectivamente.