Pertimbangkan skenario ketika perlu untuk memastikan keamanan brankas bank. Itu dianggap benar-benar ditembus tanpa kunci, yang diberikan kepada Anda pada hari pertama kerja. Tujuan Anda adalah menyimpan kunci dengan aman.

Misalkan Anda memutuskan untuk menyimpan kunci itu sepanjang waktu, memberikan akses ke toko sesuai kebutuhan. Tetapi Anda akan segera menyadari bahwa solusi seperti itu dalam praktiknya tidak berskala secara normal, karena setiap kali Anda memerlukan kehadiran fisik Anda untuk membuka repositori. Bagaimana dengan liburan yang dijanjikan? Selain itu, pertanyaannya bahkan lebih menakutkan: bagaimana jika Anda kehilangan satu kunci?

Dengan memikirkan liburan, Anda memutuskan untuk membuat salinan kunci dan mempercayakannya kepada karyawan lain. Namun, Anda mengerti bahwa ini juga tidak ideal. Dengan menggandakan jumlah kunci, Anda juga menggandakan kemungkinan pencurian kunci.

Putus asa, Anda menghancurkan duplikat dan memutuskan untuk membagi kunci asli menjadi dua. Sekarang, Anda berpikir, dua orang tepercaya dengan pecahan kunci harus hadir secara fisik untuk mengambil kunci dan membuka toko. Ini berarti bahwa pencuri perlu mencuri dua pecahan, yang dua kali lebih sulit daripada mencuri satu kunci. Namun, Anda akan segera menyadari bahwa skema ini tidak jauh lebih baik daripada hanya satu kunci, karena jika seseorang kehilangan setengah kunci, kunci penuh tidak dapat dipulihkan.

Masalahnya dapat diselesaikan dengan serangkaian kunci dan kunci tambahan, tetapi dengan pendekatan ini Anda akan dengan cepat membutuhkan banyak kunci dan kunci. Anda memutuskan bahwa dalam skema ideal Anda perlu membagi kunci sehingga keamanan tidak sepenuhnya bergantung pada satu orang. Anda juga menyimpulkan bahwa harus ada ambang tertentu untuk jumlah fragmen, sehingga jika satu fragmen hilang (atau jika seseorang pergi berlibur), seluruh kunci tetap berfungsi.

Cara berbagi rahasia

Jenis skema manajemen kunci ini dipikirkan oleh Adi Shamir pada 1979 ketika dia menerbitkan karyanya How to Share a Secret . Artikel ini menjelaskan secara singkat apa yang disebut $$$(k, n)$ skema ambang batas untuk secara efektif membagi nilai rahasia (misalnya, kunci kriptografi) menjadi $$$n$ bagian. Lalu, kapan dan hanya kapan paling tidak $$$k$ dari $$$n$ bagian dirakit, Anda dapat dengan mudah mengembalikan rahasia $$$S$ .

Dari sudut pandang keamanan, properti penting dari skema ini adalah bahwa penyerang tidak boleh tahu apa-apa jika dia tidak memiliki setidaknya $$$k$ bagian. Bahkan ketersediaan $$$k - 1$ bagian tidak boleh memberikan informasi apa pun. Kami menyebutnya keamanan semantik properti ini.

Interpolasi polinomial

Skema ambang batas shamir $$$(k, n)$ dibangun di sekitar konsep interpolasi polinomial . Jika Anda tidak terbiasa dengan konsep ini, sebenarnya cukup sederhana. Secara umum, jika Anda pernah menggambar poin pada grafik, dan kemudian menghubungkannya dengan garis atau kurva, maka Anda sudah menggunakannya!


Jumlah polinomial tingkat 2 yang tidak terbatas dapat ditarik melalui dua poin.Untuk memilih satu-satunya, Anda memerlukan poin ketiga. Ilustrasi: Wikipedia

