तुम्हाला बँक व्हॉल्ट सुरक्षित करण्याची आवश्यकता असलेल्या परिस्थितीचा विचार करा. किल्लीशिवाय हे पूर्णपणे अभेद्य मानले जाते, जे तुम्हाला कामाच्या पहिल्याच दिवशी दिले जाते. की सुरक्षितपणे साठवणे हे तुमचे ध्येय आहे.

गरजेनुसार स्टोरेजमध्ये अ‍ॅक्सेस प्रदान करून, की नेहमी तुमच्याकडे ठेवण्याचे तुम्ही ठरवले आहे असे समजा. परंतु तुम्हाला त्वरीत लक्षात येईल की असा उपाय सरावात योग्य प्रमाणात होत नाही, कारण प्रत्येक वेळी तुम्ही स्टोरेज उघडता तेव्हा तुमची भौतिक उपस्थिती आवश्यक असते. तुम्हाला ज्या सुट्टीचे वचन दिले होते त्याचे काय? याव्यतिरिक्त, प्रश्न आणखी भयावह आहे: आपण आपली एकमेव चावी गमावल्यास काय होईल?

तुमची सुट्टी लक्षात घेऊन, तुम्ही किल्लीची एक प्रत बनवून ती दुसऱ्या कर्मचाऱ्याला सोपवण्याचा निर्णय घेता. तथापि, आपण समजता की हे देखील आदर्श नाही. चावींची संख्या दुप्पट करून, तुम्ही की चोरीची शक्यता दुप्पट करता.

हताशपणे, तुम्ही डुप्लिकेट नष्ट करा आणि मूळ की अर्ध्यामध्ये विभाजित करण्याचा निर्णय घ्या. आता, तुम्हाला असे वाटेल की किल्लीचे तुकडे असलेले दोन विश्वासू लोक किल्ली गोळा करण्यासाठी आणि तिजोरी उघडण्यासाठी प्रत्यक्ष उपस्थित असणे आवश्यक आहे. याचा अर्थ चोराला दोन तुकडे चोरणे आवश्यक आहे, जे एक किल्ली चोरण्यापेक्षा दुप्पट कठीण आहे. तथापि, तुम्हाला लवकरच समजेल की ही योजना फक्त एका किल्लीपेक्षा जास्त चांगली नाही, कारण जर एखाद्याने अर्धी चावी गमावली तर पूर्ण की परत मिळवता येणार नाही.

अतिरिक्त की आणि लॉकच्या मालिकेसह समस्येचे निराकरण केले जाऊ शकते, परंतु या दृष्टिकोनाची त्वरीत आवश्यकता असेल भरपूर चाव्या आणि कुलूप. सुरक्षितता पूर्णपणे एका व्यक्तीवर अवलंबून राहू नये म्हणून की सामायिक करणे हे आदर्श डिझाइन असेल असे तुम्ही ठरवा. तुम्ही असेही निष्कर्ष काढता की तुकड्यांच्या संख्येसाठी काही थ्रेशोल्ड असणे आवश्यक आहे जेणेकरुन एक तुकडा गमावल्यास (किंवा एखादी व्यक्ती सुट्टीवर गेल्यास), संपूर्ण की कार्यरत राहते.

गुपित कसे शेअर करावे

या प्रकारच्या प्रमुख व्यवस्थापन योजनेचा विचार आदि शमीर यांनी 1979 मध्ये केला होता जेव्हा त्यांनी त्यांचे कार्य प्रकाशित केले होते "गुप्त कसे शेअर करावे". लेख थोडक्यात तथाकथित स्पष्ट करतो गुप्त मूल्य (जसे की क्रिप्टोग्राफिक की) मध्ये कार्यक्षमतेने विभाजित करण्यासाठी थ्रेशोल्ड योजना भाग मग, केव्हा आणि फक्त तेव्हाच पासून भाग एकत्र केले जातात, आपण सहजपणे रहस्य पुनर्संचयित करू शकता .

सुरक्षेच्या दृष्टीकोनातून, या योजनेचा एक महत्त्वाचा गुणधर्म हा आहे की हल्लेखोराला त्याच्याजवळ कमीत कमी असल्याशिवाय पूर्णपणे काहीही माहित नसावे. भाग अगदी उपस्थिती भाग कोणतीही माहिती देऊ नये. याला आम्ही प्रॉपर्टी म्हणतो अर्थपूर्ण सुरक्षा.

बहुपदी इंटरपोलेशन

