Harkitse tilannetta, jossa sinun on turvattava pankkiholvi. Sitä pidetään täysin valloittamattomana ilman avainta, joka annetaan heti ensimmäisenä työpäivänä. Tavoitteesi on säilyttää avain turvallisesti.

Oletetaan, että päätät pitää avaimen aina mukanasi, jolloin voit tarvittaessa käyttää tallennustilaa. Mutta huomaat nopeasti, että tällainen ratkaisu ei skaalaudu hyvin käytännössä, koska fyysistä läsnäoloasi vaaditaan aina kun avaat varaston. Entä sinulle luvattu loma? Lisäksi kysymys on vielä pelottavampi: entä jos hukkaat ainoan avaimesi?

Lomaasi ajatellen päätät tehdä kopion avaimesta ja uskoa sen toiselle työntekijälle. Ymmärrät kuitenkin, että tämäkään ei ole ihanteellinen. Kaksinkertaistamalla avainten määrän kaksinkertaistat myös avainvarkauden todennäköisyyden.

Epätoivoissasi tuhoat kaksoiskappaleen ja päätät jakaa alkuperäisen avaimen kahtia. Nyt luulisi, että kahden luotettavan henkilön, joilla on avaimenpalaset, pitäisi olla fyysisesti paikalla avaimen noutamiseksi ja holvin avaamiseksi. Tämä tarkoittaa, että varkaan on varastettava kaksi kappaletta, mikä on kaksi kertaa vaikeampaa kuin yhden avaimen varastaminen. Ymmärrät kuitenkin pian, että tämä järjestelmä ei ole paljon parempi kuin yksi avain, koska jos joku kadottaa puolet avaimesta, koko avainta ei voida palauttaa.

Ongelma voidaan ratkaista sarjalla lisäavaimia ja lukkoja, mutta tämä lähestymistapa vaatii nopeasti много avaimet ja lukot. Päätät, että ihanteellinen suunnittelu olisi jakaa avain, jotta turvallisuus ei ole täysin yhden henkilön varassa. Päätät myös, että fragmenttien lukumäärälle on oltava jokin kynnys, jotta jos yksi fragmentti katoaa (tai jos henkilö lähtee lomalle), koko avain pysyy toimivana.

Kuinka jakaa salaisuus

Adi Shamir ajatteli tämäntyyppistä avaintenhallintajärjestelmää vuonna 1979, kun hän julkaisi työnsä "Kuinka jakaa salaisuus". Artikkelissa selitetään lyhyesti ns kynnysmalli salaisen arvon (kuten salausavaimen) tehokkaaseen jakamiseen osat. Sitten, aina ja vain silloin ja osat on koottu, voit helposti palauttaa salaisuuden .

Turvallisuuden näkökulmasta tämän järjestelmän tärkeä ominaisuus on, että hyökkääjän ei pitäisi tietää yhtään mitään, ellei hänellä ole vähintään osat. Jopa läsnäolo osat eivät saa antaa mitään tietoa. Kutsumme tätä omaisuutta semanttinen turvallisuus.

Polynomiinterpolointi

Shamirin kynnysjärjestelmä rakennettu konseptin ympärille polynomin interpolaatio. Jos tämä käsite ei ole sinulle tuttu, se on itse asiassa melko yksinkertainen. Itse asiassa, jos olet joskus piirtänyt pisteitä kaavioon ja sitten yhdistänyt ne viivoilla tai käyrillä, olet jo käyttänyt sitä!

Kahden pisteen kautta voit piirtää rajattoman määrän 2-asteisia polynomeja. Valitaksesi niistä ainoan, tarvitset kolmannen pisteen. Kuva: Wikipedia

Tarkastellaan polynomia, jonka aste on yksi, . Jos haluat piirtää tämän funktion kaavioon, kuinka monta pistettä tarvitset? Tiedämme, että tämä on lineaarinen funktio, joka muodostaa suoran, joten se tarvitsee vähintään kaksi pistettä. Tarkastellaan seuraavaksi polynomifunktiota, jolla on aste kaksi, . Tämä on neliöfunktio, joten kaavion piirtämiseen tarvitaan vähintään kolme pistettä. Entä polynomi, jolla on aste kolme? Vähintään neljä pistettä. Ja niin edelleen.

Todella siistiä tässä ominaisuudessa on, että ottaen huomioon polynomifunktion aste ja ainakin pisteet, voimme johtaa lisäpisteitä tälle polynomifunktiolle. Kutsumme näiden lisäpisteiden ekstrapolointia polynomin interpolaatio.