Pertimbangkan polinomial dengan derajat satu, $$$f (x) = x + 2$ . Jika Anda ingin memplot fungsi ini pada grafik, berapa banyak poin yang Anda butuhkan? Kita tahu bahwa ini adalah fungsi linier yang membentuk garis dan oleh karena itu setidaknya diperlukan dua titik. Selanjutnya, pertimbangkan fungsi polinomial dengan derajat dua, $$$f (x) = x ^ 2 + 2x + 1$ . Ini adalah fungsi kuadrat, jadi setidaknya tiga titik diperlukan untuk membuat grafik. Bagaimana dengan polinomial dengan gelar tiga? Setidaknya empat poin. Dan seterusnya dan seterusnya.

Hal yang sangat keren tentang properti ini adalah, mengingat tingkat fungsi polinomial, dan setidaknya $$$gelar + 1$ poin, kita dapat memperoleh poin tambahan untuk fungsi polinomial ini. Ekstrapolasi titik-titik tambahan ini disebut interpolasi polinomial .

Membuat rahasia

Anda mungkin sudah menyadari bahwa skema pintar Shamir ikut berperan di sini. Misalkan rahasia kita $$$S$ Apakah itu $$$42$ . Kita bisa berbalik $$$S$ ke titik pada grafik $$$(0,42)$ dan datang dengan fungsi polinom dengan derajat $$$k-1$ yang memenuhi titik ini. Ingat itu $$$k$ akan menjadi ambang batas kami untuk fragmen yang diperlukan, jadi jika kami menetapkan ambang batas menjadi tiga fragmen, kita harus memilih fungsi polinomial dengan derajat dua.

Polinomial kami akan berbentuk $$$f (x) = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1}$ dimana $$$a_0 = S$ dan $$$a_1, ..., a_ {k-1}$ - bilangan bulat positif yang dipilih secara acak. Kami hanya membangun polinomial dengan gelar $$$k-1$ di mana koefisien gratis $$$a_0$ Apakah rahasia kita $$$S$ , dan masing-masing dari yang berikut ini $$$k-1$ Anggota memiliki koefisien positif yang dipilih secara acak. Jika Anda kembali ke contoh asli dan menganggap itu $$$S = 42, k = 3, a_1, ..., a_ {k-1} = [3,5]$ maka kita mendapatkan fungsinya $$$f (x) = 42 + 3x + 5x ^ 2$ .

Pada tahap ini, kita dapat menghasilkan fragmen dengan menghubungkan $$$n$ bilangan bulat unik di $$$f (x) = 42 + 3x + 5x ^ 2$ dimana $$$x \ neq 0$ (karena ini adalah rahasia kami). Dalam contoh ini, kami ingin mendistribusikan empat fragmen dengan ambang tiga, jadi kami menghasilkan poin secara acak $$$(18, 1716), (27, 3768), (31, 4940), (35, 6272)$ dan kirim satu poin ke masing-masing dari empat orang tepercaya, penjaga kunci. Kami juga memberi tahu orang-orang itu $$$k = 3$ , karena dianggap informasi publik dan diperlukan untuk pemulihan $$$S$ .

Pemulihan Rahasia

Kami telah membahas konsep interpolasi polinomial dan fakta bahwa itu mendasari skema ambang Shamir $$$(k, n)$ . Ketika tiga dari empat proxy ingin pulih $$$S$ mereka hanya perlu melakukan interpolasi $$$f (0)$ dengan poin uniknya sendiri. Untuk melakukan ini, mereka dapat menentukan poin mereka $$$(x_1, y_1), ..., (x_k, y_k) = (18, 1716), (27, 3768), (31, 4940)$ dan menghitung polinomial interpolasi Lagrange menggunakan rumus berikut. Jika pemrograman lebih dapat dipahami oleh Anda daripada matematika, maka pi pada dasarnya adalah pernyataan for yang mengalikan semua hasil, dan sigma adalah pernyataan for yang menambahkan semuanya.

$$

$$P (x) = \ sum_ {j = 1} ^ {k} p_j (x)$$

$$

$$P_j (x) = y_j \ prod _ {\ scriptstyle m = 1 \ di atas \ scriptstyle m \ neq j} ^ {k} \ frac {x-x_m} {x_j-x_m}$$

