Eritrereto ny scenario iray izay ilanao ny fiarovana ny banky. Izy io dia heverina ho tsy azo resena tanteraka raha tsy misy fanalahidy, izay omena anao amin'ny andro voalohany fiasana. Ny tanjonao dia ny hitahiry tsara ny lakile.
Aoka hatao hoe manapa-kevitra ny hitazona ny fanalahidy miaraka aminao amin'ny fotoana rehetra ianao, manome fahafahana miditra amin'ny fitahirizana raha ilaina. Saingy ho tsapanao haingana fa ny vahaolana toy izany dia tsy mitombo tsara amin'ny fampiharana, satria ilaina ny fisian'ny vatanao isaky ny manokatra ny fitahirizana ianao. Ahoana ny momba ny fialan-tsasatra nampanantenaina anao? Fanampin'izany, vao mainka mampatahotra ny fanontaniana hoe: ahoana raha very ny fanalahidy tokana?
Miaraka amin'ny fialan-tsasatrao ao an-tsainao, manapa-kevitra ny hanao dika mitovy amin'ny fanalahidy ianao ary ankinina amin'ny mpiasa hafa. Na izany aza, azonao antoka fa tsy mety izany. Amin'ny fampitomboana ny isan'ny fanalahidy, dia avo roa heny ny mety hisian'ny halatra fanalahidy.
Amin'ny famoizam-po, dia manimba ny dika mitovy ianao ary manapa-kevitra ny hizara ny fanalahidy tany am-boalohany ho antsasany. Amin'izao fotoana izao, heverinao fa olona roa atokisana miaraka amin'ny sombiny fototra dia tsy maintsy manatrika ara-batana mba hanangona ny lakile sy hanokafana ny vault. Midika izany fa mila mangalatra tapany roa ny mpangalatra, izay avo roa heny noho ny halatra lakile iray. Na izany aza, tsy ho ela dia ho tsapanao fa tsy tsara kokoa noho ny fanalahidy iray fotsiny io tetika io, satria raha misy olona very antsasa-kilasy, dia tsy azo averina ny fanalahidy feno.
Ny olana dia azo voavaha amin'ny andiana fanalahidy sy hidin-trano fanampiny, fa ity fomba ity dia mitaky haingana много fanalahidy sy hidin-trano. Manapa-kevitra ianao fa ny endrika tsara indrindra dia ny mizara ny fanalahidy mba tsy hiankina tanteraka amin'ny olona iray ny fiarovana. Manatsoaka hevitra ihany koa ianao fa tsy maintsy misy tokonam-baravarana ho an'ny isan'ny sombintsombiny ka raha very ny sombintsombiny iray (na raha misy olona miala sasatra), dia mijanona ho miasa ny fanalahidy iray manontolo.
Ahoana ny fizarana tsiambaratelo
Ity karazana rafitra fitantanana fototra ity dia noheverin'i Adi Shamir tamin'ny 1979 rehefa namoaka ny asany izy . Hazavain’ilay lahatsoratra fohy ilay antsoina hoe 
tetika tokonam-baravarana ahafahana mizara tsara ny sanda miafina (toy ny fanalahidy kriptografika). 
ampahany. Avy eo, rahoviana ary rehefa farafaharatsiny 
avy amin'ny 
ampahany dia nivory, dia afaka mora foana hamerina ny zava-miafina 
.
Amin'ny lafiny fiarovana, ny fananana manan-danja amin'ity tetika ity dia ny hoe tsy tokony hahalala na inona na inona ny mpanafika raha tsy manana farafaharatsiny. 
ampahany. Na ny fisiana 
ny ampahany dia tsy tokony hanome vaovao. Antsoinay hoe fananana io fiarovana semantika.
Fampifangaroana polynomial
Shamir tokonam-baravarana 
naorina manodidina ny foto-kevitra polynomial interpolation. Raha tsy zatra an'io hevitra io ianao dia tena tsotra. Raha ny marina, raha nanao sary teo amin'ny grafika ianao ary nampifandray azy ireo tamin'ny tsipika na curve, dia efa nampiasa izany ianao!
Amin'ny alàlan'ny teboka roa dia azonao atao ny manoritra polynomial tsy misy fetra amin'ny ambaratonga 2. Mba hisafidianana ny hany tokana amin'izy ireo dia mila teboka fahatelo ianao. Fanoharana:
Diniho ny polynomial misy ambaratonga iray, 
. Raha te hamolavola an'io asa io amin'ny grafika ianao, isa firy no ilainao? Eny ary, fantatsika fa ity dia asa tsipika izay mamorona tsipika ary noho izany dia mila teboka roa farafahakeliny. Manaraka, diniho ny asa polynomial misy ambaratonga roa, 
. Fampiasa efamira io, ka teboka telo farafahakeliny no ilaina mba hamolavolana ny grafika. Ahoana ny amin'ny polynomial misy diplaoma telo? Teboka efatra farafahakeliny. Ary ny sisa sy ny sisa.
Ny tena mahafinaritra momba ity fananana ity dia ny hoe, raha jerena ny haavon'ny asa polynomial ary farafaharatsiny 
teboka, dia afaka mahazo teboka fanampiny ho an'ity asa polynomial ity. Antsoinay hoe extrapolation ireo teboka fanampiny ireo polynomial interpolation.
Mamorona tsiambaratelo
Mety ho efa tonga saina ianao fa eo no miditra ny teti-dratsin'i Shamir. Aleo lazaina ny tsiambaratelontsika 
- ity dia 
. Afaka mitodika isika 
amin'ny teboka iray eo amin'ny grafika 
ary tonga amin'ny asa polynomial miaraka amin'ny diplaoma 
, izay mahafa-po io hevitra io. Aoka hotsaroantsika izany 
dia ho tokonam-baravaran'ny sombintsombiny ilaina, ka raha mametraka ny tokonam-baravarana amin'ny ampahany telo isika, dia tsy maintsy misafidy asa polynomial misy ambaratonga roa.
Ny polynomial antsika dia hanana ny endrika 
izay 
и 
- isa tsara nofantenana kisendrasendra. Manangana polynomial misy diplaoma fotsiny izahay 
, izay misy ny coefficient maimaim-poana 
- Izany no tsiambaratelontsika 
, ary ho an'ny tsirairay amin'ireo manaraka 
Misy coefficient tsara nofantenana kisendrasendra. Raha miverina amin'ny ohatra tany am-boalohany isika ary mihevitra izany 
, dia mahazo ny asa 
.
Amin'izao fotoana izao dia afaka mamorona sombiny amin'ny fifandraisana isika 
isa tokana in 
izay 
(satria tsiambaratelontsika izany). Amin'ity ohatra ity, te-hizara ampahany efatra miaraka amin'ny tokonam-baravaran'ny telo izahay, noho izany dia mamorona teboka kisendrasendra izahay. 
ary andefaso teboka iray ho an’ny tsirairay amin’ireo olona efatra atokisana, mpitahiry ny lakile. Ampahafantarinay ny olona koa izany 
, satria heverina ho fampahafantarana ho an'ny daholobe izany ary ilaina amin'ny fanarenana 
.
Famerenana ny tsiambaratelo
Efa niresaka momba ny foto-kevitry ny interpolation polynomial sy ny fomba iorenan'ny tetika tokonam-baravaran'i Shamir isika 
. Rehefa misy telo amin'ireo mpitantan-draharaha efatra te-hamerina 
, mila interpolate fotsiny izy ireo 
miaraka amin'ny teboka miavaka. Mba hanaovana izany, dia afaka mamaritra ny heviny izy ireo 
ary kajy ny polynomial interpolation Lagrange amin'ny fampiasana ity formula manaraka ity. Raha mazava kokoa aminao ny fandaharana noho ny matematika, ny pi dia tena mpandraharaha for, izay mampitombo ny vokatra rehetra, ary ny sigma dia for, izay manampy ny zava-drehetra.
amin'ny 
Afaka mamaha azy toy izao isika ary mamerina ny fiasa polynomial tany am-boalohany:
Satria fantatsika izany 
, fanarenana 
natao tsotra:
Mampiasa aritmetika integer tsy azo antoka
Na dia nampihatra soa aman-tsara ny hevitra fototry ny Shamir aza izahay 
, misy olana tsy noraharahiana hatramin'izao. Ny fiasa polynomial dia mampiasa aritmetika integer tsy azo antoka. Mariho fa isaky ny teboka fanampiny azon'ny mpanafika eo amin'ny tabilaon'ny asantsika dia vitsy kokoa ny mety ho an'ny teboka hafa. Azonao atao ny mahita izany amin'ny masonao rehefa mamolavola teboka mitombo isa ho an'ny fiasa polynomial ianao amin'ny alàlan'ny aritmetika integer. Mifanohitra amin'ny tanjon'ny fiarovana nambarantsika izany, satria tsy tokony hahalala na inona na inona ny mpanafika raha tsy manana farafaharatsiny 
sombiny.
Mba hampisehoana ny fahalemen'ny faribolana arithmetika integer dia diniho ny scenario iray nahazoan'ny mpanafika teboka roa. 
ary mahalala ny vaovaom-bahoaka izany 
. Afaka manatsoaka hevitra izy avy amin’izany fanazavana izany 
, mitovy amin'ny roa, ary ampidiro ao amin'ny formula ny soatoavina fantatra 
и 
.
Ny mpanafika dia afaka mahita 
, manisa 
:
Satria nofaritantsika 
amin'ny maha integer tsara nofantenana kisendrasendra, dia voafetra ny isa azo atao 
. Amin'ny fampiasana an'io fampahalalana io dia afaka manatsoaka hevitra ny mpanafika 
, satria izay rehetra mihoatra ny 5 dia hanao 
ratsy. Marina izany satria efa tapa-kevitra izahay 
Ny mpanafika dia afaka manao kajy ny sanda mety 
, manolo 
в 
:
Miaraka amin'ny safidy voafetra ho an'ny 
dia lasa mazava ny fomba mora ny mifidy sy manamarina ny soatoavina 
. Dimy ihany ny safidy eto.
Famahana ny olana amin'ny aritmetika integer tsy azo antoka
Mba hanafoanana an'io vulnerable io, Shamir dia manoro hevitra ny fampiasana aritmetika modular, manolo 
amin'ny 
izay 
и 
- ny fitambaran'ny isa voalohany rehetra.
Aoka ho tsaroantsika haingana ny fomba fiasan'ny aritmetika modular. Ny famantaranandro misy tanana dia hevitra mahazatra. Mampiasa famantaranandro izy io 
. Raha vao lasa roa ambin'ny folo ny tanana ora dia miverina ho iray izany. Ny fananana mahaliana an'ity rafitra ity dia ny fijerena fotsiny ny famantaranandro, dia tsy azontsika tsoahina hoe firy ny revolisiona nataon'ny tanana ora. Na izany aza, raha fantatsika fa lasa in-12 in-efatra ny tanana ora, dia azontsika atao ny mamaritra tanteraka ny isan'ny ora izay nandalo tamin'ny fampiasana raikipohy tsotra. 
izay 
no mpizara antsika (eto 
), 
dia ny coefficient (impiry ny mpizara no miditra amin'ny isa voalohany tsy misy ambiny, eto 
), ary 
dia ny ambiny, izay matetika mamerina antso modulo operator (eto 
). Ny fahafantarana ireo soatoavina rehetra ireo dia ahafahantsika mamaha ny equation for 
, fa raha tsy mahita ny coefficient isika dia tsy ho afaka hamerina ny sanda tany am-boalohany.
Azontsika atao ny mampiseho ny fomba hanatsarana ny fiarovana ny tetitsika amin'ny alalan'ny fampiharana ny tetika amin'ny ohatra teo aloha sy ny fampiasana azy 
. Ny asa polynomial vaovao 
, ary ireo teboka vaovao 
. Amin'izao fotoana izao dia afaka mampiasa interpolation polynomial indray ireo mpiambina manan-danja mba hananganana indray ny asantsika, amin'ity indray mitoraka ity dia tsy maintsy ampiarahana amin'ny fampihenana modulo ny asa fanampiny sy fampitomboana. 
(oh: 
).
Amin'ny fampiasana an'ity ohatra vaovao ity, andeha hatao hoe nianatra roa tamin'ireo teboka vaovao ireo ilay mpanafika, 
, ary fampahafantarana ho an'ny daholobe 
. Amin'ity indray mitoraka ity, ny mpanafika, mifototra amin'ny fampahalalana rehetra ananany, dia mamoaka ireto asa manaraka ireto, aiza 
dia ny fitambaran'ny isa tsara rehetra, ary 
maneho ny modulus coefficient 
.
Hita indray izao ilay mpanafika anay 
, manao kajy 
:
Dia nanandrana indray izy 
, manolo 
в 
:
Amin'ity indray mitoraka ity dia manana olana goavana izy. Sanda tsy misy formula 
, 
и 
. Koa satria misy fitambarana tsy manam-petra amin'ireo fari-piainana ireo, dia tsy afaka mahazo fampahalalana fanampiny izy.
Hevitra momba ny fiarovana
Manome soso-kevitra ny teti-pizarana tsiambaratelon'i Shamir fiarovana avy amin'ny fomba fijerin'ny teoria fampahalalana. Midika izany fa ny matematika dia mahatohitra na dia amin'ny mpanafika manana hery informatika tsy voafetra aza. Na izany aza, mbola misy olana maro fantatra ny faritra.
Ohatra, tsy mamorona ny teti-dratsin'i Shamir sombiny hojerena, izany hoe, afaka manolotra malalaka sombintsombiny sandoka ny olona ary manelingelina ny famerenana ny tsiambaratelo marina. Ny mpitahiry sombintsombiny mankahala manana fampahalalana ampy dia mety hamokatra sombiny hafa amin'ny fanovana 
araka ny fahaizanao manokana. Ity olana ity dia voavaha amin'ny fampiasana tetika fizarana tsiambaratelo azo hamarinina, toy ny tetik'i Feldman.
Ny olana iray hafa dia ny halavan'ny sombin-javatra rehetra dia mitovy amin'ny halavan'ny tsiambaratelo mifandraika amin'izany, ka mora ny mamaritra ny halavan'ny tsiambaratelo. Ity olana ity dia azo vahana amin'ny tsy misy dikany padding tsiambaratelo miaraka amin'ny isa tsy misy dikany hatramin'ny halavany raikitra.
Farany, zava-dehibe ny manamarika fa ny olana momba ny fiarovana dia mety hihoatra ny famolavolana azy. Ho an'ny fampiharana kriptografika tena misy, dia matetika misy ny fandrahonana ny fanafihana amin'ny sisiny izay misy mpanafika iray manandrana maka vaovao mahasoa amin'ny fotoana fampiharana ny fampiharana, caching, fianjerana, sns. Raha mampanahy izany, dia tokony hojerena tsara mandritra ny fampandrosoana ny fampiasana fepetra fiarovana toy ny fiasa sy ny fitadiavana fotoana tsy tapaka, ny fisorohana ny fitadidiana tsy ho voatahiry ao amin'ny kapila, ary ny fiheverana maro hafa izay tsy voafehin'ity lahatsoratra ity.
Demo
amin'ny Misy fihetsiketsehana ifanakalozan-kevitra momba ny tetika fizarana tsiambaratelon'i Shamir. Fampisehoana mifototra amin'ny tranomboky , izay seranan-tsambo JavaScript amin'ny programa malaza . Mariho fa ny kajy sanda lehibe 
, 
и 
mety haka fotoana kely.
Source: www.habr.com