Salaisuuden keksiminen

Olet ehkä jo tajunnut, että tässä Shamirin älykäs suunnitelma tulee peliin. Sanotaanpa salaisuutemme - Onko . Voimme kääntyä kaavion pisteeseen ja keksiä polynomifunktio asteella , joka täyttää tämän seikan. Muistutetaan tästä tulee olemaan vaadittujen fragmenttien kynnys, joten jos asetamme kynnysarvoksi kolme fragmenttia, meidän on valittava polynomifunktio, jolla on aste kaksi.

Polynomillamme on muoto Missä и — satunnaisesti valitut positiiviset kokonaisluvut. Rakennamme vain polynomin asteen kanssa , jossa vapaa kerroin  - Tämä on salaisuutemme , ja jokaiselle seuraavalle termeillä on satunnaisesti valittu positiivinen kerroin. Jos palataan alkuperäiseen esimerkkiin ja oletetaan, että , niin saamme funktion .

Tässä vaiheessa voimme luoda fragmentteja yhdistämällä ainutlaatuisia kokonaislukuja Missä (koska se on salaisuutemme). Tässä esimerkissä haluamme jakaa neljä fragmenttia, joiden kynnys on kolme, joten luomme satunnaisesti pisteitä ja lähetä yksi piste jokaiselle neljälle luotetulle henkilölle, avaimen säilyttäjälle. Kerromme siitä myös ihmisille , koska tämä katsotaan julkiseksi tiedoksi ja on välttämätöntä palauttamisen kannalta .

Salaisuuden palauttaminen

Olemme jo keskustelleet polynomin interpolaation käsitteestä ja siitä, kuinka se on Shamirin kynnysjärjestelmän perusta . Kun joku kolmesta neljästä luottamushenkilöstä haluaa palauttaa , niiden tarvitsee vain interpoloida omilla ainutlaatuisilla pisteillään. Tätä varten he voivat määrittää pisteensä ja laske Lagrangen interpolaatiopolynomi seuraavan kaavan avulla. Jos ohjelmointi on sinulle selkeämpää kuin matematiikka, niin pi on pohjimmiltaan operaattori for, joka kertoo kaikki tulokset, ja sigma on for, joka lisää kaiken.

At voimme ratkaista sen näin ja palauttaa alkuperäisen polynomifunktiomme:

Koska me tiedämme sen , elpyminen tehty yksinkertaisesti:

Käyttää vaarallista kokonaislukuaritmetiikkaa

Vaikka olemme onnistuneesti soveltaneet Shamirin perusideaa , meille jää ongelma, jonka olemme tähän asti jättäneet huomiotta. Polynomifunktiomme käyttää vaarallista kokonaislukuaritmetiikkaa. Huomaa, että jokaista lisäpistettä kohti, jonka hyökkääjä saa funktiomme kaaviosta, on vähemmän mahdollisuuksia muille pisteille. Voit nähdä tämän omin silmin, kun piirrät kasvavan määrän pisteitä polynomifunktiolle kokonaislukuaritmetiikkaa käyttäen. Tämä on haitallista ilmoittamamme turvallisuustavoitteen suhteen, koska hyökkääjän ei pitäisi tietää mitään, ennen kuin heillä on ainakin fragmentteja.

Osoittaaksesi kuinka heikko kokonaislukuaritmeettinen piiri on, harkitse skenaariota, jossa hyökkääjä sai kaksi pistettä ja tietää siitä julkista tietoa . Näistä tiedoista hän voi päätellä , yhtä suuri kuin kaksi, ja liitä tunnetut arvot kaavaan и .

Hyökkääjä voi sitten löytää , laskenta :

Koska olemme määritelleet satunnaisesti valittuina positiivisina kokonaislukuina mahdollisia on rajoitettu määrä . Näiden tietojen perusteella hyökkääjä voi päätellä , koska kaikki yli 5 riittää negatiivinen. Tämä osoittautuu todeksi, koska olemme päättäneet

Hyökkääjä voi sitten laskea mahdolliset arvot korvaamalla в :

Rajoitetut vaihtoehdot tulee selväksi, kuinka helppoa arvojen valitseminen ja tarkistaminen on . Tässä on vain viisi vaihtoehtoa.

Ongelman ratkaiseminen vaarallisella kokonaislukuaritmetiikalla

Tämän haavoittuvuuden poistamiseksi Shamir ehdottaa modulaarista aritmetiikkaa korvaamalla päälle Missä и — kaikkien alkulukujen joukko.