Di $$$k = 3$ kita dapat menyelesaikan ini sebagai berikut dan mengembalikan fungsi polinomial asli kami:

$$

$$\ begin {aligned} P (x) & = {y_1} \ left ({x-x_2 \ over x_1-x_2} \ cdot {x-x_3 \ lebih dari x_1-x_3} \ kanan) + {y_2} \ kiri ( {x-x_1 \ lebih dari x_2-x_1} \ cdot {x - \ _ 3 \ lebih dari x_2-x_3} \ kanan) + {y_3} \ kiri ({x-x_1 \ lebih dari x_3-x_1} \ cdot {x-x_2 \ lebih dari x_3-x_2} \ kanan) \\ P (x) & = {1716} \ kiri ({x-27 \ lebih dari 18-27} \ cdot {x-31 \ lebih dari 18-31} \ kanan) + {3768 } \ kiri ({x-18 \ lebih dari 27-18} \ cdot {x-31 \ lebih dari 27-31} \ kanan) + {4940} \ kiri ({x-18 \ lebih dari 31-18} \ cdot {x -27 \ lebih dari 31-27} \ kanan) \\ P (x) & = 42 + 3x + 5x ^ 2 \ end {aligned}$$

Karena kita tahu itu $$$S = P (0)$ pemulihan $$$S$ dilakukan secara sederhana:

$$

$$\ begin {aligned} P (0) & = 42 + 3 (0) + 5 (0) ^ 2 \\ P (0) & = 42 \ end {aligned}$$

Menggunakan aritmatika integer yang tidak aman

Meskipun kami telah berhasil menerapkan ide dasar Shamir $$$(k, n)$ , kami masih memiliki masalah yang sejauh ini kami abaikan. Fungsi polinomial kami menggunakan aritmatika integer tidak aman. Perhatikan bahwa untuk setiap titik tambahan yang diterima penyerang pada grafik fungsi kami, ada lebih sedikit opsi untuk titik lainnya. Anda dapat melihatnya dengan mata kepala sendiri saat membuat grafik dengan peningkatan jumlah titik untuk fungsi polinom menggunakan aritmatika integer. Ini kontraproduktif untuk tujuan keamanan yang kami nyatakan, karena penyerang tidak harus mempelajari apa pun sampai mereka memiliki setidaknya $$$k$ fragmen.

Untuk menunjukkan seberapa lemah skema dengan bilangan bulat aritmatika, pertimbangkan skenario di mana penyerang mendapat dua poin $$$(18, 1716), (27,3768)$ dan mengetahui informasi publik itu $$$k = 3$ . Dari informasi ini dia dapat menyimpulkan $$$f (x)$ sama dengan dua dan hubungkan nilai-nilai yang diketahui dalam rumus $$$x$ dan $$$f (x)$ .

$$

$$\ begin {aligned} f (x) & = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1} \\ f (x) & = S + a_1x + a_2x ^ 2 \\ f (18) \ equiv 1716 & = S + a_118 + a_218 ^ 2 \\ f (27) \ equiv 3768 & = S + a_127 + a_227 ^ 2 \ end {aligned}$$

Kemudian penyerang dapat menemukan $$$a_1$ menghitung $$$f (27) - f (18)$ :

$$

$$\ begin {aligned} 3768 - 1716 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) \\ 2052 & = 9a_1 + 405a_2 \\ 9a_1 & = 2052 - 405a_2 \\ a_1 & = \ frac {2052 - 405a_2} {9} \\ a_1 & = 228 - 45a_2 \ end {aligned}$$

Karena kami telah mengidentifikasi $$$a_1, ..., a_ {k-1}$ sebagai bilangan bulat positif yang dipilih secara acak, ada sejumlah kemungkinan $$$a_2$ . Dengan menggunakan informasi ini, penyerang dapat menyimpulkan $$$a_2 \ dalam [1,2,3,4,5]$ , karena semua yang lebih dari 5 akan dilakukan $$$a_1$ negatif. Ini ternyata benar, seperti yang kami tentukan $$$a_2 = 5$

