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

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

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

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

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

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

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

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

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

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

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

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

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

रहस्य बनाना

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

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

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

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

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

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

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

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

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

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

हमलावर तब यह पता लगा सकता है कि , गिनती करके :

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

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

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

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

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

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

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

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

अब हमारा हमलावर इसे फिर से पाता है , गणना करके :

फिर वह फिर से पीछे हटने की कोशिश करता है , प्रतिस्थापित в :

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

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

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

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

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

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

डेमो

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

स्रोत: www.habr.com