एमआईटी पाठ्यक्रम "कंप्यूटर सिस्टम सुरक्षा"। व्याख्यान 16: "साइड चैनल हमलों", भाग 3

मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी। व्याख्यान पाठ्यक्रम # 6.858। "कंप्यूटर सिस्टम की सुरक्षा।" निकोलाई ज़ेल्डोविच, जेम्स मिकेंस। 2014 साल

कंप्यूटर सिस्टम सुरक्षा सुरक्षित कंप्यूटर सिस्टम के विकास और कार्यान्वयन पर एक कोर्स है। व्याख्यान खतरे के मॉडल को कवर करते हैं, हमले जो सुरक्षा से समझौता करते हैं, और हाल के वैज्ञानिक कार्यों के आधार पर सुरक्षा तकनीक। विषयों में ऑपरेटिंग सिस्टम (OS) सुरक्षा, सुविधाएँ, सूचना प्रवाह प्रबंधन, भाषा सुरक्षा, नेटवर्क प्रोटोकॉल, हार्डवेयर सुरक्षा और वेब अनुप्रयोग सुरक्षा शामिल हैं।

व्याख्यान 1: "परिचय: खतरे के मॉडल" भाग 1 / भाग 2 / भाग 3
व्याख्यान 2: "हैकर हमलों का नियंत्रण" भाग 1 / भाग 2 / भाग 3
व्याख्यान 3: "बफर ओवरफ्लो: शोषण और संरक्षण" भाग 1 / भाग 2 / भाग 3
व्याख्यान 4: "पृथक्करण का पृथक्करण" भाग 1 / भाग 2 / भाग 3
व्याख्यान 5: "सुरक्षा प्रणालियाँ कहाँ से आती हैं?" भाग 1 / भाग 2
व्याख्यान 6: "अवसर" भाग 1 / भाग 2 / भाग 3
व्याख्यान 7: "मूल ग्राहक सैंडबॉक्स" भाग 1 / भाग 2 / भाग 3
व्याख्यान 8: "नेटवर्क सुरक्षा मॉडल" भाग 1 / भाग 2 / भाग 3
व्याख्यान 9: "वेब अनुप्रयोग सुरक्षा" भाग 1 / भाग 2 / भाग 3
व्याख्यान 10: "प्रतीकात्मक निष्पादन" भाग 1 / भाग 2 / भाग 3
व्याख्यान 11: "उर / वेब प्रोग्रामिंग भाषा" भाग 1 / भाग 2 / भाग 3
व्याख्यान 12: नेटवर्क सुरक्षा भाग 1 / भाग 2 / भाग 3
व्याख्यान 13: "नेटवर्क प्रोटोकॉल" भाग 1 / भाग 2 / भाग 3
व्याख्यान 14: "एसएसएल और एचटीटीपीएस" भाग 1 / भाग 2 / भाग 3
व्याख्यान 15: "मेडिकल सॉफ्टवेयर" भाग 1 / भाग 2 / भाग 3
व्याख्यान 16: "साइड चैनल हमलों" भाग 1 / भाग 2 / भाग 3

श्रोता: क्या आप करतसुबा पद्धति का उपयोग करते हैं?

प्रोफेसर: हाँ, यह एक स्मार्ट गुणन विधि है जिसमें गणना के चार चरणों की आवश्यकता नहीं होती है। करतसुबा पद्धति को .601 पाठ्यक्रम में पढ़ाया जाता है, या यह आज कैसे निर्दिष्ट है?

श्रोता: ०४२।

प्रोफेसर: ०४२, उत्कृष्ट। हाँ, यह एक बहुत अच्छी विधि है। लगभग हर क्रिप्टोग्राफिक लाइब्रेरी इसका उपयोग करती है। आप में से जो हमारे संस्थान के स्नातक नहीं हैं - मैं यह कहता हूं क्योंकि हमारे यहां स्नातक के छात्र हैं - मैं बोर्ड पर करतसुबा पद्धति के बारे में लिखूंगा। यहां आपको तीन मानों की गणना करने की आवश्यकता है:

एक _१ बी _१
( ₁ ए - ₀ ) (बी ₁ - बी ₀ )
एक ₀ b ₀

