Xav txog qhov xwm txheej uas koj xav tau kom ruaj ntseg lub tsev txhab nyiaj. Nws yog suav tias yog impregnable kiag li tsis muaj tus yuam sij, uas koj tau muab rau thawj hnub ntawm kev ua haujlwm. Koj lub hom phiaj yog khaws tus yuam sij kom ruaj ntseg.
Cia peb hais tias koj txiav txim siab khaws tus yuam sij nrog koj txhua lub sijhawm, muab kev nkag mus rau qhov chaw cia raws li xav tau. Tab sis koj yuav paub sai sai tias qhov kev daws teeb meem no tsis zoo hauv kev xyaum, vim tias koj lub cev yuav tsum muaj txhua zaus koj qhib qhov chaw cia. Yuav ua li cas txog hnub so koj tau cog lus tseg? Tsis tas li ntawd, lo lus nug tseem ceeb dua: ua li cas yog tias koj poob koj tus yuam sij nkaus xwb?
Nrog koj so nyob rau hauv lub siab, koj txiav txim siab ua ib daim qauv ntawm tus yuam sij thiab tso siab rau lwm tus neeg ua haujlwm. Txawm li cas los xij, koj nkag siab tias qhov no tsis zoo tagnrho. Los ntawm ob npaug ntawm tus lej ntawm tus yuam sij, koj kuj tseem muaj ob npaug ntawm qhov muaj feem ntawm tub sab nyiag.
Hauv kev poob siab, koj rhuav tshem cov duplicate thiab txiav txim siab faib tus yuam sij thawj hauv ib nrab. Tam sim no, koj yuav xav tias ob tus neeg ntseeg siab nrog cov khoom tseem ceeb yuav tsum tau muaj lub cev los khaws tus yuam sij thiab qhib lub vault. Qhov no txhais tau hais tias tus tub sab yuav tsum nyiag ob daim, uas yog ob zaug nyuaj li nyiag ib tus yuam sij. Txawm li cas los xij, sai sai no koj paub tias cov tswv yim no tsis zoo dua li ib tus yuam sij xwb, vim tias yog ib tus neeg poob ib nrab ntawm tus yuam sij, tus yuam sij tag nrho tsis tuaj yeem rov qab los.
Qhov teeb meem tuaj yeem daws tau nrog cov yawm sij ntxiv thiab cov xauv, tab sis txoj hauv kev no yuav xav tau sai ntau yuam sij thiab xauv. Koj txiav txim siab tias tus qauv tsim zoo tshaj plaws yuav yog los qhia tus yuam sij kom kev ruaj ntseg tsis vam khom rau ib tus neeg. Koj kuj tau txiav txim siab tias yuav tsum muaj qee qhov pib ntawm tus lej ntawm qhov tawg yog li ntawd yog tias ib qho tawg lawm (lossis yog ib tus neeg mus so), tag nrho tus yuam sij tseem ua haujlwm.
Yuav ua li cas qhia qhov zais cia
Hom kev tswj hwm qhov tseem ceeb no tau xav txog los ntawm Adi Shamir hauv 1979 thaum nws luam tawm nws txoj haujlwm . Kab lus luv luv piav txog qhov hu ua 
cov txheej txheem rau kev faib cov nqi zais cia (xws li tus yuam sij cryptographic) rau hauv ntu. Tom qab ntawd, thaum twg thiab tsuas yog thaum tsawg kawg los ntawm cov khoom tau sib sau ua ke, koj tuaj yeem yooj yim rov qab qhov zais cia .
Los ntawm kev saib xyuas kev ruaj ntseg, ib qho tseem ceeb ntawm cov tswv yim no yog tias tus neeg tawm tsam yuav tsum tsis txhob paub dab tsi kiag li tshwj tsis yog nws muaj tsawg kawg nkaus. ntu. Txawm lub xub ntiag qhov chaw yuav tsum tsis txhob muab cov ntaub ntawv. Peb hu cov cuab yeej no semantic kev ruaj ntseg.
Polynomial interpolation
Shamir threshold scheme ua ib ncig ntawm lub tswvyim polynomial interpolation. Yog tias koj tsis paub txog lub tswv yim no, nws ua tau yooj yim heev. Qhov tseeb, yog tias koj tau kos cov ntsiab lus ntawm daim duab thiab txuas nrog lawv nrog kab lossis nkhaus, koj twb tau siv nws!
Los ntawm ob lub ntsiab lus koj tuaj yeem kos tus lej tsis txwv ntawm polynomials ntawm degree 2. Txhawm rau xaiv ib qho ntawm lawv, koj xav tau qhov thib peb. Piv txwv:
Xav txog polynomial nrog degree ib, . Yog tias koj xav npaj cov haujlwm no rau ntawm daim duab, koj xav tau pes tsawg lub ntsiab lus? Zoo, peb paub tias qhov no yog ib txoj haujlwm linear uas tsim cov kab thiab yog li nws xav tau tsawg kawg yog ob lub ntsiab lus. Tom ntej no, xav txog kev ua haujlwm polynomial nrog qib ob, . Qhov no yog ib qho kev ua quadratic, yog li tsawg kawg yog peb lub ntsiab lus yuav tsum tau ua rau daim duab. Yuav ua li cas yog ib tug polynomial nrog degree peb? Tsawg kawg yog plaub lub ntsiab lus. Thiab lwm yam thiab lwm yam.
Qhov zoo tshaj plaws txog cov cuab yeej no yog tias, muab cov degree ntawm polynomial muaj nuj nqi thiab tsawg kawg cov ntsiab lus, peb tuaj yeem muab cov ntsiab lus ntxiv rau qhov kev ua haujlwm polynomial no. Peb hu lub extrapolation ntawm cov ntsiab lus ntxiv polynomial interpolation.
Ua ib qho zais cia
Tej zaum koj twb paub lawm tias qhov no yog qhov twg Shamir lub tswv yim ntse los ua si. Cia peb hais peb qhov zais cia Yog . Peb tuaj yeem tig mus rau qhov taw tes ntawm daim duab thiab tuaj nrog polynomial muaj nuj nqi nrog degree , uas txaus siab rau qhov no. Cia peb nco ntsoov koj li ntawd yuav yog peb qhov chaw pib ntawm qhov yuav tsum tau muaj, yog li yog tias peb teeb tsa qhov pib mus rau peb ntu, peb yuav tsum xaiv qhov muaj nuj nqi polynomial nrog qib ob.
Peb polynomial yuav muaj daim ntawv qhov twg ΠΈ - randomly xaiv tus lej zoo. Peb tsuas yog tsim lub polynomial nrog degree , qhov twg free coefficient - Nov yog peb qhov zais cia , thiab rau txhua tus tom ntej cov nqe lus muaj ib tug randomly xaiv zoo coefficient. Yog peb rov qab mus rau qhov qub piv txwv thiab xav tias , tom qab ntawd peb tau txais cov haujlwm .
Ntawm no peb tuaj yeem tsim cov khoom tawg los ntawm kev sib txuas cim integers nyob rau hauv qhov twg (vim nws yog peb qhov zais cia). Hauv qhov piv txwv no, peb xav faib plaub ntu nrog qhov pib ntawm peb, yog li peb randomly tsim cov ntsiab lus thiab xa ib qho taw tes rau txhua tus ntawm plaub tus neeg ntseeg siab, cov neeg saib xyuas ntawm tus yuam sij. Peb kuj qhia rau tib neeg paub li ntawd , vim qhov no suav tias yog cov ntaub ntawv pej xeem thiab tsim nyog rau kev rov qab los .
Rov qab qhov zais cia
Peb twb tau tham txog lub tswvyim ntawm polynomial interpolation thiab yuav ua li cas nws underlies Shamir qhov pib txheej txheem . Thaum twg peb ntawm plaub tus neeg saib xyuas xav rov qab los , lawv tsuas xav tau interpolate nrog nws tus kheej cov ntsiab lus tshwj xeeb. Ua li no, lawv tuaj yeem txiav txim siab lawv cov ntsiab lus thiab xam cov Lagrange interpolation polynomial siv cov qauv hauv qab no. Yog hais tias qhov kev zov me nyuam pom tseeb rau koj dua li kev ua lej, ces pi yog qhov tseem ceeb ntawm tus neeg teb xov tooj for, uas multiplies tag nrho cov txiaj ntsig, thiab sigma yog for, uas ntxiv txhua yam.
ntawm peb tuaj yeem daws nws zoo li qhov no thiab xa rov qab peb qhov kev ua haujlwm polynomial qub:
Txij li thaum peb paub qhov ntawd , rov qab ua tau yooj yim:
Siv cov lej lej tsis zoo
Txawm hais tias peb tau ua tiav siv Shamir lub tswv yim yooj yim , peb tshuav ib qho teeb meem uas peb tsis quav ntsej txog tam sim no. Peb txoj haujlwm polynomial siv cov lej lej tsis zoo. Nco ntsoov tias rau txhua qhov ntxiv tus neeg tawm tsam tau txais ntawm daim duab ntawm peb txoj haujlwm, muaj tsawg dua rau lwm cov ntsiab lus. Koj tuaj yeem pom qhov no nrog koj tus kheej ob lub qhov muag thaum koj npaj cov ntsiab lus ntau ntxiv rau kev ua haujlwm ntawm ntau tus lej siv cov lej lej. Qhov no yog qhov tsis zoo rau peb lub hom phiaj kev nyab xeeb, vim tias tus neeg tawm tsam yuav tsum paub tsis muaj dab tsi txog thaum lawv muaj tsawg kawg tawg.
Txhawm rau ua kom pom qhov tsis muaj zog ntawm integer arithmetic circuit, xav txog qhov xwm txheej uas tus neeg tawm tsam tau txais ob lub ntsiab lus thiab paub cov ntaub ntawv pej xeem uas . Los ntawm cov ntaub ntawv no nws tuaj yeem txiav txim siab , sib npaug rau ob, thiab ntsaws rau hauv qhov paub qhov tseem ceeb rau hauv cov qauv ΠΈ .
Tus neeg tawm tsam tuaj yeem nrhiav tau , suav :
Txij li thaum peb tau txhais raws li randomly xaiv tus lej zoo, muaj tsawg tsawg ntawm qhov ua tau . Siv cov ntaub ntawv no, tus neeg tawm tsam tuaj yeem txiav txim siab , vim dab tsi ntau dua 5 yuav ua tsis zoo. Qhov no hloov mus rau qhov tseeb txij li thaum peb tau txiav txim siab
Tus neeg tawm tsam tuaj yeem suav cov txiaj ntsig tau hloov Π² :
Nrog txwv kev xaiv rau nws paub meej tias nws yooj yim npaum li cas los xaiv thiab xyuas cov txiaj ntsig . Tsuas muaj tsib txoj kev xaiv ntawm no.
Kev daws qhov teeb meem nrog cov lej lej tsis zoo
Txhawm rau tshem tawm qhov tsis zoo no, Shamir qhia siv cov lej lej, hloov pauv rau qhov twg ΠΈ - cov txheej txheem ntawm txhua tus lej tseem ceeb.
Cia peb nco ntsoov sai npaum li cas modular arithmetic ua haujlwm. Lub moos nrog txhais tes yog ib lub tswv yim paub. Nws siv lub moos uas yog . Sai li lub teev tes hla kaum ob, nws rov qab mus rau ib qho. Ib qho txiaj ntsig zoo ntawm cov kab ke no yog qhov yooj yim los ntawm kev saib lub moos, peb tsis tuaj yeem txiav txim siab pes tsawg lub kiv puag ncig lub teev tes tau ua. Txawm li cas los xij, yog tias peb paub tias lub teev tes tau dhau 12 plaub zaug, peb tuaj yeem txiav txim siab tag nrho cov teev uas tau dhau los siv cov qauv yooj yim. qhov twg yog peb tus divisor (ntawm no ), yog tus coefficient (peb lub sij hawm tus divisor mus rau hauv tus lej qub yam tsis muaj qhov seem, ntawm no ), thiab yog qhov seem, uas feem ntau xa rov qab tus neeg teb xov tooj modulo (ntawm no ). Paub tag nrho cov txiaj ntsig no tso cai rau peb los daws qhov sib npaug rau , tab sis yog peb nco tus coefficient, peb yuav tsis muaj peev xwm rov qab tau tus nqi qub.
Peb tuaj yeem ua kom pom tias qhov no txhim kho kev ruaj ntseg ntawm peb lub tswv yim los ntawm kev siv lub tswv yim rau peb qhov piv txwv yav dhau los thiab siv . Peb txoj haujlwm tshiab polynomial , thiab cov ntsiab lus tshiab . Tam sim no cov neeg tseem ceeb tuaj yeem rov siv dua polynomial interpolation los tsim kho peb txoj haujlwm, tsuas yog lub sijhawm no qhov sib ntxiv thiab kev ua haujlwm sib npaug yuav tsum tau nrog los ntawm kev txo cov modulo. (xws li ).
Siv qhov piv txwv tshiab no, cia peb xav tias tus neeg tawm tsam tau kawm ob ntawm cov ntsiab lus tshiab no, , thiab cov ntaub ntawv pej xeem . Lub sijhawm no, tus neeg tawm tsam, raws li tag nrho cov ntaub ntawv nws muaj, tso tawm cov haujlwm hauv qab no, qhov twg yog cov txheej txheem ntawm tag nrho cov lej zoo, thiab sawv cev rau lub modulus coefficient .
Tam sim no peb tus neeg tawm tsam pom dua , suav :
Ces nws rov sim dua hloov Π² :
Lub sijhawm no nws muaj teeb meem loj. Cov qauv uas ploj lawm , ΠΈ . Txij li thaum muaj tus lej tsis kawg ntawm kev sib txuas ntawm cov hloov pauv no, nws tsis tuaj yeem tau txais cov ntaub ntawv ntxiv.
Kev xav txog kev nyab xeeb
Shamir's secret sharing scheme qhia kev ruaj ntseg los ntawm qhov pom ntawm cov ntaub ntawv kev tshawb xav. Qhov no txhais tau hais tias kev ua lej yog resistant txawm tawm tsam ib tug attacker nrog unlimited suav hwj chim. Txawm li cas los xij, lub Circuit Court tseem muaj ntau yam teeb meem paub.
Piv txwv li, Shamir lub tswv yim tsis tsim fragments yuav tsum tau kuaj, uas yog, tib neeg tuaj yeem tuaj yeem nthuav tawm cov khoom cuav thiab cuam tshuam nrog kev rov qab los ntawm qhov tseeb zais cia. Tus neeg saib xyuas qhov tsis sib haum xeeb nrog cov ntaub ntawv txaus tuaj yeem tsim lwm qhov tawg los ntawm kev hloov pauv ntawm koj tus kheej kev txiav txim siab. Qhov teeb meem no daws tau siv kev txheeb xyuas tsis pub lwm tus paub schemes, xws li Feldman's scheme.
Lwm qhov teeb meem yog tias qhov ntev ntawm cov khoom tawg yog sib npaug rau qhov ntev ntawm cov ntaub ntawv zais cia, yog li qhov ntev ntawm qhov zais cia yog qhov yooj yim los txiav txim siab. Qhov teeb meem no tuaj yeem daws tau los ntawm qhov tsis tseem ceeb padding zais cia nrog tus lej arbitrary mus txog qhov ntev.
Thaum kawg, nws yog ib qho tseem ceeb uas yuav tsum nco ntsoov tias peb qhov kev txhawj xeeb txog kev ruaj ntseg yuav ntev dhau ntawm tus qauv tsim nws tus kheej. Rau lub ntiaj teb cryptographic daim ntawv thov, feem ntau muaj kev hem thawj ntawm sab-channel tawm tsam qhov twg tus neeg tawm tsam sim rho tawm cov ntaub ntawv muaj txiaj ntsig los ntawm daim ntawv thov ua tiav lub sijhawm, caching, tsoo, thiab lwm yam. Yog tias qhov no yog qhov kev txhawj xeeb, yuav tsum tau ua tib zoo saib xyuas thaum lub sijhawm txhim kho los siv kev tiv thaiv kev tiv thaiv xws li kev ua haujlwm thiab kev saib xyuas tas li, tiv thaiv kev nco los ntawm kev khaws cia rau disk, thiab lwm yam kev txiav txim siab uas dhau ntawm cov kab lus no.
Demo
rau Muaj kev sib tham ua qauv qhia ntawm Shamir txoj kev sib qhia zais cia. Ua qauv qhia raws li lub tsev qiv ntawv , uas nws tus kheej yog qhov chaw nres nkoj JavaScript ntawm qhov program nrov . Nco ntsoov tias suav cov nqi loj , ΠΈ tej zaum yuav siv sijhawm me ntsis.
Tau qhov twg los: www.hab.com