Le të shqyrtojmë një skenar kur është e nevojshme të sigurohet siguria e një depo bankare. Ajo konsiderohet krejtësisht e paprekshme pa çelësin, i cili ju jepet në ditën e parë të punës. Qëllimi juaj është të ruani çelësin në mënyrë të sigurt.

Supozoni se keni vendosur ta mbani gjithnjë çelësin me vete, duke ofruar akses në depo sipas nevojës. Por shpejt do të kuptoni se ky zgjidhje në praktikë nuk është e qëndrueshme, sepse çdo herë për të hapur depon kërkohet prania juaj fizike. Çfarë ndodh me pushimet që ju janë premtuar? Për më tepër, mbetet një pyetje e frikshme: çfarë ndodh nëse humbni çelësin tuaj të vetëm?

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

Duke u dëshpëruar, ju shkaterroni një kopje dhe vendosni të ndani çelësin origjinal në dy pjesë. Tani, mendoni se dy persona të besueshëm me fragmentet e çelësit duhet të jenë fizikisht të pranishëm për të mbledhur çelësin dhe hapur arkën. Kjo do të thotë që hajduti duhet të vjedhë dy fragmente, që është dyfish më e vështirë se vjedhja e një çelësi. Megjithatë, shpejt kuptoni se kjo skemë nuk është shumë më e mirë sesa thjesht një çelës, sepse nëse dikush humbet një pjesë të çelësit, çelësi i plotë nuk mund të restaurohet.

Problemi mund të zgjidhet me një seri çelësash dhe çelësash, por me këtë qasje shpejt do të nevojiten shumë çelësa dhe çelësa. Ju vendosni që në një skemë ideale duhet të ndahet çelësi, në mënyrë që siguria të mos mbështetet plotësisht në një person të vetëm. Ju gjithashtu arrini në përfundimin se duhet të ekzistojë një kufi i caktuar i numrit të fragmenteve, kështu që në rast se humbet një fragment (ose nëse një person largohet për pushime) i gjithë çelësi të mbetet funksional.

Si të ndani një sekret

Për këtë lloj skeme të menaxhimit të çelësave mendohej nga Adi Shamir në vitin 1979, kur publikoi punimin e tij "Si të ndahet një sekret". Artikulli shpjegon shkurtimisht që është e ashtuquajtura skema pragmatike për ndarjen efektive të një vlerë sekrete (p.sh., çelësi kriptografik) në pjesë. Pastaj, kur dhe vetëm kur të paktën nga pjesët janë mbledhur, mund të rikuperohet lehtësisht sekreti .

Nga pikëpamja e sigurisë, një nga atributet e rëndësishme të kësaj skeme është se një sulmues nuk duhet të dijë absolutisht asgjë, nëse ai nuk ka të paktën pjesë. Edhe posedimi i pjesëve nuk duhet të japë asnjë informacion. Ne e quajmë këtë atribut siguria semantike.

Interpolimi polinomial

Skema pragmatike e Shamir ndërtohet rreth konceptit të interpolimit polinomial. Nëse nuk jeni njohur me këtë koncept, ai në fakt është mjaft i thjeshtë. Në përgjithësi, nëse ndonjëherë keni vizatuar pika në një grafik dhe më pas i keni lidhur ato me linja ose kurba, atëherë keni përdorur tashmë atë!

Përmes dy pikave, mund të tërheqni një numër të pakufizuar polinomësh të gradës 2. Për të zgjedhur vetëm një të tillë - nevojitet një pikë e tretë. Ilustrimi: Wikipedia

Le të shqyrtojmë një polinom me gradë një, . Nëse dëshironi të ndërtoni këtë funksion në grafik, sa pika ju nevojiten? E dimë se ky është një funksion linear, i cili formon një vijë dhe për këtë arsye nevojiten të paktën dy pika. Më pas, le të shqyrtojmë një funksion polinomial me gradë dy, . Ky është një funksion katror, prandaj për ndërtimin e grafikës kërkohen të paktën tre pika. Si për një polinom me gradë tre? Të paktën katër pika. Dhe kështu me radhë.

Ajo që është vërtet e mrekullueshme në këtë pronë është se, duke marrë parasysh gradën e funksionit polinom, dhe, të paktën, pikave, ne mund të nxjerrim pika të tjera për këtë funksion polinomial. Ekstrapolimi i këtyre pikave të tjera ne e quajmë interpolimi polinomial.

