Beachdaich air suidheachadh far am feum thu seilear banca a dhèanamh tèarainte. Thathas den bheachd gu bheil e gu tur do-chreidsinneach às aonais iuchair, a gheibh thu air a’ chiad latha den obair. Is e an t-amas agad an iuchair a stòradh gu tèarainte.

Canaidh sinn gun co-dhùin thu an iuchair a chumail leat fad na h-ùine, a’ toirt cothrom air an stòradh mar a dh’ fheumar. Ach tuigidh tu gu sgiobalta nach eil fuasgladh mar seo a ’dol gu math ann an cleachdadh, oir tha feum air do làthaireachd corporra a h-uile uair a dh’ fhosglas tu an stòradh. Dè mu dheidhinn na saor-làithean a chaidh a ghealltainn dhut? A bharrachd air an sin, tha a’ cheist eadhon nas eagallach: dè ma chailleas tu an aon iuchair agad?

Le do shaor-làithean san amharc, bidh thu a’ co-dhùnadh leth-bhreac den iuchair a dhèanamh agus a chuir gu neach-obrach eile. Ach, tuigidh tu nach eil seo air leth freagarrach nas motha. Le bhith a’ dùblachadh àireamh nan iuchraichean, bidh thu cuideachd a’ dùblachadh na cothroman air prìomh goid.

Ann an èiginn, sgriosaidh tu an dùblachadh agus co-dhùin thu an iuchair thùsail a roinn ann an leth. A-nis, shaoileadh tu gum feumadh dithis dhaoine earbsach le prìomh chriomagan a bhith an làthair gu corporra gus an iuchair a chruinneachadh agus an seilear fhosgladh. Tha seo a 'ciallachadh gum feum mèirleach dà phìos a ghoid, a tha dà uair cho doirbh ri bhith a' goid aon iuchair. Ach, chan fhada gus an tuig thu nach eil an sgeama seo mòran nas fheàrr na dìreach aon iuchair, oir ma chailleas cuideigin leth-iuchrach, chan fhaighear an iuchair slàn air ais.

Faodar an duilgheadas fhuasgladh le sreath de iuchraichean agus glasan a bharrachd, ach bidh feum air an dòigh-obrach seo gu sgiobalta много iuchraichean agus glasan. Tha thu a’ co-dhùnadh gur e an dealbhadh air leth a bhiodh ann an iuchair a cho-roinn gus nach bi tèarainteachd gu tur an urra ri aon neach. Tha thu cuideachd a 'co-dhùnadh gum feum cuid de stairsneach a bhith ann airson an àireamh de mhìrean gus am bi aon chriomag air chall (no ma thèid neach air saor-làithean), bidh an iuchair gu lèir fhathast ag obair.

Ciamar a roinn dìomhair

Bha Adi Shamir a’ smaoineachadh air an t-seòrsa seo de phrìomh sgeama riaghlaidh ann an 1979 nuair a dh’ fhoillsich e an obair aige "Mar a roinneas tu dìomhaireachd". Tha an artaigil a 'mìneachadh goirid mar a chanar ris sgeama stairsneach airson luach dìomhair a roinn gu h-èifeachdach (leithid iuchair criptografach). pàirtean. An uairsin, cuin agus dìreach cuin co-dhiù bho tha pàirtean air an cruinneachadh, is urrainn dhut an dìomhair a thoirt air ais gu furasta .

Bho thaobh tèarainteachd, is e feart cudromach den sgeama seo nach bu chòir fios a bhith aig an neach-ionnsaigh air rud sam bith mura h-eil co-dhiù aige. pàirtean. Fiù 's an làthair cha bu chòir do phàirtean fiosrachadh sam bith a thoirt seachad. Canaidh sinn an togalach seo ris tèarainteachd semantach.

Eadar-theangachadh polynomial

Sgeama stairsneach Shamir air a thogail timcheall air a’ bhun-bheachd eadar-theangachadh polynomial. Mura h-eil thu eòlach air a’ bhun-bheachd seo, tha e gu math sìmplidh. Gu dearbh, ma tha thu a-riamh air puingean a tharraing air graf agus an uairsin gan ceangal le loidhnichean no lùban, tha thu air a chleachdadh mu thràth!