शामीर थ्रेशोल्ड योजना संकल्पनेभोवती बांधले गेले बहुपदी प्रक्षेपण. आपण या संकल्पनेशी परिचित नसल्यास, प्रत्यक्षात ते अगदी सोपे आहे. खरं तर, जर तुम्ही कधीही आलेखावर बिंदू काढले असतील आणि नंतर त्यांना रेषा किंवा वक्रांनी जोडले असेल, तर तुम्ही ते आधीच वापरले असेल!

दोन बिंदूंद्वारे तुम्ही पदवी 2 च्या बहुपदांची अमर्याद संख्या काढू शकता. त्यापैकी एकच निवडण्यासाठी, तुम्हाला तिसऱ्या बिंदूची आवश्यकता आहे. चित्रण: विकिपीडिया

पदवी एक सह बहुपदी विचारात घ्या, . जर तुम्हाला हे फंक्शन आलेखावर प्लॉट करायचे असेल तर तुम्हाला किती गुण हवे आहेत? बरं, आपल्याला माहित आहे की हे एक रेखीय कार्य आहे जे एक रेषा बनवते आणि म्हणून त्याला किमान दोन बिंदू आवश्यक आहेत. पुढे, पदवी दोन सह बहुपदी कार्याचा विचार करा, . हे एक चतुर्भुज कार्य आहे, त्यामुळे आलेख प्लॉट करण्यासाठी किमान तीन बिंदू आवश्यक आहेत. पदवी तीन सह बहुपदी बद्दल काय? किमान चार गुण. आणि अशीच आणि पुढे.

या मालमत्तेबद्दल खरोखर छान गोष्ट म्हणजे, बहुपदी कार्याची पदवी आणि किमान बिंदू, या बहुपदी कार्यासाठी आपण अतिरिक्त गुण मिळवू शकतो. आम्ही या अतिरिक्त बिंदूंचे एक्सट्रापोलेशन म्हणतो बहुपदी प्रक्षेपण.

एक गुपित तयार करणे

शमीरची हुशार योजना इथेच प्रत्यक्षात येते हे तुमच्या आधीच लक्षात आले असेल. आमचे रहस्य सांगू - हे आहे . आपण वळू शकतो आलेखावरील एका बिंदूपर्यंत आणि पदवीसह बहुपदी कार्य घेऊन या , जे या बिंदूचे समाधान करते. त्याची आठवण करून द्या आवश्यक तुकड्यांचा आमचा उंबरठा असेल, म्हणून जर आपण थ्रेशोल्ड तीन तुकड्यांवर सेट केला, तर आपण पदवी दोनसह बहुपदी कार्य निवडले पाहिजे.

आपल्या बहुपदीला फॉर्म असेल कुठे и — यादृच्छिकपणे निवडलेले सकारात्मक पूर्णांक. आम्ही फक्त पदवीसह बहुपदी तयार करत आहोत , जेथे मुक्त गुणांक  - हे आमचे रहस्य आहे , आणि त्यानंतरच्या प्रत्येकासाठी अटी यादृच्छिकपणे निवडलेल्या सकारात्मक गुणांक आहेत. जर आपण मूळ उदाहरणाकडे परत गेलो आणि असे गृहीत धरले तर , नंतर फंक्शन मिळेल .

या टप्प्यावर आपण कनेक्ट करून तुकडे तयार करू शकतो मध्ये अद्वितीय पूर्णांक कुठे (कारण ते आमचे रहस्य आहे). या उदाहरणात, आम्हाला तीनच्या थ्रेशोल्डसह चार तुकड्यांचे वितरण करायचे आहे, म्हणून आम्ही यादृच्छिकपणे गुण निर्माण करतो आणि चार विश्वासू लोकांपैकी प्रत्येकाला एक पॉइंट पाठवा, किल्लीचे संरक्षक. आम्ही लोकांना ते देखील कळवले , कारण ही सार्वजनिक माहिती मानली जाते आणि पुनर्प्राप्तीसाठी आवश्यक आहे .

गुप्त पुनर्प्राप्ती

बहुपदी इंटरपोलेशनची संकल्पना आणि ती शमीरच्या थ्रेशोल्ड योजना कशी अधोरेखित करते याबद्दल आम्ही आधीच चर्चा केली आहे. . जेव्हा चारपैकी तीन विश्वस्तांना पुनर्संचयित करायचे आहे , त्यांना फक्त इंटरपोलेट करणे आवश्यक आहे त्याच्या स्वतःच्या अद्वितीय गुणांसह. हे करण्यासाठी, ते त्यांचे गुण निश्चित करू शकतात आणि खालील सूत्र वापरून Lagrange इंटरपोलेशन बहुपदीची गणना करा. जर तुम्हाला गणितापेक्षा प्रोग्रामिंग अधिक स्पष्ट वाटत असेल, तर pi हा मूलत: ऑपरेटर आहे for, जे सर्व परिणामांना गुणाकार करते आणि सिग्मा आहे for, जे सर्वकाही जोडते.

