Tụlee ihe atụ ebe ị ga-achọ ijide ụlọ akụ. A na-ewere ya dị ka enweghị isi na-enweghị igodo, nke enyere gị n'ụbọchị mbụ nke ọrụ. Ebumnuche gị bụ ịchekwa igodo ahụ n'enweghị nsogbu.
Ka anyị kwuo na ị kpebiri idobe igodo ahụ n'aka gị oge niile, na-enye ohere ịnweta nchekwa ahụ dịka ọ dị mkpa. Ma ị ga-achọpụta ngwa ngwa na ngwọta dị otú ahụ adịghị abawanye nke ọma na omume, n'ihi na a na-achọ ọnụnọ anụ ahụ gị oge ọ bụla ị meghere nchekwa ahụ. Kedu maka ezumike e kwere gị nkwa? Na mgbakwunye, ajụjụ a na-atụ ụjọ karị: gịnị ma ọ bụrụ na naanị igodo gị efunahụ gị?
N'iburu ezumike gị n'uche, ị kpebiri ime otu igodo ma nyefee ya n'aka onye ọrụ ọzọ. Agbanyeghị, ị ghọtara na nke a adịghịkwa mma. Site na iji igodo ugboro abụọ, ị na-enwekwa ohere izu ohi okpukpu abụọ.
N'ime obi nkoropụ, ị ga-ebibi ihe oyiri ahụ wee kpebie kewaa igodo mbụ na ọkara. Ugbu a, ị ga-eche na mmadụ abụọ tụkwasịrị obi nwere iberibe isi ga-anọrịrị n'anụ ahụ iji nakọta igodo wee mepee oghere. Nke a pụtara na onye ohi kwesịrị izu iberibe abụọ, nke siri ike okpukpu abụọ karịa izu otu igodo. Otú ọ dị, n'oge na-adịghị anya, ị ga-achọpụta na atụmatụ a adịghị mma karịa naanị otu igodo, n'ihi na ọ bụrụ na mmadụ efunahụ ọkara igodo, enweghị ike ị nwetaghachi igodo zuru ezu.
Enwere ike idozi nsogbu ahụ site na iji usoro igodo ndị ọzọ na mkpọchi, mana usoro a ga-achọ ngwa ngwa много igodo na mkpọchi. Ị kpebiri na ihe dị mma ga-abụ ịkekọrịta igodo ka nchekwa ghara ịdabere kpamkpam n'otu onye. Ị na-ekwubi na a ghaghị inwe ọnụ ụzọ maka ọnụ ọgụgụ nke iberibe nke mere na ọ bụrụ na otu iberibe efu efu (ma ọ bụ ọ bụrụ na mmadụ na-aga ezumike), igodo ahụ dum ka na-arụ ọrụ.
Otu esi ekekọrịta ihe nzuzo
Ụdị atụmatụ njikwa isi a bụ nke Adi Shamir chere na 1979 mgbe o bipụtara ọrụ ya . Isiokwu na-akọwa nkenke nkenke ihe a na-akpọ 
Atụmatụ ọnụ ụzọ maka ikesa uru nzuzo nke ọma (dị ka igodo cryptographic) n'ime akụkụ. Mgbe ahụ, mgbe na naanị mgbe opekempe si A na-agbakọta akụkụ, ị nwere ike iweghachi ihe nzuzo ahụ ngwa ngwa .
Site n'echiche nchekwa, ihe dị mkpa nke atụmatụ a bụ na onye na-awakpo ekwesịghị ịma ihe ọ bụla ma ọ bụrụ na o nwere ma ọ dịkarịa ala. akụkụ. Ọbụna ọnụnọ akụkụ ekwesịghị inye ozi ọ bụla. Anyị na-akpọ ihe onwunwe a nchekwa semantik.
Njikọta polynomial
Usoro nhazi nke Shamir wuru gburugburu echiche interpolation nke polynomial. Ọ bụrụ na ịmabeghị echiche a, ọ dị nnọọ mfe. N'ezie, ọ bụrụ na ị nwetala isi ihe na eserese wee jikọta ha na ahịrị ma ọ bụ akụkụ, ị ejirila ya!
Site na isi ihe abụọ ị nwere ike ịdọrọ ọnụ ọgụgụ na-akparaghị ókè nke polynomials nke ogo 2. Iji họrọ naanị otu n'ime ha, ị chọrọ isi nke atọ. Ihe atụ:
Tụlee otu polynomial nwere ogo nke mbụ, . Ọ bụrụ na ịchọrọ ịkọ ọrụ a na eserese, isi ihe ole ka ị chọrọ? Ọfọn, anyị maara na nke a bụ ọrụ ahịrị na-emepụta ahịrị na ya mere ọ chọrọ ma ọ dịkarịa ala isi ihe abụọ. Ọzọ, tụlee ọrụ polynomial nwere ogo abụọ, . Nke a bụ ọrụ quadratic, yabụ ọ dịkarịa ala, achọrọ isi atọ iji kpapụta eserese ahụ. Kedu maka polynomial nwere ogo atọ? Opekempe isi anọ. Na ihe ndị ọzọ na ndị ọzọ.
Ihe kacha mma gbasara ihe onwunwe a bụ na, nyere ogo nke ọrụ polynomial na ọ dịkarịa ala isi ihe, anyị nwere ike nwetakwuo ihe maka ọrụ polynomial a. Anyị na-akpọ extrapolation nke isi ihe ndị ọzọ interpolation nke polynomial.
Ime ihe nzuzo
O nwere ike ịbụ na ị chọpụtala na ebe a ka atụmatụ aghụghọ Shamir si malite. Ka anyị kwuo ihe nzuzo anyị Ndi . Anyị nwere ike ịtụgharị ruo n'ókè na eserese wee jiri ogo ya were rụọ ọrụ polynomial , nke na-eju isi okwu a. Ka anyị chetara gị nke ahụ ga-abụ ọnụ ụzọ nke iberibe ihe achọrọ, yabụ ọ bụrụ na anyị edobe ọnụ ụzọ na iberibe atọ, anyị ga-ahọrọ ọrụ polynomial na ogo abụọ.
Anyị polynomial ga-enwe ụdị ebe и - ọnụọgụgụ dị mma ahọpụtara enweghị usoro. Naanị ihe anyị na-eji ogo na-arụ polynomial , ebe ọnụọgụ n'efu - Nke a bụ ihe nzuzo anyị , na nke ọ bụla n'ime ndị na-esote N'okwu enwere ọnụọgụ dị mma ahọpụtara na-enweghị usoro. Ọ bụrụ na anyị alaghachi na ihe atụ mbụ wee were nke ahụ , mgbe ahụ, anyị na-enweta ọrụ ahụ .
N'ebe a, anyị nwere ike ịmepụta iberibe site na ijikọ ọnụọgụgụ pụrụ iche na ebe (n'ihi na ọ bụ ihe nzuzo anyị). N'ihe atụ a, anyị chọrọ ikesa iberibe anọ nwere ọnụ ụzọ atọ, yabụ anyị na-ewepụta isi ihe na-enweghị usoro. ma ziga otu isi ihe nye onye ọ bụla n'ime mmadụ anọ ahụ tụkwasịrị obi, ndị na-elekọta igodo ahụ. Anyị na-emekwa ka ndị mmadụ mara nke ahụ , ebe ọ bụ na a na-ewere nke a ozi ọha na eze ma dị mkpa maka mgbake .
Na-agbake nzuzo
Anyị atụleworị echiche nke interpolation polynomial yana otu o siri dabere atụmatụ ọnụ ụzọ Shamir. . Mgbe atọ ọ bụla n'ime ndị nlekọta anọ chọrọ iweghachi , naanị ha kwesịrị itinye ọnụ ya na isi ihe pụrụ iche. Iji mee nke a, ha nwere ike ikpebi isi ihe ha wee gbakọọ Lagrange interpolation polynomial site na iji usoro a. Ọ bụrụ na mmemme doro gị anya karịa mgbakọ na mwepụ, yabụ pi bụ onye ọrụ for, nke na-amụba nsonaazụ niile, na sigma bụ for, nke na-agbakwụnye ihe niile.
na anyị nwere ike dozie ya dị ka nke a wee weghachi ọrụ mbụ polynomial anyị:
N'ihi na anyị maara nke ahụ , mgbake emere ya dị mfe:
Iji mgbakọ integer na-adịghị ize ndụ
Ọ bụ ezie na anyị ejirila echiche bụ isi nke Shamir tinye nke ọma , anyị nwere nsogbu anyị leghaara anya ruo ugbu a. Ọrụ polynomial anyị na-eji mgbakọ integer na-adịghị ize ndụ. Rịba ama na maka isi ihe ọ bụla onye na-awakpo nwetara na eserese nke ọrụ anyị, enwere ohere dị nta maka isi ihe ndị ọzọ. Ị nwere ike iji anya nke gị hụ nke a mgbe ị na-akpa nkata ọnụ ọgụgụ na-abawanye ụba maka ọrụ polynomial site na iji mgbakọ integer. Nke a megidere ebumnuche nchekwa anyị kwuru, n'ihi na onye na-awakpo ekwesịghị ịma ihe ọ bụla ruo mgbe ha nwere opekata mpe. iberibe.
Iji gosi otú sekit mgbakọ na mwepụ integer si esighị ike, tụlee otu ihe atụ nke onye mwakpo nwetara isi ihe abụọ. ma mara ozi ọhaneze na . Site na ozi a ọ nwere ike wepụta , hà abụọ, wee tinye ụkpụrụ amaara n'ime usoro и .
Onye mwakpo ahụ nwere ike ịchọta ya , agụta :
Ebe ọ bụ na anyị kọwara dị ka ọnụọgụgụ dị mma ahọpụtara na-enweghị usoro, enwere ọnụọgụ ole enwere ike . Iji ozi a, onye na-awakpo nwere ike wepụ ya , ebe ọ bụ na ihe ọ bụla karịrị 5 ga-eme adịghị mma. Nke a ga-abụ eziokwu ebe ọ bụ na anyị ekpebiela
Onye mwakpo ahụ nwere ike gbakọọ ụkpụrụ enwere ike , dochie в :
Na oke nhọrọ maka ọ ga-edo anya ka ọ dị mfe ịhọrọ ma lelee ụkpụrụ . Enwere naanị nhọrọ ise ebe a.
Iji mgbakọ integer na-edozi nsogbu ahụ
Iji kpochapụ adịghị ike a, Shamir na-atụ aro iji modul mgbakọ na mwepụ, dochie on ebe и - set nke niile isi nọmba.
Ka anyị cheta ngwa ngwa ka mgbakọ na mwepụ modular si arụ ọrụ. Elekere nwere aka bụ echiche amaara nke ọma. Ọ na-eji elekere bụ . Ozugbo aka elekere ahụ gafere iri na abụọ, ọ na-alaghachi na otu. Ihe na-adọrọ mmasị nke usoro a bụ na nanị site n'ịle elekere anya, anyị enweghị ike ịchọta mgbanwe mgbanwe nke oge awa ahụ mere. Agbanyeghị, ọ bụrụ na anyị maara na aka elekere agafeela ugboro 12, anyị nwere ike ikpebi awa ole gafere site na iji usoro dị mfe. ebe bụ onye nkesa anyị (ebe a ), bụ ọnụọgụgụ (ugboro ole onye nkesa na-abanye na ọnụọgụ mbụ na-enweghị nke fọdụrụ, ebe a ), na bụ nke fọdụrụ, nke na-eweghachite oku onye ọrụ modulo (ebe a ). Ịmara ụkpụrụ ndị a niile na-enye anyị ohere idozi nha maka , ma ọ bụrụ na anyị na-atụ uche ọnụ ọgụgụ, anyị agaghị enwe ike iweghachi mbụ uru.
Anyị nwere ike igosi otu nke a si eme ka nchekwa nke atụmatụ anyị dịkwuo mma site n'itinye atụmatụ ahụ n'ihe atụ anyị gara aga na iji . Ọrụ polynomial ọhụrụ anyị , na isi ihe ọhụrụ . Ugbu a ndị na-echekwa isi nwere ike iji interpolation polynomial ọzọ rụkwaa ọrụ anyị, naanị oge a, mgbakwunye na mbelata arụmọrụ ga-esonyere ya na mbelata modulo. (dika ).
N'iji ihe atụ ọhụrụ a, ka anyị were na onye mwakpo ahụ mụtara isi ihe abụọ n'ime ọhụrụ ndị a. , na ozi ọha . Oge a, onye na-awakpo ahụ, dabere na ozi niile o nwere, na-emepụta ọrụ ndị a, ebe bụ set nke niile nti integers, na na-anọchi anya ọnụọgụ modulus .
Ugbu a onye mwakpo anyị chọtara ọzọ , ịgbakọ :
Ọ nwaa ọzọ , dochie в :
Oge a o nwere nnukwu nsogbu. Usoro efu ụkpụrụ , и . Ebe ọ bụ na enwere ọnụọgụ na-enweghị ngwụcha nke njikọta nke mgbanwe ndị a, ọ nweghị ike ịnweta ozi ọ bụla ọzọ.
Nchekwa echiche
Atụmatụ ịkekọrịta nzuzo nke Shamir na-atụ aro nchekwa site n'echiche nke ozi ọmụma. Nke a pụtara na mgbakọ na mwepụ na-eguzogide ọgwụ ọbụna megide onye na-awakpo nwere ike mgbako na-akparaghị ókè. Agbanyeghị, sekit ahụ ka nwere ọtụtụ okwu ama ama.
Dịka ọmụmaatụ, atụmatụ Shamir adịghị emepụta iberibe ihe a ga-enyocha, ya bụ, ndị mmadụ na-enwere onwe ha iwepụta iberibe adịgboroja ma gbochie mgbake nke ihe nzuzo ziri ezi. Onye na-edebe iberiibe nke nwere ihe ọmụma zuru oke nwere ike wepụta iberibe ọzọ site n'ịgbanwe n'uche nke gị. A na-edozi nsogbu a site na iji atụmatụ nkekọrịta nzuzo nwere ike ịnwapụta, dị ka atụmatụ Feldman.
Nsogbu ọzọ bụ na ogologo nke iberibe ọ bụla hà nhata ogologo nke ihe nzuzo kwekọrọ, ya mere ogologo ihe nzuzo dị mfe iji chọpụta. Enwere ike idozi nsogbu a site na obere ihe padding nzuzo na nọmba aka ike ruo ogologo ogologo.
N'ikpeazụ, ọ dị mkpa iburu n'obi na nchegbu nchekwa anyị nwere ike ịgbatị karịa nhazi ahụ n'onwe ya. Maka ngwa cryptographic nke ụwa n'ezie, a na-enwekarị ihe iyi egwu nke mwakpo ọwa n'akụkụ ebe onye na-awakpo na-anwa iwepụta ozi bara uru na oge mkpochapụ ngwa, caching, mkpọka, wdg. Ọ bụrụ na nke a bụ nchegbu, ekwesịrị iji nlezianya tụlee n'oge mmepe iji usoro nchebe dị ka ọrụ na nyocha oge niile, na-egbochi ebe nchekwa nchekwa na diski, na ọtụtụ ihe ndị ọzọ na-agafe na isiokwu a.
Ngosi
Na Enwere ngosipụta mmekọrịta nke atụmatụ ikesa nzuzo Shamir. Ihe ngosi dabere n'ọbá akwụkwọ , nke n'onwe ya bụ ọdụ ụgbọ mmiri Javascript nke mmemme a ma ama . Rịba ama na ịgbakọ ụkpụrụ buru ibu , и nwere ike iwe obere oge.
isi: www.habr.com