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

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

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

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

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

कैसे एक रहस्य साझा करने के लिए

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

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

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

शमीर दहलीज योजना $$$(k, n)$ बहुपद प्रक्षेप की अवधारणा के आसपास निर्मित। यदि आप इस अवधारणा से परिचित नहीं हैं, तो यह वास्तव में काफी सरल है। सामान्य तौर पर, यदि आपने कभी चार्ट पर अंक खींचे हैं, और फिर उन्हें लाइनों या घटता के साथ जोड़ा है, तो आप पहले से ही इसका इस्तेमाल करते हैं!


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

डिग्री एक के साथ एक बहुपद पर विचार करें, $$$f (x) = x + 2$ । यदि आप इस फ़ंक्शन को चार्ट पर प्लॉट करना चाहते हैं, तो आपको कितने बिंदुओं की आवश्यकता है? खैर, हम जानते हैं कि यह एक रैखिक कार्य है जो एक रेखा बनाता है और इसलिए कम से कम दो बिंदुओं की आवश्यकता होती है। अगला, दो डिग्री के साथ एक बहुपद समारोह पर विचार करें, $$$f (x) = x ^ 2 + 2x + 1$ । यह एक द्विघात कार्य है, इसलिए ग्राफ बनाने के लिए कम से कम तीन बिंदुओं की आवश्यकता होती है। डिग्री तीन के साथ एक बहुपद के बारे में क्या? कम से कम चार अंक। वगैरह वगैरह।

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

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

आपको पहले ही पता चल गया होगा कि शमीर की स्मार्ट योजना यहां चल रही है। मान लीजिए हमारा राज $$$एस$ क्या वह $$$42$ । हम मोड़ सकते हैं $$$एस$ चार्ट के एक बिंदु पर $$$(0.42)$ और डिग्री के साथ एक बहुपद समारोह के साथ आते हैं $$$k-1$ जो इस बात को संतुष्ट करता है। उसको याद करो $$$k$ आवश्यक टुकड़ों के लिए हमारी सीमा होगी, इसलिए यदि हम तीन टुकड़े निर्धारित करते हैं, तो हमें डिग्री दो के साथ एक बहुपद समारोह का चयन करना होगा।

हमारा बहुपद रूप ले लेगा $$$f (x) = a_0 + axx + a2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1}$ जहाँ $$$a_0 = S$ और $$$a_1, ..., a_ {k-1}$ - बेतरतीब ढंग से चयनित सकारात्मक पूर्णांक। हम सिर्फ एक डिग्री के साथ एक बहुपद का निर्माण कर रहे हैं $$$k-1$ मुक्त गुणांक कहां है $$$a_0$ हमारा रहस्य है $$$एस$ , और निम्न में से प्रत्येक $$$k-1$ सदस्यों के पास एक यादृच्छिक रूप से चयनित सकारात्मक गुणांक है। यदि आप मूल उदाहरण पर वापस जाते हैं और मान लेते हैं $$$S = 42, k = 3, a_1, ..., a_ {k-1} = [3,5]$ तब हमें फंक्शन मिलता है $$$f (x) = 42 + 3x + 5x ^ 2$ ।

इस स्तर पर, हम कनेक्ट करके टुकड़े उत्पन्न कर सकते हैं $$$एन$ में अद्वितीय पूर्णांक $$$f (x) = 42 + 3x + 5x ^ 2$ जहाँ $$$x \ neq 0$ (क्योंकि यह हमारा रहस्य है)। इस उदाहरण में, हम तीन की सीमा के साथ चार टुकड़े वितरित करना चाहते हैं, इसलिए हम बेतरतीब ढंग से अंक उत्पन्न करते हैं $$$(18, 1716), (27, 3768), (31, 4940), (35, 6272)$ और चार विश्वसनीय लोगों, प्रमुख रखवाले में से प्रत्येक को एक बिंदु भेजें। हम लोगों को भी बताते हैं कि $$$k = 3$ , क्योंकि यह सार्वजनिक जानकारी माना जाता है और वसूली के लिए आवश्यक है $$$एस$ ।

गुप्त वसूली

