Apsveriet situÄciju, kad jums ir nepiecieÅ”ams nodroÅ”inÄt bankas glabÄtuvi. Tas tiek uzskatÄ«ts par absolÅ«ti neieÅemamu bez atslÄgas, kas jums tiek izsniegta jau pirmajÄ darba dienÄ. JÅ«su mÄrÄ·is ir droÅ”i uzglabÄt atslÄgu.
PieÅemsim, ka nolemjat vienmÄr paturÄt atslÄgu sev lÄ«dzi, nodroÅ”inot piekļuvi krÄtuvei pÄc vajadzÄ«bas. TaÄu jÅ«s Ätri sapratÄ«sit, ka Å”Äds risinÄjums praksÄ neder, jo jÅ«su fiziskÄ klÄtbÅ«tne ir nepiecieÅ”ama ikreiz, kad atverat krÄtuvi. KÄ ar jums apsolÄ«tajÄm brÄ«vdienÄm? TurklÄt jautÄjums ir vÄl biedÄjoÅ”Äks: kÄ bÅ«tu, ja pazaudÄtu savu vienÄ«go atslÄgu?
DomÄjot par atvaļinÄjumu, jÅ«s nolemjat izgatavot atslÄgas kopiju un uzticÄt to citam darbiniekam. TomÄr jÅ«s saprotat, ka arÄ« tas nav ideÄli. DivkÄrÅ”ojot atslÄgu skaitu, jÅ«s arÄ« dubultojat atslÄgu zÄdzÄ«bas iespÄjas.
IzmisumÄ jÅ«s iznÄ«cinÄt dublikÄtu un nolemjat sadalÄ«t sÄkotnÄjo atslÄgu uz pusÄm. Tagad jÅ«s domÄjat, ka diviem uzticamiem cilvÄkiem ar atslÄgu fragmentiem ir jÄbÅ«t fiziski klÄt, lai savÄktu atslÄgu un atvÄrtu glabÄtuvi. Tas nozÄ«mÄ, ka zaglim ir jÄnozag divi gabali, kas ir divreiz grÅ«tÄk nekÄ vienas atslÄgas nozagÅ”ana. TaÄu drÄ«z vien saproti, ka Ŕī shÄma nav daudz labÄka par vienu atslÄgu, jo, ja kÄds pazaudÄ pusi atslÄgas, pilnu atslÄgu nevar atgÅ«t.
ProblÄmu var atrisinÄt ar papildu atslÄgu un slÄdzeÅu sÄriju, taÄu Ŕī pieeja Ätri prasÄ«s Š¼Š½Š¾Š³Š¾ atslÄgas un slÄdzenes. JÅ«s nolemjat, ka ideÄls dizains bÅ«tu koplietot atslÄgu, lai droŔība nebÅ«tu pilnÄ«bÄ atkarÄ«ga tikai no vienas personas. JÅ«s arÄ« secinÄt, ka ir jÄbÅ«t kÄdam fragmentu skaita slieksnim, lai, ja kÄds fragments tiek pazaudÄts (vai ja cilvÄks dodas atvaļinÄjumÄ), visa atslÄga paliktu funkcionÄla.
KÄ dalÄ«ties noslÄpumÄ
Par Å”Äda veida atslÄgu pÄrvaldÄ«bas shÄmu Adi Å amirs domÄja 1979. gadÄ, kad viÅÅ” publicÄja savu darbu . RakstÄ Ä«si izskaidrots t.s 
sliekÅ”Åa shÄma slepenas vÄrtÄ«bas (piemÄram, kriptogrÄfiskÄs atslÄgas) efektÄ«vai sadalÄ«Å”anai daļas. Tad, kad un tikai tad, kad vismaz no daļas ir samontÄtas, jÅ«s varat viegli atjaunot noslÄpumu .
No droŔības viedokļa svarÄ«ga Ŕīs shÄmas Ä«paŔība ir tÄda, ka uzbrucÄjam nav jÄzina pilnÄ«gi nekas, ja vien viÅam nav vismaz daļas. Pat klÄtbÅ«tne daļÄm nevajadzÄtu sniegt nekÄdu informÄciju. MÄs to saucam par Ä«paÅ”umu semantiskÄ droŔība.
Polinomu interpolÄcija
Å amira sliekÅ”Åa shÄma veidota ap koncepciju polinoma interpolÄcija. Ja jÅ«s neesat pazÄ«stams ar Å”o koncepciju, tas patiesÄ«bÄ ir diezgan vienkÄrÅ”i. PatiesÄ«bÄ, ja jÅ«s kÄdreiz esat zÄ«mÄjis punktus grafikÄ un pÄc tam savienojis tos ar lÄ«nijÄm vai lÄ«knÄm, jÅ«s to jau esat izmantojis!
Caur diviem punktiem var uzzÄ«mÄt neierobežotu skaitu 2. pakÄpes polinomu. Lai no tiem izvÄlÄtos vienÄ«go, nepiecieÅ”ams treÅ”ais punkts. IlustrÄcija:
Apsveriet polinomu ar pirmo pakÄpi, . Ja vÄlaties attÄlot Å”o funkciju grafikÄ, cik punktu jums ir nepiecieÅ”ams? MÄs zinÄm, ka Ŕī ir lineÄra funkcija, kas veido lÄ«niju, un tÄpÄc tai ir nepiecieÅ”ami vismaz divi punkti. PÄc tam apsveriet polinoma funkciju ar otro pakÄpi, . Å Ä« ir kvadrÄtiskÄ funkcija, tÄpÄc, lai izveidotu grafiku, ir nepiecieÅ”ami vismaz trÄ«s punkti. KÄ bÅ«tu ar polinomu ar treÅ”o pakÄpi? Vismaz Äetri punkti. Un tÄ tÄlÄk un tÄ tÄlÄk.
PatieÅ”Äm forÅ”s Å”ajÄ Ä«paÅ”umÄ ir tas, ka, Åemot vÄrÄ polinoma funkcijas pakÄpi un vismaz punktu, mÄs varam iegÅ«t papildu punktus Å”ai polinoma funkcijai. MÄs saucam par Å”o papildu punktu ekstrapolÄciju polinoma interpolÄcija.
NoslÄpuma izdomÄÅ”ana
JÅ«s, iespÄjams, jau esat sapratis, ka tieÅ”i Å”eit parÄdÄs Å amira gudrÄ shÄma. Teiksim savu noslÄpumu -Å o . MÄs varam pagriezties lÄ«dz punktam grafikÄ un izdomÄt polinoma funkciju ar pakÄpi , kas atbilst Å”im punktam. AtgÄdinÄsim jums to bÅ«s mÅ«su nepiecieÅ”amo fragmentu slieksnis, tÄdÄļ, ja mÄs iestatÄm slieksni uz trim fragmentiem, mums jÄizvÄlas polinoma funkcija ar otro pakÄpi.
MÅ«su polinomam bÅ«s forma Kur Šø ā nejauÅ”i izvÄlÄti pozitÄ«vi veseli skaitļi. MÄs tikai konstruÄjam polinomu ar pakÄpi , kur brÄ«vais koeficients ā Tas ir mÅ«su noslÄpums , un katram nÄkamajam terminos ir nejauÅ”i izvÄlÄts pozitÄ«vs koeficients. Ja atgriezÄ«simies pie sÄkotnÄjÄ piemÄra un pieÅemam, ka , tad mÄs iegÅ«stam funkciju .
Å ajÄ brÄ«dÄ« mÄs varam Ä£enerÄt fragmentus, savienojot unikÄli veseli skaitļi Kur (jo tas ir mÅ«su noslÄpums). Å ajÄ piemÄrÄ mÄs vÄlamies izplatÄ«t Äetrus fragmentus ar trÄ«s slieksni, tÄpÄc mÄs nejauÅ”i Ä£enerÄjam punktus un nosÅ«tiet vienu punktu katram no Äetriem uzticamiem cilvÄkiem, atslÄgas glabÄtÄjiem. MÄs arÄ« darÄm to zinÄmu cilvÄkiem , jo tÄ tiek uzskatÄ«ta par publisku informÄciju un ir nepiecieÅ”ama atkopÅ”anai .
NoslÄpuma atgÅ«Å”ana
MÄs jau esam apsprieduÅ”i polinoma interpolÄcijas jÄdzienu un to, kÄ tas ir Å amira sliekÅ”Åa shÄmas pamatÄ. . Kad kÄdi trÄ«s no Äetriem pilnvarotajiem vÄlas atjaunot , viÅiem ir tikai jÄinterpolÄ ar saviem unikÄlajiem punktiem. Lai to izdarÄ«tu, viÅi var noteikt savus punktus un aprÄÄ·iniet Lagranža interpolÄcijas polinomu, izmantojot Å”Ädu formulu. Ja programmÄÅ”ana jums ir skaidrÄka nekÄ matemÄtika, tad pi bÅ«tÄ«bÄ ir operators for, kas reizina visus rezultÄtus, un sigma ir for, kas visu saskaita.
Pie mÄs varam to atrisinÄt Å”Ädi un atgriezt savu sÄkotnÄjo polinoma funkciju:
Jo mÄs to zinÄm , atveseļoÅ”anÄs darÄ«ts vienkÄrÅ”i:
NedroÅ”as veselu skaitļu aritmÄtikas izmantoÅ”ana
Lai gan esam veiksmÄ«gi pielietojuÅ”i Å amira pamatideju , mums ir radusies problÄma, kuru lÄ«dz Å”im esam ignorÄjuÅ”i. MÅ«su polinoma funkcija izmanto nedroÅ”u veselu skaitļu aritmÄtiku. Å
emiet vÄrÄ, ka katram papildu punktam, ko uzbrucÄjs iegÅ«st mÅ«su funkcijas grafikÄ, citiem punktiem ir mazÄk iespÄju. To var redzÄt savÄm acÄ«m, kad, izmantojot veselu skaitļu aritmÄtiku, uzzÄ«mÄjat arvien lielÄku punktu skaitu polinoma funkcijai. Tas ir neproduktÄ«vs mÅ«su izvirzÄ«tajam droŔības mÄrÄ·im, jo āāuzbrucÄjam nevajadzÄtu zinÄt pilnÄ«gi neko, kamÄr viÅam tas ir vismaz fragmenti.
Lai parÄdÄ«tu, cik vÄja ir veselo skaitļu aritmÄtiskÄ Ä·Äde, apsveriet scenÄriju, kurÄ uzbrucÄjs ieguva divus punktus un zina publisko informÄciju, ka . No Ŕīs informÄcijas viÅÅ” var secinÄt , vienÄds ar diviem, un pievienojiet zinÄmÄs vÄrtÄ«bas formulÄ Šø .
PÄc tam uzbrucÄjs var atrast , skaitot :
TÄ kÄ mÄs esam definÄjuÅ”i kÄ nejauÅ”i atlasÄ«ti pozitÄ«vi veseli skaitļi, ir ierobežots skaits iespÄjamo . Izmantojot Å”o informÄciju, uzbrucÄjs var secinÄt , jo derÄs viss, kas lielÄks par 5 negatÄ«vs. Tas izrÄdÄs taisnÄ«ba, jo mÄs esam noteikuÅ”i
PÄc tam uzbrucÄjs var aprÄÄ·inÄt iespÄjamÄs vÄrtÄ«bas aizstÄjot Š² :
Ar ierobežotÄm iespÄjÄm priekÅ” kļūst skaidrs, cik viegli ir izvÄlÄties un pÄrbaudÄ«t vÄrtÄ«bas . Å eit ir tikai piecas iespÄjas.
Uzdevuma atrisinÄÅ”ana ar nedroÅ”u veselu skaitļu aritmÄtiku
Lai novÄrstu Å”o ievainojamÄ«bu, Å amirs iesaka izmantot modulÄro aritmÄtiku, aizstÄjot par Kur Šø ā visu pirmskaitļu kopa.
Ätri atcerÄsimies, kÄ darbojas modulÄrÄ aritmÄtika. Pulkstenis ar rÄdÄ«jumiem ir pazÄ«stams jÄdziens. ViÅa izmanto pulksteni, kas ir . TiklÄ«dz stundu rÄdÄ«tÄjs paiet divpadsmit, tas atgriežas pie viena. Interesanta Ŕīs sistÄmas Ä«paŔība ir tÄda, ka, vienkÄrÅ”i skatoties pulkstenÄ«, mÄs nevaram izsecinÄt, cik apgriezienus ir veikusi stundu rÄdÄ«tÄjs. TomÄr, ja mÄs zinÄm, ka stundu rÄdÄ«tÄjs ir pagÄjis 12 Äetras reizes, mÄs varam pilnÄ«bÄ noteikt pagÄjuÅ”o stundu skaitu, izmantojot vienkÄrÅ”u formulu Kur ir mÅ«su dalÄ«tÄjs (Å”eit ), ir koeficients (cik reizes dalÄ«tÄjs ieiet sÄkotnÄjÄ skaitÄ¼Ä bez atlikuma, Å”eit ) un ir atlikums, kas parasti atgriež modulo operatora zvanu (Å”eit ). Zinot visas Ŕīs vÄrtÄ«bas, mÄs varam atrisinÄt vienÄdojumu par , bet, ja mÄs palaidÄ«sim garÄm koeficientu, mÄs nekad nevarÄsim atjaunot sÄkotnÄjo vÄrtÄ«bu.
MÄs varam parÄdÄ«t, kÄ tas uzlabo mÅ«su shÄmas droŔību, piemÄrojot shÄmu mÅ«su iepriekÅ”ÄjÄ piemÄrÄ un izmantojot . MÅ«su jaunÄ polinoma funkcija , un jaunie punkti . Tagad atslÄgu turÄtÄji atkal var izmantot polinoma interpolÄciju, lai rekonstruÄtu mÅ«su funkciju, tikai Å”oreiz saskaitÄ«Å”anas un reizinÄÅ”anas operÄcijÄm ir jÄpievieno modulo samazinÄÅ”ana (piemÄram, ).
Izmantojot Å”o jauno piemÄru, pieÅemsim, ka uzbrucÄjs uzzinÄja divus no Å”iem jaunajiem punktiem, un publisko informÄciju . Å oreiz uzbrucÄjs, pamatojoties uz visu viÅa rÄ«cÄ«bÄ esoÅ”o informÄciju, izvada Å”Ädas funkcijas, kur ir visu pozitÄ«vo veselo skaitļu kopa un apzÄ«mÄ moduļa koeficientu .
Tagad mÅ«su uzbrucÄjs atrod vÄlreiz , aprÄÄ·inot :
Tad viÅÅ” mÄÄ£ina vÄlreiz aizstÄjot Š² :
Å oreiz viÅam ir nopietna problÄma. FormulÄ trÅ«kst vÄrtÄ«bu , Šø . TÄ kÄ ir bezgalÄ«gi daudz Å”o mainÄ«go kombinÄciju, viÅÅ” nevar iegÅ«t papildu informÄciju.
DroŔības apsvÄrumi
Å amira slepenÄ koplietoÅ”anas shÄma liecina droŔība no informÄcijas teorijas viedokļa. Tas nozÄ«mÄ, ka matemÄtika ir izturÄ«ga pat pret uzbrucÄju ar neierobežotu skaitļoÅ”anas jaudu. TomÄr Ä·ÄdÄ joprojÄm ir vairÄkas zinÄmas problÄmas.
PiemÄram, Å amira shÄma nerada fragmenti, kas jÄpÄrbauda, tas ir, cilvÄki var brÄ«vi uzrÄdÄ«t viltotus fragmentus un traucÄt atgÅ«t pareizo noslÄpumu. NaidÄ«gs fragmentu glabÄtÄjs ar pietiekamu informÄciju var pat radÄ«t citu fragmentu, mainoties pÄc saviem ieskatiem. Å Ä« problÄma tiek atrisinÄta, izmantojot pÄrbaudÄmas slepenÄs koplietoÅ”anas shÄmas, piemÄram, Feldmana shÄma.
VÄl viena problÄma ir tÄda, ka jebkura fragmenta garums ir vienÄds ar atbilstoÅ”Ä noslÄpuma garumu, tÄpÄc noslÄpuma garumu ir viegli noteikt. Å o problÄmu var atrisinÄt triviÄli polsterÄjums noslÄpums ar patvaļīgiem cipariem lÄ«dz noteiktam garumam.
Visbeidzot, ir svarÄ«gi atzÄ«mÄt, ka mÅ«su bažas par droŔību var pÄrsniegt paÅ”u dizainu. ReÄlÄs pasaules kriptogrÄfijas lietojumprogrammÄm bieži vien pastÄv sÄnu kanÄlu uzbrukumu draudi, kad uzbrucÄjs mÄÄ£ina iegÅ«t noderÄ«gu informÄciju no lietojumprogrammas izpildes laika, keÅ”atmiÅas, avÄrijÄm utt. Ja tas rada bažas, izstrÄdes laikÄ rÅ«pÄ«gi jÄapsver, vai izmantot aizsardzÄ«bas pasÄkumus, piemÄram, funkcijas un pastÄvÄ«ga laika uzmeklÄÅ”anu, nepieļaut atmiÅas saglabÄÅ”anu diskÄ un vairÄkus citus apsvÄrumus, kas neietilpst Ŕī raksta darbÄ«bas jomÄ.
Demo
uz Ir interaktÄ«va Å amira slepenÄs koplietoÅ”anas shÄmas demonstrÄcija. DemonstrÄcija, pamatojoties uz bibliotÄku , kas pati par sevi ir populÄrÄs programmas JavaScript ports . Å
emiet vÄrÄ, ka lielu vÄrtÄ«bu aprÄÄ·inÄÅ”ana , Šø var paiet kÄds laiks.
Avots: www.habr.com