Íhugaðu atburðarás þar sem þú þarft að tryggja bankahólfi. Það er talið algerlega ómögulegt án lykils, sem þú færð strax á fyrsta vinnudegi. Markmið þitt er að geyma lykilinn á öruggan hátt.

Segjum að þú ákveður að hafa lykilinn alltaf hjá þér og veita aðgang að geymslunni eftir þörfum. En þú munt fljótt átta þig á því að slík lausn mælist ekki vel í reynd, vegna þess að líkamleg nærvera þín er nauðsynleg í hvert skipti sem þú opnar geymsluna. Hvað með fríið sem þér var lofað? Að auki er spurningin enn ógnvekjandi: hvað ef þú týnir eina lyklinum þínum?

Með fríið þitt í huga ákveður þú að taka afrit af lyklinum og fela það öðrum starfsmanni. Hins vegar skilurðu að þetta er ekki tilvalið heldur. Með því að tvöfalda fjölda lykla tvöfaldarðu líka líkurnar á lyklaþjófnaði.

Í örvæntingu eyðir þú afritinu og ákveður að skipta upprunalega lyklinum í tvennt. Nú gætirðu haldið að tveir traustir einstaklingar með lykilbrot þyrftu að vera líkamlega til staðar til að sækja lykilinn og opna hvelfinguna. Þetta þýðir að þjófur þarf að stela tveimur stykkjum, sem er tvöfalt erfiðara en að stela einum lykli. Hins vegar áttarðu þig fljótt á því að þetta kerfi er ekki mikið betra en bara einn lykill, því ef einhver týnir hálfum lykli er ekki hægt að endurheimta allan lykilinn.

Vandamálið er hægt að leysa með röð aukalykla og læsinga, en þessi aðferð mun fljótt krefjast много lykla og læsa. Þú ákveður að tilvalin hönnun væri að deila lyklinum þannig að öryggi byggist ekki algjörlega á einum aðila. Þú ályktar líka að það verði að vera einhver þröskuldur fyrir fjölda brota þannig að ef eitt brot týnist (eða ef einstaklingur fer í frí) haldist allur lykillinn virkur.

Hvernig á að deila leyndarmáli

Þessa tegund lykilstjórnunarkerfis hugsaði Adi Shamir um árið 1979 þegar hann gaf út verk sín „Hvernig á að deila leyndarmáli“. Greinin útskýrir í stuttu máli svokallaða þröskuldskerfi til að skipta leynigildi (svo sem dulmálslykli) á skilvirkan hátt í hlutar. Þá, hvenær og aðeins þegar að minnsta kosti á hlutar eru settir saman, þú getur auðveldlega endurheimt leyndarmálið .

Frá öryggissjónarmiði er mikilvægur eiginleiki þessa kerfis að árásarmaðurinn ætti ekki að vita nákvæmlega neitt nema hann hafi a.m.k. hlutar. Jafnvel nærveran hlutar ættu ekki að veita neinar upplýsingar. Við köllum þetta eign merkingarfræðilegt öryggi.

Margliðu innskot

Shamir þröskuldskerfi byggt í kringum hugmyndina margliða innskot. Ef þú ert ekki kunnugur þessu hugtaki, þá er það í raun frekar einfalt. Reyndar, ef þú hefur einhvern tíma teiknað punkta á línuriti og síðan tengt þá með línum eða línum, hefurðu þegar notað það!

Í gegnum tvo punkta er hægt að draga ótakmarkaðan fjölda margliða af 2. gráðu. Til að velja eina úr þeim þarftu þriðja punktinn. Myndskreyting: Wikipedia

Lítum á margliðu með gráðu eitt, . Ef þú vilt teikna þessa aðgerð á línurit, hversu marga punkta þarftu? Jæja, við vitum að þetta er línulegt fall sem myndar línu og þarf því að minnsta kosti tvo punkta. Næst skaltu íhuga margliðufall með gráðu tvö, . Þetta er ferningsfall, þannig að það þarf að minnsta kosti þrjá punkta til að teikna línuritið. Hvað með margliðu með gráðu þrjú? Að minnsta kosti fjögur stig. Og svo framvegis og svo framvegis.

Það sem er mjög flott við þessa eiginleika er að miðað við gráðu margliðufallsins og amk stig, getum við dregið til viðbótar stig fyrir þetta margliðufall. Við köllum framreikning þessara viðbótarpunkta margliða innskot.