हम पहले से ही बहुपद प्रक्षेप की अवधारणा और इस तथ्य पर चर्चा कर चुके हैं कि यह शमीर सीमा योजना पर आधारित है $$$(k, n)$ । जब चार में से कोई भी तीन ठीक होना चाहते हैं $$$एस$ उन्हें केवल प्रक्षेप करने की आवश्यकता है $$$च (0)$ अपने स्वयं के अनूठे बिंदुओं के साथ। ऐसा करने के लिए, वे अपने अंक निर्धारित कर सकते हैं $$$(x_1, y_1), ..., (x_k, y_k) = (18, 1716), (27, 3768), (31, 4940)$ और निम्न सूत्र का उपयोग करके लैग्रेग प्रक्षेप प्रक्षेप बहुपद की गणना करें। यदि प्रोग्रामिंग गणित की तुलना में आपके लिए अधिक समझ में आता है, तो पीआई अनिवार्य रूप से एक बयान के for है जो सभी परिणामों को गुणा करता है, और सिग्मा एक बयान के for है जो सब कुछ जोड़ता है।

$$

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

$$

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

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

$$

$$\ start {align} P (x) & = {y_1} \ left ({x-x_2 \ over x_1-x_2} \ cdot {x-x_3 \ over x_1-x_3} \ दाएँ) + {y}} \ left ( {x-x_1 \ ओवर x_2-x_1} \ cdot {x - \ _ 3 \ _ x_2-x_3} \ right) + {y_3} \ left ({x-x_1 \ _ x_3-x_1 \ _ cdot {x-x_2} से अधिक x_3-x_2} \ right) \\ P (x) & = {1716} \ left ({x-27 \ over 18-27} \ cdot {x-31 \ over 18-31} \ right) + {3768 } \ बायां ({x-18 \ over 27-18} \ cdot {x-31 \ over 27-31} \ right) + {4940} \ left ({x-18 \ _ 31-18} \ cdot {x -27 \ ओवर 31-27} \ राइट) \\ पी (एक्स) और = 42 + 3x + 5x ^ 2 \ अंत {गठबंधन}$$

क्योंकि हम जानते हैं कि $$$S = P (0)$ , वसूली $$$एस$ बस बाहर किया:

$$

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

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

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

यह दिखाने के लिए कि पूर्णांक अंकगणित वाली योजना कितनी कमजोर है, एक परिदृश्य पर विचार करें जिसमें एक हमलावर को दो अंक मिले $$$(18, 1716), (27,3768)$ और सार्वजनिक जानकारी है कि जानता है $$$k = 3$ । इस जानकारी से वह कटौती कर सकता है $$$च (x)$ दो के बराबर और सूत्र में ज्ञात मूल्यों को जोड़ते हैं $$$x$ और $$$च (x)$ ।

$$

$$\ start {align} f (x) & = a_0 + axx + a2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1} \\ f (x) & S + axx + a_2x ^ 2 \\ f (18) \ equiv 1716 & = S + a_118 + a_218 ^ 2 \\ f (27) \ equiv 3768 & = S + a_127 + a_227: 2 \ end {गठबंधन}$$

तब हमलावर मिल सकता है $$$a_1$ , पर विचार $$$f (27) - f (18)$ :

$$

$$\ start {align} 3768 - 1716 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) \\ 2052 & = 9a_1 + 405a_2 \\ 9+_1 और = 2052 - 405a_2 \\ a_1 & = \ _ frac {2052 - 405a_2} {9} \\ a_1 & = 228 - 45a_2 \ end {संरेखित}$$

जब से हमने पहचान की है $$$a_1, ..., a_ {k-1}$ बेतरतीब ढंग से चयनित सकारात्मक पूर्णांकों के रूप में, संभव की एक सीमित संख्या है $$$a_2$ । इस जानकारी का उपयोग करते हुए, एक हमलावर अनुमान लगा सकता है $$$a_2 \ [1,2,3,4,5] $ मे$ , क्योंकि सब कुछ जो 5 से अधिक है वह करेगा $$$a_1$ नकारात्मक। यह सच है, जैसा कि हमने निर्धारित किया है $$$a_2 = 5$

फिर हमलावर संभावित मूल्यों की गणना कर सकता है $$$एस$ जगह $$$a_1$ में $$$f (18)$ :

$$

$$\ start {align} 1716 & = S + a_118 + a_218 ^ 2 \\ 1716 & = S + 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 \\ 1716 - S & 18 \ left (228) 45a_2 \ right) + a_218 ^ 2 \\ -S & = 18 \ left (228 - 45a_2 \ right) + 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 \ अंत {गठबंधन}$$

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

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

इस भेद्यता को खत्म करने के लिए, शमीर ने मॉड्यूलर अंकगणितीय, प्रतिस्थापन का उपयोग करने का सुझाव दिया $$$च (x)$ पर $$$f (x) \ mod p$ जहाँ $$$p \ in \ mathbb {P}: p> S, p> n$ और $$$\ mathbb {P}$ - सभी अपराधों का सेट।

