Coba skenario ing ngendi sampeyan kudu ngamanake brankas bank. Iki dianggep pancen ora bisa dikalahake tanpa kunci, sing diwenehake ing dina pisanan kerja. Tujuan sampeyan kanggo nyimpen kunci kanthi aman.

Contone, sampeyan mutusake kanggo nyimpen kunci ing sawayah-wayah, nyedhiyakake akses menyang panyimpenan yen perlu. Nanging sampeyan bakal cepet nyadari yen solusi kasebut ora cocog karo praktik, amarga anane fisik sampeyan dibutuhake saben mbukak panyimpenan. Kepiye babagan preian sing dijanjikake? Kajaba iku, pitakonan iki malah luwih medeni: apa yen sampeyan ilang mung tombol?

Kanthi preian, sampeyan mutusake nggawe salinan kunci kasebut lan pasrahake menyang karyawan liyane. Nanging, sampeyan ngerti manawa iki uga ora cocog. Kanthi dobel nomer tombol, sampeyan uga pindho kasempatan nyolong tombol.

Ing desperation, sampeyan numpes duplikat lan mutusaké kanggo pamisah tombol asli ing setengah. Saiki, sampeyan bakal mikir yen rong wong sing dipercaya karo pecahan kunci kudu ana fisik kanggo ngumpulake kunci lan mbukak lemari besi. Iki tegese maling kudu nyolong rong potong, sing kaping pindho luwih angel tinimbang nyolong siji kunci. Nanging, sampeyan bakal ngerti manawa skema iki ora luwih apik tinimbang mung siji tombol, amarga yen ana wong sing ilang setengah kunci, kunci lengkap ora bisa dibalekake.

Masalah bisa ditanggulangi kanthi serangkaian tombol lan kunci tambahan, nanging pendekatan iki bakal mbutuhake kanthi cepet много kunci lan kunci. Sampeyan mutusake manawa desain sing cocog yaiku nuduhake kunci supaya keamanan ora gumantung ing wong siji. Sampeyan uga nyimpulake yen kudu ana sawetara ambang kanggo jumlah pecahan supaya yen siji fragmen ilang (utawa yen ana wong sing preian), kabeh tombol tetep fungsional.

Carane nuduhake rahasia

Jinis skema manajemen kunci iki dipikirake dening Adi Shamir ing taun 1979 nalika nerbitake karyane "Carane Nuduhake Rahasia". Artikel kasebut kanthi ringkes nerangake apa sing diarani skema ambang kanggo mbagi nilai rahasia (kayata kunci kriptografi) kanthi efisien bagean. Banjur, nalika lan mung nalika paling saka bagean nglumpuk, sampeyan bisa kanthi gampang mulihake rahasia .

Saka sudut pandang keamanan, properti penting saka skema iki yaiku manawa panyerang ora ngerti apa-apa kajaba dheweke duwe paling ora. bagean. Malah anane bagean ngirim ora nyedhiyani informasi sembarang. Kita nelpon properti iki keamanan semantik.

Interpolasi polinomial

Skema ambang Shamir dibangun watara konsep interpolasi polinomial. Yen sampeyan ora ngerti konsep iki, iku bener cukup prasaja. Nyatane, yen sampeyan wis nggambar titik ing grafik banjur disambungake karo garis utawa kurva, sampeyan wis nggunakake!

Liwat rong titik sampeyan bisa nggambar jumlah polinomial tanpa wates derajat 2. Kanggo milih siji-sijine, sampeyan butuh titik katelu. Ilustrasi: Wikipedia

Coba polinomial kanthi gelar siji, . Yen sampeyan pengin ngrancang fungsi iki ing grafik, sampeyan butuh pira? Ya, kita ngerti manawa iki minangka fungsi linier sing mbentuk garis lan mula butuh paling ora rong titik. Sabanjure, nimbang fungsi polinomial kanthi derajat loro, . Iki minangka fungsi kuadrat, mula paling ora telung poin sing dibutuhake kanggo ngrancang grafik kasebut. Kepiye babagan polinomial kanthi gelar telu? Paling ora papat poin. Lan sateruse.

