Mõelge stsenaariumile, kus peate tagama pangahoidla. Seda peetakse täiesti immutamatuks ilma võtmeta, mis antakse teile esimesel tööpäeval. Teie eesmärk on võtit turvaliselt hoida.

Oletame, et otsustate võtit alati endaga kaasas hoida, võimaldades vajaduse korral juurdepääsu salvestusruumile. Kuid saate kiiresti aru, et selline lahendus ei mastaap praktikas hästi, sest teie füüsiline kohalolek on vajalik iga kord, kui salvestusruumi avate. Aga puhkus, mida sulle lubati? Lisaks on veelgi hirmutavam küsimus: mis siis, kui kaotate oma ainsa võtme?

Oma puhkust silmas pidades otsustate teha võtmest koopia ja usaldada selle teisele töötajale. Samas saate aru, et ka see pole ideaalne. Kahekordistades võtmete arvu, kahekordistate ka võtmevarguse tõenäosust.

Meeleheitel hävitate duplikaadi ja otsustate algse võtme pooleks jagada. Nüüd võiks arvata, et võtme kogumiseks ja varahoidla avamiseks peavad füüsiliselt kohal olema kaks usaldusväärset inimest, kellel on võtmekillud. See tähendab, et vargal on vaja varastada kaks tükki, mis on kaks korda raskem kui ühe võtme varastamine. Peagi mõistad aga, et see skeem polegi palju parem kui üks võti, sest kui keegi kaotab poole võtme, siis täisvõtit enam tagasi ei saa.

Probleemi saab lahendada täiendavate võtmete ja lukkude seeriaga, kuid see lähenemine nõuab kiiresti много võtmed ja lukud. Otsustate, et ideaalne lahendus oleks võtit jagada, et turvalisus ei sõltuks täielikult ühest inimesest. Samuti järeldate, et fragmentide arvul peab olema mingi lävi, et kui üks fragment kaob (või kui inimene läheb puhkusele), jääks kogu võti toimima.

Kuidas jagada saladust

Seda tüüpi võtmehaldusskeemile mõtles Adi Shamir 1979. aastal, kui ta oma teose avaldas "Kuidas jagada saladust". Artiklis selgitatakse lühidalt nn läviskeem salajase väärtuse (nt krüptovõtme) tõhusaks jagamiseks osad. Siis, millal ja ainult siis, vähemalt kohta osad on kokku pandud, saate saladuse hõlpsalt taastada .

Turvalisuse seisukohast on selle skeemi oluline omadus see, et ründaja ei peaks teadma absoluutselt midagi, kui tal pole vähemalt osad. Isegi kohalolu osad ei tohiks anda mingit teavet. Me nimetame seda kinnisvara semantiline turvalisus.

Polünoomiline interpolatsioon

Shamiri läve skeem kontseptsiooni ümber ehitatud polünoomiline interpolatsioon. Kui te pole selle kontseptsiooniga tuttav, on see tegelikult üsna lihtne. Tegelikult, kui olete kunagi joonistanud graafikule punkte ja seejärel ühendanud need joonte või kõveratega, olete seda juba kasutanud!

Kahe punkti kaudu saab joonistada piiramatu arvu 2. astme polünoome. Nende hulgast ainsa valimiseks on vaja kolmandat punkti. Illustratsioon: Wikipedia

Vaatleme esimese astmega polünoomi, . Kui soovite selle funktsiooni graafikule joonistada, mitu punkti teil on vaja? Noh, me teame, et see on lineaarne funktsioon, mis moodustab sirge ja seega vajab see vähemalt kahte punkti. Järgmiseks vaatleme teise astmega polünoomfunktsiooni, . See on ruutfunktsioon, seega on graafiku koostamiseks vaja vähemalt kolme punkti. Kuidas oleks kolmanda astmega polünoomiga? Vähemalt neli punkti. Ja nii edasi.

Tõeliselt lahe asi selle omaduse juures on see, et arvestades polünoomfunktsiooni astet ja vähemalt punktid, saame selle polünoomfunktsiooni jaoks tuletada lisapunkte. Nimetame nende lisapunktide ekstrapolatsiooni polünoomiline interpolatsioon.

