Konsidere yon senaryo kote ou bezwen an sekirite yon vout labank. Li konsidere kòm absoliman inexpugnable san yo pa yon kle, yo ba ou nan premye jou travay la. Objektif ou se byen estoke kle a.

Ann di ou deside kenbe kle a avèk ou tout tan, bay aksè nan depo a jan sa nesesè. Men, ou pral byen vit reyalize ke yon solisyon konsa pa echèl byen nan pratik, paske prezans fizik ou obligatwa chak fwa ou louvri depo a. E vakans yo te pwomèt ou a? Anplis de sa, kesyon an se menm plis pè: e si ou pèdi sèl kle ou a?

Avèk vakans ou nan tèt ou, ou deside fè yon kopi kle a epi konfye li nan yon lòt anplwaye. Sepandan, ou konprann ke sa a se pa ideyal tou. Lè w double kantite kle, ou double tou chans pou vòl kle.

Nan dezespwa, ou detwi kopi a epi deside divize kle orijinal la nan mwatye. Koulye a, ou ta panse ke de moun ou fè konfyans ak fragman kle yo ta dwe prezan fizikman kolekte kle a epi louvri vout la. Sa vle di ke yon vòlè bezwen vòlè de moso, ki se de fwa pi difisil ke vòlè yon sèl kle. Sepandan, byento ou reyalize ke konplo sa a pa pi bon pase yon sèl kle, paske si yon moun pèdi mwatye yon kle, kle a plen pa ka refè.

Pwoblèm nan ka rezoud ak yon seri de kle adisyonèl ak kadna, men apwòch sa a pral byen vit mande pou много kle ak kadna. Ou deside ke konsepsyon ideyal la ta dwe pataje kle a pou sekirite pa konte antyèman sou yon sèl moun. Ou konkli tou ke dwe gen kèk papòt pou kantite fragman pou ke si yon fragman pèdi (oswa si yon moun ale an vakans), tout kle a rete fonksyonèl.

Ki jan yo pataje yon sekrè

Sa a ki kalite konplo jesyon kle te panse sou pa Adi Shamir an 1979 lè li te pibliye travay li "Ki jan yo pataje yon sekrè". Atik la yon ti tan eksplike sa yo rele an konplo papòt pou byen divize yon valè sekrè (tankou yon kle kriptografik) an pati. Lè sa a, lè ak sèlman lè omwen nan pati yo reyini, ou ka fasilman retabli sekrè a .

Soti nan yon pwen de vi sekirite, yon pwopriyete enpòtan nan konplo sa a se ke atakè a pa ta dwe konnen absoliman anyen sof si li gen omwen pati. Menm prezans la pati yo pa ta dwe bay okenn enfòmasyon. Nou rele pwopriyete sa a sekirite semantik.

Entèpolasyon polinòm

Shamir threshold scheme bati alantou konsèp la entèpolasyon polinòm. Si ou pa abitye ak konsèp sa a, li aktyèlman byen senp. An reyalite, si ou te janm trase pwen sou yon graf epi konekte yo ak liy oswa koub, ou te deja itilize li!

Atravè de pwen ou ka trase yon kantite polinòm san limit nan degre 2. Pou chwazi youn nan sèlman nan yo, ou bezwen yon twazyèm pwen. Ilistrasyon: Wikipedya

Konsidere yon polinòm ki gen yon degre, . Si ou vle trase fonksyon sa a sou yon graf, konbyen pwen ou bezwen? Oke, nou konnen ke sa a se yon fonksyon lineyè ki fòme yon liy e konsa li bezwen omwen de pwen. Apre sa, konsidere yon fonksyon polinòm ak degre de, . Sa a se yon fonksyon kwadratik, kidonk omwen twa pwen yo oblije trase graf la. Kouman sou yon polinòm ki gen degre twa? Omwen kat pwen. Ak sou sa ak sou sa.

Bagay la vrèman fre sou pwopriyete sa a se ke, bay degre nan fonksyon an polinòm ak omwen pwen, nou ka tire pwen adisyonèl pou fonksyon polinòm sa a. Nou rele ekstrapolasyon pwen adisyonèl sa yo entèpolasyon polinòm.

Fè moute yon sekrè

