cryptography - एक्सओआर हैश को गठबंधन करने का डिफ़ॉल्ट तरीका क्यों है?




bit-manipulation hash (6)

आप सीआरसी का उपयोग कर सकते हैं और एक्सओआर करने के बजाए अपनी रैखिक संपत्ति पर भरोसा कर सकते हैं। यहां एक अच्छी व्याख्या है: https://crypto.stackexchange.com/questions/699/understanding-crc

मान लें कि आपके पास दो हैंश H(A) और H(B) और आप उन्हें गठबंधन करना चाहते हैं। मैंने पढ़ा है कि दो हैंश को गठबंधन करने का एक अच्छा तरीका XOR है, उदाहरण के लिए XOR( H(A), H(B) )

मैंने पाया है कि सबसे अच्छा स्पष्टीकरण इन हैश फ़ंक्शन दिशानिर्देशों पर संक्षेप में छुआ है:

मोटे तौर पर यादृच्छिक वितरण परिणामों के साथ दो नंबरों को एक्सओर करना, अभी भी लगभग किसी भी संख्या में यादृच्छिक वितरण * के साथ, लेकिन जो अब दो मानों पर निर्भर करता है।
...
* दो संख्याओं के प्रत्येक बिट को गठबंधन करने के लिए, 0 0 आउटपुट होता है यदि दो बिट बराबर होते हैं, अन्यथा 1. दूसरे शब्दों में, 50% संयोजनों में, 1 आउटपुट होगा। तो यदि दो इनपुट बिट्स में 0 या 1 होने का लगभग 50-50 मौका होता है, तो आउटपुट बिट भी होगा।

क्या आप अंतर्ज्ञान और / या गणित के बारे में बता सकते हैं कि XOR को हैश फ़ंक्शंस (OR या AND आदि के बजाय) के संयोजन के लिए डिफ़ॉल्ट ऑपरेशन क्यों होना चाहिए?


इसके आसान बिट-मिक्सिंग गुणों के बावजूद, एक्सओआर अपनी कम्यूटिटी के कारण हैश को गठबंधन करने का एक अच्छा तरीका नहीं है। गौर करें कि क्या होगा यदि आपने 10-टुपल्स की हैश तालिका में {1, 2, ..., 10} के क्रमपरिवर्तन संग्रहित किए हों।

एक बेहतर विकल्प m * H(A) + H(B) , जहां एम एक बड़ी विषम संख्या है।

क्रेडिट: उपरोक्त combiner बॉब जेनकींस से एक टिप था।


ऐसा कुछ है जो मैं स्पष्ट रूप से उन लोगों के लिए इंगित करना चाहता हूं जो इस पृष्ठ को ढूंढते हैं। और और ब्लूराजा जैसे आउटपुट को प्रतिबंधित करें - डैनी Pflughoe इंगित करने की कोशिश कर रहा है, लेकिन बेहतर परिभाषित किया जा सकता है:

सबसे पहले मैं इसे समझाने के लिए उपयोग किए जाने वाले दो सरल कार्यों को परिभाषित करना चाहता हूं: न्यूनतम () और अधिकतम ()।

न्यूनतम (ए, बी) ए और बी के बीच छोटा मान वापस कर देगा, उदाहरण के लिए: न्यूनतम (1, 5) 1 लौटाता है।

अधिकतम (ए, बी) ए और बी के बीच बड़ा मान लौटाएगा, उदाहरण के लिए: अधिकतम (1, 5) 5 लौटाता है।

यदि आपको दिया गया है: C = A AND B

फिर आप पाएंगे कि C <= Min(A, B) हम इसे जानते हैं क्योंकि आप कुछ भी नहीं कर सकते हैं और ए या बी के 0 बिट्स के साथ उन्हें 1 एस बना सकते हैं। तो हर शून्य बिट शून्य बिट रहता है और हर एक बिट को शून्य बिट बनने का मौका होता है (और इस प्रकार एक छोटा मान)।

के साथ: C = A OR B

इसके विपरीत सत्य है: C >= Max(A, B) इसके साथ, हम अनुक्रम को और कार्य में देखते हैं। किसी भी बिट जो पहले से ही एक शून्य होने के लिए ऑर्डर नहीं किया जा सकता है, इसलिए यह एक रहता है, लेकिन प्रत्येक शून्य बिट में एक बनने का मौका होता है, और इस प्रकार एक बड़ी संख्या होती है।

इसका तात्पर्य है कि इनपुट की स्थिति आउटपुट पर प्रतिबंध लागू करती है। यदि आप और 90 के साथ कुछ भी, तो आप जानते हैं कि आउटपुट 90 के बराबर या उससे कम होगा चाहे अन्य मूल्य क्या है।

एक्सओआर के लिए, इनपुट के आधार पर कोई निहित प्रतिबंध नहीं है। ऐसे विशेष मामले हैं जहां आप पाते हैं कि यदि आप उलटा होने से 255 के साथ एक बाइट एक्सओआर करते हैं लेकिन किसी भी संभावित बाइट उस से आउटपुट हो सकता है। प्रत्येक बिट को अन्य ऑपरेंड में एक ही बिट के आधार पर राज्य को बदलने का मौका होता है।


