Pertimbangkan skenario di mana Anda perlu mengamankan brankas bank. Itu dianggap benar-benar tidak dapat ditembus tanpa kunci yang diberikan kepada Anda pada hari pertama kerja. Tujuan Anda adalah menyimpan kunci dengan aman.

Katakanlah Anda memutuskan untuk selalu menyimpan kunci, memberikan akses ke penyimpanan sesuai kebutuhan. Namun Anda akan segera menyadari bahwa solusi seperti itu tidak dapat diterapkan dengan baik dalam praktiknya, karena kehadiran fisik Anda diperlukan setiap kali Anda membuka penyimpanan. Bagaimana dengan liburan yang dijanjikan kepada Anda? Selain itu, pertanyaannya bahkan lebih menakutkan: bagaimana jika Anda kehilangan satu-satunya kunci?

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

Dalam keputusasaan, Anda menghancurkan duplikatnya dan memutuskan untuk membagi kunci asli menjadi dua. Sekarang, Anda mungkin berpikir bahwa dua orang tepercaya dengan pecahan kunci harus hadir secara fisik untuk mengambil kunci dan membuka brankas. Artinya pencuri perlu mencuri dua buah kunci, yang dua kali lebih sulit daripada mencuri satu kunci. Namun, Anda segera menyadari bahwa skema ini tidak jauh lebih baik daripada hanya satu kunci, karena jika seseorang kehilangan setengah kunci, seluruh kunci tidak dapat diperoleh kembali.

Masalahnya dapat diselesaikan dengan serangkaian kunci dan gembok tambahan, tetapi pendekatan ini akan membutuhkan waktu yang cepat много kunci dan gembok. Anda memutuskan bahwa desain yang ideal adalah berbagi kunci sehingga keamanan tidak bergantung sepenuhnya pada satu orang. Anda juga menyimpulkan bahwa harus ada batasan tertentu untuk jumlah fragmen sehingga jika satu fragmen hilang (atau jika seseorang pergi berlibur), seluruh kunci tetap berfungsi.

Bagaimana cara berbagi rahasia

Skema manajemen kunci jenis ini dipikirkan oleh Adi Shamir pada tahun 1979 ketika ia menerbitkan karyanya "Cara Berbagi Rahasia". Artikel tersebut secara singkat menjelaskan apa yang disebut skema ambang batas untuk membagi nilai rahasia secara efisien (seperti kunci kriptografi) menjadi bagian. Lalu, kapan dan setidaknya hanya pada saat itu dari bagian-bagiannya telah dirakit, Anda dapat dengan mudah mengembalikan rahasianya .

Dari sudut pandang keamanan, fitur penting dari skema ini adalah bahwa penyerang tidak boleh mengetahui apa pun kecuali dia memiliki setidaknya bagian. Bahkan kehadirannya bagian tidak boleh memberikan informasi apa pun. Kami menyebutnya properti keamanan semantik.

Interpolasi polinomial

Skema ambang batas Shamir dibangun berdasarkan konsep tersebut interpolasi polinomial. Jika Anda belum familiar dengan konsep ini, sebenarnya cukup sederhana. Faktanya, jika Anda pernah menggambar titik-titik pada grafik dan kemudian menghubungkannya dengan garis atau kurva, Anda sudah menggunakannya!

Melalui dua titik Anda dapat menggambar polinomial derajat 2 dalam jumlah tak terbatas. Untuk memilih satu-satunya dari polinomial tersebut, Anda memerlukan titik ketiga. Ilustrasi: Wikipedia

Pertimbangkan polinomial dengan derajat satu, . Jika Anda ingin memplot fungsi ini pada grafik, berapa banyak titik yang Anda perlukan? Kita tahu bahwa ini adalah fungsi linier yang membentuk sebuah garis sehingga memerlukan setidaknya dua titik. Selanjutnya, perhatikan fungsi polinomial berderajat dua, . Ini adalah fungsi kuadrat, jadi diperlukan setidaknya tiga titik untuk membuat grafik. Bagaimana dengan polinomial yang berderajat tiga? Setidaknya empat poin. Dan seterusnya dan seterusnya.

Hal yang sangat keren tentang properti ini adalah, mengingat derajat fungsi polinomial dan setidaknya poin, kita dapat memperoleh poin tambahan untuk fungsi polinomial ini. Kami menyebutnya ekstrapolasi poin tambahan ini interpolasi polinomial.

