Vizsgáljunk meg egy olyan forgatókönyvet, ahol biztosítani kell egy banki tároló biztonságát. Teljes mértékben megközelíthetetlennek számít kulcs nélkül, amelyet az első munkanapon kap meg. Az Ön célja az, hogy biztonságosan megőrizze a kulcsot.

Tegyük fel, hogy úgy döntött, mindig maga mellett tartja a kulcsot, és szükség szerint biztosítja a hozzáférést a tárolóhoz. De gyorsan rájön, hogy ez a megoldás a gyakorlatban nem skálázható, mert minden alkalommal, amikor meg kell nyitnia a tárolót, a fizikai jelenléte szükséges. Mi a helyzet a szabadságokkal, amelyeket ígértek Önnek? Ráadásul még aggasztóbb a kérdés: mi van, ha elveszítette az egyetlen kulcsát?

A szabadság gondolatával úgy dönt, hogy készít egy másolatot a kulcsról, és megbízik egy másik munkatársat az őrzésével. Azonban tudja, hogy ez sem tökéletes. A kulcsok számának megduplázásával a kulcs ellopásának lehetőségeit is megduplázta.

Tehetetlenül megsemmisíti a másolatot, és úgy dönt, hogy az eredeti kulcsot félbe vágja. Most, azt gondolja, hogy két megbízható embernek ki kell fizikai jelen lennie ahhoz, hogy összeállítsa a kulcsot és kinyissa a tárolót. Ez azt jelenti, hogy a tolvajnak két darabot kell ellopnia, ami kétszer nehezebb, mint egy kulcsot ellopni. Azonban hamarosan rájön, hogy ez a séma nem sokkal jobb, mint egyetlen kulcs, mert ha valaki elveszíti a kulcs felét, a teljes kulcs nem állítható helyre.

A problémát egy sor további kulcs és zár segítségével lehetne megoldani, de ilyen megközelítéssel gyorsan szükség lesz sok kulcsra és zárra. Úgy dönt, hogy az ideális sémában a kulcsot fel kell osztani, hogy a biztonság ne legyen teljes mértékben egy emberre támaszkodva. Azt is megállapítja, hogy léteznie kell egy küszöbértéknek a darabok számában, hogy az egyik darab elvesztésekor (vagy ha az illető szabadságra ment) az egész kulcs funkcionális maradjon.

Hogyan oszthatjuk meg a titkot

Egy ilyen kulcskezelési sémán gondolkodott Adi Shamir 1979-ben, amikor közzétette munkáját „Hogyan oszthatjuk meg a titkot”. A cikkben röviden kifejtésre kerül a küszöbérték-séma a titkos érték (például kriptográfiai kulcs) hatékony felosztására darabra. Ezután, amikor és csak akkor, ha legalább a darabok összegyűltek, a titok könnyen helyreállítható. .

A biztonság szempontjából ennek a sémának fontos tulajdonsága, hogy a támadónak nem szabad semmit megtudnia, ha nincs legalább részből. Már az is, ha rendelkezik részecskékkel, nem adhat ki semmilyen információt. Ezt a tulajdonságot szemantikai biztonságnak.

polinomiális interpolációnak

a Shamir küszöbsémája köré épül a polinomiális interpoláció. Ha nem ismered ezt a fogalmat, valójában elég egyszerű. Ha valaha is rajzoltál pontokat egy grafikonon, majd összekötötted ezeket vonalakkal vagy görbékkel, már használtad!

Két ponton korlátlan számú 2. fokú polinom húzható. Ahhoz, hogy a közülük egyedet válasszunk, szükség van egy harmadik pontra. Illusztráció: Wikipedia

Nézzük meg az egy fokú polinomot, . Ha ezt a funkciót szeretnéd megrajzolni, hány pontra van szükséged? Nos, tudjuk, hogy ez egy lineáris funkció, amely vonalat képez, tehát legalább két pontra van szükség. Most nézzük meg a másodfokú polinomiális funkcionalitást, . Ez egy másodfokú funkció, így a grafikon megrajzolásához legalább három pontra van szükség. Mi a helyzet egy harmadfokú polinommal? Legalább négy pontra. És így tovább.

A dolog tényleg nagyszerű ebben a tulajdonságban, hogy tekintettel a polinomiális funkció fokára és legalább pontokra, újabb pontokat hozhatunk létre ehhez a polinomiális funkcióhoz. Ezt az extra pontok extrapolálását nevezik polinomiális interpolációnak.

