Razmotrimo scenarij kada je potrebno osigurati sigurnost bankovnog skladišta. Ono se smatra potpuno nedostupnim bez ključa koji vam se izdaje prvog dana rada. Vaš cilj je sigurno sačuvati ključ.

Pretpostavimo da ste odlučili uvijek držati ključ kod sebe, pružajući pristup skladištu prema potrebi. No brzo ćete shvatiti da takvo rješenje praktično nije skalabilno, jer je za otvaranje skladišta uvijek potrebna vaša fizička prisutnost. A što je s odmorima koje su vam obećali? Osim toga, još više zabrinjava pitanje: što ako izgubite jedini ključ?

S mišlju o odmoru odlučili ste napraviti kopiju ključa i povjeriti je drugom suradniku. Međutim, shvaćate da to također nije idealno. Udvostručavanjem broja ključeva, također ste udvostručili mogućnosti krađe ključa.

Bez nade, uništavate duplikat i odlučujete podijeliti izvorni ključ na dva dijela. Sada, mislite, dvije povjerljive osobe s dijelovima ključa moraju fizički biti prisutne kako bi sastavile ključ i otvorile skladište. To znači da bi lopov morao ukrasti dva dijela, što je dvostruko teže nego ukrasti jedan ključ. Međutim, ubrzo shvaćate da je shema malo bolja od samo jednog ključa, jer ako netko izgubi polovicu ključa, cijeli ključ ne može biti obnovljen.

Problem se može riješiti s nizom dodatnih ključeva i brava, ali takav pristup brzo će zahtijevati ljudi, i ovaj projekt ne bi bio moguć bez sudjelovanja nevjerojatne zajednice suradnika i korisnika. ključeva i brava. Odlučujete da u idealnoj shemi treba podijeliti ključ tako da sigurnost ne ovisi potpuno o jednoj osobi. Također zaključujete da bi trebao postojati određeni prag broja dijelova, tako da pri gubitku jednog dijela (ili ako osoba ode na odmor) cijeli ključ ostaje funkcionalan.

Kako podijeliti tajnu

O ovoj vrsti sheme upravljanja ključevima razmišljao je Adi Shamir 1979. godine kada je objavio svoj rad „Kako podijeliti tajnu”. U članku se kratko objašnjava takozvana pragovna shema za učinkovito dijeljenje tajne vrijednosti (npr. kriptografskog ključa) na dijelova. Zatim, kada i samo kada je prikupljeno barem iz dijelova, tajnu je lako obnoviti. .

S aspekta sigurnosti, važna karakteristika ovog sistema je da napadač ne smije saznati apsolutno ništa ako nema barem dijelove. Čak ni prisutnost dijelova ne bi trebala pružiti nikakve informacije. Ovu osobinu nazivamo semantičkim sigurnostima.

Polinomska interpolacija

Shamir-ova shema praga izgrađena je oko koncepta polinomskih interpolacija. Ako niste upoznati s ovim konceptom, zapravo je prilično jednostavan. U suštini, ako ste ikada crtali točke na grafu, a zatim ih povezivali linijama ili krivinama, već ste ga koristili!

Kroz dvije točke može proći neograničen broj polinoma druge stepeni. Da bismo izabrali jedan od njih, potrebna je treća točka. Ilustracija: Vikipedija

Razmotrimo polinom prvog stepena, . Ako želite izgraditi ovu funkciju na grafu, koliko točaka vam je potrebno? Pa, znamo da je to linearna funkcija koja formira liniju i da su potrebne bar dvije tačke. Dalje, razmotrite polinom drugog stepena, . To je kvadratna funkcija, tako da za izgradnju grafika zahtijeva najmanje tri tačke. A kako stoji stvar s polinom trećeg stepena? Potrebno je barem četiri točke. I tako dalje.

Zaista sjajna stvar u ovoj osobini je da uzimajući u obzir stepen polinomske funkcije i najmanje točki, možemo izvesti dodatne točke za ovu polinomsku funkciju. Ekstrapolaciju tih dodatnih točaka nazivamo polinomskom interpolacijom.

