एलगमाल एन्क्रिप्शन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Public-key cryptosystem}} | {{Short description|Public-key cryptosystem}} | ||
{{Redirect|एलगमाल| | {{Redirect|एलगमाल|सिग्नेचर एल्गोरिथ्म|एलगमाल सिग्नेचर योजना}} | ||
[[क्रिप्टोग्राफी]] में, एलगैमल एन्क्रिप्शन सिस्टम [[सार्वजनिक-कुंजी क्रिप्टोग्राफी]] के लिए एक [[असममित कुंजी एन्क्रिप्शन एल्गोरिदम]] है जो डिफी-हेलमैन | [[क्रिप्टोग्राफी]] में, एलगैमल एन्क्रिप्शन सिस्टम [[सार्वजनिक-कुंजी क्रिप्टोग्राफी|पब्लिक-की क्रिप्टोग्राफी]] के लिए एक [[असममित कुंजी एन्क्रिप्शन एल्गोरिदम|असिमेट्रिक की एन्क्रिप्शन एल्गोरिदम]] है जो डिफी-हेलमैन की एक्सचेंज पर आधारित है। इसका वर्णन 1985 में [[ताहेर एल्गामल]] द्वारा किया गया था।<ref>{{cite journal |author=Taher ElGamal |title=एक सार्वजनिक-कुंजी क्रिप्टोसिस्टम और असतत लघुगणक पर आधारित एक हस्ताक्षर योजना|journal=IEEE Transactions on Information Theory |volume=31 |issue=4 |year=1985 |pages=469–472 |doi=10.1109/TIT.1985.1057074 |url=https://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf|citeseerx=10.1.1.476.4791 |s2cid=2973271 }} (conference version appeared in [[CRYPTO]]'84, pp. 10–18)</ref>एलगमाल एन्क्रिप्शन का उपयोग मुफ़्त [[जीएनयू गोपनीयता गार्ड]] सॉफ़्टवेयर, [[काफ़ी अच्छी गोपनीयता]] के हाल के संस्करणों और अन्य [[क्रिप्टो]]सिस्टम में किया जाता है। [[ डिजिटल हस्ताक्षर एल्गोरिदम ]] (डीएसए) [[एलगमाल हस्ताक्षर योजना]] का एक प्रकार है, जिसे एल्गैमल एन्क्रिप्शन के साथ भ्रमित नहीं किया जाना चाहिए। | ||
एल्गैमल एन्क्रिप्शन को किसी भी [[चक्रीय समूह]] | एल्गैमल एन्क्रिप्शन को किसी भी [[चक्रीय समूह]] <math>G</math> पर परिभाषित किया जा सकता है , जैसे पूर्णांकों मॉड्यूलो n पूर्णांकों का गुणक समूह । इसकी सुरक्षा [[असतत लघुगणक]] की गणना से संबंधित <math>G</math> में एक निश्चित समस्या की कठिनाई पर निर्भर करती है । | ||
== एल्गोरिथ्म == | == एल्गोरिथ्म == | ||
एल्गोरिदम को एक साझा | एल्गोरिदम को पहली बार एक साझा गुप्त <math>s</math> स्थापित करने के लिए डिफी-हेलमैन की एक्सचेंज करने के रूप में वर्णित किया जा सकता है , फिर संदेश को एन्क्रिप्ट करने के लिए इसे एक बार पैड के रूप में उपयोग किया जा सकता है। एल्गैमल एन्क्रिप्शन तीन चरणों में किया जाता है: की पीढ़ी, एन्क्रिप्शन और डिक्रिप्शन। पहला विशुद्ध रूप से की विनिमय है, जबकि बाद वाले दो की विनिमय गणनाओं को संदेश गणनाओं के साथ मिलाते हैं। | ||
=== | === की जनरेशन === | ||
पहली पार्टी, ऐलिस, एक | पहली पार्टी, ऐलिस, एक की- जोड़ी इस प्रकार उत्पन्न करती है: | ||
* | * जनरेटर <math>g</math> के साथ क्रम <math>q\,</math> के चक्रीय समूह <math>G\,</math> का एक कुशल विवरण तैयार करें। मान लीजिए <math>e</math>, <math>G</math> के पहचान तत्व को दर्शाता है। | ||
*: प्रत्येक नई | *: प्रत्येक नई की के लिए नए सिरे से एक समूह और जनरेटर के साथ आना आवश्यक नहीं है। वास्तव में, कोई यह उम्मीद कर सकता है कि एलगैमल के विशिष्ट कार्यान्वयन को किसी विशिष्ट समूह, या किसी विशिष्ट सुइट के समूह का उपयोग करने के लिए हार्डकोड किया जाएगा। समूह का चयन मुख्यतः इस बात पर निर्भर करता है कि आप कितनी बड़ी कुंजियों का उपयोग करना चाहते हैं। | ||
* एक पूर्णांक चुनें <math>x</math> बेतरतीब ढंग से से <math>\{1, \ldots, q-1\}</math>. | * एक पूर्णांक चुनें <math>x</math> बेतरतीब ढंग से से <math>\{1, \ldots, q-1\}</math>. | ||
*गणना करें <math>h := g^x</math>. | *गणना करें <math>h := g^x</math>. | ||
* [[सार्वजनिक कुंजी]] में मान | * [[सार्वजनिक कुंजी|पब्लिक की]] में मान <math>(G,q,g,h)</math> सम्मिलित होते हैं। ऐलिस इस पब्लिक की को प्रकाशित करती है और बनाए रखती है <math>x</math> उसकी निजी की के रूप में, जिसे गुप्त रखा जाना चाहिए। | ||
=== एन्क्रिप्शन === | === एन्क्रिप्शन === | ||
एक दूसरा पक्ष, बॉब, एक संदेश को एन्क्रिप्ट करता है <math>M</math> ऐलिस को उसकी | एक दूसरा पक्ष, बॉब, एक संदेश को एन्क्रिप्ट करता है <math>M</math> ऐलिस को उसकी पब्लिक की के अंतर्गत <math>(G,q,g,h)</math> निम्नलिखित अनुसार: | ||
* संदेश को मैप करें <math>M</math> एक तत्व के लिए <math>m</math> का <math>G</math> एक प्रतिवर्ती मैपिंग फ़ंक्शन का उपयोग करना। | * संदेश को मैप करें <math>M</math> एक तत्व के लिए <math>m</math> का <math>G</math> एक प्रतिवर्ती मैपिंग फ़ंक्शन का उपयोग करना। | ||
| Line 28: | Line 28: | ||
* बॉब सिफरटेक्स्ट भेजता है <math>(c_1,c_2)</math> ऐलिस को. | * बॉब सिफरटेक्स्ट भेजता है <math>(c_1,c_2)</math> ऐलिस को. | ||
ध्यान दें कि यदि कोई दोनों सिफरटेक्स्ट को जानता है <math>(c_1,c_2)</math> और सादा पाठ <math>m</math>, कोई भी साझा रहस्य आसानी से पा सकता है <math>s</math>, तब से <math>c_2 \cdot m^{-1} = s</math>. इसलिए, एक नया <math>y</math> और इसलिए एक नया <math>s</math> सुरक्षा में सुधार के लिए प्रत्येक संदेश के लिए जेनरेट किया जाता है। इस कारण से, <math>y</math> इसे [[क्षणिक कुंजी]] भी कहा जाता है. | ध्यान दें कि यदि कोई दोनों सिफरटेक्स्ट को जानता है <math>(c_1,c_2)</math> और सादा पाठ <math>m</math>, कोई भी साझा रहस्य आसानी से पा सकता है <math>s</math>, तब से <math>c_2 \cdot m^{-1} = s</math>. इसलिए, एक नया <math>y</math> और इसलिए एक नया <math>s</math> सुरक्षा में सुधार के लिए प्रत्येक संदेश के लिए जेनरेट किया जाता है। इस कारण से, <math>y</math> इसे [[क्षणिक कुंजी|क्षणिक की]] भी कहा जाता है. | ||
=== डिक्रिप्शन === | === डिक्रिप्शन === | ||
ऐलिस एक सिफरटेक्स्ट को डिक्रिप्ट करता है <math>(c_1, c_2)</math> उसकी निजी | ऐलिस एक सिफरटेक्स्ट को डिक्रिप्ट करता है <math>(c_1, c_2)</math> उसकी निजी की के साथ <math>x</math> निम्नलिखित नुसार: | ||
*गणना करें <math>s := c_1^x</math>. तब से <math>c_1 = g^y</math>, <math>c_1^x = g^{xy} = h^y</math>, और इस प्रकार यह वही साझा रहस्य है जिसका उपयोग बॉब ने एन्क्रिप्शन में किया था। | *गणना करें <math>s := c_1^x</math>. तब से <math>c_1 = g^y</math>, <math>c_1^x = g^{xy} = h^y</math>, और इस प्रकार यह वही साझा रहस्य है जिसका उपयोग बॉब ने एन्क्रिप्शन में किया था। | ||
*गणना करें <math>s^{-1}</math>, का उलटा <math>s</math> समूह में <math>G</math>. इसकी गणना कई तरीकों में से एक में की जा सकती है। अगर <math>G</math> पूर्णांक मॉड्यूलो के गुणक समूह का एक उपसमूह है<math>n</math>, कहाँ <math>n</math> प्राइम है, [[मॉड्यूलर गुणक व्युत्क्रम]] की गणना [[विस्तारित यूक्लिडियन एल्गोरिथ्म]] का उपयोग करके की जा सकती है। एक विकल्प गणना करना है <math>s^{-1}</math> जैसा <math>c_1^{q-x}</math>. यह इसका उलटा है <math>s</math> लैग्रेंज प्रमेय (समूह सिद्धांत) के कारण|लैग्रेंज प्रमेय, चूंकि <math>s \cdot c_1^{q-x} = g^{xy} \cdot g^{(q-x)y} = (g^{q})^y = e^y = e</math>. | *गणना करें <math>s^{-1}</math>, का उलटा <math>s</math> समूह में <math>G</math>. इसकी गणना कई तरीकों में से एक में की जा सकती है। अगर <math>G</math> पूर्णांक मॉड्यूलो के गुणक समूह का एक उपसमूह है<math>n</math>, कहाँ <math>n</math> प्राइम है, [[मॉड्यूलर गुणक व्युत्क्रम]] की गणना [[विस्तारित यूक्लिडियन एल्गोरिथ्म]] का उपयोग करके की जा सकती है। एक विकल्प गणना करना है <math>s^{-1}</math> जैसा <math>c_1^{q-x}</math>. यह इसका उलटा है <math>s</math> लैग्रेंज प्रमेय (समूह सिद्धांत) के कारण|लैग्रेंज प्रमेय, चूंकि <math>s \cdot c_1^{q-x} = g^{xy} \cdot g^{(q-x)y} = (g^{q})^y = e^y = e</math>. | ||
| Line 39: | Line 39: | ||
=== व्यावहारिक उपयोग === | === व्यावहारिक उपयोग === | ||
अधिकांश | अधिकांश पब्लिक की प्रणालियों की तरह, एलगैमल क्रिप्टोसिस्टम का उपयोग प्रायः [[हाइब्रिड क्रिप्टोसिस्टम]] के हिस्से के रूप में किया जाता है, जहां संदेश स्वयं एक सममित क्रिप्टोसिस्टम का उपयोग करके एन्क्रिप्ट किया जाता है, और एलगैमल का उपयोग केवल सममित की को एन्क्रिप्ट करने के लिए किया जाता है। ऐसा इसलिए है क्योंकि सुरक्षा के समान स्तर के लिए एलगैमल जैसे असिमेट्रिक क्रिप्टोसिस्टम प्रायः सममित क्रिप्टो सिस्टम की तुलना में धीमे होते हैं, इसलिए संदेश को एन्क्रिप्ट करना तेज़ होता है, जो एक सममित सिफर के साथ मनमाने ढंग से बड़ा हो सकता है, और फिर एल्गैमल का उपयोग केवल सममित की को एन्क्रिप्ट करने के लिए किया जाता है, जो प्रायः संदेश के आकार की तुलना में काफी छोटा होता है। | ||
== सुरक्षा == | == सुरक्षा == | ||
Revision as of 17:20, 7 August 2023
क्रिप्टोग्राफी में, एलगैमल एन्क्रिप्शन सिस्टम पब्लिक-की क्रिप्टोग्राफी के लिए एक असिमेट्रिक की एन्क्रिप्शन एल्गोरिदम है जो डिफी-हेलमैन की एक्सचेंज पर आधारित है। इसका वर्णन 1985 में ताहेर एल्गामल द्वारा किया गया था।[1]एलगमाल एन्क्रिप्शन का उपयोग मुफ़्त जीएनयू गोपनीयता गार्ड सॉफ़्टवेयर, काफ़ी अच्छी गोपनीयता के हाल के संस्करणों और अन्य क्रिप्टोसिस्टम में किया जाता है। डिजिटल हस्ताक्षर एल्गोरिदम (डीएसए) एलगमाल हस्ताक्षर योजना का एक प्रकार है, जिसे एल्गैमल एन्क्रिप्शन के साथ भ्रमित नहीं किया जाना चाहिए।
एल्गैमल एन्क्रिप्शन को किसी भी चक्रीय समूह पर परिभाषित किया जा सकता है , जैसे पूर्णांकों मॉड्यूलो n पूर्णांकों का गुणक समूह । इसकी सुरक्षा असतत लघुगणक की गणना से संबंधित में एक निश्चित समस्या की कठिनाई पर निर्भर करती है ।
एल्गोरिथ्म
एल्गोरिदम को पहली बार एक साझा गुप्त स्थापित करने के लिए डिफी-हेलमैन की एक्सचेंज करने के रूप में वर्णित किया जा सकता है , फिर संदेश को एन्क्रिप्ट करने के लिए इसे एक बार पैड के रूप में उपयोग किया जा सकता है। एल्गैमल एन्क्रिप्शन तीन चरणों में किया जाता है: की पीढ़ी, एन्क्रिप्शन और डिक्रिप्शन। पहला विशुद्ध रूप से की विनिमय है, जबकि बाद वाले दो की विनिमय गणनाओं को संदेश गणनाओं के साथ मिलाते हैं।
की जनरेशन
पहली पार्टी, ऐलिस, एक की- जोड़ी इस प्रकार उत्पन्न करती है:
- जनरेटर के साथ क्रम के चक्रीय समूह का एक कुशल विवरण तैयार करें। मान लीजिए , के पहचान तत्व को दर्शाता है।
- प्रत्येक नई की के लिए नए सिरे से एक समूह और जनरेटर के साथ आना आवश्यक नहीं है। वास्तव में, कोई यह उम्मीद कर सकता है कि एलगैमल के विशिष्ट कार्यान्वयन को किसी विशिष्ट समूह, या किसी विशिष्ट सुइट के समूह का उपयोग करने के लिए हार्डकोड किया जाएगा। समूह का चयन मुख्यतः इस बात पर निर्भर करता है कि आप कितनी बड़ी कुंजियों का उपयोग करना चाहते हैं।
- एक पूर्णांक चुनें बेतरतीब ढंग से से .
- गणना करें .
- पब्लिक की में मान सम्मिलित होते हैं। ऐलिस इस पब्लिक की को प्रकाशित करती है और बनाए रखती है उसकी निजी की के रूप में, जिसे गुप्त रखा जाना चाहिए।
एन्क्रिप्शन
एक दूसरा पक्ष, बॉब, एक संदेश को एन्क्रिप्ट करता है ऐलिस को उसकी पब्लिक की के अंतर्गत निम्नलिखित अनुसार:
- संदेश को मैप करें एक तत्व के लिए का एक प्रतिवर्ती मैपिंग फ़ंक्शन का उपयोग करना।
- एक पूर्णांक चुनें बेतरतीब ढंग से से .
- गणना करें . इसे साझा रहस्य कहा जाता है.
- गणना करें .
- गणना करें .
- बॉब सिफरटेक्स्ट भेजता है ऐलिस को.
ध्यान दें कि यदि कोई दोनों सिफरटेक्स्ट को जानता है और सादा पाठ , कोई भी साझा रहस्य आसानी से पा सकता है , तब से . इसलिए, एक नया और इसलिए एक नया सुरक्षा में सुधार के लिए प्रत्येक संदेश के लिए जेनरेट किया जाता है। इस कारण से, इसे क्षणिक की भी कहा जाता है.
डिक्रिप्शन
ऐलिस एक सिफरटेक्स्ट को डिक्रिप्ट करता है उसकी निजी की के साथ निम्नलिखित नुसार:
- गणना करें . तब से , , और इस प्रकार यह वही साझा रहस्य है जिसका उपयोग बॉब ने एन्क्रिप्शन में किया था।
- गणना करें , का उलटा समूह में . इसकी गणना कई तरीकों में से एक में की जा सकती है। अगर पूर्णांक मॉड्यूलो के गुणक समूह का एक उपसमूह है, कहाँ प्राइम है, मॉड्यूलर गुणक व्युत्क्रम की गणना विस्तारित यूक्लिडियन एल्गोरिथ्म का उपयोग करके की जा सकती है। एक विकल्प गणना करना है जैसा . यह इसका उलटा है लैग्रेंज प्रमेय (समूह सिद्धांत) के कारण|लैग्रेंज प्रमेय, चूंकि .
- गणना करें . यह गणना मूल संदेश उत्पन्न करती है , क्योंकि ; इस तरह .
- नक्शा सादे पाठ संदेश पर वापस जाएँ .
व्यावहारिक उपयोग
अधिकांश पब्लिक की प्रणालियों की तरह, एलगैमल क्रिप्टोसिस्टम का उपयोग प्रायः हाइब्रिड क्रिप्टोसिस्टम के हिस्से के रूप में किया जाता है, जहां संदेश स्वयं एक सममित क्रिप्टोसिस्टम का उपयोग करके एन्क्रिप्ट किया जाता है, और एलगैमल का उपयोग केवल सममित की को एन्क्रिप्ट करने के लिए किया जाता है। ऐसा इसलिए है क्योंकि सुरक्षा के समान स्तर के लिए एलगैमल जैसे असिमेट्रिक क्रिप्टोसिस्टम प्रायः सममित क्रिप्टो सिस्टम की तुलना में धीमे होते हैं, इसलिए संदेश को एन्क्रिप्ट करना तेज़ होता है, जो एक सममित सिफर के साथ मनमाने ढंग से बड़ा हो सकता है, और फिर एल्गैमल का उपयोग केवल सममित की को एन्क्रिप्ट करने के लिए किया जाता है, जो प्रायः संदेश के आकार की तुलना में काफी छोटा होता है।
सुरक्षा
एल्गैमल योजना की सुरक्षा अंतर्निहित समूह की संपत्तियों पर निर्भर करती है साथ ही संदेशों पर उपयोग की जाने वाली कोई भी पैडिंग योजना। यदि कम्प्यूटेशनल डिफी-हेलमैन धारणा (सीडीएच) अंतर्निहित चक्रीय समूह में है , तो एन्क्रिप्शन फ़ंक्शन एक तरफ़ा कार्य वन-वे है।[2]
यदि निर्णयात्मक डिफी-हेलमैन धारणा (डीडीएच) कायम रहती है , तब, एलगमाल सिमेंटिक सुरक्षा हासिल करता है।[2][3] सिमेंटिक सुरक्षा अकेले कम्प्यूटेशनल डिफी-हेलमैन धारणा से निहित नहीं है। उन समूहों की चर्चा के लिए डिसीजनल डिफी-हेलमैन धारणा देखें जहां धारणा को मान्य माना जाता है।
एल्गैमल एन्क्रिप्शन बिना शर्त लचीलापन (क्रिप्टोग्राफी) है, और इसलिए चुने गए सिफरटेक्स्ट हमले के तहत सुरक्षित नहीं है। उदाहरण के लिए, एक एन्क्रिप्शन दिया गया कुछ (संभवतः अज्ञात) संदेश का , कोई आसानी से एक वैध एन्क्रिप्शन का निर्माण कर सकता है संदेश का .
चयनित-सिफरटेक्स्ट सुरक्षा प्राप्त करने के लिए, योजना को और संशोधित किया जाना चाहिए, या एक उपयुक्त पैडिंग योजना का उपयोग किया जाना चाहिए। संशोधन के आधार पर, डीडीएच धारणा आवश्यक हो भी सकती है और नहीं भी।
एलगैमल से संबंधित अन्य योजनाएं जो चुने हुए सिफरटेक्स्ट हमलों के खिलाफ सुरक्षा प्राप्त करती हैं, भी प्रस्तावित की गई हैं। डीडीएच को मानते हुए क्रैमर-शूप क्रिप्टोसिस्टम चुने गए सिफरटेक्स्ट हमले के तहत सुरक्षित है . इसका प्रमाण यादृच्छिक ओरेकल मॉडल का उपयोग नहीं करता है। एक अन्य प्रस्तावित योजना एकीकृत एन्क्रिप्शन योजना है,[4] जिसके प्रमाण के लिए ऐसी धारणा की आवश्यकता होती है जो डीडीएच धारणा से अधिक मजबूत हो।
दक्षता
एलगमाल एन्क्रिप्शन संभाव्य एन्क्रिप्शन है, जिसका अर्थ है कि एक एकल सादे पाठ को कई संभावित सिफरटेक्स्ट में एन्क्रिप्ट किया जा सकता है, जिसके परिणामस्वरूप एक सामान्यएलगमाल एन्क्रिप्शन प्लेनटेक्स्ट से सिफरटेक्स्ट तक आकार में 1:2 विस्तार उत्पन्न करता है।
एलगमाल के अंतर्गत एन्क्रिप्शन के लिए दो घातांक की आवश्यकता होती है; यदपि, ये घातांक संदेश से स्वतंत्र हैं और जरूरत पड़ने पर समय से पहले गणना की जा सकती है। डिक्रिप्शन के लिए एक घातांक और समूह व्युत्क्रम की एक गणना की आवश्यकता होती है, जिसे,यदपि, आसानी से केवल एक घातांक में जोड़ा जा सकता है।
यह भी देखें
- ताहेर एल्गामल, इस और अन्य क्रिप्टोसिस्टम के डिजाइनर
- एलगमाल हस्ताक्षर योजना
- होमोमोर्फिक एन्क्रिप्शन
अग्रिम पठन
- ए जे मेनेजेस; पी. सी. वैन ओर्सकोट; एस. ए. वैनस्टोन. "अध्याय 8.4 एलगैमल सार्वजनिक-कुंजी एन्क्रिप्शन" (PDF). एप्लाइड क्रिप्टोग्राफी की हैंडबुक. सीआरसी प्रेस.
- डैन बोनेह (1998). निर्णय डिफी-हेलमैन समस्या. pp. 48–63. CiteSeerX 10.1.1.461.9971. doi:10.1007/BFb0054851. ISBN 978-3-540-64657-0.
{{cite book}}:|journal=ignored (help)
संदर्भ
- ↑ Taher ElGamal (1985). "एक सार्वजनिक-कुंजी क्रिप्टोसिस्टम और असतत लघुगणक पर आधारित एक हस्ताक्षर योजना" (PDF). IEEE Transactions on Information Theory. 31 (4): 469–472. CiteSeerX 10.1.1.476.4791. doi:10.1109/TIT.1985.1057074. S2CID 2973271. (conference version appeared in CRYPTO'84, pp. 10–18)
- ↑ 2.0 2.1 Mike Rosulek (2008-12-13). "Elgamal encryption scheme". University of Illinois at Urbana-Champaign. Archived from the original on 2016-07-22.
- ↑ Tsiounis, Yiannis; Yung, Moti (2006-05-24). "On the security of ElGamal based encryption". Public Key Cryptography 1998. Lecture Notes in Computer Science. 1431: 117–134. doi:10.1007/BFb0054019. ISBN 978-3-540-69105-1.
- ↑ Abdalla, Michel; Bellare, Mihir; Rogaway, Phillip (2001-01-01). "The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES". CT-RSA 2001: Topics in Cryptology. Lecture Notes in Computer Science. 2020: 143–158. doi:10.1007/3-540-45353-9_12. ISBN 978-3-540-41898-6.
