Să presupunem un scenariu în care trebuie să asigurăm securitatea unei camere de bani. Aceasta este considerată complet inaccesibilă fără cheia pe care o primești în prima zi de lucru. Obiectivul tău este să păstrezi cheia în siguranță.

Să zicem că ai decis să îți păstrezi cheia tot timpul, oferind acces la cameră doar când este necesar. Dar vei realiza rapid că această soluție nu se scalează bine în practică, pentru că de fiecare dată pentru a deschide camera este necesară prezența ta fizică. Ce se întâmplă cu concediile promise? În plus, te îngrijorează și mai mult întrebarea: ce se întâmplă dacă pierzi singura cheie?

Gândindu-te la concediu, ai decis să faci o copie a cheii și să o încredințezi unui alt coleg. Totuși, îți dai seama că aceasta nu este o soluție ideală. Duplicând numărul cheilor, ai dublat și riscurile de furt al cheii.

Disperat, distrugi copia și decizi să împarți cheia originală în două. Acum, te gândești că două persoane de încredere cu fragmentele cheii trebuie să fie prezente fizic pentru a asambla cheia și a deschide camera. Aceasta înseamnă că hoțul trebuie să fure două fragmente, ceea ce este de două ori mai greu decât să fure o singură cheie. Cu toate acestea, în curând îți dai seama că această schemă nu este cu mult mai bună decât o cheie simplă, deoarece dacă cineva pierde o jumătate din cheie, cheia completă nu poate fi recreată.

Problema poate fi rezolvată printr-o serie de chei și încuietori suplimentare, dar cu acest tip de abordare rapid se va necesita multe chei și încuietori. Decizi că în schema ideală cheia ar trebui împărțită pentru ca securitatea să nu depindă complet de o singură persoană. De asemenea, concluzionezi că ar trebui să existe un prag de număr de fragmente astfel încât, în cazul pierderii unuia (sau dacă cineva pleacă în concediu), întreaga cheie să rămână funcțională.

Cum să împarți secretul

Acest tip de schemă de gestionare a cheilor a fost gândit de Adi Shamir în 1979, când și-a publicat lucrarea „Cum să împărțim un secret”. În articol se explică pe scurt așa numita Schema de împărțire a secretului lui Shamir schemă de praguri pentru împărțirea eficientă a unei valori secrete (de exemplu, a unei chei criptografice) în părți. Apoi, când și numai când cel puțin din părți sunt adunate, secretul poate fi recuperat ușor. .

Din punct de vedere al securității, o caracteristică importantă a acestui sistem este că un atacator nu ar trebui să afle nimic absolut, dacă nu are cel puțin Schema de împărțire a secretului lui Shamir părțile. Chiar și deținerea părților nu ar trebui să ofere nicio informație. Numim această caracteristică securitate semantică.

Interpolare polinomială

Schema de prag Shamir Schema de împărțire a secretului lui Shamir este construită în jurul conceptului de interpolare polinomială. Dacă nu ești familiarizat cu acest concept, este de fapt destul de simplu. În general, dacă ai desenat vreodată puncte pe un grafic și apoi le-ai unit cu linii sau curbe, atunci deja l-ai folosit!

Schema de împărțire a secretului lui Shamir
Pentru două puncte se poate trasa un număr nelimitat de polinoame de gradul 2. Pentru a alege dintre ele unicul — este nevoie de un al treilea punct. Ilustrație: Wikipedia

Să considerăm un polinom de gradul unu, Schema de împărțire a secretului lui Shamir . Dacă vrei să construiești această funcție pe grafic, câte puncte îți trebuie? Ei bine, știm că este o funcție liniară, care formează o linie, așa că ai nevoie de cel puțin două puncte. Apoi, să analizăm o funcție polinomială de gradul doi, Schema de împărțire a secretului lui Shamir . Aceasta este o funcție pătratică, deci pentru a desena graficul este necesar să ai cel puțin trei puncte. Dar ce zici de un polinom de gradul trei? Cel puțin patru puncte. Și tot așa și mai departe.

Ceea ce este cu adevărat interesant în această proprietate este că, având gradul funcției polinomiale și, cel puțin Schema de împărțire a secretului lui Shamir puncte, putem deduce puncte suplimentare pentru această funcție polinomială. Extrapolarea acestor puncte suplimentare o numim interpolare polinomială.

Compunerea secretului

