Razmislite o scenariju, ko morate zavarovati bančni trezor. Šteje se, da je popolnoma nepremagljiv brez ključa, ki ga dobite že prvi dan dela. Vaš cilj je varno shraniti ključ.
Recimo, da se odločite, da boste imeli ključ ves čas pri sebi in po potrebi omogočili dostop do shrambe. Toda hitro boste spoznali, da takšna rešitev v praksi ni primerna, saj je ob vsakem odpiranju shrambe potrebna vaša fizična prisotnost. Kaj pa dopust, ki so vam ga obljubili? Poleg tega je še bolj strašljivo vprašanje: kaj pa, če bi izgubili svoj edini ključ?
Z mislijo na dopust se odločite narediti kopijo ključa in jo zaupati drugemu zaposlenemu. Vendar razumete, da tudi to ni idealno. S podvojitvijo števila ključev podvojite tudi možnosti za krajo ključev.
V obupu uničite dvojnik in se odločite, da boste originalni ključ razdelili na pol. Zdaj bi si mislili, da bi morali biti dve zaupanja vredni osebi z delci ključev fizično prisotni, da prevzameta ključ in odpreta trezor. To pomeni, da mora tat ukrasti dva kosa, kar je dvakrat težje kot ukrasti en ključ. Vendar pa kmalu ugotovite, da ta shema ni veliko boljša od samo enega ključa, kajti če nekdo izgubi polovico ključa, celotnega ključa ni mogoče obnoviti.
Težavo je mogoče rešiti z vrsto dodatnih ključev in ključavnic, vendar bo ta pristop hitro zahteval много ključi in ključavnice. Odločite se, da bi bila idealna zasnova deljenje ključa, tako da varnost ni v celoti odvisna od ene osebe. Prav tako sklepate, da mora obstajati nek prag za število fragmentov, tako da če se en fragment izgubi (ali če gre oseba na dopust), celoten ključ ostane funkcionalen.
Kako deliti skrivnost
O tej vrsti sheme upravljanja ključev je razmišljal Adi Shamir leta 1979, ko je objavil svoje delo . Članek na kratko pojasnjuje t.i 
shema praga za učinkovito razdelitev skrivne vrednosti (kot je kriptografski ključ). deli. Takrat, ko in samo ko vsaj z dne deli so sestavljeni, lahko preprosto obnovite skrivnost .
Z varnostnega vidika je pomembna lastnost te sheme ta, da napadalec ne sme vedeti popolnoma ničesar, razen če ima vsaj deli. Tudi prisotnost deli ne smejo zagotavljati nobenih informacij. To lastnost imenujemo semantična varnost.
Polinomska interpolacija
Shamirjeva shema praga zgrajen okoli koncepta polinomska interpolacija. Če niste seznanjeni s tem konceptom, je pravzaprav precej preprost. Pravzaprav, če ste kdaj narisali točke na graf in jih nato povezali s črtami ali krivuljami, ste to že uporabili!
Skozi dve točki lahko narišete neomejeno število polinomov stopnje 2. Če želite med njimi izbrati edinega, potrebujete tretjo točko. Ilustracija:
Razmislite o polinomu prve stopnje, . Če želite to funkcijo narisati na grafu, koliko točk potrebujete? No, vemo, da je to linearna funkcija, ki tvori premico in zato potrebuje vsaj dve točki. Nato razmislite o polinomski funkciji druge stopnje, . To je kvadratna funkcija, zato so za izris grafa potrebne vsaj tri točke. Kaj pa polinom tretje stopnje? Vsaj štiri točke. In tako dalje in tako naprej.
Res kul stvar pri tej lastnosti je, da glede na stopnjo polinomske funkcije in vsaj točke, lahko izpeljemo dodatne točke za to polinomsko funkcijo. Te dodatne točke imenujemo ekstrapolacija polinomska interpolacija.
Izmišljanje skrivnosti
Morda ste že ugotovili, da tukaj nastopi Shamirjeva pametna shema. Povejmo svojo skrivnost - Je . Lahko se obrnemo do točke na grafu in pripravite polinomsko funkcijo s stopnjo , ki izpolnjuje to točko. Naj vas spomnimo, da bo naš prag zahtevanih fragmentov, tako da, če nastavimo prag na tri fragmente, moramo izbrati polinomsko funkcijo z drugo stopnjo.
Naš polinom bo imel obliko Če и — naključno izbrana pozitivna cela števila. Samo konstruiramo polinom s stopnjo , kjer je prosti koeficient - To je naša skrivnost , in za vsakega od naslednjih izrazi obstaja naključno izbran pozitivni koeficient. Če se vrnemo k prvotnemu primeru in predpostavimo, da , potem dobimo funkcijo .
Na tej točki lahko ustvarimo fragmente s povezovanjem enolična cela števila v Če (ker je to naša skrivnost). V tem primeru želimo razdeliti štiri fragmente s pragom tri, zato naključno ustvarimo točke in pošljite eno točko vsakemu od štirih zaupanja vrednih oseb, skrbnikov ključa. To ljudem tudi sporočamo , ker se to šteje za javne informacije in je potrebno za izterjavo .
Obnovitev skrivnosti
Razpravljali smo že o konceptu polinomske interpolacije in o tem, kako je osnova Shamirjeve sheme praga . Ko kateri koli trije od štirih skrbnikov želijo obnoviti , morajo samo interpolirati s svojimi edinstvenimi točkami. Da bi to naredili, lahko določijo svoje točke in izračunajte Lagrangeov interpolacijski polinom z naslednjo formulo. Če vam je programiranje bolj jasno kot matematika, potem je pi v bistvu operator for, ki pomnoži vse rezultate, sigma pa je for, kar sešteje vse.
Ob rešimo jo lahko takole in vrnemo prvotno polinomsko funkcijo:
Ker to vemo , okrevanje narejeno preprosto:
Uporaba nevarne aritmetike celih števil
Čeprav smo Shamirjevo osnovno idejo uspešno uporabili , ostane nam problem, ki smo ga do sedaj ignorirali. Naša polinomska funkcija uporablja nevarno celoštevilsko aritmetiko. Upoštevajte, da je za vsako dodatno točko, ki jo napadalec pridobi na grafu naše funkcije, manj možnosti za druge točke. To lahko vidite na lastne oči, ko narišete naraščajoče število točk za polinomsko funkcijo z uporabo celoštevilske aritmetike. To je kontraproduktivno za naš zastavljeni varnostni cilj, saj napadalec ne bi smel vedeti ničesar, dokler nima vsaj drobci.
Če želite pokazati, kako šibko je aritmetično vezje celih števil, razmislite o scenariju, v katerem je napadalec pridobil dve točki in pozna informacije javnega značaja, ki . Iz teh podatkov lahko sklepa , enako dve, in znane vrednosti vstavite v formulo и .
Napadalec lahko nato najde , štetje :
Ker smo definirali kot naključno izbrana pozitivna cela števila, obstaja omejeno število možnih . Z uporabo teh informacij lahko napadalec sklepa , saj bo zadostovalo vse, kar je večje od 5 negativno. To se izkaže za res, saj smo ugotovili
Napadalec lahko nato izračuna možne vrednosti zamenjava в :
Z omejenimi možnostmi za postane jasno, kako enostavno je izbrati in preveriti vrednosti . Tukaj je samo pet možnosti.
Reševanje problema z nevarno aritmetiko celih števil
Za odpravo te ranljivosti Shamir predlaga uporabo modularne aritmetike, zamenjavo o Če и — množica vseh praštevil.
Na hitro se spomnimo, kako deluje modularna aritmetika. Ura s kazalci je znan koncept. Uporablja uro, ki je . Takoj ko urni kazalec preteče dvanajst, se vrne na ena. Zanimiva lastnost tega sistema je, da zgolj s pogledom na uro ne moremo sklepati, koliko obratov je naredil urni kazalec. Če pa vemo, da je urni kazalec štirikrat pretekel 12, lahko s preprosto formulo popolnoma določimo število pretečenih ur Če je naš delitelj (tukaj ), je koeficient (kolikokrat gre delitelj v prvotno število brez ostanka, tukaj ), in je ostanek, ki običajno vrne klic modulo operaterja (tukaj ). Poznavanje vseh teh vrednosti nam omogoča, da rešimo enačbo za , če pa koeficient zgrešimo, ne bomo mogli nikoli povrniti prvotne vrednosti.
Lahko pokažemo, kako to izboljša varnost naše sheme, tako da shemo uporabimo v prejšnjem primeru in uporabimo . Naša nova polinomska funkcija in nove točke . Zdaj lahko skrbniki ključev ponovno uporabijo polinomsko interpolacijo za rekonstrukcijo naše funkcije, le da mora tokrat operacije seštevanja in množenja spremljati redukcija po modulu (npr ).
Z uporabo tega novega primera predpostavimo, da se je napadalec naučil dveh od teh novih točk, , in javne informacije . Tokrat napadalec na podlagi vseh informacij, ki jih ima, izpiše naslednje funkcije, kjer je množica vseh pozitivnih celih števil in predstavlja koeficient modula .
Zdaj naš napadalec spet najde , računanje :
Potem poskusi znova zamenjava в :
Tokrat ima resen problem. V formuli manjkajo vrednosti , и . Ker obstaja neskončno število kombinacij teh spremenljivk, ne more dobiti nobene dodatne informacije.
Varnostni premisleki
Shamirjeva shema delitve skrivnosti nakazuje varnost z vidika informacijske teorije. To pomeni, da je matematika odporna tudi proti napadalcu z neomejeno računalniško močjo. Vendar vezje še vedno vsebuje več znanih težav.
Na primer, Shamirjeva shema ne ustvarja fragmenti, ki jih je treba preveriti, to pomeni, da lahko ljudje prosto predstavljajo lažne fragmente in posegajo v obnovitev pravilne skrivnosti. Sovražni čuvaj fragmentov z dovolj informacijami bi lahko s spremembo celo ustvaril nov fragment po lastni presoji. Ta problem je rešen z uporabo preverljive sheme deljenja skrivnosti, kot je Feldmanova shema.
Druga težava je, da je dolžina katerega koli fragmenta enaka dolžini ustrezne skrivnosti, zato je dolžino skrivnosti enostavno določiti. Ta problem je mogoče rešiti s trivialnim oblazinjenje skrivnost s poljubnimi številkami do fiksne dolžine.
Nazadnje je pomembno omeniti, da lahko naši pomisleki glede varnosti presegajo samo zasnovo. Za dejanske kriptografske aplikacije pogosto obstaja grožnja stranskih kanalskih napadov, kjer napadalec poskuša izvleči koristne informacije iz časa izvajanja aplikacije, predpomnjenja, zrušitev itd. Če je to zaskrbljujoče, je treba med razvojem skrbno pretehtati uporabo zaščitnih ukrepov, kot so funkcije in iskanja v konstantnem času, preprečevanje shranjevanja pomnilnika na disk in številne druge pomisleke, ki presegajo obseg tega članka.
Demo
Na Na voljo je interaktivna predstavitev Shamirjeve sheme za skupno rabo skrivnosti. Predstavitev na podlagi knjižnice , ki je sama vrata JavaScript priljubljenega programa . Upoštevajte, da izračun velikih vrednosti , и lahko traja nekaj časa.
Vir: www.habr.com