Vamos considerar um cenário em que é necessário garantir a segurança de um cofre bancário. Ele é considerado absolutamente impenetrável sem a chave que lhe é entregue no primeiro dia de trabalho. Seu objetivo é guardar essa chave de forma segura.

Suponha que você decidiu manter a chave com você o tempo todo, fornecendo acesso ao cofre conforme necessário. Mas você rapidamente perceberá que essa solução não escala bem na prática, porque sempre que for abrir o cofre, é necessário estar fisicamente presente. E quanto às férias que lhe prometeram? Além disso, há uma questão ainda mais assustadora: e se você perder a única chave?

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

Desesperado, você destrói o duplicado e decide dividir a chave original ao meio. Agora, você pensa, duas pessoas de confiança com fragmentos da chave precisam estar fisicamente presentes para juntar a chave e abrir o cofre. Isso significa que o ladrão precisa roubar dois fragmentos, o que é duas vezes mais difícil do que roubar uma chave só. No entanto, em breve você percebe que esse esquema não é muito melhor do que ter apenas uma chave, porque se alguém perder metade da chave, a chave completa não pode ser recuperada.

O problema pode ser resolvido com uma série de chaves e fechaduras adicionais, mas com esse método, rapidamente será necessário muitas chaves e fechaduras. Você decide que no esquema ideal a chave deve ser dividida de tal forma que a segurança não dependa completamente de uma única pessoa. Você também conclui que deve haver um determinado limiar de fragmentos, para que, ao perder um fragmento (ou se a pessoa se ausentar de férias), a chave inteira permaneça funcional.

Como dividir um segredo

Sobre esse tipo de esquema de gerenciamento de chaves, Adi Shamir pensou em 1979, quando publicou seu trabalho “Como dividir um segredo”. O artigo explica brevemente o que é chamado de esquema de limiar para a divisão eficaz de um valor secreto (por exemplo, uma chave criptográfica) em partes. Então, quando e somente quando pelo menos do partes são reunidas, o segredo pode ser facilmente recuperado. .

Do ponto de vista da segurança, uma característica importante deste esquema é que o invasor não deve saber absolutamente nada se ele não tiver pelo menos partes. Mesmo a posse de partes não deve fornecer nenhuma informação. Chamamos isso de segurança semântica.

Interpolação polinomial

O esquema de threshold de Shamir é baseado na concepção de interpolação polinomial.Se você não está familiarizado com esse conceito, na verdade, ele é bem simples. De modo geral, se você já desenhou pontos em um gráfico e, em seguida, conectou-os com linhas ou curvas, você já o utilizou!

Através de dois pontos, é possível traçar um número ilimitado de polinômios de grau 2. Para escolher um único deles, é necessário um terceiro ponto. Ilustração: Wikipedia

Vamos considerar um polinômio de grau um, . Se você quiser traçar essa função no gráfico, quantos pontos você precisa? Bem, sabemos que é uma função linear, que forma uma linha e, portanto, são necessárias pelo menos duas pontos. Em seguida, vamos considerar uma função polinomial de grau dois, . Esta é uma função quadrática, portanto, para traçar o gráfico, são necessários pelo menos três pontos. E quanto a um polinômio de grau três? Pelo menos quatro pontos. E assim por diante.

O que é realmente legal sobre essa propriedade é que, dado o grau da função polinomial e, pelo menos, pontos, podemos derivar pontos adicionais para essa função polinomial. A extrapolação desses pontos adicionais chamamos de interpolação polinomial..

Criação de segredos

Você provavelmente já percebeu que aqui entra em jogo o inteligente esquema de Shamir. Suponha que nosso segredo seja . Podemos transformar em um ponto no gráfico e criar uma função polinomial de grau , que satisfaça esse ponto. Lembre-se de que será nosso limite de fragmentos requeridos, então se definirmos o limite em três fragmentos, devemos escolher uma função polinomial de grau dois.

Nosso polinômio terá a forma , onde e - números inteiros positivos escolhidos aleatoriamente. Estamos apenas construindo um polinômio de grau , onde o coeficiente livre  é nosso segredo , e cada um dos fragmentos subsequentes o membros têm um coeficiente positivo escolhido aleatoriamente. Se voltarmos ao exemplo original e supormos que , então obteremos a função .

Neste ponto, podemos gerar os fragmentos, conectando números inteiros únicos em , onde (porque esse é o nosso segredo). Neste exemplo, queremos distribuir quatro fragmentos com o limite três, portanto, geramos aleatoriamente os pontos e enviamos um ponto para cada uma das quatro pessoas de confiança, os guardiões da chave. Também informamos às pessoas que , pois isso é considerado informação pública e é necessário para a recuperação .

Recuperação do segredo

Já discutimos o conceito de interpolação polinomial e que ele está na base do esquema de limite de Shamir . Quando quaisquer três dos quatro indivíduos de confiança desejam recuperar , eles precisam apenas interpolar com seus pontos únicos. Para isso, podem determinar seus pontos e calcular o polinômio de interpolação de Lagrange, usando a seguinte fórmula. Se você entende programação melhor do que matemática, então pi é basicamente o operador para, que multiplica todos os resultados, e sigma é para, que soma tudo.

Ao podemos resolver isso da seguinte forma e retornar nossa função polinomial original:

