Beskôgje in senario wêr't jo in bankferwulft moatte befeiligje. It wurdt beskôge as absolút impregnable sûnder in kaai, dy't jo krije op 'e earste dei fan it wurk. Jo doel is om de kaai feilich op te slaan.
Litte wy sizze dat jo beslute om de kaai altyd by jo te hâlden, en jouwe tagong ta de opslach as nedich. Mar jo sille gau realisearje dat sa'n oplossing yn 'e praktyk net goed skaalber is, om't jo fysike oanwêzigens elke kear as jo de opslach iepenje is fereaske. Hoe sit it mei de fakânsje dy't jo tasein wiene? Dêrneist is de fraach noch skrikliker: wat as jo jo ienige kaai kwytrekke?
Mei jo fakânsje yn gedachten, beslute jo om in kopy fan 'e kaai te meitsjen en it oan in oare meiwurker ta te fertrouwen. Jo begripe lykwols dat dit ek net ideaal is. Troch it ferdûbeljen fan it oantal kaaien ferdûbelje jo ek de kâns op kaaistellerij.
Yn wanhoop ferneatigje jo it duplikaat en beslute om de orizjinele kaai yn 'e helte te splitsen. No soene jo tinke dat twa fertroude minsken mei kaaifragminten fysyk oanwêzich wêze moatte om de kaai te sammeljen en de ferwulft te iepenjen. Dit betsjut dat in dief twa stikken stelle moat, wat twa kear sa dreech is as ien kaai te stellen. Jo realisearje lykwols gau dat dit skema net folle better is as mar ien kaai, want as immen in heale kaai ferliest, kin de folsleine kaai net weromhelle wurde.
It probleem kin wurde oplost mei in rige fan ekstra kaaien en slûzen, mar dizze oanpak sil fluch fereaskje много kaaien en slûzen. Jo beslute dat it ideale ûntwerp soe wêze om de kaai te dielen, sadat feiligens net folslein op ien persoan fertrout. Jo konkludearje ek dat der wat drompel wêze moat foar it oantal fragminten, sadat as ien fragmint ferlern giet (of as in persoan op fakânsje giet), de hiele kaai funksjoneel bliuwt.
Hoe in geheim te dielen
Dit soarte fan kaaibehearskema waard tocht troch Adi Shamir yn 1979 doe't hy syn wurk publisearre . It artikel koart ferklearret de saneamde 
drompelskema foar it effisjint dielen fan in geheime wearde (lykas in kryptografyske kaai) yn dielen. Dan, wannear en allinnich wannear teminsten fan dielen wurde gearstald, kinne jo maklik weromsette it geheim .
Ut in feiligens eachpunt, in wichtige eigenskip fan dit skema is dat de oanfaller moat net witte absolút neat útsein as hy hat op syn minst dielen. Sels de oanwêzigens dielen moatte gjin ynformaasje jaan. Wy neame dit eigendom semantyske feiligens.
Polynomiale ynterpolaasje
Shamir drompelskema boud om it konsept polynomiale ynterpolaasje. As jo net bekend binne mei dit konsept, is it eins frij simpel. Yn feite, as jo oait punten op in grafyk tekene hawwe en se dan ferbûn hawwe mei rigels of bochten, hawwe jo it al brûkt!
Troch twa punten kinne jo in ûnbeheind oantal polynomen fan graad 2 tekenje. Om de iennichste fan har te kiezen, hawwe jo in tredde punt nedich. Yllustraasje:
Beskôgje in polynoom mei graad ien, . As jo dizze funksje op in grafyk plotje wolle, hoefolle punten hawwe jo dan nedich? No, wy witte dat dit in lineêre funksje is dy't in line foarmet en dus hat it op syn minst twa punten nedich. Besjoch dan in polynomiale funksje mei graad twa, . Dit is in kwadratyske funksje, sadat op syn minst trije punten nedich binne om de grafyk te plotjen. Hoe sit it mei in polynoom mei graad trije? Op syn minst fjouwer punten. En sa fierder.
De echt cool ding oer dit pân is dat, sjoen de graad fan de polynomiale funksje en op syn minst punten, kinne wy ekstra punten foar dizze polynomiale funksje ôfliede. De ekstrapolaasje fan dizze ekstra punten neame wy polynomiale ynterpolaasje.
In geheim opmeitsje
Jo hawwe miskien al realisearre dat dit is wêr't Shamir's tûke skema yn spiel komt. Litte wy ús geheim sizze Is . Wy kinne draaie nei in punt op 'e grafyk en komme mei in polynomiale funksje mei graad , dy't oan dit punt foldocht. Lit ús jo dat herinnerje sil ús drompel wêze fan fereaske fragminten, dus as wy de drompel op trije fragminten sette, moatte wy in polynomiale funksje kieze mei graad twa.
Us polynoom sil de foarm hawwe wêr и - willekeurich selektearre positive hiele getallen. Wy konstruearje gewoan in polynoom mei graad , dêr't de frije koeffisient - Dit is ús geheim , en foar elk fan 'e folgjende termen is der in willekeurich selektearre positive koeffizient. As wy weromgean nei it oarspronklike foarbyld en oannimme dat , dan krije wy de funksje .
Op dit punt kinne wy fragminten generearje troch te ferbinen unike integers yn wêr (omdat it ús geheim is). Yn dit foarbyld wolle wy fjouwer fragminten ferspriede mei in drompel fan trije, sadat wy willekeurich punten generearje en stjoer ien punt nei elk fan 'e fjouwer fertroude minsken, de hoeders fan' e kaai. Dat litte wy minsken ek witte , sûnt dit wurdt beskôge as iepenbiere ynformaasje en is nedich foar herstel .
It geheim weromhelje
Wy hawwe it konsept fan polynomiale ynterpolaasje al besprutsen en hoe't it it drompelskema fan Shamir leit . Wannear't trije fan 'e fjouwer trustees wolle restaurearje , se moatte allinich ynterpolearje mei syn eigen unike punten. Om dit te dwaan, kinne se har punten bepale en berekkenje de Lagrange-ynterpolaasje polynoom mei de folgjende formule. As programmearring foar jo dúdliker is dan wiskunde, dan is pi yn wêzen in operator for, dy't fermannichfâldigje alle resultaten, en sigma is for, dy't alles optelt.
at wy kinne it sa oplosse en ús oarspronklike polynomiale funksje weromjaan:
Sûnt wy witte dat , herstel gewoan dien:
Mei help fan ûnfeilige integer arithmetic
Hoewol wy it basisidee fan Shamir mei súkses hawwe tapast , wy sitte oer mei in probleem dat wy oant no ta hawwe negearre. Us polynomiale funksje brûkt ûnfeilige arithmetika. Tink derom dat foar elk ekstra punt dat in oanfaller krijt op 'e grafyk fan ús funksje, d'r minder mooglikheden binne foar oare punten. Jo kinne dit mei jo eigen eagen sjen as jo in tanimmend oantal punten foar in polynomiale funksje plotje mei help fan heule getal arithmetic. Dit is kontraproduktyf foar ús ferklearre feiligensdoel, om't de oanfaller hielendal neat moat witte oant se op syn minst hawwe fragminten.
Om oan te toanen hoe swak it arithmetyske sirkwy fan in heule getal is, beskôgje in senario wêryn in oanfaller twa punten krige en wit iepenbiere ynformaasje dat . Ut dizze ynformaasje kin hy ôfliede , gelyk oan twa, en plug de bekende wearden yn 'e formule и .
De oanfaller kin dan fine , telle :
Sûnt wy hawwe definiearre as willekeurich selektearre positive hiele getallen, der binne in beheind oantal mooglike . Mei dizze ynformaasje kin in oanfaller ôfliede , sûnt alles grutter dan 5 sil dwaan negatyf. Dit blykt wier te wêzen sûnt wy hawwe bepaald
De oanfaller kin dan de mooglike wearden berekkenje , ferfanging в :
Mei beheinde opsjes foar it wurdt dúdlik hoe maklik it is om de wearden te selektearjen en te kontrolearjen . D'r binne hjir mar fiif opsjes.
Oplosse it probleem mei ûnfeilige integer arithmetic
Om dizze kwetsberens te eliminearjen, suggerearret Shamir it brûken fan modulêre arithmetyk, ferfangen op wêr и - de set fan alle priemgetallen.
Lit ús gau ûnthâlde hoe't modulêre rekkenjen wurket. In klok mei hannen is in fertroud konsept. Se brûkt in horloazje dat wol . Sadree't de oerenwizer tolve foarby giet, giet it werom nei ien. In nijsgjirrige eigenskip fan dit systeem is dat gewoan troch te sjen nei de klok, wy kinne net ôfliede hoefolle revolúsjes de oere hân hat makke. As wy lykwols witte dat de oerehân fjouwer kear 12 foarby is, kinne wy it oantal oeren folslein bepale dat is ferrûn mei in ienfâldige formule wêr is ús divisor (hjir ), is de koeffizient (hoefolle kearen giet de divisor yn it oarspronklike getal sûnder in rest, hjir ), en is de rest, dy't normaal in modulo-operatoroprop werombringt (hjir ). Troch al dizze wearden te kennen kinne wy de fergeliking foar oplosse , mar as wy misse de koeffizient, wy sille nea by steat wêze om te herstellen de oarspronklike wearde.
Wy kinne demonstrearje hoe't dit de feiligens fan ús skema ferbettert troch it skema oan te passen op ús foarige foarbyld en te brûken . Us nije polynomiale funksje , en de nije punten . No kinne de kaaihâlders wer polynomiale ynterpolaasje brûke om ús funksje te rekonstruearjen, allinich dizze kear moatte de optel- en fermannichfâldigje operaasjes begelaat wurde troch modulo-reduksje (bgl ).
Lit ús mei dit nije foarbyld oannimme dat de oanfaller twa fan dizze nije punten learde, , en iepenbiere ynformaasje . Dizze kear, de oanfaller, basearre op alle ynformaasje dy't hy hat, útfiert de folgjende funksjes, wêr is de set fan alle positive hiele getallen, en stelt de moduluskoëffisjint foar .
No fynt ús oanfaller wer , berekkenjen :
Dan besiket er it nochris , ferfanging в :
Dizze kear hat hy in serieus probleem. Formule ûntbrekkende wearden , и . Om't der in ûneinich oantal kombinaasjes fan dizze fariabelen binne, kin hy gjin ekstra ynformaasje krije.
Feiligens oerwagings
Shamir's geheime dielenskema suggerearret feiligens út it eachpunt fan ynformaasje teory. Dit betsjut dat de wiskunde resistint is sels tsjin in oanfaller mei ûnbeheinde rekkenkrêft. It circuit befettet lykwols noch ferskate bekende problemen.
Bygelyks, Shamir's skema makket net fragminten wurde kontrolearre, dat is, minsken kinne frij presintearje falske fragminten en bemuoie mei it herstel fan it juste geheim. In fijannige fragminthâlder mei genôch ynformaasje koe sels in oar fragmint produsearje troch te feroarjen nei eigen goedtinken. Dit probleem wurdt oplost mei help fan ferifieare geheime dielenskema's, lykas Feldman's skema.
In oar probleem is dat de lingte fan elk fragmint gelyk is oan de lingte fan it oerienkommende geheim, sadat de lingte fan it geheim maklik te bepalen is. Dit probleem kin wurde oplost troch triviale padding geheim mei willekeurige nûmers oant in fêste lingte.
Uteinlik is it wichtich om te notearjen dat ús feiligensproblemen fierder kinne útwreidzje dan it ûntwerp sels. Foar kryptografyske tapassingen yn 'e echte wrâld is d'r faaks de bedriging fan oanfallen op side-kanaal wêr't in oanfaller besiket nuttige ynformaasje te ekstrahearjen fan útfieringstiid fan applikaasjes, caching, crashes, ensfh. As dit in soarch is, moatte jo yn 'e ûntwikkeling soarchfâldich beskôgje om beskermjende maatregels te brûken lykas funksjes en opsykjen yn konstante tiid, foarkommen dat ûnthâld wurdt bewarre op skiif, en in oantal oare oerwagings dy't bûten it berik fan dit artikel lizze.
Demo
op D'r is in ynteraktive demonstraasje fan Shamir's geheime dielingsskema. Demonstraasje basearre op de biblioteek , dy't sels in JavaScript-poarte is fan it populêre programma . Tink derom dat it berekkenjen fan grutte wearden , и kin wat tiid duorje.
Boarne: www.habr.com