RSA problem
क्रिप्टोग्राफी में, आर. एस. ए. समस्या केवल सार्वजनिक कुंजी दिए जाने पर आर. एस. ए. निजी-कुंजी संचालन करने के कार्य को संक्षेप में प्रस्तुत करती है। आर. एस. ए. एल्गोरिथ्म एक प्रतिपादक के लिए एक संदेश उठाता है, एक समग्र संख्या एन को मॉड्यूलो करता है जिसके कारक ज्ञात नहीं हैं। इस प्रकार, कार्य को बड़े आर. एस. ए. कुंजी आकारों (1024 बिट से अधिक) के लिए, इस समस्या को हल करने के लिए कोई कुशल विधि ज्ञात नहीं है; यदि एक कुशल विधि कभी विकसित की जाती है, तो यह आर. एस. ए.-आधारित क्रिप्टोसिस्टम की वर्तमान या अंतिम सुरक्षा को खतरे में डाल देगा-सार्वजनिक-कुंजी एन्क्रिप्शन और डिजिटल हस्ताक्षर दोनों के लिए। अधिक विशेष रूप से, आरएसए समस्या एक आरएसए सार्वजनिक कुंजी (एन, ई) और एक सिफरटेक्स्ट सी ष्ण पी ई (मॉड एन) को देखते हुए पी की कुशलता से गणना करना है। आर. एस. ए. सार्वजनिक कुंजी की संरचना के लिए आवश्यक है कि एन एक बड़ा अर्ध-अभाज्य (यानी, दो बड़ी अभाज्य संख्याओं का एक उत्पाद) हो, कि 2 <ई <एन, कि ई कोप्राइम से φ (एन) हो, और कि 0 ≤ सी <एन. सी. को उस सीमा के भीतर यादृच्छिक रूप से चुना जाता है; पूरी सटीकता के साथ समस्या को निर्दिष्ट करने के लिए, किसी को यह भी निर्दिष्ट करना होगा कि एन और ई कैसे उत्पन्न होते हैं, जो उपयोग में आर. एस. ए. यादृच्छिक कुंजीपटल पीढ़ी के सटीक साधनों पर निर्भर करेगा। आर. एस. ए. समस्या को हल करने के लिए ज्ञात सबसे कुशल विधि पहले मापांक एन को फ़ैक्टरिंग करना है, एक कार्य जिसे अव्यावहारिक माना जाता है यदि एन पर्याप्त रूप से बड़ा है (पूर्णांक फ़ैक्टरीकरण देखें)। आर. एस. ए. कुंजी सेटअप दिनचर्या पहले से ही सार्वजनिक प्रतिपादक ई को, इस प्रमुख गुणनखंडन के साथ, निजी गुणनखंड डी में बदल देती है, और इसलिए ठीक वही एल्गोरिथ्म किसी को भी अनुमति देता है जो निजी कुंजी प्राप्त करने के लिए एन को कारक बनाता है। फिर किसी भी सी को निजी कुंजी से डिक्रिप्ट किया जा सकता है। जिस तरह इस बात का कोई प्रमाण नहीं है कि पूर्णांक गुणनखंडन कम्प्यूटेशनल रूप से कठिन है, उसी तरह इस बात का भी कोई प्रमाण नहीं है कि आर. एस. ए. समस्या समान रूप से कठिन है। उपरोक्त विधि से, आर. एस. ए. समस्या कम से कम फैक्टरिंग जितनी आसान है, लेकिन यह अच्छी तरह से आसान हो सकती है। वास्तव में, इस निष्कर्ष की ओर इशारा करने वाले मजबूत प्रमाण हैंः कि आर. एस. ए. विधि को तोड़ने की एक विधि को आवश्यक रूप से बड़े अर्ध-अभाज्य को फैक्टरिंग करने के लिए एक विधि में परिवर्तित नहीं किया जा सकता है। फैक्टरिंग दृष्टिकोण के सरासर ओवरकिल द्वारा इसे देखना शायद सबसे आसान हैः आर. एस. ए. समस्या हमें एक मनमाने सिफरटेक्स्ट को डिक्रिप्ट करने के लिए कहती है, जबकि फैक्टरिंग विधि निजी कुंजी को प्रकट करती हैः इस प्रकार सभी मनमाने सिफरटेक्स्ट को डिक्रिप्ट करना, और यह मनमाने ढंग से आर. एस. ए. निजी-कुंजी एन्क्रिप्शन करने की भी अनुमति देता है। इन पंक्तियों के साथ, डिक्रिप्शन घातांक डी वास्तव में गणनात्मक रूप से फैक्टरिंग एन के बराबर है, भले ही आरएसए समस्या डी के लिए नहीं पूछती है। आरएसए समस्या के अलावा, आरएसए में एक विशेष गणितीय संरचना भी है जिसका संभावित रूप से आरएसए समस्या को सीधे हल किए बिना उपयोग किया जा सकता है। आर. एस. ए. समस्या की पूरी ताकत हासिल करने के लिए, आर. एस. ए. में ऐसी संरचनात्मक समस्याओं से बचाने के लिए, एक आर. एस. ए.-आधारित क्रिप्टोसिस्टम को ओ. ए. ई. पी. जैसी पैडिंग योजना का भी उपयोग करना चाहिए। मजबूत आर. एस. ए. धारणा आर. एस. ए. फैक्टरिंग चैलेंज राबिन क्रिप्टोसिस्टम को भी देखें, जिसकी फैक्टरिंग के लिए समतुल्यता ज्ञात है संदर्भ आगे पढ़ना आर. एस. ए. को तोड़ना फैक्टरिंग, डी. ब्राउन, 2005 जितना कठिन हो सकता है। इस अप्रकाशित प्रीप्रिंट का तात्पर्य है कि एक सीधी रेखा कार्यक्रम का उपयोग करके आर. एस. ए. समस्या को हल करना उतना ही कठिन है जितना कि फैक्टरिंग, बशर्ते कि ई में एक छोटा कारक हो। आर. एस. ए. को सामान्य रूप से तोड़ना फैक्टरिंग, डी. अग्रवाल और यू. मौरर, 2008 के बराबर है। यह यूरोक्रिप्ट 2009 पेपर (लिंक एक प्रीप्रिंट संस्करण के लिए है) साबित करता है कि एक सामान्य रिंग एल्गोरिथ्म का उपयोग करके आरएसए समस्या को हल करना फैक्टरिंग जितना ही कठिन है। जब ई-थ रूट्स फैक्टरिंग की तुलना में आसान हो जाते हैं, एंटोनी जॉक्स, डेविड नक्काचे और इमैनुएल थॉम, 2007। यह एशिया क्रिप्ट 2007 पेपर (लिंक एक प्रीप्रिंट संस्करण के लिए है) साबित करता है कि आर. एस. ए. समस्या के कुछ अन्य विशेष मामलों के लिए एक ओरेकल का उपयोग करके आर. एस. ए. समस्या को हल करना फैक्टरिंग की तुलना में आसान है। कम्प्यूटेशनल कठोरता धारणाएँ सार्वजनिक-कुंजी क्रिप्टोग्राफी