Muistetaan nopeasti kuinka modulaarinen aritmetiikka toimii. Kello osoittimilla on tuttu käsite. Hän käyttää kelloa . Heti kun tuntiosoitin ylittää kaksitoista, se palaa yhteen. Tämän järjestelmän mielenkiintoinen ominaisuus on se, että pelkällä kelloa katsomalla emme voi päätellä, kuinka monta kierrosta tuntiosoitin on tehnyt. Jos kuitenkin tiedämme, että tuntiosoitin on kulunut 12 neljä kertaa, voimme määrittää kuluneiden tuntien määrän täysin yksinkertaisella kaavalla Missä  on jakajamme (tässä ),  on kerroin (kuinka monta kertaa jakaja menee alkuperäiseen lukuun ilman jäännöstä, tässä ) ja  on loppuosa, joka yleensä palauttaa modulo-operaattorikutsun (tässä ). Kaikkien näiden arvojen tunteminen antaa meille mahdollisuuden ratkaista yhtälön , mutta jos kerroin puuttuu, emme koskaan voi palauttaa alkuperäistä arvoa.

Voimme osoittaa kuinka tämä parantaa järjestelmämme turvallisuutta soveltamalla mallia edelliseen esimerkkiimme ja käyttämällä . Uusi polynomifunktiomme ja uudet kohdat . Nyt avaintenpitäjät voivat jälleen käyttää polynomiinterpolaatiota funktiomme rekonstruoimiseen, vain tällä kertaa yhteen- ja kertolaskuoperaatioiden mukana tulee modulo-pelkistys (esim ).

Oletetaan tätä uutta esimerkkiä käyttäen, että hyökkääjä oppi kaksi näistä uusista kohdista, ja julkista tietoa . Tällä kertaa hyökkääjä, kaikkien hänellä olevien tietojen perusteella, tulostaa seuraavat toiminnot missä  on joukko positiivisia kokonaislukuja, ja edustaa moduulikerrointa .

Nyt hyökkääjämme löytää taas , lasketaan :

Sitten hän yrittää uudelleen korvaamalla в :

Tällä kertaa hänellä on vakava ongelma. Kaavasta puuttuu arvoja , и . Koska näiden muuttujien yhdistelmiä on ääretön määrä, hän ei voi saada lisätietoa.

Turvallisuusnäkökohdat

Shamirin salainen jakamisjärjestelmä ehdottaa turvallisuus tietoteorian näkökulmasta. Tämä tarkoittaa, että matematiikka kestää jopa hyökkääjää, jolla on rajoittamaton laskentateho. Piiri sisältää kuitenkin edelleen useita tunnettuja ongelmia.

Esimerkiksi Shamirin järjestelmä ei luo tarkistettavat palaset, eli ihmiset voivat vapaasti esittää väärennettyjä fragmentteja ja häiritä oikean salaisuuden palauttamista. Vihamielinen fragmentinpitäjä, jolla on riittävästi tietoa, voisi jopa tuottaa toisen fragmentin vaihtamalla oman harkintasi mukaan. Tämä ongelma ratkaistaan ​​käyttämällä todennettavissa olevat salaiset jakamisjärjestelmät, kuten Feldmanin järjestelmä.

Toinen ongelma on, että minkä tahansa fragmentin pituus on yhtä suuri kuin vastaavan salaisuuden pituus, joten salaisuuden pituus on helppo määrittää. Tämä ongelma voidaan ratkaista triviaalisesti pehmuste salaisuus mielivaltaisilla numeroilla kiinteään pituuteen saakka.

Lopuksi on tärkeää huomata, että turvallisuushuolemme voivat ulottua itse suunnittelua pidemmälle. Tosimaailman salaussovelluksissa on usein olemassa sivukanavahyökkäysten uhka, jolloin hyökkääjä yrittää poimia hyödyllistä tietoa sovelluksen suoritusajasta, välimuistista, kaatumisista jne. Jos tämä on huolenaihe, kehittämisen aikana tulee harkita huolellisesti suojatoimenpiteiden käyttöä, kuten funktioita ja vakioaikahakuja, muistin tallentamisen levylle estämistä ja monia muita seikkoja, jotka eivät kuulu tämän artikkelin soveltamisalaan.

esittely

Päälle tämä sivu Siellä on interaktiivinen esittely Shamirin salaisesta jakamisjärjestelmästä. Demonstraatio perustuu kirjastoon ssss-js, joka itsessään on suositun ohjelman JavaScript-portti ssss. Huomaa, että suurten arvojen laskeminen , и voi kestää jonkin aikaa.

Lähde: will.com