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




bit-manipulation hash probability xor (9)

एक्सर हैश को गठबंधन करने का "डिफ़ॉल्ट" तरीका हो सकता है लेकिन ग्रेग हेगिल का जवाब यह भी दिखाता है कि इसका नुकसान क्यों है: दो समान हैश मानों का xor शून्य है। वास्तविक जीवन में, समान हैश एक अपेक्षा की तुलना में अधिक आम हैं। फिर आप पाएंगे कि इन (इतने कम नहीं) कोने के मामलों में, परिणामस्वरूप संयुक्त हैंश हमेशा एक ही (शून्य) होते हैं। हैश टकराव बहुत अधिक होगा, आप अपेक्षा से अधिक बार।

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

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

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

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

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


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


हैरिंग के दौरान उपयोग करने के लिए 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 बिट हस्ताक्षरित पूर्णांक।


यदि आप एक पक्षपातपूर्ण इनपुट के साथ एक यादृच्छिक इनपुट XOR , आउटपुट यादृच्छिक है। AND या OR लिए भी यह सच नहीं है। उदाहरण:

00101001 XOR 00000000 = 00101001
00101001 AND 00000000 = 00000000
00101001 OR  11111111 = 11111111

जैसा कि @ ग्रेग हेगिल का उल्लेख है, भले ही दोनों इनपुट यादृच्छिक हैं, एंड्रॉइड या OR का उपयोग करके पक्षपातपूर्ण आउटपुट होगा।

XOR उपयोग कुछ और जटिल पर करने का कारण यह है कि, अच्छी तरह से, कोई ज़रूरत नहीं है: XOR पूरी तरह से काम करता है, और यह चमकदार रूप से बेवकूफ है।


ऐसा कुछ है जो मैं स्पष्ट रूप से उन लोगों के लिए इंगित करना चाहता हूं जो इस पृष्ठ को ढूंढते हैं। और और ब्लूराजा जैसे आउटपुट को प्रतिबंधित करें - डैनी 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 कितने तार्किक कार्यों में यह समान आउटपुट वितरण है? एक्सओआर आपके प्रश्न में बताए गए उद्देश्य के लिए सबसे उपयुक्त क्यों है?


hashCode() में hashCode() विभिन्न संस्करणों के लिए स्रोत कोड ठोस, सामान्य उपयोग हैशिंग एल्गोरिदम के लिए एक महान संदर्भ है। उन्हें आसानी से समझा जाता है और अन्य प्रोग्रामिंग भाषाओं में अनुवाद किया जाता है।

काफी बोलते हुए, अधिकांश बहु-गुण hashCode() कार्यान्वयन इस पैटर्न का पालन करते हैं:

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

आप 31 पीछे जादू के बारे में अधिक जानकारी के लिए अन्य Q & As खोज सकते हैं, और क्यों जावा कोड इसे अक्सर उपयोग करता है। यह अपूर्ण है, लेकिन इसमें बहुत अच्छी सामान्य प्रदर्शन विशेषताएं हैं।


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

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

यदि इस तरह उन्होंने मशीन में देखा, तो आप 50/50 वितरण प्राप्त करने के लिए निम्न-आदेश बिट का परीक्षण कर सकते हैं। हालांकि, आईईईई फ्लोट्स को मंटिसा के 2 गुना की शक्ति के रूप में दर्शाया जाता है; फ्लोट में एक फ़ील्ड 2 की शक्ति है (साथ ही एक निश्चित ऑफ़सेट)। 2 की शक्ति का चयन किया जाता है ताकि "मंटिसा" भाग हमेशा एक संख्या> = 1.0 और <2.0 हो। इसका मतलब है कि, वास्तव में, 0.0000 अलावा अन्य संख्याओं का प्रतिनिधित्व इस प्रकार किया जाएगा:

0.0001 = 2^(-4) x 1.000
0.0010 = 2^(-3) x 1.000
0.0011 = 2^(-3) x 1.100
0.0100 = 2^(-2) x 1.000
... 
0.0111 = 2^(-2) x 1.110
0.1000 = 2^(-1) x 1.000
0.1001 = 2^(-1) x 1.001
...
0.1110 = 2^(-1) x 1.110
0.1111 = 2^(-1) x 1.111

(द्विआधारी बिंदु से पहले 1 एक अंतर्निहित मूल्य है; 32- और 64-बिट फ्लोट के लिए, वास्तव में इस 1 को पकड़ने के लिए आवंटित नहीं किया जाता है।)

लेकिन उपरोक्त को देखते हुए यह प्रदर्शित करना चाहिए कि क्यों, यदि आप बिट्स को प्रतिनिधित्व को परिवर्तित करते हैं और कम बिट देखते हैं, तो आपको समय का शून्य 75% मिलेगा। यह 0.5 (बाइनरी 0.1000 ) से कम सभी मानों के कारण है, जो संभवतः आधे संभावित मूल्य हैं, जिनके 0.1000 स्थानांतरित किया गया है, जिससे 0 कम बिट में दिखाई दे रहा है। स्थिति अनिवार्य रूप से वही होती है जब मंटिसा में 52 बिट्स (अंतर्निहित 1 सहित) double नहीं होता है।

(असल में, जैसा कि @Sneftel ने एक टिप्पणी में सुझाव दिया है, हम वितरण में 16 से अधिक संभावित मूल्यों को शामिल कर सकते हैं:

0.0001000 with probability 1/128
0.0001001 with probability 1/128
...
0.0001111 with probability 1/128
0.001000  with probability 1/64
0.001001  with probability 1/64
...
0.01111   with probability 1/32 
0.1000    with probability 1/16
0.1001    with probability 1/16
...
0.1110    with probability 1/16
0.1111    with probability 1/16

लेकिन मुझे यकीन नहीं है कि यह अधिकांश प्रकार के वितरण की अपेक्षा करेगा, इसलिए यह संभवतः सार्थक नहीं है। इसके अलावा यह आपको अधिक लाभ नहीं देता है जब मानों को पूर्णांक उत्पन्न करने के लिए उपयोग किया जाता है, क्योंकि यादृच्छिक फ़्लोटिंग-पॉइंट मान अक्सर होते हैं।)