Le të shqyrtojmë një skenar ku është e nevojshme të sigurohet siguria e depozitës bankare. Ajo konsiderohet plotësisht e papërshkueshme pa çelësin që ju jepet në ditën e parë të punës. Qëllimi juaj është ta ruani çelësin me besim.

Supozoni se vendosni ta mbani gjithmonë çelësin me vete, duke ofruar akses në depozitë sipas nevojës. Por shpejt do të kuptoni se ky zgjidhje nuk është praktike pasi çdo herë për të hapur depozitën kërkohet prania juaj fizike. Dhe si ndodhet me pushimet që ju janë premtuar? Për më tepër, pyetja e frikshme është: çfarë nëse e humbni çelësin e vetëm?

Me mendimin për pushimet, vendosni të bëni një kopje të çelësit dhe t'ia besoni një kolegu tjetër. Megjithatë, kuptoni se kjo gjithashtu nuk është ideale. Duke dyfishuar numrin e çelësave, ju gjithashtu keni dyfishuar mundësitë për vjedhje të çelësit.

Të dëshpëruar, e shkatërroni kopjen dhe vendosni të ndani çelësin origjinal në dy pjesë. Tani, mendoni se dy njerëz të besuar me fragmente të çelësit duhet të jenë fizikisht të pranishëm për të bërë çelësin dhe hapur depozitën. Kjo do të thotë se vjedhësi duhet të vjedhë dy fragmente, që është dyfish më e vështirë se vjedhja e një çelësi të vetëm. Megjithatë, së shpejti kuptoni se ky skemë nuk është shumë më e mirë se një çelës i vetëm, pasi nëse dikush humb një nga pjesët e çelësit, çelësi i plotë nuk mund të rikuperohet.

Problemi mund të zgjidhet me një seri çelësash dhe çelësh shtesë, por me këtë qasje shpejt do të nevojiten shumë çelësa dhe çelësa. Ju vendosni se në një skemë ideale duhet të ndahet çelësi, në mënyrë që siguria të mos mbështetet plotësisht në një person. Ju gjithashtu arrini në përfundimin se duhet të ekzistojë një prag i numrit të pjesëve, për të bërë që humbja e një pjese (ose nëse dikush shkon në pushime) të mos çojë në mosfunksionimin e të gjithë çelësit.

Si të ndahen sekretet

Për një lloj të tillë skeme menaxhimi të çelësave mendonte Adi Shamir në vitin 1979, kur publikoi punimin e tij «Si të ndahen sekretet». Në artikull shpjegohet shkurtimisht ajo që quhet skema e pragut për ndarjen efektive të një vlere sekrete (për shembull, një çelës kriptografik) në pjesë. Më pas, kur dhe vetëm kur të paktën nga pjesë të mbledhura, mund të rikuperohet lehtë sekreti .

Nga këndvështrimi i sigurisë, një veçori e rëndësishme e kësaj skeme është se sulmuesi nuk duhet të dijë asgjë nëse nuk ka të paktën pjesë. Edhe prania e pjesëve nuk duhet t'u japë asnjë informacion. Ne e quajmë këtë veçori siguri semantike.

Interpolimi polinominal

Skema e Shamir ndërtohet rreth konceptit interpolimit polinominal. Nëse nuk jeni të njohur me këtë koncept, në të vërtetë është mjaft i thjeshtë. Në përgjithësi, nëse keni çizmuar ndonjëherë pikë në një grafik dhe pastaj i keni lidhur ato me linja ose kurba, atëherë keni përdorur atë!

Përmes dy pikave mund të kalojnë një numër të pakufizuar polinomesh të gradës 2. Për të zgjedhur një të vetme - ne kemi nevojë për një pikë të tretë. Ilustrimi: Wikipedia

Merrni një polinom me gradë një, . Nëse dëshironi ta ndërtoni këtë funksion në grafik, sa pika ju nevojiten? E dimë se ky është një funksion linear që formon një vijë dhe prandaj nevojiten të paktën dy pika. Tani, le të shqyrtojmë një funksion polinomial me gradë dy, . Ky është një funksion kuadratik, prandaj për të ndërtuar grafik nevojiten të paktën tre pika. Si qëndron me një polinom me gradë tre? Të paktën katër pika. Dhe kështu me radhë.

Gjëja vërtet e shkëlqyer lidhur me këtë veçori është se, duke marrë parasysh gradën e funksionit polinomial dhe, të paktën pikë, ne mund të nxjerrim pika shtesë për këtë funksion polinomial. Ekstrapolimin e këtyre pikave shtesë e quajmë interpolim polinomial.