Probabil că deja ai înțeles că aici intervine schema inteligentă a lui Shamir. Să presupunem că secretul nostru Schema de împărțire a secretului lui Shamir — acesta este . Putem transforma într-un punct pe grafic și să găsim o funcție polinomială de gradul , care să satisfacă acest punct. Să reamintim că va fi pragul nostru de fragmente necesare, așa că, dacă stabilim pragul la trei fragmente, atunci trebuie să alegem o funcție polinomială de gradul doi.

Polinomul nostru va avea forma Schema de împărțire a secretului lui Shamir , unde și sunt numere întregi pozitive alese aleatoriu. Construim pur și simplu un polinom de gradul , unde coeficientul liber este secretul nostru , iar fiecare dintre următorii un coeficient pozitiv ales membrilor este ales la întâmplare. Dacă ne întoarcem la exemplul inițial și presupunem că Schema de împărțire a secretului lui Shamir , atunci vom obține o funcție .

În această etapă putem genera fragmente, conectând Schema de împărțire a secretului lui Shamir numere întregi unice în , unde (deoarece acesta este secretul nostru). În acest exemplu, vrem să distribuim patru fragmente cu un prag de trei, așa că generăm puncte aleatoriu și trimitem câte un punct fiecărei dintre cele patru persoane de încredere, păstrătorii cheii. De asemenea, le comunicăm oamenilor că Schema de împărțire a secretului lui Shamir , deoarece aceasta este considerată informație publică și este necesară pentru recuperare .

Recuperarea secretului

Am discutat deja despre conceptul de interpolare polinomială și despre faptul că acesta stă la baza schemei de prag Shamir. Schema de împărțire a secretului lui Shamir . Când oricare trei din cele patru persoane de încredere doresc să recupereze , trebuie doar să interpoleze cu punctele lor unice. Pentru aceasta, ei pot determina punctele lor și pot calcula polinomul de interpolare Lagrange, folosind următoarea formulă. Dacă programarea îți este mai clară decât matematica, atunci pi este practic operatorul for, care înmulțește toate rezultatele, iar sigma este for, care adună tot.

Schema de împărțire a secretului lui Shamir

Upon Schema de împărțire a secretului lui Shamir putem rezolva asta în felul următor și să returnăm funcția noastră polinomială originală:

Schema de împărțire a secretului lui Shamir

Deoarece știm că Schema de împărțire a secretului lui Shamir , recuperarea se realizează simplu:

Schema de împărțire a secretului lui Shamir

Utilizarea aritmeticii întregi nesigure

Deși am aplicat cu succes ideea de bază a lui Shamir Schema de împărțire a secretului lui Shamir , avem încă o problemă pe care am ignorat-o până acum. Funcția noastră polinomială folosește aritmetica întreagă nesigură. Rețineți că pentru fiecare punct suplimentar pe care atacatorul îl obține pe graficul funcției noastre, rămâne un număr mai mic de oportunități pentru celelalte puncte. Puteți vedea asta cu ochii voștri atunci când construiți un grafic cu un număr crescut de puncte pentru o funcție polinomială folosind aritmetica întreagă. Acest lucru este contraproductiv pentru scopul nostru declarat de securitate, deoarece atacatorul nu ar trebui să afle absolut nimic până nu are cel puțin Schema de împărțire a secretului lui Shamir fragmente.

Pentru a demonstra cât de slabă este schema cu aritmetica întreagă, să luăm în considerare un scenariu în care atacatorul a obținut două puncte Schema de împărțire a secretului lui Shamir și știe informația publică că . Din aceste informații, acesta poate deduce , echivalent cu doi, și poate introduce în formulă valorile cunoscute și .

Schema de împărțire a secretului lui Shamir

Apoi, atacatorul poate găsi Schema de împărțire a secretului lui Shamir , calculând :

Schema de împărțire a secretului lui Shamir

Deoarece am definit Schema de împărțire a secretului lui Shamir ca numere întregi pozitive selectate aleatoriu, există un număr limitat de opțiuni posibile . Cu aceste informații, atacatorul poate deduce , deoarece orice număr mai mare de 5 va face negativ. Asta se dovedește a fi adevărat, deoarece am definit Schema de împărțire a secretului lui Shamir

Apoi, atacatorul poate calcula valorile posibile Schema de împărțire a secretului lui Shamir , înlocuind în :

Schema de împărțire a secretului lui Shamir

Cu un set limitat de opțiuni pentru Schema de împărțire a secretului lui Shamir devine clar cât de ușor este să ghicești și să verifici valorile . Există doar cinci opțiuni.

Soluția problemei cu aritmetica întreagă nesigură

