Wo oju iṣẹlẹ kan nibiti o nilo lati ni aabo ifinkan banki kan. O jẹ aibikita rara laisi bọtini kan, eyiti o fun ni ni ọjọ akọkọ ti iṣẹ. Ibi-afẹde rẹ ni lati tọju bọtini ni aabo.
Jẹ ki a sọ pe o pinnu lati tọju bọtini pẹlu rẹ ni gbogbo igba, pese iraye si ibi ipamọ bi o ti nilo. Ṣugbọn iwọ yoo yarayara mọ pe iru ojutu kan ko ni iwọn daradara ni iṣe, nitori wiwa ti ara rẹ nilo ni gbogbo igba ti o ṣii ibi ipamọ naa. Kini nipa isinmi ti a ṣeleri rẹ? Ni afikun, ibeere naa paapaa bẹru: kini ti o ba padanu bọtini rẹ nikan?
Pẹlu isinmi rẹ ni lokan, o pinnu lati ṣe ẹda bọtini kan ki o si fi le ọdọ oṣiṣẹ miiran. Sibẹsibẹ, o loye pe eyi ko bojumu boya. Nipa ilopo nọmba awọn bọtini, o tun ṣe ilọpo meji awọn aye ti ole bọtini.
Ni ainireti, o pa ẹda-ẹda jẹ ki o pinnu lati pin bọtini atilẹba ni idaji. Bayi, iwọ yoo ro pe eniyan meji ti o ni igbẹkẹle ti o ni awọn ajẹkù bọtini yoo ni lati wa ni ti ara lati gba bọtini naa ki o ṣii ifinkan naa. Eyi tumọ si pe ole kan nilo lati ji awọn ege meji, eyiti o nira lemeji bi ji bọtini kan. Sibẹsibẹ, laipẹ o rii pe ero yii ko dara pupọ ju bọtini kan lọ, nitori ti ẹnikan ba padanu bọtini idaji kan, bọtini kikun ko le gba pada.
A le yanju iṣoro naa pẹlu lẹsẹsẹ awọn bọtini afikun ati awọn titiipa, ṣugbọn ọna yii yoo nilo ni kiakia pupo awọn bọtini ati ki o titii. O pinnu pe apẹrẹ ti o dara julọ yoo jẹ lati pin bọtini naa ki aabo ko gbarale eniyan kan patapata. O tun pinnu pe ẹnu-ọna kan gbọdọ wa fun nọmba awọn ajẹkù nitori pe ti ajẹkù kan ba sọnu (tabi ti eniyan ba lọ si isinmi), bọtini gbogbo wa ni iṣẹ.
Bawo ni lati pin asiri
Iru ero iṣakoso bọtini yii jẹ ero nipa Adi Shamir ni ọdun 1979 nigbati o ṣe atẹjade iṣẹ rẹ
Lati oju-ọna aabo, ohun-ini pataki ti ero yii ni pe ikọlu ko yẹ ki o mọ ohunkohun rara ayafi ti o ba ni o kere ju. awọn ẹya ara. Paapaa wiwa awọn ẹya ko yẹ ki o pese alaye eyikeyi. A pe ohun-ini yii atunmọ aabo.
Interpolation Polynomial
Ilana ala-ilẹ Shamir itumọ ti ni ayika Erongba ilopọ interpolation. Ti o ko ba faramọ pẹlu ero yii, o rọrun pupọ. Ni otitọ, ti o ba ti fa awọn aaye lori aworan kan ati lẹhinna so wọn pọ pẹlu awọn laini tabi awọn ifọwọ, o ti lo tẹlẹ!
Nipasẹ awọn aaye meji o le fa nọmba ailopin ti awọn polynomials ti alefa 2. Lati yan ọkan nikan lati ọdọ wọn, o nilo aaye kẹta kan. Àpèjúwe:
Wo iloyepo kan pẹlu alefa kan, . Ti o ba fẹ ṣe ero iṣẹ yii lori aworan kan, awọn aaye melo ni o nilo? O dara, a mọ pe eyi jẹ iṣẹ laini ti o ṣe laini ati nitorinaa o nilo o kere ju awọn aaye meji. Nigbamii, ronu iṣẹ pipọ pẹlu iwọn meji, . Eyi jẹ iṣẹ kuadiratiki, nitorinaa o kere ju awọn aaye mẹta ni a nilo lati ṣe apẹrẹ awọnyaya naa. Bawo ni nipa iloyepo kan pẹlu iwọn mẹta? O kere ju awọn aaye mẹrin. Ati bẹbẹ lọ ati bẹbẹ lọ.
Ohun ti o wuyi gaan nipa ohun-ini yii ni pe, ti a fun ni iwọn ti iṣẹ pupọ ati o kere ju awọn aaye, a le ni awọn aaye afikun fun iṣẹ oni-iye-iye yii. A pe afikun ti awọn aaye afikun wọnyi ilopọ interpolation.
Ṣiṣe aṣiri kan
Ó ṣeé ṣe kó o ti mọ̀ tẹ́lẹ̀ pé ibi tí ọgbọ́n àrékérekè Shamir ti bẹ̀rẹ̀ sí í ṣe nìyẹn. E je ka so asiri wa Ṣe . A le yipada si aaye kan lori awonya ati pe o wa pẹlu iṣẹ ilopọ pupọ pẹlu alefa , eyi ti o ni itẹlọrun aaye yii. Jẹ ki a leti pe yoo jẹ ẹnu-ọna ti awọn ajẹkù ti a beere, nitorinaa ti a ba ṣeto iloro si awọn ajẹkù mẹta, a gbọdọ yan iṣẹ ilopọ pupọ pẹlu iwọn meji.
Oniruiyebiye wa yoo ni fọọmu naa nibo и - awọn nọmba rere ti a yan laileto. A kan n ṣe agbero iloyepo kan pẹlu alefa , ibi ti free olùsọdipúpọ - Eyi ni asiri wa , ati fun ọkọọkan awọn ti o tẹle awọn ofin nibẹ ni a laileto ti a ti yan rere olùsọdipúpọ. Ti a ba pada si apẹẹrẹ atilẹba ki o ro pe , lẹhinna a gba iṣẹ naa .
Ni aaye yii a le ṣe ina awọn ajẹkù nipasẹ sisopọ oto odidi ni nibo (nitoripe asiri wa ni). Ninu apẹẹrẹ yii, a fẹ kaakiri awọn ajẹkù mẹrin pẹlu iloro ti mẹta, nitorinaa a ṣe ipilẹṣẹ awọn aaye laileto. ki o si fi aaye kan ranṣẹ si ọkọọkan awọn eniyan mẹrin ti o gbẹkẹle, awọn olutọju bọtini. A tun jẹ ki eniyan mọ iyẹn , niwon eyi ni a kà alaye ti gbogbo eniyan ati pe o jẹ dandan fun imularada .
Bọsipọ ikoko
A ti jiroro tẹlẹ lori imọran ti interpolation onipọ-pupọ ati bii o ṣe ṣe agbekalẹ ero ala-ilẹ Shamir . Nigbati eyikeyi mẹta ninu awọn alabojuto mẹrin fẹ lati mu pada , nwọn nikan nilo lati interpolate pẹlu awọn oniwe-ara oto ojuami. Lati ṣe eyi, wọn le pinnu awọn aaye wọn ki o si ṣe iṣiro Lagrange interpolation multinomial nipa lilo agbekalẹ atẹle. Ti siseto ba han si ọ ju mathematiki lọ, lẹhinna pi jẹ oniṣẹ ẹrọ ni pataki for
, eyi ti o pọ gbogbo awọn esi, ati sigma jẹ for
, eyi ti o ṣe afikun ohun gbogbo.
ni a le yanju rẹ bii eyi ki o pada iṣẹ onipo pupọ wa atilẹba:
Niwon a mọ pe , imularada ṣe nìkan:
Lilo iṣiro odidi alailewu
Botilẹjẹpe a ti ṣaṣeyọri lilo imọran ipilẹ Shamir , a ti fi wa silẹ pẹlu iṣoro ti a ti kọju si titi di isisiyi. Išẹ pupọ wa nlo iṣiro odidi alailewu. Ṣe akiyesi pe fun gbogbo aaye afikun ti ikọlu gba lori aworan ti iṣẹ wa, awọn aye diẹ wa fun awọn aaye miiran. O le rii eyi pẹlu awọn oju tirẹ nigbati o ba gbero nọmba ti o pọ si ti awọn aaye fun iṣẹ ilopọ pupọ nipa lilo iṣiro odidi. Eyi jẹ atako si ibi-afẹde aabo ti a sọ, nitori ikọlu ko yẹ ki o mọ nkankan rara titi ti wọn yoo fi ni o kere ju. ajẹkù.
Láti ṣàṣefihàn bí àyíká oníṣirò odidi ṣe jẹ́ aláìlágbára, wo ìṣẹ̀lẹ̀ kan nínú èyí tí olùkọlù kan gba àmì méjì ati ki o mọ àkọsílẹ alaye ti o . Lati alaye yii o le yọkuro , dogba si meji, ati pulọọgi sinu awọn iye ti a mọ sinu agbekalẹ и .
Awọn attacker le ki o si ri , kika :
Niwon a ti telẹ bi laileto ti a ti yan rere odidi, nibẹ ni o wa kan lopin nọmba ti o ti ṣee . Lilo alaye yii, ikọlu le yọkuro , niwon ohunkohun ti o tobi ju 5 yoo ṣe odi. Eyi yoo jade lati jẹ otitọ niwon a ti pinnu
Olukọni le lẹhinna ṣe iṣiro awọn iye to ṣeeṣe , rirọpo в :
Pẹlu opin awọn aṣayan fun o di mimọ bi o ṣe rọrun lati yan ati ṣayẹwo awọn iye . Awọn aṣayan marun nikan wa nibi.
Yiyan iṣoro naa pẹlu iṣiro odidi alailewu
Lati yọkuro ailagbara yii, Shamir ni imọran lilo iṣiro modular, rirọpo on nibo и - ṣeto ti gbogbo nomba nomba.
Jẹ ki a yara ranti bi isiro apọjuwọn ṣe n ṣiṣẹ. Aago pẹlu ọwọ ni a faramọ Erongba. O nlo aago ti o jẹ . Ni kete ti ọwọ wakati ba kọja mejila, o pada si ọkan. Ohun-ini ti o nifẹ si ti eto yii ni pe nipa wiwo aago, a ko le yọkuro iye awọn iyipada ti ọwọ wakati ti ṣe. Bibẹẹkọ, ti a ba mọ pe ọwọ wakati naa ti kọja 12 ni igba mẹrin, a le pinnu patapata iye awọn wakati ti o ti kọja nipa lilo ilana ti o rọrun. nibo ni ipin wa (nibi ), jẹ olùsọdipúpọ (bii iye igba ti olupinpin lọ sinu nọmba atilẹba laisi iyokù, nibi ), ṣugbọn jẹ iyokù, eyiti o maa n da ipe oniṣẹ modulo pada (nibi ). Mọ gbogbo awọn iye wọnyi gba wa laaye lati yanju idogba fun , ṣugbọn ti a ba padanu olùsọdipúpọ, a kii yoo ni anfani lati mu pada iye atilẹba.
A le ṣe afihan bii eyi ṣe mu aabo eto wa pọ si nipa lilo ero naa si apẹẹrẹ wa tẹlẹ ati lilo . Iṣẹ ilopọ tuntun wa , ati awọn titun ojuami . Bayi awọn olutọju bọtini le tun lo interpolation pupọ lati tun iṣẹ wa ṣe, ni akoko yii ni afikun ati awọn iṣẹ isodipupo gbọdọ wa pẹlu idinku modulo. (fun apẹẹrẹ ).
Lilo apẹẹrẹ tuntun yii, jẹ ki a ro pe ikọlu naa kọ meji ninu awọn aaye tuntun wọnyi, , ati àkọsílẹ alaye . Ni akoko yii, ikọlu, ti o da lori gbogbo alaye ti o ni, ṣe agbejade awọn iṣẹ wọnyi, nibo ni ṣeto ti gbogbo rere odidi, ati duro fun iyeida modulus .
Bayi wa attacker ri lẹẹkansi , iṣiro :
Lẹhinna o tun gbiyanju lẹẹkansi , rirọpo в :
Ni akoko yii o ni iṣoro pataki kan. Fọọmu sonu iye , и . Niwọn bi nọmba ailopin ti awọn akojọpọ ti awọn oniyipada wọnyi wa, ko le gba alaye afikun eyikeyi.
Aabo riro
Ilana pinpin ikọkọ ti Shamir ni imọran aabo lati ojuami ti wo ti alaye yii. Eyi tumọ si pe mathimatiki jẹ sooro paapaa lodi si ikọlu kan pẹlu agbara iširo ailopin. Sibẹsibẹ, Circuit tun ni ọpọlọpọ awọn ọran ti a mọ.
Fun apẹẹrẹ, ero Shamir ko ṣẹda awọn ajẹkù lati ṣayẹwo, iyẹn ni pe, awọn eniyan le ṣafihan awọn ajẹkù iro larọwọto ati dabaru pẹlu imularada ti aṣiri to tọ. Olutọju ajẹkù ti o korira pẹlu alaye ti o to le paapaa gbe awọn ajẹkù miiran jade nipa iyipada ni ti ara rẹ lakaye. Isoro yi ti wa ni re nipa lilo verifiable ìkọkọ pinpin Siso, gẹgẹ bi ero Feldman.
Iṣoro miiran ni pe ipari ti eyikeyi ajẹkù jẹ dogba si ipari ti aṣiri ti o baamu, nitorina gigun ti asiri jẹ rọrun lati pinnu. Iṣoro yii le ṣee yanju nipasẹ ohun kekere fifẹ ikoko pẹlu lainidii awọn nọmba to kan ti o wa titi ipari.
Nikẹhin, o ṣe pataki lati ṣe akiyesi pe awọn ifiyesi aabo wa le fa kọja apẹrẹ funrararẹ. Fun awọn ohun elo cryptographic ti gidi-aye, nigbagbogbo wa ni irokeke ikọlu ikanni ẹgbẹ nibiti ikọlu kan gbiyanju lati jade alaye to wulo lati akoko ipaniyan ohun elo, caching, jamba, ati bẹbẹ lọ. Ti eyi ba jẹ ibakcdun, akiyesi ṣọra yẹ ki o fun ni lakoko idagbasoke si lilo awọn igbese aabo gẹgẹbi awọn iṣẹ ati awọn wiwa akoko igbagbogbo, idilọwọ iranti lati wa ni fipamọ si disk, ati nọmba awọn ero miiran ti o kọja ipari ti nkan yii.
Ririnkiri
Ni
orisun: www.habr.com