Ikkunsidra xenarju fejn għandek bżonn tiżgura kaxxa-forti bankarja. Huwa meqjus assolutament impregnabbli mingħajr ċavetta, li tingħata fl-ewwel jum tax-xogħol. L-għan tiegħek huwa li taħżen b'mod sigur iċ-ċavetta.
Ejja ngħidu li tiddeċiedi li żżomm iċ-ċavetta miegħek il-ħin kollu, billi tipprovdi aċċess għall-ħażna kif meħtieġ. Imma malajr tirrealizza li soluzzjoni bħal din ma tiskalax sew fil-prattika, minħabba li l-preżenza fiżika tiegħek hija meħtieġa kull darba li tiftaħ il-ħażna. Xi ngħidu għall-vaganza li ġejt imwiegħda? Barra minn hekk, il-mistoqsija hija saħansitra aktar tal-biża ': x'jiġri jekk tlift l-unika ċavetta tiegħek?
Bil-vaganza tiegħek f'moħħha, tiddeċiedi li tagħmel kopja taċ-ċavetta u tafdaha f'idejn impjegat ieħor. Madankollu, inti tifhem li dan mhux ideali lanqas. Billi tirdoppja n-numru ta 'ċwievet, tirdoppja wkoll iċ-ċansijiet ta' serq taċ-ċwievet.
Fid-disprazzjoni, teqred id-duplikat u tiddeċiedi li taqsam iċ-ċavetta oriġinali bin-nofs. Issa, inti taħseb li żewġ persuni fdati bi frammenti ewlenin ikollhom ikunu fiżikament preżenti biex jiġbru ċ-ċavetta u tiftaħ il-kaxxa-forti. Dan ifisser li ħalliel jeħtieġ li jisraq żewġ biċċiet, li huwa darbtejn aktar diffiċli milli jisraq ċavetta waħda. Madankollu, malajr tirrealizza li din l-iskema mhix wisq aħjar minn ċavetta waħda biss, għax jekk xi ħadd jitlef nofs ċavetta, iċ-ċavetta sħiħa ma tistax tiġi rkuprata.
Il-problema tista 'tiġi solvuta b'serje ta' ċwievet u serraturi addizzjonali, iżda dan l-approċċ se jirrikjedi malajr много ċwievet u serraturi. Inti tiddeċiedi li d-disinn ideali jkun li taqsam iċ-ċavetta sabiex is-sigurtà ma tiddependix kompletament fuq persuna waħda. Tikkonkludi wkoll li għandu jkun hemm xi limitu għan-numru ta 'frammenti sabiex jekk tintilef framment wieħed (jew jekk persuna tmur vaganza), iċ-ċavetta kollha tibqa' funzjonali.
Kif taqsam sigriet
Din it-tip ta 'skema ta' ġestjoni ewlenin kienet maħsuba minn Adi Shamir fl-1979 meta ppubblika x-xogħol tiegħu . L-artiklu jispjega fil-qosor l-hekk imsejħa 
skema ta' limitu għad-diviżjoni effiċjenti ta' valur sigriet (bħal ċavetta kriptografika) fi partijiet. Imbagħad, meta u biss meta mill-inqas ta ' partijiet huma mmuntati, tista 'faċilment tirrestawra s-sigriet .
Mil-lat tas-sigurtà, proprjetà importanti ta’ din l-iskema hija li l-attakkant m’għandu jkun jaf assolutament xejn sakemm ma jkollux tal-anqas partijiet. Anke l-preżenza partijiet m'għandhomx jipprovdu l-ebda informazzjoni. Aħna nsejħu din il-proprjetà sigurtà semantika.
Interpolazzjoni polinomjali
Skema ta' limitu ta' Shamir mibnija madwar il-kunċett interpolazzjoni polinomjali. Jekk m'intix familjari ma 'dan il-kunċett, fil-fatt huwa pjuttost sempliċi. Fil-fatt, jekk qatt ġibt punti fuq grafika u mbagħad qabbadhom b'linji jew kurvi, diġà użajtu!
Permezz ta 'żewġ punti tista' tiġbed numru illimitat ta 'polinomji ta' grad 2. Biex tagħżel l-uniku wieħed minnhom, għandek bżonn it-tielet punt. Illustrazzjoni:
Ikkunsidra polinomju bi grad wieħed, . Jekk trid tpinġi din il-funzjoni fuq graff, kemm għandek bżonn punti? Ukoll, nafu li din hija funzjoni lineari li tifforma linja u għalhekk teħtieġ mill-inqas żewġ punti. Sussegwentement, ikkunsidra funzjoni polinomjali bi grad tnejn, . Din hija funzjoni kwadratika, għalhekk mill-inqas tliet punti huma meħtieġa biex jitpinġu l-graff. Kif dwar polinomju bi grad tlieta? Mill-inqas erba’ punti. U l-bqija u l-bqija.
Il-ħaġa verament jibred dwar din il-proprjetà hija li, minħabba l-grad tal-funzjoni polinomjali u għall-inqas punti, nistgħu niksbu punti addizzjonali għal din il-funzjoni polinomjali. Aħna nsejħu l-estrapolazzjoni ta 'dawn il-punti addizzjonali interpolazzjoni polinomjali.
Tagħmel sigriet
Forsi diġà rrealizzajt li hawnhekk tidħol l-iskema għaqlija ta’ Shamir. Ejja ngħidu s-sigriet tagħna - dan hu . Nistgħu nduru sa punt fuq il-graff u toħroġ b'funzjoni polinomjali bi grad , li tissodisfa dan il-punt. Ejja nfakkru li se jkun il-limitu tagħna ta 'frammenti meħtieġa, għalhekk jekk nissettjaw il-limitu għal tliet frammenti, irridu nagħżlu funzjoni polinomjali bi grad tnejn.
Il-polinomju tagħna se jkollu l-forma fejn и — numri interi pożittivi magħżula bl-addoċċ. Aħna biss nibnu polinomju bi grad , fejn il-koeffiċjent ħieles - Dan huwa s-sigriet tagħna , u għal kull wieħed minn dawk sussegwenti termini hemm koeffiċjent pożittiv magħżul b'mod każwali. Jekk nerġgħu lura għall-eżempju oriġinali u nassumu li , allura nġibu l-funzjoni .
F'dan il-punt nistgħu niġġeneraw frammenti billi nikkollegaw interi uniċi fi fejn (għax huwa s-sigriet tagħna). F'dan l-eżempju, irridu nqassmu erba 'frammenti b'limitu ta' tlieta, għalhekk niġġeneraw punti b'mod każwali u ibgħat punt wieħed lil kull waħda mill-erba 'persuni fdati, il-kustodji taċ-ċavetta. Aħna wkoll inħallu lin-nies jafu , peress li din hija meqjusa bħala informazzjoni pubblika u hija meħtieġa għall-irkupru .
Jirkupraw is-sigriet
Diġà ddiskutejna l-kunċett tal-interpolazzjoni polinomjali u kif hija bbażata fuq l-iskema tal-limitu ta’ Shamir . Meta xi tlieta mill-erba’ trustees iridu jirrestawraw , għandhom bżonn biss li jinterpolaw bil-punti uniċi tagħha stess. Biex jagħmlu dan, jistgħu jiddeterminaw il-punti tagħhom u kkalkula l-polinomju ta' interpolazzjoni ta' Lagrange billi tuża l-formula li ġejja. Jekk l-ipprogrammar huwa aktar ċar għalik mill-matematika, allura pi huwa essenzjalment operatur for, li timmultiplika r-riżultati kollha, u sigma hija for, li żżid kollox.
Fuq nistgħu nsolvuha hekk u nirritornaw il-funzjoni polinomjali oriġinali tagħna:
Peress li nafu li , irkupru isir sempliċiment:
Uża aritmetika ta' numru sħiħ mhux sigur
Għalkemm applikajna b'suċċess l-idea bażika ta' Shamir , nibqgħu bi problema li sa issa injorajna. Il-funzjoni polinomjali tagħna tuża aritmetika ta' numru sħiħ mhux sigur. Innota li għal kull punt addizzjonali li attakkant jikseb fuq il-graff tal-funzjoni tagħna, hemm inqas possibbiltajiet għal punti oħra. Tista' tara dan b'għajnejk stess meta tfassal numru dejjem jikber ta' punti għal funzjoni polinomjali bl-użu ta' aritmetika ta' numru sħiħ. Dan huwa kontroproduttiv għall-għan tas-sigurtà ddikjarat tagħna, għaliex l-attakkant m'għandu jkun jaf assolutament xejn sakemm ikollu mill-inqas frammenti.
Biex turi kemm hu dgħajjef iċ-ċirkwit aritmetiku sħiħ, ikkunsidra xenarju li fih attakkant kiseb żewġ punti u jaf informazzjoni pubblika li . Minn din l-informazzjoni jista' jiddeduċi , ugwali għal tnejn, u daħħal il-valuri magħrufa fil-formula и .
L-attakkant jista 'mbagħad isib , għadd :
Peress li aħna definiti bħala numri interi pożittivi magħżula b'mod każwali, hemm numru limitat ta 'possibbli . Bl-użu ta 'din l-informazzjoni, attakkant jista' jiddeduċi , peress li xi ħaġa akbar minn 5 se tagħmel negattiv. Dan jirriżulta li hu minnu peress li ddeterminajna
L-attakkant jista 'mbagħad jikkalkula l-valuri possibbli tissostitwixxi в :
B'għażliet limitati għal jidher ċar kemm huwa faċli li tagħżel u tiċċekkja l-valuri . Hemm biss ħames għażliet hawn.
Issolvi l-problema b'aritmetika ta' numru sħiħ mhux sigur
Biex tiġi eliminata din il-vulnerabbiltà, Shamir jissuġġerixxi li tuża aritmetika modulari, li tissostitwixxi fuq fejn и — is-sett tan-numri primi kollha.
Ejja niftakru malajr kif taħdem l-aritmetika modulari. Arloġġ bl-idejn huwa kunċett familjari. Hija tuża għassa jiġifieri . Hekk kif l-idejn tas-siegħa tgħaddi t-tnax, terġa’ lura għal waħda. Proprjetà interessanti ta’ din is-sistema hija li sempliċement billi nħarsu lejn l-arloġġ, ma nistgħux niddeduċu kemm għamlet rivoluzzjonijiet l-idejn tas-siegħa. Madankollu, jekk nafu li l-id tas-siegħa għaddiet 12 erba’ darbiet, nistgħu niddeterminaw kompletament in-numru ta’ sigħat li għaddew permezz ta’ formula sempliċi fejn huwa d-diviżur tagħna (hawn ), huwa l-koeffiċjent (kemm-il darba d-diviżur jidħol fin-numru oriġinali mingħajr fdal, hawn ), u huwa l-bqija, li normalment jirritorna sejħa ta 'operatur modulo (hawn ). Li nkunu nafu dawn il-valuri kollha jippermettilna nsolvu l-ekwazzjoni għal , imma jekk nitilfu l-koeffiċjent, qatt ma nkunu nistgħu nirrestawraw il-valur oriġinali.
Nistgħu nuru kif dan itejjeb is-sigurtà tal-iskema tagħna billi napplikaw l-iskema għall-eżempju preċedenti tagħna u nużaw . Il-funzjoni polinomjali l-ġdida tagħna , u l-punti l-ġodda . Issa l-kustodji ewlenin jistgħu għal darb'oħra jużaw l-interpolazzjoni polinomjali biex jibnu mill-ġdid il-funzjoni tagħna, biss din id-darba l-operazzjonijiet ta 'żieda u multiplikazzjoni għandhom ikunu akkumpanjati minn tnaqqis modulo (eż ).
Billi tuża dan l-eżempju ġdid, ejja nassumu li l-attakkant tgħallem tnejn minn dawn il-punti ġodda, , u informazzjoni pubblika . Din id-darba, l-attakkant, ibbażat fuq l-informazzjoni kollha li għandu, joħroġ il-funzjonijiet li ġejjin, fejn huwa s-sett tan-numri interi pożittivi kollha, u jirrappreżenta l-koeffiċjent tal-modulu .
Issa l-attakkant tagħna jerġa' jsib , kalkolu :
Imbagħad jerġa' jipprova tissostitwixxi в :
Din id-darba għandu problema serja. Formula valuri nieqsa , и . Peress li hemm numru infinit ta 'kombinazzjonijiet ta' dawn il-varjabbli, ma jista 'jikseb ebda informazzjoni addizzjonali.
Konsiderazzjonijiet ta' Sigurtà
L-iskema ta’ qsim sigriet ta’ Shamir tissuġġerixxi sigurtà mil-lat tat-teorija tal-informazzjoni. Dan ifisser li l-matematika hija reżistenti anke kontra attakkant b'qawwa tal-kompjuter illimitata. Madankollu, iċ-ċirkwit għadu fih diversi kwistjonijiet magħrufa.
Pereżempju, l-iskema ta’ Shamir ma toħloqx frammenti li jridu jiġu ċċekkjati, jiġifieri, in-nies jistgħu jippreżentaw liberament frammenti foloz u jinterferixxu mal-irkupru tas-sigriet korrett. Kustodju tal-frammenti ostili b'informazzjoni suffiċjenti jista' saħansitra jipproduċi framment ieħor billi jinbidel fid-diskrezzjoni tiegħek. Din il-problema tissolva bl-użu skemi ta’ qsim sigriet verifikabbli, bħall-iskema ta' Feldman.
Problema oħra hija li t-tul ta 'kwalunkwe framment huwa ugwali għat-tul tas-sigriet korrispondenti, għalhekk it-tul tas-sigriet huwa faċli biex jiġi ddeterminat. Din il-problema tista 'tiġi solvuta bi trivjali padding sigriet b'numri arbitrarji sa tul fiss.
Fl-aħħarnett, huwa importanti li wieħed jinnota li t-tħassib tagħna dwar is-sigurtà jista 'jestendi lil hinn mid-disinn innifsu. Għal applikazzjonijiet kriptografiċi fid-dinja reali, ħafna drabi jkun hemm it-theddida ta 'attakki fuq kanali sekondarji fejn attakkant jipprova jiġbed informazzjoni utli mill-ħin tal-eżekuzzjoni tal-applikazzjoni, caching, ħabtiet, eċċ. Jekk dan huwa ta 'tħassib, għandha tingħata konsiderazzjoni bir-reqqa waqt l-iżvilupp għall-użu ta' miżuri protettivi bħal funzjonijiet u lookups f'ħin kostanti, il-prevenzjoni tal-memorja milli tiġi ssejvjata fuq disk, u numru ta 'konsiderazzjonijiet oħra li huma lil hinn mill-ambitu ta' dan l-artikolu.
Demo
Fuq Hemm turija interattiva tal-iskema ta' qsim sigriet ta' Shamir. Dimostrazzjoni bbażata fuq il-librerija , li huwa stess huwa port JavaScript tal-programm popolari . Innota li l-kalkolu ta 'valuri kbar , и jista 'jieħu ftit.
Sors: www.habr.com