संघट्टन प्रतिरोध: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Property of cryptographic hash functions}} {{Refimprove|date=December 2009}} क्रिप्टोग्राफी में, टकराव प...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Property of cryptographic hash functions}} | {{Short description|Property of cryptographic hash functions}} | ||
[[क्रिप्टोग्राफी]] में, '''कोलीजन रेजिस्टेंस''' [[क्रिप्टोग्राफ़िक हैश फ़ंक्शंस]] की प्रॉपर्टी है: एक हैश फ़ंक्शन एच कोलीजन-रेजिस्टेंस है यदि एक ही आउटपुट के लिए हैश वाले दो इनपुट ढूंढना कठिन है; यानी, दो इनपुट ए और बी जहां ए ≠ बी लेकिन एच(ए) = एच(बी)। <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> | ||
[[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] आमतौर पर | [[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] आमतौर पर कोलीजन रेजिस्टेंस होने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई हैश फ़ंक्शन जिन्हें कभी कोलीजन रेजिस्टेंस माना जाता था, बाद में टूट गए। विशेष रूप से [[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 /> | ||
==परिभाषा== | ==परिभाषा== | ||
कार्यों का एक परिवार {h<sub>''k''</sub> : {0, 1}<sup>एम(के)</sup> → {0, 1}<sup>l(k)</sup>} कुछ एल्गोरिदम द्वारा उत्पन्न G | कार्यों का एक परिवार {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 दिए गए बहुपद समय के भीतर गणना की जा सकती है, लेकिन किसी भी संभाव्य बहुपद एल्गोरिथ्म ए के लिए, हमारे पास है | ||
: पीआर [के ← जी(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), | : पीआर [के ← जी(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), | ||
| Line 16: | Line 15: | ||
==तर्क== | ==तर्क== | ||
कोलीजन रेजिस्टेंस कई कारणों से वांछनीय है। | |||
* कुछ डिजिटल हस्ताक्षर प्रणालियों में, एक पक्ष दस्तावेज़ के हैश पर [[सार्वजनिक कुंजी]] हस्ताक्षर प्रकाशित करके दस्तावेज़ को प्रमाणित करता है। यदि एक ही हैश के साथ दो दस्तावेज़ तैयार करना संभव है, तो एक हमलावर एक पक्ष से एक को प्रमाणित करवा सकता है, और फिर दावा कर सकता है कि पार्टी ने दूसरे को प्रमाणित कर दिया है। | * कुछ डिजिटल हस्ताक्षर प्रणालियों में, एक पक्ष दस्तावेज़ के हैश पर [[सार्वजनिक कुंजी]] हस्ताक्षर प्रकाशित करके दस्तावेज़ को प्रमाणित करता है। यदि एक ही हैश के साथ दो दस्तावेज़ तैयार करना संभव है, तो एक हमलावर एक पक्ष से एक को प्रमाणित करवा सकता है, और फिर दावा कर सकता है कि पार्टी ने दूसरे को प्रमाणित कर दिया है। | ||
* कुछ वितरित सामग्री प्रणालियों में, पार्टियां यह सुनिश्चित करने के लिए फ़ाइलों के क्रिप्टोग्राफ़िक हैश की तुलना करती हैं कि उनका संस्करण समान है। एक हमलावर जो एक ही हैश के साथ दो फ़ाइलें तैयार कर सकता है, उपयोगकर्ताओं को यह विश्वास दिला सकता है कि उनके पास फ़ाइल का एक ही संस्करण है जबकि वास्तव में ऐसा नहीं था। | * कुछ वितरित सामग्री प्रणालियों में, पार्टियां यह सुनिश्चित करने के लिए फ़ाइलों के क्रिप्टोग्राफ़िक हैश की तुलना करती हैं कि उनका संस्करण समान है। एक हमलावर जो एक ही हैश के साथ दो फ़ाइलें तैयार कर सकता है, उपयोगकर्ताओं को यह विश्वास दिला सकता है कि उनके पास फ़ाइल का एक ही संस्करण है जबकि वास्तव में ऐसा नहीं था। | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[टकराव का हमला]] | * [[टकराव का हमला|कोलीजन का हमला]] | ||
* [[प्रीइमेज हमला]] | * [[प्रीइमेज हमला]] | ||
* [[एनआईएसटी हैश फ़ंक्शन प्रतियोगिता]] | * [[एनआईएसटी हैश फ़ंक्शन प्रतियोगिता]] | ||
Revision as of 11:37, 5 August 2023
क्रिप्टोग्राफी में, कोलीजन रेजिस्टेंस क्रिप्टोग्राफ़िक हैश फ़ंक्शंस की प्रॉपर्टी है: एक हैश फ़ंक्शन एच कोलीजन-रेजिस्टेंस है यदि एक ही आउटपुट के लिए हैश वाले दो इनपुट ढूंढना कठिन है; यानी, दो इनपुट ए और बी जहां ए ≠ बी लेकिन एच(ए) = एच(बी)। [1]: 136 पिजनहोल प्रिंसिपल का अर्थ है कि आउटपुट से अधिक इनपुट वाले किसी भी हैश फ़ंक्शन में आवश्यक रूप से ऐसी कोलीजन होंगी; [1]: 136 उन्हें ढूंढना जितना कठिन होगा, हैश फ़ंक्शन उतना ही अधिक क्रिप्टोग्राफ़िक रूप से सुरक्षित होगा।
बर्थडे पैराडॉक्स कोलीजन रेजिस्टेंस पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक अटैकर जो केवल 2N/2 (या ) की गणना करता है रैंडम इनपुट पर हैश संचालन से दो मैचिंग आउटपुट मिलने की संभावना है। यदि जानवर-बल के हमले की तुलना में ऐसा करने का कोई आसान तरीका है, तो इसे आमतौर पर हैश फ़ंक्शन में दोष माना जाता है।[2] क्रिप्टोग्राफ़िक हैश फ़ंक्शन आमतौर पर कोलीजन रेजिस्टेंस होने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई हैश फ़ंक्शन जिन्हें कभी कोलीजन रेजिस्टेंस माना जाता था, बाद में टूट गए। विशेष रूप से MD5 और SHA-1 दोनों ने कोलीजन का पता लगाने के लिए पाशविक बल की तुलना में अधिक कुशल तकनीकें प्रकाशित की हैं।[3][4] हालाँकि, कुछ हैश फ़ंक्शंस में इस बात का प्रमाण है कि कोलीजन ढूंढना कम से कम किसी कठिन गणितीय समस्या (जैसे पूर्णांक गुणनखंडन या असतत लघुगणक) जितना कठिन है। उन फ़ंक्शंस को प्रमाणित रूप से सुरक्षित क्रिप्टोग्राफ़िक हैश फ़ंक्शन कहा जाता है।[2]
परिभाषा
कार्यों का एक परिवार {hk : {0, 1}एम(के) → {0, 1}l(k)} कुछ एल्गोरिदम द्वारा उत्पन्न G कोलीजन-रेजिस्टेंस हैश फ़ंक्शंस का एक परिवार है, यदि |m(k)| > |एल(के)| किसी भी k के लिए, अर्थात, hk इनपुट स्ट्रिंग को संपीड़ित करता है, और प्रत्येक hk k दिए गए बहुपद समय के भीतर गणना की जा सकती है, लेकिन किसी भी संभाव्य बहुपद एल्गोरिथ्म ए के लिए, हमारे पास है
- पीआर [के ← जी(1n), (x1, एक्स2) ← ए(के, 1n) एस.टी. एक्स1 ≠ एक्स2 लेकिन एचk(एक्स1) = एचk(एक्स2)] < उपेक्षा(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.
