Considere o cenário em que é necessário garantir a segurança do cofre do banco. É considerado absolutamente inexpugnável sem uma chave, que é dada a você no primeiro dia de trabalho. Seu objetivo é salvar a chave com segurança.

Suponha que você decida manter a chave com você o tempo todo, fornecendo acesso à loja conforme necessário. Mas você perceberá rapidamente que essa solução na prática não é dimensionada normalmente, porque toda vez que você precisa de sua presença física para abrir o repositório. E as férias que lhe foram prometidas? Além disso, a pergunta é ainda mais assustadora: e se você perdesse uma única chave?

Com o pensamento de férias, você decidiu fazer uma cópia da chave e confiá-la a outro funcionário. No entanto, você entende que isso também não é o ideal. Ao dobrar o número de chaves, você também duplicou as possibilidades de roubo de chaves.

Desesperado, você destrói a duplicata e decide dividir a chave original ao meio. Agora, você pensa que duas pessoas de confiança com fragmentos de chave devem estar fisicamente presentes para coletar a chave e abrir a loja. Isso significa que o ladrão precisa roubar dois fragmentos, o que é duas vezes mais difícil do que roubar uma chave. No entanto, você logo perceberá que esse esquema não é muito melhor do que apenas uma chave, porque se alguém perder metade da chave, a chave completa não poderá ser restaurada.

O problema pode ser resolvido com uma série de chaves e bloqueios adicionais, mas com essa abordagem, você precisará rapidamente de muitas chaves e bloqueios. Você decide que, em um esquema ideal, precisará dividir a chave para que a segurança não dependa inteiramente de uma pessoa. Você também conclui que deve haver um certo limite para o número de fragmentos, para que, se um fragmento for perdido (ou se uma pessoa sair de férias), a chave inteira permanecerá funcional.

Como compartilhar um segredo

Esse tipo de esquema de gerenciamento de chaves foi pensado por Adi Shamir em 1979, quando ele publicou seu trabalho Como compartilhar um segredo . O artigo explica brevemente o chamado $$$(k, n)$esquema de limite para dividir efetivamente um valor secreto (por exemplo, uma chave criptográfica) em $$$n$peças. Então, quando e somente quando pelo menos $$$k$de $$$n$peças montadas, você pode facilmente restaurar o segredo $$$S$.

Do ponto de vista da segurança, uma propriedade importante desse esquema é que o invasor não deve saber absolutamente nada se não tiver pelo menos $$$k$peças. Disponibilidade uniforme $$$k - 1$partes não devem fornecer nenhuma informação. Chamamos essa propriedade de segurança semântica .

Interpolação polinomial

Esquema de limiares de Shamir $$$(k, n)$construído em torno do conceito de interpolação polinomial . Se você não está familiarizado com esse conceito, é realmente bastante simples. Em geral, se você desenhou pontos em um gráfico e os conectou com linhas ou curvas, então já o usou!


Um número ilimitado de polinômios de grau 2. pode ser traçado através de dois pontos: para escolher o único, você precisa de um terceiro ponto. Ilustração: Wikipedia

Considere um polinômio com grau um, $$$f (x) = x + 2$. Se você deseja plotar esta função em um gráfico, quantos pontos você precisa? Bem, sabemos que essa é uma função linear que forma uma linha e, portanto, são necessários pelo menos dois pontos. Em seguida, considere uma função polinomial com grau dois, $$$f (x) = x ^ 2 + 2x + 1$. Como é uma função quadrática, são necessários pelo menos três pontos para criar um gráfico. Que tal um polinômio com grau três? Pelo menos quatro pontos. E assim por diante e assim por diante.

O que é realmente interessante nessa propriedade é que, dado o grau da função polinomial e pelo menos $$$grau + 1$pontos, podemos derivar pontos adicionais para essa função polinomial. A extrapolação desses pontos adicionais é chamada interpolação polinomial .

Fazendo um segredo

Você já deve ter percebido que o esquema inteligente de Shamir entra em jogo aqui. Suponha que nosso segredo $$$S$É isso $$$42$. Podemos virar $$$S$para um ponto no gráfico $$$(0,42)$e chegar a uma função polinomial com grau $$$k-1$o que satisfaz esse ponto. Lembre-se que $$$k$será o nosso limite para os fragmentos necessários, portanto, se definirmos o limite para três fragmentos, devemos escolher uma função polinomial com grau dois.