Membuat rahasia

Anda mungkin sudah menyadari bahwa di sinilah skema cerdik Shamir berperan. Katakanlah rahasia kita - Apakah . Kita bisa berbalik ke suatu titik pada grafik dan menghasilkan fungsi polinomial dengan derajat , yang memenuhi poin ini. Mari kita ingat hal itu akan menjadi ambang batas fragmen yang diperlukan, jadi jika kita menetapkan ambang batas menjadi tiga fragmen, kita harus memilih fungsi polinomial dengan derajat dua.

Polinomial kita akan berbentuk Dimana и — bilangan bulat positif yang dipilih secara acak. Kami baru saja membuat polinomial dengan derajat , di mana koefisien bebasnya  - Ini adalah rahasia kami , dan untuk masing-masing berikutnya syaratnya ada koefisien positif yang dipilih secara acak. Jika kita kembali ke contoh awal dan berasumsi demikian , lalu kita mendapatkan fungsinya .

Pada titik ini kita dapat menghasilkan fragmen dengan menghubungkan bilangan bulat unik di Dimana (karena itu rahasia kami). Dalam contoh ini, kami ingin mendistribusikan empat fragmen dengan ambang batas tiga, jadi kami menghasilkan poin secara acak dan kirimkan satu poin ke masing-masing dari empat orang tepercaya, penjaga kunci. Kami juga memberi tahu orang-orang tentang hal itu , karena ini dianggap sebagai informasi publik dan diperlukan untuk pemulihan .

Memulihkan rahasianya

Kita telah membahas konsep interpolasi polinomial dan bagaimana konsep tersebut mendasari skema ambang batas Shamir . Ketika salah satu dari empat wali ingin memulihkan , mereka hanya perlu melakukan interpolasi dengan poin uniknya sendiri. Untuk melakukan ini, mereka dapat menentukan poinnya dan hitung polinomial interpolasi Lagrange menggunakan rumus berikut. Jika pemrograman lebih jelas bagi Anda daripada matematika, maka pi pada dasarnya adalah sebuah operator for, yang mengalikan semua hasil, dan sigma adalah for, yang menambahkan semuanya.

Di kita bisa menyelesaikannya seperti ini dan mengembalikan fungsi polinomial asli kita:

Karena kita tahu itu , pemulihan dilakukan secara sederhana:

Menggunakan aritmatika bilangan bulat yang tidak aman

Meskipun ide dasar Shamir telah berhasil kita terapkan , kita dihadapkan pada masalah yang selama ini kita abaikan. Fungsi polinomial kami menggunakan aritmatika bilangan bulat yang tidak aman. Perhatikan bahwa untuk setiap poin tambahan yang diperoleh penyerang pada grafik fungsi kita, kemungkinan poin lainnya semakin kecil. Anda dapat melihatnya dengan mata kepala sendiri ketika Anda memplot peningkatan jumlah poin untuk fungsi polinomial menggunakan aritmatika bilangan bulat. Hal ini kontraproduktif terhadap sasaran keamanan yang kami nyatakan, karena penyerang seharusnya tidak mengetahui apa pun sampai mereka setidaknya mengetahui hal tersebut fragmen.

Untuk menunjukkan betapa lemahnya rangkaian aritmatika bilangan bulat, pertimbangkan skenario di mana penyerang memperoleh dua poin dan mengetahui informasi publik itu . Dari informasi ini dia dapat menyimpulkan , sama dengan dua, dan masukkan nilai yang diketahui ke dalam rumus и .

Penyerang kemudian dapat menemukannya , menghitung :

Karena kita telah mendefinisikannya sebagai bilangan bulat positif yang dipilih secara acak, jumlah kemungkinannya terbatas . Dengan menggunakan informasi ini, penyerang dapat menyimpulkan , karena angka yang lebih besar dari 5 sudah cukup negatif. Ini ternyata benar karena kita sudah menentukannya

Penyerang kemudian dapat menghitung nilai yang mungkin menggantikan в :

Dengan pilihan terbatas untuk menjadi jelas betapa mudahnya memilih dan memeriksa nilainya . Hanya ada lima pilihan di sini.

Memecahkan masalah dengan aritmatika bilangan bulat yang tidak aman

Untuk menghilangkan kerentanan ini, Shamir menyarankan penggunaan aritmatika modular, penggantian pada Dimana и — himpunan semua bilangan prima.