इस प्रकार, आप चार के बजाय 3 गुणा करते हैं, और यह पता चलता है कि आप इन तीन गुणा परिणामों से इस मूल्य को ₁ b ₀ + + ₀ b ₁ को पुनर्स्थापित कर सकते हैं।



ऐसा करने का विशेष तरीका यह है ... मुझे इसे एक अलग रूप में रखना चाहिए।

तो, हमारे पास होगा:

(२ ^६४ + २ ^३२ ) (एक _१ बी _१ ) +
(२ ^३२ ) (- (ए _१ - ए _० ) (बी _१ - बी _० )
(२ ^३२ + १) (एक _० बी _० )

यह बहुत स्पष्ट नहीं है, लेकिन यदि आप विवरणों पर काम करते हैं, तो अंततः खुद को समझाएं कि इन 3 पंक्तियों में यह मान ab के बराबर है, लेकिन एक ही समय में गणना को एक गुणा से कम कर देता है। और जिस तरह से हम इसे अधिक मात्रा में गुणा करने के लिए लागू करते हैं, यह है कि आप पुनरावर्ती रूप से नीचे जा रहे हैं। इसलिए, यदि आपके पास 512 बिट मान हैं, तो आप उन्हें 256-बिट गुणन में विभाजित कर सकते हैं। आप तीन 256-बिट गुणन करते हैं, हर बार पुन: Karatsuba विधि का उपयोग करते हुए। अंत में, आपकी गणना मशीन के आकार में आ जाती है और इसे एकल मशीन निर्देश द्वारा संसाधित किया जा सकता है।



तो समय हमला कहाँ है? ये लोग करातसुबा गुणा का उपयोग कैसे करते हैं? ओपनएसएसएल चालू करता है दो प्रकार के गुणन के बारे में चिंतित है जो आपको करना पड़ सकता है।
पहला लगभग एक ही आकार की दो बड़ी संख्याओं का गुणन है। ऐसा कई बार होता है जब हम एक मॉड्यूलर एक्सपोनेंशन करते हैं, क्योंकि सभी वैल्यूज जो हम गुणा करेंगे, उनका साइज़ लगभग 512 बिट्स होगा। इसलिए, जब हम y या वर्ग से गुणा करते हैं, तो हम लगभग एक ही आकार की दो चीजों को गुणा करते हैं। इस मामले में, करतसुबा विधि बहुत मायने रखती है, क्योंकि यह संख्या के आकार को लगभग 1.58 गुना कम कर देता है, जो गणना प्रक्रिया को बहुत तेज करता है।
दूसरे प्रकार का गुणन तब होता है जब ओपनएसएसएल दो संख्याओं को गुणा करता है जिसका आकार एक दूसरे से काफी भिन्न होता है: एक बहुत बड़ा है और दूसरा बहुत छोटा है। इस मामले में, आप Karatsuba विधि का उपयोग भी कर सकते हैं, लेकिन यह आदिम गुणन की तुलना में धीमी गति से काम करेगा। मान लें कि आप एक 512-बिट संख्या को 64-बिट संख्या से गुणा करते हैं, तो आपको पहले नंबर की प्रत्येक बिट को 64 की शक्ति तक बढ़ाने की आवश्यकता होगी, जिसके परिणामस्वरूप n / 1.58 त्वरण के बजाय 2n प्रक्रिया में मंदी होगी। इसलिए, OpenSSL का उपयोग करने वाले इन लोगों ने और बेहतर करने की कोशिश की, और यह यहां था कि समस्याएं शुरू हुईं।

उन्होंने फैसला किया कि वे प्रभावी रूप से प्रभावी करत्सुबा पद्धति और प्राथमिक विद्यालय गुणा पद्धति के बीच स्विच करेंगे। उनका अनुमान इस प्रकार था। यदि दो संख्याओं को आप समान रूप से मशीन शब्दों की संख्या से गुणा करते हैं, या कम से कम 32-बिट इकाइयों के समान बिट्स हैं, तो करतसुबा विधि का उपयोग किया जाता है। यदि दो संख्याएं एक दूसरे से आकार में बहुत भिन्न होती हैं, तो स्क्वेरिंग या प्रत्यक्ष सरल, सामान्य गुणा किया जाता है।

इस स्थिति में, आप ट्रैक कर सकते हैं कि गुणन के किसी अन्य तरीके पर स्विच कैसे होता है। चूंकि स्विचिंग का क्षण ट्रेस के बिना नहीं गुजरता है, इसके बाद यह ध्यान देने योग्य होगा कि क्या अब इसे गुणा के लिए बहुत अधिक समय की आवश्यकता है या पहले की तुलना में बहुत कम है। शोधकर्ताओं ने इस परिस्थिति का फायदा उठाते हुए समय पद्धति का उपयोग कर हमले का आयोजन किया।

मुझे लगता है कि मैंने आपको उन सभी अजीब ट्रिक्स के बारे में बताया है जो लोग RSA को लागू करते समय उपयोग करते हैं। अब चलो उन्हें एक साथ रखने की कोशिश करते हैं और पूरे वेब सर्वर के संबंध में उनका उपयोग करते हैं यह जानने के लिए कि आप इनपुट नेटवर्क पैकेट से हमें ब्याज की बिट्स कैसे "चुटकी" कर सकते हैं।

यदि आप HTTPS पर व्याख्यान से याद करते हैं, तो वेब सर्वर में एक गुप्त कुंजी है। वह इस गुप्त कुंजी का उपयोग यह साबित करने के लिए करता है कि वह HTTPS या TLS के सभी प्रमाणपत्रों का सही स्वामी है। यह इस तथ्य के कारण है कि क्लाइंट कुछ बेतरतीब ढंग से चयनित बिट्स भेजते हैं, इन बिट्स को सर्वर की सार्वजनिक कुंजी का उपयोग करके एन्क्रिप्ट किया जाता है, और सर्वर टीएलएस प्रोटोकॉल का उपयोग करके इस संदेश को डिक्रिप्ट करता है। और यदि संदेश की जांच की जाती है, तो इन यादृच्छिक बिट्स का उपयोग संचार सत्र स्थापित करने के लिए किया जाता है।

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

यहाँ हम यहाँ क्या करने जा रहे हैं। सर्वर - आप मान सकते हैं कि यह ओपन एसएसएल के साथ अपाचे है - क्लाइंट से एक संदेश प्राप्त होगा जिसे वह एन्क्रिप्ट किए गए पाठ के साथ या कुछ काल्पनिक एन्क्रिप्टेड पाठ के रूप में मानता है जिसे क्लाइंट ने बनाया है। पहली बात जो हम सिफरटेक् सी के साथ करते हैं वह है → (c ^d mod n) = m के साथ सूत्र का उपयोग करके इसे डिक्रिप्ट करना।

यदि आपको पहला अनुकूलन याद है, तो हम चीनी शेष प्रमेय लागू करने जा रहे हैं और हमारे पाठ को दो भागों में विभाजित करते हैं: एक mod ​​p द्वारा गणना करने के लिए, दूसरा mod q द्वारा, और फिर परिणामों को संयोजित करें। सबसे पहले, c को लें और इसे दो मात्राओं में दर्शाएँ: पहले को c ₀ कहा जाता है, यह mod q के बराबर होगा, और दूसरा c _{1 है} , और यह c mod p के बराबर होगा। फिर हम डी मॉड पी के लिए सी और डी मॉड क्यू के लिए गणना करने के लिए एक ही करेंगे।



अगला, हम मोंटगोमरी के दृश्य पर स्विच करने जा रहे हैं क्योंकि यह हमारे गुणन को बहुत तेज कर देगा। तो अगली चीज़ जो आपके नंबर के साथ SSL करने जा रही है वह है c ₀ 'की गणना करना, जो c ₀ R mod q के बराबर होगा और यहाँ c1 के लिए नीचे की तरह करें, मैंने इसे इसलिए नहीं लिखा क्योंकि यह एक जैसा दिखता है ।

अब जब हम मोंटगोमरी के रूप में बदल गए हैं, तो हम अंत में अपने गुणन कर सकते हैं, और यहां हम "स्लाइडिंग विंडो" तकनीक का उपयोग करेंगे। जैसे ही हमें c ₀ 'मिलता है, हम इस सरल' s 'को' c 'में d की शक्ति में बनाते हैं। और यहाँ, चूंकि हम d के लिए इस मान की गणना करते हैं, इसलिए हम घातांक d के बिट्स के लिए "स्लाइडिंग विंडो" का उपयोग करेंगे, और हम अपने ऑपरेंड्स के आकार के आधार पर करतसुबा विधि या सामान्य गुणा का भी उपयोग करेंगे।



इसलिए, अगर यह पता चला है कि यह मान c ₀ 'और पहले से प्राप्त स्क्वरिंग परिणाम समान आकार के हैं, तो हम Karatsuba पद्धति का उपयोग करते हैं। यदि c ₀ 'बहुत छोटा है, और गुणन का पिछला परिणाम बड़ा है, तो हम सामान्य तरीके से वर्ग और गुणा करेंगे। यहाँ हम सामान्य गुणन के बजाय "स्लाइडिंग विंडो" और करतसुबा पद्धति का उपयोग करते हैं।



इस स्तर पर भी, अतिरिक्त कटौती दिखाई देती है। क्योंकि प्रत्येक गुणन के साथ, अतिरिक्त कटौती उस अनुपात के लिए आनुपातिक होगी जो हम mod q की शक्ति को बढ़ाते हैं, अर्थात (c ₀ ') ^d का मान। यहां, सूत्र के एक साधारण कनेक्शन के साथ, अतिरिक्त कटौती की संभावना 2R से विभाजित मूल्य c ₀ 'mod q के समानुपाती होगी। यह इस जगह पर है कि थोड़ा सा दिखाई देता है जो समय को प्रभावित करता है।

वास्तव में, दो संभावित प्रभाव हैं: सामान्य गुणा के बजाय करत्सुबा विधि का उपयोग करना और अतिरिक्त संक्षिप्तिकरण की उपस्थिति जो आप करने जा रहे हैं।

एक सेकंड में आप देखेंगे कि इसका उपयोग कैसे किया जा सकता है। अब, जब आप मॉड क्यू के लिए यह परिणाम प्राप्त करते हैं और मॉड पी के लिए एक समान परिणाम प्राप्त करने जा रहे हैं, तो आप अंत में ऊपर और नीचे इन दो हिस्सों को फिर से जोड़ सकते हैं और चीनी शेष प्रमेय सीआरटी का उपयोग कर सकते हैं।

और परिणामस्वरूप आपको सीआरटी से क्या मिलता है ... क्षमा करें, मुझे लगता है कि हमें पहले मॉन्टगोमरी फॉर्म से इसे वापस बदलना होगा। इसलिए, पुनर्संयोजन से पहले, हम ऊपरी भाग को अभिव्यक्ति (c ₀ ') ^d / R mod q में बदलते हैं और अपना मान cd mod q वापस करते हैं। निचले हिस्से में, हम तदनुसार सीडी मॉड पी प्राप्त करते हैं।

अब आप c ^d mod n का मान प्राप्त करने के लिए CRT का उपयोग कर सकते हैं। छोटे फ़ॉन्ट के लिए क्षमा करें, मेरे पास पर्याप्त ब्लैकबोर्ड नहीं है। उसी चीज़ के बारे में जो हम नीचे ₁ के साथ प्राप्त करते हैं, और हम अंत में अपना परिणाम प्राप्त कर सकते हैं, वह है, संदेश m।



इस प्रकार, सर्वर एक आने वाले पैकेट को लेता है जो इसे प्राप्त करता है, इसे इस पूरी पाइपलाइन के माध्यम से चलाता है, इस पाइपलाइन के दो हिस्सों को निष्पादित करता है, और एक डिक्रिप्ट किए गए संदेश के साथ समाप्त होता है cd mod m के बराबर। फिर वह इस पद की गद्दी की गद्दी की जाँच करने जा रहा है। हमारे विशिष्ट हमले के मामले में, हमने इस तरह से बनाया है कि वास्तव में यह जोड़ मेल नहीं खाएगा। हमने उन आंकडों के लिए मूल्य c चुना जो सही पैडिंग जोड़ के साथ वास्तविक संदेश को एन्क्रिप्ट नहीं करते हैं।

इस प्रकार, ऐड-ऑन परीक्षण पास नहीं करता है, सर्वर को एक त्रुटि रिकॉर्ड करने, क्लाइंट को एक त्रुटि संदेश भेजने और डिस्कनेक्ट करने की आवश्यकता होगी। इसलिए, हम इस पाइपलाइन के माध्यम से हमारे संदेश को पारित करने के लिए सर्वर को लगने वाले समय को मापने जा रहे हैं। क्या आपके पास सर्वर द्वारा एक संदेश को संसाधित करने और इन सभी अनुकूलन को संयोजित करने की प्रक्रिया के बारे में कोई प्रश्न हैं?

श्रोता: मेरी राय में, परिमाण c के सूचकांक में त्रुटि है।

प्रोफेसर: हाँ, आप सही हैं, मैं इंडेक्स 0 जोड़ रहा हूँ, यहाँ c ₀ ^d mod q होना चाहिए।



श्रोता: जब आप R mod q से विभाजित होते हैं, तो क्या इस बात के बारे में कोई धारणा नहीं है कि आपको कम बिट्स को शून्य करने के लिए कितना q जोड़ना चाहिए?

प्रोफेसर: हाँ, आप सही हैं, इस अंतिम चरण में (c ₀ ') ^d / R mod q अतिरिक्त कटौती हो सकती है। तो हमें इस विभाजन को R के द्वारा सही तरीके से करना चाहिए, और संभवतया यही करना चाहिए कि जब हम R से विभाजित करते हैं, तो मान को वापस बदलने के लिए, यहाँ मॉन्टगोमेरी की कमी को पूरा करना चाहिए। चूंकि गणनाओं की शुरुआत में यह बिल्कुल स्पष्ट नहीं है कि हमें कितना क्ष जोड़ना चाहिए, हम चयन विधि का उपयोग करते हैं, कम शून्य को नष्ट करते हैं, फिर फिर से मॉड क्ष बनाते हैं, और, संभवतः, एक अतिरिक्त कमी। आप पूरी तरह से सही हैं, इस मामले में यह मॉन्टगोमरी गुणन के प्रत्येक चरण के लिए आर मॉड क्यू द्वारा बिल्कुल समान विभाजन है।

तो आप इसका फायदा कैसे उठाते हैं? किसी हमलावर ने किसी सर्वर की गुप्त कुंजी को उस समय को माप कर कैसे हल किया जा सकता है, जिसे पूरा करने में समय लगता है? इन लोगों के पास एक योजना है जो एक समय में एक निजी कुंजी बिट का अनुमान लगाने पर आधारित है। हम मान सकते हैं कि गुप्त कुंजी एन्क्रिप्टेड घातांक d है, क्योंकि आप ई जानते हैं और n जानते हैं, यह सार्वजनिक कुंजी है। केवल एक चीज जिसे आप नहीं जानते हैं वह है डी।



वास्तव में, इस हमले में, वे सीधे डी के मूल्य का अनुमान नहीं लगाते हैं, क्योंकि यह जटिल है। इसके बजाय, वे q या p पर विचार करते हैं, चाहे वह इन दोनों में से कोई भी मात्रा हो। एक बार जब आप अनुमान लगा लेते हैं कि p या q क्या मायने रखता है, तो आप n = pq की गणना कर सकते हैं। फिर, यदि आप पी और क्यू के मूल्यों को जानते हैं, तो आप उस फ़ंक्शन the की गणना कर सकते हैं जो हमने पहले के बारे में बात की थी। यह आपको ई के मूल्य से डी का मूल्य प्राप्त करने की अनुमति देगा। इस प्रकार, n के मूल्य का यह कारककरण अत्यंत महत्वपूर्ण है, इसे RSA सुरक्षा सुनिश्चित करने के लिए गुप्त रखा जाना चाहिए।

इसलिए वास्तव में, इन लोगों ने इस पाइपलाइन के समय का विश्लेषण करके q मान का अनुमान लगाया। इसके लिए वे क्या कर रहे हैं? वे सावधानीपूर्वक ग के मूल्य के प्रारंभिक मूल्य का चयन करते हैं और सर्वर पाइपलाइन के माध्यम से इसके पारित होने के समय को मापते हैं।

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

तो, मान लीजिए कि आपके पास इस q के मूल्य में बिट्स क्या हैं, इस बारे में धारणा जी है। इस मान को ऐसे बिट्स से मिलकर बनाते हैं: g = g ₀ g ₁ g _{2 2} ... और इसी तरह। बल्कि, यह g भी नहीं है, लेकिन q के वास्तविक बिट्स हैं, इसलिए मुझे इसे इस तरह से फिर से लिखना चाहिए: g = q ₀ q ₁ q ₂ .... हम मानते हैं कि ये q उच्च बिट्स हैं, और हम बिट्स को और कम करने का अनुमान लगा रहे हैं। मान लीजिए हम बिट qj तक q का मान जानते हैं, और फिर सभी शून्य का पालन करते हैं। आपको कुछ पता नहीं है कि बाकी बिट्स क्या हैं।



इन लोगों ने इस अनुमान g को हमारी पाइपलाइन की इस जगह पर इंजेक्ट करने की कोशिश की: (c0 ') d mod q। क्योंकि यह वह जगह है जहां दो प्रकार के अनुकूलन का उपयोग किया जाता है: सामान्य गुणा के बजाय करतसूब विधि और सी ₀ के मूल्य के आधार पर एक अलग संख्या में अतिरिक्त संक्षिप्तीकरण। दरअसल, उन्होंने पाइप लाइन की इस जगह में दो अलग-अलग अनुमान लगाने की कोशिश की: पहला, जो जी = क्यू ₀ क्यू ₁ क्यू ₂ ... क्यूज 000 ... 0000, और दूसरा, जिसे वे जी _हाई कहते हैं, जिसमें समान उच्च बिट्स होते हैं, लेकिन सभी शून्य के अंत में एक उच्च बिट को दर्शाती एक इकाई है, उसके बाद फिर से शून्य:

g = q ₀ q ₁ q ₂ ... qj 100 ... 0000।

यह इन लोगों को यह समझने में कैसे मदद करता है कि क्या हो रहा है? ऐसा करने के दो तरीके हैं। मान लीजिए हमारा अनुमान g मान c ₀ 'के बराबर है। हम मान सकते हैं कि ये जी और जी _उच्च मूल्य के बाईं ओर दिए गए सी ₀ 'के अनुरूप हैं। वास्तव में, ऐसा करना काफी सरल है, क्योंकि c ₀ 'एन्क्रिप्टेड इनपुट वैल्यू c ₀ से पीछे की गणना करना बहुत आसान है, आप इसे R से गुणा करें।



इसलिए, मान (c ₀ ') ^d का अनुमान लगाने के लिए, उन्हें केवल अपना अनुमान, अपना अनुमान g लेना चाहिए, और पहले इसे R से विभाजित करना चाहिए, अर्थात, वहाँ 512 mod से विभाजित करें। फिर वे इसे वापस लाने जा रहे हैं, सर्वर इसे R से गुणा करेगा और हमारी पाइपलाइन योजना में वर्णित प्रक्रिया को जारी रखेगा।

तो, मान लें कि हम अपने विशेष रूप से चयनित पूर्णांक मान को सही जगह पर रखने में सक्षम थे। तो, मॉड क्यू के लिए अभिकलन समय c ₀ 'क्या होगा?



दो संभावित विकल्प हैं जहां q इस तस्वीर में फिट बैठता है। यह हो सकता है कि q, g और g _{उच्च के} इन दो मूल्यों के बीच है, क्योंकि q का अगला भाग 0. है। इस प्रकार, यह मान - qj के बाद पहला 0 - q से कम होगा, लेकिन यह मान - q के बाद 1 - से अधिक होगा क्यू। ऐसा तब होता है जब q का अगला बिट 0 होता है, या यह संभव है कि q इन दोनों मानों से ऊपर है यदि q का अगला बिट 1 है।



अब हम कह सकते हैं कि इन दोनों मानों का डिक्रिप्शन समय क्या होगा यदि q उनके बीच स्थित है, या यदि q दोनों के ऊपर स्थित है।

आइए उस स्थिति को देखें जहां q ऊपर स्थित है। इस मामले में, सब कुछ बहुत अधिक समान है। चूँकि ये दोनों मान q से कम हैं, इसलिए mod q में इन चीजों का मूल्य लगभग समान होगा। वे इस अतिरिक्त बिट के कारण थोड़ा अलग हैं, लेकिन अभी भी कमोबेश उसी आकार के हैं। और अतिरिक्त कटौती, अतिरिक्त कमी की संख्या भी, शायद बहुत भिन्न नहीं होगी, क्योंकि यह c0 'mod q के मान के समानुपाती है। और छ और छ _उच्च मान दोनों के लिए क्ष से कम है, वे सभी एक ही हैं। उनमें से कोई भी क्यू से अधिक नहीं होगा और बड़ी संख्या में अतिरिक्त कटौती का कारण नहीं होगा, क्योंकि इन दोनों अनुमानों से अधिक क्यू के लिए, सामान्य गणनाओं की संख्या के संबंध में करतसुबा विधि द्वारा गणना की संख्या समान रहेगी। इस संबंध के संदर्भ में, सर्वर जी और जी दोनों को समान रूप से संभाल लेगा। इसलिए, सर्वर इन दोनों मानों के लिए एक ही राशि के अतिरिक्त संक्षिप्ताक्षर बनाने वाला है। इस प्रकार, यदि आप देखते हैं कि सर्वर इन अनुमानों का जवाब देने में एक ही समय खर्च कर रहा है, तो आपको शायद यह मान लेना चाहिए कि इस बिंदु पर जी _उच्च मूल्य में वास्तव में 1 है।



दूसरी ओर, यदि q इन दो मूल्यों के बीच स्थित है, तो दो संभावित चीजें हैं जो स्विचिंग और समय परिवर्तन का कारण बन सकती हैं। चीजों में से एक यह है कि चूंकि जी _उच्च q से थोड़ा बड़ा है, अतिरिक्त कटौती की संख्या c ₀ 'mod q के समानुपाती होगी, जो कि बहुत छोटी है क्योंकि c ₀ ' q प्लस 100 के इस अतिरिक्त बिट अनुक्रम में कुछ बिट्स हैं ... 00। इस प्रकार, अतिरिक्त कटौती की संख्या अधिक ध्यान देने योग्य होगी और सब कुछ तेजी से होने लगेगा।
, , , , , : «, !». , g c ₀ ' , q, , g _high q, g _high mod q . , . – , , .

c ₀ ' mod q. c ₀ g _high , q, , g q. , . , , . , 32- , .

, 32- , , , . , . 32 , , - . , , 32, , , , .

, , , . , q 1, , q 0, , g _high q , , .

. , . , . , , 1-2 . , , Ethernet.
, . . , 7 . , , -, , ?

: ?

: , , , , , . , .

, , 7 , , 7 . 7 g, 7 g + 1, g + 2 7 g + 400. g, g, , 7 400, ?



: , , ?

: , , , — (c ₀ ') ^d . . , , , mod p. , , . , g, 1, 2, 3, , .

, , – 100…00. , mod p, , mod p . « », , (c ₀ ') ^d , . ?

: , ?

: - , q. , q, , , .

: c ₀ '?

: c ₀ ', c, c ₀ ' R mod n.



, «» , c ₀ = mod q, c ₀ = ((c ₀ ' R ^-1 ) mod n) mod q. R, R. c ₀ ', (c ₀ ') ^d mod q. , , , , R. , R = 2 ⁵¹² . , .

: mod p ?

: , , ? , ! , .


.

हमारे साथ बने रहने के लिए धन्यवाद। क्या आप हमारे लेख पसंद करते हैं? अधिक दिलचस्प सामग्री देखना चाहते हैं? एक आदेश रखकर या अपने दोस्तों को इसकी अनुशंसा करके हमें समर्थन दें, एंट्री-लेवल सर्वरों के अनूठे एनालॉग पर हैबर उपयोगकर्ताओं के लिए 30% छूट जो हमने आपके लिए ईजाद की है: VPS (KVM) E5-2650 v4 (6 कोर) 10GB DDR4 240GB SSD 1Gbps से पूरा सच $ 20 या सर्वर को कैसे विभाजित करें? (विकल्प RAID1 और RAID10 के साथ उपलब्ध हैं, 24 कोर तक और 40GB DDR4 तक)।

VPS (KVM) E5-2650 v4 (6 Cores) 10GB DDR4 240GB SSD 1Gbps , .

डेल R730xd 2 बार सस्ता? केवल हमारे पास 2 x Intel Dodeca-Core Xeon E5-2650v4 128GB DDR4 6x480GB SSD 1Gbps 100 टीवी 249 डॉलर में नीदरलैंड और यूएसए से है! इन्फ्रास्ट्रक्चर Bldg का निर्माण कैसे करें के बारे में पढ़ें । एक पैसा के लिए 9,000 यूरो की लागत डेल R730xd E5-2650 v4 सर्वर का उपयोग कर वर्ग?