संघट्टन प्रतिरोध: Difference between revisions
From Vigyanwiki
No edit summary |
(text) |
||
| 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>) की गणना करता है | [[जन्मदिन विरोधाभास|बर्थडे पैराडॉक्स]] कोलीजन रेजिस्टेंस पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक अटैकर जो केवल 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|एमडी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>''m''(''k'')</sup> → {0, 1}<sup>''l''(''k'')</sup>} का समूह कुछ एल्गोरिदम द्वारा उत्पन्न G कोलीजन-रेजिस्टेंस हैश फ़ंक्शंस का एक समूह है, यदि |''m''(''k'')| > |''l''(''k'')| किसी भी k के लिए, अर्थात, h<sub>''k''</sub> इनपुट स्ट्रिंग को संपीड़ित करता है, और प्रत्येक h<sub>''k''</sub> k दिए गए पोलीनोमिअल टाइम के भीतर गणना की जा सकती है, लेकिन किसी भी प्रोबबिलिस्टिक पोलीनोमिअल एल्गोरिथ्म ए के लिए, हमारे पास निम्न हैं | |||
: 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''), | : 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(·) कुछ | जहां 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> | ||
== | ==रैशनल== | ||
कोलीजन रेजिस्टेंस कई कारणों से | कोलीजन रेजिस्टेंस कई कारणों से डिज़ायरेबल है। | ||
* कुछ डिजिटल | * कुछ डिजिटल सिग्नेचर सिस्टम में, एक पार्टी डॉक्यूमेंट के हैश पर [[सार्वजनिक कुंजी|पब्लिक की]] सिग्नेचर पब्लिश करके डॉक्यूमेंट को अटेस्ट करता है। यदि एक ही हैश के साथ दो डॉक्यूमेंट तैयार करना संभव है, तो एक अटैकर एक पार्टी से एक को अटेस्ट करवा सकता है, और फिर दावा कर सकता है कि पार्टी ने दूसरे को अटेस्ट कर दिया है। | ||
* कुछ | * कुछ डिस्ट्रिब्यूटेड कंटेंट सिस्टम में, पार्टियां यह सुनिश्चित करने के लिए फ़ाइलों के क्रिप्टोग्राफ़िक हैश को कमपेअर करती हैं कि उनका वर्ज़न समान है। अटैकर जो एक ही हैश के साथ दो फ़ाइलें तैयार कर सकता है, यूजर को यह भरोसा दिला सकता है कि उनके पास फ़ाइल का एक ही वर्ज़न है जबकि वास्तव में ऐसा नहीं था। | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[टकराव का हमला|कोलीजन | * [[टकराव का हमला|कोलीजन अटैक]] | ||
* [[प्रीइमेज हमला]] | * [[प्रीइमेज हमला|प्रीइमेज अटैक]] | ||
* [[एनआईएसटी हैश फ़ंक्शन प्रतियोगिता]] | * [[एनआईएसटी हैश फ़ंक्शन प्रतियोगिता|एनआईएसटी हैश फ़ंक्शन कॉम्पटीशन]] | ||
* | * प्रूवेबली सिक्योर क्रिप्टोग्राफ़िक हैश फ़ंक्शन | ||
*[[त्रुटि का पता लगाना और सुधार करना]] | *[[त्रुटि का पता लगाना और सुधार करना|एरर डिटेक्शन एंड करेक्शन]] | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 18:48, 6 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.0 1.1 Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001
- ↑ 2.0 2.1 Pass, R. "Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme". Course on Cryptography, Cornell University, 2009
- ↑ 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.
- ↑ Xiaoyun Wang; Yiqun Lisa Yin; Hongobo Yu. पूर्ण SHA-1 में टकराव ढूँढना (PDF). CRYPTO 2005. doi:10.1007/11535218_2.
- ↑ Dodis, Yevgeniy. "Lecture 12 of Introduction to Cryptography" (PDF). Retrieved 3 January 2016., def 1.
