Apsvarstykite scenarijų, kai jums reikia apsaugoti banko saugyklą. Jis laikomas visiškai neįveikiamu be rakto, kuris jums įteikiamas pirmąją darbo dieną. Jūsų tikslas yra saugiai laikyti raktą.

Tarkime, kad nusprendėte visada laikyti raktą su savimi ir prireikus suteikti prieigą prie saugyklos. Tačiau greitai suprasite, kad toks sprendimas praktiškai nepasiteisina, nes kiekvieną kartą atidarius saugyklą reikalingas jūsų fizinis buvimas. O atostogos, kurios jums buvo pažadėtos? Be to, dar labiau baugina klausimas: o jei pametėte vienintelį raktą?

Turėdami omenyje savo atostogas, nusprendžiate pasidaryti rakto kopiją ir patikėti kitam darbuotojui. Tačiau jūs suprantate, kad tai taip pat nėra idealu. Padvigubinę raktų skaičių, taip pat padvigubinate rakto vagystės tikimybę.

Iš nevilties sunaikinate dublikatą ir nusprendžiate padalyti pradinį raktą per pusę. Dabar manote, kad du patikimi žmonės, turintys rakto fragmentus, turėtų būti fiziškai, kad paimtų raktą ir atidarytų saugyklą. Tai reiškia, kad vagis turi pavogti du gabalus, o tai yra dvigubai sunkiau nei pavogti vieną raktą. Tačiau greitai supranti, kad ši schema nėra daug geresnė už vieną raktą, nes jei kas nors pameta pusę rakto, viso rakto atkurti nepavyks.

Problema gali būti išspręsta naudojant daugybę papildomų raktų ir spynų, tačiau šis metodas greitai pareikalaus много raktai ir spynos. Jūs nusprendžiate, kad idealus dizainas būtų dalintis raktu, kad saugumas nepasikliautų tik vienu asmeniu. Taip pat darote išvadą, kad turi būti tam tikras fragmentų skaičiaus slenkstis, kad pametus vieną fragmentą (ar žmogui išvykus atostogų), visas raktas išliktų funkcionalus.

Kaip pasidalinti paslaptimi

Apie tokio tipo raktų valdymo schemą galvojo Adi Shamiras 1979 m., kai paskelbė savo darbą „Kaip pasidalinti paslaptimi“. Straipsnyje trumpai paaiškinama vadinamoji slenksčio schema, leidžianti efektyviai padalinti slaptą reikšmę (pvz., kriptografinį raktą) į dalys. Tada, kada ir tik tada, bent jau iš dalys yra surinktos, nesunkiai atkursite paslaptį .

Saugumo požiūriu svarbi šios schemos savybė yra ta, kad užpuolikas neturėtų žinoti absoliučiai nieko, nebent turi bent dalys. Netgi buvimas dalys neturi pateikti jokios informacijos. Mes tai vadiname nuosavybe semantinis saugumas.

Polinominė interpoliacija

Šamiro slenksčio schema sukurta remiantis koncepcija daugianario interpoliacija. Jei nesate susipažinę su šia sąvoka, tai iš tikrųjų gana paprasta. Tiesą sakant, jei kada nors nubraižėte taškus grafike ir sujungėte juos linijomis ar kreivėmis, tai jau naudojote!

Per du taškus galima nubrėžti neribotą skaičių 2 laipsnio daugianario. Norint pasirinkti vienintelį iš jų, reikia trečiojo taško. Iliustracija: Vikipedija

Apsvarstykite daugianarį su vienu laipsniu, . Jei norite pavaizduoti šią funkciją grafike, kiek taškų jums reikia? Na, mes žinome, kad tai yra tiesinė funkcija, kuri sudaro liniją, todėl jai reikia bent dviejų taškų. Tada apsvarstykite daugianario funkciją su antrojo laipsnio, . Tai kvadratinė funkcija, todėl norint nubraižyti grafiką reikia bent trijų taškų. Kaip apie daugianarį su trečiuoju laipsniu? Bent keturi taškai. Ir taip toliau.

Tikrai šaunus šios savybės dalykas yra tas, kad atsižvelgiant į daugianario funkcijos laipsnį ir bent jau taškų, šiai daugianario funkcijai galime gauti papildomų taškų. Šių papildomų taškų ekstrapoliacija vadiname daugianario interpoliacija.

