Demagun bankuko ganga bat ziurtatu behar duzun eszenatoki bat. Giltzarik gabe erabat erasoezintzat jotzen da, laneko lehen egunean bertan ematen dizuna. Zure helburua giltza modu seguruan gordetzea da.
Demagun giltza uneoro zurekin edukitzea erabakitzen duzula, behar den moduan biltegiratze sarbidea emanez. Baina azkar konturatuko zara soluzio hori ez dela ondo eskalatzen praktikan, zure presentzia fisikoa beharrezkoa delako biltegia irekitzen duzun bakoitzean. Zer esan zidaten oporretan? Gainera, galdera are beldurgarriagoa da: giltza bakarra galduko bazenu?
Zure oporrak kontuan hartuta, giltzaren kopia bat egitea eta beste langile baten esku uztea erabakitzen duzu. Hala ere, ulertzen duzu hori ere ez dela ideala. Gako kopurua bikoiztuz, giltzak lapurtzeko aukerak ere bikoiztu egiten dituzu.
Etsituta, bikoiztua suntsitu eta jatorrizko gakoa erditik banatzea erabakitzen duzu. Orain, giltza zatiak dituzten konfiantzazko bi pertsona fisikoki egon beharko liratekeela pentsatuko zenuke giltza jasotzeko eta ganga irekitzeko. Horrek esan nahi du lapur batek bi pieza lapurtu behar dituela, eta hori giltza bat lapurtzea baino bi aldiz zaila da. Hala ere, laster konturatzen zara eskema hau ez dela gako bakarra baino askoz hobea, norbaitek gako erdia galtzen badu ezin baita gako osoa berreskuratu.
Arazoa giltza eta sarraila gehigarri batzuekin konpondu daiteke, baina hurbilketa honek azkar eskatuko du ΠΌΠ½ΠΎΠ³ΠΎ giltzak eta sarrailak. Diseinu aproposa giltza partekatzea litzatekeela erabakitzen duzu, segurtasuna pertsona bakar batengan ez egon dadin. Era berean, zati kopuruaren atalase bat egon behar dela ondorioztatzen duzu, zati bat galtzen bada (edo pertsona bat oporretara joaten bada), gako osoa funtzionala izaten jarrai dezan.
Nola partekatu sekretu bat
Gakoen kudeaketa-eskema mota hau Adi Shamirrek pentsatu zuen 1979an bere lana argitaratu zuenean . Artikuluak laburki azaltzen du deiturikoak 
Balio sekretu bat (adibidez, gako kriptografikoa) modu eraginkorrean banatzeko atalase-eskema zatiak. Orduan, noiz eta noiz behintzat - piezak muntatzen dira, erraz berreskuratu dezakezu sekretua .
Segurtasunaren ikuspuntutik, eskema honen propietate garrantzitsu bat da erasotzaileak ez lukeela ezer jakin behar gutxienez ez badu. zatiak. Baita presentzia ere zatiek ez dute inolako informaziorik eman behar. Jabetza honi deitzen diogu segurtasun semantikoa.
Interpolazio polinomiala
Shamir atalasearen eskema kontzeptuaren inguruan eraikia interpolazio polinomiala. Kontzeptu hau ezagutzen ez baduzu, nahiko erraza da. Izan ere, inoiz grafiko batean puntuak marraztu badituzu eta gero lerro edo kurbekin lotu badituzu, dagoeneko erabili duzu!
Bi punturen bidez 2. graduko polinomio kopuru mugagabea marraz dezakezu. Horietatik bakarra aukeratzeko, hirugarren puntu bat behar duzu. Ilustrazioa:
Demagun bat graduko polinomio bat, . Funtzio hau grafiko batean irudikatu nahi baduzu, zenbat puntu behar dituzu? Bada, badakigu zuzena osatzen duen funtzio lineala dela eta, beraz, gutxienez bi puntu behar dituela. Ondoren, kontuan hartu bi graduko funtzio polinomiko bat, . Funtzio koadratikoa da, beraz, gutxienez hiru puntu behar dira grafikoa marrazteko. Zer moduz hiru graduko polinomio bat? Gutxienez lau puntu. Eta abar eta abar.
Propietate honen gauza polita hau da, funtzio polinomialaren gradua eta gutxienez puntuak, funtzio polinomiko honetarako puntu gehigarriak lor ditzakegu. Puntu gehigarri hauen estrapolazioari deitzen diogu interpolazio polinomiala.
Sekretu bat osatzea
Baliteke dagoeneko konturatu zarete hementxe sartzen dela Shamirren eskema burutsua. Esan dezagun gure sekretua - Is . Biratu dezakegu grafikoko puntu batera eta lortu graduko funtzio polinomiko bat , puntu hau betetzen duena. Gogora dezagun hori gure behar diren zatien atalasea izango da, beraz, atalasea hiru zatitan ezartzen badugu, bi graduko funtzio polinomiko bat aukeratu beharko dugu.
Gure polinomioak forma izango du Non ΠΈ β ausaz hautatutako zenbaki oso positiboak. Gradudun polinomio bat eraikitzen ari gara , non koefiziente librea - Hau da gure sekretua , eta ondorengo bakoitzerako terminoak ausaz hautatutako koefiziente positibo bat dago. Jatorrizko adibidera itzuli eta hori suposatzen badugu , orduan funtzioa lortuko dugu .
Puntu honetan konektatuz zatiak sor ditzakegu zenbaki oso bakarrak Non (gure sekretua baita). Adibide honetan, lau zati banatu nahi ditugu hiruko atalasearekin, beraz, ausaz puntuak sortzen ditugu eta bidali puntu bana konfiantzazko lau pertsona bakoitzari, giltzaren zaindari. Jendeari horren berri ere ematen diogu , informazio publikotzat hartzen baita eta berreskuratzeko beharrezkoa baita .
Sekretua berreskuratzen
Dagoeneko eztabaidatu dugu interpolazio polinomialaren kontzeptua eta Shamir-en atalasearen eskemaren azpian dagoena. . Lau administratzaileetatik hiruk berreskuratu nahi dutenean , interpolatu besterik ez dute behar bere puntu bereziekin. Horretarako, puntuak zehaztu ditzakete eta kalkulatu Lagrange-ren interpolazio-polinomioa honako formula hau erabiliz. Programazioa matematika baino argiagoa bada, pi operatzailea da funtsean for, emaitza guztiak biderkatzen dituena, eta sigma da for, dena batzen duena.
Egun Honela ebatzi dezakegu eta gure jatorrizko funtzio polinomikoa itzul dezakegu:
Hori dakigunez , berreskuratzea besterik gabe egin:
Zenbaki osoen aritmetika segurua erabiltzea
Shamirren oinarrizko ideia arrakastaz aplikatu dugun arren , orain arte baztertu dugun arazo batekin geratzen gara. Gure funtzio polinomikoak zenbaki oso aritmetika segurua erabiltzen du. Kontuan izan erasotzaile batek gure funtzioaren grafikoan lortzen duen puntu gehigarri bakoitzeko, beste puntuetarako aukera gutxiago daudela. Hori zure begiekin ikus dezakezu funtzio polinomiko baterako puntu kopuru handiagoa marrazten duzunean osoko aritmetika erabiliz. Hau gure segurtasun-helburuarentzat kontrakoa da, erasotzaileak ez duelako ezer jakin behar izan arte, gutxienez zatiak.
Zenbaki osoko zirkuitu aritmetikoa zein ahula den erakusteko, kontuan hartu erasotzaileak bi puntu lortu dituen eszenatoki bat. eta informazio publiko hori badaki . Informazio horretatik ondoriozta dezake , biren berdina, eta sartu balio ezagunak formulan ΠΈ .
Erasotzaileak aurki dezake orduan , zenbatzen :
Definitu dugunez ausaz hautatutako zenbaki oso positibo gisa, posible kopuru mugatu bat dago . Informazio hori erabiliz, erasotzaile batek ondorioztatu dezake , 5 baino gehiago edozer balioko baitu negatiboa. Hau egia bihurtzen da zehaztu dugunetik
Erasotzaileak balio posibleak kalkula ditzake orduan ordezkatuz Π² :
Aukera mugatuekin argi geratzen da zein erraza den balioak hautatzea eta egiaztatzea . Bost aukera baino ez daude hemen.
Aritmetika oso ez seguruarekin arazoa ebaztea
Ahultasun hori kentzeko, Shamirrek aritmetika modularra erabiltzea proposatzen du, ordezkatuz on Non ΠΈ β Zenbaki lehen guztien multzoa.
Gogora dezagun azkar nola funtzionatzen duen aritmetika modularra. Eskudun erlojua kontzeptu ezaguna da. Erloju bat erabiltzen du, alegia . Orduko orratza hamabiak igaro bezain pronto, batera itzultzen da. Sistema honen propietate interesgarri bat zera da: erlojuari erreparatuta ezin dugula ondorioztatu orduko orratzak zenbat bira eman dituen. Hala ere, badakigu orduen orratza lau aldiz 12 igaro dela, guztiz zehaztu dezakegu zenbat ordu igaro diren formula sinple baten bidez. Non gure zatitzailea da (hemen ), koefizientea da (zatitzailea zenbat aldiz sartzen den jatorrizko zenbakian hondarrik gabe, hemen ), eta hondarra da, normalean modulo operadorearen deia itzultzen duena (hemen ). Balio hauek guztiak ezagutzeak ekuazioa ebazteko aukera ematen digu , baina koefizientea galduz gero, ezingo dugu inoiz jatorrizko balioa berreskuratu.
Honek gure eskemaren segurtasuna nola hobetzen duen froga dezakegu eskema gure aurreko adibideari aplikatuz eta erabiliz . Gure funtzio polinomiko berria , eta puntu berriak . Orain gakoen arduradunek berriro ere erabil dezakete interpolazio polinomiala gure funtzioa berreraikitzeko, oraingoan batuketa eta biderketa eragiketak modulo murrizketarekin batera joan behar dira. (adibidez, ).
Adibide berri hau erabiliz, demagun erasotzaileak puntu berri horietako bi ikasi zituela, , eta informazio publikoa . Oraingoan, erasotzaileak, daukan informazio guztian oinarrituta, honako funtzio hauek ateratzen ditu, non zenbaki oso positibo guztien multzoa da, eta modulu-koefizientea adierazten du .
Orain gure erasotzaileak berriro aurkitzen du , kalkulatzen :
Orduan berriro saiatzen da ordezkatuz Π² :
Oraingoan arazo larri bat dauka. Formularen balioak falta dira , ΠΈ . Aldagai horien konbinazio kopuru infinitua dagoenez, ezin du informazio gehigarririk lortu.
Segurtasun-gogoetak
Shamirren sekretua partekatzeko eskemak iradokitzen du segurtasuna informazioaren teoriaren ikuspuntutik. Horrek esan nahi du matematika erresistentea dela konputazio ahalmen mugagabea duen erasotzaile baten aurka ere. Hala ere, zirkuituak hainbat arazo ezagun ditu oraindik.
Adibidez, Shamirren eskemak ez du sortzen egiaztatu beharreko zatiak, hau da, jendeak libreki aurkez ditzakete zati faltsuak eta sekretu zuzena berreskuratzea oztopatu. Informazio nahikoa duen zatien zaintzaile etsai batek beste zati bat ere sor dezake aldatuz zure diskrezioan. Arazo hau erabiliz konpontzen da sekretuak partekatzeko eskemak egiaztagarriak, esate baterako, Feldmanen eskema.
Beste arazo bat edozein zatiren luzera dagokion sekretuaren luzera berdina dela da, beraz, sekretuaren luzera erraza da zehazten. Arazo hau hutsalez konpondu daiteke betegarria luzera finkora arteko zenbaki arbitrarioekin sekretua.
Azkenik, garrantzitsua da gure segurtasun kezkak diseinutik haratago zabal daitezkeela. Mundu errealeko aplikazio kriptografikoetarako, sarritan alboko kanaleko erasoen mehatxua egon ohi da, non erasotzaileak aplikazioen exekuzio denboratik, cachetik, hutsegiteetatik eta abar informazio erabilgarria ateratzen saiatzen den. Hau kezkagarria bada, garapenean arreta handiz hartu behar da kontuan babes-neurriak erabiltzea, hala nola funtzioak eta etengabeko bilaketak, memoria diskoan gordetzea saihestea eta artikulu honen esparrutik kanpo dauden beste hainbat kontu.
demo
On Shamirren sekretua partekatzeko eskemaren erakustaldi interaktibo bat dago. Liburutegian oinarritutako erakustaldia , programa ezagunaren JavaScript ataka dena . Kontuan izan balio handiak kalkulatuz , ΠΈ denbora pixka bat behar izan dezake.
Iturria: www.habr.com