Fontolja meg azt a forgatókönyvet, amelyben banki trezort kell biztosítania. Teljesen bevehetetlennek tekinthető kulcs nélkül, amelyet az első munkanapon kapsz. A cél a kulcs biztonságos tárolása.
Tegyük fel, hogy úgy dönt, hogy a kulcsot mindig magánál tartja, és szükség szerint hozzáférést biztosít a trezorhoz. De hamar rájön, hogy egy ilyen megoldás nem skálázható jól a gyakorlatban, mert minden alkalommal, amikor fizikailag jelen kell lenni a páncélszekrény kinyitásához. Mi lesz a nyaralással, amit ígértek? Ráadásul még ijesztőbb a kérdés: mi van, ha elveszíti az egyetlen kulcsot?
A nyaralás ötletével úgy dönt, hogy másolatot készít a kulcsról, és egy másik alkalmazottra bízza. Azonban megérti, hogy ez sem ideális. A kulcsok számának megduplázásával a kulcslopás esélyét is megduplázta.
Kétségbeesetten megsemmisíti a másolatot, és úgy dönt, hogy az eredeti kulcsot kettéosztja. Most úgy gondolja, hogy két megbízható embernek kell fizikailag jelen lennie a kulcstöredékekkel a kulcs átvételéhez és a páncélszekrény kinyitásához. Ez azt jelenti, hogy a tolvajnak két töredéket kell ellopnia, ami kétszer olyan nehéz, mint egy kulcsot. Azonban hamar rájössz, hogy ez a séma nem sokkal jobb, mint egy kulcs, mert ha valaki elveszíti a kulcs felét, a teljes kulcsot nem lehet visszaszerezni.
A probléma számos további kulccsal és zárral megoldható, de ez a megközelítés gyorsan megköveteli много kulcsok és zárak. Ön úgy dönt, hogy az ideális megoldás az, ha megosztjuk a kulcsot, hogy a biztonság ne egy személyen múljon. Arra is következtet, hogy a töredékek számának meg kell határoznia bizonyos küszöböt, hogy ha egy töredék elveszett (vagy ha a személy nyaralni megy), az egész kulcs működőképes maradjon.
Hogyan osszunk meg egy titkot
Az ilyen típusú kulcskezelési sémákra gondolt Adi Shamir 1979-ben, amikor publikálta munkáját . A cikk röviden ismerteti az ún 
küszöbérték séma egy titkos érték (például kriptográfiai kulcs) hatékony felosztására alkatrészek. Akkor, amikor és legalábbis csak akkor A alkatrészek össze vannak szerelve, könnyedén visszaállíthatja a titkot .
Biztonsági szempontból ennek a sémának az egyik fontos tulajdonsága, hogy a támadó semmit sem tanulhat, ha nem rendelkezik legalább alkatrészek. Még a jelenlét is részei nem adhatnak információt. Ezt az ingatlant hívjuk szemantikai biztonság.
Polinom interpoláció
Threshol Shamir séma koncepció köré épült polinom interpoláció. Ha nem ismeri ezt a koncepciót, akkor valójában nagyon egyszerű. Általánosságban elmondható, hogy ha valaha pontokat rajzolt egy diagramra, majd összekapcsolta őket vonalakkal vagy görbékkel, akkor már használta!
Két ponton keresztül korlátlan számú 2. fokú polinom rajzolható. Ahhoz, hogy közülük az egyetlent válasszuk, egy harmadik pontra van szükség. Ábra:
Tekintsünk egy fokú polinomot, . Ha ezt a függvényt grafikonon szeretné ábrázolni, hány pontra van szüksége? Nos, tudjuk, hogy ez egy lineáris függvény, amely egy egyenest alkot, és ezért legalább két pontra van szükségünk. Ezután tekintsünk egy polinomiális függvényt második fokozattal, . Ez egy másodfokú függvény, tehát legalább három pont szükséges a grafikon ábrázolásához. Mit szólnál egy háromfokú polinomhoz? Legalább négy pont. És így tovább, és így tovább.
Az igazán klassz ebben a tulajdonságban az, hogy a polinomiális függvény mértékét figyelembe véve és legalább pontokat, további pontokat származtathatunk ehhez a polinomfüggvényhez. E további pontok extrapolációjának nevezzük polinom interpoláció.
Titkot csinálni
Lehet, hogy már kitaláltad, hogy itt jön képbe Shamir okos terve. Tegyük fel a titkunkat - Van . Megfordulhatunk a grafikon pontjáig és kitalálunk egy polinom függvényt fokával , ami megfelel ennek a pontnak. Emlékezzen arra lesz a szükséges töredékek küszöbértéke, tehát ha három töredékre állítjuk a küszöböt, akkor kettős fokszámú polinomfüggvényt kell választanunk.
A polinomunk alakja lesz Ahol и véletlenszerűen kiválasztott pozitív egész számok. Csak egy polinomot építünk fokszámmal , ahol a szabad együttható - Ez a mi titkunk , és minden további termek egy véletlenszerűen választott pozitív együttható. Visszatérve az eredeti példához, és azt feltételezve , akkor megkapjuk a függvényt .
Ezen a ponton összekapcsolással fragmentumokat generálhatunk egyedi egész számok Ahol (mert ez a mi titkunk). Ebben a példában négy töredéket szeretnénk elosztani három küszöbértékkel, így véletlenszerűen generálunk pontokat és küldjön egy pontot mind a négy megbízható embernek, a kulcs őrzőjének. Ezt is elmondjuk az embereknek , mivel nyilvános információnak minősül, és a helyreállításhoz szükséges .
Titkos helyreállítás
Korábban már tárgyaltuk a polinomiális interpoláció fogalmát, és azt, hogy miként alapozza meg Shamir küszöbértékét. . Amikor négyből három megbízott vissza akarja állítani , csak interpolálniuk kell egyedi pontjaikkal. Ehhez meg tudják határozni a pontjaikat és számítsuk ki a Lagrange-interpolációs polinomot a következő képlet segítségével. Ha a programozás világosabb számodra, mint a matematika, akkor a pi lényegében egy operátor for, amely minden eredményt megszoroz, a szigma pedig az forez mindent összead.
-On megoldhatjuk így, és visszaadjuk az eredeti polinomfüggvényünket:
Mióta ezt tudjuk , felépülés egyszerűen megtörténik:
Nem biztonságos egész számok használata
Bár sikeresen alkalmaztuk a Shamir alapötletét , egy olyan problémánk maradt, amelyet eddig figyelmen kívül hagytunk. Polinom függvényünk nem biztonságos egész számot használ. Ne feledje, hogy minden további pont után, amelyet a támadó kap a függvénygrafikonon, kevesebb lehetőség van más pontokra. Ezt a saját szemével láthatja, ha egy polinomiális függvény növekvő számú pontját egész számot használva ábrázolja. Ez ellentétes a kinyilvánított biztonsági célunkkal, mert a támadónak semmiről sem szabad tudnia, amíg legalább nem töredékek.
Annak szemléltetésére, hogy mennyire gyenge az egész számtani séma, vegyünk egy forgatókönyvet, amelyben a támadó két pontot kapott és ismeri azokat a nyilvános információkat . Ebből az információból arra következtethet , egyenlő kettővel, és csatlakoztassa az ismert értékeket a képlethez и .
A támadó ezután megtalálhatja , számolva :
Mióta meghatároztuk véletlenszerűen kiválasztott pozitív egész számokként korlátozott számú lehetséges . Ezen információk alapján a támadó következtethet , mert minden 5-nél nagyobb lesz negatív. Ez igaznak bizonyul, hiszen elhatároztuk
A támadó ezután kiszámíthatja a lehetséges értékeket cseréje в :
Korlátozott lehetőségekkel világossá válik, milyen egyszerű az értékek felvétele és ellenőrzése . Itt csak öt lehetőség van.
A feladat megoldása nem biztonságos egész számokkal
A biztonsági rés kijavításához Shamir moduláris aritmetika használatát javasolja cserével on Ahol и az összes prímszám halmaza.
Gyorsan idézzük fel a moduláris aritmetika működését. A kézi óra ismerős fogalom. Olyan órát használ . Amint az óramutató eltelik a tizenkettőt, visszaáll egyre. Érdekes tulajdonsága ennek a rendszernek, hogy pusztán az órára nézve nem tudjuk megállapítani, hány fordulatot tett meg az óramutató. Ha azonban tudjuk, hogy az óramutató négyszer telt el 12-nél, akkor egy egyszerű képlettel teljesen meg tudjuk határozni az eltelt órák számát Ahol az osztónk (itt ), - ez az együttható (itt hányszor megy be a maradék nélküli osztó az eredeti számba ), és a maradék, ami általában egy hívást ad vissza a modulo operátornak (itt ). Mindezen értékek ismerete lehetővé teszi számunkra, hogy megoldjuk az egyenletet , de ha kihagyjuk az együtthatót, soha nem tudjuk visszaállítani az eredeti értéket.
Bemutathatjuk, hogy ez hogyan javítja áramkörünk biztonságát, ha az áramkört alkalmazzuk az előző példánkra és használjuk . Új polinomiális függvényünk , és az új pontok . A kulcstartók most ismét polinomiális interpolációval rekonstruálhatják függvényünket, csak ezúttal az összeadási és szorzási műveleteket modulo redukciónak kell követnie. (például ).
Ezzel az új példával tegyük fel, hogy a támadó megtanult két új pontot, és nyilvános információk . Ezúttal a támadó a rendelkezésére álló összes információ alapján a következő funkciókat jeleníti meg, ahol az összes pozitív egész halmaza, és a modulus együtthatót jelenti .
Most a betolakodónk újra megtalálja , számítva :
Aztán ismét megpróbálja visszavonulni cseréje в :
Ezúttal komoly problémája van. A képlet értékei hiányoznak , и . Mivel ezeknek a változóknak végtelen számú kombinációja létezik, nem tud további információt szerezni.
Biztonsági szempontok
Shamir titkos megosztási rendszere azt sugallja információ biztonság. Ez azt jelenti, hogy a matematika még a korlátlan számítási teljesítményű támadóval szemben is erős. A séma azonban továbbra is számos ismert problémát tartalmaz.
Például a Shamir-séma nem hoz létre ellenőrizendő töredékek, vagyis az emberek szabadon bemutathatnak hamis töredékeket és beleavatkozhatnak a helyes titok visszaszerzésébe. Egy ellenséges töredékmegőrző elegendő információval akár egy másik töredéket is előállíthat a változtatással saját belátása szerint. Ez a probléma megoldva a ellenőrizhető titkos megosztási sémák, mint például a Feldman-séma.
További probléma, hogy bármely töredék hossza megegyezik a megfelelő titok hosszával, így a titok hossza könnyen meghatározható. Ezt a problémát a triviális oldja meg párnázás titkos tetszőleges számok által meghatározott hosszúságig.
Végül fontos megjegyezni, hogy biztonsági aggályaink túlmutathatnak magán a rendszeren. Valódi kriptográfiai alkalmazások esetén gyakran fennáll az oldalcsatornás támadások veszélye, amikor a támadó megpróbál hasznos információkat kinyerni az alkalmazás végrehajtási idejéből, gyorsítótárazásából, összeomlásából stb. Ha ez aggodalomra ad okot, gondosan fontolja meg a védintézkedések használatát a fejlesztés során, például a funkciókat és az állandó idejű kereséseket, megakadályozza a memória lemezre mentését, és vegye figyelembe számos egyéb olyan dolgot, amelyek kívül esnek e cikk hatókörén.
Demó
tovább van egy interaktív bemutató Shamir titkos megosztási rendszeréről. A bemutató a könyvtár alapján készült , amely maga egy népszerű program JavaScript portja . Vegye figyelembe, hogy nagy értékek kiszámítása , и eltarthat egy ideig.
Forrás: will.com