पोस्ट-क्वांटम क्रिप्टोग्राफी - नया एल्गोरिदम "60 मिनट में चला गया"

हमने PQC के बारे में लिखा है, संक्षेप में पोस्ट-क्वांटम क्रिप्टोग्राफी, पहले कई बार।

यदि आप तथाकथित क्वांटम कंप्यूटिंग के बारे में पिछले कुछ वर्षों के सभी मीडिया उत्साह से चूक गए हैं ...

…यह (यदि आप क्षमा करेंगे, तो कुछ विशेषज्ञ शायद एक लापरवाह ओवरसिम्प्लीफिकेशन पर विचार करेंगे) कंप्यूटिंग उपकरणों के निर्माण का एक तरीका है जो इसका ट्रैक रख सकता है कई संभावित परिणाम एक ही समय में गणना।

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

क्वांटम कंप्यूटिंग डिवाइस का उपयोग करके दो दिलचस्प क्रिप्टैनालिटिकल स्पीडअप संभव हैं, यह मानते हुए कि एक उपयुक्त शक्तिशाली और विश्वसनीय वास्तव में बनाया जा सकता है:

• ग्रोवर का क्वांटम सर्च एल्गोरिथम। आम तौर पर, यदि आप यह देखने के लिए कि क्या आपका उत्तर सूची में है, बेतरतीब ढंग से क्रमबद्ध उत्तरों के सेट को खोजना चाहते हैं, तो आप निश्चित उत्तर प्राप्त करने से पहले, पूरी सूची के माध्यम से हल करने की अपेक्षा करेंगे। उदाहरण के लिए, यदि आप किसी दस्तावेज़ को खोलने के लिए 128-बिट एईएस डिक्रिप्शन कुंजी खोजना चाहते हैं, तो आपको सभी संभावित कुंजियों की सूची खोजनी होगी, 000..001, ..2, ..3, और इसी तरह, सभी तरह से FFF..FFF (16 बाइट्स' लायक FF), समस्या को पूरा करने के लिए निश्चित होना। दूसरे शब्दों में, आपको सभी 2 try आज़माने के लिए बजट देना होगा¹²⁸ संभव कुंजी या तो सही कुंजी खोजने से पहले, या यह निर्धारित करने से पहले कि कोई एक नहीं थी। हालांकि, ग्रोवर का एल्गोरिदम, एक बड़ा और शक्तिशाली पर्याप्त क्वांटम कंप्यूटर दिया गया है, यह दावा करता है कि वह उसी उपलब्धि को पूरा करने में सक्षम है। वर्गमूल सामान्य प्रयास में, इस प्रकार कोड को क्रैक करना, सिद्धांत रूप में, केवल 2⁶⁴ इसके बजाय कोशिश करता है।
• शोर का क्वांटम गुणनखंड एल्गोरिथ्म। कई समकालीन एन्क्रिप्शन एल्गोरिदम इस तथ्य पर भरोसा करते हैं कि दो बड़ी अभाज्य संख्याओं को एक साथ गुणा करना जल्दी से किया जा सकता है, जबकि उनके उत्पाद को उन दो संख्याओं में विभाजित करना जिन्हें आपने शुरू किया था, उतना ही अच्छा है जितना असंभव है। इसे महसूस करने के लिए, पेन-एंड-पेपर का उपयोग करके 59×87 गुणा करने का प्रयास करें। इसे निकालने में एक या दो मिनट लग सकते हैं (5133 उत्तर है), लेकिन यह इतना कठिन नहीं है। अब दूसरा तरीका आजमाएं। कहें, 4171 को इसके दो कारकों में विभाजित करें। अधिक कठोर! (यह 43×97 है।) अब इसे 600 अंकों की संख्या के साथ करने की कल्पना करें। संक्षेप में, जब तक आप जैकपॉट नहीं मारते हैं, तब तक आप 600 अंकों की संख्या को हर संभावित 300 अंकों की अभाज्य संख्या से विभाजित करने की कोशिश में फंस जाते हैं, या कोई जवाब नहीं मिलता है। हालाँकि, शोर का एल्गोरिथ्म इस समस्या को हल करने का वादा करता है लोगारित्म सामान्य प्रयास से। इस प्रकार 2048 बाइनरी अंकों की संख्या को फ़ैक्टर करने में 1024-बिट संख्या को फ़ैक्टर करने में केवल दुगना समय लगना चाहिए, न कि 2047-बिट संख्या के फ़ैक्टरिंग के रूप में दो बार, जो एक विशाल गति का प्रतिनिधित्व करता है।

खतरे का मुकाबला

ग्रोवर के एल्गोरिथम से खतरे का मुकाबला केवल उन संख्याओं के आकार को बढ़ाकर किया जा सकता है जिनका आप उपयोग कर रहे हैं, जिसका अर्थ है कि आपके क्रिप्टोग्राफ़िक हैश या आपकी सममित एन्क्रिप्शन कुंजी में बिट्स की संख्या को दोगुना करना। (दूसरे शब्दों में, अगर आपको लगता है कि SHA-256 अभी ठीक है, तो इसके बजाय SHA-512 का उपयोग करने से PQC-प्रतिरोधी विकल्प मिल जाएगा।)

लेकिन शोर के एल्गोरिदम को इतनी आसानी से काउंटर नहीं किया जा सकता है।

2048 बिट्स की एक सार्वजनिक कुंजी को इसके आकार में तेजी से वृद्धि की आवश्यकता होगी, न कि केवल वर्ग द्वारा, ताकि 2 × 2048 = 4096 बिट्स की कुंजी के बजाय, या तो आपको 2 के असंभव आकार के साथ एक नई कुंजी की आवश्यकता होगी²⁰⁴⁸ बिट्स…

या आपको एक पूरी तरह से नए प्रकार के पोस्ट-क्वांटम एन्क्रिप्शन सिस्टम को अपनाना होगा, जिस पर शोर का एल्गोरिदम लागू नहीं होता।

खैर, अमेरिकी मानक निकाय एनआईएसटी चल रहा है PQC "प्रतियोगिता" 2017 के अंत से।

प्रक्रिया सभी के लिए खुली है, सभी प्रतिभागियों का स्वागत है, सभी एल्गोरिदम खुले तौर पर प्रकाशित हुए हैं, और सार्वजनिक जांच न केवल संभव है बल्कि सक्रिय रूप से प्रोत्साहित किया गया:

प्रस्तावों के लिए कॉल। [बंद 2017-11-30]। [...] यह इरादा है कि नए सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी मानक एक या अधिक अतिरिक्त अवर्गीकृत, सार्वजनिक रूप से प्रकट किए गए डिजिटल हस्ताक्षर, सार्वजनिक-कुंजी एन्क्रिप्शन, और कुंजी-स्थापना एल्गोरिदम निर्दिष्ट करेंगे जो दुनिया भर में उपलब्ध हैं, और संवेदनशील सरकारी जानकारी की सुरक्षा करने में सक्षम हैं। क्वांटम कंप्यूटरों के आगमन के बाद सहित, निकट भविष्य में अच्छी तरह से।

तीन दौर की प्रस्तुतियाँ और चर्चा के बाद, एनआईएसटी ने घोषणा की, 2022-07-05 को, कि उसने चार एल्गोरिदम को चुना था जिसे उसने तत्काल प्रभाव से "मानकों" के रूप में माना था, सभी रमणीय-लगने वाले नामों के साथ: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, तथा SPHINCS+.

सबसे पहला (CRYSTALS-KYBER) के रूप में प्रयोग किया जाता है जिसे a . कहा जाता है प्रमुख समझौता तंत्र (केईएम), जहां एक सार्वजनिक संचार चैनल के दो छोर सुरक्षित रूप से एक सत्र के मूल्य के डेटा को गोपनीय रूप से आदान-प्रदान करने के लिए एक बार की निजी एन्क्रिप्शन कुंजी को सुरक्षित रूप से तैयार करते हैं। (सीधे शब्दों में कहें: स्नूपर्स को सिर्फ कटी हुई गोभी मिलती है, इसलिए वे बातचीत पर ध्यान नहीं दे सकते.)

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

अधिक एल्गोरिदम की आवश्यकता

उसी समय, नए मानकों की घोषणा करते हुए, एनआईएसटी ने भी घोषणा की चौथा दौर अपनी प्रतिस्पर्धा के लिए, संभावित वैकल्पिक KEMs के रूप में और चार एल्गोरिदम को आगे बढ़ाना। (याद रखें कि, लेखन के समय, हमारे पास चुनने के लिए पहले से ही तीन स्वीकृत डिजिटल हस्ताक्षर एल्गोरिदम हैं, लेकिन केवल एक आधिकारिक KEM है।)

ये थे: BIKE, Classic McEliece, HQC और SIKE.

दिलचस्प बात यह है कि मैकएलीस एल्गोरिथम 1970 के दशक में अमेरिकी क्रिप्टोग्राफर रॉबर्ट मैक एलीस द्वारा आविष्कार किया गया था, जिनकी 2019 में मृत्यु हो गई थी, एनआईएसटी की प्रतियोगिता पहले से ही चल रही थी।

हालांकि, यह कभी भी पकड़ा नहीं गया, क्योंकि इसे दिन के लोकप्रिय विकल्प, डिफी-हेलमैन-मेर्कल एल्गोरिदम (डीएचएम, या कभी-कभी सिर्फ डीएच) की तुलना में बड़ी मात्रा में महत्वपूर्ण सामग्री की आवश्यकता होती है।

दुर्भाग्य से, तीन राउंड फोर एल्गोरिदम में से एक, अर्थात् SIKE, ऐसा लगता है कि फट गया है।

एक दिमाग घुमा देने वाले पेपर में जिसका शीर्षक है सिद्ध पर एक प्रभावी कुंजी पुनर्प्राप्ति हमला (प्रारंभिक संस्करण)ऐसा लगता है कि बेल्जियम के क्रिप्टोग्राफर राउटर कास्त्रिक और थॉमस डेक्रू ने SIKE एल्गोरिथम को एक घातक झटका दिया है।

यदि आप सोच रहे हैं, तो SIKE संक्षिप्त है सुपरसिंगुलर आइसोजेनी कुंजी एनकैप्सुलेशन, और SIDH का अर्थ है सुपरसिंगुलर आइसोजेनी डिफी-हेलमैन, का एक विशिष्ट उपयोग SIKE एल्गोरिथम जिससे एक संचार चैनल के दो छोर सार्वजनिक डेटा के एक समूह का आदान-प्रदान करने के लिए एक डीएचएम-जैसे "क्रिप्टोडांस" का प्रदर्शन करते हैं जो प्रत्येक छोर को एक बार की गुप्त एन्क्रिप्शन कुंजी के रूप में उपयोग करने के लिए एक निजी मूल्य प्राप्त करने की अनुमति देता है।

हम यहां हमले की व्याख्या करने की कोशिश नहीं करने जा रहे हैं; हम वही दोहराएँगे जो पेपर दावा करता है, अर्थात्:

बहुत ही ढीले शब्दों में, यहां इनपुट में प्रमुख स्थापना क्रिप्टोडांस में प्रतिभागियों में से एक द्वारा प्रदान किया गया सार्वजनिक डेटा शामिल है, साथ ही प्रक्रिया में उपयोग किए जाने वाले पूर्व-निर्धारित (और इसलिए सार्वजनिक रूप से ज्ञात) पैरामीटर शामिल हैं।

लेकिन जो आउटपुट निकाला जाता है (जानकारी के रूप में संदर्भित) आइसोजेनी ऊपर) को प्रक्रिया का कभी-कभी प्रकट नहीं किया गया हिस्सा माना जाता है - तथाकथित निजी कुंजी।

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

