Considere um cenário em que você precisa proteger um cofre de banco. É considerado absolutamente inexpugnável sem chave, que lhe é entregue logo no primeiro dia de trabalho. Seu objetivo é armazenar a chave com segurança.
Digamos que você decida manter a chave sempre com você, fornecendo acesso ao armazenamento conforme necessário. Mas você perceberá rapidamente que tal solução não é bem dimensionada na prática, porque sua presença física é necessária sempre que você abre o armazenamento. E as férias que lhe foram prometidas? Além disso, a questão é ainda mais assustadora: e se você perder sua única chave?
Pensando nas férias, você decide 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 duplicar o número de chaves, você também duplica as chances de roubo de chaves.
Em desespero, você destrói a duplicata e decide dividir a chave original pela metade. Agora, você pensaria que duas pessoas de confiança com fragmentos de chave teriam que estar fisicamente presentes para coletar a chave e abrir o cofre. Isto significa que um ladrão precisa roubar duas peças, o que é duas vezes mais difícil do que roubar uma chave. Porém, você logo percebe que esse esquema não é muito melhor do que apenas uma chave, pois se alguém perder meia chave, a chave completa não poderá ser recuperada.
O problema pode ser resolvido com uma série de chaves e fechaduras adicionais, mas esta abordagem exigirá rapidamente muitos chaves e fechaduras. Você decide que o design ideal seria compartilhar a chave para que a segurança não dependa inteiramente de uma pessoa. Você também conclui que deve haver algum limite para o número de fragmentos, de modo que, se um fragmento for perdido (ou se uma pessoa sair de férias), toda a chave permaneça funcional.
Como compartilhar um segredo
Este tipo de esquema de gerenciamento de chaves foi pensado por Adi Shamir em 1979, quando publicou seu trabalho . O artigo explica brevemente o chamado 
esquema de limite para dividir eficientemente um valor secreto (como uma chave criptográfica) em peças. Então, quando e somente quando pelo menos de as peças são montadas, você pode facilmente restaurar o segredo .
Do ponto de vista da segurança, uma propriedade importante deste esquema é que o invasor não deve saber absolutamente nada, a menos que tenha pelo menos peças. Mesmo a presença partes não devem fornecer nenhuma informação. Chamamos esta propriedade segurança semântica.
Interpolação polinomial
Esquema de limite de Shamir construído em torno do conceito interpolação polinomial. Se você não está familiarizado com esse conceito, na verdade é bastante simples. Na verdade, se você já desenhou pontos em um gráfico e depois os conectou com linhas ou curvas, você já o usou!
Através de dois pontos você pode desenhar um número ilimitado de polinômios de grau 2. Para escolher o único deles, você precisa de um terceiro ponto. Ilustração:
Considere um polinômio com grau um, . Se você quiser representar esta função em um gráfico, de quantos pontos você precisa? Bem, sabemos que esta é uma função linear que forma uma reta e por isso precisa de pelo menos dois pontos. A seguir, considere uma função polinomial com grau dois, . Esta é uma função quadrática, portanto, são necessários pelo menos três pontos para traçar o gráfico. Que tal um polinômio com grau três? Pelo menos quatro pontos. E assim por diante.
O mais legal dessa propriedade é que, dado o grau da função polinomial e pelo menos pontos, podemos derivar pontos adicionais para esta função polinomial. Chamamos a extrapolação desses pontos adicionais interpolação polinomial.
Inventando um segredo
Você já deve ter percebido que é aqui que entra em jogo o esquema inteligente de Shamir. Vamos contar nosso segredo - É . Nós podemos virar para um ponto no gráfico e crie uma função polinomial com grau , o que satisfaz este ponto. Lembremos que será nosso limite de fragmentos necessários, portanto, se definirmos o limite para três fragmentos, devemos escolher uma função polinomial com grau dois.
Nosso polinômio terá a forma Onde и — inteiros positivos selecionados aleatoriamente. Estamos apenas construindo um polinômio com grau , onde o coeficiente livre - Este é o nosso segredo , e para cada um dos subsequentes termos, há um coeficiente positivo selecionado aleatoriamente. Se voltarmos ao exemplo original e assumirmos que , então obtemos a função .
Neste ponto podemos gerar fragmentos conectando inteiros únicos em Onde (porque é o nosso segredo). Neste exemplo, queremos distribuir quatro fragmentos com um limite de três, então geramos pontos aleatoriamente e envie um ponto para cada uma das quatro pessoas de confiança, os guardiões da chave. Também informamos às pessoas que , uma vez que esta é considerada informação pública e é necessária para recuperação .
Recuperando o segredo
Já discutimos o conceito de interpolação polinomial e como ele fundamenta o esquema de limiar de Shamir . Quando quaisquer três dos quatro curadores quiserem restaurar , eles só precisam interpolar com seus próprios pontos únicos. Para fazer isso, eles podem determinar seus pontos e calcule o polinômio de interpolação de Lagrange usando a seguinte fórmula. Se a programação é mais clara para você do que a matemática, então pi é essencialmente um operador for, que multiplica todos os resultados, e sigma é for, que soma tudo.
em podemos resolvê-lo assim e retornar nossa função polinomial original:
Já que sabemos que , recuperação feito simplesmente:
Usando aritmética inteira insegura
Embora tenhamos aplicado com sucesso a ideia básica de Shamir , ficamos com um problema que ignorámos até agora. Nossa função polinomial usa aritmética inteira insegura. Observe que para cada ponto adicional que um invasor obtém no gráfico da nossa função, há menos possibilidades para outros pontos. Você pode ver isso com seus próprios olhos ao traçar um número crescente de pontos para uma função polinomial usando aritmética inteira. Isto é contraproducente para o nosso objetivo de segurança declarado, porque o invasor não deve saber absolutamente nada até ter pelo menos fragmentos.
Para demonstrar o quão fraco é o circuito aritmético inteiro, considere um cenário em que um invasor obteve dois pontos e conhece informações públicas que . A partir desta informação ele pode deduzir , igual a dois, e insira os valores conhecidos na fórmula и .
O invasor pode então encontrar , contando :
Já que definimos como números inteiros positivos selecionados aleatoriamente, há um número limitado de possíveis . Usando essas informações, um invasor pode deduzir , já que qualquer coisa maior que 5 servirá negativo. Isso acaba sendo verdade, pois determinamos
O invasor pode então calcular os valores possíveis substituindo в :
Com opções limitadas para fica claro como é fácil selecionar e verificar os valores . Existem apenas cinco opções aqui.
Resolvendo o problema com aritmética inteira insegura
Para eliminar esta vulnerabilidade, Shamir sugere o uso de aritmética modular, substituindo em Onde и - o conjunto de todos os números primos.
Vamos lembrar rapidamente como funciona a aritmética modular. Um relógio com ponteiros é um conceito familiar. Ela usa um relógio que é . Assim que o ponteiro das horas passa do meio-dia, ele retorna para um. Uma propriedade interessante deste sistema é que simplesmente olhando para o relógio não podemos deduzir quantas revoluções o ponteiro das horas deu. No entanto, se soubermos que o ponteiro das horas passou 12 quatro vezes, podemos determinar completamente o número de horas que se passaram usando uma fórmula simples Onde é o nosso divisor (aqui ), é o coeficiente (quantas vezes o divisor vai para o número original sem deixar resto, aqui ) e é o restante, que geralmente retorna uma chamada de operador de módulo (aqui ). Conhecer todos esses valores nos permite resolver a equação para , mas se perdermos o coeficiente, nunca poderemos restaurar o valor original.
Podemos demonstrar como isso melhora a segurança do nosso esquema aplicando o esquema ao nosso exemplo anterior e usando . Nossa nova função polinomial , e os novos pontos . Agora os guardiões das chaves podem mais uma vez usar a interpolação polinomial para reconstruir nossa função, só que desta vez as operações de adição e multiplicação devem ser acompanhadas pela redução do módulo (por exemplo: ).
Usando este novo exemplo, vamos supor que o invasor aprendeu dois desses novos pontos, e informações públicas . Desta vez, o invasor, com base em todas as informações que possui, executa as seguintes funções, onde é o conjunto de todos os inteiros positivos, e representa o coeficiente do módulo .
Agora nosso atacante encontra novamente , calculando :
Então ele tenta novamente substituindo в :
Desta vez ele tem um problema sério. Valores ausentes da fórmula , и . Como existe um número infinito de combinações dessas variáveis, ele não consegue obter nenhuma informação adicional.
Considerações de segurança
O esquema de partilha secreta de Shamir sugere segurança do ponto de vista da 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 a serem verificados, ou seja, as pessoas podem apresentar livremente fragmentos falsos e interferir na recuperação do segredo correto. Um detentor de fragmentos hostil com informações suficientes poderia até produzir outro fragmento alterando a seu próprio critério. Este problema é resolvido usando esquemas verificáveis de compartilhamento de segredos, como o esquema de Feldman.
Outro problema é que o comprimento de qualquer fragmento é igual ao comprimento do segredo correspondente, portanto é fácil determinar o comprimento do segredo. Este problema pode ser resolvido por trivial preenchimento segredo com números arbitrários até um comprimento fixo.
Finalmente, é importante notar que as nossas preocupações de segurança podem ir além do design em si. Para aplicações criptográficas do mundo real, muitas vezes existe a ameaça de ataques de canal lateral, onde um invasor tenta extrair informações úteis do tempo de execução da aplicação, cache, falhas, etc. Se isso for uma preocupação, deve-se considerar cuidadosamente durante o desenvolvimento o uso de medidas de proteção, como funções e pesquisas em tempo constante, evitando que a memória seja salva em disco e uma série de outras considerações que estão além do escopo deste artigo.
Programa demonstrativo
На Há uma demonstração interativa do esquema de compartilhamento secreto de Shamir. Demonstração baseada na biblioteca , que em si é uma versão JavaScript do popular programa . Observe que calcular valores grandes , и pode demorar algum tempo.
Fonte: habr.com