Pertimbangkeun skenario dimana anjeun kedah ngamankeun kolong bank. Hal ieu dianggap kacida impregnable tanpa konci, nu dibikeun dina dinten pisan mimiti gawé. Tujuanana anjeun pikeun nyimpen konci anu aman.
Anggap anjeun mutuskeun pikeun nyimpen konci sareng anjeun unggal waktos, nyayogikeun aksés kana panyimpenan upami diperyogikeun. Tapi anjeun bakal gancang nyadar yén solusi sapertos henteu skala ogé dina prakna, sabab ayana fisik anjeun diperlukeun unggal waktos Anjeun muka gudang. Kumaha upami liburan anu anjeun janjikeun? Salaku tambahan, patarosan langkung pikasieuneun: kumaha upami anjeun kaleungitan hiji-hijina konci anjeun?
Kalayan liburan anjeun dina pikiran, anjeun mutuskeun ngadamel salinan konci sareng mercayakeun ka karyawan anu sanés. Nanging, anjeun ngartos yén ieu ogé henteu idéal. Ku duka kali jumlah konci, Anjeun ogé ganda kasempetan maling konci.
Dina desperation, Anjeun ngancurkeun duplikat jeung mutuskeun pikeun dibeulah konci aslina dina satengah. Ayeuna, anjeun bakal nyangka yén dua jalma anu dipercaya sareng fragmen konci kedah hadir sacara fisik pikeun ngumpulkeun konci sareng muka kolong. Ieu ngandung harti yén maling kudu maok dua lembar, nu dua kali leuwih hese ti maok hiji konci. Najan kitu, anjeun geura-giru nyadar yén skéma ieu teu leuwih hadé ti ngan hiji konci, sabab lamun batur leungit satengah konci, konci pinuh teu bisa pulih.
Masalahna bisa direngsekeun ku runtuyan kenop tambahan sarta konci, tapi pendekatan ieu bakal gancang merlukeun много konci jeung konci. Anjeun mutuskeun yén desain idéal bakal babagi konci ambéh kaamanan teu ngandelkeun sagemblengna ka hiji jalma. Anjeun ogé nyimpulkeun yén kedah aya sababaraha bangbarung pikeun jumlah fragmen supados upami hiji fragmen leungit (atanapi upami hiji jalma nuju liburan), sadayana konci tetep fungsional.
Kumaha babagi rusiah
Jenis skéma manajemén konci ieu panginten ku Adi Shamir di 1979 nalika anjeunna nyebarkeun karyana . Artikel sakeudeung ngajelaskeun disebut 
skéma bangbarung pikeun épisién ngabagi nilai rahasia (sapertos konci kriptografi) kana bagian. Lajeng, iraha jeung ngan lamun sahenteuna ti bagian nu dirakit, anjeun bisa kalayan gampang balikkeun rusiah .
Tina sudut pandang kaamanan, sipat penting tina skéma ieu nyaéta yén panyerang henteu kedah terang naon waé kecuali anjeunna gaduh sahenteuna bagian. Komo ayana bagian teu kudu nyadiakeun informasi nanaon. Urang nelepon sipat ieu kaamanan semantis.
Interpolasi polinomial
Skéma bangbarung Shamir diwangun sabudeureun konsep interpolasi polinomial. Mun anjeun teu wawuh jeung konsep ieu, éta sabenerna cukup basajan. Kanyataanna, upami anjeun kantos ngagambar titik dina grafik teras nyambungkeunana sareng garis atanapi kurva, anjeun parantos nganggo éta!
Ngaliwatan dua titik anjeun tiasa ngagambar jumlah taya polynomials gelar 2. Pikeun milih hiji-hijina ti aranjeunna, anjeun peryogi titik katilu. Ilustrasi:
Pertimbangkeun polinomial kalayan gelar hiji, . Upami anjeun hoyong plot fungsi ieu dina grafik, sabaraha titik anjeun peryogi? Nya, urang terang yén ieu mangrupikeun fungsi linier anu ngabentuk garis sahingga peryogi sahenteuna dua titik. Salajengna, mertimbangkeun fungsi polinomial kalayan gelar dua, . Ieu fungsi kuadrat, jadi sahenteuna tilu titik diperlukeun pikeun plot grafik. Kumaha upami polinomial kalayan gelar tilu? Sahenteuna opat titik. Jeung saterusna jeung saterusna.
Hal anu saé pisan ngeunaan sipat ieu nyaéta, upami darajat fungsi polinomial sareng sahenteuna titik, urang bisa nurunkeun titik tambahan pikeun fungsi polynomial ieu. Urang nelepon extrapolation tina titik tambahan ieu interpolasi polinomial.
Nyieun rusiah
Anjeun panginten parantos sadar yén ieu mangrupikeun skéma pinter Shamir. Sebutkeun rusiah urang - eta . Urang bisa ngahurungkeun ka titik dina grafik sarta datang nepi ka hiji fungsi polynomial kalawan gelar , nu satisfies titik ieu. Hayu urang ngingetan yén bakal bangbarung urang tina fragmen diperlukeun, jadi lamun urang nyetel bangbarung ka tilu fragmen, urang kudu milih hiji fungsi polynomial kalawan gelar dua.
polynomial urang bakal boga formulir dimana и - wilangan bulat positif dipilih acak. Kami ngan ukur ngawangun polinomial kalayan gelar , dimana koefisien bébas - Ieu rusiah urang , sareng pikeun tiap anu salajengna istilah aya koefisien positif dipilih acak. Lamun urang balik deui ka conto aslina tur nganggap éta , lajeng urang meunang fungsi .
Dina titik ieu urang bisa ngahasilkeun fragmen ku nyambungkeun integer unik dina dimana (sabab éta rusiah urang). Dina conto ieu, urang rék ngadistribusikaeun opat fragmen kalawan bangbarung tilu, jadi urang acak ngahasilkeun titik sarta ngirimkeun hiji titik ka unggal opat jalma dipercaya, nu custodians sahiji konci. Urang ogé ngantep jalma terang éta , Kusabab ieu dianggap informasi umum sarta diperlukeun pikeun recovery .
Pulihkeun rusiah
Kami parantos ngabahas konsép interpolasi polinomial sareng kumaha éta ngadasarkeun skéma ambang Shamir . Sabot tilu ti opat wali rék mulangkeun , aranjeunna ngan perlu interpolate kalawan titik unik sorangan. Jang ngalampahkeun ieu, maranéhna bisa nangtukeun titik maranéhanana jeung ngitung polinomial interpolasi Lagrange ngagunakeun rumus ieu di handap. Upami pemrograman langkung jelas pikeun anjeun tibatan matematika, maka pi dasarna mangrupikeun operator for, nu multiplies sadayana hasil, sarta sigma nyaeta for, anu nambihan sadayana.
di urang tiasa ngajawabna sapertos kieu sareng mulangkeun fungsi polinomial asli urang:
Kusabab urang terang éta , pamulihan dipigawé saukur:
Ngagunakeun aritmetika integer anu teu aman
Sanajan urang geus hasil nerapkeun gagasan dasar Shamir , urang tinggalkeun masalah anu ku urang teu dipalire nepi ka ayeuna. Fungsi polinomial urang ngagunakeun aritmatika integer anu teu aman. Catet yén pikeun unggal titik tambahan anu ditampi ku panyerang dina grafik fungsi urang, aya kamungkinan langkung sakedik pikeun titik-titik sanés. Anjeun tiasa ningali ieu ku panon anjeun nyalira nalika anjeun ngarencanakeun paningkatan jumlah titik pikeun fungsi polinomial nganggo aritmetika integer. Ieu kontraproduktif pikeun tujuan kaamanan anu kami nyatakeun, sabab panyerang kedah terang nanaon dugi ka gaduh sahenteuna sempalan.
Pikeun nunjukkeun kumaha lemahna sirkuit aritmatika integer, pertimbangkeun skénario dimana panyerang nampi dua titik. sareng terang inpormasi umum éta . Tina inpormasi ieu anjeunna tiasa nyimpulkeun , sarua jeung dua, sarta nyolok dina nilai dipikawanoh kana rumus и .
Panyerang teras tiasa mendakan , ngitung :
Kusabab urang geus ngartikeun salaku wilangan bulat positif dipilih acak, aya sababaraha kawates kamungkinan . Ngagunakeun informasi ieu, hiji lawan bisa deduce , saprak nanaon gede ti 5 bakal ngalakukeun négatip. Ieu tétéla leres saprak urang geus ditangtukeun
Panyerang teras tiasa ngitung nilai anu mungkin ngagantikeun в :
Kalawan pilihan kawates pikeun janten jelas kumaha gampang éta pikeun milih jeung pariksa nilai . Aya ngan lima pilihan di dieu.
Ngarengsekeun masalah sareng aritmetika integer anu teu aman
Pikeun ngaleungitkeun kerentanan ieu, Shamir nyarankeun ngagunakeun arithmetic modular, ngagentos dina dimana и - susunan sadaya wilangan prima.
Hayu urang gancang nginget kumaha aritmatika modular jalan. Hiji jam jeung leungeun mangrupakeun konsép akrab. Manéhna ngagunakeun arloji éta . Pas jarum jam ngaliwatan dua belas, éta balik deui ka hiji. Hiji sipat metot tina sistem ieu nu saukur ku nempo jam, urang teu bisa deduce sabaraha révolusi leungeun jam geus dijieun. Sanajan kitu, lamun urang nyaho yén jarum jam geus kaliwat 12 opat kali, urang sagemblengna bisa nangtukeun jumlah jam nu geus kaliwat ngagunakeun rumus basajan. dimana nyaeta divisor urang (di dieu ), nyaeta koefisien (sabaraha kali divisor asup kana angka aslina tanpa sésana, di dieu ), Jeung nyaeta sésana, nu biasana mulih panggero operator modulo (di dieu ). Nyaho sadayana nilai ieu ngamungkinkeun urang pikeun ngajawab persamaan , Tapi lamun urang sono koefisien, urang moal bisa mulangkeun nilai aslina.
Urang tiasa nunjukkeun kumaha ieu ningkatkeun kaamanan skéma urang ku cara nerapkeun skéma kana conto anu saacanna sareng nganggo . Fungsi polinomial anyar urang , jeung titik anyar . Ayeuna penjaga konci tiasa sakali deui nganggo interpolasi polinomial pikeun ngarekonstruksikeun fungsi urang, ngan waktos ieu operasi tambah sareng multiplikasi kedah dibarengan ku réduksi modulo. (upamana) ).
Ngagunakeun conto anyar ieu, hayu urang nganggap yén panyerang diajar dua titik anyar ieu, , jeung informasi umum . Waktos ieu, panyerang, dumasar kana sadaya inpormasi anu anjeunna gaduh, ngahasilkeun fungsi di handap ieu, dimana nyaéta set sadaya wilangan bulat positif, jeung ngagambarkeun koefisien modulus .
Ayeuna panyerang urang mendakan deui , ngitung :
Lajeng anjeunna nyobian deui ngagantikeun в :
Waktos ieu anjeunna ngagaduhan masalah anu serius. Rumus leungit nilai , и . Kusabab aya hiji angka tanpa wates of kombinasi variabel ieu, anjeunna teu bisa ménta sagala informasi tambahan.
Pertimbangan Kaamanan
Skéma babagi rusiah Shamir nunjukkeun kaamanan ti sudut pandang téori informasi. Ieu ngandung harti yén matématika tahan sanajan ngalawan panyerang kalayan kakuatan komputasi anu henteu terbatas. Sanajan kitu, sirkuit masih ngandung sababaraha isu dipikawanoh.
Contona, skéma Shamir teu nyieun fragmen pikeun dipariksa, nyaeta, jalma kalawan bébas bisa nampilkeun fragmen palsu tur ngaganggu recovery tina rusiah bener. Penjaga fragmen anu mumusuhan sareng inpormasi anu cukup bahkan tiasa ngahasilkeun fragmen anu sanés ku ngarobih dina kawijaksanaan anjeun sorangan. Masalah ieu direngsekeun ngagunakeun skéma babagi rusiah verifiable, sapertos skéma Feldman.
masalah sejen nyaeta panjang fragmen nu mana wae nu sarua jeung panjang rusiah pakait, jadi panjang rusiah gampang pikeun nangtukeun. masalah ieu bisa direngsekeun ku trivial padding rusiah kalawan angka wenang nepi ka panjangna tetep.
Tungtungna, hal anu penting pikeun dicatet yén masalah kaamanan urang bisa manjangkeun saluareun desain sorangan. Pikeun aplikasi kriptografi dunya nyata, sering aya ancaman serangan saluran sisi dimana panyerang nyobian nimba inpormasi mangpaat tina waktos palaksanaan aplikasi, cache, kacilakaan, jsb. Upami ieu mangrupikeun perhatian, pertimbangan ati-ati kedah dipasihkeun salami pangwangunan pikeun ngagunakeun ukuran pelindung sapertos fungsi sareng pamariksaan waktos konstan, nyegah mémori disimpen kana disk, sareng sajumlah pertimbangan sanés anu saluareun ruang lingkup tulisan ieu.
Demo
on Aya démo interaktif ngeunaan skéma babagi rusiah Shamir. Demonstrasi dumasar kana perpustakaan , nu sorangan mangrupakeun port JavaScript tina program populér . Catet yén ngitung nilai badag , и bisa nyandak bari.
sumber: www.habr.com