येथे आम्ही ते याप्रमाणे सोडवू शकतो आणि आमचे मूळ बहुपदी कार्य परत करू शकतो:

आम्हाला ते माहीत असल्याने , पुनर्प्राप्ती फक्त केले:

असुरक्षित पूर्णांक अंकगणित वापरणे

जरी आम्ही शमीरची मूळ कल्पना यशस्वीरित्या लागू केली आहे , आमच्याकडे एक समस्या आहे ज्याकडे आम्ही आतापर्यंत दुर्लक्ष केले आहे. आमचे बहुपदीय कार्य असुरक्षित पूर्णांक अंकगणित वापरते. लक्षात घ्या की आक्रमणकर्त्याने आमच्या फंक्शनच्या आलेखावर प्राप्त केलेल्या प्रत्येक अतिरिक्त बिंदूसाठी, इतर बिंदूंसाठी कमी शक्यता आहेत. जेव्हा तुम्ही पूर्णांक अंकगणित वापरून बहुपदी फंक्शनसाठी गुणांची संख्या वाढवता तेव्हा तुम्ही हे तुमच्या स्वतःच्या डोळ्यांनी पाहू शकता. हे आमच्या सांगितलेल्या सुरक्षा उद्दिष्टासाठी प्रतिकूल आहे, कारण हल्लेखोराला किमान काहीही कळत नसावे. तुकडे

पूर्णांक अंकगणित सर्किट किती कमकुवत आहे हे दाखवण्यासाठी, आक्रमणकर्त्याने दोन गुण मिळविलेल्या परिस्थितीचा विचार करा आणि सार्वजनिक माहिती माहीत आहे की . या माहितीवरून तो निष्कर्ष काढू शकतो , दोन च्या बरोबरीने, आणि सूत्रामध्ये ज्ञात मूल्ये प्लग इन करा и .

हल्लेखोर नंतर शोधू शकतात , मोजणी :

आम्ही व्याख्या केल्यापासून यादृच्छिकपणे निवडलेले धन पूर्णांक म्हणून, तेथे मर्यादित संख्या शक्य आहे . या माहितीचा वापर करून, आक्रमणकर्ता निष्कर्ष काढू शकतो , कारण 5 पेक्षा मोठे काहीही करेल नकारात्मक आम्ही ठरवल्यापासून हे खरे ठरते

आक्रमणकर्ता नंतर संभाव्य मूल्यांची गणना करू शकतो बदलत आहे в :

साठी मर्यादित पर्यायांसह मूल्ये निवडणे आणि तपासणे किती सोपे आहे हे स्पष्ट होते . येथे फक्त पाच पर्याय आहेत.

असुरक्षित पूर्णांक अंकगणितासह समस्या सोडवणे

ही असुरक्षा दूर करण्यासाठी, शमीर मॉड्यूलर अंकगणित वापरून बदलण्याची सूचना देतात वर कुठे и — सर्व मूळ संख्यांचा संच.

मॉड्यूलर अंकगणित कसे कार्य करते ते त्वरीत लक्षात ठेवूया. हात असलेले घड्याळ ही एक परिचित संकल्पना आहे. ती एक घड्याळ वापरते . तासाचे बारा पास होताच ते परत एकावर येते. या प्रणालीचा एक मनोरंजक गुणधर्म असा आहे की फक्त घड्याळ पाहून, तासाच्या हाताने किती आवर्तने केली आहेत हे आपण काढू शकत नाही. तथापि, जर आपल्याला माहित असेल की तासाचा हात 12 वेळा चार वेळा गेला आहे, तर आपण साधे सूत्र वापरून किती तास निघून गेले आहेत हे पूर्णपणे ठरवू शकतो. कुठे  आमचा विभाजक आहे (येथे ),  गुणांक आहे (विभाजक मूळ संख्येमध्ये किती वेळा उरलेला नाही, येथे ), आणि  उर्वरित आहे, जे सहसा मोड्युलो ऑपरेटर कॉल परत करते (येथे ). ही सर्व मूल्ये जाणून घेतल्याने आम्हाला समीकरण सोडवता येते , परंतु आम्ही गुणांक चुकवल्यास, आम्ही मूळ मूल्य पुनर्संचयित करू शकणार नाही.