Titkosítás

Valószínűleg már rájöttél, hogy itt belép a Shamir intelligens rendszere. Tegyük fel, hogy a titkunk — ez . Átalakíthatjuk egy pontra a grafikonon , és kitalálhatunk egy polinomiális funkciót, amelynek foka , amely megfelel ennek a pontnak. Emlékezzünk, hogy lesz a szükséges résszel lévő küszöbünk, tehát ha a küszöböt három részre állítjuk be, akkor egy másodfokú polinomiális funkciót kell választanunk.

A polinomunk formája , ahol és — véletlenszerűen kiválasztott pozitív egész számok. Csak egy polinomot építünk, amelynek foka , ahol a szabad együttható  — ez a mi titkunk , és mindegyik következő A tagolóknál véletlenszerűen kiválasztott pozitív együttható van. Ha visszatérünk az eredeti példához, és feltételezzük, hogy , akkor megkapjuk a funkciót .

Ezen a ponton generálhatunk fraktálokat, kapcsolódva egyedi egész számokhoz , ahol (mivel ez a mi titkunk). Ebben a példában négy fraktált akarunk kiosztani a három küszöbérték miatt, ezért véletlenszerűen generálunk pontokat és minden egyes pontot eljuttatunk a négy megbízott személy, a kulcstokokhoz. Azt is közöljük az emberekkel, hogy , mivel ez nyilvános információnak számít, és szükséges a helyreállításhoz .

A titok helyreállítása

Már beszéltünk a polinomiális interpoláció fogalmáról, amely a Shamir-küszöbös sémán alapul . Amikor bármelyik három a négy megbízott személy közül szeretné helyreállítani , csak interpolálniuk kell a saját egyedi pontjaikkal. Ehhez definiálhatják a pontjaikat és kiszámíthatják a Lagrange-interpoláló polinomot a következő képlettel. Ha a programozás értelmesebb számodra, mint a matematika, akkor a pi lényegében egy operátor for, amely minden eredményt megszoroz, a szigma pedig for, amely mindent összead.

Mikor ezt a következőképpen meg tudjuk oldani, és vissza tudjuk adni a kezdeti polinomiális funkciónkat:

Mivel tudjuk, hogy , a helyreállítás egyszerűen történik:

A biztonságtalan egész számú aritmetika használata

Bár sikeresen alkalmaztuk Shamir alapvető ötletét, van egy probléma, amit eddig figyelmen kívül hagytunk. A mi polinomiális funkciónk biztonságtalan egész számú aritmetikát használ. Ne feledd, hogy minden egyes további ponttal, amelyet a támadó megkap a funkciónk grafikonján, egyre kevesebb lehetőség marad a többi pontra. Ezt saját szemeddel láthatod, amikor grafikonokat építesz a polinomiális funkciókhoz, használva az egész számú aritmetikát. Ez ellentétes a biztonsági célunkkal, mivel a támadónak semmit sem szabad tudnia, amíg legalább darabot nem kap. Annál is inkább, hogy megmutassuk, mennyire gyenge a biztonság az egész számú aritmetikát használó sémával, nézzünk egy olyan forgatókönyvet, amelyben a támadó két pontot kapott.

Hogy bemutassuk, mennyire gyenge a megfelelő egész számok aritmetikájának rendszere, nézzünk meg egy olyan forgatókönyvet, ahol egy támadó megszerzett két pontot. tudja, hogy nyilvános információval rendelkezik, ami Ebből az információból ki tudja következtetni , ami egyenlő kettővel, és be tudja helyettesíteni a képletbe a jól ismert értékeket és .

Ezután a támadó megtalálhatja , miután kiszámította :

Mivel meghatároztuk mint véletlenszerűen választott pozitív egész számokat, korlátozott számú lehetséges . Ezzel az információval a támadó ki tudja következtetni , mivel minden, ami nagyobb mint 5, negatívvá válik. Ez igaznak bizonyul, mivel meghatároztuk Ezután a támadó kiszámíthatja a lehetséges értékeket

, helyettesítve egy korlátozott számú lehetőséggel be. :

. Itt mindössze öt lehetőség van. A biztonságos egész számú aritmetika problémájának megoldása A sebezhetőség megszüntetése érdekében Shamir javasolja a moduláris aritmetika használatát, helyettesítve

