संघट्टन प्रतिरोध: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 4 users not shown)
Line 2: Line 2:
[[क्रिप्टोग्राफी]] में, '''कोलीजन रेजिस्टेंस''' [[क्रिप्टोग्राफ़िक हैश फ़ंक्शंस]] की प्रॉपर्टी है: एक हैश फ़ंक्शन एच कोलीजन-रेजिस्टेंस है यदि एक ही आउटपुट के लिए हैश वाले दो इनपुट ढूंढना कठिन है; यानी, दो इनपुट ए और बी जहां ए ≠ बी लेकिन एच(ए) = एच(बी)। <ref name=GoldwasserBellare>[[Shafi Goldwasser|Goldwasser, S.]] and [[Mihir Bellare|Bellare, M.]] [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"]. Summer course on cryptography, MIT, 1996-2001</ref>{{rp|136}} पिजनहोल प्रिंसिपल का अर्थ है कि आउटपुट से अधिक इनपुट वाले किसी भी हैश फ़ंक्शन में आवश्यक रूप से ऐसी कोलीजन होंगी; <ref name=GoldwasserBellare />{{rp|136}} उन्हें ढूंढना जितना कठिन होगा, हैश फ़ंक्शन उतना ही अधिक क्रिप्टोग्राफ़िक रूप से सुरक्षित होगा।
[[क्रिप्टोग्राफी]] में, '''कोलीजन रेजिस्टेंस''' [[क्रिप्टोग्राफ़िक हैश फ़ंक्शंस]] की प्रॉपर्टी है: एक हैश फ़ंक्शन एच कोलीजन-रेजिस्टेंस है यदि एक ही आउटपुट के लिए हैश वाले दो इनपुट ढूंढना कठिन है; यानी, दो इनपुट ए और बी जहां ए ≠ बी लेकिन एच(ए) = एच(बी)। <ref name=GoldwasserBellare>[[Shafi Goldwasser|Goldwasser, S.]] and [[Mihir Bellare|Bellare, M.]] [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"]. Summer course on cryptography, MIT, 1996-2001</ref>{{rp|136}} पिजनहोल प्रिंसिपल का अर्थ है कि आउटपुट से अधिक इनपुट वाले किसी भी हैश फ़ंक्शन में आवश्यक रूप से ऐसी कोलीजन होंगी; <ref name=GoldwasserBellare />{{rp|136}} उन्हें ढूंढना जितना कठिन होगा, हैश फ़ंक्शन उतना ही अधिक क्रिप्टोग्राफ़िक रूप से सुरक्षित होगा।


[[जन्मदिन विरोधाभास|बर्थडे पैराडॉक्स]] कोलीजन रेजिस्टेंस पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक अटैकर जो केवल 2<sup>''N''/2</sup> (या <math>\scriptstyle \sqrt{ 2^N}</math>) की गणना करता है '''रैंडम इनपुट पर हैश संचा'''लन से दो मैचिंग आउटपुट मिलने की संभावना है। यदि जानवर-बल के हमले की तुलना में ऐसा करने का कोई आसान तरीका है, तो इसे आमतौर पर हैश फ़ंक्शन में दोष माना जाता है।<ref name=Lecture21Collision>Pass, R. [https://www.cs.cornell.edu/courses/cs6830/2009fa/scribes/lecture21.pdf "Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme"]. Course on Cryptography, Cornell University, 2009</ref>
[[जन्मदिन विरोधाभास|बर्थडे पैराडॉक्स]] कोलीजन रेजिस्टेंस पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक अटैकर जो केवल 2<sup>''N''/2</sup> (या <math>\scriptstyle \sqrt{ 2^N}</math>) की गणना करता है और रैंडम इनपुट पर हैश ऑपरेशन से दो मैचिंग आउटपुट मिलने की संभावना है। यदि ब्रूट-फ़ोर्स अटैक की तुलना में ऐसा करने का कोई आसान तरीका है, तो इसे सामान्यतः हैश फ़ंक्शन में दोष माना जाता है। <ref name=Lecture21Collision>Pass, R. [https://www.cs.cornell.edu/courses/cs6830/2009fa/scribes/lecture21.pdf "Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme"]. Course on Cryptography, Cornell University, 2009</ref>
[[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] आमतौर पर कोलीजन रेजिस्टेंस होने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई हैश फ़ंक्शन जिन्हें कभी कोलीजन रेजिस्टेंस माना जाता था, बाद में टूट गए। विशेष रूप से [[MD5]] और [[SHA-1]] दोनों ने कोलीजन का पता लगाने के लिए पाशविक बल की तुलना में अधिक कुशल तकनीकें प्रकाशित की हैं।<ref>{{Cite web|url=http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf|title=How to Break MD5 and Other Hash Functions|author1=Xiaoyun Wang|author2=Hongbo Yu|accessdate=2009-12-21|archive-url=https://web.archive.org/web/20090521024709/http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf|archive-date=2009-05-21|url-status=dead}}</ref><ref>{{cite conference |author1=Xiaoyun Wang |author2=Yiqun Lisa Yin|author2-link= Yiqun Lisa Yin |author3=Hongobo Yu |title=पूर्ण SHA-1 में टकराव ढूँढना|url=http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf |conference=CRYPTO 2005 |doi=10.1007/11535218_2}}</ref> हालाँकि, कुछ हैश फ़ंक्शंस में इस बात का प्रमाण है कि कोलीजन ढूंढना कम से कम किसी कठिन गणितीय समस्या (जैसे [[पूर्णांक गुणनखंडन]] या [[असतत लघुगणक]]) जितना कठिन है। उन फ़ंक्शंस को [[प्रमाणित रूप से सुरक्षित क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] कहा जाता है।<ref name=Lecture21Collision />
 
[[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] सामान्यतः कोलीजन रेजिस्टेंस होने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई हैश फ़ंक्शन जिन्हें कभी कोलीजन रेजिस्टेंस माना जाता था, बाद में टूट गए। विशेष रूप से [[MD5|एमडी5]] और [[SHA-1|एसएचए-1]] दोनों ने कोलीजन का पता लगाने के लिए ब्रूट-फ़ोर्स की तुलना में अधिक कुशल तकनीकें पब्लिश की हैं। <ref>{{Cite web|url=http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf|title=How to Break MD5 and Other Hash Functions|author1=Xiaoyun Wang|author2=Hongbo Yu|accessdate=2009-12-21|archive-url=https://web.archive.org/web/20090521024709/http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf|archive-date=2009-05-21|url-status=dead}}</ref><ref>{{cite conference |author1=Xiaoyun Wang |author2=Yiqun Lisa Yin|author2-link= Yiqun Lisa Yin |author3=Hongobo Yu |title=पूर्ण SHA-1 में टकराव ढूँढना|url=http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf |conference=CRYPTO 2005 |doi=10.1007/11535218_2}}</ref> हालाँकि, कुछ हैश फ़ंक्शंस में इस बात का प्रूफ है कि कोलीजन ढूंढना कम से कम किसी कठिन गणितीय प्रॉब्लम (जैसे [[पूर्णांक गुणनखंडन|इन्टिजर फेक्टराइज़ेशन]] या [[असतत लघुगणक|डिस्क्रीट लोगारिथ्म]]) जितना कठिन है। उन फ़ंक्शंस को [[प्रमाणित रूप से सुरक्षित क्रिप्टोग्राफ़िक हैश फ़ंक्शन|प्रूवेबली सिक्योर]] कहा जाता है। <ref name="Lecture21Collision" />
 




==परिभाषा==
==परिभाषा==
कार्यों का एक परिवार {h<sub>''k''</sub> : {0, 1}<sup>एम(के)</sup> → {0, 1}<sup>l(k)</sup>} कुछ एल्गोरिदम द्वारा उत्पन्न G कोलीजन-रेजिस्टेंस हैश फ़ंक्शंस का एक परिवार है, यदि |m(k)| > |एल(के)| किसी भी k के लिए, अर्थात, h<sub>''k''</sub> इनपुट स्ट्रिंग को संपीड़ित करता है, और प्रत्येक h<sub>''k''</sub> k दिए गए बहुपद समय के भीतर गणना की जा सकती है, लेकिन किसी भी संभाव्य बहुपद एल्गोरिथ्म ए के लिए, हमारे पास है
फंक्शन {''h<sub>k</sub>'' : {0, 1}<sup>''m''(''k'')</sup> → {0, 1}<sup>''l''(''k'')</sup>} का समूह कुछ एल्गोरिदम द्वारा उत्पन्न G कोलीजन-रेजिस्टेंस हैश फ़ंक्शंस का एक समूह है, यदि |''m''(''k'')| > |''l''(''k'')| किसी भी k के लिए, अर्थात, h<sub>''k''</sub> इनपुट स्ट्रिंग को संपीड़ित करता है, और प्रत्येक h<sub>''k''</sub> k दिए गए पोलीनोमिअल टाइम के भीतर गणना की जा सकती है, लेकिन किसी भी प्रोबबिलिस्टिक पोलीनोमिअल एल्गोरिथ्म ए के लिए, हमारे पास निम्न हैं


: पीआर [के ← जी(1<sup>n</sup>), (x<sub>1</sub>, एक्स<sub>2</sub>) ← ए(के, 1<sup>n</sup>) एस.टी. एक्स<sub>1</sub> ≠ एक्स<sub>2</sub> लेकिन एच<sub>''k''</sub>(एक्स<sub>1</sub>) = एच<sub>''k''</sub>(एक्स<sub>2</sub>)] < उपेक्षा(n),
: Pr [''k'' ← ''G''(1<sup>''n''</sup>), (''x''<sub>1</sub>, ''x''<sub>2</sub>) ← ''A''(''k'', 1<sup>''n''</sup>) s.t. ''x''<sub>1</sub> ≠ ''x''<sub>2</sub> but ''h<sub>k</sub>''(''x''<sub>1</sub>) = ''h<sub>k</sub>''(''x''<sub>2</sub>)] < negl(''n''),


जहां negl(·) कुछ नगण्य फ़ंक्शन को दर्शाता है, और n सुरक्षा पैरामीटर है।<ref>{{cite web|last1=Dodis|first1=Yevgeniy|title=Lecture 12 of Introduction to Cryptography|url=http://cs.nyu.edu/courses/fall08/G22.3210-001/lect/lecture12.pdf|accessdate=3 January 2016}}, def 1.</ref>
जहां negl(·) कुछ नेग्लिजिबल फ़ंक्शन को दर्शाता है, और n सिक्योरिटी पैरामीटर है। <ref>{{cite web|last1=Dodis|first1=Yevgeniy|title=Lecture 12 of Introduction to Cryptography|url=http://cs.nyu.edu/courses/fall08/G22.3210-001/lect/lecture12.pdf|accessdate=3 January 2016}}, def 1.</ref>




==तर्क==
==रैशनल==
कोलीजन रेजिस्टेंस कई कारणों से वांछनीय है।
कोलीजन रेजिस्टेंस कई कारणों से डिज़ायरेबल है।
* कुछ डिजिटल हस्ताक्षर प्रणालियों में, एक पक्ष दस्तावेज़ के हैश पर [[सार्वजनिक कुंजी]] हस्ताक्षर प्रकाशित करके दस्तावेज़ को प्रमाणित करता है। यदि एक ही हैश के साथ दो दस्तावेज़ तैयार करना संभव है, तो एक हमलावर एक पक्ष से एक को प्रमाणित करवा सकता है, और फिर दावा कर सकता है कि पार्टी ने दूसरे को प्रमाणित कर दिया है।
* कुछ डिजिटल सिग्नेचर सिस्टम में, एक पार्टी डॉक्यूमेंट के हैश पर [[सार्वजनिक कुंजी|पब्लिक की]] सिग्नेचर पब्लिश करके डॉक्यूमेंट को अटेस्ट करता है। यदि एक ही हैश के साथ दो डॉक्यूमेंट तैयार करना संभव है, तो एक अटैकर एक पार्टी से एक को अटेस्ट करवा सकता है, और फिर दावा कर सकता है कि पार्टी ने दूसरे को अटेस्ट कर दिया है।
* कुछ वितरित सामग्री प्रणालियों में, पार्टियां यह सुनिश्चित करने के लिए फ़ाइलों के क्रिप्टोग्राफ़िक हैश की तुलना करती हैं कि उनका संस्करण समान है। एक हमलावर जो एक ही हैश के साथ दो फ़ाइलें तैयार कर सकता है, उपयोगकर्ताओं को यह विश्वास दिला सकता है कि उनके पास फ़ाइल का एक ही संस्करण है जबकि वास्तव में ऐसा नहीं था।
* कुछ डिस्ट्रिब्यूटेड कंटेंट सिस्टम में, पार्टियां यह सुनिश्चित करने के लिए फ़ाइलों के क्रिप्टोग्राफ़िक हैश को कमपेअर करती हैं कि उनका वर्ज़न समान है। अटैकर जो एक ही हैश के साथ दो फ़ाइलें तैयार कर सकता है, यूजर को यह भरोसा दिला सकता है कि उनके पास फ़ाइल का एक ही वर्ज़न है जबकि वास्तव में ऐसा नहीं था।


==यह भी देखें==
==यह भी देखें==
* [[टकराव का हमला|कोलीजन का हमला]]
* [[टकराव का हमला|कोलीजन अटैक]]
* [[प्रीइमेज हमला]]
* [[प्रीइमेज हमला|प्रीइमेज अटैक]]
* [[एनआईएसटी हैश फ़ंक्शन प्रतियोगिता]]
* [[एनआईएसटी हैश फ़ंक्शन प्रतियोगिता|एनआईएसटी हैश फ़ंक्शन कॉम्पटीशन]]
* सिद्ध रूप से सुरक्षित क्रिप्टोग्राफ़िक हैश फ़ंक्शन
* प्रूवेबली सिक्योर क्रिप्टोग्राफ़िक हैश फ़ंक्शन
*[[त्रुटि का पता लगाना और सुधार करना]]
*[[त्रुटि का पता लगाना और सुधार करना|एरर डिटेक्शन एंड करेक्शन]]


==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}


{{DEFAULTSORT:Collision Resistance}}[[Category: सममित-कुंजी क्रिप्टोग्राफी]] [[Category: क्रिप्टोग्राफी का सिद्धांत]]
{{DEFAULTSORT:Collision Resistance}}
 
 


[[Category: Machine Translated Page]]
[[Category:Created On 26/07/2023|Collision Resistance]]
[[Category:Created On 26/07/2023]]
[[Category:Lua-based templates|Collision Resistance]]
[[Category:Machine Translated Page|Collision Resistance]]
[[Category:Pages with script errors|Collision Resistance]]
[[Category:Short description with empty Wikidata description|Collision Resistance]]
[[Category:Templates Vigyan Ready|Collision Resistance]]
[[Category:Templates that add a tracking category|Collision Resistance]]
[[Category:Templates that generate short descriptions|Collision Resistance]]
[[Category:Templates using TemplateData|Collision Resistance]]
[[Category:क्रिप्टोग्राफी का सिद्धांत|Collision Resistance]]
[[Category:सममित-कुंजी क्रिप्टोग्राफी|Collision Resistance]]

Latest revision as of 12:06, 10 August 2023

क्रिप्टोग्राफी में, कोलीजन रेजिस्टेंस क्रिप्टोग्राफ़िक हैश फ़ंक्शंस की प्रॉपर्टी है: एक हैश फ़ंक्शन एच कोलीजन-रेजिस्टेंस है यदि एक ही आउटपुट के लिए हैश वाले दो इनपुट ढूंढना कठिन है; यानी, दो इनपुट ए और बी जहां ए ≠ बी लेकिन एच(ए) = एच(बी)। [1]: 136  पिजनहोल प्रिंसिपल का अर्थ है कि आउटपुट से अधिक इनपुट वाले किसी भी हैश फ़ंक्शन में आवश्यक रूप से ऐसी कोलीजन होंगी; [1]: 136  उन्हें ढूंढना जितना कठिन होगा, हैश फ़ंक्शन उतना ही अधिक क्रिप्टोग्राफ़िक रूप से सुरक्षित होगा।

बर्थडे पैराडॉक्स कोलीजन रेजिस्टेंस पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक अटैकर जो केवल 2N/2 (या ) की गणना करता है और रैंडम इनपुट पर हैश ऑपरेशन से दो मैचिंग आउटपुट मिलने की संभावना है। यदि ब्रूट-फ़ोर्स अटैक की तुलना में ऐसा करने का कोई आसान तरीका है, तो इसे सामान्यतः हैश फ़ंक्शन में दोष माना जाता है। [2]

क्रिप्टोग्राफ़िक हैश फ़ंक्शन सामान्यतः कोलीजन रेजिस्टेंस होने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई हैश फ़ंक्शन जिन्हें कभी कोलीजन रेजिस्टेंस माना जाता था, बाद में टूट गए। विशेष रूप से एमडी5 और एसएचए-1 दोनों ने कोलीजन का पता लगाने के लिए ब्रूट-फ़ोर्स की तुलना में अधिक कुशल तकनीकें पब्लिश की हैं। [3][4] हालाँकि, कुछ हैश फ़ंक्शंस में इस बात का प्रूफ है कि कोलीजन ढूंढना कम से कम किसी कठिन गणितीय प्रॉब्लम (जैसे इन्टिजर फेक्टराइज़ेशन या डिस्क्रीट लोगारिथ्म) जितना कठिन है। उन फ़ंक्शंस को प्रूवेबली सिक्योर कहा जाता है। [2]


परिभाषा

फंक्शन {hk : {0, 1}m(k) → {0, 1}l(k)} का समूह कुछ एल्गोरिदम द्वारा उत्पन्न G कोलीजन-रेजिस्टेंस हैश फ़ंक्शंस का एक समूह है, यदि |m(k)| > |l(k)| किसी भी k के लिए, अर्थात, hk इनपुट स्ट्रिंग को संपीड़ित करता है, और प्रत्येक hk k दिए गए पोलीनोमिअल टाइम के भीतर गणना की जा सकती है, लेकिन किसी भी प्रोबबिलिस्टिक पोलीनोमिअल एल्गोरिथ्म ए के लिए, हमारे पास निम्न हैं

Pr [k ← G(1n), (x1, x2) ← A(k, 1n) s.t. x1 ≠ x2 but hk(x1) = hk(x2)] < negl(n),

जहां negl(·) कुछ नेग्लिजिबल फ़ंक्शन को दर्शाता है, और n सिक्योरिटी पैरामीटर है। [5]


रैशनल

कोलीजन रेजिस्टेंस कई कारणों से डिज़ायरेबल है।

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

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001
  2. ↑ 2.0 2.1 Pass, R. "Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme". Course on Cryptography, Cornell University, 2009
  3. ↑ Xiaoyun Wang; Hongbo Yu. "How to Break MD5 and Other Hash Functions" (PDF). Archived from the original (PDF) on 2009-05-21. Retrieved 2009-12-21.
  4. ↑ Xiaoyun Wang; Yiqun Lisa Yin; Hongobo Yu. पूर्ण SHA-1 में टकराव ढूँढना (PDF). CRYPTO 2005. doi:10.1007/11535218_2.
  5. ↑ Dodis, Yevgeniy. "Lecture 12 of Introduction to Cryptography" (PDF). Retrieved 3 January 2016., def 1.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=संघट्टन_प्रतिरोध&oldid=241723’