क्रिप्टोग्राफिक हैश फ़ंक्शन प्रत्येक संभावित मान तक पहुंचते हैं, उदा। क्या वे प्रक्षेपित हैं?

Question

एक सामान्य रूप से प्रयुक्त बाइनरी हैश फ़ंक्शन लें - उदाहरण के लिए, SHA-256। जैसा कि नाम का तात्पर्य है, यह 256 बिट मान आउटपुट करता है।

ए सभी संभावित 256 बिट बाइनरी मानों का सेट बनें। ए बेहद बड़ा है, लेकिन सीमित है।

बी सभी संभावित बाइनरी मानों का सेट बनें। बी अनंत है।

सीबी के हर सदस्य पर SHA-256 चल रहा द्वारा प्राप्त मूल्यों का वह समूह बनें। जाहिर है यह अभ्यास में नहीं किया जा सकता है, लेकिन मुझे लगता है कि हम अभी भी इसके गणितीय विश्लेषण कर सकते हैं।

मेरे प्रश्न: आवश्यकता करके, सी ⊆ एक। लेकिन सी = ए है?

संपादित करें: जैसा कि कुछ उत्तरों द्वारा इंगित किया गया था, यह पूरी तरह से प्रश्न में कार्य करने पर निर्भर है। इसलिए, यदि आप किसी विशेष हैश फ़ंक्शन के लिए उत्तर जानते हैं, तो कृपया ऐसा कहें!

Answer 1

सबसे पहले, मान लें कि SHA-256 इनपुट के रूप में सभी संभावित बाइनरी तारों को स्वीकार नहीं करता है। जैसा कि FIPS 180-3 द्वारा परिभाषित किया गया है, SHA-256 इनपुट के रूप में स्वीकार करता है 2^64 बिट्स (यानी 1844674407370 9 551615 बिट्स से अधिक नहीं) की लंबाई के बिट्स के किसी अनुक्रम को इनपुट के रूप में स्वीकार करता है। यह बहुत आम है; सभी हैश फ़ंक्शन किसी भी तरह औपचारिक इनपुट लंबाई में सीमित हैं।एक कारण यह है कि सुरक्षा की धारणा को कम्प्यूटेशनल लागत के संबंध में परिभाषित किया गया है; कम्प्यूटेशनल पावर के बारे में एक सीमा है कि किसी भी हमलावर को जरूरी है। किसी दिए गए लम्बाई से परे इनपुट को केवल अधिकतम गणना करने के लिए उस अधिकतम कम्प्यूटेशनल पावर की आवश्यकता होगी। संक्षेप में, क्रिप्टोग्राफर्स infinites से बहुत सावधान हैं, क्योंकि infinites सुरक्षा को भी परिभाषित होने से रोकते हैं, अकेले मात्रा निर्धारित करते हैं। तो अपने इनपुट सेट सी2^64-1 बिट तक दृश्यों के लिए प्रतिबंधित किया जाना चाहिए।

कहा जा रहा है, चलो देखते हैं कि क्या बारे में हैश समारोह surjectivity जाना जाता रहा है।

हैश फंक्शन एक यादृच्छिक प्रामाणिक, एक वैचारिक वस्तु जो केवल बाधा है कि यह पिछले इनपुट और आउटपुट "याद" के अंतर्गत यादृच्छिक पर आउटपुट का चयन करता है अनुकरण करने के लिए प्रयास करें, और, अगर एक पहले से ही देखा इनपुट दिया, यह एक ही रिटर्न पहले से उत्पादन। परिभाषा के अनुसार, एक यादृच्छिक ऑरैकल केवल इनपुट की कोशिश करके और आउटपुट स्पेस को थकाऊ करके अनुमानित सिद्ध किया जा सकता है। यदि आउटपुट का आकार n बिट्स है, तो यह अनुमान है कि 2^(2n) आकार 2^n के आउटपुट स्पेस को निकालने के लिए अलग-अलग इनपुट की आवश्यकता होगी। एन = 256 के लिए, इसका मतलब है कि के बारे में 2^512 संदेशों (जैसे 512 बिट के सभी संदेशों) hashing पर्याप्त (औसतन) होना चाहिए। SHA-256, बहुत बहुत लंबे समय तक 512 बिट (वास्तव में, यह आदानों 18446744073709551615 बिट्स स्वीकार करता है) की तुलना में आदानों स्वीकार करता है तो ऐसा लगता है अत्यधिक प्रशंसनीय कि SHA-256 surjective है।

हालांकि, यह साबित नहीं किया गया है कि SHA-256 surjective है, और कहा कि उम्मीदहै। जैसा कि ऊपर दिखाया गया है, एक यादृच्छिक ऑरैकल के लिए एक प्रक्षेपण प्रमाण के लिए कंप्यूटिंग पावर की एक बहुत बड़ी आवश्यकता होती है, जो कि अनुमानों (2^एन) और टकराव (2^(एन/2)) जैसे हमलों से काफी अधिक है। नतीजतन, एक अच्छा हैश फ़ंक्शन "प्रॉपर्टी" जैसी संपत्ति को वास्तव में साबित करने की अनुमति नहीं देनी चाहिए। यह बहुत संदिग्ध होगा: हैश फ़ंक्शन की सुरक्षा उनकी आंतरिक संरचना की अव्यवस्था से उत्पन्न होती है, और ऐसी अव्यवस्था को दृढ़ता से गणितीय विश्लेषण के किसी भी प्रयास का विरोध करना चाहिए।

परिणामस्वरूप, surjectivity औपचारिक रूप से किसी भी सभ्य हैश फंक्शन के लिए सिद्ध नहीं है, और न इस तरह के MD4 के रूप में "टूटा" हैश फंक्शन के लिए भी। यह केवल "अत्यधिक संदिग्ध" है (उत्पादन के मुकाबले इनपुट के साथ एक यादृच्छिक ओरेकल प्रक्षेपण होना चाहिए)।

Answer 2

आवश्यक नहीं है। कबूतर सिद्धांत बताता है कि ए के आकार से एक बार एक और हैश उत्पन्न हुआ है कि 1 की टकराव की संभावना है, लेकिन यह नहीं बताता है कि ए के प्रत्येक तत्व को उत्पन्न किया गया है।

Answer 3

आवश्यक नहीं है। वह हैश फ़ंक्शन पर निर्भर करेगा।

यह संभवतः आदर्श होगा यदि हैश फ़ंक्शन surjective था, लेकिन ऐसी चीजें हैं जो आम तौर पर अधिक महत्वपूर्ण होती हैं, जैसे टकराव की संभावना कम होती है।

Answer 4

यह हमेशा ऐसा नहीं होता है। हालांकि, एक हैश एल्गोरिथ्म के लिए आवश्यक गुणवत्ता कर रहे हैं:

• बी की प्रमुखता
हैश की
• Repartition बी में (बी में हर मूल्य एक ही संभावना होना आवश्यक है एक हैश होने के लिए)

Answer 5

यह वास्तव में हैश फ़ंक्शन पर निर्भर करता है। आप इस वैध हैश फंक्शन का उपयोग करते हैं:

Int256 Hash (string input) { 
    return 0; 
} 

तो यह स्पष्ट है कि सी = ए तो "उदाहरण के लिए, SHA256" विचार करने के लिए एक बहुत महत्वपूर्ण नोट है!।

अपने वास्तविक प्रश्न का उत्तर देने के लिए: मुझे विश्वास है, लेकिन मैं बस अनुमान लगा रहा हूं। विकिपीडिया इस पर कोई सार्थक जानकारी प्रदान नहीं करता है।