आम्ही आमच्या मागील उदाहरणावर योजना लागू करून आणि वापरून आमच्या योजनेची सुरक्षा कशी सुधारते हे आम्ही दाखवू शकतो . आमचे नवीन बहुपदी कार्य , आणि नवीन मुद्दे . आता मुख्य कीपर पुन्हा एकदा बहुपदी इंटरपोलेशन वापरून आमच्या कार्याची पुनर्रचना करू शकतात, फक्त यावेळी बेरीज आणि गुणाकार ऑपरेशन्स मॉड्युलो रिडक्शनसह असणे आवश्यक आहे. (उदा ).

या नवीन उदाहरणाचा वापर करून, असे गृहीत धरू की हल्लेखोराने यापैकी दोन नवीन मुद्दे शिकले, , आणि सार्वजनिक माहिती . यावेळी, हल्लेखोर, त्याच्याकडे असलेल्या सर्व माहितीवर आधारित, खालील कार्ये आउटपुट करतो, कुठे  सर्व सकारात्मक पूर्णांकांचा संच आहे, आणि मॉड्यूलस गुणांक दर्शवितो .

आता आमचा हल्लेखोर पुन्हा सापडला , गणना करत आहे :

मग तो पुन्हा प्रयत्न करतो बदलत आहे в :

यावेळी त्याला एक गंभीर समस्या आहे. सूत्र गहाळ मूल्ये , и . या चलांच्या अगणित संयोगांमुळे, त्याला कोणतीही अतिरिक्त माहिती मिळू शकत नाही.

सुरक्षा विचार

शमीरची सिक्रेट शेअरिंग स्कीम सुचवते माहिती सिद्धांताच्या दृष्टिकोनातून सुरक्षा. याचा अर्थ असा की, गणित अमर्यादित संगणकीय शक्ती असलेल्या आक्रमणकर्त्याविरूद्ध देखील प्रतिरोधक आहे. तथापि, सर्किटमध्ये अद्याप अनेक ज्ञात समस्या आहेत.

उदाहरणार्थ, शमीरची योजना तयार करत नाही तपासायचे तुकडे, म्हणजे, लोक मुक्तपणे बनावट तुकडे सादर करू शकतात आणि योग्य रहस्य पुनर्प्राप्त करण्यात हस्तक्षेप करू शकतात. पुरेशी माहिती असलेला प्रतिकूल तुकडा कीपर बदलून आणखी एक तुकडा तयार करू शकतो आपल्या स्वत: च्या विवेकबुद्धीनुसार. वापरून ही समस्या सोडवली जाते सत्यापित करण्यायोग्य गुप्त सामायिकरण योजना, जसे की फेल्डमॅनची योजना.

दुसरी अडचण अशी आहे की कोणत्याही तुकड्याची लांबी संबंधित गुपिताच्या लांबीइतकी असते, त्यामुळे गुपिताची लांबी निश्चित करणे सोपे असते. ही समस्या क्षुल्लक करून सोडवली जाऊ शकते पॅडिंग एका निश्चित लांबीपर्यंत अनियंत्रित संख्येसह गुप्त.

शेवटी, हे लक्षात घेणे महत्त्वाचे आहे की आमच्या सुरक्षेची चिंता डिझाइनच्या पलीकडेही वाढू शकते. वास्तविक-जगातील क्रिप्टोग्राफिक ऍप्लिकेशन्ससाठी, अनेकदा साइड-चॅनल हल्ल्यांचा धोका असतो जेथे आक्रमणकर्ता ऍप्लिकेशनच्या अंमलबजावणीची वेळ, कॅशिंग, क्रॅश इत्यादींमधून उपयुक्त माहिती काढण्याचा प्रयत्न करतो. ही चिंता असल्यास, विकासादरम्यान संरक्षणात्मक उपाय जसे की फंक्शन्स आणि सतत-वेळ लुकअप वापरणे, मेमरी डिस्कवर जतन होण्यापासून प्रतिबंधित करणे आणि या लेखाच्या व्याप्तीच्या पलीकडे असलेल्या इतर अनेक बाबींचा काळजीपूर्वक विचार केला पाहिजे.

डेमो

वर हे पृष्ठ शमीरच्या गुप्त शेअरिंग योजनेचे संवादात्मक प्रात्यक्षिक आहे. ग्रंथालयावर आधारित प्रात्यक्षिक ssss-js, जे स्वतः लोकप्रिय प्रोग्रामचे JavaScript पोर्ट आहे ssss. लक्षात ठेवा की मोठ्या मूल्यांची गणना करणे , и थोडा वेळ लागू शकतो.

स्त्रोत: www.habr.com