और एक बार जब आप मेरी निजी कुंजी जान जाते हैं, तो आप आसानी से और अनजाने में मेरे होने का दिखावा कर सकते हैं, इसलिए एन्क्रिप्शन प्रक्रिया टूट जाती है।

जाहिर है, की-क्रैकिंग एल्गोरिथम को अपना काम करने में लगभग एक घंटे का समय लगता है, बस एक सीपीयू कोर का उपयोग करके उस तरह की प्रोसेसिंग पावर जो आपको रोजमर्रा के लैपटॉप में मिलती है।

स्तर 1 को पूरा करने के लिए कॉन्फ़िगर किए जाने पर यह SIKE एल्गोरिथम के विरुद्ध है, NIST की एन्क्रिप्शन सुरक्षा के मूल ग्रेड।

क्या करना है?

कुछ भी तो नहीं!

(यह अच्छी खबर है।)

जैसा कि पेपर के लेखक सुझाव देते हैं, यह देखते हुए कि उनका परिणाम अभी भी प्रारंभिक है, "वर्तमान स्थिति के साथ, SIDH किसी भी सार्वजनिक रूप से उत्पन्न आधार वक्र के लिए पूरी तरह से टूटा हुआ प्रतीत होता है।"

(यह बुरी खबर है।)

हालाँकि, यह दें कि SIKE एल्गोरिथम को अभी तक आधिकारिक रूप से स्वीकृत नहीं किया गया है, अब इसे या तो इस विशेष हमले को विफल करने के लिए अनुकूलित किया जा सकता है (ऐसा कुछ जिसे लेखक मानते हैं कि संभव हो सकता है), या बस पूरी तरह से गिरा दिया गया।

SIKE के साथ जो कुछ भी होता है, यह एक उत्कृष्ट अनुस्मारक है कि क्यों अपने स्वयं के एन्क्रिप्शन एल्गोरिदम का आविष्कार करने की कोशिश करना खतरे से भरा है।

यह इस बात का भी एक स्पष्ट उदाहरण है कि क्यों मालिकाना एन्क्रिप्शन सिस्टम जो स्वयं एल्गोरिथम की गोपनीयता पर निर्भर करते हैं 2022 में उनकी सुरक्षा बनाए रखना अस्वीकार्य है।

यदि SIKE जैसा PQC एल्गोरिथम विशेष रूप से प्रकट किए जाने के बावजूद पांच साल से अधिक समय तक दुनिया भर के विशेषज्ञों द्वारा लगातार और जांच में जीवित रहा, ताकि इसे सार्वजनिक जांच के अधीन किया जा सके ...

...तो अपने आप से यह पूछने की कोई आवश्यकता नहीं है कि आपके घर-निर्मित, छिपे हुए-से-दृश्य एन्क्रिप्शन एल्गोरिदम के जंगली में जारी होने पर कितना अच्छा प्रदर्शन करने की संभावना है!

---