Sastavljanje tajne

Moguće je da ste već shvatili da ovdje ulazi u igru pametna Shamir-ova shema. Pretpostavimo da je naš tajni — to je . Možemo transformirati u točku na grafu i smisliti polinomsku funkciju stepena , koja zadovoljava ovu točku. Podsjetimo, će biti naš prag potrebnih fragmenata, stoga ako postavimo prag na tri fragmenta, trebamo odabrati polinomsku funkciju stepena dva.

Naš polinom će imati oblik , gdje i — nasumično odabrani pozitivni cijeli brojevi. Samo gradimo polinom stepena , gdje slobodni koeficijent  je naša tajna , a kod svakog od sljedećih Članova je slučajno odabran pozitivni koeficijent. Ako se vratimo na prvotni primjer i pretpostavimo da , onda ćemo dobiti funkciju .

U ovoj fazi možemo generirati dijelove povezivanjem jedinstvenih cijelih brojeva u , gdje (jer je to naš tajni podaci). U ovom primjeru želimo podijeliti četiri dijela s pragom tri, stoga slučajno generiramo točke i šaljemo jednu točku svakom od četiri povjerenika, čuvarima ključeva. Također obavještavamo ljude da , budući da se to smatra javnom informacijom i potrebnim za obnovu .

Obnova tajne

Već smo raspravili koncept polinomske interpolacije i to što stoji iza Shamirove sheme praga . Kada bilo koja tri od četiri povjerenika žele obnoviti , potrebno je samo interpolirati svojim jedinstvenim točkama. U tu svrhu mogu definirati svoje točke i izračunati Lagrangeov interpolacijski polinom koristeći sljedeću formulu. Ako vam je programiranje jasnije od matematike, tada pi - to je u suštini operator for, koji množi sve rezultate, a sigma - to je for, koji sve zbraja.

Tijekom možemo to riješiti na sljedeći način i vratiti naš izvorni polinomski funkciju:

Budući da znamo da , obnova se provodi jednostavno:

Korištenje nesigurne cijelobrojne aritmetike

Iako smo uspješno primijenili osnovnu ideju Shamira , imamo problem koji smo ignorirali do sada. Naša polinom funkcija koristi nesigurnu cijelobrojnu aritmetiku. Imajte na umu da za svaku dodatnu točku koju napadač dobije na grafikonu naše funkcije, ostaje manje mogućnosti za druge točke. Možete to vidjeti vlastitim očima kada crtate grafikon s povećanjem broja točaka za polinomsku funkciju koristeći cijelobrojnu aritmetiku. To je kontraproduktivno za našu izjavnu sigurnosnu svrhu, jer napadač ne bi trebao saznati apsolutno ništa, sve dok nemaju barem dijelova.

Da bismo pokazali koliko je slaba shema s cijelobrojnom aritmetikom, razmotrimo scenarij u kojem je napadač dobio dvije točke i zna javnu informaciju, da Na temelju tih informacija može izvesti , koji je jednak dva, i uključiti poznate vrijednosti u formulu i .

Zatim napadač može pronaći , izračunavajući :

Budući da smo definirali kao slučajno odabrane cijele pozitivne brojeve, postoji ograničen broj mogućih . Ova informacija omogućava napadaču da izvede , jer će sve što je veće od 5 učiniti negativnim. To se pokazuje točnim, budući da smo definirali

Zatim napadač može izračunati moguće vrijednosti , zamjenjujući u :

S ograničenim skupom opcija za postaje jasno koliko je lako pogoditi i provjeriti vrijednosti . Ovdje je samo pet opcija.

Rješenje problema s nesigurnom cijelom aritmetikom

Kako bi se uklonila ova ranjivost, Shamir predlaže korištenje modularne aritmetike, zamjenjujući na , gdje i — skup svih prostih brojeva.