az

— az összes prím szám halmaza. Gyorsan emlékezzünk vissza, hogyan működik a moduláris aritmetika. Az óra már egy ismert koncepció. Az órák használata , ahol és . Amint az óra mutatója elhalad tizenkettő mellett, visszatér egyhez. Ennek a rendszernek az érdekes tulajdonsága, hogy egyszerűen ránézve az órára, nem tudjuk megmondani, hány fordulatot tett a mutató. Azonban ha tudjuk, hogy a mutató négyszer haladta meg a 12-t, a mögöttes órák számát egy egyszerű képlettel teljesen meg lehet határozni

— ez a mi osztónk (itt — a szorzó (hányszor osztható maradék nélkül az osztó az alap számba, itt , ahol  ), és ),  — a maradék, amit a modul operátor hívása általában visszaad (itt ). Ezeknek az értékeknek a tudása lehetővé teszi számunkra, hogy megoldjuk az egyenletet  , de ha kihagyjuk a szorzót, soha nem tudjuk visszaállítani az eredeti értéket. Meg lehet mutatni, hogy ez hogyan javítja a védelmünket, ha a sémát a korábbi példánkra alkalmazzuk és használjuk . Az új polinomiális funkciónk

, és az új pontok . Most a kulcsőrök újra felhasználhatják a polinomiális interpolációt a funkciónk helyreállítására, de ezúttal az összeadási és szorzási műveleteket modulárisan kell végrehajtani (pl. Használva ezt az új példát, tegyük fel, hogy a támadó kettő ezek közül az új pontok közül tudott meg, (pl. ).

Ez az új példa alapján tegyük fel, hogy a támadó tudott két új pontról, , és a nyilvános információ . Ezúttal a támadó az összes rendelkezésére álló információ alapján a következő funkciókat vonja le, ahol  — a pozitív egész számok halmaza, és a modulus koefficiens .

Most a támadónk újra megtalálja , kiszámítva :

Ezután újra megpróbálja leszűrni egy korlátozott számú lehetőséggel be. :

Ezúttal súlyos problémával áll szemben. A képletből hiányoznak az értékek , és . Mivel végtelen számú kombináció létezik ezen változók között, nem tud további információt kapni.

Biztonsági megfontolások

Shamir titkosítási sémája ajánl biztonságot információelméleti szempontból. Ez azt jelenti, hogy a matematika ellenálló még a korlátlan számítási kapacitással rendelkező támadóval szemben is. Azonban a séma még mindig tartalmaz néhány ismert problémát.

Például a Shamir séma nem hoz létre ellenőrizhető darabokat, ami azt jelenti, hogy az emberek szabadon bemutathatnak hamis darabokat, megakadályozva a helyes titok helyreállítását. Egy ellenséges darabtároló elegendő információval akár másik darabot is előállíthat, megváltoztatva a saját belátása szerint. Ezt a problémát ellenőrizhető titkosítási sémák megoldják, például Feldman séma.Egy másik probléma az, hogy bármely darab hossza megegyezik a megfelelő titok hosszával, tehát a titok hossza könnyen meghatározható. Ezt a problémát triviális

kitöltéssel oldják meg, amely a titkot véletlen számokkal tölti ki, hogy fix hosszúságú legyen. Végül fontos megjegyezni, hogy a biztonsággal kapcsolatos aggodalmaink túlmutathatnak magán a sémán. Valós kriptográfiai alkalmazások esetén gyakran fenyegetést jelent a mellékcsatornás támadások veszélye, amikor a támadó megpróbál hasznos információt kiszivárogtatni az alkalmazás futásidejéből, gyorsítótárból, hibákból stb. Ha ez aggodalomra ad okot, a fejlesztési folyamat során gondosan mérlegelni kell védelmi intézkedések alkalmazását, például állandó futási időt igénylő funkciók használatát, megakadályozva a memória lemezre írását, és más tényezők alapos áttekintését, amelyek túlmutatnak ezen a cikken.

Demó

Demos

Ezen az oldalon interaktív bemutató található Shamir titkosítási sémájáról. A bemutató a ssss-js, amely önállóan a népszerű program JavaScript-portja. ssss. Kérjük, vegye figyelembe, hogy a nagy értékek számítása , és időbe telhet.

Forrás: habr.com