Vaatame olukorda, kus on vaja tagada pangahoiustamise turvalisus. Seda peetakse täiesti ligipääsmatuks ilma võtmeta, mille saad esimesel tööpäeval. Sinu eesmärk on turvaliselt hoida võti.

Oletame, et otsustasid alati hoida võtit enda juures, andes ligipääsu hoiusele vastavalt vajadusele. Aga sa mõistad kiiresti, et selline lahendus ei skaleeru hästi, kuna iga kord, kui on vaja avada hoius, on vajalik sinu füüsiline kohalolek. Aga kuidas on puhkuseteemaga, mida lubati? Veelgi enam, hiilivad mõtted: mis juhtub, kui kaotad ainulaadse võtme?

Puhkuse mõttega otsustasid sa teha võtme koopia ja usaldada selle teisele töötajale. Siiski mõistad, et see pole ka ideaalne. Kahekordistades võtmete arvu, kahekordistad sa ka varguse võimalusi.

Kehva välja, hävitad sa koopia ja otsustad jagada algse võtme kaheks. Praegu arvad sa, et kaks usaldusväärset inimest fragmentidega võtmetest peavad füüsiliselt kohal olema, et kokku koguda võti ja avada hoius. See tähendab, et vargal on vaja varastada kaks fragmenti, mis on kahekordselt keerulisem kui ühe võtme varastamine. Kuid peagi mõistad, et see skeem ei ole palju parem kui lihtsalt üks võti, kuna kui keegi kaotab ühe võtme osa, ei saa kogu võtit taastada.

Probleemi saab lahendada täiendavate võtmete ja lukkudega, kuid sellise lähenemise puhul on kiiresti vaja palju võtmeid ja lukke. Otsustad, et ideaalses skeemis tuleks jagada võti, et turvalisus ei sõltuks täielikult ühest inimesest. Oled ka veendunud, et peaks olema mingi lävi fragmentide arvu osas, et ühe fraktsiooni kadumise (või kui inimene läheb puhkusele) korral jääks kogu võti toimivaks.

Kuidas jagada saladust

Sellise võtmehalduse skeemi mõtles välja Adi Shamir 1979. aastal, kui ta avaldas oma töö „Kuidas jagada saladust”. Artiklis selgitab ta lühidalt nn lävitaskeemi, et tõhusalt jagada saladuslik väärtus (näiteks krüptograafiline võti) osadeks järel. Siis, kui ja ainult siis, kui vähemalt API-s osa on kogutud, saab saladuse kergesti taastada. .

Turvalisuse seisukohalt on selle skeemi oluline omadus see, et ründaja ei tohiks teada saada absoluutselt midagi, kui tal ei ole vähemalt osakest. Isegi ühe osakese olemasolu ei tohiks anda mingit teavet. Me nimetame seda omadust semantiliseks turvalisuseks Polünoomi interpolatsioon.

Shamira lävendiskeem

on üles ehitatud polünoomi interpolatsiooni kontseptsiooni ümber. Kui te pole selle kontseptsiooniga tuttav, siis see on tegelikult üsna lihtne. Üldiselt, kui olete kunagi graafikule punkte joonistanud ja seejärel neid joonte või kõveratega ühendades, siis olete seda juba kasutanud! Kaks punkti võivad määrata piiramatult palju 2. astme polüneome. Nende hulgast unikaalse valimiseks on vajalik kolmas punkt. Näide: Võtame ühe astme polünoomi,. Kui soovite seda funktsiooni graafikule joonistada, kui palju punkte on vaja? Noh, me teame, et see on lineaarefunktsioon, mis moodustab joone, ning seetõttu on vajalik vähemalt kaks punkti. Järgmine vaatleme kahe astme polünoomi,

. See on ruutfunktsioon, seega on graafiku loomiseks vajalik vähemalt kolm punkti. Ent kuidas on kolme astme polüneomiga? Vähemalt neli punkti. Ja nii edasi. Vikipeedia

Tõeliselt lahe asi selle omaduse juures on see, et arvestades polünoomi funktsiooni astet ja vähemalt punkti, saame tuletada täiendavaid punkte selle polünoomi funktsiooni jaoks. Nende täiendavate punktide ekstrapoleerimist nimetatakse polünoomi interpolatsiooniks

