Razmotrite scenarij u kojem trebate osigurati bankovni trezor. Smatra se apsolutno neosvojivim bez ključa, koji dobivate prvog dana rada. Vaš cilj je sigurno pohraniti ključ.
Recimo da ste odlučili držati ključ uvijek sa sobom, omogućavajući pristup pohrani prema potrebi. Ali brzo ćete shvatiti da takvo rješenje nije dobro skalirano u praksi, jer je vaša fizička prisutnost potrebna svaki put kada otvorite skladište. Što je s odmorom koji vam je obećan? Osim toga, još je strašnije pitanje: što ako ste izgubili jedini ključ?
S obzirom na godišnji odmor, odlučili ste napraviti kopiju ključa i povjeriti je drugom zaposleniku. Međutim, shvaćate da ni to nije idealno. Udvostručenjem broja ključeva udvostručujete i šanse za krađu ključeva.
U očaju uništavate duplikat i odlučujete prepoloviti originalni ključ. Sada biste pomislili da bi dvije osobe od povjerenja s fragmentima ključa morale biti fizički prisutne da uzmu ključ i otvore trezor. To znači da lopov treba ukrasti dva komada, što je dvostruko teže nego ukrasti jedan ključ. Međutim, ubrzo shvatite da ova shema nije puno bolja od samo jednog ključa, jer ako netko izgubi pola ključa, cijeli ključ se ne može vratiti.
Problem se može riješiti s nizom dodatnih ključeva i brava, ali ovaj će pristup brzo zahtijevati много ključeve i brave. Odlučili ste da bi idealan dizajn bio dijeljenje ključa tako da se sigurnost ne oslanja u potpunosti na jednu osobu. Također zaključujete da mora postojati neki prag za broj fragmenata tako da ako se jedan fragment izgubi (ili ako osoba ode na odmor), cijeli ključ ostane funkcionalan.
Kako podijeliti tajnu
O ovoj vrsti sheme upravljanja ključevima razmišljao je Adi Shamir 1979. kada je objavio svoj rad . U članku se ukratko objašnjavaju tzv 
shema praga za učinkovito dijeljenje tajne vrijednosti (kao što je kriptografski ključ) u dijelovi. Tada, kada i samo kada barem od dijelovi su sastavljeni, možete jednostavno vratiti tajnu .
Sa sigurnosne točke gledišta, važno svojstvo ove sheme je da napadač ne bi trebao znati apsolutno ništa osim ako ima barem dijelovi. Čak i prisutnost dijelovi ne bi trebali pružati nikakve informacije. Ovo svojstvo nazivamo semantička sigurnost.
Interpolacija polinoma
Shamirova shema praga izgrađen oko koncepta polinomska interpolacija. Ako niste upoznati s ovim konceptom, zapravo je vrlo jednostavan. Zapravo, ako ste ikada nacrtali točke na grafikonu i zatim ih povezali linijama ili krivuljama, to ste već koristili!
Kroz dvije točke možete povući neograničen broj polinoma stupnja 2. Da biste odabrali jedan od njih, potrebna vam je treća točka. Ilustracija:
Razmotrimo polinom prvog stupnja, . Ako želite iscrtati ovu funkciju na grafikonu, koliko točaka trebate? Pa, znamo da je ovo linearna funkcija koja tvori pravac i stoga su joj potrebne najmanje dvije točke. Zatim, razmotrite polinomsku funkciju drugog stupnja, . Ovo je kvadratna funkcija, pa su najmanje tri točke potrebne za iscrtavanje grafa. Što kažete na polinom trećeg stupnja? Najmanje četiri boda. I tako dalje.
Stvarno cool stvar u vezi ovog svojstva je da, s obzirom na stupanj polinomske funkcije i najmanje bodova, možemo izvesti dodatne točke za ovu polinomsku funkciju. Nazivamo ekstrapolacijom tih dodatnih točaka polinomska interpolacija.
Izmišljanje tajne
Možda ste već shvatili da ovdje Shamirova pametna shema stupa na scenu. Recimo našu tajnu - Je . Možemo se okrenuti do točke na grafikonu i doći do polinomske funkcije sa stupnjem , što zadovoljava ovu točku. Prisjetimo se toga će biti naš prag potrebnih fragmenata, pa ako postavimo prag na tri fragmenta, moramo odabrati polinomsku funkciju sa stupnjem dva.
Naš polinom će imati oblik Gdje и — slučajno odabrani prirodni brojevi. Samo konstruiramo polinom sa stupnjem , gdje je slobodni koeficijent - Ovo je naša tajna , te za svaki sljedeći izrazi postoji nasumično odabrani pozitivni koeficijent. Ako se vratimo na izvorni primjer i pretpostavimo da , tada dobivamo funkciju .
U ovom trenutku možemo generirati fragmente povezivanjem jedinstveni cijeli brojevi u Gdje (jer je to naša tajna). U ovom primjeru želimo distribuirati četiri fragmenta s pragom od tri, tako da nasumično generiramo bodove i pošaljite po jedan bod svakoj od četiri osobe od povjerenja, čuvarima ključa. To također dajemo ljudima do znanja , jer se to smatra javnom informacijom i neophodno je za oporavak .
Oporavak tajne
Već smo raspravljali o konceptu polinomske interpolacije i o tome kako je ona temelj Shamirove sheme praga . Kada bilo koja tri od četiri povjerenika žele vratiti , trebaju samo interpolirati sa svojim jedinstvenim točkama. Da bi to učinili, mogu odrediti svoje bodove i izračunajte Lagrangeov interpolacijski polinom pomoću sljedeće formule. Ako vam je programiranje jasnije od matematike, onda je pi u biti operator for, koji množi sve rezultate, a sigma je for, što sve zbraja.
u možemo to riješiti ovako i vratiti našu izvornu polinomsku funkciju:
Pošto to znamo , oporavak učinjeno jednostavno:
Korištenje nesigurne aritmetike cijelih brojeva
Iako smo Shamirovu temeljnu ideju uspješno primijenili , ostaje nam problem koji smo do sada ignorirali. Naša polinomska funkcija koristi nesigurnu aritmetiku cijelog broja. Imajte na umu da za svaki dodatni bod koji napadač dobije na grafu naše funkcije, ima manje mogućnosti za druge bodove. To možete vidjeti vlastitim očima kada crtate sve veći broj točaka za polinomsku funkciju koristeći aritmetiku cjelobrojnih brojeva. Ovo je kontraproduktivno za naš navedeni sigurnosni cilj, jer napadač ne bi trebao znati apsolutno ništa dok ne sazna barem fragmenti.
Da biste pokazali koliko je slab aritmetički krug cjelobrojnih brojeva, razmotrite scenarij u kojem je napadač dobio dva boda i zna javne informacije koje . Iz ove informacije može zaključiti , jednako dva, i ubacite poznate vrijednosti u formulu и .
Napadač tada može pronaći , brojeći :
Budući da smo definirali kao nasumično odabranih pozitivnih cijelih brojeva, postoji ograničen broj mogućih . Koristeći ove informacije, napadač može zaključiti , budući da će biti dovoljno sve što je veće od 5 negativan. Ovo se pokazalo točnim budući da smo utvrdili
Napadač tada može izračunati moguće vrijednosti zamjenjujući в :
S ograničenim mogućnostima za postaje jasno kako je lako odabrati i provjeriti vrijednosti . Ovdje postoji samo pet opcija.
Rješavanje problema nesigurnom cjelobrojnom aritmetikom
Kako bi se uklonila ova ranjivost, Shamir predlaže korištenje modularne aritmetike, zamjenu na Gdje и — skup svih prostih brojeva.
Prisjetimo se na brzinu kako modularna aritmetika funkcionira. Sat s kazaljkama poznat je koncept. Ona koristi sat koji je . Čim satna kazaljka prijeđe dvanaest, vraća se na jedan. Zanimljivo svojstvo ovog sustava je da jednostavnim pogledom na sat ne možemo zaključiti koliko je okretaja napravila satna kazaljka. Međutim, ako znamo da je satna kazaljka četiri puta prešla 12, pomoću jednostavne formule možemo u potpunosti odrediti broj sati koji su prošli Gdje je naš djelitelj (ovdje ), je koeficijent (koliko puta djelitelj ulazi u izvorni broj bez ostatka, ovdje ), i je ostatak, koji obično vraća modulo poziv operatora (ovdje ). Poznavanje svih ovih vrijednosti omogućuje nam rješavanje jednadžbe za , ali ako promašimo koeficijent, nikada nećemo moći vratiti izvornu vrijednost.
Možemo pokazati kako ovo poboljšava sigurnost naše sheme primjenom sheme na naš prethodni primjer i korištenjem . Naša nova polinomska funkcija , i nove bodove . Sada čuvari ključeva ponovno mogu koristiti interpolaciju polinoma za rekonstrukciju naše funkcije, samo ovaj put operacije zbrajanja i množenja moraju biti popraćene modulo redukcijom (npr ).
Koristeći ovaj novi primjer, pretpostavimo da je napadač naučio dvije od ovih novih točaka, , i javno informiranje . Ovaj put napadač na temelju svih informacija koje ima ispisuje sljedeće funkcije, gdje je skup svih pozitivnih cijelih brojeva, i predstavlja koeficijent modula .
Sada naš napadač ponovno pronalazi , računajući :
Zatim pokušava ponovno zamjenjujući в :
Ovaj put ima ozbiljan problem. U formuli nedostaju vrijednosti , и . Budući da postoji beskonačan broj kombinacija ovih varijabli, on ne može dobiti nikakve dodatne informacije.
Sigurnosna razmatranja
Shamirova shema dijeljenja tajni sugerira sigurnost sa stajališta informacijske teorije. To znači da je matematika otporna čak i protiv napadača s neograničenom računalnom snagom. Međutim, sklop i dalje sadrži nekoliko poznatih problema.
Na primjer, Shamirova shema ne stvara fragmenti koje treba provjeriti, to jest, ljudi mogu slobodno predstavljati lažne fragmente i ometati oporavak ispravne tajne. Neprijateljski čuvar fragmenta s dovoljno informacija mogao bi čak proizvesti još jedan fragment promjenom prema vlastitom nahođenju. Ovaj problem se rješava pomoću provjerljive sheme dijeljenja tajni, kao što je Feldmanova shema.
Drugi problem je što je duljina bilo kojeg fragmenta jednaka duljini odgovarajuće tajne, pa je duljinu tajne lako odrediti. Ovaj problem se može riješiti trivijalnim podstava tajna s proizvoljnim brojevima do fiksne duljine.
Na kraju, važno je napomenuti da se naša zabrinutost za sigurnost može proširiti izvan samog dizajna. Za kriptografske aplikacije u stvarnom svijetu često postoji prijetnja od napada sporednih kanala gdje napadač pokušava izvući korisne informacije iz vremena izvršavanja aplikacije, predmemoriranja, rušenja itd. Ako je to zabrinjavajuće, tijekom razvoja treba pažljivo razmotriti korištenje zaštitnih mjera kao što su funkcije i pretraživanja u konstantnom vremenu, sprječavanje spremanja memorije na disk i brojna druga razmatranja koja su izvan opsega ovog članka.
demo
Na Postoji interaktivna demonstracija Shamirove sheme dijeljenja tajni. Demonstracija na temelju knjižnice , koji je i sam JavaScript priključak popularnog programa . Imajte na umu da izračunavanje velikih vrijednosti , и može potrajati.
Izvor: www.habr.com