SHA1 टकराव की संभावना

Question

बराबर लंबाई के 100 अलग-अलग तारों के सेट को देखते हुए, आप संभावना को कैसे माप सकते हैं कि तारों के लिए SHA1 पाचन टकराव असंभव है ...?

Answer 1

160 बिट हैश मान SHA-1 इतना बड़ा सुनिश्चित करने के लिए हर ब्लॉक के फिंगरप्रिंट अद्वितीय है द्वारा उत्पन्न कर रहे हैं? एक समान वितरण के साथ यादृच्छिक हैश मान मान लिया जाये, n अलग डेटा ब्लॉक का एक संग्रह है और एक हैश समारोह है कि ख बिट्स उत्पन्न करता है, संभावना पी नहीं होगा कि एक या एक से अधिक टकराव जोड़े की संख्या से घिरा है ब्लॉक की संख्या संभावना से एक दी गई जोड़ी टक्कर लगी होगी।

(स्रोत: http://bitcache.org/faq/hash-collision-probabilities)

Answer 2

यह Birthday Problem है - यह आलेख अच्छा अनुमान प्रदान करता है जो संभाव्यता का अनुमान लगाने में काफी आसान बनाता है। वास्तविक संभावना बहुत कम होगी - उदाहरण के लिए this question देखें।

Answer 3

ठीक है, टकराव की संभावना 1 - ((2^160 - 1)/2^160) * ((2^160 - 2)/2^160) * ... * (2^160 - 99)/2^160)।

10 की जगह में 2 वस्तुओं की टक्कर की संभावना के बारे में सोचें। पहला आइटम संभावना 100% के साथ अद्वितीय है। दूसरी संभावना 9/10 के साथ अद्वितीय है। इसलिए अद्वितीय होने की संभावना 100% * 9 0% है, और टकराव की संभावना 1 - (100% * 9 0%), या 1 - ((10 - 0)/10) * ((10 - 1)/10), या 1 - ((10 - 1)/10)।

यह बहुत ही असंभव है। रिमोट संभावना होने के लिए आपको कई और तारों की आवश्यकता होगी।

this page on Wikipedia पर तालिका पर एक नज़र डालें; 128 बिट्स और 256 बिट्स के लिए पंक्तियों के बीच बस इंटरपोलेट करें।