Penseu en un escenari en què necessiteu protegir una caixa de seguretat bancària. Es considera absolutament inexpugnable sense clau, que us donen el primer dia de treball. El vostre objectiu és emmagatzemar la clau de manera segura.
Suposem que decidiu mantenir la clau amb vosaltres en tot moment, proporcionant accés a l'emmagatzematge segons sigui necessari. Però ràpidament us adonareu que aquesta solució no s'escala bé a la pràctica, perquè la vostra presència física és necessària cada vegada que obriu l'emmagatzematge. Què passa amb les vacances que et van prometre? A més, la pregunta és encara més espantosa: què passa si perds la teva única clau?
Tenint en compte les vacances, decideixes fer una còpia de la clau i confiar-la a un altre empleat. Tanmateix, enteneu que això tampoc és ideal. En duplicar el nombre de claus, també duplicaràs les possibilitats de robatori de claus.
Desesperat, destrueixes el duplicat i decideixes dividir la clau original per la meitat. Ara, podríeu pensar que dues persones de confiança amb fragments de clau haurien d'estar físicament presents per recollir la clau i obrir la volta. Això vol dir que un lladre ha de robar dues peces, cosa que és el doble de difícil que robar una clau. Tanmateix, aviat us adoneu que aquest esquema no és molt millor que només una clau, perquè si algú perd mitja clau, no es pot recuperar la clau completa.
El problema es pot resoldre amb una sèrie de claus i panys addicionals, però aquest enfocament requerirà ràpidament много claus i panys. Tu decideixes que el disseny ideal seria compartir la clau perquè la seguretat no depengui completament d'una sola persona. També conclou que hi ha d'haver un llindar per al nombre de fragments de manera que si es perd un fragment (o si una persona se'n va de vacances), tota la clau segueixi funcionant.
Com compartir un secret
Aquest tipus d'esquema de gestió de claus va ser pensat per Adi Shamir el 1979 quan va publicar el seu treball . L'article explica breument l'anomenat 
esquema de llindar per dividir de manera eficient un valor secret (com ara una clau criptogràfica). parts. Aleshores, quan i només quan almenys d' les peces estan muntades, podeu restaurar fàcilment el secret .
Des del punt de vista de la seguretat, una propietat important d'aquest esquema és que l'atacant no hauria de saber absolutament res tret que tingui almenys parts. Fins i tot la presència parts no haurien de proporcionar cap informació. Anomenem aquesta propietat seguretat semàntica.
Interpolació polinomial
Esquema de llindar de Shamir construït al voltant del concepte interpolació polinomial. Si no esteu familiaritzat amb aquest concepte, en realitat és bastant senzill. De fet, si alguna vegada has dibuixat punts en un gràfic i després els has connectat amb línies o corbes, ja ho has fet servir!
A través de dos punts pots dibuixar un nombre il·limitat de polinomis de grau 2. Per triar l'únic d'entre ells cal un tercer punt. Il·lustració:
Considereu un polinomi de grau u, . Si voleu representar aquesta funció en un gràfic, quants punts necessiteu? Bé, sabem que aquesta és una funció lineal que forma una línia i per tant necessita almenys dos punts. A continuació, considereu una funció polinomial de grau dos, . Aquesta és una funció quadràtica, de manera que calen almenys tres punts per traçar el gràfic. Què tal un polinomi de grau tres? Almenys quatre punts. I així successivament i així successivament.
El més interessant d'aquesta propietat és que, donat el grau de la funció polinomial i almenys punts, podem derivar punts addicionals per a aquesta funció polinomial. Anomenem l'extrapolació d'aquests punts addicionals interpolació polinomial.
Inventant un secret
Potser ja us heu adonat que aquí és on entra en joc l'esquema intel·ligent de Shamir. Diguem el nostre secret - És . Podem girar fins a un punt del gràfic i trobar una funció polinomial amb grau , que compleix aquest punt. Recordem-ho serà el nostre llindar de fragments requerits, de manera que si establim el llindar en tres fragments, haurem de triar una funció polinomial de grau dos.
El nostre polinomi tindrà la forma On и — nombres enters positius seleccionats aleatòriament. Només estem construint un polinomi amb grau , on el coeficient lliure - Aquest és el nostre secret , i per a cadascuna de les posteriors termes hi ha un coeficient positiu seleccionat aleatòriament. Si tornem a l'exemple original i assumim això , llavors obtenim la funció .
En aquest punt podem generar fragments connectant nombres enters únics a On (perquè és el nostre secret). En aquest exemple, volem distribuir quatre fragments amb un llindar de tres, de manera que generem punts aleatòriament i envia un punt a cadascuna de les quatre persones de confiança, els dipositaris de la clau. També ho fem saber a la gent , ja que es considera informació pública i és necessària per a la seva recuperació .
Recuperant el secret
Ja hem comentat el concepte d'interpolació polinòmica i com subjau a l'esquema de llindars de Shamir. . Quan tres dels quatre patrons volen restaurar , només cal interpolar amb els seus punts únics. Per fer-ho, poden determinar els seus punts i calculeu el polinomi d'interpolació de Lagrange utilitzant la fórmula següent. Si la programació us és més clara que les matemàtiques, llavors pi és essencialment un operador for, que multiplica tots els resultats, i sigma ho és for, que ho suma tot.
En podem resoldre-ho així i retornar la nostra funció polinomial original:
Perquè ho sabem , recuperació fet senzillament:
Utilitzant aritmètica entera no segura
Tot i que hem aplicat amb èxit la idea bàsica de Shamir , ens queda un problema que fins ara hem ignorat. La nostra funció polinòmica utilitza aritmètica entera no segura. Tingueu en compte que per cada punt addicional que un atacant obté al gràfic de la nostra funció, hi ha menys possibilitats per a altres punts. Podeu veure-ho amb els vostres propis ulls quan traceu un nombre creixent de punts per a una funció polinòmica mitjançant l'aritmètica de nombres enters. Això és contraproduent per al nostre objectiu de seguretat declarat, perquè l'atacant no hauria de saber absolutament res fins que ho tingui com a mínim fragments.
Per demostrar com de feble és el circuit aritmètic enter, considereu un escenari en què un atacant obtingués dos punts i coneix informació pública que . D'aquesta informació pot deduir , igual a dos, i introduïu els valors coneguts a la fórmula и .
Aleshores l'atacant pot trobar , comptant :
Ja que hem definit com a nombres enters positius seleccionats aleatòriament, hi ha un nombre limitat de possibles . Utilitzant aquesta informació, un atacant pot deduir , ja que qualsevol cosa superior a 5 servirà negatiu. Això resulta ser cert des que ho hem determinat
Aleshores, l'atacant pot calcular els valors possibles substituint в :
Amb opcions limitades per queda clar com de fàcil és seleccionar i comprovar els valors . Aquí només hi ha cinc opcions.
Resoldre el problema amb l'aritmètica de nombres enters no segurs
Per eliminar aquesta vulnerabilitat, Shamir suggereix utilitzar aritmètica modular, substituint en On и - el conjunt de tots els nombres primers.
Recordem ràpidament com funciona l'aritmètica modular. Un rellotge amb agulles és un concepte familiar. Ella utilitza un rellotge que és . Tan bon punt la mà de les hores passa les dotze, torna a la una. Una propietat interessant d'aquest sistema és que només mirant el rellotge no podem deduir quantes revolucions ha fet l'agulla de les hores. Tanmateix, si sabem que la maneta de les hores ha passat 12 quatre vegades, podem determinar completament el nombre d'hores que han passat mitjançant una fórmula senzilla On és el nostre divisor (aquí ), és el coeficient (quantes vegades el divisor entra al nombre original sense resta, aquí ), i és la resta, que normalment retorna una trucada d'operador mòdul (aquí ). Conèixer tots aquests valors ens permet resoldre l'equació per , però si ens perdem el coeficient, mai podrem restaurar el valor original.
Podem demostrar com això millora la seguretat del nostre esquema aplicant l'esquema al nostre exemple anterior i utilitzant . La nostra nova funció polinomial , i els nous punts . Ara els responsables de claus poden tornar a utilitzar la interpolació polinòmica per reconstruir la nostra funció, només que aquesta vegada les operacions de suma i multiplicació han d'anar acompanyades de reducció de mòdul (per exemple ).
Utilitzant aquest nou exemple, suposem que l'atacant va aprendre dos d'aquests nous punts, , i informació pública . Aquesta vegada, l'atacant, basant-se en tota la informació que té, dóna sortida a les següents funcions, on és el conjunt de tots els nombres enters positius, i representa el coeficient del mòdul .
Ara el nostre atacant torna a trobar , calculant :
Després ho torna a intentar substituint в :
Aquesta vegada té un problema greu. Falten valors de fórmula , и . Com que hi ha un nombre infinit de combinacions d'aquestes variables, no pot obtenir cap informació addicional.
Consideracions de seguretat
L'esquema secret per compartir de Shamir suggereix seguretat des del punt de vista de la teoria de la informació. Això vol dir que les matemàtiques són resistents fins i tot contra un atacant amb una potència de càlcul il·limitada. Tanmateix, el circuit encara conté diversos problemes coneguts.
Per exemple, l'esquema de Shamir no crea fragments a comprovar, és a dir, les persones poden presentar lliurement fragments falsos i interferir en la recuperació del secret correcte. Un conservador de fragments hostil amb informació suficient podria fins i tot produir un altre fragment canviant a la seva pròpia discreció. Aquest problema es resol utilitzant esquemes d'intercanvi de secrets verificables, com l'esquema de Feldman.
Un altre problema és que la longitud de qualsevol fragment és igual a la longitud del secret corresponent, de manera que la longitud del secret és fàcil de determinar. Aquest problema es pot resoldre de manera trivial farciment secret amb nombres arbitraris fins a una longitud fixa.
Finalment, és important tenir en compte que les nostres preocupacions de seguretat poden anar més enllà del propi disseny. Per a les aplicacions criptogràfiques del món real, sovint hi ha l'amenaça d'atacs de canal lateral on un atacant intenta extreure informació útil del temps d'execució de l'aplicació, la memòria cau, els bloquejos, etc. Si això és una preocupació, s'ha de tenir en compte durant el desenvolupament l'ús de mesures de protecció com ara funcions i cerques en temps constant, evitar que la memòria es desi al disc i una sèrie d'altres consideracions que estan fora de l'abast d'aquest article.
Demostració
En Hi ha una demostració interactiva de l'esquema d'intercanvi secret de Shamir. Demostració basada en la biblioteca , que en si mateix és un port de JavaScript del programa popular . Tingueu en compte que calcular valors grans , и pot trigar una mica.
Font: www.habr.com