ऐसे परिदृश्य पर विचार करें जहां आपको बैंक तिजोरी सुरक्षित करने की आवश्यकता है। यह बिना चाबी के बिल्कुल अभेद्य माना जाता है, जो आपको काम के पहले दिन ही दी जाती है। आपका लक्ष्य कुंजी को सुरक्षित रूप से संग्रहीत करना है।

मान लीजिए कि आप आवश्यकतानुसार भंडारण तक पहुंच प्रदान करते हुए चाबी को हर समय अपने पास रखने का निर्णय लेते हैं। लेकिन आप जल्द ही महसूस करेंगे कि ऐसा समाधान व्यवहार में अच्छा नहीं है, क्योंकि हर बार जब आप भंडारण खोलते हैं तो आपकी भौतिक उपस्थिति की आवश्यकता होती है। आपसे जिस छुट्टी का वादा किया गया था उसके बारे में क्या? इसके अलावा, यह प्रश्न और भी भयावह है: यदि आपकी एकमात्र चाबी खो जाए तो क्या होगा?

अपनी छुट्टियों को ध्यान में रखते हुए, आप चाबी की एक प्रति बनाने और उसे किसी अन्य कर्मचारी को सौंपने का निर्णय लेते हैं। हालाँकि, आप समझते हैं कि यह भी आदर्श नहीं है। चाबियों की संख्या दोगुनी करके, आप चाबी चोरी होने की संभावना भी दोगुनी कर देते हैं।

हताशा में, आप डुप्लिकेट को नष्ट कर देते हैं और मूल कुंजी को आधे में विभाजित करने का निर्णय लेते हैं। अब, आप सोचेंगे कि चाबी के टुकड़े वाले दो भरोसेमंद लोगों को चाबी लेने और तिजोरी खोलने के लिए शारीरिक रूप से उपस्थित होना होगा। इसका मतलब यह है कि एक चोर को दो टुकड़े चुराने होंगे, जो एक चाबी चुराने से दोगुना मुश्किल है। हालाँकि, आपको जल्द ही एहसास होगा कि यह योजना सिर्फ एक कुंजी से ज्यादा बेहतर नहीं है, क्योंकि यदि कोई आधी कुंजी खो देता है, तो पूरी कुंजी वापस नहीं मिल सकती है।

समस्या को अतिरिक्त चाबियों और तालों की एक श्रृंखला के साथ हल किया जा सकता है, लेकिन इस दृष्टिकोण की तुरंत आवश्यकता होगी много चाबियाँ और ताले. आप तय करते हैं कि आदर्श डिज़ाइन कुंजी साझा करना होगा ताकि सुरक्षा पूरी तरह से एक व्यक्ति पर निर्भर न रहे। आप यह भी निष्कर्ष निकालते हैं कि टुकड़ों की संख्या के लिए कुछ सीमा होनी चाहिए ताकि यदि एक टुकड़ा खो जाए (या यदि कोई व्यक्ति छुट्टी पर जाता है), तो पूरी कुंजी कार्यशील बनी रहे।

एक राज को कैसे साझा करें

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

सुरक्षा की दृष्टि से, इस योजना की एक महत्वपूर्ण विशेषता यह है कि हमलावर को तब तक कुछ भी पता नहीं चलना चाहिए जब तक कि उसके पास कम से कम न हो भागों. यहां तक ​​कि उपस्थिति भी भागों को कोई जानकारी नहीं देनी चाहिए. इसे हम संपत्ति कहते हैं अर्थ संबंधी सुरक्षा.

बहुपद प्रक्षेप

शमीर दहलीज योजना अवधारणा के इर्द-गिर्द निर्मित बहुपद प्रक्षेप. यदि आप इस अवधारणा से परिचित नहीं हैं, तो यह वास्तव में काफी सरल है। वास्तव में, यदि आपने कभी किसी ग्राफ़ पर बिंदु बनाए हैं और फिर उन्हें रेखाओं या वक्रों से जोड़ा है, तो आप पहले ही इसका उपयोग कर चुके हैं!