Nosso polinômio assumirá a forma $$$f (x) = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1}$onde $$$a_0 = S$e $$$a_1, ..., a_ {k-1}$- inteiros positivos selecionados aleatoriamente. Estamos apenas construindo um polinômio com um grau $$$k-1$onde está o coeficiente livre $$$a_0$É o nosso segredo $$$S$e cada um dos seguintes $$$k-1$Os membros têm um coeficiente positivo selecionado aleatoriamente. Se você voltar ao exemplo original e assumir que $$$S = 42, k = 3, a_1, ..., a_ {k-1} = [3,5]$então temos a função $$$f (x) = 42 + 3x + 5x ^ 2$.

Nesta fase, podemos gerar fragmentos conectando $$$n$números inteiros únicos em $$$f (x) = 42 + 3x + 5x ^ 2$onde $$$x \ neq 0$(porque este é o nosso segredo). Neste exemplo, queremos distribuir quatro fragmentos com um limite de três, para gerar pontos aleatoriamente $$$(18, 1716), (27, 3768), (31, 4940), (35, 6272)$e envie um ponto para cada uma das quatro pessoas de confiança, responsáveis ​​pela manutenção. Também dizemos às pessoas que $$$k = 3$, pois é considerada informação pública e é necessária para recuperação $$$S$.

Recuperação Secreta

Já discutimos o conceito de interpolação polinomial e o fato de estar subjacente ao esquema de limiares de Shamir $$$(k, n)$. Quando qualquer um dos quatro proxies quiser recuperar $$$S$eles só precisam interpolar $$$f (0)$com seus próprios pontos únicos. Para fazer isso, eles podem determinar seus pontos $$$(x_1, y_1), ..., (x_k, y_k) = (18, 1716), (27, 3768), (31, 4940)$e calcule o polinômio de interpolação de Lagrange usando a seguinte fórmula. Se a programação é mais compreensível para você do que a matemática, então pi é essencialmente uma instrução for que multiplica todos os resultados, e sigma é uma instrução for que adiciona tudo.

$$

$$P (x) = \ sum_ {j = 1} ^ {k} p_j (x)$$

$$

$$P_j (x) = y_j \ prod _ {\ scriptstyle m = 1 \ no topo \ scriptstyle m \ neq j} ^ {k} \ frac {x-x_m} {x_j-x_m}$$

At $$$k = 3$podemos resolver isso da seguinte maneira e retornar nossa função polinomial original:

$$

$$\ begin {alinhado} P (x) & = {y_1} \ left ({x-x_2 \ over x_1-x_2} \ cdot {x-x_3 \ over x_1-x_3} \ right) + {y_2} \ left ( {x-x_1 \ over x_2-x_1} \ cdot {x - \ _ 3 \ over x_2-x_3} \ right) + {y_3} \ left ({x-x_1 \ over x_3-x_1} \ cdot {x-x_2 \ acima de x_3-x_2} \ right) \\ P (x) & = {1716} \ left ({x-27 \ over 18-27} \ cdot {x-31 \ over 18-31} \ right) + {3768 } \ left ({x-18 \ over 27-18} \ cdot {x-31 \ over 27-31} \ right) + {4940} \ left ({x-18 \ over 31-18} \ cdot {x -27 \ over 31-27} \ right) \\ P (x) & = 42 + 3x + 5x ^ 2 \ end {alinhado}$$

Porque sabemos que $$$S = P (0)$recuperação $$$S$realizada simplesmente:

$$

$$\ begin {alinhado} P (0) & = 42 + 3 (0) + 5 (0) ^ 2 \\ P (0) & = 42 \ end {alinhado}$$

Usando aritmética de número inteiro inseguro

Embora tenhamos aplicado com sucesso a idéia básica de Shamir $$$(k, n)$, ainda temos um problema que ignoramos até agora. Nossa função polinomial usa aritmética de número inteiro inseguro. Observe que, para cada ponto adicional que o atacante recebe no gráfico de nossa função, há menos opções para outros pontos. Você pode vê-lo com seus próprios olhos ao criar um gráfico com um aumento no número de pontos para uma função polinomial usando aritmética inteira. Isso é contraproducente para nossa meta de segurança declarada, porque o invasor não precisa aprender absolutamente nada até que tenha pelo menos $$$k$fragmentos.