Mari kita segera mengingat cara kerja aritmatika modular. Jam dengan tangan adalah konsep yang familiar. Dia menggunakan jam tangan itu . Begitu jarum penunjuk jam melewati angka dua belas, ia kembali ke angka satu. Sifat yang menarik dari sistem ini adalah hanya dengan melihat jam, kita tidak dapat menyimpulkan berapa putaran yang telah dilakukan jarum penunjuk jam. Akan tetapi, jika kita mengetahui bahwa jarum penunjuk jam telah melewati 12 sebanyak empat kali, kita dapat menentukan secara lengkap jumlah jam yang telah berlalu dengan menggunakan rumus sederhana. Dimana  adalah pembagi kita (di sini ),  adalah koefisien (berapa kali pembagi menjadi bilangan asli tanpa sisa, di sini ), dan  adalah sisanya, yang biasanya mengembalikan panggilan operator modulo (di sini ). Mengetahui semua nilai ini memungkinkan kita menyelesaikan persamaannya , tetapi jika kita melewatkan koefisiennya, kita tidak akan pernah bisa mengembalikan nilai aslinya.

Kita dapat mendemonstrasikan bagaimana hal ini meningkatkan keamanan skema kita dengan menerapkan skema tersebut pada contoh dan penggunaan kita sebelumnya . Fungsi polinomial baru kami , dan poin baru . Sekarang penjaga kunci dapat sekali lagi menggunakan interpolasi polinomial untuk merekonstruksi fungsi kita, hanya saja kali ini operasi penjumlahan dan perkalian harus disertai dengan reduksi modulo (misalnya ).

Dengan menggunakan contoh baru ini, mari kita asumsikan penyerang mempelajari dua poin baru ini, , dan informasi publik . Kali ini, penyerang, berdasarkan semua informasi yang dimilikinya, mengeluarkan fungsi berikut, di mana  adalah himpunan semua bilangan bulat positif, dan mewakili koefisien modulus .

Sekarang penyerang kita menemukannya lagi , menghitung :

Lalu dia mencoba lagi menggantikan в :

Kali ini dia punya masalah serius. Nilai rumus hilang , и . Karena kombinasi variabel-variabel ini jumlahnya tak terhingga, ia tidak dapat memperoleh informasi tambahan apa pun.

Pertimbangan Keamanan

Skema pembagian rahasia Shamir menunjukkan keamanan dari sudut pandang teori informasi. Ini berarti matematikanya tahan bahkan terhadap penyerang dengan daya komputasi tak terbatas. Namun, sirkuit tersebut masih mengandung beberapa masalah yang diketahui.

Misalnya, skema Shamir tidak tercipta pecahan yang akan diperiksa, yaitu, orang dapat dengan bebas menyajikan fragmen palsu dan mengganggu pemulihan rahasia yang benar. Penjaga fragmen yang bermusuhan dengan informasi yang cukup bahkan dapat menghasilkan fragmen lain dengan mengubahnya atas kebijaksanaan Anda sendiri. Masalah ini diselesaikan dengan menggunakan skema pembagian rahasia yang dapat diverifikasi, seperti skema Feldman.

Masalah lainnya adalah panjang setiap fragmen sama dengan panjang rahasia yang bersangkutan, sehingga panjang rahasianya mudah ditentukan. Masalah ini bisa diselesaikan dengan cara yang sepele lapisan rahasia dengan angka sembarang hingga panjang tetap.

Terakhir, penting untuk dicatat bahwa masalah keamanan kami mungkin melampaui desain itu sendiri. Untuk aplikasi kriptografi dunia nyata, sering kali terdapat ancaman serangan saluran samping di mana penyerang mencoba mengekstrak informasi berguna dari waktu eksekusi aplikasi, caching, crash, dll. Jika hal ini menjadi perhatian, pertimbangan yang cermat harus diberikan selama pengembangan untuk menggunakan tindakan perlindungan seperti fungsi dan pencarian waktu konstan, mencegah penyimpanan memori ke disk, dan sejumlah pertimbangan lain yang berada di luar cakupan artikel ini.

Demonstrasi

Pada Halaman ini Ada demonstrasi interaktif skema pembagian rahasia Shamir. Demonstrasi berdasarkan perpustakaan ssss-js, yang merupakan port JavaScript dari program populer ssss. Perhatikan bahwa menghitung nilai besar , и mungkin butuh waktu.

Sumber: www.habr.com