Krijimi i sekreteve

Mund të keni kuptuar tashmë se këtu hyjnë në loje skemat e mençura të Shamir. Le të supozojmë se sekreti ynë — është . Ne mund ta kthejmë në një pikë në grafik dhe të krijojmë një funksion polinomial me gradë , që plotëson këtë pikë. Kujtojmë se do të jetë prag i fragmenteve të kërkuara, prandaj nëse e vendosim pragun në tre fragmente, duhet të zgjedhim një funksion polinomial me gradë dy.

Polinomi ynë do të ketë formën index dhe — numra të plotë pozitivë të zgjedhur rastësisht. Ne thjesht po ndërtojmë një polinom me gradë , ku koeficenti i lirë  është sekreti ynë , dhe çdo një nga të tjerët anëtarët kanë një koeficient pozitiv të zgjedhur rastësisht. Nëse kthehemi te shembulli fillestar dhe supozoni se , atëherë do të marrim funksionin .

Në këtë fazë ne mund të gjenerojmë pjesë duke lidhur numra të veçantë të plotë në index (sepse është sekreti ynë). Në këtë shembull ne duam të shpërndajmë katër pjesë me prag tre, prandaj gjenerojmë rastësisht pikët dhe dërgojmë një pikë për secilin nga katër individët e besuar, ruajtësit e çelësit. Ne gjithashtu i njoftojmë ata se , pasi kjo konsiderohet informacion publik dhe është e nevojshme për rikuperimin .

Rikuperimi i sekrecionit

Ne kemi diskutuar tashmë konceptin e interpolimit polinomik dhe se çfarë qëndron në bazë të skemës së pragut të Shamir . Kur çdo tre nga katër individët e besuar duan të rikuperojnë , ata vetëm duhet të interpozojnë me pikët e tyre unike. Për këtë ata mund të përcaktojnë pikët e tyre dhe të llogaritin polinomin e interpolimit të Lagranges, duke përdorur formulën e mëposhtme. Nëse programimi është më i kuptueshëm për ju se matematika, atëherë pi është në thelb operatori për, i cili shumon të gjithë rezultatet, ndërsa sigma është për, i cili i shton të gjitha.

Kur ne mund ta zgjidhim këtë në këtë mënyrë dhe të kthejmë funksionin tonë polinomial origjinal:

Pasi e dimë që , rikuperimi ndodh thjesht:

Përdorimi i aritmetikës konsideruese të plotë të pasigurt

Megjithëse kemi aplikuar me sukses idenë themelore të Shamir , na mbetet një problem që e kemi injoruar deri tani. Funksioni ynë polinomial përdor aritmetikën konsideruese të plotë të pasigurt. Kini parasysh se për secilën pikë shtesë që sulmuesi merr në grafikën e funksionit tonë, mbetet më pak mundësi për pikët e tjera. Ju mund ta shihni këtë me sy tuaj kur përbëni një grafik me rritjen e numrit të pikëve për funksionin polinomial duke përdorur aritmetikën e plotë. Kjo është kontraproduktive për qëllimin tonë të deklaruar të sigurisë, sepse sulmuesi nuk duhet të dijë asgjë derisa të ketë të paktën pjesë.

Për të demonstruar se sa e dobët është skema me aritmetikë të plotë, shqyrtoni një skenar ku sulmuesi ka marrë dy pika dhe di informacionin publik që . Nga këto informacione ai mund të nxjerrë , i barabartë me dy, dhe të lidhet në formulë me vlerat e njohura dhe .

Pastaj sulmuesi mund të gjejë , duke llogaritur :

Pasi e kemi përcaktuar si numra të rinj pozitiv, ka një numër të kufizuar mundësish . Me këtë informacion, sulmuesi mund të nxjerrë , pasi gjithçka më shumë se 5 do të bëjë negative. Kjo del të jetë e vërtetë, pasi e kemi përcaktuar

Pastaj, sulmuesi mund të llogarisë vlerat e mundshme , duke zëvendësuar në :

Me një grup të kufizuar mundësish për është e qartë se sa lehtë është të përshtaten dhe verifikohen vlerat . Ka gjithsej pesë mundësi.

Zgjidhja e problemit me aritmetikën e sigurt të numrave të plotë

Për të eliminuar këtë dobësi, Shamir sugjeron përdorimin e aritmetikës modulare, duke zëvendësuar në index dhe — grupi i të gjitha numrave të thjeshtë.