Para demonstrar o quão fraco é o esquema com aritmética inteira, considere um cenário em que um invasor tenha dois pontos $$$(18, 1716), (27,3768)$e conhece informações públicas que $$$k = 3$. A partir dessa informação, ele pode deduzir $$$f (x)$igual a dois e conecte os valores conhecidos na fórmula $$$x$e $$$f (x)$.

$$

$$\ begin {alinhado} f (x) & = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1} \\ f (x) & = S + a_1x + a_2x ^ 2 \\ f (18) \ equiv 1716 & = S + a_118 + a_218 ^ 2 \\ f (27) \ equiv 3768 & = S + a_127 + a_227 ^ 2 \ end {alinhado}$$

Então o atacante pode encontrar $$$a_1$contando $$$f (27) - f (18)$:

$$

$$\ begin {alinhado} 3768 - 1716 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) \\ 2052 & = 9a_1 + 405a_2 \\ 9a_1 & = 2052 - 405a_2 \\ a_1 & = \ frac {2052 - 405a_2} {9} \\ a_1 & = 228 - 45a_2 \ end {alinhado}$$

Desde que identificamos $$$a_1, ..., a_ {k-1}$como números inteiros positivos selecionados aleatoriamente, há um número limitado de possíveis $$$a_2$. Usando essas informações, um invasor pode inferir $$$a_2 \ in [1,2,3,4,5]$, já que tudo o que for maior que 5 fará $$$a_1$negativo. Isso acaba sendo verdade, como determinamos $$$a_2 = 5$

Então o atacante pode calcular os valores possíveis $$$S$substituindo $$$a_1$em $$$f (18)$:

$$

$$\ begin {alinhado} 1716 & = S + a_118 + a_218 ^ 2 \\ 1716 & = S + 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 \\ 1716 - S & = 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 \\ -S & = 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 - 1716 \\ -S & = 4104 - 810a_2 + a_218 ^ 2 - 1716 \\ S & = -4104 + 810a_2 - a_218 ^ 2 + 1716 \\ S & = 810a_2 - 324a_2 -2388 \\ S & = 486a_2 - 2388 \ end {alinhado}$$

Com uma seleção limitada de opções para $$$a_2$fica claro como é fácil escolher e verificar os valores $$$S$. Existem apenas cinco opções.

Resolvendo o problema com aritmética de número inteiro inseguro

Para eliminar essa vulnerabilidade, Shamir sugere o uso de aritmética modular, substituindo $$$f (x)$em $$$f (x) \ mod p$onde $$$p \ in \ mathbb {P}: p> S, p> n$e $$$\ mathbb {P}$- o conjunto de todos os números primos.

Lembre-se rapidamente de como a aritmética modular funciona. Um relógio com flechas já é um conceito familiar. Ela usa relógios que são $$$\ mod 12$. Assim que o ponteiro das horas passa doze, volta para um. Uma propriedade interessante desse sistema é que, simplesmente olhando o relógio, não podemos deduzir quantas rotações o ponteiro das horas fez. No entanto, se soubermos que o ponteiro das horas passou 12 vezes quatro vezes, podemos determinar completamente o número de horas decorridas usando uma fórmula simples $$$a = mq + r$onde $$$m$É o nosso divisor (aqui $$$m = 12$), $$$q$É o coeficiente (quantas vezes o divisor sem o resto vai para o número original, aqui $$$q = 4$) e $$$r$É o restante, que geralmente retorna o módulo de chamada do operador (aqui $$$r = 1,5$) Conhecer todos esses valores nos permite resolver a equação para $$$a = 49,5$mas se pularmos o coeficiente, nunca poderemos restaurar o valor original.

Você pode demonstrar como isso melhora a segurança do nosso circuito aplicando o circuito ao nosso exemplo anterior e usando $$$p = 73$. Nossa nova função polinomial $$$f '(x) = 42 + 3x + 5x ^ 2 \ mod 73$e novos pontos $$$(18, 37), (27, 45), (31, 49), (35, 67)$. Agora, os detentores de chaves podem mais uma vez usar a interpolação polinomial para restaurar nossa função, só que desta vez as operações de adição e multiplicação devem ser acompanhadas por uma redução de módulo $$$p$(por exemplo $$$48 + 93 \ mod 73 = 68$)