Ou ka deja reyalize ke sa a se kote konplo entelijan Shamir a antre nan jwèt. Ann di sekrè nou an - Eske . Nou ka vire nan yon pwen sou graf la epi vini ak yon fonksyon polinòm ak degre , ki satisfè pwen sa a. Se pou nou sonje sa pral papòt nou an nan fragman obligatwa yo, kidonk si nou mete papòt la nan twa fragman, nou dwe chwazi yon fonksyon polinòm ak degre de.

Polinòm nou an ap gen fòm nan kote и — owaza chwazi nonm antye relatif pozitif. Nou jis konstwi yon polinòm ak degre , kote koyefisyan a gratis  - Sa a se sekrè nou an , ak pou chak nan sa ki vin apre yo tèm gen yon koyefisyan pozitif chwazi owaza. Si nou retounen nan egzanp orijinal la epi sipoze sa , Lè sa a, nou jwenn fonksyon an .

Nan pwen sa a nou ka jenere fragman pa konekte nonb antye relatif inik nan kote (paske se sekrè nou an). Nan egzanp sa a, nou vle distribye kat fragman ak yon papòt twa, kidonk nou jenere pwen owaza. epi voye yon pwen bay chak nan kat moun ou fè konfyans yo, gadyen kle a. Nou tou fè moun konnen sa , piske sa a konsidere kòm enfòmasyon piblik epi li nesesè pou rekiperasyon an .

Rekipere sekrè a

Nou te deja diskite konsèp nan entèpolasyon polinòm ak fason li kache konplo papòt Shamir la. . Lè nenpòt twa nan kat administratè yo vle retabli , yo sèlman bezwen entèpole ak pwòp pwen inik li yo. Pou fè sa, yo ka detèmine pwen yo epi kalkile polinòm entèpolasyon Lagrange lè l sèvi avèk fòmil sa a. Si pwogramasyon pi klè pou ou pase matematik, Lè sa a, pi se esansyèlman yon operatè for, ki miltipliye tout rezilta, ak sigma se for, ki ajoute tout bagay.

Nan nou ka rezoud li tankou sa a epi retounen fonksyon polinòm orijinal nou an:

Depi nou konnen sa , rekiperasyon fè tou senpleman:

Sèvi ak aritmetik nonb antye ki pa an sekirite

Malgre ke nou te aplike avèk siksè lide debaz Shamir la , nou rete ak yon pwoblèm ke nou te inyore jiska kounye a. Fonksyon polinòm nou an itilize aritmetik nonb antye ki pa an sekirite. Remake byen ke pou chak pwen adisyonèl yon atakè jwenn sou graf fonksyon nou an, gen mwens posiblite pou lòt pwen. Ou ka wè sa ak pwòp je ou lè ou trase yon kantite pwen ki ogmante pou yon fonksyon polinòm lè l sèvi avèk aritmetik nonb antye relatif. Sa a se kontreproduktiv nan objektif sekirite deklare nou an, paske atakè a ta dwe konnen absoliman anyen jiskaske yo gen omwen fragman.

Pou demontre kijan sikwi aritmetik nonb antye relatif la fèb, konsidere yon senaryo kote yon atakè te jwenn de pwen. epi li konnen enfòmasyon piblik sa . Apati enfòmasyon sa a li ka dedwi , egal a de, epi ploge valè yo li te ye nan fòmil la и .

Lè sa a, atakè a ka jwenn , konte :

Depi nou te defini kòm nonm antye ki pozitif chwazi owaza, gen yon kantite limite posib . Sèvi ak enfòmasyon sa a, yon atakè ka dedwi , depi nenpòt bagay ki pi gran pase 5 ap fè negatif. Sa a vin vre depi nou te detèmine

Lè sa a, atakè a ka kalkile valè posib yo , ranplase в :

Ak opsyon limite pou li vin klè ki jan li fasil pou chwazi ak tcheke valè yo . Genyen sèlman senk opsyon isit la.

Rezoud pwoblèm nan ak aritmetik nonb antye ki pa an sekirite

Pou elimine vilnerabilite sa a, Shamir sijere lè l sèvi avèk modilè aritmetik, ranplase sou kote и — ansanm tout nonb premye yo.