Paslapties kūrimas

Galbūt jau supratote, kad čia pasirodo protinga Šamiro schema. Tarkime, mūsų paslaptis - yra . Galime pasukti iki taško grafike ir sugalvoti daugianario funkciją su laipsniu , kuris atitinka šį punktą. Prisiminkime tai bus mūsų reikalingų fragmentų slenkstis, taigi, jei nustatysime slenkstį į tris fragmentus, turime pasirinkti daugianario funkciją, kurios laipsnis yra antras.

Mūsų daugianario forma bus tokia Kur и — atsitiktinai atrinkti sveikieji skaičiai. Mes tik sudarome daugianarį su laipsniu , kur laisvasis koeficientas  – Tai mūsų paslaptis , ir kiekvienam paskesniam yra atsitiktinai parinktas teigiamas koeficientas. Jei grįšime prie pradinio pavyzdžio ir manysime, kad , tada gauname funkciją .

Šiuo metu sujungdami galime generuoti fragmentus unikalūs sveikieji skaičiai Kur (nes tai mūsų paslaptis). Šiame pavyzdyje norime paskirstyti keturis fragmentus, kurių slenkstis yra trys, todėl atsitiktinai generuojame taškus ir nusiųskite po vieną tašką kiekvienam iš keturių patikimų žmonių – rakto saugotojų. Taip pat pranešame žmonėms apie tai , nes tai laikoma vieša informacija ir būtina norint susigrąžinti .

Paslapties atgavimas

Mes jau aptarėme daugianario interpoliacijos koncepciją ir kaip ji yra Shamiro slenksčio schemos pagrindas. . Kai kurie trys iš keturių patikėtinių nori atkurti , jiems tereikia interpoliuoti su savo unikaliais taškais. Norėdami tai padaryti, jie gali nustatyti savo taškus ir apskaičiuokite Lagranžo interpoliacijos polinomą naudodami šią formulę. Jei programavimas jums aiškesnis nei matematika, tada pi iš esmės yra operatorius for, kuris padaugina visus rezultatus, o sigma yra for, kuris viską papildo.

prie galime tai išspręsti taip ir grąžinti pradinę daugianario funkciją:

Kadangi mes tai žinome , atsigavimas padaryta paprastai:

Naudojama nesaugi sveikųjų skaičių aritmetika

Nors mes sėkmingai pritaikėme pagrindinę Šamiro idėją , likome su problema, į kurią iki šiol nepaisėme. Mūsų daugianario funkcija naudoja nesaugią sveikųjų skaičių aritmetiką. Atminkite, kad už kiekvieną papildomą tašką, kurį užpuolikas gauna mūsų funkcijos grafike, yra mažiau galimybių kitiems taškams. Tai galite pamatyti savo akimis, kai brėžiate vis didesnį daugianario funkcijos taškų skaičių naudodami sveikųjų skaičių aritmetiką. Tai prieštarauja mūsų nurodytam saugumo tikslui, nes užpuolikas neturėtų žinoti visiškai nieko, kol neturi fragmentai.

Norėdami parodyti, kokia silpna yra sveikųjų skaičių aritmetinė grandinė, apsvarstykite scenarijų, kai užpuolikas gavo du taškus ir žino viešą informaciją, kad . Iš šios informacijos jis gali nuspręsti , lygus dviem, ir įkiškite žinomas reikšmes į formulę и .

Tada užpuolikas gali rasti , skaičiuojant :

Kadangi mes apibrėžėme kaip atsitiktinai atrinkti teigiami sveikieji skaičiai, galimų yra ribotas skaičius . Naudodamasis šia informacija, užpuolikas gali padaryti išvadą , nes tiks bet kas didesnis nei 5 neigiamas. Pasirodo, kad tai tiesa, nes mes nusprendėme

Tada užpuolikas gali apskaičiuoti galimas reikšmes , pakeičiant в :

Su ribotomis galimybėmis tampa aišku, kaip lengva pasirinkti ir patikrinti reikšmes . Čia yra tik penki variantai.

Problemos sprendimas naudojant nesaugią sveikųjų skaičių aritmetiką

Norėdami pašalinti šį pažeidžiamumą, Shamiras siūlo naudoti modulinę aritmetiką, pakeisti apie Kur и — visų pirminių skaičių aibė.