बाएं 2 कॉलम को कवर करें और आउटपुट का उपयोग कर इनपुट का उपयोग करने का प्रयास करें।

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

जब आपने 1-बिट देखा तो आपको यह पता होना चाहिए था कि दोनों इनपुट 1 थे।

अब एक्सओआर के लिए ऐसा ही करें

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

एक्सओआर इनपुट के बारे में कुछ भी नहीं देता है।


समान रूप से यादृच्छिक (1-बिट) इनपुट मानते हुए, और फ़ंक्शन आउटपुट संभाव्यता वितरण 75% 0 और 25% 1 । इसके विपरीत, या 25% 0 और 75% 1

एक्सओआर फ़ंक्शन 50% 0 और 50% 1 , इसलिए यह समान संभावना वितरण के संयोजन के लिए अच्छा है।

यह सच तालिकाओं को लिखकर देखा जा सकता है:

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

 a | b | a OR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    1

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

व्यायाम: दो 1-बिट इनपुट a और b कितने तार्किक कार्यों में यह समान आउटपुट वितरण है? एक्सओआर आपके प्रश्न में बताए गए उद्देश्य के लिए सबसे उपयुक्त क्यों है?


हैरिंग के दौरान उपयोग करने के लिए xor एक खतरनाक डिफ़ॉल्ट फ़ंक्शन है। यह और से या बेहतर है, लेकिन यह ज्यादा नहीं कहता है।

xor सममित है, इसलिए तत्वों का क्रम खो गया है। तो "bad" हैश हैश को "dab" रूप में जोड़ देगा।

xor शून्य के समान मानों को मानचित्र करता है, और आपको शून्य पर "सामान्य" मान मैपिंग से बचना चाहिए:

तो (a,a) 0 पर मैप हो जाता है, और (b,b) को 0 तक मैप किया जाता है। चूंकि ऐसे जोड़े यादृच्छिकता से अधिक आम हैं, तो आप शून्य से कई टकरावों को समाप्त कर सकते हैं।

इन दो समस्याओं के साथ, xor एक हैश combiner होने के समाप्त होता है जो सतह पर आधा सभ्य दिखता है, लेकिन आगे निरीक्षण के बाद नहीं।

आधुनिक हार्डवेयर पर, आमतौर पर जितना तेज़ xor के रूप में जोड़ते हैं (यह संभवतः इसे खींचने के लिए अधिक शक्ति का उपयोग करता है, स्वीकार्य रूप से)। जोड़ना सच्चाई तालिका प्रश्न में थोड़ा सा xor के समान है, लेकिन जब दोनों मान 1 हैं तो यह अगले बिट पर थोड़ा सा भेजता है। इससे कम जानकारी मिटा दी जाती है।

तो hash(a) + hash(b) उसमें बेहतर है यदि a==b , परिणाम इसके बजाय hash(a)<<1 बजाय hash(a)<<1

यह सममित रहता है। हम इस समरूपता को मामूली लागत के लिए तोड़ सकते हैं:

hash(a)<<1 + hash(a) + hash(b)

उर्फ hash(a)*3 + hash(b) । ( hash(a) गणना करना hash(a) बार और भंडारण की सलाह दी जाती है यदि आप शिफ्ट समाधान का उपयोग करते हैं)। 3 बजाए कोई अजीब स्थिरता एक size_t (या के-बिट हस्ताक्षरित स्थिरांक) को अपने आप में जोड़ देगा, क्योंकि बिना हस्ताक्षरित स्थिरांक पर मानचित्र कुछ के लिए गणित मॉड्यूलो 2^k , और कोई विषम स्थिरता 2^k अपेक्षाकृत प्रमुख है।

यहां तक ​​कि एक प्रशंसक संस्करण के लिए, हम boost::hash_combine जांच कर सकते हैं, जो प्रभावी रूप से है:

size_t hash_combine( size_t lhs, size_t rhs ) {
  lhs^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
  return lhs;
}

यहां हम seed कुछ स्थानांतरित संस्करणों को एक स्थिर के साथ जोड़ते हैं (जो मूल रूप से यादृच्छिक 0 एस और 1 एस है - विशेष रूप से यह 32 बिट निश्चित बिंदु अंश के रूप में सुनहरा अनुपात के विपरीत है) कुछ अतिरिक्त और एक xor के साथ। यह समरूपता को तोड़ता है, और कुछ "शोर" पेश करता है यदि आने वाले शेड मूल्य खराब होते हैं (यानी, प्रत्येक घटक की 0 हैश की कल्पना करें - उपरोक्त इसे अच्छी तरह से संभालता है, प्रत्येक गठबंधन के बाद 1 और 0 एस की धुंध उत्पन्न करता है। मेरा बस एक आउटपुट करता है 0 )।

उन लोगों के लिए जो सी / सी ++ से परिचित नहीं हैं, एक size_t एक हस्ताक्षरित पूर्णांक मान है जो स्मृति में किसी ऑब्जेक्ट के आकार का वर्णन करने के लिए काफी बड़ा है। 64 बिट सिस्टम पर, यह आमतौर पर 64 बिट हस्ताक्षरित पूर्णांक होता है। 32 बिट सिस्टम पर, एक 32 बिट हस्ताक्षरित पूर्णांक।