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

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

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

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

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

कसरी गोप्य साझा गर्ने

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

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

बहुपदीय प्रक्षेपण

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

दुईवटा बिन्दुहरू मार्फत तपाईंले डिग्री 2 को बहुपदहरूको असीमित संख्या कोर्न सक्नुहुन्छ। तिनीहरूबाट एक मात्र छनोट गर्न, तपाईंलाई तेस्रो बिन्दु चाहिन्छ। दृष्टान्त: विकिपीडिया

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

यस सम्पत्तीको बारेमा साँच्चै राम्रो कुरा यो हो कि, बहुपद प्रकार्यको डिग्री दिएर र कम्तिमा बिन्दुहरू, हामी यस बहुपद प्रकार्यको लागि थप बिन्दुहरू प्राप्त गर्न सक्छौं। हामी यी अतिरिक्त बिन्दुहरूको एक्स्ट्रापोलेसन भन्छौं बहुपदीय प्रक्षेपण.

गोप्य बनाउँदै

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

हाम्रो बहुपदको फारम हुनेछ कहाँ и - अनियमित रूपमा चयन गरिएको सकारात्मक पूर्णाङ्कहरू। हामी केवल डिग्री संग बहुपद निर्माण गर्दैछौं , जहाँ मुक्त गुणांक  - यो हाम्रो रहस्य हो , र त्यसपछिका प्रत्येकको लागि सर्तहरू अनियमित रूपमा चयन गरिएको सकारात्मक गुणांक हो। यदि हामी मौलिक उदाहरणमा फर्क्यौं र मानौं , त्यसपछि हामीले प्रकार्य पाउँछौं .

यस बिन्दुमा हामी जडान गरेर टुक्राहरू उत्पन्न गर्न सक्छौं मा अद्वितीय पूर्णांक कहाँ (किनभने यो हाम्रो रहस्य हो)। यस उदाहरणमा, हामी तीनको थ्रेसहोल्डको साथ चार टुक्राहरू वितरण गर्न चाहन्छौं, त्यसैले हामी अनियमित रूपमा अंकहरू उत्पन्न गर्छौं। र प्रत्येक चार विश्वसनीय व्यक्तिहरू, कुञ्जीका संरक्षकहरूलाई एक-एक बिन्दु पठाउनुहोस्। हामीले जनतालाई पनि थाहा दियौं , किनकि यो सार्वजनिक जानकारी मानिन्छ र पुन: प्राप्तिको लागि आवश्यक छ .

गोप्य पुन: प्राप्ति

हामीले बहुपदीय प्रक्षेपणको अवधारणा र यसले कसरी शमिरको थ्रेसहोल्ड योजनालाई अण्डर गर्छ भन्ने बारेमा छलफल गरिसकेका छौं। । जब चार मध्ये कुनै तीन ट्रस्टीहरू पुनर्स्थापना गर्न चाहन्छन् , तिनीहरूले मात्र interpolate गर्न आवश्यक छ आफ्नै अद्वितीय बिन्दुहरु संग। यो गर्न, तिनीहरूले आफ्नो अंक निर्धारण गर्न सक्नुहुन्छ र तलको सूत्र प्रयोग गरी Lagrange interpolation polynomial गणना गर्नुहोस्। यदि प्रोग्रामिङ तपाईलाई गणित भन्दा स्पष्ट छ, तब pi अनिवार्य रूपमा एक अपरेटर हो for, जसले सबै परिणामहरूलाई गुणन गर्छ, र सिग्मा हो for, जसले सबै कुरा थप्छ।

मा हामी यसलाई यसरी समाधान गर्न सक्छौं र हाम्रो मूल बहुपद प्रकार्य फर्काउन सक्छौं:

हामीलाई थाहा भएकोले , रिकभरी सरल रूपमा गरियो:

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

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

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

त्यसपछि आक्रमणकारी फेला पार्न सक्छ , गणना :

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

आक्रमणकारीले त्यसपछि सम्भावित मानहरू गणना गर्न सक्छ प्रतिस्थापन गर्दै в :

को लागि सीमित विकल्पहरु संग यो स्पष्ट हुन्छ कि यो मान चयन गर्न र जाँच गर्न कति सजिलो छ । यहाँ केवल पाँच विकल्पहरू छन्।

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

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

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

हामीले हाम्रो अघिल्लो उदाहरणमा योजना लागू गरेर र प्रयोग गरेर यसले हाम्रो योजनाको सुरक्षा कसरी सुधार गर्छ भनेर देखाउन सक्छौं । हाम्रो नयाँ बहुपद प्रकार्य र नयाँ बिन्दुहरू । अब कुञ्जी रक्षकहरूले हाम्रो प्रकार्यलाई पुन: निर्माण गर्नको लागि एक पटक फेरि बहुपदीय प्रक्षेपण प्रयोग गर्न सक्छन्, केवल यस पटक थप र गुणन कार्यहरू मोड्युलो कटौतीको साथ हुनुपर्छ। (जस्तै ).

यो नयाँ उदाहरण प्रयोग गरेर, मानौं कि आक्रमणकारीले यी दुईवटा नयाँ बिन्दुहरू सिके, , र सार्वजनिक जानकारी । यस पटक, आक्रमणकारीले आफूसँग भएको सबै जानकारीको आधारमा निम्न प्रकार्यहरू आउटपुट गर्दछ, जहाँ  सबै सकारात्मक पूर्णांकहरूको सेट हो, र मोड्युलस गुणांक प्रतिनिधित्व गर्दछ .

अब हाम्रो आक्रमणकारी फेरि फेला पार्छ , गणना गर्दै :

त्यसपछि उसले फेरि प्रयास गर्छ प्रतिस्थापन गर्दै в :

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

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

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

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

अर्को समस्या यो हो कि कुनै पनि टुक्राको लम्बाइ सम्बन्धित गोप्यको लम्बाइ बराबर छ, त्यसैले गोप्यको लम्बाइ निर्धारण गर्न सजिलो छ। यो समस्या मामूली द्वारा हल गर्न सकिन्छ प्याडिङ एक निश्चित लम्बाइ सम्म मनमानी संख्या संग गोप्य।

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

डेमो

मा यो पृष्ठ शामीरको गोप्य साझेदारी योजनाको एक अन्तरक्रियात्मक प्रदर्शन छ। पुस्तकालयमा आधारित प्रदर्शन ssss-js, जुन आफैमा लोकप्रिय कार्यक्रमको जाभास्क्रिप्ट पोर्ट हो आइतएसदशनि। ध्यान दिनुहोस् कि ठूलो मानहरू गणना गर्दै , и केहि समय लिन सक्दछ।

स्रोत: www.habr.com