क्रिप्टोग्राफी में एक नई उपलब्धि - 795-बिट आरएसए का फैक्टराइजेशन

2 दिसंबर, 2019 को, संख्या सिद्धांत मेलिंग सूची nmbrthry@listserv.nodak.edu ने RSA-240 संख्या (240 दशमलव स्थान, 795 बिट्स) के कारककरण की सूचना दी। यह क्रिप्टोग्राफी और संख्या सिद्धांत और RSA फैक्टरिंग चैलेंज सूची से अगले पूर्ण असाइनमेंट में एक नई उपलब्धि है।

यहाँ संख्या और इसके कारक हैं:

RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447 

वर्तमान प्रवृत्ति के आधार पर, आप मोटे तौर पर कल्पना कर सकते हैं जब RSA-1024 (309 दशमलव अंक) और RSA-2048 (617 अंक) हैक हो जाएंगे।

पिछली उपलब्धियां 2009 में 768-बिट संख्या (232 दशमलव स्थानों) का कारक रही हैं और 2016 में 768-बिट संख्या का असतत लघुगणक ।



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

तेजी से परिष्कृत सिफर धीरे-धीरे टूट रहे हैं क्योंकि सीपीयू प्रदर्शन बढ़ता है और एल्गोरिदम में सुधार होता है।

90 के दशक की शुरुआत में सामान्य संख्या क्षेत्र छलनी (GNFS) एल्गोरिथ्म के आविष्कार के बाद, पूर्णांक कारक के क्षेत्र में कुछ भी क्रांतिकारी नहीं दिखाई दिया, हालांकि कुछ महत्वपूर्ण अनुकूलन किए गए थे। उदाहरण के लिए, पिछले कुछ वर्षों में, शोधकर्ता एक उपयुक्त बहुपद को खोजने के चरण में बहुत तेजी लाने में सक्षम हुए हैं।

RSA-240 का कारकीकरण भी सामान्य पंक्ति से बाहर है, क्योंकि यह न केवल कंप्यूटिंग शक्ति को बढ़ाकर, बल्कि सॉफ्टवेयर और एल्गोरिदम के अनुकूलन के कारण भी किया गया था। किए गए परिवर्तनों की प्रभावशीलता को साबित करने के लिए, शोधकर्ताओं ने उन्हीं उपकरणों पर कार्यक्रम शुरू किया, जिनका उपयोग 2016 में 768-बिट असतत लघुगणक की गणना के लिए किया गया था। उन्होंने पाया कि 795-बिट संख्या के मैट्रिक्स को उस पर स्थानांतरित करना अनुकूलन के बिना 768-बिट संख्याओं के मैट्रिक्स को स्थानांतरित करने की तुलना में 25% अधिक तेज है।

शोधकर्ताओं के एक ही समूह ने एक ही आकार के असतत लघुगणक की गणना की। इतिहास में पहली बार, एक ही आकार के संख्याओं के असतत लॉगआर्मिंग और फैक्टराइजेशन के रिकॉर्ड एक ही समय में सेट किए गए हैं, और यहां तक ​​कि एक ही हार्डवेयर और सॉफ्टवेयर पर भी।

एल्गोरिदम और सॉफ्टवेयर के अनुकूलन के लिए धन्यवाद, एक ही हार्डवेयर पर अनुकूलन के बिना 768-बिट संख्या के लघुगणक की तुलना में 795-बिट संख्या के असतत लघुगणक को 33% तक त्वरित किया गया था।

सिद्धांत के अनुसार, 795-बिट संख्या का लघुगणक 768-बिट संख्या की तुलना में 2.25 गुना अधिक जटिल है। इसका मतलब है कि अनुकूलन प्रभाव वास्तव में तीन गुना (2.25 × 1.33 = 3) है।

ओपन सोर्स CADO-NFS प्रोग्राम में छलनी नंबर फील्ड एल्गोरिदम का उपयोग करके दोनों प्रकार की गणना की गई। अनुकूलन में सुधार के साथ समानांतरकरण और मेमोरी का उपयोग होता है, साथ ही साथ अधिक इष्टतम गणना मापदंडों को खोजने के लिए बहुत सारे काम (विशेष सॉफ्टवेयर को विभिन्न गणना मापदंडों के परीक्षण और रैंकिंग के लिए विकसित किया गया था)।

दोनों नए रिकॉर्ड के लिए कम्प्यूटेशनल समय का योग इंटेल Xeon गोल्ड 6130 प्रोसेसर (2.1 गीगाहर्ट्ज की आवृत्ति पर) के भौतिक कोर के संचालन के लगभग 4000 वर्षों का है, अगर इस प्रोसेसर को संदर्भ के रूप में लिया जाता है।

कारक और लघुगणक में समय का एक मोटा टूटना:

• स्क्रीनिंग RSA-240: 800 कोर-वर्ष
  
• RSA-240 मैट्रिक्स: 100 कोर-वर्ष
  
• स्क्रीनिंग DLP-240: 2400 कोर-वर्ष
  
• मैट्रिक्स DLP-240: 700 कोर-वर्ष

फ्रेंच नेशनल इंस्टीट्यूट ऑफ इंफॉर्मेटिक्स एंड एप्लाइड मैथेमेटिक्स के एक प्रमुख शोधकर्ता इमैनुएल थॉम की अगुवाई में एक शोध दल ने इस उपलब्धि को हासिल किया।

आरएसए सिफर के अन्वेषकों ने आरएसए -2048 तक सभी आकारों के आरएसए नंबर प्रकाशित किए हैं। हर कोई उन्हें हैक करने की कोशिश कर सकता है।

वर्तमान प्रवृत्ति के आधार पर, आप गणना कर सकते हैं कि RSA-1024 (309 वर्ण) और RSA-2048 (617 वर्ण) कब हैक किए जाएंगे। यदि आप अनुसूची को एक्सट्रपलेशन करते हैं, तो आपको क्रमशः 2031 और 2073 मिलते हैं। लेकिन हम देखते हैं कि सॉफ्टवेयर और एल्गोरिदम का अनुकूलन इस शब्द को काफी करीब ला सकता है। शायद RSA-2048 हमारे जीवनकाल के दौरान हैक हो जाएगा।

व्यवहार में, RSA 2048 या 4096 बिट्स के न्यूनतम RSA कुंजी आकार का उपयोग करने की सलाह देता है।

क्वांटम कंप्यूटरों के विकास को देखते हुए, वे जल्द ही इस आकार की ब्रेकिंग कीज़ के करीब नहीं आएंगे, हालाँकि यहाँ कुछ भविष्यवाणी करना मुश्किल है। 2012 में, शोर एल्गोरिथ्म ने 21 (3 × 7) के कारक के साथ मुकाबला किया, एंट्रोपी के पांच बिट्स। यह संख्या लंबे समय तक क्वांटम फैक्टराइजेशन का रिकॉर्ड बनी हुई है, लेकिन 2018 में, आईबीएम 5- और 16-क्विट प्रोसेसर पर प्रिम्स 4088459 के प्रोडक्ट का फैक्टराइजेशन प्रदर्शित किया गया, जो पहले से ही 22 बिट्स है।

---