Tro dhà phuing faodaidh tu àireamh neo-chuingealaichte de polynomials de cheum 2 a tharraing. Gus an aon fhear a thaghadh bhuapa, feumaidh tu treas puing. Dealbh: Uicipeid

Beachdaich air polynomial le ceum a h-aon, . Ma tha thu airson an gnìomh seo a dhealbhadh air graf, cia mheud puing a tha a dhìth ort? Uill, tha fios againn gur e gnìomh sreathach a tha seo a tha a’ cruthachadh loidhne agus mar sin feumaidh e co-dhiù dà phuing. An ath rud, beachdaich air gnìomh polynomial le ceum a dhà, . Is e gnìomh ceithir-cheàrnach a tha seo, agus mar sin tha feum air co-dhiù trì puingean airson an graf a dhealbhadh. Dè mu dheidhinn polynomial le ceum a trì? Co-dhiù ceithir puingean. Agus mar sin air adhart agus mar sin air adhart.

Is e an rud fìor fhionnar mun togalach seo, leis cho ìre sa tha an gnìomh polynomial agus co-dhiù puingean, is urrainn dhuinn puingean a bharrachd fhaighinn airson a’ ghnìomh polynomial seo. Canaidh sinn cur às na puingean a bharrachd sin eadar-theangachadh polynomial.

A 'dèanamh suas dìomhaireachd

Is dòcha gu bheil thu air tuigsinn mar-thà gur ann an seo a thig sgeama snasail Shamir a-steach. Canamaid ar dìomhaireachd A bheil . Faodaidh sinn tionndadh gu puing air a’ ghraf agus thig suas le gnìomh polynomial le ceum , a tha a’ sàsachadh a’ phuing seo. Leig leinn sin a chuimhneachadh Bidh an stairsneach againn de mhìrean a tha a dhìth, mar sin ma shuidhicheas sinn an stairsneach gu trì pìosan, feumaidh sinn gnìomh polynomial a thaghadh le ceum a dhà.

Bidh an cruth aig ar polynomial càite и - àireamhan dearbhach air an taghadh air thuaiream. Tha sinn dìreach a’ togail polynomial le ceum , far a bheil an coefficient an-asgaidh  - Is e seo an dìomhaireachd againn , agus airson gach aon de na leanas teirmean tha co-èifeachd dearbhach air a thaghadh air thuaiream. Ma thilleas sinn chun an eisimpleir thùsail agus gun gabh sinn ris , an uairsin gheibh sinn an gnìomh .