Krijimi i një sekreti

Mund të keni kuptuar tashmë se këtu hyn në lojë skema e mençur e Shamir. Le të supozojmë se sekreti ynë — kjo është . Ne mund ta kthejmë në një pikë në grafik dhe të krijojmë një funksion polinomial me gradë , i cili përmbush këtë pikë. Le të kujtojmë se do të jetë prag i kërkuar për fragmentet, prandaj nëse e vendosim pragun në tre fragmente, duhet të zgjedhim një funksion polinom me gradë dy.

Polinomi ynë do të ketë formën , ku dhe — numra të rastësishëm pozitivë të plotë. Ne thjesht po ndërrmarim një polinom me gradë , ku koeficienti i lirë  — është sekreti ynë , ndërsa secili nga anëtarët e mbetur ka një koeficient pozitiv të zgjedhur rastësisht. Nëse kthehemi në shembullin fillestar dhe supozojmë se , atëherë do të marrim funksionin .

Në këtë fazë, mund të gjenerojmë fragmentet, duke lidhur numra të plotë unikë në , ku (sepse ky është sekreti ynë). Në këtë rast, ne duam të japim katër fragmente me prag tre, prandaj gjenerojmë rastësisht pikët dhe dërgojmë nga një pikë për secilin nga katër personat e besuar, ruajtësit e çelësave. Ne gjithashtu i njoftojmë njerëzit se , pasi kjo konsiderohet informacion publik dhe është e nevojshme për rikuperimin .

Rikuperimi i sekretit

Kemi diskutuar tashmë konceptin e interpolimit polinom dhe atë që qëndron në bazë të skemës së pragut të Shamir . Kur tre personat nga katër të besueshëm duan të rikuperojnë , ata duhet vetëm të ndërtojnë me pikat e tyre unike. Për këtë ata mund të përcaktojnë pikat e tyre dhe të llogarisin polinomin e interpolimit të Lagrange-it, duke përdorur formulën në vijim. Nëse programimi ju kuptohet më mirë se matematika, pi është në thelb një operator për, i cili shumëzon të gjitha rezultatet, dhe sigma është për, i cili gjithçka i shton.

Në ne mund ta zgjidhim këtë duke e bërë në këtë mënyrë dhe të kthejmë funksionin tonë polinomial origjinal:

Duke ditur se , rikuperimi realizohet thjesht:

Përdorimi i aritmetikës së sigurtë të numrave të plotë

Megjithëse kemi aplikuar me sukses idenë kryesore të Shamirit , ne na mbetet një problem, të cilin e kemi injoruar deri më tani. Funksioni ynë polinomial përdor aritmetikë të pa sigurt të numrave të plotë. Mbani parasysh se për çdo pikë shtesë që një sulmues merr në grafikën e funksionit tonë, mbetet një numër më i vogël mundësish për pika të tjera. Mund ta shihni këtë me sy kur ndërtoni grafik me rritjen e numrit të pikave për funksionin polinomial duke përdorur aritmetikë të numrave të plotë. Kjo është kontraproduktive për qëllimin tonë të pretenduar të sigurisë, sepse një sulmues nuk duhet të dijë asgjë derisa të ketë të paktën fragmente.

Për të demonstruar sa e dobët është skema e aritmetikës së numrave të plotë, le të shqyrtojmë një skenar në të cilin një sulmues ka marrë dy pika dhe di informacionin publik që . Nga ky informacion ai mund të nxjerrë , i cili është i barabartë me dy, dhe të lidhë në formulë vlerat e njohura dhe .

Pastaj, sulmuesi mund të gjejë , duke e llogaritur :

Duke marrë parasysh se ne e kemi përcaktuar si numra të plotë pozitivë të zgjedhur rastësisht, ka një numër të kufizuar mundësish . Me këtë informacion, një sulmues mund të nxjerrë , pasi çdo gjë më shumë se 5 do ta bëjë negative. Kjo rezulton të jetë e vërtetë, pasi ne e kemi përcaktuar

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

Me një grup të kufizuar mundësish për bëhet e qartë se sa lehtë është të gjenden dhe të verifikohen vlerat . Këtu ka vetëm pesë mundësi.

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

Për të eliminuar këtë dobësi, Shamir sugjeron të përdoren aritmetika modulo, duke zëvendësuar në , ku dhe — grupi i të gjithë numrave të thjeshtë.

