अण्डाकार क्रिप्टोग्राफी: सिद्धांत

हाय% उपयोगकर्ता नाम%!
हाल ही में, हबल पर एक बहुत ही विवादास्पद लेख प्रकाशित हुआ था, जिसका शीर्षक था "विशेषज्ञ एक क्रिप्टोकरंसी के लिए तैयार होने का आग्रह करते हैं । " ईमानदारी से, मैं लेखकों के निष्कर्ष से सहमत नहीं हूं कि "गोलैक्टेको खतरा" है, सभी जल्द ही दरार हो जाएंगे और एक प्रकार का अनाज मूल्य में बढ़ जाएगा। हालांकि, यह वह नहीं है जिसके बारे में मैं बात करना चाहता हूं।
उस लेख पर टिप्पणियों में, मैंने राय व्यक्त की कि कुछ मामलों में बोलने वाले सही हैं और यह अण्डाकार क्रिप्टोग्राफी पर स्विच करने के लिए उच्च समय है। ठीक है, वास्तव में, क्या किसी ने इंटरनेट पर ईसीडीएसए प्रमाण पत्र देखा है? यद्यपि मानक पहले से ही लगभग 13 वर्ष पुराना है, हम हमेशा की तरह अच्छे पुराने आरएसए का उपयोग करना जारी रखते हैं। सामान्य तौर पर, मैंने यह कहा, और जैसा कि अक्सर होता है, मैंने इस बारे में सोचा कि क्या "अण्डाकार" के लिए संक्रमण इतना आवश्यक है? और किस तरह का जानवर ऐसी अण्डाकार क्रिप्टोग्राफी है? पेशेवरों, विपक्ष, सूक्ष्मताएं क्या हैं। एक शब्द में, आइए समझते हैं।

अण्डाकार वक्र

एक अण्डाकार वक्र, वीयरस्ट्रैस समीकरण द्वारा वर्णित बिंदुओं का एक समूह है:

विशिष्ट अण्डाकार वक्र ग्राफ जिसे आप स्पॉइलर के नीचे देख सकते हैं:

पहले 4 आंकड़ों में प्रस्तुत अण्डाकार वक्रों को सुचारू कहा जाता है। जबकि दो निचले वक्र तथाकथित के हैं एकवचन अण्डाकार वक्र।
चिकनी अण्डाकार घटता के लिए, निम्नलिखित असमानता रखती है:

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

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

"जोड़" का बीजगणितीय प्रतिनिधित्व

हम सूत्र के रूप में दो बिंदुओं को जोड़ते हैं:

बिंदु P के निर्देशांक (x _p , y _p ) और बिंदु Q के निर्देशांक क्रमश: (x _q , y _q ) हो जाने दें। हम हिसाब लगाते हैं

और फिर P + Q बिंदु के निर्देशांक बराबर होंगे:

क्रिप्टोग्राफी में अण्डाकार वक्र

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

क्रिप्टोग्राफी में, दो प्रकार के अण्डाकार वक्रों पर विचार किया जाता है: एक परिमित क्षेत्र पर - अवशेषों का वलय modulo a prime number। और मैदान पर - बाइनरी परिमित क्षेत्र।
एक क्षेत्र पर अण्डाकार घटता है एक महत्वपूर्ण लाभ क्षेत्र तत्व है आसानी से एन-बिट कोड शब्दों के रूप में प्रतिनिधित्व किया जा सकता है, यह आपको दीर्घवृत्त एल्गोरिदम के हार्डवेयर कार्यान्वयन की गति को बढ़ाने की अनुमति देता है।

एक परिमित क्षेत्र पर अण्डाकार वक्रों पर सभी गणितीय कार्य एक परिमित क्षेत्र के नियमों के अनुसार किए जाते हैं, जिस पर एक अण्डाकार वक्र का निर्माण किया जाता है। यानी गणना करने के लिए, उदाहरण के लिए, अवशेषों की अंगूठी के ऊपर वक्र E के दो बिंदुओं का योग सभी ऑपरेशन मोडुलो पी।

हालांकि, वहाँ नुकसान कर रहे हैं। यदि हम एक बाइनरी परिमित क्षेत्र से दो समान तत्व जोड़ते हैं, तो हमें परिणाम के रूप में 0 मिलता है, क्योंकि इसके अलावा मोडुलो होता है 2. इसका मतलब है कि इस तरह के क्षेत्र की विशेषता 2. फार्म का एक अण्डाकार वक्र है