Ing bab tenan kelangan babagan sifat iki sing, diwenehi gelar saka fungsi polynomial lan paling titik, kita bisa nurunake TCTerms tambahan kanggo fungsi polynomial iki. Kita nelpon ekstrapolasi saka titik tambahan iki interpolasi polinomial.

Nggawe rahasia

Sampeyan bisa uga wis ngerti yen ing kene rencana pinter Shamir. Ayo ngomong rahasia kita Punika . Kita bisa nguripake menyang titik ing grafik lan teka karo fungsi polinomial kanthi gelar , sing marem titik iki. Ayo kita ngelingi sing bakal dadi batesan pecahan sing dibutuhake, mula yen kita nyetel batesan dadi telung pecahan, kita kudu milih fungsi polinomial kanthi gelar loro.

Polinomial kita bakal duwe wangun ngendi и - wilangan bulat positif sing dipilih kanthi acak. Kita mung mbangun polinomial kanthi gelar , ngendi koefisien free  - Iki rahasia kita , lan kanggo saben sing sakteruse istilah ana koefisien positif sing dipilih kanthi acak. Yen kita bali menyang conto asli lan nganggep , banjur entuk fungsi kasebut .

Ing titik iki kita bisa ngasilake pecahan kanthi nyambungake integer unik ing ngendi (amarga iku rahasia kita). Ing conto iki, kita pengin nyebarake papat fragmen kanthi batesan telung, supaya kita ngasilake poin kanthi acak lan ngirim siji titik kanggo saben wong papat dipercaya, kustodian tombol. Kita uga supaya wong ngerti , amarga iki dianggep informasi umum lan perlu kanggo Recovery .

Mbalekake rahasia

Kita wis ngrembug babagan konsep interpolasi polinomial lan carane ndasari skema ambang Shamir . Nalika ana telu saka papat wali sing pengin dipulihake , dheweke mung kudu interpolasi karo titik unik dhewe. Kanggo nindakake iki, padha bisa nemtokake titik lan ngitung polinomial interpolasi Lagrange nggunakake rumus ing ngisor iki. Yen pemrograman luwih jelas tinimbang matematika, mula pi minangka operator for, kang multiplies kabeh asil, lan sigma punika for, sing nambah kabeh.

ing kita bisa ngatasi kaya iki lan ngasilake fungsi polinomial asli:

Amarga kita ngerti , pulih rampung mung:

Nggunakake aritmetika integer sing ora aman

Sanajan kita wis kasil ngetrapake ide dhasare Shamir , kita kiwa karo masalah sing wis ora digatekake nganti saiki. Fungsi polinomial kita nggunakake aritmetika integer sing ora aman. Elinga yen saben titik tambahan sing ditampa panyerang ing grafik fungsi kita, kemungkinan luwih sithik kanggo titik liyane. Sampeyan bisa ndeleng iki kanthi mripat dhewe nalika sampeyan ngrancang jumlah poin sing saya tambah kanggo fungsi polinom nggunakake aritmetika integer. Iki kontraproduktif kanggo tujuan keamanan sing wis ditemtokake, amarga panyerang kudu ngerti apa-apa nganti paling ora pecahan.

Kanggo nduduhake kekirangan sirkuit aritmetika integer, nimbang skenario ing ngendi panyerang entuk rong poin. lan ngerti informasi umum sing . Saka informasi kasebut bisa disimpulake , padha karo loro, lan plug ing nilai dikenal menyang rumus и .

Penyerang banjur bisa nemokake , ngetang :

Awit kita wis ditetepake minangka wilangan bulat positif sing dipilih kanthi acak, ana jumlah winates sing bisa . Nggunakake informasi iki, panyerang bisa nyimpulake , wiwit apa luwih saka 5 bakal nindakake negatif. Iki dadi bener amarga kita wis nemtokake

Penyerang banjur bisa ngetung nilai sing bisa ditindakake ngganti в :

Kanthi opsi winates kanggo dadi cetha carane gampang kanggo milih lan mriksa nilai . Mung ana limang pilihan ing kene.

Ngatasi masalah karo aritmetika integer sing ora aman

Kanggo ngilangi kerentanan iki, Shamir nyaranake nggunakake aritmetika modular, ngganti ing ngendi и - pesawat kabeh nomer prima.