Le të rikujtojmë shpejt si funksionon aritmetika modulo. Ora me shifra është një koncept i njohur. Ajo përdor orët që janë . Sa herë që akrepi i orës kalon 12, ai kthehet në një. Një karakteristikë interesante e kësaj sistemi është se vetëm duke e parë orën, nuk mund të nxjerrim se sa herë ka kaluar akrepi i orës. Megjithatë, nëse e dimë që akrepi i 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ë , ku  — ky është ndarësi ynë (këtu ),  — është koeficienti (sa herë ndahen pa mbetje ndarësi në numrin fillestar, këtu ), ndërsa  — është mbetja, që zakonisht e kthen thirrja e operatorit modulo (këtu ). Njohja e të gjitha këtyre vlerave na lejon të zgjidhim ekuacionin për , por nëse e anashkalojmë koeficientin, kurrë nuk do të jemi në gjendje të rikuperojmë vlerën fillestare.

Mund të demonstrojmë se si kjo përmirëson sigurinë e skemës tonë, duke aplikuar skemën në shembullin tonë të mëparshëm dhe duke përdorur . Funksioni ynë polinom i ri , dhe pikët e reja . Tani ruajtësit e çelësit mund të përdorin përsëri interpolimin polinom për të rikuperuar funksionin tonë, por këtë herë operacionet e mbledhjes dhe shumëzimit duhet të shoqërohen me reduktimin modulo (p.sh. ).

Duke përdorur këtë shembull të ri, supozoni se një sulmues ka mësuar dy nga këto pika të reja, , dhe informacioni publik . Këtë herë, sulmuesi bazuar në gjithë informacionin që ka nxjerrë funksionet në vijim, ku  — është grupi i të gjithë numrave të plotë pozitivë, dhe përfaqëson koeficientin e modulit .

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

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

Këtë herë ai ka një problem serioz. Në formulë mungojnë vlerat , dhe . Duke qenë se ekzistojnë një numër të pafund të kombinimeve të këtyre variablave, ai nuk mund të marrë ndonjë informacion të mëtejshëm.

Konsideratat e sigurisë

Skema e ndarjes së sekretit të Shamires ofron siguri nga perspektiva e teorisë së informacionit. Kjo do të thotë se matematika është e qëndrueshme edhe përballë një sulmuesi me fuqinë e pakufizuar të llogaritjes. Sidoqoftë, skema ende përmban disa probleme të njohura.

Për shembull, skema e Shamires nuk krijon fragmente verifikues, domethënë njerëzit mund të paraqesin lirisht fragmente fals dhe të pengojnë rikonsolidimin e sekretit të saktë. Një ruajtës armiqësor i fragmenteve me informacion të mjaftueshëm mund të prodhojë madje një fragment tjetër, duke ndryshuar sipërfaqësisht. Ky problem zgjidhet me skema verifikues të ndarjes së sekretit, siç është skema e Feldmanit.

Një tjetër problem është se gjatë e çdo fragmeni është e barabartë me gjatësi e sekretit përkatës, kështu që gjatësi e sekretit përcaktohet lehtësisht. Ky problem zgjidhet me një mbushje triviale sekret me numra të rastit deri në gjatësi të caktuar.

Në fund, është e rëndësishme të theksohet se shqetësimet tona për sigurinë mund të kalojnë përtej vetë skemës. Për aplikacionet reale të kriptografisë, shpesh ka rreziqe të sulmeve nga kanale të jashtme, kur një sulmues përpiqet të nxjerrë informacion të dobishëm nga koha e ekzekutimit të aplikacionit, ndihmësve, dështimeve, etj. Nëse ky është një shqetësim, gjatë zhvillimit duhet të shqyrtohet me kujdes përdorimi i masave mbrojtëse, si funksionet dhe kërkimi me kohë të qëndrueshëm të ekzekutimit, të parandalohet ruajtja e memorjes në disk dhe të merren parasysh një sërë gjërash që kalojnë përtej këtij artikulli.

Demo

Në këtë faqe ka një demo interaktive të skemës së ndarjes së sekretit të Shamir. Demonstra është bërë në bazë të bibliotekës ssss-js, e cila vetë është një port JavaScript i programit të njohur ssss. Vini re se llogaritja e vlerave të mëdha , dhe mund të marrë disa kohë.

Burimi: habr.com