Kujutame ette olukorda, kus on vajalik pangahoiustamise turvalisuse tagamine. Seda peetakse täiesti ligipääsmatuks ilma võtmeta, mille saate esimese tööpäeva jooksul. Teie eesmärk on võti turvaliselt hoida.

Oletame, et otsustasite kogu aeg võtme enda juures hoida, võimaldades juurdepääsu hoiustamisele vajaduse korral. Kuid kiiresti mõistate, et selline lahendus ei toimi, kuna igaks hoiustamise avamiseks on vajalik teie füüsiline kohalolu. Mis siis, kui soovite puhkusele minna? Veelgi rohkem häirib teid küsimus: mis juhtub, kui kaotate ainulaadse võtme?

Mõeldes puhkusele, otsustasite teha võtme koopia ja anda see usaldusväärsele kolleegile. Kuid mõistate, et see pole ka ideaalne lahendus. Kahe võtme olemasolu kahekordistab ka võtme varguse võimalused.

Meeleheite tõttu hävitate koopia ja otsustate jagada algse võtme kahele osale. Nüüd arvate, et kaks usaldusväärset isikut, kellel on võtme fragmentide osad, peavad füüsiliselt kohal olema, et koos kokku panna võtmega ja avada ladu. See tähendab, et vargal on vaja varastada kaks fragmenti, mis teeb selle varguse kaks korda raskemaks kui ühe võtme varastamine. Siiski mõistate peagi, et see skeem ei ole palju parem kui lihtsalt üks võti, sest kui keegi kaotab poole võtme, ei saa tervet võtit taastada.

Probleemi saab lahendada täiendavate võtmete ja lukkude seeria abil, kuid sellise lähenemise korral on kiiresti vajalikud palju võtmed ja lukud. Otsustate, et ideaalne skeem peaks võtme jagama, et turvalisus ei sõltuks täielikult ühest inimesest. Jõuate ka järeldusele, et peab olema mingi minimaalne fragmentide arv, nii et ühe fragmendi kadumise korral (või kui inimene on puhkusele läinud) jääks kogu võti funktsionaalseks.

Kuidas jagada saladust

Sellise võtmete haldamise skeemi mõtles välja Adi Shamir 1979. aastal, kui avaldas oma töö „Kuidas jagada saladust“. Artiklis selgitatakse lühidalt nii nimetatud efektiivne piiriülese jagamise skeem, et jagada salajane väärtus (näiteks krüptograafiline võti) osadeks. Seejärel, kui vähemalt kohast osakest on kogutud, saab salajase väärtuse lihtsalt taastada. .

Turvalisuse seisukohast on selle skeemi oluline omadus see, et kurjategija ei tohiks teada midagi, kui tal ei ole vähemalt osakest. Isegi osakese olemasolu ei tohi andma mingit teavet. Me nimetame seda omadust semantiliseks turvalisuseks..

Polünoomiline interpolatsioon.

Shamir'i piiriülese skeem on üles ehitatud polünoomilise interpolatsiooni kontseptsioonile. Kui te pole selle kontseptsiooniga tuttav, on see tegelikult üsna lihtne. Üldiselt, kui olete kunagi joonistanud punkte graafikule ja seejärel neid joonte või kõveratega ühendama hakanud, olete juba seda kasutanud!

Kaks punkti võivad läbi minna piiramatu arvu teise astme polünoome. Nende seast ainulaadse valimiseks on vajalik kolmas punkt. Illustreerimiseks: Vikipeedia

Vaatame polünoomi, mille aste on üks, . Kui soovite seda funktsiooni graafikule joonistada, kui palju punkte teil vaja on? Noh, me teame, et see on lineaarne funktsioon, mis moodustab joone ja seetõttu on vajalik vähemalt kaks punkti. Edasi vaatame polünoomfunktsiooni astmega kaks, . See on ruutfunktsioon, seega on graafiku joonistamiseks vajalik vähemalt kolm punkti. Kuidas on kolmanda astme polünoomiga? Vähemalt neli punkti. Ja nii edasi ja nii edasi.

