आरएसए और पूर्णांक गुणनखंडन

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

Definition

आरएसए एक सार्वजनिक-कुंजी क्रिप्टोसिसटम है जिसमें एक सार्वजनिक मापांक n दो गुप्त अभाज्य संख्याओं का गुणनफल होता है; एन्क्रिप्शन संदेश को एक सार्वजनिक घातांक मापांक n तक बढ़ाता है, और डिक्रिप्शन एक निजी घातांक का उपयोग करता है जिसे केवल n के गुणनखंडन से प्राप्त किया जा सकता है।

Scope

यह विषय आरएसए एल्गोरिथम को कवर करता है — कुंजी निर्माण, एन्क्रिप्शन, डिक्रिप्शन, और मॉड्यूलर घातांक के माध्यम से हस्ताक्षर करना — साथ ही पूर्णांक-गुणनखंडन समस्या जिस पर यह निर्भर करता है, इसे खतरे में डालने वाले गुणनखंडन एल्गोरिदम, और पैडिंग योजनाएं (OAEP, PSS) जो पाठ्यपुस्तक आरएसए को व्यवहार में सुरक्षित बनाती हैं। यह कुंजी-आकार की सिफारिशों और कार्यान्वयन हमलों जैसे समय और दोष हमलों को संबोधित करता है। इसमें असतत-लॉग-आधारित योजनाएं और अण्डाकार-वक्र क्रिप्टोग्राफी शामिल नहीं हैं, जिन्हें अलग से माना जाता है।

Core questions

• आरएसए सार्वजनिक और निजी घातांक मॉड्यूलर अंकगणित की संरचना से कैसे उत्पन्न होते हैं?
• आरएसए की सुरक्षा मापांक के गुणनखंडन की कठिनाई पर क्यों निर्भर करती है?
• बड़ी पूर्णांकों का गुणनखंडन कितनी तेजी से किया जा सकता है, और इसका कुंजी आकारों के लिए क्या अर्थ है?
• पाठ्यपुस्तक आरएसए असुरक्षित क्यों है, और OAEP और PSS जैसी पैडिंग योजनाएं इसे कैसे ठीक करती हैं?
• व्यवहार में आरएसए को कौन से कार्यान्वयन-स्तर के हमले (समय, दोष, कमजोर यादृच्छिकता) खतरे में डालते हैं?

Key concepts

• मॉड्यूलर घातांक
• सार्वजनिक और निजी घातांक
• यूलर का टोटिएंट और कारमाइकल फ़ंक्शन
• गुणनखंडन समस्या
• सामान्य संख्या क्षेत्र छलनी
• OAEP पैडिंग
• PSS हस्ताक्षर पैडिंग
• कुंजी आकार और सुरक्षा स्तर

Key theories

आरएसए ट्रैपडोर क्रमचय

आरएसए एक ट्रैपडोर वन-वे क्रमचय को परिभाषित करता है: सार्वजनिक घातांक मापांक n तक बढ़ाना आसान है, लेकिन इसे उलटने के लिए निजी घातांक की आवश्यकता होती है, जिसे केवल n के अभाज्य गुणनखंडन से गणना की जा सकती है — ट्रैपडोर।

गुणनखंडन धारणा और कुंजी आकार

आरएसए की व्यावहारिक सुरक्षा सर्वोत्तम गुणनखंडन एल्गोरिदम (वर्तमान में सामान्य संख्या क्षेत्र छलनी, मापांक लंबाई में उपघातीय) को ट्रैक करती है; उनका विरोध करना ही कारण है कि आधुनिक आरएसए 2048-बिट या बड़े मापांक का उपयोग करता है।

Mechanisms

कुंजी निर्माण दो बड़े यादृच्छिक अभाज्य p और q का चयन करता है, n = p*q सेट करता है, (p-1)(q-1) के सह-अभाज्य एक सार्वजनिक घातांक e चुनता है, और e के मॉड्यूलर व्युत्क्रम के रूप में निजी घातांक d की गणना करता है। एन्क्रिप्शन c = m^e mod n की गणना करता है; डिक्रिप्शन m = c^d mod n को पुनर्प्राप्त करता है। शुद्धता यूलर के प्रमेय से आती है। सुरक्षित परिनियोजन एन्क्रिप्शन के लिए OAEP पैडिंग में प्लेनटेक्स्ट को लपेटता है और हस्ताक्षरों के लिए PSS का उपयोग करता है, क्योंकि कच्चा 'पाठ्यपुस्तक' आरएसए परिवर्तनशील और नियतात्मक होता है।