Greitai prisiminkime, kaip veikia modulinė aritmetika. Laikrodis su rodyklėmis yra pažįstama sąvoka. Ji naudoja laikrodį, kuris yra . Kai tik valandos rodyklė pasiekia dvylika, ji grįžta į vieną. Įdomi šios sistemos savybė yra ta, kad vien pažvelgę ​​į laikrodį negalime nustatyti, kiek apsisukimų padarė valandos rodyklė. Tačiau jei žinome, kad valandų rodyklė praėjo 12 keturis kartus, galime visiškai nustatyti prabėgusių valandų skaičių naudodami paprastą formulę Kur  yra mūsų daliklis (čia ),  yra koeficientas (kiek kartų daliklis patenka į pradinį skaičių be liekanos, čia ), ir  yra likusioji dalis, kuri paprastai grąžina modulo operatoriaus skambutį (čia ). Žinodami visas šias vertes, galime išspręsti lygtį , bet jei praleisime koeficientą, niekada negalėsime atkurti pradinės vertės.

Galime parodyti, kaip tai pagerina mūsų schemos saugumą, pritaikydami schemą ankstesniame pavyzdyje ir naudodami . Mūsų nauja daugianario funkcija , ir nauji taškai . Dabar raktų turėtojai vėl gali naudoti daugianario interpoliaciją, kad atkurtų mūsų funkciją, tik šį kartą sudėjimo ir daugybos operacijas turi lydėti modulio redukcija (pvz ).

Naudodami šį naują pavyzdį, tarkime, kad užpuolikas sužinojo du iš šių naujų taškų, , ir vieša informacija . Šį kartą užpuolikas, remdamasis visa turima informacija, išveda šias funkcijas, kur  yra visų teigiamų sveikųjų skaičių aibė ir reiškia modulio koeficientą .

Dabar mūsų užpuolikas vėl randa , skaičiuojant :

Tada jis bando dar kartą , pakeičiant в :

Šį kartą jis turi rimtą problemą. Formulės trūksta verčių , и . Kadangi yra begalinis šių kintamųjų derinių skaičius, jis negali gauti jokios papildomos informacijos.

Saugumo svarstymai

Šamiro slapto dalijimosi schema rodo saugumas informacijos teorijos požiūriu. Tai reiškia, kad matematika yra atspari net užpuolikui, turinčiam neribotą skaičiavimo galią. Tačiau grandinėje vis dar yra keletas žinomų problemų.

Pavyzdžiui, Šamiro schema nesukuria fragmentai, kuriuos reikia patikrintity žmonės gali laisvai pateikti netikrus fragmentus ir trukdyti atkurti teisingą paslaptį. Priešiškas fragmentų saugotojas, turintis pakankamai informacijos, pakeisdamas netgi galėtų sukurti kitą fragmentą savo nuožiūra. Ši problema išspręsta naudojant patikrinamos paslapties dalijimosi schemos, pavyzdžiui, Feldmano schema.

Kita problema yra ta, kad bet kurio fragmento ilgis yra lygus atitinkamos paslapties ilgiui, todėl paslapties ilgį nesunku nustatyti. Šią problemą galima išspręsti trivialiu būdu kamšalas slaptas su savavališkais skaičiais iki fiksuoto ilgio.

Galiausiai svarbu pažymėti, kad mūsų saugumo problemos gali apimti ne tik patį dizainą. Realioms kriptografinėms programoms dažnai kyla šoninių kanalų atakų grėsmė, kai užpuolikas bando išgauti naudingą informaciją iš programos vykdymo laiko, talpyklos, gedimų ir kt. Jei tai kelia susirūpinimą, kuriant reikia atidžiai apsvarstyti, ar naudoti apsaugos priemones, pvz., funkcijas ir nuolatinio laiko paieškas, neleisti atminties įrašyti į diską ir daugybę kitų svarstymų, kurie nepatenka į šio straipsnio taikymo sritį.

Demo

Apie šiuo puslapiu Yra interaktyvus Shamiro slapto dalijimosi schemos demonstravimas. Demonstracija pagal biblioteką ssss-js, kuris pats yra populiarios programos „JavaScript“ prievadas ssss. Atkreipkite dėmesį, kad skaičiuojant dideles reikšmes , и gali užtrukti šiek tiek laiko.

Šaltinis: www.habr.com