Razmislite o scenariju u kojem trebate osigurati bankovni trezor. Smatra se apsolutno neosvojivim bez ključa, koji vam se daje prvog dana rada. Vaš cilj je da bezbedno pohranite ključ.
Pretpostavimo da odlučite da ključ uvijek držite sa sobom, pružajući pristup trezoru po potrebi. Ali brzo ćete shvatiti da takvo rješenje nije dobro u praksi, jer svaki put morate biti fizički prisutni da biste otvorili trezor. Šta je sa odmorom koji vam je obećan? Osim toga, pitanje je još strašnije: šta ako ste izgubili jedini ključ?
Sa idejom odmora odlučujete da napravite kopiju ključa i povjerite je drugom zaposleniku. Međutim, shvaćate da ni to nije idealno. Udvostručavanjem broja ključeva udvostručili ste i šanse za krađu ključeva.
Očajni, uništite duplikat i odlučite podijeliti originalni ključ na pola. Sada mislite da dvije osobe od povjerenja s fragmentima ključa moraju biti fizički prisutne da bi preuzele ključ i otvorile trezor. To znači da lopov treba ukrasti dva fragmenta, što je dvostruko teže od krađe jednog ključa. Međutim, ubrzo shvatite da ova šema nije mnogo bolja od samo jednog ključa, jer ako neko izgubi polovinu ključa, cijeli ključ se ne može povratiti.
Problem se može riješiti nizom dodatnih ključeva i brava, ali će ovaj pristup brzo zahtijevati много ključeve i brave. Vi odlučujete da je idealna šema 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 šeme upravljanja ključem razmišljao je Adi Shamir 1979. kada je objavio svoj rad . U članku se ukratko objašnjava tzv 
šema praga za efektivnu podjelu tajne vrijednosti (na primjer, kriptografski ključ). dijelovi. Tada, kada i samo kada barem из dijelovi su sastavljeni, lako možete vratiti tajnu .
Sa sigurnosne tačke gledišta, važno svojstvo ove šeme je da napadač ne treba da nauči apsolutno ništa ako nema barem dijelovi. Čak i prisustvo dijelovi ne bi trebali davati nikakve informacije. Mi zovemo ovu imovinu semantička sigurnost.
Polinomska interpolacija
Prag Šamir šema izgrađen oko koncepta polinomska interpolacija. Ako niste upoznati s ovim konceptom, zapravo je prilično jednostavan. Općenito, ako ste ikada crtali tačke na grafikonu, a zatim ih povezivali linijama ili krivuljama, već ste to koristili!
Kroz dvije tačke možete povući neograničen broj polinoma stepena 2. Da biste odabrali jedini od njih, potrebna vam je treća tačka. Ilustracija:
Razmotrimo polinom sa stepenom jedan, . Ako želite da iscrtate ovu funkciju na grafikonu, koliko bodova vam je potrebno? Pa, znamo da je ovo linearna funkcija koja formira liniju i stoga su nam potrebne najmanje dvije točke. Zatim, razmotrimo polinomsku funkciju sa stepenom dva, . Ovo je kvadratna funkcija, tako da su za iscrtavanje grafa potrebne najmanje tri tačke. Šta kažete na polinom sa stepenom tri? Najmanje četiri tačke. I tako dalje i tako dalje.
Zaista cool stvar u vezi s ovim svojstvom je da, s obzirom na stupanj polinomske funkcije i najmanje tačke, možemo izvesti dodatne tačke za ovu polinomsku funkciju. Ove dodatne tačke nazivamo ekstrapolacijom polinomska interpolacija.
Pravljenje tajne
Možda ste već shvatili da ovdje dolazi do izražaja Shamirova pametna šema. Pretpostavimo našu tajnu Je . Možemo se okrenuti do tačke na grafikonu i smisliti polinomsku funkciju sa stepenom , što zadovoljava ovu tačku. Prisjetite se toga će biti naš prag potrebnih fragmenata, tako da ako postavimo prag na tri fragmenta, moramo odabrati polinomsku funkciju sa stupnjem dva.
Naš polinom će imati oblik gde и su nasumično odabrani pozitivni cijeli brojevi. Samo gradimo polinom sa stepenom , gdje je slobodni koeficijent - Ovo je naša tajna , i svaki od sljedećih termini je nasumično odabran pozitivni koeficijent. Ako se vratimo na izvorni primjer i pretpostavimo da , tada dobijamo funkciju .
U ovom trenutku možemo generirati fragmente povezivanjem jedinstveni cijeli brojevi u gde (jer je to naša tajna). U ovom primjeru želimo distribuirati četiri fragmenta s pragom od tri, tako da nasumično generišemo bodove i pošalji po jedan bod svakoj od četiri osobe od povjerenja, čuvarima ključa. To takođe govorimo ljudima , jer se smatra javnom informacijom i neophodan je za oporavak .
Secret Recovery
Već smo raspravljali o konceptu polinomske interpolacije i kako ona leži u osnovi Shamirove šeme praga. . Kada bilo koja tri od četiri povjerenika žele vratiti , oni samo trebaju interpolirati sa svojim jedinstvenim tačkama. Da bi to učinili, oni mogu definirati svoje tačke i izračunajte Lagrangeov interpolacijski polinom koristeći sljedeću formulu. Ako vam je programiranje jasnije od matematike, onda je pi u suštini operator for, što množi sve rezultate, a sigma je forto sve zbraja.
u možemo to riješiti ovako i vratiti našu originalnu polinomsku funkciju:
Pošto to znamo , oporavak se radi jednostavno:
Korištenje nesigurne cjelobrojne aritmetike
Iako smo osnovnu Shamirovu ideju uspješno primijenili , ostaje nam problem koji smo do sada ignorisali. Naša polinomska funkcija koristi nesigurnu cjelobrojnu aritmetiku. Imajte na umu da za svaku dodatnu točku koju napadač dobije na našem grafu funkcije, postoji manje mogućnosti za druge točke. To možete vidjeti vlastitim očima kada iscrtate sve veći broj tačaka za polinomsku funkciju koristeći cjelobrojnu aritmetiku. Ovo je kontraproduktivno za naš navedeni sigurnosni cilj, jer napadač ne bi trebao znati apsolutno ništa dok barem ne zna fragmenti.
Da biste pokazali koliko je slaba šema celobrojne aritmetike, razmotrite scenario u kojem je napadač dobio dva boda i zna javne informacije koje . Iz ovih informacija može zaključiti , jednako dva, i povežite poznate vrijednosti u formulu и .
Napadač tada može pronaći , računajući :
Pošto smo definisali kao nasumično odabrani pozitivni cijeli brojevi, postoji ograničen broj mogućih . Na osnovu ovih informacija napadač može zaključiti , jer će sve veće od 5 biti negativan. Ispostavilo se da je to istina, pošto smo utvrdili
Napadač tada može izračunati moguće vrijednosti , zamjena в :
Sa ograničenim mogućnostima za postaje jasno kako je lako pokupiti i provjeriti vrijednosti . Ovdje postoji samo pet opcija.
Rješavanje problema s nesigurnom cjelobrojnom aritmetikom
Da bi popravio ovu ranjivost, Shamir predlaže korištenje modularne aritmetike zamjenom na gde и je skup svih prostih brojeva.
Prisjetimo se brzo kako modularna aritmetika funkcionira. Ručni satovi su poznati koncept. Ona koristi sat . Čim kazaljka sata prođe dvanaest, vraća se na jedan. Zanimljivo svojstvo ovog sistema je da samo gledanjem na sat ne možemo zaključiti koliko je obrtaja kazaljka sata napravila. Međutim, ako znamo da je kazaljka sata prošla 12 četiri puta, možemo u potpunosti odrediti broj sati koji su prošli jednostavnom formulom gde je naš djelitelj (ovdje ), - ovo je koeficijent (koliko puta djelitelj bez ostatka ide u originalni broj, ovdje ), i je ostatak, koji obično vraća poziv modulo operatoru (ovdje ). Poznavanje svih ovih vrijednosti nam omogućava da riješimo jednačinu za , ali ako preskočimo koeficijent, nikada nećemo moći vratiti izvornu vrijednost.
Možemo demonstrirati kako ovo poboljšava sigurnost našeg kola primjenom kola na prethodni primjer i korištenjem . Naša nova polinomska funkcija , i nove tačke . Sada čuvari ključeva mogu ponovo koristiti polinomsku interpolaciju da rekonstruišu našu funkciju, samo što ovaj put operacije sabiranja i množenja moraju biti praćene modulo redukcijom. (npr ).
Koristeći ovaj novi primjer, pretpostavimo da je napadač naučio dvije od ovih novih stvari, i javne informacije . Ovog puta napadač, na osnovu svih informacija koje ima, prikazuje sledeće funkcije, gde je skup svih pozitivnih cijelih brojeva, i predstavlja koeficijent modula .
Sada naš uljez ponovo pronalazi , računajući :
Zatim ponovo pokušava da se povuče , zamjena в :
Ovaj put ima ozbiljan problem. Formuli nedostaju vrijednosti , и . Budući da postoji beskonačan broj kombinacija ovih varijabli, on ne može dobiti nikakve dodatne informacije.
Sigurnosna razmatranja
Šamirova šema dijeljenja tajne sugerira sigurnost informacija. To znači da je matematika jaka čak i protiv napadača s neograničenom računarskom snagom. Međutim, shema još uvijek sadrži nekoliko poznatih problema.
Na primjer, Shamir šema ne stvara fragmenti koje treba provjeriti, odnosno ljudi su slobodni da iznesu lažne fragmente i ometaju pronalaženje ispravne tajne. Neprijateljski čuvar fragmenta sa dovoljno informacija može čak proizvesti još jedan fragment promenom po Vašem nahođenju. Ovaj problem je riješen sa provjerljive šeme dijeljenja tajne, kao što je Feldmanova šema.
Drugi problem je što je dužina bilo kojeg fragmenta jednaka dužini odgovarajuće tajne, tako da je dužinu tajne lako odrediti. Ovaj problem se rješava trivijalnim padding tajna proizvoljnim brojevima do fiksne dužine.
Na kraju, važno je napomenuti da naši sigurnosni problemi mogu ići dalje od same šeme. Za stvarne kriptografske aplikacije, često postoji opasnost od napada sa strane kanala, kada napadač pokušava izvući korisne informacije iz vremena izvršavanja aplikacije, keširanja, rušenja itd. Ako je ovo zabrinutost, trebali biste pažljivo razmotriti korištenje zaštitnih mjera tokom razvoja, kao što su funkcije i pretraživanja u stalnom vremenu, spriječiti spremanje memorije na disk i razmotriti niz drugih stvari koje su izvan dosega ovog članka.
Demo
U postoji interaktivna demonstracija Shamirove šeme dijeljenja tajne. Demonstracija je napravljena na bazi biblioteke , koji je i sam JavaScript port popularnog programa . Imajte na umu da izračunavanje velikih vrijednosti , и može potrajati
izvor: www.habr.com