Clinical relevance

आरएसए दशकों से तैनात बुनियादी ढांचे को सुरक्षित करता है: टीएलएस सर्वर प्रमाणपत्र, कोड हस्ताक्षर, एसएसएच कुंजी, पीजीपी/एस-एमआईएमई ईमेल, स्मार्ट कार्ड और दस्तावेज़ हस्ताक्षर। हालांकि छोटे कुंजियों के कारण नए सिस्टम के लिए अण्डाकार-वक्र योजनाएं तेजी से पसंद की जाती हैं, आरएसए प्रमाणपत्रों और विरासत प्रोटोकॉल में व्यापक रहता है, और वास्तविक दुनिया के क्रिप्टोग्राफिक जोखिम का आकलन करने के लिए इसे समझना आवश्यक है।

Evidence & guidelines

आरएसए PKCS #1 (RFC 8017) में मानकीकृत है, जो OAEP और PSS को निर्दिष्ट करता है। NIST (SP 800-57) उच्च सुरक्षा स्तरों के लिए 3072-बिट के साथ न्यूनतम 2048-बिट मापांक की सिफारिश करता है। उल्लेखनीय विफलताएं (डेबियन कमजोर-कुंजी बग, इन्फिनियन कुंजी निर्माण में ROCA दोष, और 512-बिट निर्यात आरएसए के लिए FREAK डाउनग्रेड) सही कुंजी निर्माण और पैरामीटर आकारों के महत्व को रेखांकित करती हैं।

History

आरएसए को 1977-1978 में रिवेस्ट, शमीर और एडलमैन द्वारा एमआईटी में प्रकाशित किया गया था, जो डिफी और हेलमैन द्वारा प्रस्तावित सार्वजनिक-कुंजी अवधारणा की पहली व्यावहारिक प्राप्ति थी। (क्लिफर्ड कॉक्स ने 1973 में जीसीएचक्यू में गुप्त रूप से एक समान योजना की खोज की थी।) गुणनखंडन में प्रगति — द्विघात छलनी और फिर 1980-1990 के दशक में संख्या क्षेत्र छलनी — ने सुरक्षित कुंजी आकार को उत्तरोत्तर बढ़ाया, और आरएसए गुणनखंडन चुनौतियां व्यावहारिक प्रगति को ट्रैक करती थीं।

Key figures

• Ronald Rivest
• Adi Shamir
• Leonard Adleman
• Carl Pomerance
• Arjen Lenstra

Seminal works

• rivest1978
• katz2020
• menezes1996

Frequently asked questions

क्या आरएसए टूट गया है?

कोई भी शास्त्रीय हमला पर्याप्त बड़े मापांक (2048 बिट्स या अधिक) के साथ ठीक से लागू आरएसए को नहीं तोड़ता है। वास्तविक दुनिया में आरएसए की विफलताएं बहुत छोटी कुंजियों, कमजोर यादृच्छिक संख्या पीढ़ी, या गुम/गलत पैडिंग से उत्पन्न होती हैं, न कि एल्गोरिथम के टूटने से। हालांकि, एक बड़ा क्वांटम कंप्यूटर शोर के एल्गोरिथम के माध्यम से आरएसए को तोड़ देगा।

मैं सीधे आरएसए फ़ंक्शन के साथ एन्क्रिप्ट क्यों नहीं कर सकता?

कच्चा 'पाठ्यपुस्तक' आरएसए नियतात्मक और परिवर्तनशील है, जो जानकारी लीक करता है और सिफरटेक्स्ट हेरफेर की अनुमति देता है। सुरक्षित उपयोग के लिए एन्क्रिप्शन के लिए OAEP और हस्ताक्षरों के लिए PSS जैसी यादृच्छिक पैडिंग की आवश्यकता होती है, यही कारण है कि मानक इन योजनाओं को अनिवार्य करते हैं।