Konsideroni një skenar ku duhet të siguroni një kasafortë bankare. Konsiderohet absolutisht i pathyeshëm pa çelës, i cili ju jepet që në ditën e parë të punës. Qëllimi juaj është të ruani në mënyrë të sigurt çelësin.
Le të themi se keni vendosur ta mbani çelësin me vete gjatë gjithë kohës, duke siguruar akses në hapësirën ruajtëse sipas nevojës. Por shpejt do të kuptoni se një zgjidhje e tillë nuk përshkallëzohet mirë në praktikë, sepse prania juaj fizike kërkohet sa herë që hapni hapësirën ruajtëse. Po pushimet që ju premtuan? Përveç kësaj, pyetja është edhe më e frikshme: po sikur të humbisni çelësin tuaj të vetëm?
Duke pasur parasysh pushimet tuaja, ju vendosni të bëni një kopje të çelësit dhe t'ia besoni atë një punonjësi tjetër. Megjithatë, ju e kuptoni që as kjo nuk është ideale. Duke dyfishuar numrin e çelësave, ju gjithashtu dyfishoni shanset për vjedhje të çelësave.
Në dëshpërim, ju shkatërroni kopjen dhe vendosni të ndani çelësin origjinal në gjysmë. Tani, ju do të mendoni se dy njerëz të besuar me fragmente kyçe do të duhej të ishin fizikisht të pranishëm për të mbledhur çelësin dhe për të hapur kasafortën. Kjo do të thotë që një hajdut duhet të vjedhë dy pjesë, që është dy herë më e vështirë se vjedhja e një çelësi. Megjithatë, shpejt e kuptoni se kjo skemë nuk është shumë më e mirë se vetëm një çelës, sepse nëse dikush humb gjysmë çelësi, çelësi i plotë nuk mund të rikuperohet.
Problemi mund të zgjidhet me një sërë çelësash dhe bravash shtesë, por kjo qasje do të kërkojë shpejt много çelësat dhe bravat. Ju vendosni që dizajni ideal do të ishte të ndani çelësin në mënyrë që siguria të mos varet tërësisht nga një person. Ju gjithashtu arrini në përfundimin se duhet të ketë një prag për numrin e fragmenteve, në mënyrë që nëse një fragment humbet (ose nëse një person shkon me pushime), i gjithë çelësi të mbetet funksional.
Si të ndani një sekret
Ky lloj i skemës së menaxhimit kyç u mendua nga Adi Shamir në vitin 1979 kur botoi veprën e tij . Artikulli shpjegon shkurtimisht të ashtuquajturat 
skema e pragut për ndarjen efikase të një vlere sekrete (siç është një çelës kriptografik) në pjesët. Atëherë, kur dhe vetëm kur të paktën nga pjesët janë mbledhur, ju lehtë mund ta rivendosni sekretin .
Nga pikëpamja e sigurisë, një veti e rëndësishme e kësaj skeme është se sulmuesi nuk duhet të dijë absolutisht asgjë nëse nuk ka të paktën pjesët. Edhe prania pjesët nuk duhet të japin asnjë informacion. Ne e quajmë këtë pronë siguria semantike.
Interpolimi polinomial
Skema e pragut të Shamirit ndërtuar rreth konceptit interpolimi polinom. Nëse nuk jeni të njohur me këtë koncept, në fakt është mjaft i thjeshtë. Në fakt, nëse keni vizatuar ndonjëherë pika në një grafik dhe më pas i keni lidhur ato me vija ose kthesa, tashmë e keni përdorur atë!
Nëpërmjet dy pikave mund të vizatoni një numër të pakufizuar polinomesh të shkallës 2. Për të zgjedhur të vetmen prej tyre, ju duhet një pikë e tretë. Ilustrim:
Konsideroni një polinom me shkallën e parë, . Nëse dëshironi ta vizatoni këtë funksion në një grafik, sa pikë ju nevojiten? Epo, ne e dimë se ky është një funksion linear që formon një vijë dhe kështu i duhen të paktën dy pika. Më pas, merrni parasysh një funksion polinom me shkallën dy, . Ky është një funksion kuadratik, kështu që të paktën tre pika kërkohen për të paraqitur grafikun. Po për një polinom me shkallën tre? Të paktën katër pikë. Dhe kështu me radhë e kështu me radhë.
Gjëja vërtet interesante në lidhje me këtë veti është se, duke pasur parasysh shkallën e funksionit polinomial dhe të paktën pikë, mund të nxjerrim pika shtesë për këtë funksion polinom. Ne e quajmë ekstrapolimin e këtyre pikave shtesë interpolimi polinom.
Krijimi i një sekreti
Mund ta keni kuptuar tashmë se këtu hyn në lojë skema e zgjuar e Shamirit. Le të themi sekretin tonë - A . Mund të kthehemi në një pikë të grafikut dhe të dalë me një funksion polinom me shkallë , që e plotëson këtë pikë. Le t'ju kujtojmë se do të jetë pragu ynë i fragmenteve të kërkuara, kështu që nëse e vendosim pragun në tre fragmente, duhet të zgjedhim një funksion polinom me shkallën dy.
Polinomi ynë do të ketë formën Ku и - numra të plotë pozitiv të zgjedhur rastësisht. Ne thjesht po ndërtojmë një polinom me shkallë , ku koeficienti i lirë - Ky është sekreti ynë , dhe për secilën nga ato pasuese terma ka një koeficient pozitiv të zgjedhur rastësisht. Nëse i kthehemi shembullit origjinal dhe supozojmë se , atëherë marrim funksionin .
Në këtë pikë ne mund të gjenerojmë fragmente duke u lidhur numra të plotë unikë në Ku (sepse është sekreti ynë). Në këtë shembull, ne duam të shpërndajmë katër fragmente me një prag prej tre, kështu që ne gjenerojmë në mënyrë të rastësishme pikë dhe dërgoji një pikë secilit prej katër njerëzve të besuar, kujdestarëve të çelësit. Ne gjithashtu ua bëjmë të ditur njerëzve këtë , pasi ky konsiderohet informacion publik dhe është i nevojshëm për rikuperim .
Rikuperimi i sekretit
Ne kemi diskutuar tashmë konceptin e interpolimit polinomial dhe se si ai qëndron në themel të skemës së pragut të Shamirit . Kur çdo tre nga katër të besuarit dëshiron të rivendosë , ata vetëm duhet të interpolojnë me pikat e veta unike. Për ta bërë këtë, ata mund të përcaktojnë pikat e tyre dhe llogaritni polinomin e interpolimit të Lagranzhit duke përdorur formulën e mëposhtme. Nëse programimi është më i qartë për ju sesa matematika, atëherë pi është në thelb një operator for, e cila shumëzon të gjitha rezultatet, dhe sigma është for, e cila shton gjithçka.
në ne mund ta zgjidhim atë si kjo dhe të kthejmë funksionin tonë origjinal polinom:
Meqenëse e dimë këtë , rimëkëmbje bëhet thjesht:
Përdorimi i aritmetikës së numrave të plotë të pasigurt
Edhe pse ne kemi zbatuar me sukses idenë bazë të Shamirit , na ka mbetur një problem që e kemi injoruar deri tani. Funksioni ynë polinom përdor aritmetikë të pasigurt të numrave të plotë. Vini re se për çdo pikë shtesë që një sulmues merr në grafikun e funksionit tonë, ka më pak mundësi për pika të tjera. Ju mund ta shihni këtë me sytë tuaj kur vizatoni një numër në rritje pikash për një funksion polinom duke përdorur aritmetikën e numrave të plotë. Kjo është kundërproduktive për qëllimin tonë të deklaruar të sigurisë, sepse sulmuesi nuk duhet të dijë absolutisht asgjë derisa të paktën të ketë fragmente.
Për të demonstruar se sa i dobët është qarku aritmetik me numra të plotë, merrni parasysh një skenar në të cilin një sulmues ka marrë dy pikë dhe njeh informacionin publik që . Nga ky informacion ai mund të nxjerrë përfundime , e barabartë me dy, dhe futni vlerat e njohura në formulë и .
Sulmuesi më pas mund të gjejë , duke numëruar :
Meqenëse e kemi përcaktuar si numra të plotë pozitivë të zgjedhur rastësisht, ka një numër të kufizuar të mundshëm . Duke përdorur këtë informacion, një sulmues mund të nxjerrë përfundime , pasi çdo gjë më e madhe se 5 do të bëjë negativ. Kjo rezulton të jetë e vërtetë pasi ne kemi vendosur
Sulmuesi më pas mund të llogarisë vlerat e mundshme duke zëvendësuar в :
Me opsione të kufizuara për bëhet e qartë se sa e lehtë është përzgjedhja dhe kontrollimi i vlerave . Këtu ka vetëm pesë opsione.
Zgjidhja e problemit me aritmetikë të pasigurt të numrave të plotë
Për të eliminuar këtë dobësi, Shamir sugjeron përdorimin e aritmetikës modulare, duke zëvendësuar mbi Ku и - bashkësia e të gjithë numrave të thjeshtë.
Le të kujtojmë shpejt se si funksionon aritmetika modulare. Një orë me akrepa është një koncept i njohur. Ajo përdor një orë që është . Sapo akrepi i orës kalon dymbëdhjetë, ai kthehet në një. Një veti interesante e këtij sistemi është se thjesht duke parë orën, ne nuk mund të nxjerrim përfundimin se sa rrotullime ka bërë akrepa e orës. Megjithatë, nëse e dimë se akrepi i orës ka kaluar 12 katër herë, ne mund të përcaktojmë plotësisht numrin e orëve që kanë kaluar duke përdorur një formulë të thjeshtë. Ku është pjesëtuesi ynë (këtu ), është koeficienti (sa herë pjesëtuesi hyn në numrin origjinal pa mbetje, këtu ), dhe është pjesa e mbetur, e cila zakonisht kthen një telefonatë modul operatori (këtu ). Njohja e të gjitha këtyre vlerave na lejon të zgjidhim ekuacionin për , por nëse humbasim koeficientin, nuk do të mund të rivendosim kurrë vlerën origjinale.
Ne mund të demonstrojmë se si kjo përmirëson sigurinë e skemës sonë duke aplikuar skemën në shembullin tonë të mëparshëm dhe duke përdorur . Funksioni ynë i ri polinom , dhe pikat e reja . Tani mbajtësit e çelësave mund të përdorin edhe një herë interpolimin polinomial për të rindërtuar funksionin tonë, vetëm këtë herë operacionet e mbledhjes dhe shumëzimit duhet të shoqërohen me reduktim të modulit (p.sh. ).
Duke përdorur këtë shembull të ri, le të supozojmë se sulmuesi mësoi dy nga këto pika të reja, , dhe informacion publik . Këtë herë, sulmuesi, bazuar në të gjitha informacionet që disponon, nxjerr funksionet e mëposhtme, ku është bashkësia e të gjithë numrave të plotë pozitivë, dhe paraqet koeficientin e modulit .
Tani sulmuesi ynë gjen përsëri , duke llogaritur :
Pastaj ai provon përsëri duke zëvendësuar в :
Këtë herë ai ka një problem serioz. Formulës i mungojnë vlerat , и . Meqenëse ka një numër të pafund kombinimesh të këtyre variablave, ai nuk mund të marrë asnjë informacion shtesë.
Konsideratat e Sigurisë
Skema e ndarjes së fshehtë të Shamirit sugjeron siguria nga pikëpamja e teorisë së informacionit. Kjo do të thotë se matematika është rezistente edhe ndaj një sulmuesi me fuqi llogaritëse të pakufizuar. Megjithatë, qarku ende përmban disa çështje të njohura.
Për shembull, skema e Shamirit nuk krijon fragmente që duhen kontrolluar, domethënë, njerëzit mund të paraqesin lirisht fragmente të rreme dhe të ndërhyjnë në rikuperimin e sekretit të saktë. Një ruajtës i fragmentit armiqësor me informacion të mjaftueshëm mund të prodhojë edhe një fragment tjetër duke ndryshuar sipas gjykimit tuaj. Ky problem zgjidhet duke përdorur skema të verifikueshme të ndarjes së sekretit, siç është skema e Feldman-it.
Një problem tjetër është se gjatësia e çdo fragmenti është e barabartë me gjatësinë e sekretit përkatës, kështu që gjatësia e sekretit është e lehtë për t'u përcaktuar. Ky problem mund të zgjidhet në mënyrë të parëndësishme mbushje sekret me numra arbitrar deri në një gjatësi fikse.
Së fundi, është e rëndësishme të theksohet se shqetësimet tona të sigurisë mund të shtrihen përtej vetë dizajnit. Për aplikacionet kriptografike të botës reale, shpesh ekziston kërcënimi i sulmeve të kanalit anësor, ku një sulmues përpiqet të nxjerrë informacione të dobishme nga koha e ekzekutimit të aplikacionit, memoria e fshehtë, përplasjet, etj. Nëse ky është një shqetësim, gjatë zhvillimit duhet t'i kushtohet vëmendje përdorimit të masave mbrojtëse të tilla si funksionet dhe kërkimet në kohë të vazhdueshme, parandalimi i ruajtjes së kujtesës në disk dhe një sërë konsideratash të tjera që janë përtej qëllimit të këtij neni.
demonstrim
Mbi Ekziston një demonstrim interaktiv i skemës së ndarjes së fshehtë të Shamirit. Demonstrimi i bazuar në bibliotekë , e cila në vetvete është një port JavaScript e programit popullor . Vini re se llogaritja e vlerave të mëdha , и mund të marrë pak kohë.
Burimi: www.habr.com