Ayo cepet ngelingi cara kerja aritmetika modular. Jam karo tangan minangka konsep sing akrab. Dheweke nggunakake jam tangan sing . Sanalika jarum jam liwat rolas, bali menyang siji. Properti menarik saka sistem iki yaiku mung kanthi ndeleng jam, kita ora bisa nyimpulake pirang-pirang revolusi sing digawe tangan jam. Nanging, yen kita ngerti yen jarum jam wis liwati 12 kaping papat, kita bisa nemtokake jumlah jam sing wis liwati nggunakake rumus prasaja. ngendi  minangka pembagi kita (kene ),  yaiku koefisien (kaping pirang-pirang pembagi mlebu menyang nomer asli tanpa sisa, ing kene ), lan  minangka sisa, sing biasane ngasilake telpon operator modulo (kene ). Ngerti kabeh nilai kasebut ngidini kita ngrampungake persamaan kasebut , nanging yen kita kantun koefisien, kita ora bakal bisa mulihake nilai asli.

Kita bisa nduduhake carane iki nambah keamanan skema kita kanthi nggunakake skema kasebut ing conto sadurunge lan nggunakake . Fungsi polinomial anyar kita , lan TCTerms anyar . Saiki penjaga kunci bisa maneh nggunakake interpolasi polinomial kanggo mbangun maneh fungsi kita, mung wektu iki operasi tambahan lan multiplikasi kudu diiringi pengurangan modulo. (eg ).

Nggunakake conto anyar iki, ayo nganggep manawa panyerang sinau loro poin anyar kasebut, , lan informasi umum . Wektu iki, penyerang, adhedhasar kabeh informasi sing diduweni, ngasilake fungsi ing ngisor iki, ing ngendi  iku pesawat kabeh wilangan bulat positif, lan nuduhake koefisien modulus .

Saiki penyerang kita nemokake maneh , ngitung :

Banjur dheweke nyoba maneh ngganti в :

Wektu iki dheweke duwe masalah serius. Rumus ilang nilai , и . Amarga ana kombinasi tanpa wates saka variabel kasebut, dheweke ora bisa entuk informasi tambahan.

Pertimbangan Keamanan

Skema enggo bareng rahasia Shamir nyaranake keamanan saka sudut pandang teori informasi. Iki tegese matématika tahan sanajan marang panyerang kanthi daya komputasi tanpa wates. Nanging, sirkuit isih ngemot sawetara masalah sing dikenal.

Contone, skema Shamir ora nggawe pecahan kanggo dipriksa, yaiku, wong bisa kanthi bebas nampilake pecahan palsu lan ngganggu pemulihan rahasia sing bener. Penjaga fragmen sing musuhan kanthi informasi sing cukup malah bisa ngasilake fragmen liyane kanthi ngganti ing discretion dhewe. Masalah iki ditanggulangi nggunakake skema sharing rahasia sing bisa diverifikasi, kayata rencana Feldman.

Masalah liyane yaiku dawa fragmen apa wae sing padha karo dawa rahasia sing cocog, mula dawa rahasia kasebut gampang ditemtokake. Masalah iki bisa ditanggulangi kanthi sepele padding rahasia karo nomer kasepakatan nganti dawa tetep.

Pungkasan, penting kanggo dicathet yen masalah keamanan bisa ngluwihi desain kasebut. Kanggo aplikasi kriptografi nyata, asring ana ancaman serangan saluran sisih ing ngendi panyerang nyoba ngekstrak informasi sing migunani saka wektu eksekusi aplikasi, cache, kacilakan, lsp. Yen ana masalah, kudu dipikirake kanthi ati-ati sajrone pangembangan nggunakake langkah-langkah protèktif kayata fungsi lan telusuran wektu sing tetep, nyegah memori disimpen ing disk, lan sawetara pertimbangan liyane sing ora ana ing ruang lingkup artikel iki.

Demo

Ing kaca iki Ana demonstrasi interaktif skema sharing rahasia Shamir. Demonstrasi adhedhasar perpustakaan ssss-js, sing dhewe minangka port JavaScript saka program populer ssss. Elinga yen ngitung nilai gedhe , и bisa uga njupuk sawetara wektu.

Source: www.habr.com