Tõeliselt lahe asi selle omaduse juures on see, et arvestades polünoomfunktsiooni astet ja vähemalt punkte, saame järeldada täiendavaid punkte selle polünoomfunktsiooni jaoks. Täiendavate punktide ekstrapoleerimist nimetame polünoominterpoleerimiseks..

Saladuse koostamine.

Võib-olla olete juba aru saanud, et siia astub mängu Shamir'i nutikas skeem. Oletame, et meie saladus — see on . Saame selle punktiks graafikul ja leiutada polünoomfunktsiooni astmega , mis rahuldab seda punkti. Kordan, et see on meie nõutavate fragmentide lävi, seega kui seame läve kolmeks fragmentideks, peame valima polünoomi, mille kraad on kaks.

Meie polünoom on kujul , kus ja — juhuslikult valitud positiivsed täisarvud. Ehitatakse lihtsalt polünoom, mille kraad on , kus vaba koefitsient  — see on meie saladus , ja iga järgmise liikme jaoks on juhuslikult valitud positiivne koefitsient. Kui naasta algse näite juurde ja eeldada, et , siis saame funktsiooni .

Sellel etapil saame genereerida fragmente, ühendades ainulaadsed täisarvud , kus (sest see on meie saladus). Antud näites soovime jagada nelja fragmenti, mille lävi on kolm, seega genereerime juhuslikult punktid ja saadame ühe punkti igaühele neljast usaldusväärsest inimesest, kes on võtmehoidjad. Ütleme ka inimestele, et , kuna see loetakse avalikuks informatsiooniks ja on vajalik taastamiseks. .

Saladuse taastamine

Oleme juba arutanud polünoomilise interpolatsiooni mõistet ja seda, et see on Shamir'i läve skeemi alus. . Kui kolm neljast usaldusväärsest isikust soovivad taastada , peavad nad lihtsalt interpoleerima oma unikaalsete punktidega. Selleks saavad nad määrata oma punktid ja arvutada Lagrange'i interpoleerimispolünomi, kasutades järgmist valemit. Kui programmeerimine on teile arusaadavam kui matemaatika, siis pi — see on põhimõtteliselt operaator for, mis korrutab kõik tulemused, ja sigma — see on for, mis liidab kõik kokku.

Koormuse analüüsi korral Me saame seda järgmiselt lahendada ja tagastada meie algse polünomi:

Kuna me teame, et , taastamine toimub lihtsalt:

Kasutades ebaturvalist täisarvude aritmeetikat

Kuigi me rakendasime Shamir'i põhiideed edukalt , meil on probleem, millele oleme seni tähelepanu pööranud. Meie polünoomfunktsioon kasutab ebaturvalist täisarvude aritmeetikat. Pidage meeles, et iga täiendava punkti kohta, mille ründaja meie funktsiooni graafikul saab, jääb vähem võimalusi teiste punktide jaoks. Saate seda ise näha, kui ehitate graafiku polünoomfunktsiooni puhul, kasutades täisarvude aritmeetikat. See on meie väljendatud turvalisuse eesmärgi jaoks vastutustundetu, sest kurjategija ei tohiks mitte midagist teada saada, enne kui tal ei ole vähemalt fragmente.

Kuidas demonstreerida, kui nõrk on täisarvude aritmeetika skeem, kaalume stsenaariumi, kus kurjategija sai kaks punkti ja teab avalikku teavet, et . Sellest teabest saab ta tuletada , mille väärtus on kaks, ja sisestada tuntud väärtused valemisse ja .

Seejärel saab kurjategija leida , arvutades :

Kuna oleme määratlenud nagu juhuslikult valitud positiivsed täisarvud, on olemas piiratud hulk võimalikke Selle teabe abil võib kurjategija välja selgitada , kuna kõik, mis on üle 5, muudab negatiivseks. See osutub tõeks, kuna oleme kindlaks teinud

Seejärel võib kurjategija arvutada võimalikke väärtusi , asendades ühes :

Piiratud valikute hulgaga saab arusaadavaks, kui lihtne on väärtusi hankida ja kontrollida . Siin on vaid viis varianti.

Probleemi lahendamine ebaturvalise täisarvuaritmetiaga

Selle haavatavuse kõrvaldamiseks soovitab Shamir kasutada moodulaarset aritmeetikat, asendades järgnevaga , kus ja — kõigi prime arvude hulk.