Le të përkujtojmë shpejt se si funksionon aritmetika modulare. Orarët me dritare janë një koncept i njohur. Ajo përdor oraret që janë . Sa herë që shigjeta e orës kalon nga dymbëdhjeta, ajo kthehet tek një. Një veçori interesante e kësaj sistemi është se thjesht duke parë orën, ne nuk mund ta nxjerrim se sa herë ka kaluar shigjeta e orës. Megjithatë, nëse e dimë se shigjeta e orës ka kaluar 12 katër herë, mund të përcaktojmë plotësisht numrin e orëve të kaluara me një formulë të thjeshtë index  — kjo është ndarja jonë (këtu ),  — kjo është koeficienti (sa herë ndarja kalon në numrin origjinal pa mbetje, këtu — emri i funksionit (  — kjo është mbetja, e cila zakonisht kthehet nga operatori i modulit (këtu ). Të diturit të gjitha këto vlera na lejon të zgjidhim ekuacionin për , por nëse humbasim koeficientin, kurrë nuk do të mund të rikthejmë vlerën origjinale.

Mund të demonstrohet se si kjo përmirëson sigurinë e skemës sonë duke zbatuar skemën në shembullin tonë të mëparshëm dhe duke përdorur . Funksioni ynë polinomial i ri , dhe pikët e reja . Tani ruajtësit e çelësit mund të përdorin përsëri interpolimin polinomial për të rikthyer funksionin tonë, megjithatë, këtë herë operacionet e shtimit dhe shumëzimit duhet të shoqërohen me zvogëlimin modulas (p.sh. ).

Duke përdorur këtë shembull të ri, le të supozojmë se sulmuesi ka mësuar dy nga këto pika të reja, , dhe informacioni publik . Në këtë rast, sulmuesi, duke u mbështetur në të gjitha informacionet në dispozicion, nxjerr funksionet e mëposhtme, ku  është集合të gjithë numrat e plotë pozitivë, dhe përdor koeficientin e modulit .

Tani, sulmuesi ynë përsëri gjen , duke llogaritur :

Pastaj ai përpiqet sërish të nxjerrë , duke zëvendësuar në :

Në këtë rast, ai ka një problem serioz. Në formulë mungojnë vlerat , dhe . Duke marrë parasysh se ekziston një numër të pafund kombinimesh këthese, ai nuk mund të marrë asnjë informacion shtesë.

Konsideratat e sigurisë

Skema e ndarjes së sekreteve të Shamir ofron siguri nga këndvështrimi i teorisë së informacionit. Kjo do të thotë se matematika është e fortë, madje edhe përballë një sulmuesi me kapacitete të pakufizuara llogaritëse. Megjithatë, skema tërheq disa probleme të njohura.

Për shembull, skema e Shamir-it nuk krijon fragmente të verifikueshme, domethënë, njerëzit mund të paraqesin lirshëm fragmente fallco dhe ta pengojnë rikuperimin e sekreteve të sakta. Një ruajtës armiqesor i fragmenteve me informacion të mjaftueshëm mund të krijojë madje një fragment tjetër, duke modifikuar sipër dëshirës së tij. Ky problem zgjidhet përmes schema të verifikueshme të ndarjes së sekreteve, siç është skema e Feldman.

Një problem tjetër është se gjatësia e çdo fragmenti është e barabartë me gjatësinë e sekreteve përkatëse, kështu që gjatësia e sekreteve është e lehtë për t'u përcaktuar. Ky problem zgjidhet përmes një mbushjeje të sekreteve me numra të rastësishëm deri në një gjatësi fikse.

Së fundi, është e rëndësishme të theksohet se shqetësimet tona për sigurinë mund të tejkalojnë veten e skemës. Për aplikacione reale kriptografike shpesh ka kërcënim nga sulmet përmes kanaleve anësore, kur sulmuesi përpiqet të nxjerrë informacion të dobishëm nga koha e ekzekutimit të aplikacionit, caches, dështime, etj. Nëse kjo ngre shqetësime, duhet të shqyrtohen me kujdes masa mbrojtëse si funksionet dhe kërkimi me kohë të qëndrueshme të ekzekutimit, për të parandaluar ruajtjen e të dhënave në disk dhe të mendohet për një sërë gjërash që kalojnë jashtë këtij artikulli.

Demo

Në në këtë faqe eksiston një demonstrim interaktiv të skemës së ndarjes së sekreteve të Shamir. Demonstrimi është i bazuar në bibliotekën ssss-js, e cila vetë është një port të njohur të programit JavaScript ssss. Ju kujtojmë se llogaritja e vlerave të mëdha , dhe mund të marrë pak kohë.

Burimi: habr.com