Saladuse koostamine Võite juba aru saada, et siin astub mängu nutikas Shamiri skeem. Oletame, et meie saladus on . Saame muuta.

punktiks graafikul

ja välja mõelda polünoomi funktsiooni astmega — see on , mis rahuldab seda punkti. Peame meeles pidama, et on meie nõutud fragmentide lävend, seega kui seadistame läve kolme fragmenti peale, siis peame valima polünoomi funktsiooni astmega kaks. Meie polünoom on kujul — juhuslikult valitud positiivsed täisarvud. Me ehitame lihtsalt polünoomi astmega , kus vaba kordaja

on meie saladus , kus ja , ja iga järgmine punkti jaoks  . , а у каждого из последующих liikmetel on juhuslikult valitud positiivne koefitsient. Kui naasta algse näite juurde ja eeldada, et , saame siis funktsiooni .

Selles etapis saame genereerida fragmente, ühendades ainulaadseid täisarve , kus (sest see on meie saladus). Antud näites soovime jagada nelja fragmenti lävendi kolme, seetõttu genereerime juhuslikult punktid ja saadame igale neljale usaldusväärsele isikule, võtmekaitsjale, ühe punkti. Anname ka inimestele teada, et , kuna seda peetakse avalikuks informatsiooniks ja see on vajalik taastamiseks .

Saladuse taastamine

Oleme juba arutanud polünoomi interpolatsiooni kontseptsiooni ja et see on aluseks Shamir'i läve skeemile . Kui tahes kolm neljast usaldusisikust soovivad taastada , peavad nad lihtsalt interpolatsiooni tegema oma ainulaadsete punktidega. Selleks võivad nad määrata oma punktid ja arvutada Lagrange'i interpolatsioonipolünoomi, kasutades järgmist valemit. Kui programmeerimine on teile tuttavam kui matemaatika, siis pii on põhimõtteliselt operaator for, mis korrutab kõik tulemused, ja sigma on for, mis on kõik summad.

Kaugjuhtimisega saame selle lahendada järgmiselt ja tagastada oma algse polünoomi funktsiooni:

Kuna me teame, et , taastamine käib lihtsalt:

Ohutu täisarvude aritmeetika kasutamine

Kuigi oleme edukalt rakendanud Shamir'i põhiideed , on meil probleem, mida oleme seni ignoreerinud. Meie polünoomi funktsioon kasutab ebaturvalist täisarvude aritmeetikat. Pidage meeles, et iga täiendava punkti puhul, mille ründeõigus omandab meie funktsiooni graafikult, jääb vähem võimalusi teiste punktide jaoks. Saate seda oma silmaga näha, kui joonistate graafikut, suurendades polünoomi funktsioonile punkte, kasutades täisarvude aritmeetikat. See on meie deklaratsiooni turvalisuse eesmärgiga vastuolus, sest kurjategija ei tohiks absoluutselt midagi teada, kuni neil pole vähemalt fragmente.

Kuna demonstreerime, kui nõrk on täisarvude aritmeetika skeem, arvestame stsenaariumi, kus kurjategija on saanud kaks punkti ja teab avalikku teavet, et . Selle teabe põhjal saab järeldada , mis on kaks, ja sisestada valemisse tuntud väärtused ja .

Seejärel võib ründaja leida , arvestades :

Kuna oleme määratlenud kui juhuslikult valitud positiivsed täisarvud, on piiratud arv võimalikke . Selle teabe abil saab ründaja järeldada , kuna kõik, mis on üle 5, muudab negatiivseks. See osutub tõeks, kuna oleme määratlenud

Seejärel võib ründaja arvutada võimalikke väärtusi , asendades ja :

Piiratud valikute komplektiga on selge, kui lihtne on leida ja kontrollida väärtusi . Siin on kokku viis varianti.

Probleemi lahendamine ohtliku täisarvuarvutusega

Selle haavatavuse kõrvaldamiseks soovitab Shamir kasutada moodulaarset aritmeetikat, asendades . Tundub, et , kus ja — kõikide algarvude hulk.

