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

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

बर्थडे पैराडॉक्स कोलीजन रेजिस्टेंस पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक अटैकर जो केवल 2^N/2 (या $\scriptstyle {\sqrt {2^{N}}}$) की गणना करता है रैंडम इनपुट पर हैश संचालन से दो मैचिंग आउटपुट मिलने की संभावना है। यदि जानवर-बल के हमले की तुलना में ऐसा करने का कोई आसान तरीका है, तो इसे आमतौर पर हैश फ़ंक्शन में दोष माना जाता है। क्रिप्टोग्राफ़िक हैश फ़ंक्शन आमतौर पर कोलीजन रेजिस्टेंस होने के लिए डिज़ाइन किए गए हैं। हालाँकि, कई हैश फ़ंक्शन जिन्हें कभी कोलीजन रेजिस्टेंस माना जाता था, बाद में टूट गए। विशेष रूप से MD5 और SHA-1 दोनों ने कोलीजन का पता लगाने के लिए पाशविक बल की तुलना में अधिक कुशल तकनीकें प्रकाशित की हैं। हालाँकि, कुछ हैश फ़ंक्शंस में इस बात का प्रमाण है कि कोलीजन ढूंढना कम से कम किसी कठिन गणितीय समस्या (जैसे पूर्णांक गुणनखंडन या असतत लघुगणक) जितना कठिन है। उन फ़ंक्शंस को प्रमाणित रूप से सुरक्षित क्रिप्टोग्राफ़िक हैश फ़ंक्शन कहा जाता है।

परिभाषा

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

पीआर [के ← जी(1ⁿ), (x₁, एक्स₂) ← ए(के, 1ⁿ) एस.टी. एक्स₁ ≠ एक्स₂ लेकिन एच_k(एक्स₁) = एच_k(एक्स₂)] < उपेक्षा(n),

जहां negl(·) कुछ नगण्य फ़ंक्शन को दर्शाता है, और n सुरक्षा पैरामीटर है।

तर्क

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

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

यह भी देखें

• कोलीजन का हमला
• प्रीइमेज हमला
• एनआईएसटी हैश फ़ंक्शन प्रतियोगिता
• सिद्ध रूप से सुरक्षित क्रिप्टोग्राफ़िक हैश फ़ंक्शन
• त्रुटि का पता लगाना और सुधार करना