Aig an ìre seo is urrainn dhuinn criomagan a ghineadh le bhith a’ ceangal àireamhan àraid ann an càite (oir is e ar dìomhaireachd a th 'ann). San eisimpleir seo, tha sinn airson ceithir pìosan a sgaoileadh le stairsneach de thrì, agus mar sin bidh sinn a’ cruthachadh puingean air thuaiream agus cuiribh aon phuing ris gach aon de na ceithir daoine earbsach, luchd-gleidhidh na h-iuchrach. Leig sinn fios do dhaoine cuideachd , leis gu bheil seo air a mheas mar fhiosrachadh poblach agus gu bheil e riatanach airson faighinn seachad air .

A 'faighinn air ais an dìomhair

Tha sinn mu thràth air bruidhinn air a’ bhun-bheachd de eadar-theachd polynomial agus mar a tha e mar bhunait air sgeama stairsneach Shamir . Nuair a tha triùir de na ceithir urrasairean ag iarraidh a thoirt air ais , chan fheum iad ach eadar-theangachadh le na puingean sònraichte aige fhèin. Gus seo a dhèanamh, faodaidh iad na puingean aca a cho-dhùnadh agus obrachadh a-mach polynomial eadar-roinn Lagrange a’ cleachdadh na foirmle a leanas. Ma tha prògramadh nas soilleire dhut na matamataig, is e gnìomhaiche a th’ ann am pi for, a tha ag iomadachadh a h-uile toradh, agus tha sigma for, a chuireas ris a h-uile càil.

aig is urrainn dhuinn a fhuasgladh mar seo agus ar gnìomh polynomial tùsail a thilleadh:

Leis gu bheil fios againn air sin , faighinn seachad air air a dhèanamh gu sìmplidh:

A’ cleachdadh àireamhachd iomlanachd neo-shàbhailte

Ged a tha sinn air bun-bheachd Shamir a chuir an gnìomh gu soirbheachail , tha sinn air ar fàgail le duilgheadas nach do dhìochuimhnich sinn gu ruige seo. Bidh an gnìomh polynomial againn a’ cleachdadh àireamhachd iomlanachd neo-shàbhailte. Thoir an aire, airson a h-uile puing a bharrachd a gheibh neach-ionnsaigh air graf ar gnìomh, gu bheil nas lugha de chothroman ann airson puingean eile. Chì thu seo le do shùilean fhèin nuair a bhios tu a’ dealbhadh àireamh a tha a’ sìor fhàs airson gnìomh polynomial a’ cleachdadh àireamhachd iomlan. Tha seo an aghaidh ar n-amas tèarainteachd ainmichte, oir cha bu chòir fios a bhith aig an neach-ionnsaigh air rud sam bith gus am bi co-dhiù aca mìrean.

Gus sealltainn cho lag sa tha an cuairteachadh àireamhachd iomlan, smaoinich air suidheachadh anns an d’ fhuair neach-ionnsaigh dà phuing agus tha fios aige air fiosrachadh poblach . Bhon fhiosrachadh seo faodaidh e co-dhùnadh , co-ionann ri dhà, agus cuir a-steach na luachan aithnichte a-steach don fhoirmle и .

Faodaidh an neach-ionnsaigh an uairsin a lorg , cunntadh :

Bhon a tha sinn air a mhìneachadh mar àireamhan dearbhach air an taghadh air thuaiream, tha àireamh chuingealaichte de chomas ann . A’ cleachdadh an fhiosrachaidh seo, faodaidh neach-ionnsaigh faighinn a-mach , oir nì rud sam bith nas motha na 5 àicheil. Tha seo a’ tionndadh a-mach gu bhith fìor bhon a tha sinn air co-dhùnadh

Faodaidh an neach-ionnsaigh an uairsin na luachan comasach obrachadh a-mach cuir an àite в :

Le roghainnean cuibhrichte airson bidh e soilleir cho furasta ‘s a tha e na luachan a thaghadh agus a sgrùdadh . Chan eil ach còig roghainnean an seo.

Fuasgladh na trioblaid le àireamhachd iomlan neo-shàbhailte

Gus cuir às don so-leòntachd seo, tha Shamir a’ moladh a bhith a’ cleachdadh àireamhachd modular, ath-chur air càite и - seata de phrìomh àireamhan.

Cuimhnichidh sinn gu sgiobalta mar a tha àireamhachd modular ag obair. Tha gleoc le làmhan na bhun-bheachd eòlach. Bidh i a’ cleachdadh uaireadair a tha . Cho luath 's a bhios an uair a thìde seachad air a dhà-dheug, tillidh i gu aon. Is e feart inntinneach den t-siostam seo nach urrainn dhuinn dìreach le bhith a’ coimhead air a’ ghleoc faighinn a-mach cia mheud tionndadh a rinn an uair a thìde. Ach, ma tha fios againn gu bheil an làmh uair air a dhol seachad air 12 ceithir tursan, is urrainn dhuinn gu tur faighinn a-mach an àireamh de dh'uairean a chaidh seachad a ’cleachdadh foirmle sìmplidh càite  is e ar roinnear (an so ),  a bheil an co-èifeachd (co mheud uair a thèid an roinnear a-steach don àireamh thùsail gun chòrr, an seo ), agus  an còrr, a bhios mar as trice a’ tilleadh fios gnìomhaiche modulo (an seo ). Le bhith eòlach air na luachan sin uile leigidh sin leinn an co-aontar fhuasgladh airson , ach ma chailleas sinn an co-èifeachd, cha bhith e comasach dhuinn an luach tùsail a thoirt air ais.

Is urrainn dhuinn sealltainn mar a leasaicheas seo tèarainteachd ar sgeama le bhith a’ cur an sgeama an sàs san eisimpleir a bh’ againn roimhe agus a’ cleachdadh . An gnìomh polynomial ùr againn , agus na puingean ùra . A-nis faodaidh na prìomh luchd-gleidhidh eadar-ghluasad polynomial a chleachdadh a-rithist gus ar gnìomh ath-chruthachadh, is e dìreach an turas seo a dh’ fheumas lughdachadh modulo a dhol còmhla ris na h-obraichean cur-ris agus iomadachaidh. (me ).

A’ cleachdadh an eisimpleir ùr seo, leig dhuinn gabhail ris gun do dh’ ionnsaich an neach-ionnsaigh dhà de na puingean ùra sin, , agus fiosrachadh poblach . An turas seo, bidh an neach-ionnsaigh, stèidhichte air a h-uile fiosrachadh a th ’aige, a’ toirt a-mach na gnìomhan a leanas, càite  is e an seata de na h-àireamhan dearbhach uile, agus a’ riochdachadh a’ cho-èifeachd modulus .

A-nis lorg an neach-ionnsaigh againn a-rithist , àireamhachadh :

An uairsin bidh e a’ feuchainn a-rithist cuir an àite в :

An turas seo tha fìor dhuilgheadas aige. Foirmle luachan a dhìth , и . Leis gu bheil àireamh neo-chrìochnach de choimeasgaidhean de na caochladairean sin ann, chan urrainn dha fiosrachadh a bharrachd fhaighinn.

Beachdachaidhean tèarainteachd

Tha sgeama roinneadh dìomhair Shamir a’ moladh tèarainteachd bho shealladh teòiridh fiosrachaidh. Tha seo a 'ciallachadh gu bheil am matamataig seasmhach eadhon an aghaidh neach-ionnsaigh le cumhachd coimpiutaireachd gun chrìoch. Ach, tha grunn chùisean aithnichte fhathast anns a’ chuairt.

Mar eisimpleir, chan eil sgeama Shamir a 'cruthachadh pìosan ri sgrùdadh, is e sin, faodaidh daoine criomagan meallta a thaisbeanadh gu saor agus casg a chuir air faighinn seachad air an dìomhaireachd cheart. Dh'fhaodadh neach-gleidhidh criomag nàimhdeil le fiosrachadh gu leòr eadhon criomag eile a thoirt gu buil le bhith ag atharrachadh a rèir do thoil fhèin. Tha an duilgheadas seo air a fuasgladh le bhith a 'cleachdadh sgeamaichean roinneadh dìomhair dearbhaidh, leithid sgeama Feldman.

Is e duilgheadas eile a th 'ann gu bheil fad criomag sam bith co-ionnan ri fad an dìomhair co-fhreagarrach, agus mar sin tha fad an dìomhair furasta a dhearbhadh. Faodar an duilgheadas seo fhuasgladh le mion-fhiosrachadh pleadhag dìomhair le àireamhan neo-riaghailteach suas gu fad stèidhichte.

Mu dheireadh, tha e cudromach cuimhneachadh gum faodadh na draghan tèarainteachd againn a dhol nas fhaide na an dealbhadh fhèin. Airson tagraidhean criptografach san t-saoghal fhìor, gu tric tha cunnart ann bho ionnsaighean taobh-seanail far am bi neach-ionnsaigh a’ feuchainn ri fiosrachadh feumail a thoirt a-mach à ùine cur an gnìomh tagraidh, tasgadh, tubaistean, msaa. Ma tha seo na adhbhar dragh, bu chòir beachdachadh gu faiceallach rè leasachadh air a bhith a’ cleachdadh ceumannan dìon leithid gnìomhan agus sgrùdadh ùine shìorraidh, a’ cur casg air cuimhne bho bhith air a shàbhaladh gu diosc, agus grunn nithean eile a tha taobh a-muigh raon an artaigil seo.

Demo

air a ' an duilleag seo Tha taisbeanadh eadar-ghnìomhach ann de sgeama roinneadh dìomhair Shamir. Taisbeanadh stèidhichte air an leabharlainn ssss-js, a tha ann fhèin na phort JavaScript den phrògram mòr-chòrdte faqs. Thoir an aire gu bheil thu a 'cunntadh luachan mòra , и bheir e greis.

Source: www.habr.com