क्षेत्र के ऊपर 2 या 3 विशेषताओं का वर्णन विलक्षण हो जाता है, और जैसा कि पहले ही ऊपर उल्लेख किया गया है, यह क्रिप्टोग्राफी में एकवचन घटता का उपयोग करने का एक असफल विचार है।

इसलिए, एक बाइनरी परिमित क्षेत्र पर, फॉर्म के घटता का उपयोग किया जाता है:


अण्डाकार क्रिप्टोग्राफी की एक अन्य महत्वपूर्ण अवधारणा अण्डाकार वक्र का क्रम है , जो एक परिमित क्षेत्र पर वक्र के बिंदुओं की संख्या को दर्शाता है।
हसी के प्रमेय में कहा गया है कि यदि N एक वक्र में बिंदुओं की संख्या है जो कि q तत्वों के साथ एक क्षेत्र Zq से अधिक है तो निम्नलिखित गुण हैं:


क्योंकि बाइनरी फाइनल फील्ड 2 ⁿ तत्वों से मिलकर हम कह सकते हैं कि वक्र का क्रम के बराबर है जहाँ ।

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

अण्डाकार वक्र क्रिप्टोग्राफी

एक परिमित क्षेत्र पर अण्डाकार वक्र के बिंदु एक समूह का प्रतिनिधित्व करते हैं। और जैसा कि हमने ऊपर उल्लेख किया है, इस समूह के लिए अतिरिक्त संचालन को परिभाषित किया गया है।
तदनुसार, हम संख्या जी के गुणन का प्रतिनिधित्व बिंदु G द्वारा G + G + .. + G के रूप में कर सकते हैं।

अब कल्पना करें कि हमारे पास एक संदेश है जो एक पूर्णांक के रूप में दर्शाया गया है। हम इसे अभिव्यक्ति का उपयोग करके एन्क्रिप्ट कर सकते हैं
सी = एम * जी।
सवाल यह है कि क को E (a, b), सिफरटेक् सी, और बिंदु G के मापदंडों को जानकर M को पुनर्स्थापित करना कितना मुश्किल है।
इस समस्या को अण्डाकार वक्र पर असतत लघुगणक कहा जाता है और इसका त्वरित समाधान नहीं होता है। इसके अलावा, यह माना जाता है कि अण्डाकार वक्र पर असतत लघुगणक समस्या परिमित क्षेत्रों में असतत लघुगणक समस्या की तुलना में हल करना अधिक कठिन है।

परिमित क्षेत्रों के लिए विकसित सबसे तेज़ तरीके अण्डाकार वक्रों के मामले में बेकार हैं।
तो एक असतत लघुगणक को हल करने के लिए जटिलता के साथ काफी तेज एल्गोरिदम हैं , जहां सी और डी कुछ स्थिरांक हैं, और पी क्षेत्र का आकार है। इस तरह के एल्गोरिदम को उपसंचालक कहा जाता है और अंतिम फ़ील्ड में असतत लघुगणक को खोलना अपेक्षाकृत आसान बनाता है, यदि 2 ¹⁰²⁴ के क्रम में फ़ील्ड का आकार बहुत बड़ा नहीं चुना गया है।
इसी समय, अण्डाकार वक्र पर असतत लघुगणक को हल करने की सबसे तेज़ विधियों में जटिलता होती है जहाँ q अण्डाकार वक्र के बिंदुओं की संख्या है।
इस प्रकार, 2 ⁸⁰ संचालन के स्थायित्व के स्तर को सुनिश्चित करने के लिए, यह आवश्यक है कि q = 2 ¹⁶⁰ । मुझे याद है कि परिमित क्षेत्र में असतत लघुगणक की गणना करते समय एक समान स्तर की जटिलता प्राप्त करने के लिए, आदेश q = 2 ^{1024 के} एक क्षेत्र की आवश्यकता होती है।

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

हमले के विकल्प

