Luați în considerare un scenariu în care trebuie să asigurați un seif bancar. Este considerat absolut inexpugnabil fără cheie, care ți se dă chiar în prima zi de muncă. Scopul tău este să păstrezi în siguranță cheia.
Să presupunem că decideți să păstrați cheia cu dvs. în orice moment, oferind acces la spațiu de stocare după cum este necesar. Dar îți vei da repede seama că o astfel de soluție nu se scalează bine în practică, deoarece prezența ta fizică este necesară de fiecare dată când deschideți depozitul. Dar vacanța care ți s-a promis? În plus, întrebarea este și mai înfricoșătoare: ce se întâmplă dacă ți-ai pierde singura cheie?
Având în vedere vacanța, decizi să faci o copie a cheii și să o încredințezi altui angajat. Totuși, înțelegeți că nici acest lucru nu este ideal. Dubland numărul de chei, dublezi și șansele de furt de chei.
În disperare, distrugi duplicatul și decideți să împărțiți cheia originală în jumătate. Acum, ați crede că doi oameni de încredere cu fragmente de cheie ar trebui să fie prezenți fizic pentru a colecta cheia și a deschide seiful. Aceasta înseamnă că un hoț trebuie să fure două piese, ceea ce este de două ori mai dificil decât să fure o cheie. Cu toate acestea, vă dați seama curând că această schemă nu este cu mult mai bună decât o singură cheie, deoarece dacă cineva pierde o jumătate de cheie, cheia completă nu poate fi recuperată.
Problema poate fi rezolvată cu o serie de chei și încuietori suplimentare, dar această abordare va necesita rapid multe chei și încuietori. Decizi că designul ideal ar fi să partajezi cheia, astfel încât securitatea să nu se bazeze în întregime pe o singură persoană. De asemenea, ajungeți la concluzia că trebuie să existe un anumit prag pentru numărul de fragmente, astfel încât dacă un fragment este pierdut (sau dacă o persoană pleacă în vacanță), întreaga cheie să rămână funcțională.
Cum să împărtășești un secret
La acest tip de schemă de management cheie a fost gândit de Adi Shamir în 1979, când și-a publicat lucrarea . Articolul explică pe scurt așa-numitul 
schema de prag pentru împărțirea eficientă a unei valori secrete (cum ar fi o cheie criptografică) în părți. Atunci, când și numai când măcar de piesele sunt asamblate, puteți restabili cu ușurință secretul .
Din punct de vedere al securității, o proprietate importantă a acestei scheme este că atacatorul nu ar trebui să știe absolut nimic decât dacă are cel puțin părți. Chiar și prezența piesele nu ar trebui să ofere nicio informație. Numim această proprietate securitate semantică.
Interpolare polinomială
Schema de prag Shamir construit în jurul conceptului interpolare polinomială. Dacă nu ești familiarizat cu acest concept, este de fapt destul de simplu. De fapt, dacă ați desenat vreodată puncte pe un grafic și apoi le-ați conectat cu linii sau curbe, l-ați folosit deja!
Prin două puncte poți trage un număr nelimitat de polinoame de gradul 2. Pentru a alege singurul dintre ele, ai nevoie de un al treilea punct. Ilustrare:
Să considerăm un polinom cu gradul unu, . Dacă doriți să reprezentați această funcție pe un grafic, de câte puncte aveți nevoie? Ei bine, știm că aceasta este o funcție liniară care formează o linie și deci are nevoie de cel puțin două puncte. În continuare, considerăm o funcție polinomială cu gradul doi, . Aceasta este o funcție pătratică, deci sunt necesare cel puțin trei puncte pentru a reprezenta graficul. Ce zici de un polinom cu gradul trei? Cel puțin patru puncte. Și așa mai departe și așa mai departe.
Lucrul cu adevărat cool despre această proprietate este că, având în vedere gradul funcției polinomiale și cel puțin puncte, putem obține puncte suplimentare pentru această funcție polinomială. Numim extrapolarea acestor puncte suplimentare interpolare polinomială.
Inventarea unui secret
Poate ți-ai dat seama deja că aici intervine schema inteligentă a lui Shamir. Să spunem secretul nostru - E . Ne putem întoarce până la un punct din grafic și veniți cu o funcție polinomială cu grad , care satisface acest punct. Să ne amintim asta va fi pragul nostru de fragmente necesare, deci dacă setăm pragul la trei fragmente, trebuie să alegem o funcție polinomială cu gradul doi.
Polinomul nostru va avea forma Unde и — numere întregi pozitive alese aleatoriu. Construim doar un polinom cu grad , unde coeficientul liber - Acesta este secretul nostru , iar pentru fiecare dintre cele ulterioare termeni există un coeficient pozitiv selectat aleatoriu. Dacă ne întoarcem la exemplul original și presupunem că , apoi obținem funcția .
În acest moment putem genera fragmente prin conectare numere întregi unice în Unde (pentru că este secretul nostru). În acest exemplu, dorim să distribuim patru fragmente cu un prag de trei, așa că generăm aleatoriu puncte și trimite câte un punct fiecăruia dintre cei patru oameni de încredere, deținătorii cheii. De asemenea, le anunțăm oamenilor asta , deoarece aceasta este considerată informație publică și este necesară pentru recuperare .
Recuperarea secretului
Am discutat deja despre conceptul de interpolare polinomială și despre modul în care acesta stă la baza schemei de prag a lui Shamir . Când oricare trei dintre cei patru mandatari doresc să restaureze , trebuie doar să interpoleze cu punctele sale unice. Pentru a face acest lucru, ei își pot determina punctele și calculați polinomul de interpolare Lagrange folosind următoarea formulă. Dacă programarea este mai clară pentru tine decât matematica, atunci pi este în esență un operator for, care înmulțește toate rezultatele, iar sigma este for, care adună totul.
la o putem rezolva astfel și returnăm funcția polinomială inițială:
Din moment ce știm asta , recuperare facut simplu:
Utilizarea aritmeticii întregi nesigure
Deși am aplicat cu succes ideea de bază a lui Shamir , am ramas cu o problema pe care am ignorat-o pana acum. Funcția noastră polinomială folosește aritmetică cu numere întregi nesigure. Rețineți că pentru fiecare punct suplimentar pe care un atacator îl obține pe graficul funcției noastre, există mai puține posibilități pentru alte puncte. Puteți vedea acest lucru cu proprii dumneavoastră ochi când trasați un număr tot mai mare de puncte pentru o funcție polinomială folosind aritmetica întregi. Acest lucru este contraproductiv pentru obiectivul nostru de securitate declarat, deoarece atacatorul nu ar trebui să știe absolut nimic până când nu o are cel puțin fragmente.
Pentru a demonstra cât de slab este circuitul aritmetic întreg, luați în considerare un scenariu în care un atacator a obținut două puncte și cunoaște informații publice care . Din aceste informații el poate deduce , egal cu doi și introduceți valorile cunoscute în formulă и .
Atacatorul poate găsi apoi , socoteală :
Din moment ce am definit ca numere întregi pozitive selectate aleatoriu, există un număr limitat de posibile . Folosind aceste informații, un atacator poate deduce , deoarece orice lucru mai mare de 5 va funcționa negativ. Acest lucru se dovedește a fi adevărat, deoarece ne-am hotărât
Atacatorul poate calcula apoi valorile posibile înlocuind в :
Cu opțiuni limitate pentru devine clar cât de ușor este să selectați și să verificați valorile . Există doar cinci opțiuni aici.
Rezolvarea problemei cu aritmetica întregi nesigure
Pentru a elimina această vulnerabilitate, Shamir sugerează utilizarea aritmeticii modulare, înlocuind pe Unde и — mulțimea tuturor numerelor prime.
Să ne amintim rapid cum funcționează aritmetica modulară. Un ceas cu mâini este un concept familiar. Ea folosește un ceas care este . De îndată ce acul orelor trece de doisprezece, se întoarce la unu. O proprietate interesantă a acestui sistem este că, pur și simplu, uitându-ne la ceas, nu putem deduce câte rotații a făcut acul orelor. Cu toate acestea, dacă știm că acul orelor a trecut de 12 de patru ori, putem determina complet numărul de ore care au trecut folosind o formulă simplă Unde este divizorul nostru (aici ), este coeficientul (de câte ori divizorul intră în numărul original fără rest, aici ) și este restul, care returnează de obicei un apel de operator modulo (aici ). Cunoașterea tuturor acestor valori ne permite să rezolvăm ecuația pentru , dar dacă pierdem coeficientul, nu vom putea niciodată să restabilim valoarea inițială.
Putem demonstra cum acest lucru îmbunătățește securitatea schemei noastre prin aplicarea schemei la exemplul nostru anterior și folosind . Noua noastră funcție polinomială , și noile puncte . Acum, deținătorii cheilor pot folosi din nou interpolarea polinomială pentru a reconstrui funcția noastră, doar că de data aceasta operațiile de adunare și înmulțire trebuie să fie însoțite de reducerea modulo. (de exemplu ).
Folosind acest nou exemplu, să presupunem că atacatorul a învățat două dintre aceste noi puncte, , și informații publice . De data aceasta, atacatorul, pe baza tuturor informațiilor pe care le are, scoate următoarele funcții, unde este mulțimea tuturor numerelor întregi pozitive și reprezintă coeficientul de modul .
Acum atacatorul nostru găsește din nou , calculând :
Apoi încearcă din nou înlocuind в :
De data aceasta are o problemă serioasă. Valori lipsă de formulă , и . Deoarece există un număr infinit de combinații ale acestor variabile, el nu poate obține nicio informație suplimentară.
Considerații de securitate
Schema de partajare secretă a lui Shamir sugerează securitate din punct de vedere al teoriei informaţiei. Aceasta înseamnă că matematica este rezistentă chiar și împotriva unui atacator cu putere de calcul nelimitată. Cu toate acestea, circuitul conține încă mai multe probleme cunoscute.
De exemplu, schema lui Shamir nu creează fragmente de verificat, adică oamenii pot prezenta liber fragmente false și pot interfera cu recuperarea secretului corect. Un deținător de fragment ostil cu suficiente informații ar putea chiar să producă un alt fragment prin schimbare la propria discreție. Această problemă este rezolvată folosind scheme verificabile de partajare a secretelor, cum ar fi schema lui Feldman.
O altă problemă este că lungimea oricărui fragment este egală cu lungimea secretului corespunzător, astfel încât lungimea secretului este ușor de determinat. Această problemă poate fi rezolvată prin trivial umplutura secret cu numere arbitrare până la o lungime fixă.
În cele din urmă, este important să rețineți că preocupările noastre de securitate se pot extinde dincolo de designul în sine. Pentru aplicațiile criptografice din lumea reală, există adesea amenințarea atacurilor pe canale laterale în care un atacator încearcă să extragă informații utile din timpul de execuție a aplicației, cache, blocări etc. Dacă aceasta este o problemă, în timpul dezvoltării ar trebui să se acorde atenție utilizării măsurilor de protecție, cum ar fi funcții și căutări în timp constant, împiedicând salvarea memoriei pe disc și o serie de alte considerente care depășesc domeniul de aplicare al acestui articol.
Demo
Pe Există o demonstrație interactivă a schemei de partajare secretă a lui Shamir. Demonstrație bazată pe bibliotecă , care în sine este un port JavaScript al programului popular . Rețineți că calcularea valorilor mari , и poate dura ceva timp.
Sursa: www.habr.com