Coppersmith's attack
कॉपरस्मिथ का हमला कॉपरस्मिथ विधि पर आधारित सार्वजनिक-प्रमुख क्रिप्टोसिस्टम आरएसए पर क्रिप्टोग्राफिक हमलों के एक वर्ग का वर्णन करता है। आर. एस. ए. पर हमला करने के लिए कॉपरस्मिथ विधि के विशेष अनुप्रयोगों में ऐसे मामले शामिल हैं जब सार्वजनिक प्रतिपादक ई छोटा होता है या जब गुप्त कुंजी के प्रमुख कारक का आंशिक ज्ञान उपलब्ध होता है। आर. एस. ए. मूल बातें आर. एस. ए. प्रणाली में सार्वजनिक कुंजी पूर्णांकों का एक टुपल है, जहाँ एन दो अभाज्य संख्याओं पी और क्यू का गुणनफल है। गुप्त कुंजी एक पूर्णांक डी संतोषजनक द्वारा दी गई है; समान रूप से, गुप्त कुंजी द्वारा दी जा सकती है और यदि चीनी शेष प्रमेय का उपयोग डिक्रिप्शन की गति में सुधार के लिए किया जाता है, तो सीआरटी-आरएसए देखें। एक संदेश एम का एन्क्रिप्शन सिफरटेक्स्ट उत्पन्न करता है, जिसे कंप्यूटिंग का उपयोग करके डिक्रिप्ट किया जा सकता है। कम सार्वजनिक घातांक हमला कूटलेखन या हस्ताक्षर सत्यापन समय को कम करने के लिए, एक छोटे से सार्वजनिक घातांक () का उपयोग करना उपयोगी है। व्यवहार में, 3,17 और 65537 के लिए सामान्य विकल्प हैं। ई के लिए ये मान फर्मेट अभाज्य संख्याएँ हैं, जिन्हें कभी-कभी क्रमशः और के रूप में संदर्भित किया जाता है। उन्हें इसलिए चुना जाता है क्योंकि वे मॉड्यूलर एक्सपोनेंटिएशन ऑपरेशन को तेज करते हैं। इसके अलावा, इस तरह का चयन करने के बाद, कुंजी पीढ़ी के चरण 1 में अभाज्य संख्याओं को उत्पन्न और परीक्षण करते समय यह परीक्षण करना आसान है। इस परीक्षण के या असफल होने वाले मूल्यों को वहाँ और फिर अस्वीकार किया जा सकता है। (इससे भी बेहतरः यदि ई अभाज्य है और 2 से अधिक है, तो परीक्षण अधिक महंगे परीक्षण की जगह ले सकता है।) यदि सार्वजनिक प्रतिपादक छोटा है और सादा पाठ बहुत छोटा है, तो आर. एस. ए. कार्य को उलटना आसान हो सकता है, जिससे कुछ हमले संभव हो जाते हैं। पैडिंग योजनाएं यह सुनिश्चित करती हैं कि संदेशों की पूरी लंबाई हो, लेकिन इसके अतिरिक्त सार्वजनिक प्रतिपादक का चयन करने की सिफारिश की जाती है। जब इस मान का उपयोग किया जाता है, तो हस्ताक्षर सत्यापन के लिए 17 गुणन की आवश्यकता होती है, जबकि लगभग 25 के विपरीत जब समान आकार के यादृच्छिक का उपयोग किया जाता है। निम्न निजी प्रतिपादक के विपरीत (वीनर का हमला देखें), जब एक छोटे का उपयोग किया जाता है तो जो हमले लागू होते हैं, वे कुल विराम से बहुत दूर होते हैं, जो गुप्त कुंजी डी को पुनर्प्राप्त करेंगे। निम्न सार्वजनिक प्रतिपादक आरएसए पर सबसे शक्तिशाली हमले निम्नलिखित प्रमेय पर आधारित होते हैं, जो डॉन कॉपरस्मिथ के कारण होता है। कॉपरस्मिथ विधि प्रमेय 1 (कॉपरस्मिथ) मान लीजिए कि एन एक पूर्णांक है और पूर्णांकों पर डिग्री का एक मोनिक बहुपद है। के लिए सेट करें। फिर, दिए गए, हमलावर (ईव) कुशलता से सभी पूर्णांकों को संतोषजनक पा सकते हैं। चलने का समय उस समय पर हावी होता है जब एल. एल. एल. एल्गोरिदम को आयाम ओ के जाली पर चलाने में लगता है। यह प्रमेय एक एल्गोरिथ्म के अस्तित्व को बताता है जो मॉड्यूलो के उन सभी मूलों को कुशलता से ढूंढ सकता है जो उससे छोटे हैं। जैसे-जैसे छोटा होता जाता है, एल्गोरिथ्म का रनटाइम कम होता जाता है। इस प्रमेय की ताकत बहुपदों के सभी छोटे मूलों को एक समग्र रूप में खोजने की क्षमता है। उस्ताद का प्रसारण हमला उस्ताद के हमले का सबसे सरल रूप समझ को आसान बनाने के लिए प्रस्तुत किया गया है। सामान्य मामला कॉपरस्मिथ विधि का उपयोग करता है। मान लीजिए कि एक प्रेषक एक ही संदेश को एन्क्रिप्टेड रूप में कई लोगों को भेजता है, जिनमें से प्रत्येक एक ही छोटे सार्वजनिक प्रतिपादक, मान लीजिए, और अलग-अलग मॉडुली का उपयोग करता है। एक सरल तर्क से पता चलता है कि जैसे ही सिफरटेक्स्ट का पता चलता है, संदेश अब सुरक्षित नहीं हैः मान लीजिए कि ईव इंटरसेप्ट करती है, और, कहाँ। हम सभी के लिए मान सकते हैं (अन्यथा, गणना करके संख्याओं में से एक के कारक की गणना करना संभव है।) चीनी शेष प्रमेय के अनुसार, वह इस तरह से गणना कर सकती है। फिर; हालाँकि, सभी के लिए, हमारे पास है। इस प्रकार पूर्णांक पर पकड़ रखता है, और ईव प्राप्त करने के लिए घन मूल की गणना कर सकती है। के बड़े मूल्यों के लिए, अधिक सिफरटेक्स्ट की आवश्यकता होती है, विशेष रूप से, सिफरटेक्स्ट पर्याप्त हैं। सामान्यीकरण उस्ताद ने यह भी दिखाया कि एन्क्रिप्शन से पहले एक रैखिक पैडिंग लगाने से इस हमले से सुरक्षा नहीं मिलती है। मान लीजिए कि हमलावर को पता चलता है कि कुछ रैखिक कार्य के लिए, यानी, बॉब संदेश को कूटबद्ध करने से पहले उस पर एक पैड लगाता है ताकि प्राप्तकर्ताओं को थोड़ा अलग संदेश प्राप्त हो सकें। उदाहरण के लिए, यदि बिट लंबा है, तो बॉब एन्क्रिप्ट कर सकता है और इसे-th प्राप्तकर्ता को भेज सकता है। यदि लोगों का एक बड़ा पर्याप्त समूह शामिल है, तो हमलावर समान तरीकों से सभी सिफरटेक्स्ट से प्लेनटेक्स्ट को पुनर्प्राप्त कर सकता है। अधिक सामान्यता में, हेस्टाड ने साबित किया कि एकात्मक समीकरणों की एक प्रणाली, जैसे कि किसी भी निश्चित बहुपद को लागू करना, को हल किया जा सकता है यदि पर्याप्त रूप से कई समीकरण प्रदान किए जाएं। इस हमले से पता चलता है कि आर. एस. ए. कूटलेखन में यादृच्छिक पैडिंग का उपयोग किया जाना चाहिए। प्रमेय 2 (हेस्ताद) मान लीजिए कि ये अपेक्षाकृत अभाज्य पूर्णांक और समुच्चय हैं। मान लीजिए कि वे अधिकतम डिग्री के बहुपद हैं। मान लीजिए कि सभी के लिए एक अद्वितीय संतुष्टि मौजूद है। इसके अलावा, मान लीजिए। एक कुशल एल्गोरिथ्म है जो, सभी के लिए दिया गया है, गणना करता है। सबूत चूंकि ये अपेक्षाकृत अभाज्य हैं, इसलिए चीनी शेष प्रमेय का उपयोग सभी के लिए संतोषजनक गुणांक की गणना करने के लिए किया जा सकता है। सेटिंग, हम यह जानते हैं। चूँकि ये गैर-शून्य हैं, हमारे पास यह भी गैर-शून्य है। की डिग्री अधिक से अधिक है। कॉपरस्मिथ के प्रमेय के अनुसार, हम सभी पूर्णांक मूल की गणना कर सकते हैं जो संतुष्ट करते हैं और। हालाँकि, हम जानते हैं कि, कॉपरस्मिथ के प्रमेय द्वारा पाए गए मूल में से एक है। इस प्रमेय को प्रसारण आर. एस. ए. की समस्या पर निम्नलिखित तरीके से लागू किया जा सकता हैः मान लीजिए कि-th प्लेनटेक्स्ट को एक बहुपद के साथ पैडेड किया गया है, ताकि। तब यह सच है, और कॉपरस्मिथ की विधि का उपयोग किया जा सकता है। हमला एक बार सफल हो जाता है, संदेशों की संख्या कहाँ है। मूल परिणाम में पूर्ण कॉपरस्मिथ विधि के बजाय हेस्टैड के संस्करण का उपयोग किया गया। नतीजतन, इसे संदेशों की आवश्यकता थी, कहाँ। फ्रैंकलिन-रेइटर संबंधित-संदेश हमले फ्रैंकलिन और रेइटर ने आर. एस. ए. के खिलाफ हमले की पहचान की जब कई संबंधित संदेश एन्क्रिप्ट किए जाते हैंः यदि दो संदेश केवल दो संदेशों के बीच एक ज्ञात निश्चित अंतर से भिन्न होते हैं और एक ही आर. एस. ए. मापांक के तहत आर. एस. ए.-एन्क्रिप्ट किए जाते हैं, तो दोनों को पुनर्प्राप्त करना संभव है। हमले को मूल रूप से सार्वजनिक प्रतिपादक के साथ वर्णित किया गया था, लेकिन यह अधिक सामान्य रूप से काम करता है (बढ़ती लागत के साथ)। एलिस की सार्वजनिक कुंजी होने दें। मान लीजिए कि कुछ सार्वजनिक रूप से ज्ञात बहुपद के लिए दो अलग-अलग संदेश संतोषजनक हैं। एलिस को भेजने और भेजने के लिए, बॉब नादानी से संदेशों को एन्क्रिप्ट कर सकता है और परिणामी सिफरटेक्स्ट को प्रसारित कर सकता है। ईव निम्नलिखित प्रमेय का उपयोग करके आसानी से पुनर्प्राप्त कर सकती हैः प्रमेय 3 (फ्रैंकलिन-रेइटर) एक आर. एस. ए. सार्वजनिक कुंजी होने दें। कुछ रैखिक बहुपद के लिए संतुष्ट करें। फिर, दिए गए, हमलावर (ईव) समय में क्वाड्रैटिक में ठीक हो सकते हैं। सबूत चूंकि, हम जानते हैं कि यह बहुपद का मूल है। इसी तरह, का एक मूल है। अतः, रैखिक कारक दोनों बहुपदों को विभाजित करता है। इसलिए, हव्वा और के सबसे बड़े सामान्य भाजक की गणना कर सकती है, और यदि रैखिक हो जाता है, तो पाया जाता है। इसकी गणना यूक्लिडियन एल्गोरिदम का उपयोग करके द्विघात समय में की जा सकती है। हैस्टैड और फ्रैंकलिन-रेइटर के हमलों की तरह कॉपरस्मिथ का शॉर्ट-पैड हमला, यह हमला सार्वजनिक प्रतिपादक के साथ आरएसए की कमजोरी का फायदा उठाता है। कॉपरस्मिथ ने दिखाया कि यदि हेस्टाड द्वारा सुझाए गए यादृच्छिक पैडिंग का अनुचित तरीके से उपयोग किया जाता है, तो आरएसए एन्क्रिप्शन सुरक्षित नहीं है। मान लीजिए कि बॉब एलिस को एन्क्रिप्ट करने से पहले एक छोटी सी यादृच्छिक पैडिंग का उपयोग करके एक संदेश भेजता है। एक हमलावर, ईव, सिफरटेक्स्ट को रोकता है और इसे अपने गंतव्य तक पहुंचने से रोकता है। बॉब एलिस को फिर से भेजने का फैसला करता है क्योंकि एलिस ने उसके संदेश का जवाब नहीं दिया। वह यादृच्छिक रूप से फिर से पैड करता है और परिणामी सिफरटेक्स्ट को प्रसारित करता है। ईव के पास अब दो अलग-अलग यादृच्छिक पैड का उपयोग करके एक ही संदेश के दो एन्क्रिप्शन के अनुरूप दो सिफरटेक्स्ट हैं। भले ही ईव को पता नहीं है कि यादृच्छिक पैड का उपयोग किया जा रहा है, फिर भी वह निम्नलिखित प्रमेय का उपयोग करके संदेश को पुनर्प्राप्त कर सकती है, यदि यादृच्छिक पैडिंग बहुत छोटी है। प्रमेय 4 (कॉपरस्मिथ) को एक सार्वजनिक आर. एस. ए. कुंजी माना जाता है, जहाँ बिट लंबा होता है। सेट करें। अधिक से अधिक बिट्स पर एक लंबा संदेश होने दें। परिभाषित करें और कहाँ और कहाँ के साथ अलग-अलग पूर्णांक हैं। यदि हव्वा को एन्क्रिप्शन दिया जाता है (लेकिन नहीं दिया जाता है या), तो वह कुशलता से ठीक हो सकती है। प्रमाण परिभाषित करें और। हम जानते हैं कि कब, इन बहुपदों का एक सामान्य मूल होता है। दूसरे शब्दों में, यह परिणामी का मूल है। इसके अलावा,। इसलिए, यह मॉडुलो की एक छोटी जड़ है, और ईव इसे कॉपरस्मिथ विधि का उपयोग करके कुशलता से पा सकती है। एक बार पता चल जाने के बाद, फ्रैंकलिन-रेइटर हमले का उपयोग ठीक होने और इसके परिणामस्वरूप किया जा सकता है। आरओसीए हमला संदर्भ क्रिप्टोग्राफिक हमले सार्वजनिक-प्रमुख क्रिप्टोसिस्टम पर हमले भी देखें।