RSA की व्याख्या
हर बार जब ब्राउज़र ताले का निशान दिखाता है, किसी संदेश पर हस्ताक्षर होता है या कोई सॉफ़्टवेयर किसी अपडेट की जाँच करता है, तब सार्वजनिक कुंजी क्रिप्टोग्राफ़ी काम कर रही होती है, और RSA इसका सबसे प्रसिद्ध रूप है। इसका विचार यह है कि संदेश पर ताला लगाने वाली कुंजी प्रकाशित की जा सकती है, जबकि उसे खोलने वाली कुंजी निजी रहती है। उल्लेखनीय है कि पूरी प्रणाली स्कूल में पढ़ाए जाने वाले अंकगणित पर टिकी है: अभाज्य संख्याएँ, गुणा और शेषफल।
RSA कौन-सी समस्या हल करता है
पुराने सिफ़र, सीज़र के खिसकाव से लेकर आधुनिक AES तक, ताला लगाने और खोलने के लिए एक ही कुंजी इस्तेमाल करते हैं, इसलिए दोनों पक्षों को पहले निजी तौर पर एक गुप्त कुंजी साझा करनी पड़ती है। सार्वजनिक कुंजी क्रिप्टोग्राफ़ी यह चरण हटा देती है। हर व्यक्ति के पास दो कुंजियाँ होती हैं: एक सार्वजनिक कुंजी, जिससे कोई भी उसके लिए संदेश एन्क्रिप्ट कर सकता है, और एक निजी कुंजी, जो केवल उसी के पास होती है और केवल वही उस संदेश को डिक्रिप्ट कर सकती है। व्हिटफ़ील्ड डिफ़ी और मार्टिन हेलमैन ने 1976 में यह विचार प्रस्तुत किया, और एक साल बाद MIT में रॉन रिवेस्ट, आदि शमीर और लियोनार्ड एडलमैन ने इसे साकार करने का तरीका खोजा, जिसका नाम उनके नामों के पहले अक्षरों पर RSA रखा गया।
कुंजियाँ बनाना
दो बड़ी अभाज्य संख्याएँ p और q चुनें, और उन्हें गुणा करें: n = p × q। φ(n) = (p − 1)(q − 1) निकालें, यानी ऑयलर का टोशिएंट फलन, जो उन संख्याओं को गिनता है जो n से छोटी हैं और जिनका n के साथ कोई उभयनिष्ठ गुणनखंड नहीं है। एक सार्वजनिक घातांक e चुनें जिसका φ(n) के साथ कोई उभयनिष्ठ गुणनखंड न हो; आमतौर पर 65537 चुना जाता है। फिर निजी घातांक d ढूँढें, ताकि e × d को φ(n) से भाग देने पर शेषफल 1 बचे। विस्तारित यूक्लिडियन एल्गोरिदम यह काम जल्दी कर देता है। सार्वजनिक कुंजी युग्म (e, n) है; निजी कुंजी d है। p = 61 और q = 53 के साथ इससे n = 3233, φ(n) = 3120, e = 17 और d = 2753 मिलते हैं।
एन्क्रिप्ट और डिक्रिप्ट करना
संदेश को पहले n से छोटी एक संख्या m में बदला जाता है। इसे एन्क्रिप्ट करने के लिए c = mᵉ mod n निकालें, यानी mᵉ को n से भाग देने पर बचा शेषफल। डिक्रिप्ट करने के लिए cᵈ mod n निकालें। ऑयलर का प्रमेय गारंटी देता है कि इससे m वापस मिलता है, क्योंकि e × d, φ(n) के किसी गुणज से एक अधिक है। ऊपर की कुंजियों के साथ अक्षर A, जिसका कोड 65 है, 65¹⁷ mod 3233 = 2790 बन जाता है, और 2790²⁷⁵³ mod 3233 = 65 फिर से। इतनी बड़ी घातें कभी पूरी लिखी नहीं जातीं: बार-बार वर्ग करने की विधि घातांक के हर बिट के लिए एक बार वर्ग करके और हर चरण पर शेषफल लेकर इनकी गणना करती है।
डिजिटल हस्ताक्षर
RSA उलटी दिशा में भी काम करता है। किसी संदेश को निजी घातांक तक उठाने से, s = mᵈ mod n, एक ऐसा हस्ताक्षर बनता है जिसे केवल कुंजी का मालिक बना सकता है। कोई भी सार्वजनिक कुंजी से इसकी जाँच कर सकता है: अगर sᵉ mod n से m वापस मिलता है, तो संदेश d के धारक से आया है और रास्ते में बदला नहीं गया। व्यवहार में हस्ताक्षर संदेश पर नहीं, बल्कि संदेश के एक छोटे हैश पर किया जाता है। इस तरह के हस्ताक्षर सॉफ़्टवेयर अपडेट, सुरक्षित वेबसाइटों और इलेक्ट्रॉनिक दस्तावेज़ों की रक्षा करते हैं।
यह सुरक्षित क्यों है
n और e सब देख सकते हैं। d ढूँढने के लिए हमलावर को φ(n) चाहिए, और φ(n) ढूँढने के लिए p और q, इसलिए RSA को तोड़ना n के गुणनखंडन पर आकर टिकता है। दो अभाज्य संख्याओं को गुणा करने में कंप्यूटर को एक माइक्रोसेकंड का अंश लगता है; गुणनफल को वापस उनमें तोड़ना अत्यंत कठिन माना जाता है। अब तक गुणनखंडित सबसे बड़ी RSA चुनौती संख्या, 2020 में RSA-250, में 829 बिट हैं और इसमें लगभग 2700 वर्ष का कंप्यूटर समय लगा। आज इस्तेमाल होने वाली कुंजियों में कम से कम 2048 बिट होते हैं, यानी लगभग 617 अंक।
दो बार खोजा गया रहस्य
1973 में, RSA से चार साल पहले, ब्रिटिश गणितज्ञ क्लिफ़र्ड कॉक्स ने ख़ुफ़िया एजेंसी GCHQ में काम करते हुए अपने सहकर्मी जेम्स एलिस के एक विचार को आगे बढ़ाकर यही योजना खोज ली थी। यह काम गोपनीय रखा गया और 1997 में ही सार्वजनिक किया गया। RSA को ख़ुद 1983 में संयुक्त राज्य अमेरिका में पेटेंट किया गया; पेटेंट सितंबर 2000 में समाप्त हुआ, एल्गोरिदम को सार्वजनिक डोमेन में जारी किए जाने के दो सप्ताह बाद।
व्यवहार में RSA
असली RSA कभी पाठ को सीधे एन्क्रिप्ट नहीं करता। OAEP जैसी किसी योजना से संदेश में यादृच्छिक बाइट्स की पैडिंग जोड़ी जाती है, ताकि एक ही संदेश हर बार अलग तरह से एन्क्रिप्ट हो और पैटर्न लीक न हो सकें। चूँकि RSA धीमा है, इसलिए यह ज़्यादातर AES जैसे किसी तेज़ सममित सिफ़र की छोटी कुंजी के आदान-प्रदान या सुरक्षा के लिए, या हस्ताक्षर के लिए इस्तेमाल होता है। पर्याप्त बड़े क्वांटम कंप्यूटर 1994 के शोर एल्गोरिदम से n का गुणनखंडन जल्दी कर सकते हैं, इसीलिए RSA के साथ-साथ नई पोस्ट-क्वांटम विधियाँ लाई जा रही हैं।
ख़ुद आज़माएँ
अपनी खुद की अभाज्य संख्याओं से या 2 से 8 अंकों की यादृच्छिक अभाज्य संख्याओं से कुंजियाँ बनाने, विस्तारित यूक्लिडियन एल्गोरिदम को पंक्ति-दर-पंक्ति d ढूँढते देखने, किसी संदेश को अक्षर-दर-अक्षर एन्क्रिप्ट करने या उस पर हस्ताक्षर करने, और किसी भी अक्षर के लिए बार-बार वर्ग करने की प्रक्रिया को चरण-दर-चरण देखने के लिए RSA एन्क्रिप्शन डेमो खोलें। फिर ईव को n का गुणनखंडन करने दें और देखें कि अभाज्य संख्याओं के आकार के साथ उसे लगने वाला समय कैसे बढ़ता है।
अक्सर पूछे जाने वाले प्रश्न
RSA को अभाज्य संख्याओं की ज़रूरत क्यों है?
क्योंकि φ(n) की गणना तभी आसान है जब आप जानते हों कि n अभाज्य गुणनखंडों में कैसे टूटता है। n = p × q के लिए, जहाँ p और q अभाज्य हैं, φ(n) = (p − 1)(q − 1)। अभाज्य संख्याएँ n को उसके आकार के हिसाब से गुणनखंडन के लिए यथासंभव कठिन भी बनाती हैं, क्योंकि उसका कोई छोटा गुणनखंड होता ही नहीं।
e अक्सर 65537 क्यों होता है?
65537 = 2¹⁶ + 1 अभाज्य है और द्विआधारी में इसमें केवल दो 1 हैं, इसलिए इससे एन्क्रिप्ट करने में केवल 16 बार वर्ग करना और एक गुणा लगता है। यह इतना बड़ा भी है कि 3 जैसे बहुत छोटे घातांकों की कमज़ोरियों से बचा जा सके।
RSA और डिफ़ी–हेलमैन में क्या अंतर है?
डिफ़ी–हेलमैन दो लोगों को एक खुले चैनल पर एक साझा गुप्त कुंजी पर सहमत होने देता है; यह अपने आप न कुछ एन्क्रिप्ट करता है, न किसी चीज़ पर हस्ताक्षर करता है। RSA एक कुंजी जोड़ी से सीधे एन्क्रिप्ट और हस्ताक्षर करता है। दोनों ऐसी समस्याओं पर टिके हैं जो एक दिशा में आसान और दूसरी दिशा में कठिन हैं: RSA के लिए गुणनखंडन, डिफ़ी–हेलमैन के लिए असतत लघुगणक।
क्या डेमो की कुंजियाँ असली एन्क्रिप्शन के लिए इस्तेमाल की जा सकती हैं?
नहीं। इसकी अभाज्य संख्याओं में अधिकतम एक दर्जन अंक होते हैं, इसलिए इसकी बनाई किसी भी कुंजी का गुणनखंडन कुछ सेकंड या उससे भी कम में हो सकता है, और यह हर अक्षर को बिना पैडिंग के अलग-अलग एन्क्रिप्ट करता है। यह यह देखने के लिए है कि RSA कैसे काम करता है, किसी चीज़ की सुरक्षा के लिए नहीं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
RSA एन्क्रिप्शन डेमो खोलें