Ann sonje byen vit kijan aritmetik modilè ap travay. Yon revèy ak men se yon konsèp abitye. Li sèvi ak yon mont ki se . Le pli vit ke men lè a pase douz, li retounen nan yon sèl. Yon pwopriyete enteresan nan sistèm sa a se ke tou senpleman lè nou gade nan revèy la, nou pa ka dedwi konbyen revolisyon lan lè a te fè. Sepandan, si nou konnen ke lè a te pase 12 kat fwa, nou ka konplètman detèmine kantite èdtan ki te pase lè l sèvi avèk yon fòmil senp. kote  se divizyon nou an (isit la ),  se koyefisyan an (konbyen fwa divizè a antre nan nimewo orijinal la san rès, isit la ), yon  se rès la, ki anjeneral retounen yon apèl operatè modulo (isit la ). Konnen tout valè sa yo pèmèt nou rezoud ekwasyon an pou , men si nou rate koyefisyan an, nou p'ap janm kapab retabli valè orijinal la.

Nou kapab demontre ki mannyer sa i amelyor sekirite nou konplo par aplik sa bann legzanp avan e nou servi . Nouvo fonksyon polinòm nou an , ak nouvo pwen yo . Koulye a, gadyen kle yo ka yon lòt fwa ankò itilize entèpolasyon polinòm pou rekonstwi fonksyon nou an, se sèlman fwa sa a adisyon ak operasyon miltiplikasyon yo dwe akonpaye pa rediksyon modulo. (eg ).

Sèvi ak nouvo egzanp sa a, an n sipoze atakè a te aprann de nan nouvo pwen sa yo, , ak enfòmasyon piblik . Fwa sa a, atakè a, ki baze sou tout enfòmasyon li genyen, pwodiksyon fonksyon sa yo, kote  se ansanm tout antye pozitif, ak reprezante koyefisyan modil la .

Koulye a, atakè nou an jwenn ankò , kalkile :

Lè sa a, li eseye ankò , ranplase в :

Fwa sa a li gen yon pwoblèm grav. Fòmil ki manke valè , и . Piske gen yon kantite enfini nan konbinezon varyab sa yo, li pa ka jwenn okenn enfòmasyon adisyonèl.

Konsiderasyon sekirite

Konplo pataje sekrè Shamir sijere sekirite nan pwen de vi nan teyori enfòmasyon. Sa vle di ke matematik la rezistan menm kont yon atakè ki gen pouvwa enfòmatik san limit. Sepandan, kous la toujou gen plizyè pwoblèm li te ye.

Pou egzanp, konplo Shamir a pa kreye fragman yo dwe tcheke, se sa ki, moun ka lib prezante fragman fo ak entèfere ak rekiperasyon an nan sekrè ki kòrèk la. Yon gadyen fragman ostil ki gen ase enfòmasyon ka menm pwodui yon lòt fragman lè li chanje nan pwòp diskresyon ou. Pwoblèm sa a rezoud lè l sèvi avèk plan pataje sekrè ki verifye, tankou konplo Feldman a.

Yon lòt pwoblèm se ke longè nenpòt fragman egal a longè sekrè ki koresponn lan, kidonk longè sekrè a fasil pou detèmine. Pwoblèm sa a ka rezoud pa trivial padding sekrè ak nimewo abitrè jiska yon longè fiks.

Finalman, li enpòtan sonje ke enkyetid sekirite nou yo ka pwolonje pi lwen pase konsepsyon an tèt li. Pou aplikasyon kriptografik nan mond reyèl la, souvan gen menas atak sou bò kote yon atakè ap eseye ekstrè enfòmasyon itil nan tan ekzekisyon aplikasyon an, kachèt, aksidan, elatriye. Si sa a se yon enkyetid, yo ta dwe pran anpil prekosyon pandan devlopman nan sèvi ak mezi pwoteksyon tankou fonksyon ak rechèch tan konstan, anpeche memwa yo te sove sou disk, ak yon kantite lòt konsiderasyon ki pi lwen pase sijè ki abòde lan atik sa a.

Dine

Sou paj sa a Gen yon demonstrasyon entèaktif nan konplo pataje sekrè Shamir la. Demonstrasyon ki baze sou bibliyotèk la ssss-js, ki li menm se yon pò JavaScript nan pwogram popilè a aaaa. Remake byen ke kalkile gwo valè , и ka pran kèk tan.

Sous: www.habr.com