Kemudian penyerang dapat menghitung nilai yang mungkin $$$S$ mengganti $$$a_1$ masuk $$$f (18)$ :

$$

$$\ begin {aligned} 1716 & = S + a_118 + a_218 ^ 2 \\ 1716 & = S + 18 \ kiri (228 - 45a_2 \ kanan) + a_218 ^ 2 \\ 1716 - S & = 18 \ kiri (228 - 45a_2 \ kanan) + a_218 ^ 2 \\ -S & = 18 \ kiri (228 - 45a_2 \ kanan) + a_218 ^ 2 - 1716 \\ -S & = 4104 - 810a_2 + a_218 ^ 2 - 1716 \\ S & = -4104 + 810a_2 - a_218 ^ 2 + 1716 \\ S & = 810a_2 - 324a_2 -2388 \\ S & = 486a_2 - 2388 \ end {aligned}$$

Dengan pilihan opsi terbatas untuk $$$a_2$ menjadi jelas betapa mudahnya untuk memilih dan memeriksa nilai $$$S$ . Hanya ada lima opsi.

Memecahkan masalah dengan aritmatika integer tidak aman

Untuk menghilangkan kerentanan ini, Shamir menyarankan untuk menggunakan aritmatika modular, menggantikannya $$$f (x)$ pada $$$f (x) \ mod p$ dimana $$$p \ in \ mathbb {P}: p> S, p> n$ dan $$$\ mathbb {P}$ - himpunan semua bilangan prima.

Cepat ingat cara kerja aritmatika modular. Jam dengan panah sudah merupakan konsep yang akrab. Dia menggunakan jam tangan $$$\ mod 12$ . Begitu jarum jam lewat dua belas, itu kembali ke satu. Sifat yang menarik dari sistem ini adalah bahwa hanya dengan melihat jam, kita tidak dapat menyimpulkan berapa banyak putaran yang telah dihasilkan oleh jarum jam. Namun, jika kita tahu bahwa jarum jam telah melewati 12 kali empat kali, kita dapat sepenuhnya menentukan jumlah jam yang berlalu menggunakan rumus sederhana $$$a = mq + r$ dimana $$$m$ Apakah pembagi kami (di sini $$$m = 12$ ), $$$q$ Adalah koefisien (berapa kali pembagi tanpa sisa pergi ke nomor asli, di sini $$$q = 4$ ), dan $$$r$ Adalah sisanya, yang biasanya mengembalikan modulo panggilan operator (di sini $$$r = 1,5$ ) Mengetahui semua nilai ini memungkinkan kita untuk memecahkan persamaan $$$a = 49,5$ tetapi jika kita melewatkan koefisien, kita tidak pernah dapat mengembalikan nilai aslinya.

Anda dapat menunjukkan bagaimana ini meningkatkan keamanan sirkuit kami dengan menerapkan sirkuit pada contoh dan penggunaan kami sebelumnya $$$p = 73$ . Fungsi polinomial baru kami $$$f ’(x) = 42 + 3x + 5x ^ 2 \ mod 73$ , dan poin baru $$$(18, 37), (27, 45), (31, 49), (35, 67)$ . Sekarang, penjaga kunci dapat sekali lagi menggunakan interpolasi polinomial untuk mengembalikan fungsi kita, hanya saja kali ini penambahan dan operasi multiplikasi harus disertai dengan pengurangan modulo $$$p$ (mis $$$48 + 93 \ mod 73 = 68$ )

Dengan menggunakan contoh baru ini, anggap penyerang mengenali dua poin baru ini, $$$(18, 37), (27, 45)$ , dan informasi publik $$$k = 3, p = 73$ . Kali ini, penyerang, berdasarkan semua informasi yang dimilikinya, menampilkan fungsi berikut, di mana $$$\ mathbb {N}$ Apakah himpunan semua bilangan bulat positif, dan $$$q_x$ mewakili koefisien modul $$$f ’(x)$ .

$$