Saladuse väljamõtlemine

Võib-olla olete juba aru saanud, et siin tuleb mängu Shamiri nutikas skeem. Ütleme oma saladuse - Kas . Me võime pöörata graafiku punkti ja leia astmega polünoomfunktsioon , mis seda punkti rahuldab. Tuletame teile seda meelde on meie nõutavate fragmentide lävi, nii et kui seame läveks kolm fragmenti, peame valima polünoomfunktsiooni astmega kaks.

Meie polünoomil on vorm Kus и — juhuslikult valitud positiivsed täisarvud. Me lihtsalt konstrueerime astmega polünoomi , kus vaba koefitsient  - See on meie saladus , ja iga järgneva jaoks on juhuslikult valitud positiivne koefitsient. Kui pöördume tagasi algse näite juurde ja eeldame, et , siis saame funktsiooni .

Sel hetkel saame luua fragmente ühendades kordumatud täisarvud Kus (sest see on meie saladus). Selles näites tahame jagada neli fragmenti lävega kolm, nii et genereerime punkte juhuslikult ja saatke igale neljale usaldusväärsele inimesele, võtme hoidjale, üks punkt. Anname sellest ka inimestele teada , kuna seda peetakse avalikuks teabeks ja see on taastamiseks vajalik .

Saladuse taastamine

Oleme juba arutanud polünoomi interpolatsiooni kontseptsiooni ja seda, kuidas see Shamiri läve skeemi aluseks on . Kui suvalised kolm neljast usaldusisikust soovivad taastada , peavad nad ainult interpoleerima oma ainulaadsete punktidega. Selleks saavad nad määrata oma punktid ja arvutage Lagrange'i interpolatsiooni polünoom järgmise valemi abil. Kui programmeerimine on teile selgem kui matemaatika, siis pi on sisuliselt operaator for, mis korrutab kõik tulemused ja sigma on for, mis liidab kõik kokku.

juures saame selle lahendada järgmiselt ja tagastada oma algse polünoomifunktsiooni:

Kuna me teame seda , taastumine lihtsalt tehtud:

Kasutades ebaturvalist täisarvulist aritmeetikat

Kuigi oleme Shamiri põhiideed edukalt rakendanud , oleme jäänud probleemiga, mida oleme seni ignoreerinud. Meie polünoomfunktsioon kasutab ebaturvalist täisarvulist aritmeetikat. Pange tähele, et iga täiendava punkti korral, mille ründaja meie funktsiooni graafikul saab, on teiste punktide jaoks vähem võimalusi. Seda näete oma silmaga, kui joonistate täisarvude aritmeetika abil polünoomfunktsiooni jaoks järjest suurema arvu punkte. See on vastuolus meie seatud turvaeesmärgiga, sest ründaja ei peaks teadma absoluutselt mitte midagi, kuni tal on vähemalt see olemas kilde.

Et näidata, kui nõrk on täisarvude aritmeetiline skeem, kaaluge stsenaariumi, kus ründaja sai kaks punkti ja teab seda avalikku teavet . Sellest teabest saab ta järeldada , võrdub kahega, ja sisestage teadaolevad väärtused valemisse и .

Seejärel saab ründaja leida , lugedes :

Kuna oleme määratlenud juhuslikult valitud positiivsete täisarvudena on võimalikke piiratud arv . Seda teavet kasutades saab ründaja järeldada , sest kõik, mis on suurem kui 5, sobib negatiivne. See osutub tõeks, kuna oleme otsustanud

Seejärel saab ründaja võimalikud väärtused välja arvutada asendamine в :

Piiratud valikutega saab selgeks, kui lihtne on väärtusi valida ja kontrollida . Siin on ainult viis võimalust.

Ülesande lahendamine ebaturvalise täisarvu aritmeetikaga

Selle haavatavuse kõrvaldamiseks soovitab Shamir kasutada modulaarset aritmeetikat, asendades edasi Kus и — kõigi algarvude hulk.