Korraks meenutame, kuidas moodulaarne aritmeetika töötab. Kellade mõisted on juba tuttavad. Need kasutavad kellasid, mis on . Kui tunni käsi möödub kaheteistkümnest, naaseb see ühenumbrisse. Selle süsteemi huvitav omadus on see, et lihtsalt kelladele vaatamisega ei saa me selgeks, kui mitu ringi tund käsi on teinud. Kuid kui me teame, et tunni käsi on möödunud 12 neli korda, saab kergesti kindlaks määrata möödunud tundide arvu lihtsa valemi abil , kus  — see on meie jagaja (siin ),  — see on koefitsient (kui palju kordi jagaja tervikuna läheb algsesse numbrisse, siin ), and  — see on jääk, mille tavaliselt annab tagasi mooduli operaator (siin ). Nende väärtuste tundmine võimaldab meil lahendada võrrandi , kuid kui jätame koefitsiendi vahele, siis me kunagi ei suuda algset väärtust taastada.

Saame demonstreerida, kuidas see suurendab meie skeemi turvalisust, rakendades skeemi meie varasemale näitele ja kasutades . Meie uus polünoomi funktsioon , ning uued punktid . Nüüd saavad võtmehoidjad taas kasutada polünoom interpolatsiooni, et taastada meie funktsioon, kuid seekord peavad liitmise ja korrutamise toimingud olema koos mooduliga vähendatud (nt ).

Kasutades seda uut näidet, oletame, et ründaja teab kahte uut punkti, , ning avalik teave . Seekord järeleandja, tuginedes kogu teabele, mis tal on, järeldab järgmised funktsioonid, kus  — kõik positiivsed täisarvud, ja esindab mooduli koefitsiendi .

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

Siis ta üritab jälle järeldada , asendades ühes :

Seekord on tal tõsine probleem. Valemilt puuduvad väärtused , ja . Kuna nende muutuja kombinatsioone on lõputult, ei saa ta mingit täiendavat teavet.

Turvakaalutlused

Shamira sekreetide jagamise skeem pakub teabeooria perspektiivist turvalisust. See tähendab, et matemaatika on vastupidav isegi pahatahtlikule isikule, kellel on piiramatu arvutusressurss. Siiski sisaldab skeem endiselt mitmeid tuntud probleeme.

Näiteks ei loo Shamira skeem kontrollitavaid fragmente, ehkki inimesed võivad vabalt esituda vale fragmente ja häirida õige salajase taastamist. Vaenulik fragmentide hoidja, kellel on piisavalt teavet, võib isegi toota teise fragmendi, muutes oma äranägemise järgi. See probleem lahendatakse kontrollitavate sekreetide jagamise skeemide abil, nagu Feldmani skeem.

Teine probleem on see, et iga fragmendi pikkus on sama mis vastava salajase pikkus, nii et salajase pikkust on lihtne kindlaks teha. Seda probleemi lahendatakse triviaalsete täitmistega salajaste juhuslike numbrite fikseeritud pikkusega.

Lõpuks on oluline märkida, et meie mured seoses turvalisusega võivad ulatuda kaugemale skeemist endast. Reaalsetes krüptograafilistes rakendustes eksisteerib sageli oht kõrvalkanalite rünnakuteks, kus ründaja üritab välja tõmmata kasulikku teavet, põhinedes rakenduse täitmise ajale, vahemällu salvestamisele, tõrkeidele jne. Kui see tekitab muret, tuleks arenduse käigus hoolikalt kaaluda kaitsemeetmete, nagu funktsioonide ja pideva täitmisaja otsing, kasutamist, vältida mälu talletamist ketta ning planeerida mitmeid muid aspekte, mis ületavad selle artikli ulatust.

Demos

VDS-l on võimalik installida: sellel lehel on interaktiivne demo Shamir'i salajaste jagamise skeemist. Demonstreerimine on tehtud raamatukogu baasil ssss-js, mis on iseenesest populaarse programmi JavaScripti port ssss. Pange tähele, et suurte väärtuste arvutamine , ja võib võtta aega.

Allikas: habr.com