$$\ begin {aligned} f '(x) & = S + a_1x + a_2x ^ 2 \ mod 73 \\ f' (x) & = S + a_1x + a_2x ^ 2 - 73q_x: q_x \ in \ mathbb {N} \\ f '(18) \ equiv 37 & = S + a_118 + a_218 ^ 2 - 73q_ {18} \\ f' (27) \ equiv 45 & = S + a_127 + a_227 ^ 2 - 73q_ {27} \ end {aligned}$$

Sekarang penyerang kita menemukan lagi $$$a_1$ dengan komputasi $$$f ’(27) - f’ (18)$ :

$$

$$\ begin {aligned} 45 - 37 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) + (-73q_ {27} - (-73q_ {18})) \\ 8 & = 9a_1 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ -9a_1 & = -8 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ 9a_1 & = 8 - 405a_2 - 73 (q_ {18} - q_ {27}) \\ a_1 & = \ frac {8 - 405a_2 - 73 (q_ {18} - q_ {27})} {9} \\ a_1 & = \ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ end {aligned}$$

Kemudian dia kembali mencoba menarik $$$S$ mengganti $$$a_1$ masuk $$$f ’(18)$ :

$$

$$\ begin {aligned} 37 & = S + 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ kanan) + a_218 ^ 2 - 73q_ {18} \\ -S & = 18 \ kiri (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ kanan) + a_218 ^ 2 - 73q_ {18} - 37 \\ S & = -18 \ kiri (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27} ) \ kanan) - 324a_2 + 73q_ {18} + 37 \\ S & = 486a_2 + 21 + 219q_ {18} - 146q_ {27} \ end {aligned}$$

Kali ini ia memiliki masalah serius. Tidak ada nilai dalam rumus $$$a_2$ , $$$q_ {18}$ dan $$$q_ {27}$ . Karena ada jumlah tak terbatas dari kombinasi variabel-variabel ini, itu tidak dapat menerima informasi tambahan.

Pertimbangan Keamanan

Skema berbagi rahasia Shamir menawarkan keamanan dalam hal teori informasi . Ini berarti matematika itu tahan bahkan terhadap penyerang dengan kekuatan komputasi tidak terbatas. Namun, rangkaian itu masih mengandung beberapa masalah yang diketahui.

Misalnya, skema Shamir tidak membuat fragmen uji , yaitu, orang dapat dengan bebas menyajikan fragmen palsu dan mengganggu pemulihan rahasia yang benar. Seorang penjaga fragmen yang bermusuhan dengan informasi yang cukup bahkan dapat menghasilkan fragmen lain dengan mengubah $$$S$ atas kebijakannya sendiri. Masalah ini diselesaikan dengan menggunakan skema berbagi rahasia yang terverifikasi , seperti skema Feldman.

Masalah lain adalah bahwa panjang fragmen sama dengan panjang rahasia yang sesuai, sehingga panjang rahasia mudah ditentukan. Masalah ini diselesaikan dengan secara sepele memasukkan rahasia dengan angka acak hingga panjang yang tetap.

Akhirnya, penting untuk dicatat bahwa masalah keamanan kita mungkin melampaui lingkup skema itu sendiri. Untuk aplikasi kriptografi dunia nyata, sering ada ancaman serangan pada saluran pihak ketiga, ketika penyerang mencoba mengekstraksi informasi yang berguna dari runtime aplikasi, caching, crash, dll. Jika ini merupakan masalah, Anda harus mempertimbangkan dengan hati-hati penggunaan perlindungan selama pengembangan, seperti fungsi dan pencarian dengan waktu berjalan yang konstan, mencegah penyimpanan memori pada disk, dan mempertimbangkan sejumlah hal lain yang berada di luar cakupan artikel ini.

Demo

Halaman ini memiliki demo interaktif skema berbagi rahasia Shamir. Demonstrasi dibuat berdasarkan pustaka ssss-js , yang dengan sendirinya merupakan port JavaScript dari program ssss populer. Perhatikan bahwa menghitung nilai besar $$$k$ , $$$n$ dan $$$S$ mungkin perlu waktu.