Að búa til leyndarmál

Þú hefur kannski þegar áttað þig á því að hér kemur hið snjalla kerfi Shamirs við sögu. Segjum leyndarmál okkar - Er . Við getum snúið okkur að punkti á línuritinu og komdu með margliðufall með gráðu , sem fullnægir þessu atriði. Við skulum minna þig á það verður þröskuldur okkar á nauðsynlegum brotum, þannig að ef við setjum þröskuldinn á þrjú brot, verðum við að velja margliðufall með gráðu tvö.

Margliðan okkar mun hafa formið hvar и — jákvæðar heiltölur sem valdar eru af handahófi. Við erum bara að smíða margliðu með gráðu , þar sem frjáls stuðullinn  - Þetta er leyndarmál okkar , og fyrir hverja þeirra síðari hugtök þar er tilviljunarkenndur jákvæður stuðull. Ef við snúum okkur aftur að upprunalega dæminu og gerum ráð fyrir því , þá fáum við fallið .

Á þessum tímapunkti getum við búið til brot með því að tengja einstakar heiltölur í hvar (vegna þess að það er leyndarmál okkar). Í þessu dæmi viljum við dreifa fjórum brotum með þröskuldinn þriggja, þannig að við búum til stig af handahófi og sendu eitt stig til hvers hinna fjögurra traustu manna, vörsluaðila lyklanna. Við látum fólk líka vita það , þar sem þetta teljast opinberar upplýsingar og eru nauðsynlegar til endurheimtar .

Að endurheimta leyndarmálið

Við höfum nú þegar fjallað um hugtakið margliða innskot og hvernig það liggur til grundvallar þröskuldskerfi Shamirs . Þegar einhverjir þrír af fjórum fjárvörsluaðilum vilja endurheimta , þeir þurfa aðeins að interpolera með sína einstöku punkta. Til að gera þetta geta þeir ákvarðað stig sín og reiknaðu Lagrange innskotsmargliðuna með því að nota eftirfarandi formúlu. Ef forritun er þér skýrari en stærðfræði, þá er pi í raun rekstraraðili for, sem margfaldar allar niðurstöður, og sigma er for, sem leggur allt saman.

á við getum leyst það svona og skilað upprunalegu margliðufallinu okkar:

Þar sem við vitum það , bata gert einfaldlega:

Notar óörugga heiltölureikning

Þó að við höfum beitt grunnhugmynd Shamirs með góðum árangri , við sitjum eftir með vandamál sem við höfum hunsað fram að þessu. Margliðufallið okkar notar óörugga heiltölureikning. Athugaðu að fyrir hvert viðbótarstig sem árásarmaður fær á línuriti fallsins okkar eru færri möguleikar á öðrum stigum. Þú getur séð þetta með eigin augum þegar þú teiknar upp aukinn fjölda punkta fyrir margliðufall með heiltölureikningi. Þetta stangast á við yfirlýst öryggismarkmið okkar, því árásarmaðurinn ætti að vita nákvæmlega ekkert fyrr en hann hefur að minnsta kosti brot.

Til að sýna fram á hversu veik heiltölu reiknirásin er, skoðaðu atburðarás þar sem árásarmaður fékk tvö stig og veit opinberar upplýsingar sem . Af þessum upplýsingum getur hann dregið þá ályktun , jafnt og tveimur, og settu þekkt gildi inn í formúluna и .

Árásarmaðurinn getur þá fundið , telja :

Þar sem við höfum skilgreint sem af handahófi valdar jákvæðar heiltölur, það er takmarkaður fjöldi mögulegra . Með því að nota þessar upplýsingar getur árásarmaður ályktað , þar sem allt sem er meira en 5 dugar neikvæð. Þetta reynist rétt þar sem við höfum ákveðið

Árásarmaðurinn getur síðan reiknað út möguleg gildi skipta um в :

Með takmarkaða möguleika fyrir kemur í ljós hversu auðvelt er að velja og athuga gildin . Hér eru aðeins fimm valkostir.

Að leysa vandamálið með óöruggum heiltölureikningi

Til að útrýma þessum varnarleysi, stingur Shamir upp á að nota mátreikning, skipta út á hvar и — mengi allra frumtalna.