जल्दी से याद रखें कि मॉड्यूलर अंकगणित कैसे काम करता है। तीर के साथ एक घड़ी पहले से ही एक परिचित अवधारणा है। वह ऐसी घड़ियों का उपयोग करती है जो हैं $$$\ mod 12$ । जैसे ही घंटे का हाथ बारह से गुजरता है, यह एक पर लौटता है। इस प्रणाली की एक दिलचस्प संपत्ति यह है कि बस घड़ी को देखकर, हम यह नहीं घटा सकते हैं कि घंटे के हाथ में कितने चक्कर हैं। हालांकि, अगर हम जानते हैं कि घंटे का हाथ 12 बार चार बार बीत चुका है, तो हम एक सरल सूत्र का उपयोग करके पूरी तरह से बीते हुए घंटों की संख्या निर्धारित कर सकते हैं $$$a = mq + r$ जहाँ $$$एम$ क्या हमारा विभाजक (यहां है) $$$m = 12$ ) $$$q$ क्या गुणांक है (शेष के बिना भाजक कितनी बार मूल संख्या में जाता है, यहां $$$q = 4$ ), और $$$आर$ शेष है, जो आमतौर पर ऑपरेटर की कॉल मोडुलो (यहां) लौटाता है $$$r = 1.5$ )। इन सभी मूल्यों को जानने से हमें समीकरण को हल करने की अनुमति मिलती है $$$a = 49.5$ लेकिन अगर हम गुणांक को छोड़ देते हैं, तो हम मूल मूल्य को कभी भी बहाल नहीं कर सकते।

आप यह प्रदर्शित कर सकते हैं कि यह हमारे पिछले उदाहरण और उपयोग के लिए सर्किट को लागू करके हमारे सर्किट की सुरक्षा को कैसे बेहतर बनाता है $$$p = 73$ । हमारे नए बहुपद समारोह $$$f '(x) = 42 + 3x + 5x ^ 2 \ mod 73$ , और नए अंक $$$(18, 37), (27, 45), (31, 49), (35, 67)$ । अब, मुख्य रखवाले एक बार फिर हमारे कार्य को बहाल करने के लिए बहुपद प्रक्षेप का उपयोग कर सकते हैं, केवल इस बार इसके अलावा और गुणन क्रियाओं को एक मोडुलो कमी के साथ होना चाहिए $$$पी$ (उदाहरण के लिए $$$48 + 93 \ mod 73 = 68$ )।

इस नए उदाहरण का उपयोग करते हुए, मान लीजिए कि हमलावर ने इन नए बिंदुओं में से दो को मान्यता दी है, $$$(18, 37), (27, 45)$ , और सार्वजनिक जानकारी $$$k = 3, p = 73$ । इस समय, हमलावर, उसके पास मौजूद सभी सूचनाओं के आधार पर, निम्नलिखित कार्यों को प्रदर्शित करता है, जहां $$$\ mathbb {N}$ सभी धनात्मक पूर्णांक का सेट है, और $$$q_x$ मॉड्यूल के गुणांक का प्रतिनिधित्व करता है $$$f '(x)$ ।

$$

$$\ start {align} 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 {संरेखित}$$

अब हमारा हमलावर फिर से मिल जाता है $$$a_1$ कंप्यूटिंग के द्वारा $$$f '(27) - f' (18)$ :

$$

$$\ start {align} 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}) \ n संरेखित}$$

फिर वह वापस लेने की कोशिश करता है $$$एस$ जगह $$$a_1$ में $$$f '(18)$ :

$$

$$\ start {align} 37 & = S + 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ right) + a_218 ^ 2 - 73q_ {18} \\ -S & = 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) का दायां + a_218 ^ 2 - 73q_ {18} - 37 \\ S & = -18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18) - q_ {27}) ) \ right) - 324a_2 + 73q_ {18} + 37 \\ S & = 486a_2 + 21 + 219q_ {18} - 146q_ {27} \ अंत {गठबंधन}$$

इस बार उसे एक गंभीर समस्या है। सूत्र में कोई मूल्य नहीं हैं $$$a_2$ । $$$q_ {18}$ और $$$q_ {27}$ । चूंकि इन चरों के संयोजनों की अनंत संख्या है, इसलिए यह कोई अतिरिक्त जानकारी प्राप्त नहीं कर सकता है।

सुरक्षा संबंधी बातें

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

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

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

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

डेमो

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