1. पॉलिगम-हेलमैन एल्गोरिथम । असतत लघुगणक को हल करने के लिए एक एल्गोरिथ्म। मान लीजिए कि एक अंडाकार वक्र में n अंकों की संख्या है। संख्या n को primes p ₁ , p ₂ , .., p _n में विघटित होने दें। विधि का सार असतत लघुगणक मापांक संख्या पी _i को खोजना है, और फिर चीनी शेष प्रमेय का उपयोग करके एक सामान्य समाधान प्राप्त करना है । हमले से हमें एक बड़ी समस्या में असत्य लघुगणक समस्या को कम करने की अनुमति मिलती है, लेकिन एक बहुत छोटे क्षेत्र के साथ। हमले का विरोध करने के लिए, आपको बस उन वक्रों को चुनने की आवश्यकता है जिनके अंकों की संख्या एक बहुत बड़ी अभाज्य संख्या से विभाजित है।
2. शंक एल्गोरिथ्म , बेहतर बेबी कदम / विशाल कदम के रूप में जाना जाता है। एक विशिष्ट उदाहरण समय स्मृति व्यापार बंद है। आकार n के समूह के लिए, आकार n ^{1/2 के} तालिकाओं की गणना की जाती है, फिर यह तालिका वांछित वस्तु की खोज करती है। एल्गोरिथम जटिलता ।
3. एकवचन और सुपरसिंगुलर वक्रों की भेद्यता । मैंने पहले ही उल्लेख किया है कि असतत लघुगणक समस्या को हल करने के लिए समाधान की कोई उपसक्रिय क्षमता नहीं है। वास्तव में, एक चेतावनी है, ऐसे तरीके हैं, लेकिन केवल एक निश्चित प्रकार के घटता के लिए: एकवचन और सुपरसिंगुलर। ऐसे घटता के विशेष गुण एक परिमित क्षेत्र में असतत लघुगणक समस्या पर अण्डाकार वक्र पर असतत लघुगणक समस्या को कम करना संभव बनाते हैं। तदनुसार, घटता के इस तरह के एक वर्ग के लिए, आकार में 160-320 बिट्स की मानक चाबियाँ वसाहीन रूप से कमजोर होंगी, जो हमलावरों को अपेक्षाकृत कम समय में गुप्त कुंजी को प्रकट करने की अनुमति देगा।
4. विषम घटता की भेद्यता मुझे आपको याद दिलाना है कि अण्डाकार वक्र के बिंदुओं की संख्या सूत्र द्वारा गणना की जाती है
   n = q + 1-t , जहां q प्रारंभिक क्षेत्र का आकार है। और उस वक्र को सुपरसिंगुलर कहा जाता है यदि t 2 से विभाज्य है।
   इसलिए, पहली नज़र में यह घटता उपयोग करने के लिए एक अच्छे विचार की तरह लग सकता है जिसमें अंकों की संख्या q, अर्थात् है। टी = 1।
   हालांकि, इस तरह के वक्रों को विसंगति कहा जाता है , और विसंगत अण्डाकार वक्रों के असतत लघुगणक को हल करना सुपरसिंगुलर और एकवचन घटता की तुलना में और भी सरल समस्या है।

संक्षेप में कहना

पूर्वगामी के आधार पर, हम अण्डाकार क्रिप्टोग्राफी के मुख्य फायदे और नुकसान लिखते हैं:
तो, मुख्य लाभ:

1. "शास्त्रीय" असममित क्रिप्टोग्राफी की तुलना में बहुत छोटी कुंजी लंबाई।
2. अण्डाकार एल्गोरिदम की गति शास्त्रीय लोगों की तुलना में बहुत अधिक है। यह क्षेत्र के आकार और कंप्यूटर के करीब एक द्विआधारी अंतिम क्षेत्र संरचना के उपयोग द्वारा समझाया गया है।
3. छोटी कुंजी लंबाई और उच्च गति के कारण, दीर्घवृत्तीय वक्रों पर असममित क्रिप्टोग्राफी एल्गोरिदम का उपयोग सीमित कंप्यूटिंग संसाधनों वाले स्मार्ट कार्ड और अन्य उपकरणों में किया जा सकता है।

अण्डाकार क्रिप्टोग्राफी के मुख्य नुकसान:

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

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

साहित्य का इस्तेमाल किया

1. डॉन जॉनसन, अल्फ्रेड मेनेजेस, स्कॉट वनस्टोन - द एलिप्टिक कर्व डिजिटल सिग्नेचर एल्गोरिथम।
2. ए। बोल्तोव, एस। गशकोव, ए। फ्रोलोव, ए। च्सोवस्किख - दीर्घवृत्तीय क्रिप्टोग्राफी का एक प्रारंभिक परिचय।
3. लॉरेंस वाशिंगटन - अण्डाकार वक्र, संख्या सिद्धांत और क्रिप्टोग्राफी।