Tuletame kiiresti meelde, kuidas modulaararitmeetika töötab. Osutega kell on tuttav mõiste. Ta kasutab kella, mis on . Niipea kui tunniosuti läbib kaksteist, naaseb see ühele. Selle süsteemi huvitav omadus on see, et lihtsalt kella vaadates ei saa me järeldada, mitu pööret tunniosuti on teinud. Kui aga teame, et tunniosuti on neli korda möödunud 12, saame möödunud tundide arvu lihtsa valemi abil täielikult kindlaks teha Kus  on meie jagaja (siin ),  on koefitsient (mitu korda läheb jagaja algarvusse ilma jäägita, siin ) ja  on jääk, mis tavaliselt tagastab mooduloperaatori kõne (siin ). Kõigi nende väärtuste tundmine võimaldab meil lahendada võrrandi , aga kui koefitsiendist puudu jääb, ei saa me kunagi algset väärtust taastada.

Saame näidata, kuidas see parandab meie skeemi turvalisust, rakendades skeemi meie eelmises näites ja kasutades . Meie uus polünoomfunktsioon ja uued punktid . Nüüd saavad võtmehoidjad meie funktsiooni rekonstrueerimiseks taas kasutada polünoominterpolatsiooni, ainult seekord peab liitmis- ja korrutustehtetega kaasnema mooduli redutseerimine (nt ).

Seda uut näidet kasutades oletame, et ründaja õppis neist uutest punktidest kaks, ja avalikku teavet . Seekord väljastab ründaja kogu tema käsutuses oleva info põhjal järgmised funktsioonid, kuhu  on kõigi positiivsete täisarvude hulk ja tähistab mooduli koefitsienti .

Nüüd leiab meie ründaja uuesti , arvutades :

Siis proovib uuesti asendamine в :

Seekord on tal tõsine probleem. Valemil puuduvad väärtused , и . Kuna nende muutujate kombinatsioone on lõpmatu arv, ei saa ta lisateavet hankida.

Turvakaalutlused

Shamiri salajane jagamisskeem viitab turvalisus infoteooria seisukohalt. See tähendab, et matemaatika on vastupidav isegi piiramatu arvutusvõimsusega ründajale. Ahel sisaldab siiski mitmeid teadaolevaid probleeme.

Näiteks Shamiri skeem ei loo killud, mida tuleb kontrollidast inimesed võivad vabalt esitada võltskilde ja segada õige saladuse taastamist. Piisava teabega vaenulik killuhoidja võib muutudes isegi teise fragmendi toota oma äranägemise järgi. See probleem lahendatakse kasutades kontrollitavad salajagamisskeemid, nagu Feldmani skeem.

Probleemiks on ka see, et mis tahes fragmendi pikkus on võrdne vastava saladuse pikkusega, mistõttu on saladuse pikkust lihtne määrata. Seda probleemi saab lahendada triviaalselt polsterdus salajane suvaliste numbritega kuni fikseeritud pikkuseni.

Lõpuks on oluline märkida, et meie turvaprobleemid võivad ulatuda disainist endast kaugemale. Reaalmaailma krüptograafiliste rakenduste puhul on sageli oht külgkanalite rünnakuteks, kus ründaja püüab hankida kasulikku teavet rakenduse täitmisajast, vahemällu salvestamisest, krahhidest jne. Kui see on muret tekitav, tuleks arenduse ajal hoolikalt kaaluda kaitsemeetmete kasutamist, nagu funktsioonid ja konstantse aja otsingud, mälu kettale salvestamise vältimine ja mitmed muud kaalutlused, mis ei kuulu käesoleva artikli reguleerimisalasse.

Demo

Edasi see leht Shamiri salajase jagamisskeemi interaktiivne esitlus. Demonstratsioon raamatukogu põhjal ssss-js, mis ise on populaarse programmi JavaScripti port ssss. Pange tähele, et suurte väärtuste arvutamine , и võib aega võtta.

Allikas: www.habr.com