Usando este novo exemplo, suponha que o invasor reconheceu dois desses novos pontos, $$$(18, 37), (27, 45)$e informações públicas $$$k = 3, p = 73$. Desta vez, o atacante, com base em todas as informações que possui, exibe as seguintes funções, onde $$$\ mathbb {N}$É o conjunto de todos os números inteiros positivos e $$$q_x$representa o coeficiente do módulo $$$f '(x)$.

$$

$$\ begin {alinhado} f '(x) & = S + a_1x + a_2x ^ 2 \ mod 73 \\ f' (x) & = S + a_1x + a_2x ^ 2 - 73q_x: q_x \ in \ mathbb {N} \\ f '(18) \ equiv 37 & = S + a_118 + a_218 ^ 2 - 73q_ {18} \\ f' (27) \ equiv 45 & = S + a_127 + a_227 ^ 2 - 73q_ {27} \ end {alinhado}$$

Agora nosso atacante encontra novamente $$$a_1$por computação $$$f '(27) - f' (18)$:

$$

$$\ begin {alinhado} 45 - 37 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) + (-73q_ {27} - (-73q_ {18})) \\ 8 & = 9a_1 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ -9a_1 & = -8 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ 9a_1 & = 8 - 405a_2 - 73 (q_ {18} - q_ {27}) \\ a_1 & = \ frac {8 - 405a_2 - 73 (q_ {18} - q_ {27})} {9} \\ a_1 & = \ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ end {alinhado}$$

Então ele novamente tenta se retirar $$$S$substituindo $$$a_1$em $$$f '(18)$:

$$

$$\ begin {alinhado} 37 & = S + 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ right) + a_218 ^ 2 - 73q_ {18} \\ -S & = 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ right) + a_218 ^ 2 - 73q_ {18} - 37 \\ S & = -18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27} ) \ right) - 324a_2 + 73q_ {18} + 37 \\ S & = 486a_2 + 21 + 219q_ {18} - 146q_ {27} \ end {alinhado}$$

Desta vez, ele tem um problema sério. Não há valores na fórmula $$$a_2$, $$$q_ {18}$e $$$q_ {27}$. Como há um número infinito de combinações dessas variáveis, ele não pode receber nenhuma informação adicional.

Considerações de segurança

O esquema de compartilhamento secreto de Shamir oferece segurança em termos de teoria da informação . Isso significa que a matemática é resistente mesmo contra um invasor com poder computacional ilimitado. No entanto, o circuito ainda contém vários problemas conhecidos.

Por exemplo, o esquema de Shamir não cria fragmentos de teste , ou seja, as pessoas podem apresentar fragmentos falsos livremente e interferir na restauração do segredo correto. Um detentor de fragmentos hostil com informações suficientes pode até produzir outro fragmento alterando $$$S$a seu critério. Esse problema é resolvido usando esquemas de compartilhamento secreto verificados , como o esquema de Feldman.

Outro problema é que o tamanho de qualquer fragmento é igual ao tamanho do segredo correspondente, de modo que é fácil determinar o tamanho do segredo. Esse problema é resolvido preenchendo trivialmente o segredo com números arbitrários até um comprimento fixo.

Por fim, é importante observar que nossas preocupações com segurança podem ir além do escopo do próprio esquema. Para aplicativos criptográficos da vida real, geralmente há uma ameaça de ataques a canais de terceiros quando um invasor tenta extrair informações úteis do tempo de execução, cache, falhas do aplicativo, etc. Se isso for uma preocupação, considere cuidadosamente o uso de salvaguardas durante o desenvolvimento, como funções e pesquisa com um tempo de execução constante, impeça o armazenamento de memória no disco e considere várias outras coisas que estão além do escopo deste artigo.

Demo

Esta página possui uma demonstração interativa do esquema de compartilhamento secreto de Shamir. A demonstração foi feita com base na biblioteca ssss-js , que por si só é a porta JavaScript do popular programa ssss . Observe que o cálculo de valores grandes $$$k$, $$$n$e $$$S$pode levar algum tempo.