दो बिंदुओं के माध्यम से आप घात 2 वाले असीमित संख्या में बहुपद बना सकते हैं। उनमें से केवल एक को चुनने के लिए, आपको तीसरे बिंदु की आवश्यकता है। चित्रण: विकिपीडिया

घात एक वाले बहुपद पर विचार करें, . यदि आप इस फ़ंक्शन को ग्राफ़ पर प्लॉट करना चाहते हैं, तो आपको कितने बिंदुओं की आवश्यकता होगी? खैर, हम जानते हैं कि यह एक रैखिक फलन है जो एक रेखा बनाता है और इसलिए इसे कम से कम दो बिंदुओं की आवश्यकता होती है। इसके बाद, घात दो वाले बहुपद फलन पर विचार करें, . यह एक द्विघात फलन है, इसलिए ग्राफ़ बनाने के लिए कम से कम तीन बिंदुओं की आवश्यकता होती है। घात तीन वाले बहुपद के बारे में क्या ख्याल है? कम से कम चार अंक. और इतने पर और आगे।

इस संपत्ति के बारे में वास्तव में अच्छी बात यह है कि कम से कम बहुपद फलन की डिग्री दी गई है अंक, हम इस बहुपद फलन के लिए अतिरिक्त अंक प्राप्त कर सकते हैं। हम इन अतिरिक्त बिंदुओं का एक्सट्रपलेशन कहते हैं बहुपद प्रक्षेप.

एक रहस्य बनाना

आप पहले ही समझ गए होंगे कि यहीं पर शमीर की चतुर योजना काम आती है। चलिए बताते हैं अपना राज़ - क्या . हम पलट सकते हैं ग्राफ़ पर एक बिंदु तक और डिग्री के साथ एक बहुपद फलन लेकर आएं , जो इस बात को संतुष्ट करता है। आइए हम आपको वह याद दिला दें आवश्यक अंशों की हमारी सीमा होगी, इसलिए यदि हम सीमा को तीन अंशों पर सेट करते हैं, तो हमें घात दो के साथ एक बहुपद फलन चुनना होगा।

हमारे बहुपद का रूप होगा जहां и - बेतरतीब ढंग से चयनित सकारात्मक पूर्णांक। हम केवल डिग्री के साथ एक बहुपद का निर्माण कर रहे हैं , जहां मुक्त गुणांक  - यह हमारा रहस्य है , और बाद वाले प्रत्येक के लिए शर्तों में एक यादृच्छिक रूप से चयनित सकारात्मक गुणांक है। यदि हम मूल उदाहरण पर लौटते हैं और मान लेते हैं , तो हमें फ़ंक्शन मिलता है .

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

रहस्य पुनः प्राप्त करना

हम पहले ही बहुपद प्रक्षेप की अवधारणा पर चर्चा कर चुके हैं और यह कैसे शमीर की दहलीज योजना को रेखांकित करता है . जब चार में से कोई तीन ट्रस्टी बहाल करना चाहें , उन्हें केवल प्रक्षेप करने की आवश्यकता है अपने अनूठे बिंदुओं के साथ। ऐसा करने के लिए, वे अपने अंक निर्धारित कर सकते हैं और निम्न सूत्र का उपयोग करके लैग्रेंज इंटरपोलेशन बहुपद की गणना करें। यदि प्रोग्रामिंग आपके लिए गणित की तुलना में अधिक स्पष्ट है, तो पीआई अनिवार्य रूप से एक ऑपरेटर है for, जो सभी परिणामों को गुणा करता है, और सिग्मा है for, जो सब कुछ जोड़ता है।

में हम इसे इस प्रकार हल कर सकते हैं और अपना मूल बहुपद फलन लौटा सकते हैं:

क्योंकि हम यह जानते हैं , स्वास्थ्य लाभ सरलता से किया गया:

असुरक्षित पूर्णांक अंकगणित का उपयोग करना

हालाँकि हमने शमीर के मूल विचार को सफलतापूर्वक लागू किया है , हम एक ऐसी समस्या से बचे हुए हैं जिसे हमने अब तक नजरअंदाज किया है। हमारा बहुपद फ़ंक्शन असुरक्षित पूर्णांक अंकगणित का उपयोग करता है। ध्यान दें कि हमारे फ़ंक्शन के ग्राफ़ पर हमलावर द्वारा प्राप्त प्रत्येक अतिरिक्त बिंदु के लिए, अन्य बिंदुओं के लिए कम संभावनाएँ होती हैं। आप इसे अपनी आँखों से देख सकते हैं जब आप पूर्णांक अंकगणित का उपयोग करके एक बहुपद फलन के लिए अंकों की बढ़ती संख्या को आलेखित करते हैं। यह हमारे घोषित सुरक्षा लक्ष्य के प्रतिकूल है, क्योंकि हमलावर को तब तक कुछ भी पता नहीं होना चाहिए जब तक कि उसे कम से कम पता न चल जाए टुकड़े टुकड़े।

यह प्रदर्शित करने के लिए कि पूर्णांक अंकगणितीय सर्किट कितना कमजोर है, उस परिदृश्य पर विचार करें जिसमें एक हमलावर ने दो अंक प्राप्त किए और सार्वजनिक जानकारी जानता है कि . इस जानकारी से वह यह निष्कर्ष निकाल सकते हैं , दो के बराबर, और ज्ञात मानों को सूत्र में प्लग करें и .

फिर हमलावर ढूंढ सकता है , गिनती :

चूँकि हमने परिभाषित किया है यादृच्छिक रूप से चयनित सकारात्मक पूर्णांकों की संख्या सीमित है . इस जानकारी का उपयोग करके, एक हमलावर निष्कर्ष निकाल सकता है , चूँकि 5 से अधिक कुछ भी करेगा नकारात्मक। जब से हमने ठान लिया है यह सच साबित हो रहा है

इसके बाद हमलावर संभावित मूल्यों की गणना कर सकता है जगह в :

के लिए सीमित विकल्पों के साथ यह स्पष्ट हो जाता है कि मूल्यों का चयन करना और जांचना कितना आसान है . यहां केवल पांच विकल्प हैं.

असुरक्षित पूर्णांक अंकगणित के साथ समस्या का समाधान

इस भेद्यता को खत्म करने के लिए, शमीर प्रतिस्थापन, मॉड्यूलर अंकगणित का उपयोग करने का सुझाव देता है पर जहां и - सभी अभाज्य संख्याओं का समुच्चय।

आइए जल्दी से याद करें कि मॉड्यूलर अंकगणित कैसे काम करता है। सूइयों वाली घड़ी एक परिचित अवधारणा है। वह एक घड़ी का उपयोग करती है . जैसे ही घंटे की सुई बारह पार करती है, वह एक पर लौट आती है। इस प्रणाली की एक दिलचस्प विशेषता यह है कि केवल घड़ी को देखकर, हम यह अनुमान नहीं लगा सकते कि घंटे की सुई ने कितने चक्कर लगाए हैं। हालाँकि, यदि हम जानते हैं कि घंटे की सुई 12 से चार बार गुजर चुकी है, तो हम एक सरल सूत्र का उपयोग करके बीते घंटों की संख्या पूरी तरह से निर्धारित कर सकते हैं। जहां  हमारा विभाजक है (यहाँ)। ),  गुणांक है (भाजक कितनी बार बिना किसी शेषफल के मूल संख्या में जाता है, यहाँ ), और  शेष है, जो आम तौर पर एक मॉड्यूलो ऑपरेटर कॉल लौटाता है (यहां)। ). इन सभी मूल्यों को जानने से हमें समीकरण को हल करने की अनुमति मिलती है , लेकिन यदि हम गुणांक चूक जाते हैं, तो हम मूल मान को कभी भी पुनर्स्थापित नहीं कर पाएंगे।

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