Við skulum fljótt muna hvernig einingareikningur virkar. Klukka með vísum er kunnuglegt hugtak. Hún notar úr semsagt . Um leið og klukkuvísan er liðin yfir tólf fer hún aftur í eitt. Áhugaverður eiginleiki þessa kerfis er að einfaldlega með því að horfa á klukkuna getum við ekki ályktað hversu margar snúningar klukkuvísinn hefur gert. Hins vegar, ef við vitum að tímavísan hefur farið framhjá 12 fjórum sinnum, getum við alveg ákvarðað fjölda klukkustunda sem hafa liðið með einfaldri formúlu hvar  er deilirinn okkar (hér ),  er stuðullinn (hversu oft deilirinn fer inn í upprunalegu töluna án afgangs, hér ), og  er afgangurinn, sem venjulega skilar modulo símasímtali (hér ). Að þekkja öll þessi gildi gerir okkur kleift að leysa jöfnuna fyrir , en ef við missum af stuðlinum, munum við aldrei geta endurheimt upprunalega gildið.

Við getum sýnt fram á hvernig þetta bætir öryggi kerfisins okkar með því að nota kerfið á fyrra dæmi okkar og nota . Nýja margliðafallið okkar , og nýju atriðin . Nú geta lykilverðirnir enn og aftur notað margliða innskot til að endurbyggja fallið okkar, aðeins í þetta skiptið verður samlagningar- og margföldunaraðgerðum að fylgja stuðull minnkun (td ).

Með því að nota þetta nýja dæmi skulum við gera ráð fyrir að árásarmaðurinn hafi lært tvo af þessum nýju atriðum, , og opinberar upplýsingar . Að þessu sinni framleiðir árásarmaðurinn, byggt á öllum þeim upplýsingum sem hann hefur, eftirfarandi aðgerðir, þar sem  er mengi allra jákvæðra heiltalna, og táknar stuðullinn .

Nú finnur árásarmaðurinn okkar aftur , reikna :

Svo reynir hann aftur skipta um в :

Að þessu sinni á hann við alvarleg vandamál að etja. Formúlu vantar gildi , и . Þar sem það eru til óendanlega margir samsetningar þessara breyta getur hann ekki fengið neinar viðbótarupplýsingar.

Öryggissjónarmið

Leynilegt deilingarkerfi Shamirs bendir til öryggi frá sjónarhóli upplýsingafræðinnar. Þetta þýðir að stærðfræðin er ónæm jafnvel gegn árásarmanni með ótakmarkaða tölvugetu. Hins vegar inniheldur hringrásin enn nokkur þekkt vandamál.

Til dæmis skapar áætlun Shamirs ekki brot sem á að athuga, það er, fólk getur frjálslega framvísað fölsuðum brotum og truflað endurheimt rétta leyndarmálsins. Fjandsamlegur brotavörður með nægar upplýsingar gæti jafnvel búið til annað brot með því að breyta að eigin geðþótta. Þetta vandamál er leyst með því að nota sannanlegt leyndarmál samnýtingarkerfi, eins og áætlun Feldmans.

Annað vandamál er að lengd hvers brots er jöfn lengd samsvarandi leyndarmáls, þannig að lengd leyndarmálsins er auðvelt að ákvarða. Þetta vandamál er hægt að leysa með léttvægi bólstrun leyndarmál með handahófskenndum tölum upp að fastri lengd.

Að lokum er mikilvægt að hafa í huga að öryggisáhyggjur okkar kunna að ná út fyrir hönnunina sjálfa. Fyrir raunveruleg dulritunarforrit er oft hætta á árásum á hliðarrás þar sem árásarmaður reynir að draga fram gagnlegar upplýsingar úr framkvæmdartíma forrita, skyndiminni, hrun osfrv. Ef þetta er áhyggjuefni, ætti að íhuga vandlega við þróun að nota verndarráðstafanir eins og aðgerðir og stöðugar uppflettingar, koma í veg fyrir að minni sé vistað á diski og fjölda annarra atriða sem falla utan gildissviðs þessarar greinar.

Демо

Á Þessi síða Það er gagnvirk sýning á leyndarmálsmiðlun Shamirs. Sýning byggð á bókasafninu ssss-js, sem sjálft er JavaScript tengi hins vinsæla forrits ssss. Athugaðu að reikna stór gildi , и getur tekið smá tíma.

Heimild: www.habr.com