Brzo ćemo se podsjetiti kako funkcioniše modularna aritmetika. Satovi s kazaljkama su već poznata koncepcija. Koriste satove koji su . Kada kazaljka na satu prođe pored dvanaest, vraća se na jedan. Zanimljiva osobina ovog sistema je ta što, jednostavno gledajući na sat, ne možemo izvesti koliko je okreta kazaljka napravila. Međutim, ako znamo da je kazaljka na satu prošla dvanaest četiri puta, možemo potpuno odrediti broj sati koji su prošli pomoću jednostavne formule , gdje  — to je naš djelitelj (ovdje ),  — to je koeficijent (koliko puta djelitelj bez ostatka ide u početni broj, ovdje ), a  — to je ostatak koji obično vraća poziv operatora po modulu (ovdje ). Poznavanje svih ovih vrijednosti omogućava nam rješavanje jednadžbe za , ali ako propustimo koeficijent, nikada nećemo moći obnoviti izvorni broj.

Možemo demonstrirati kako to poboljšava sigurnost našeg sistema primjenjujući shemu na naš prethodni primjer i koristeći . Naša nova polinomna funkcija , a nove točke . Sada čuvari ključeva mogu ponovno koristiti polinomnu interpolaciju za obnavljanje naše funkcije, samo što sada operacije zbrajanja i množenja moraju biti praćene smanjenjem po modu (npr. ).

Pretpostavljajući da je napadač saznao dvije od ovih novih točaka, , a javne informacije . Ovaj put napadač na temelju svih dostupnih informacija ispisuje sljedeće funkcije, gdje  — skup svih pozitivnih cijelih brojeva, a predstavlja koeficijent modula .

Sada naš napadač ponovno pronalazi , izračunavajući :

Zatim ponovno pokušava ispisati , zamjenjujući u :

Ovaj put ima ozbiljan problem. U formuli nedostaju vrijednosti , i . Budući da postoji beskonačno mnogo kombinacija ovih varijabli, ne može dobiti nikakve dodatne informacije.

Razmatranja sigurnosti

Shema dijeljenja tajne Shamir predlaže sigurnost s gledišta teorije informacija. To znači da je matematika otporna čak i na napadača s neograničenom računalnom moći. Međutim, shema još uvijek ima nekoliko poznatih problema.

Na primjer, Shamirina shema ne stvara provjerljive fragmente, to jest ljudi mogu slobodno predstaviti falsificirane fragmente i ometati obnavljanje ispravne tajne. Zlonamjernik s dovoljno informacija može čak proizvesti drugi fragment mijenjajući po vlastitom nahođenju. Ovaj problem se rješava pomoću provjerljivih shema dijeljenja tajne, poput Feldmanove sheme.

Drugi problem je u tome što je duljina bilo kojeg fragmenta jednaka duljini odgovarajuće tajne, tako da je duljinu tajne lako odrediti. Ovaj problem se rješava trivijalnim punjenjem tajne proizvoljnim brojevima do fiksne duljine.

Na kraju, važno je napomenuti da naša zabrinutost za sigurnost može premašiti samu shemu. Za stvarne kriptografske primjene često postoji prijetnja napadima putem vanjskih kanala, kada napadač pokušava izvući korisne informacije iz vremena izvođenja aplikacije, keširanja, kvarova i sl. Ako to predstavlja zabrinutost, tijekom razvoja treba pažljivo razmotriti korištenje sigurnosnih mjera, kao što su funkcije i pretraga s konstantnim vremenom izvođenja, sprječavanje spremanja podataka na disk i razmatranje niza drugih stvari koje nadilaze ovaj članak.

Demo

Na ovoj stranici ima interaktivnu demonstraciju sheme dijeljenja tajne Shamir. Demonstracija je temeljena na biblioteci ssss-js, koja sama po sebi predstavlja JavaScript port popularnog programa ssssObratite pažnju da izračunavanje velikih vrijednosti , i može potrajati neko vrijeme.

Izvor: habr.com