Pentru a elimina această vulnerabilitate, Shamir propune utilizarea aritmeticii modulare, înlocuind Schema de împărțire a secretului lui Shamir pe , unde și — mulțimea tuturor numerelor prime.

Să ne amintim rapid cum funcționează aritmetica modulară. Ceasurile cu ace sunt o conceptie deja cunoscută. Acesta utilizează ceasuri care sunt Schema de împărțire a secretului lui Shamir . Atunci când bratul orar trece de douăsprezece, acesta revine la unu. O caracteristică interesantă a acestui sistem este că, doar uitându-ne la ceas, nu putem deduce câte rotații a făcut bratul orar. Cu toate acestea, dacă știm că bratul orar a trecut de 12 de patru ori, putem determina complet numărul de ore trecute cu ajutorul unei formule simple Schema de împărțire a secretului lui Shamir , unde — acesta este divizorul nostru (aici ), — acesta este coeficientul (de câte ori divizorul se împacă cu numărul inițial fără rest, aici ), iar — acesta este restul, care de obicei este returnat de operatorul modulo (aici ). Cunoașterea tuturor acestor valori ne permite să rezolvăm ecuația pentru Schema de împărțire a secretului lui Shamir , dar dacă omitem coeficientul, nu vom putea niciodată să recuperăm valoarea inițială.

Putem demonstra cum acest lucru îmbunătățește securitatea schemei noastre aplicând schema la exemplul nostru anterior și folosind Schema de împărțire a secretului lui Shamir . Funcția noastră polinomială nouă , iar noile puncte . Acum, cei care păstrează cheia pot folosi din nou interpolarea polinomială pentru a recupera funcția noastră, dar de data aceasta operațiile de adunare și înmulțire trebuie să fie însoțite de reducerea modulo Schema de împărțire a secretului lui Shamir (ex. ).

Folosind acest nou exemplu, să presupunem că atacatorul a aflat două dintre aceste puncte noi, Schema de împărțire a secretului lui Shamir , iar informațiile publice . De această dată, atacatorul pe baza tuturor informațiilor disponibile extrage următoarele funcții, unde — un set al tuturor numerelor întregi pozitive, iar reprezintă coeficientul modulelor .

Schema de împărțire a secretului lui Shamir

Acum, atacatorul nostru găsește din nou Schema de împărțire a secretului lui Shamir , calculând :

Schema de împărțire a secretului lui Shamir

Apoi, încearcă din nou să extragă Schema de împărțire a secretului lui Shamir , înlocuind în :

Schema de împărțire a secretului lui Shamir

De data aceasta, are o problemă serioasă. Formula nu conține valori Schema de împărțire a secretului lui Shamir , și . Deoarece există un număr infinit de combinații ale acestor variabile, nu poate obține informații suplimentare.

Considerații de securitate

Schema de împărțire a secretului lui Shamir oferă securitate din perspectiva teoriei informației. Asta înseamnă că matematica este rezistentă chiar și în fața unui atacator cu putere de calcul nelimitată. Cu toate acestea, schema conține totuși câteva probleme cunoscute.

De exemplu, schema lui Shamir nu generează fragmente verificabile, adică oamenii pot prezenta liber fragmente false și pot împiedica restaurarea secretului corect. Un stăpân inamic al fragmentelor cu informații suficiente ar putea chiar să genereze un alt fragment, modificând Schema de împărțire a secretului lui Shamir după bunul plac. Această problemă este rezolvată prin scheme verificabile de împărțire a secretului, 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 poate fi ușor identificată. Această problemă este abordată printr-o umplere a secretului cu numere aleatoare până la o lungime fixă.

În cele din urmă, este important de menționat că temerile noastre legate de securitate pot depăși cadrul schemei în sine. Pentru aplicațiile criptografice reale, există adesea amenințări din atacuri pe canale laterale, când atacatorul încearcă să extragă informații utile din timpul de execuție al aplicației, cache, erori etc. Dacă aceasta reprezintă o îngrijorare, este recomandat să se considere cu atenție utilizarea măsurilor de protecție în timpul dezvoltării, cum ar fi funcții și căutări cu timp de execuție constant, prevenirea salvării memoriei pe disc și o serie de alte aspecte ce depășesc această discuție.

Demo

Pe această pagină are o demonstrație interactivă a schemei de împărțire a secretului lui Shamir. Demonstrația este realizată pe baza bibliotecii ssss-js, care este în sine un port JavaScript al unei programe populare ssss. Vă rugăm să rețineți că calcularea valorilor mari Schema de împărțire a secretului lui Shamir , și poate dura ceva timp.

Sursa: habr.com