Considere un escenario no que necesite protexer unha bóveda bancaria. Considérase absolutamente inexpugnable sen chave, que se lle entrega o primeiro día de traballo. O teu obxectivo é almacenar de forma segura a chave.
Digamos que decides manter a chave contigo en todo momento, proporcionando acceso ao almacenamento segundo sexa necesario. Pero axiña entenderás que tal solución non se escala ben na práctica, porque a túa presenza física é necesaria cada vez que abres o almacenamento. E as vacacións que che prometeron? Ademais, a pregunta é aínda máis aterradora: e se perdes a túa única chave?
Tendo en conta as túas vacacións, decides facer unha copia da chave e confiala a outro empregado. Non obstante, entendes que isto tampouco é o ideal. Ao duplicar o número de chaves, tamén duplicas as posibilidades de roubo de chaves.
Desesperado, destrúes o duplicado e decides dividir a clave orixinal pola metade. Agora, pensarías que dúas persoas de confianza con fragmentos de chave terían que estar fisicamente presentes para recoller a chave e abrir a bóveda. Isto significa que un ladrón necesita roubar dúas pezas, o que é dúas veces máis difícil que roubar unha chave. Non obstante, pronto entenderás que este esquema non é moito mellor que só unha chave, porque se alguén perde media chave, a chave completa non se pode recuperar.
O problema pódese resolver cunha serie de chaves e bloqueos adicionais, pero este enfoque requirirá rapidamente много chaves e pechaduras. Vostede decide que o deseño ideal sería compartir a chave para que a seguridade non dependa totalmente dunha persoa. Tamén conclúe que debe haber algún limiar para o número de fragmentos para que, se se perde un fragmento (ou se unha persoa vai de vacacións), toda a chave siga funcionando.
Como compartir un segredo
Este tipo de esquema de xestión de claves foi pensado por Adi Shamir en 1979 cando publicou o seu traballo . O artigo explica brevemente o chamado 
esquema de limiar para dividir de forma eficiente un valor secreto (como unha clave criptográfica). pezas. Entón, cando e só cando polo menos de as pezas están montadas, pode facilmente restaurar o segredo .
Desde o punto de vista da seguridade, unha propiedade importante deste esquema é que o atacante non debería saber absolutamente nada a menos que teña polo menos pezas. Incluso a presenza partes non deben proporcionar ningunha información. Chamámoslle esta propiedade seguridade semántica.
Interpolación polinómica
Esquema de limiar de Shamir construído arredor do concepto interpolación polinómica. Se non estás familiarizado con este concepto, en realidade é bastante sinxelo. De feito, se algunha vez debuxaches puntos nun gráfico e despois os conectaches con liñas ou curvas, xa o utilizaches!
A través de dous puntos pódese debuxar un número ilimitado de polinomios de grao 2. Para elixir o único deles, necesitas un terceiro punto. Ilustración:
Considere un polinomio de grao un, . Se queres representar esta función nun gráfico, cantos puntos necesitas? Ben, sabemos que esta é unha función lineal que forma unha liña e, polo tanto, necesita polo menos dous puntos. A continuación, considere unha función polinómica de grao dous, . Esta é unha función cuadrática, polo que son necesarios polo menos tres puntos para representar a gráfica. Que tal un polinomio de grao tres? Polo menos catro puntos. E así por diante.
O realmente interesante desta propiedade é que, dado o grao da función polinómica e polo menos puntos, podemos derivar puntos adicionais para esta función polinómica. Chamamos a extrapolación destes puntos adicionais interpolación polinómica.
Inventando un segredo
Quizais xa te deches conta de que aquí é onde entra en xogo o intelixente esquema de Shamir. Digamos o noso segredo - É . Podemos virar a un punto da gráfica e crea unha función polinómica con grao , que satisface este punto. Lembremos iso será o noso limiar de fragmentos necesarios, polo que se establecemos o limiar en tres fragmentos, debemos escoller unha función polinómica de grao dous.
O noso polinomio terá a forma onde и — Enteiros positivos seleccionados aleatoriamente. Só estamos construíndo un polinomio con grao , onde o coeficiente libre - Este é o noso segredo , e para cada unha das seguintes termos hai un coeficiente positivo seleccionado aleatoriamente. Se volvemos ao exemplo orixinal e asumimos que , entón obtemos a función .
Neste punto podemos xerar fragmentos conectando enteiros únicos en onde (porque é o noso segredo). Neste exemplo, queremos distribuír catro fragmentos cun limiar de tres, polo que xeramos puntos aleatoriamente e enviar un punto a cada unha das catro persoas de confianza, os custodios da chave. Tamén o avisamos á xente , xa que se considera información pública e é necesaria para a súa recuperación .
Recuperando o segredo
Xa comentamos o concepto de interpolación polinómica e como subxace ao esquema de limiar de Shamir . Cando tres dos catro administradores queiran restaurar , só precisan interpolar cos seus propios puntos únicos. Para iso, poden determinar os seus puntos e calcula o polinomio de interpolación de Lagrange mediante a seguinte fórmula. Se a programación é máis clara para ti que as matemáticas, entón pi é esencialmente un operador for, que multiplica todos os resultados, e sigma é for, que suma todo.
En podemos resolvelo así e devolver a nosa función polinómica orixinal:
Xa que o sabemos , recuperación feito simplemente:
Usando aritmética de enteiros inseguros
Aínda que aplicamos con éxito a idea básica de Shamir , quedamos cun problema que ata agora ignoramos. A nosa función polinómica usa aritmética de enteiros inseguros. Teña en conta que por cada punto adicional que obtén un atacante na gráfica da nosa función, hai menos posibilidades para outros puntos. Podes ver isto cos teus propios ollos cando representas un número crecente de puntos para unha función polinómica usando a aritmética enteira. Isto é contraproducente para o noso obxectivo de seguridade declarado, porque o atacante non debe saber absolutamente nada ata que o teña polo menos fragmentos.
Para demostrar o débil que é o circuíto aritmético enteiro, considere un escenario no que un atacante obtivo dous puntos e coñece información pública que . Desta información pode deducir , igual a dous, e conecte os valores coñecidos na fórmula и .
O atacante pode entón atopar , contando :
Xa que temos definido como enteiros positivos seleccionados aleatoriamente, hai un número limitado de posibles . Usando esta información, un atacante pode deducir , xa que calquera cousa maior que 5 servirá negativa. Isto resulta ser certo xa que o determinamos
O atacante pode entón calcular os posibles valores substituíndo в :
Con opcións limitadas para queda claro o fácil que é seleccionar e comprobar os valores . Só hai cinco opcións aquí.
Resolver o problema con aritmética de enteiros inseguros
Para eliminar esta vulnerabilidade, Shamir suxire usar aritmética modular, substituíndo en onde и - o conxunto de todos os números primos.
Lembremos rapidamente como funciona a aritmética modular. Un reloxo con agullas é un concepto familiar. Ela usa un reloxo que é . En canto a agulla das horas pasa das doce, volve á unha. Unha propiedade interesante deste sistema é que simplemente mirando o reloxo non podemos deducir cantas revolucións fixo a agulla das horas. Non obstante, se sabemos que a agulla das horas pasou 12 catro veces, podemos determinar completamente o número de horas que pasaron usando unha fórmula sinxela onde é o noso divisor (aquí ), é o coeficiente (cantas veces o divisor entra no número orixinal sen resto, aquí ), e é o resto, que normalmente devolve unha chamada de operador de módulo (aquí ). Coñecer todos estes valores permítenos resolver a ecuación para , pero se perdemos o coeficiente, nunca poderemos restaurar o valor orixinal.
Podemos demostrar como isto mellora a seguridade do noso esquema aplicando o esquema ao noso exemplo anterior e usando . A nosa nova función polinómica , e os novos puntos . Agora os encargados das chaves poden volver usar a interpolación polinómica para reconstruír a nosa función, só que esta vez as operacións de suma e multiplicación deben ir acompañadas de redución de módulo. (por exemplo: ).
Usando este novo exemplo, supoñamos que o atacante aprendeu dous destes novos puntos, , e información pública . Nesta ocasión, o atacante, baseándose en toda a información que ten, saca as seguintes funcións, onde é o conxunto de todos os enteiros positivos, e representa o coeficiente do módulo .
Agora o noso atacante volve atopar , calculando :
Despois volve tentalo substituíndo в :
Esta vez ten un grave problema. Faltan valores de fórmula , и . Dado que hai un número infinito de combinacións destas variables, non pode obter ningunha información adicional.
Consideracións de seguridade
O esquema de compartición secreta de Shamir suxire seguridade desde o punto de vista da teoría da información. Isto significa que as matemáticas son resistentes mesmo contra un atacante con capacidade de cálculo ilimitada. Non obstante, o circuíto aínda contén varios problemas coñecidos.
Por exemplo, o esquema de Shamir non crea fragmentos a revisar, é dicir, as persoas poden presentar libremente fragmentos falsos e interferir coa recuperación do segredo correcto. Un garda fragmento hostil con información suficiente podería incluso producir outro fragmento cambiando ao seu criterio. Este problema resólvese usando esquemas de compartición de segredos verificables, como o esquema de Feldman.
Outro problema é que a lonxitude de calquera fragmento é igual á lonxitude do segredo correspondente, polo que a lonxitude do segredo é fácil de determinar. Este problema pódese resolver por trivial acolchado secreto con números arbitrarios ata unha lonxitude fixa.
Finalmente, é importante ter en conta que as nosas preocupacións de seguridade poden estenderse máis alá do propio deseño. Para as aplicacións criptográficas do mundo real, adoita existir a ameaza de ataques de canle lateral nos que un atacante tenta extraer información útil do tempo de execución da aplicación, a caché, os fallos, etc. Se isto é un problema, durante o desenvolvemento débese considerar coidadosamente o uso de medidas de protección como funcións e buscas en tempo constante, evitando que a memoria se garde no disco e outras consideracións que están fóra do alcance deste artigo.
Demostración
En Hai unha demostración interactiva do esquema de compartición secreta de Shamir. Demostración baseada na biblioteca , que é un porto de JavaScript do popular programa . Teña en conta que calcular valores grandes , и pode levar un tempo.
Fonte: www.habr.com