Tixgeli dhacdo meesha aad u baahan tahay si aad u xafido khasnadda bangiga. Waxaa loo tixgaliyaa inaan gabi ahaanba aan la dafiri karin furaha la'aanteed, kaas oo lagu siiyo maalinta ugu horeysa ee shaqada. Hadafkaagu waa inaad si ammaan ah u kaydiso furaha.
Aynu nidhaahno inaad go'aansatid inaad furaha ku hayso mar walba, adigoo siinaya gelitaanka kaydinta hadba sida loogu baahdo. Laakiin waxaad si dhakhso ah u ogaan doontaa in xalkan oo kale uusan si fiican u cabbirin ficil ahaan, sababtoo ah joogitaankaaga jireed ayaa loo baahan yahay mar kasta oo aad furto kaydinta. Ka warran fasaxii laguu ballan qaaday? Intaa waxaa dheer, su'aashu waa xitaa cabsi badan: ka waran haddii aad lumiso furahaaga kaliya?
Adiga oo maskaxda ku haya fasaxaaga, waxaad go'aansataa inaad nuqul ka sameyso furaha oo aad u dhiibto shaqaale kale. Si kastaba ha ahaatee, waxaad fahamsan tahay in tani aysan sidoo kale ku habboonayn. Markaad labajibaarto tirada furayaasha, waxaad sidoo kale labanlaabaysaa fursadaha xatooyada muhiimka ah.
Markaad quusto, waxaad burburisaa nuqulka oo waxaad go'aansataa inaad kala qaybiso furaha asalka ah kala badh. Hadda, waxaad u malaynaysaa in laba qof oo la aamini karo oo leh jajabyo muhiim ah ay tahay inay jir ahaan joogaan si ay furaha u soo ururiyaan una furaan khasnadda. Taas macnaheedu waxa weeye in tuuggu u baahan yahay in uu xado laba qaybood, taas oo laba jibaar ka adag in uu xado hal fure. Si kastaba ha ahaatee, waxaad si dhakhso ah u ogaanaysaa in nidaamkani aanu aad uga fiicneyn hal fure, sababtoo ah haddii qof lumiyo furaha kala bar, furaha buuxa lama soo celin karo.
Dhibaatada waxaa lagu xalin karaa dhowr fure oo dheeraad ah iyo quful, laakiin habkani wuxuu si dhakhso ah u baahan doonaa ΠΌΠ½ΠΎΠ³ΠΎ furayaasha iyo qufulka. Waxaad go'aansatey in naqshadda ugu habbooni ay tahay in la wadaago furaha si ammaanku uusan ugu tiirsanayn hal qof. Waxaad sidoo kale ku soo gabagabeyneysaa in ay tahay in ay jirto xoogaa xaddidan oo loogu talagalay tirada jajabyada si haddii hal jajab uu lumo (ama haddii qofku fasax galo), furaha oo dhan wuxuu ahaanayaa mid shaqeynaya.
Sida loo wadaago sirta
Noocan nidaamka maamulka muhiimka ah waxaa ka fikiray Adi Shamir 1979 markii uu daabacay shaqadiisa . Maqaalku wuxuu si kooban u sharaxay waxa loogu yeero 
nidaamka bilowga ah ee si hufan loogu qaybinayo qiimaha sirta ah (sida furaha cryptographic). qaybo. Kadib, goorta iyo kaliya marka ugu yaraan ka qaybo ayaa la isku soo ururiyaa, waxaad si fudud u soo celin kartaa sirta .
Marka la eego dhinaca amniga, hantida muhiimka ah ee nidaamkan ayaa ah in qofka weerarka geystay uusan si buuxda u ogaanin wax kasta ilaa uu haysto ugu yaraan mooyaane. qaybo. Xataa joogitaanka Qaybaha waa inaysan bixin wax macluumaad ah. Waxaan ugu yeernaa hantidaan ammaanka semantiga.
Dhexdhexaadinta badan
Nidaamka marinka Shamir dhisay agagaarka fikradda interpolation polynomial. Haddii aadan aqoon u lahayn fikraddan, runtii waa wax fudud. Dhab ahaantii, haddii aad waligaa dhibco ku sawirtay garaaf ka dibna aad ku xidhatay xariiqyo ama qaloocyo, horay ayaad u isticmaashay!
Iyada oo la adeegsanayo laba dhibcood waxaad sawiri kartaa tiro aan xadidnayn oo tiro badan oo ah shahaadada 2. Si aad u doorato midka kaliya ee iyaga ka mid ah, waxaad u baahan tahay dhibic saddexaad. Sawir:
Tixgeli polynomial leh shahaadada koowaad, . Haddii aad rabto inaad shaqadan ku sawirto garaaf, imisa dhibcood ayaad u baahan tahay? Hagaag, waxaynu ognahay in tani ay tahay hawl toosan oo samaysa xariiq oo ay u baahan tahay ugu yaraan laba dhibcood. Marka xigta, tixgeli shaqo badan oo leh shahaadada labaad, . Tani waa shaqo afar geesle ah, markaa ugu yaraan saddex dhibcood ayaa loo baahan yahay si loo sawiro garaafka. Sidee ku saabsan polynomial oo leh shahaadada seddexaad? Ugu yaraan afar dhibcood. Iyo wixi la mida iyo wixi la mida.
Waxa ugu fiican ee ku saabsan hantidan ayaa ah, marka la eego heerka shaqada polynomial iyo ugu yaraan dhibcood, waxaan u soo saari karnaa dhibco dheeraad ah shaqadan badan. Waxaan ugu yeernaa ka-saarista qodobbadan dheeraadka ah interpolation polynomial.
Samaynta sir
Waxaa laga yaabaa inaad horeba u garatay in meeshan ay tahay meesha uu ka soo baxay qorshaha xariifnimada ah ee Shamir. Aan sheegno sirtayada Waa . Waan u jeesan karnaa ilaa hal dhibic garaafka oo la yimaadaan shaqo badan oo leh shahaado , taas oo ku qanacsan qodobkan. Aan xasuusano taas waxay noqon doontaa marinkayaga jajabyada loo baahan yahay, sidaas darteed haddii aan dejinno marinka saddex jajab, waa inaan dooranaa shaqo badan oo leh shahaadada labaad.
Badankayaga ayaa yeelan doona foomka halkaas oo ΠΈ - tirooyinka togan ee si aan kala sooc lahayn loo doortay. Waxaan kaliya dhisaynaa polynomial oo leh shahaado , halkaas oo isku-dhafka bilaashka ah - Tani waa sirtayada , iyo mid kasta oo ka mid ah kuwa xiga Erayada waxaa jira isku-dheellitirnaan togan oo si aan kala sooc lahayn loo doortay. Haddii aan u soo noqonno tusaalaha asalka ah oo aan u qaadanno taas , ka dibna waxaan helnaa shaqada .
Halkaa marka ay marayso waxa aan dhalin karnaa jajab marka la isku xidho tirooyin gaar ah oo ku jira halkaas oo (waayo waa sirteena). Tusaalahan, waxaan rabnaa inaan u qaybinno afar jajab oo leh marin saddex geesood ah, markaa waxaan si aan kala sooc lahayn u dhalinay dhibco oo u dir hal dhibic mid kasta oo ka mid ah afarta qof ee la aaminay, ilaaliyaasha furaha. Waxaan sidoo kale ogeysiin dadka taas , maadaama tan loo tixgeliyo macluumaadka dadweynaha oo ay lagama maarmaan u tahay soo kabashada .
Soo kabashada sirta
Waxaan mar hore ka hadalnay fikradda isdhexgalka badan iyo sida ay u hoos timaado nidaamka bilowga ee Shamir . Marka mid ka mid ah seddex ka mid ah afarta wakiil ee doonaya inay soo celiyaan , kaliya waxay u baahan yihiin inay is dhexgalaan oo leh dhibco u gaar ah. Si tan loo sameeyo, waxay go'aamin karaan dhibcahooda oo xisaabi Lagrange interpolation polynomial adoo isticmaalaya qaacidada soo socota. Haddii barnaamijku kaaga cad yahay xisaabta, markaa pi runtii waa hawlwadeen for, taas oo badinaysa dhammaan natiijooyinka, iyo sigma waa for, taas oo wax walba soo kordhinaysa.
at Waxaan ku xallin karnaa sidan oo kale oo soo celin karnaa shaqadeenii asalka ahayd:
Maadaama aan taas ognahay , soo kabasho si fudud loo sameeyay:
Isticmaalka xisaabta is-dhex-galka aan badbaadada lahayn
Inkastoo aan si guul leh u dabaqnay fikradda aasaasiga ah ee Shamir , dhibaato aan ilaa hadda iska indha tirnay ayaa innaga hartay. Hawshayada badan ee kala duwan waxay isticmaashaa xisaabinta isku dhafka aan badbaadada lahayn. Ogsoonow in dhibco kasta oo dheeri ah uu weeraryahanku ka helo garaafka shaqadayada, waxaa jira fursado yar oo dhibco kale ah. Tan waxaad ku arki kartaa indhahaaga marka aad qorsheyso tiro dhibco ah oo sii kordheysa oo loogu talagalay hawl badan oo kala duwan adoo isticmaalaya xisaabinta isku dhafan. Tani waxay ka soo horjeedaa yoolkayaga amniga ee la sheegay, sababtoo ah weeraryahanku waa inuu gabi ahaanba waxba ka ogaanin ilaa uu ka helayo ugu yaraan. jajab.
Si aad u muujiso sida uu daciifka u yahay wareegga xisaabinta isku dhafka ah, tixgeli xaalad uu weeraryahanku ka helay laba dhibcood. waana uu garanayaa xogta dadweynaha taas . Xogtan ayuu ka soo saari karaa , oo le'eg laba, oo ku xidh qiyamka la yaqaan ee qaacidada ΠΈ .
Weerarka ayaa markaa heli kara , tirinta :
Mar haddii aan qeexnay Sida aan kala sooc lahayn loo doortay shaandhada togan, waxaa jira tiro xaddidan oo suurtagal ah . Isticmaalka macluumaadkan, weeraryahan ayaa ka saari kara , maadaama wax ka weyn 5 ay sameyn doonaan taban. Tani waxay noqotaa run maadaama aan go'aansanay
Weeraryahanku wuxuu markaas xisaabin karaa qiyamka suurtagalka ah bedelid Π² :
Iyada oo leh xulashooyin xaddidan way caddaatay sida ay u fududahay in la doorto oo la hubiyo qiyamka . Waxaa jira shan doorasho oo keliya halkan.
Ku xallinta dhibaatada iyadoo la adeegsanayo xisaabta is-dhexgalka aan badbaado lahayn
Si meesha looga saaro nuglaantan, Shamir waxa ay soo jeedinaysaa in la isticmaalo xisaabinta modular, beddelka on halkaas oo ΠΈ - dhammaan tirooyinka ugu muhiimsan.
Aynu si degdeg ah u xasuusanno sida xisaabtu u shaqeyso. Saacad gacmuhu waa fikrad la yaqaan. Waxay isticmaashaa saacad ah . Isla markii ay saacaddu gacantu laba iyo toban dhaafto, waxay ku soo noqotaa hal. Hantida xiisaha leh ee nidaamkani waa in si fudud loo eego saacadda, ma ogaan karno inta kacdoon ee saacaddu ay samaysay. Si kastaba ha ahaatee, haddii aan ognahay in gacantu ay dhaaftay 12 afar jeer, waxaan si buuxda u go'aamin karnaa tirada saacadood ee ka soo wareegtay annaga oo adeegsanayna qaacido fudud. halkaas oo waa qaybiyeheena (halkan ), waa isku xidhka (immisa jeer ayuu qaybiyuhu galaa lambarka asalka ah iyada oo aan wax ka hadhayn, halkan ), waa inta soo hartay, kaas oo inta badan soo celisa wicitaanka modulo (halkan ). Ogaanshaha dhammaan qiyamkan ayaa noo ogolaanaya inaan xallino isla'egta , laakiin haddii aan seegno isku-dhafka, marnaba ma awoodi doono inaan soo celinno qiimihii asalka ahaa.
Waxaan muujin karnaa sida ay tani u wanaajiso amniga nidaamkayaga anagoo adeegsanayna nidaamka tusaalaheenii hore oo isticmaalaya . Shaqadeena cusub ee polynomial , iyo qodobbada cusub . Hadda ilaaliyayaasha furaha ah waxay mar labaad isticmaali karaan isku-xirnaanta kala duwan si ay dib ugu dhisaan shaqadeena, kaliya markan kaliya isku darka iyo isku dhufashada hawlgallada waa in ay la socdaan dhimista modulo. (tusaale ahaan ).
Anaga oo adeegsanayna tusaalahan cusub, aan ka soo qaadno in weeraryahanku uu bartay laba qodob oo ka mid ah kuwan cusub, , iyo xogta guud . Markan, weeraryahanku, isagoo ka duulaya dhammaan macluumaadka uu haysto, wuxuu soo saaraa hawlaha soo socda, halka waa isku dhafka dhammaan shaandhada togan, iyo waxay matalaysaa iskudarka modules-ka .
Hadda weeraryahankii ayaa mar kale helay , xisaabinta :
Haddana mar kale ayuu isku dayaa bedelid Π² :
Markan dhibaato halis ah ayuu haystaa. Formula ka maqan qiyamka , ΠΈ . Maadaama ay jiraan tiro aan dhammaad lahayn oo isku dhafan doorsoomayaashan, ma heli karo macluumaad dheeraad ah.
Tixgelinta Amniga
Qorshaha wadaagga sirta ah ee Shamir ayaa soo jeedinaya amniga marka laga eego dhinaca aragtida macluumaadka. Tani waxay ka dhigan tahay in xisaabtu ay u adkaysanayso xitaa weeraryahan leh awood xisaabeed aan xadidnayn. Si kastaba ha ahaatee, wareeggu wali wuxuu ka kooban yahay dhowr arrimood oo la yaqaan.
Tusaale ahaan, qorshaha Shamir ma abuuro jajab in la hubiyo, taas oo ah, dadku waxay si xor ah u soo bandhigi karaan jajabyo been abuur ah waxayna farageliyaan soo kabashada sirta saxda ah. Goolhayaha cadawga leh ee haysta xog ku filan wuxuu xitaa soo saari karaa jajab kale isagoo bedelaya go'aankaaga. Dhibaatadan waxaa lagu xalliyaa iyadoo la isticmaalayo qorshayaasha wadaagga sirta ah ee la xaqiijin karo, sida nidaamka Feldman.
Dhibaato kale ayaa ah in dhererka jajab kasta uu la mid yahay dhererka sirta u dhiganta, sidaas darteed dhererka sirta waa sahlan tahay in la go'aamiyo. Dhibaatadan waxaa lagu xallin karaa wax yar cufan sirta leh tirooyinka aan sabab lahayn ilaa dherer go'an.
Ugu dambeyntii, waxaa muhiim ah in la ogaado in walaacayada amnigu ay dhaafi karaan naqshadda lafteeda. Codsiyada cryptographic-ka dhabta ah ee aduunka, inta badan waxaa jira halista werarada dhanka kanaalka ah halkaas oo uu weerarku isku dayo inuu ka soo saaro macluumaadka waxtarka leh wakhtiga fulinta codsiga, kaydinta, shilalka, iwm. Haddii tani ay tahay walaac, tixgelin taxaddar leh waa in la siiyaa inta lagu jiro horumarka si loo isticmaalo tallaabooyinka ilaalinta sida hawlaha iyo raadinta wakhti-joogta ah, ka hortagga xusuusta in lagu kaydiyo diskka, iyo tiro ka mid ah tixgelinno kale oo ka baxsan xadka qodobkan.
Demo
In Waxaa jira mudaaharaad is dhexgal ah oo ku saabsan nidaamka wadaagga sirta ah ee Shamir. Mudaaharaad ku salaysan maktabadda , taas oo lafteedu tahay dekedda JavaScript ee barnaamijka caanka ah . Ogow xisaabinta qiimayaasha waaweyn , ΠΈ laga yaabaa inay muddo qaadato
Source: www.habr.com