Korrake kiiresti, kuidas moodulaarne aritmeetika töötab. Kellad on juba tuttav kontseptsioon. Need kasutavad kelli, mis on . Kui tunni käsi läbib kaksteist, pöördub see tagasi ühte. Selle süsteemi huvitav omadus on see, et lihtsalt kelladele vaadates ei saa me järeldada, mitu korda tundidoos on käinud. Kuid kui me teame, et tunni käsi on neli korda möödunud 12-st, saame kogu möödunud tunni arvu täiesti määrata lihtsa valemi abil , kus  — see on meie jagaja (siin ),  — see on koefitsient (mitu korda jagaja jagab algset numbrit ilma jäägita, siin ), ja  — see on jääk, mille tavaliselt tagastab mooduliga operatsiooni väljakutse (siin ). Kõikide nende väärtuste teadmine võimaldab meil lahendada võrrandi , kuid kui me jätame koefitsiendi vahele, ei saa me kunagi taastada algset väärtust.

Saame demonstreerida, kuidas see parandab meie skeemi turvalisust, rakendades skeemi meie eelnevale näitele ja kasutades . Meie uus polünoomiline funktsioon , ja uued punktid . Nüüd saavad võtmehoidjad uuesti kasutada polünoomilist interpoleerimist, et taastada meie funktsioon, ainult et seekord peavad liitmis- ja korrutamisoperatsioonid olema koos jäägiga jagamisel (nt. ).

Kasutades seda uut näidet, oletame, et ründaja teada kaks neist uutest punktidest, , ning avalik teave . Seekord ründaja tugineb kogu oma olemasolevale teabele, et tuletada järgmisi funktsioone, kus  — kõik positiivsete täisarvude kogum, ja esindab mudelit. .

Nüüd leiab meie kurjategija taas , arvutades :

Seejärel proovib ta taas tuletada , asendades ja :

Seekord on tal tõsine probleem. Valemist puuduvad väärtused , ja . Kuna nende muutuja kombinatsioone on lõpmatu arv, ei saa ta mingit lisainfot.

Turvakaalutlused

Shamir'i saladuse jagamise skeem pakub turvalisust teooria kohaselt. See tähendab, et matemaatika on tugev isegi ründaja vastu, kellel on piiramatu arvutusvõime. Siiski sisaldab skeem endiselt mitmeid tuntud probleeme.

Näiteks Shamir'i skeem ei loo kontrollitavaid fragmente, see tähendab, et inimesed saavad vabalt esitada valefragmente ja segada õige saladuse taastamist. Vaenulik fragmentide hoidja, kellel on piisavalt teavet, võib isegi luua teise fragmendi, muutes oma äranägemisel. See probleem lahendatakse kontrollitavate saladuse jagamise skeemide abil, nagu Felmani skeem.

Teine probleem on see, et igasuguse fragmenti pikkus võrdub vastava saladuse pikkusega, mistõttu on saladuse pikkust kerge määrata. See probleem lahendatakse triviaalsete täidete saladuse täiendamisega juhuslike numbritega kindla pikkuseni.

Lõpuks on oluline märkida, et meie mured turvalisuse osas võivad ulatuda kaugemale skeemi enda piiridest. Reaalsetes krüptograafilistes rakendustes eksisteerib sageli oht kõrvalkanali rünnakuteks, kui ründaja püüab välja tuua kasuliku teabe rakenduse tööajast, vahemälu, tõrgetest jne. Kui see teeb murettekitavaks, tuleks arendada kaitsemeetmete kasutamist, nagu pideva töötlemise ajaga funktsioonid ja otsingud, vältida mälu salvestamist kettale ning kaaluda mitmeid muid aspekte, mis jäävad selle artikli piiridest väljapoole.

Demo

Pealehe sellel leheküljel on interaktiivne Shamir'i saladuse jagamise skeem. Demonstreerimine on tehtud libraryst ssss-js, mis on iseenesest populaarse programmi ssssPange tähele, et suurte väärtuste arvutamine , ja võib võtta aega.

Allikas: habr.com