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

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

जन्मदिन विरोधाभास टकराव प्रतिरोध पर एक ऊपरी सीमा रखता है: यदि एक हैश फ़ंक्शन आउटपुट के एन बिट उत्पन्न करता है, तो एक हमलावर जो केवल 2 की गणना करता है^एन/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 सुरक्षा पैरामीटर है।

तर्क

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

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

यह भी देखें

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