अपना खुद का एमडी 5 टकराव बनाएं

Question

मैं एमडी 5 टकराव पर एक प्रेजेंटेशन कर रहा हूं और मैं लोगों को यह जानना चाहता हूं कि टकराव कितनी संभावना है।

यह अच्छा होगा कि पाठ के दो ब्लॉक हैं जो एक ही चीज़ के हैंश है, और यह बताएं कि टक्कर मारने से पहले [ए-जेए-जेड] के कितने संयोजन की आवश्यकता थी।

स्पष्ट उत्तर हैश प्रत्येक संभावित संयोजन है जब तक कि दो हिट समान न हो। तो आप इसे कोडिंग के बारे में कैसे जाना होगा। एक त्वरित प्रयोग के रूप में मैंने [ए-जेड] के 5 कॉलम के प्रत्येक संयोजन को हिसिंग करने की कोशिश की, इसे .NET हैशटेबल में संग्रहीत किया और टकराव अपवाद को पकड़ लिया। इसके साथ दो समस्याएं - हैशटेबल अंततः समाप्त हो गया है, और मुझे पूरा यकीन है कि मुझे बहुत अधिक पात्रों की आवश्यकता होगी।

स्पष्ट रूप से यह डेटा संरचना मेमोरी में संभालने के लिए बहुत बड़ी है, इसलिए अब मुझे डेटाबेस शामिल करना होगा। एज़ूर का परीक्षण करने के लिए एक अच्छी परियोजना की तरह लगता है - these guys की तरह थोड़ा।

क्या कोई मुझे कुशल इस दिशा के तरीके से इंगित कर सकता है?

Answer 1

इनमें निम्नलिखित दो अलग-अलग 128 बाइट दृश्यों एक ही करने के लिए हैश:

MD5 हैश: 79054025255fb1a26e4bc422aef54eb4

नीचे अंतर पर प्रकाश डाला जाता है (बोल्ड)। क्षमा करें यह देखना मुश्किल है।

 
d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70 

और

 
d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70 

टक्कर/block1 के दृश्य (स्रोत: Links.Org)

टक्कर/block2 के दृश्य (स्रोत: Links.Org)

Answer 2

मैं Hashcash पर एक नज़र डालेगा। एक प्रभावी हैश एल्गोरिदम के साथ, एमडी 5 की तरह, बिट्स की संख्या के साथ घातीय होने के लिए टकराव की गणना करने का समय। हैशकैश क्या आंशिक टकराव की गणना करता है। यही है, हैश के निचले 16 बिट्स का कहना है। मैच के लिए कम 16 बिट्स प्राप्त करने के लिए, किसी को औसतन 2^15 अलग-अलग संयोजनों का उपयोग करना होगा। यदि आप जानते हैं कि 16, 24, या 32 बिट टकराव के साथ आने में कितना समय लगता है, तो आप आसानी से बिट्स की उच्च संख्या के लिए गणना कर सकते हैं।

Answer 3

यदि आप इस बारे में बात कर रहे हैं कि सीधी टक्कर कितनी संभावना है - एक जहां एक कारण का कोई जानबूझकर प्रयास नहीं है - तो आप निराश होने जा रहे हैं: आपको औसत 2^64 सादे टेक्स्ट पहले उत्पन्न करना होगा आप टकराव देखने की उम्मीद कर सकते हैं, और यह उचित है कि आप उचित (या वास्तव में, यहां तक ​​कि एक _un_reasonable) समय में करने में सक्षम होने के लिए काफी अधिक हैं।

यदि आप जानबूझकर टकराव तैयार करने की कठिनाई का प्रदर्शन करना चाहते हैं, तो अन्य उत्तरों ने पहले से ही इसका प्रदर्शन किया है। तारों को पूरी तरह से पाठ्यचर्या की आवश्यकता के अतिरिक्त बाधा को भी, हालांकि, उन दृष्टिकोणों को काफी हद तक अव्यवहारिक बनाता है।

Answer 4

इस तरह के हैंश का पूरा बिंदु यह है कि टकराव बेहद असंभव हैं।आप मौके से एक उत्पन्न नहीं कर रहे हैं - सफल होने से पहले आपकी मशीन लगभग बुढ़ापे से मर जाएगी। यदि आप उचित रूप से टक्कर उत्पन्न कर सकते हैं तो हैश का उपयोग करने का पूरा बिंदु दूर जाएगा!

Answer 5

केवल टेक्स्ट फ़ाइलों, AFAIK के साथ ऐसा करना मुश्किल है। आप कुछ टकराव प्राप्त कर सकते हैं, लेकिन उन्हें केवल [ए-जेए-जेड] से भी होना आसान नहीं है (अभी तक)।

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

उदा। देखें this problem (एच 2 भाग) और solution। उदाहरण के लिए, this PS file और this one में एक ही MD5sum है लेकिन वे अच्छी तरह से बनाई गई पोस्टस्क्रिप्ट फ़ाइलों दोनों हैं जिनके पास आप उन्हें खोलते समय पूरी तरह से अलग पाठ रखते हैं।