Como sabemos que , a recuperação é feita simplesmente:

Uso de aritmética inteira insegura

Embora tenhamos aplicado com sucesso a ideia central de Shamir , ainda temos um problema que ignoramos até agora. Nossa função polinomial usa aritmética inteira insegura. Note que para cada ponto adicional que um atacante obtém no gráfico de nossa função, resta menos oportunidades para outros pontos. Você pode ver isso por si mesmo ao construir o gráfico com um número crescente de pontos para uma função polinomial usando aritmética inteira. Isso é contraproducente para nosso objetivo declarado de segurança, porque um invasor não deve saber absolutamente nada até que tenha pelo menos fragmentos.

Para demonstrar o quão fraca é a esquema de aritmética inteira, consideremos um cenário em que um invasor obteve dois pontos e sabe a informação pública, que . A partir dessa informação, ele pode deduzir , igual a dois, e conectar os valores conhecidos na fórmula e .

Em seguida, o invasor pode encontrar , calculando :

Uma vez que definimos como números inteiros positivos escolhidos aleatoriamente, há um número limitado de possíveis . Com essa informação, o invasor pode deduzir , uma vez que qualquer coisa maior do que 5 tornará negativo. Isso se revela verdadeiro, pois definimos

Então o invasor pode calcular os valores possíveis , substituindo em :

Com um conjunto limitado de opções para torna-se claro o quão fácil é ajustar e verificar os valores . Aqui, existem apenas cinco opções.

Solução para o problema da aritmética inteira insegura

Para eliminar essa vulnerabilidade, Shamir propõe o uso de aritmética modular, substituindo para , onde e — o conjunto de todos os números primos.

Vamos lembrar rapidamente como funciona a aritmética modular. Relógios de ponteiro são uma ideia familiar. Eles utilizam horas que são . Assim que o ponteiro das horas passa das doze, ele retorna a uma. Uma propriedade interessante desse sistema é que, simplesmente olhando para o relógio, não conseguimos deduzir quantas voltas o ponteiro das horas deu. Contudo, se soubermos que o ponteiro das horas passou por 12 quatro vezes, podemos determinar completamente a quantidade de horas passadas usando uma fórmula simples , onde  — esse é o nosso divisor (aqui ),  — é o coeficiente (quantas vezes o divisor se encaixa no número original sem resto, aqui ), e  — é o resto, que geralmente é retornado pela chamada do operador de módulo (aqui ). Conhecer todos esses valores nos permite resolver a equação para , mas se perdermos o coeficiente, nunca conseguiremos recuperar o valor original.

Podemos demonstrar como isso melhora a segurança de nosso esquema, aplicando o esquema ao nosso exemplo anterior e usando . Nossa nova função polinomial , e os novos pontos . Agora os guardiões da chave podem usar novamente a interpolação polinomial para recuperar nossa função, apenas desta vez as operações de adição e multiplicação devem ser acompanhadas de redução pelo módulo (e.g. ).

Usando este novo exemplo, suponha que o invasor descobriu dois desses novos pontos, , e as informações públicas . Desta vez, o atacante, com base em todas as informações disponíveis, extrai as seguintes funções, onde  — é o conjunto de todos os números inteiros positivos, e representa o coeficiente do módulo .

Agora nosso criminoso novamente encontra , calculando :

Em seguida, ele tenta extrair novamente , substituindo em :

Desta vez, ele tem um sério problema. Faltam valores na fórmula , e . Como há um número infinito de combinações dessas variáveis, ele não pode obter mais informações.

Considerações de segurança

O esquema de compartilhamento de segredo de Shamir oferece segurança sob a perspectiva da teoria da informação. Isso significa que a matemática é robusta mesmo contra um atacante com poder computacional ilimitado. No entanto, o esquema ainda contém alguns problemas conhecidos.

Por exemplo, o esquema de Shamir não cria fragmentos verificáveis, ou seja, as pessoas podem livremente apresentar fragmentos falsos e dificultar a recuperação do segredo correto. Um guardião hostil de fragmentos com informações suficientes pode até gerar um outro fragmento, alterando ao seu critério. Este problema é resolvido com esquemas verificáveis de compartilhamento de segredo, como o esquema de Feldman.

Outro problema é que o comprimento de qualquer fragmento é igual ao comprimento do respectivo segredo, tornando fácil determinar o tamanho do segredo. Este problema é resolvido com uma preenchimento do segredo com números aleatórios até um comprimento fixo.

Finalmente, é importante notar que nossas preocupações de segurança podem ir além do próprio esquema. Para aplicações criptográficas reais, frequentemente existe a ameaça de ataques por canais laterais, onde um atacante tenta extrair informações úteis do tempo de execução do aplicativo, cache, falhas, etc. Se isso for uma preocupação, medidas de proteção, como funções e buscas com tempo de execução constante, devem ser cuidadosamente consideradas durante o desenvolvimento, prevenir a gravação de memória em disco, e pensar em uma série de outras coisas que vão além deste artigo.

Demonstração

Sobre nesta página há uma demonstração interativa do esquema de compartilhamento de segredo de Shamir. A demonstração é baseada na biblioteca ssss-js, que é um porto JavaScript do popular programa ssss. Observe que o cálculo de grandes valores , e pode levar algum tempo.

Fonte: habr.com