इस नए उदाहरण का उपयोग करते हुए, मान लें कि हमलावर ने इनमें से दो नए बिंदु सीखे हैं, , और सार्वजनिक जानकारी . इस बार, हमलावर, उसके पास मौजूद सभी जानकारी के आधार पर, निम्नलिखित कार्यों को आउटपुट करता है  सभी धनात्मक पूर्णांकों का समुच्चय है, और मापांक गुणांक का प्रतिनिधित्व करता है .

अब हमारा हमलावर फिर से मिल गया , गणना :

फिर वह दोबारा कोशिश करता है जगह в :

इस बार उनके सामने एक गंभीर समस्या है. सूत्र में मान गुम हैं , и . चूँकि इन चरों के संयोजनों की संख्या अनंत है, इसलिए वह कोई अतिरिक्त जानकारी प्राप्त नहीं कर सकता।

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

शमीर की गुप्त साझाकरण योजना सुझाती है सूचना सिद्धांत के दृष्टिकोण से सुरक्षा. इसका मतलब यह है कि गणित असीमित कंप्यूटिंग शक्ति वाले हमलावर के खिलाफ भी प्रतिरोधी है। हालाँकि, सर्किट में अभी भी कई ज्ञात समस्याएँ हैं।

उदाहरण के लिए, शमीर की योजना नहीं बनती है जांचे जाने वाले टुकड़े, अर्थात्, लोग स्वतंत्र रूप से नकली अंश प्रस्तुत कर सकते हैं और सही रहस्य की पुनर्प्राप्ति में हस्तक्षेप कर सकते हैं। पर्याप्त जानकारी वाला एक शत्रुतापूर्ण टुकड़ा रक्षक परिवर्तन करके दूसरा टुकड़ा भी उत्पन्न कर सकता है अपने विवेक पर. का उपयोग करके इस समस्या का समाधान किया जाता है सत्यापन योग्य गुप्त साझाकरण योजनाएँ, जैसे फेल्डमैन की योजना।

एक और समस्या यह है कि किसी भी टुकड़े की लंबाई संबंधित रहस्य की लंबाई के बराबर होती है, इसलिए रहस्य की लंबाई निर्धारित करना आसान है। इस समस्या को छोटी-छोटी बातों से हल किया जा सकता है गद्दी एक निश्चित लंबाई तक मनमानी संख्याओं के साथ रहस्य।

अंत में, यह ध्यान रखना महत्वपूर्ण है कि हमारी सुरक्षा संबंधी चिंताएँ डिज़ाइन से परे भी विस्तारित हो सकती हैं। वास्तविक दुनिया के क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए, अक्सर साइड-चैनल हमलों का खतरा होता है जहां एक हमलावर एप्लिकेशन निष्पादन समय, कैशिंग, क्रैश इत्यादि से उपयोगी जानकारी निकालने का प्रयास करता है। यदि यह एक चिंता का विषय है, तो विकास के दौरान कार्यों और निरंतर-समय लुकअप जैसे सुरक्षात्मक उपायों का उपयोग करने, मेमोरी को डिस्क पर सहेजे जाने से रोकने और कई अन्य विचारों पर सावधानीपूर्वक विचार किया जाना चाहिए जो इस आलेख के दायरे से परे हैं।

डेमो

पर यह पृष्ठ शमीर की गुप्त साझाकरण योजना का एक इंटरैक्टिव प्रदर्शन है। पुस्तकालय पर आधारित प्रदर्शन ssss-js, जो स्वयं लोकप्रिय प्रोग्राम का जावास्क्रिप्ट पोर्ट है ssss. ध्यान दें कि बड़े मानों की गणना , и कुछ समय लग सकता है।

स्रोत: www.habr.com