संघट्टन प्रतिरोध

From Vigyanwiki

क्रिप्टोग्राफी में, कोलीजन रेजिस्टेंस क्रिप्टोग्राफ़िक हैश फ़ंक्शंस की प्रॉपर्टी है: एक हैश फ़ंक्शन एच कोलीजन-रेजिस्टेंस है यदि एक ही आउटपुट के लिए हैश वाले दो इनपुट ढूंढना कठिन है; यानी, दो इनपुट ए और बी जहां ए ≠ बी लेकिन एच(ए) = एच(बी)। [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 [kG(1n), (x1, x2) ← A(k, 1n) s.t. x1x2 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.